pp.18–19 — the unrolled mean-squared error bound (corrected: Assumptions 3, 4, )
ProvedOnlineUBSR.unrolled_boundThroughout, is a probability space; is a random variable with a.s. (Assumption 2); are independent random variables, each distributed as ; is convex and differentiable; with , where (Assumption 1); with for (Assumption 3, corrected); ; for ; the iterates are with ; ; ; and with a.s. for all (Assumption 4, corrected). Write .
Then for every , with the deterministic ,
This is the bound for a general step sequence; Theorem 1 follows by inserting .
Formalization Note The step sequence is a general a : ℕ → ℝ (a 0 unread); the iterates are OnlineUBSR.iterate, is OnlineUBSR.noise, is OnlineUBSR.iterSigma, is OnlineUBSR.gFun and is the real infimum OnlineUBSR.ubsr. Expectations are Bochner integrals and conditional expectations are Mathlib's condExp; all integrands are bounded a.s. The sum over is empty when .
Differences from the source:
- correction: Assumption 3 (p.5): −L₁ ≤ −ℓ′(−t) ≤ −µ₁ for all t ∈ [t_l, t_u] → −L₁ ≤ g′(t) ≤ −µ₁ for all t ∈ [t_l, t_u], with g′ the derivative of g; reason: the printed form is false: X ≡ 10, t_l = 0, t_u = 2, a C¹ convex ℓ with ℓ′ = 0.1 on (−∞, −10] and ℓ′ = 1 on [−2, ∞), λ = ℓ(−11), c = 1, t₀ = 0 meet every printed assumption with µ₁ = L₁ = 1, yet E[z₁₀₀²] = 0.348 > 0.208, the right side of (6); the proof (p.18) uses bounds on g′(t) = −E[ℓ′(−X − t)], which is −ℓ′(−t) only when X ≡ 0
- correction: Assumption 4 (p.5): E[ε_n² | 𝓕_n] ≤ σ² a.s. for all n ≥ 1 → for all n ≥ 0; reason: the proof applies the bound to E[ε₀² | 𝓕₀] in (28) at n = 1; with the bound only for n ≥ 1, P(ξ = 1) = 10⁻⁴, P(ξ = 0) = 1 − 10⁻⁴, X = −ξ, a steep convex ℓ above 1, λ = −10⁻⁴, t_l = t₀ = −0.01, t_u = 110, c = 1 give E[z₁²] = 1.02 > 0.363, the right side of (6) at n = 1
- correction: t₀ unrestricted → t₀ ∈ [t_l, t_u]; reason: (28)–(30) use J₀ = J(t₀), and (27) holds only inside [t_l, t_u]; X ≡ 0, t_l = 0, t_u = 10, g(t) = 1 − t on [0, 10], ℓ(1) ≥ λ + 11, σ = 0.01, c = 1 and t₀ = −1 give t₁ = 10 and E[z₁²] = 81 > 20.7, the right side of (6) at n = 1
- reading: ε_n = ĝ(t_n) − g(t_n), with ĝ(t) = ℓ(ξ_n − t) − λ and the sample in ε_n unnamed → ε_n = ℓ(ξ_{n+1} − t_n) − λ − g(t_n), the fresh sample; reason: (26) writes t_n = Γ(t_{n−1} + a_n(g(t_{n−1}) + ε_{n−1})), so ε_{n−1} uses ξ_n; only this reading makes ε_n centred given 𝓕_n
- generalization: ℓ convex and monotone (§3, p.4) → ℓ convex (and differentiable, p.5); monotonicity not assumed; reason: only the root of g inside [t_l, t_u] is used, and convexity with Assumption 1 gives it; with a monotone ℓ the hypotheses are the page's
- encoding: λ in the interior of the range of ℓ (§2, p.3) → not assumed; reason: implied by Assumption 1 (g(t_l) > 0 > g(t_u)) and the continuity of the convex ℓ, so no instance changes
- generalization: step sizes a_k = c/k with 1/2 < µ₁c (Theorem 1) → any step sequence a with a_k > 0 for k ≥ 1; reason: the proof up to (30) uses a general a_n ("The passage leading up to (30) holds for any choice of stepsize", p.21); a_k = c/k is a special case
- encoding: the interval [t_l, t_u] of Assumption 3 and of Γ → t_l < t_u; reason: the page treats [t_l, t_u] as a nondegenerate interval; for a monotone ℓ, g(t_l) > 0 > g(t_u) forces it
- encoding: SR_λ(X) = inf{t ∈ ℝ : t + X ∈ A} (2) → the real sInf (OnlineUBSR.ubsr); reason: under the hypotheses the set is nonempty and bounded below (OnlineUBSR.sr_is_root), so the infimum is finite and no junk value occurs
- encoding: random variables; an i.i.d. sequence {ξ_i} from the distribution of −X; expectations → measurable functions on a probability space; ξ 1, ξ 2, … mutually independent (iIndepFun) and each identically distributed with −X; Bochner integrals and condExp; ξ 0 and a 0 unread; reason: same instances; every integrand is bounded a.s. and 𝓕_n is a sub-σ-algebra (verification files)
import Mathlib import Definitions.Def_OnlineUBSR_gFun import Definitions.Def_OnlineUBSR_acceptanceSet import Definitions.Def_OnlineUBSR_ubsr import Definitions.Def_OnlineUBSR_proj import Definitions.Def_OnlineUBSR_iterate import Definitions.Def_OnlineUBSR_noise import Definitions.Def_OnlineUBSR_iterSigma open MeasureTheory ProbabilityTheory Real
namespace OnlineUBSR
/-- **The unrolled bound, the display after "Hence, we obtain", pp.18–19.**
Hegde, Menon, Prashanth & Jagannathan, arXiv:2111.08805v3, §7.1, pp.18–19: "Hence, we obtain E[z²n] ≤ z²0 exp(−2µ1 Σ_{k=1}^n ak + L²1 Σ_{k=1}^n a²k) +
σ² Σ_{k=1}^n a²k exp(−2µ1 Σ_{j=k+1}^n aj + L²1 Σ_{j=k+1}^n a²j)"
With `z_n = t_n − SR_λ(X)` and the deterministic `z_0 = t₀ − SR_λ(X)`, for every `n ≥ 0`:
`E[z_n²] ≤ z_0² exp(−2μ₁ Σ_{k=1}^n a_k + L₁² Σ_{k=1}^n a_k²)
+ σ² Σ_{k=1}^n a_k² exp(−2μ₁ Σ_{j=k+1}^n a_j + L₁² Σ_{j=k+1}^n a_j²)`.
**Formalization Note.** The standing hypotheses are those of Theorem 1 (pp.4–5), for a general
positive step sequence `a` (`a 0` is never read): `(Ω, μ)` a probability space; `X` measurable with
`|X| ≤ M₀` a.s. (Assumption 2); the samples `ξ 1, ξ 2, …` measurable, independent and each
distributed as `−X`; `ℓ` convex and differentiable on `ℝ`; `t_l < t_u` with `g(t_l) > 0 > g(t_u)`
(Assumption 1); `μ₁, L₁ > 0` with `−L₁ ≤ g′(t) ≤ −μ₁` on `[t_l, t_u]` (Assumption 3, corrected:
the page bounds `−ℓ′(−t)`, which is `g′(t)` only when `X ≡ 0`); `σ > 0` with
`E[ε_n² | 𝓕_n] ≤ σ²` a.s. for every `n ≥ 0` (Assumption 4, corrected: the page says `n ≥ 1`,
the proof uses `n = 0`); `t₀ ∈ [t_l, t_u]` (corrected: the page leaves `t₀` free, but (27) is
applied at `k = 0`). `ε_n` uses the fresh sample `ξ_{n+1}` (`OnlineUBSR.noise`), and `𝓕_n` is
the σ-field of `t_0, …, t_n` (`OnlineUBSR.iterSigma`). Sums `Σ_{k=1}^n` are over `Finset.Icc 1 n` and `Σ_{j=k+1}^n` over
`Finset.Icc (k + 1) n` (empty when `k = n`). -/
theorem unrolled_bound
{Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
(X : Ω → ℝ) (hX : Measurable X)
(ξ : ℕ → Ω → ℝ) (hξ : ∀ n, Measurable (ξ (n + 1)))
(hind : iIndepFun (fun n => ξ (n + 1)) μ)
(hident : ∀ n, IdentDistrib (ξ (n + 1)) (fun ω => -X ω) μ μ)
(ℓ : ℝ → ℝ) (hℓconv : ConvexOn ℝ Set.univ ℓ) (hℓdiff : Differentiable ℝ ℓ)
(lam tl tu : ℝ) (htlu : tl < tu)
(hA1l : 0 < gFun μ ℓ lam X tl) (hA1u : gFun μ ℓ lam X tu < 0)
(M₀ : ℝ) (hA2 : ∀ᵐ ω ∂μ, |X ω| ≤ M₀)
(μ₁ L₁ : ℝ) (hμ₁ : 0 < μ₁) (hL₁ : 0 < L₁)
(hA3 : ∀ t ∈ Set.Icc tl tu,
-L₁ ≤ deriv (gFun μ ℓ lam X) t ∧ deriv (gFun μ ℓ lam X) t ≤ -μ₁)
(σ : ℝ) (hσ : 0 < σ)
(t₀ : ℝ) (ht₀ : t₀ ∈ Set.Icc tl tu)
(a : ℕ → ℝ) (ha : ∀ k, 1 ≤ k → 0 < a k)
(hA4 : ∀ n : ℕ, μ[fun ω => noise μ ℓ lam X (iterate ℓ lam tl tu t₀ a ξ) ξ n ω ^ 2 |
iterSigma (iterate ℓ lam tl tu t₀ a ξ) n] ≤ᵐ[μ] fun _ => σ ^ 2) :
∀ n : ℕ,
∫ ω, (iterate ℓ lam tl tu t₀ a ξ n ω - ubsr μ ℓ lam X) ^ 2 ∂μ ≤
(t₀ - ubsr μ ℓ lam X) ^ 2 *
Real.exp (-2 * μ₁ * ∑ k ∈ Finset.Icc 1 n, a k +
L₁ ^ 2 * ∑ k ∈ Finset.Icc 1 n, a k ^ 2) +
σ ^ 2 * ∑ k ∈ Finset.Icc 1 n, a k ^ 2 *
Real.exp (-2 * μ₁ * ∑ j ∈ Finset.Icc (k + 1) n, a j +
L₁ ^ 2 * ∑ j ∈ Finset.Icc (k + 1) n, a j ^ 2) := by sorry
end OnlineUBSR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.