(30), first line, p.18 — the one-step inequality in expectation (corrected: Assumptions 3, 4, )
ProvedOnlineUBSR.eq_30Throughout, 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
Only the first line of (30) is formalized; the second line is not well formed as printed (its right side is random), and the next display of the proof follows from the first line alone.
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.
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)
- encoding: index n ≥ 1 with n − 1 on the right → index n ≥ 0 with n + 1 on the left; reason: renaming n − 1 to n; avoids natural-number subtraction
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 one-step inequality in expectation, (30) first line, p.18.**
Hegde, Menon, Prashanth & Jagannathan, arXiv:2111.08805v3, §7.1, (30), p.18: "Using (29) in (28) and taking total expectations, we obtain
E[z²n] ≤ exp(−2µ1an + L²1a²n) E[z²n−1] + a²nσ²"
With `z_n = t_n − SR_λ(X)`, for every `n ≥ 0` (the page's `n ≥ 1` with `n − 1` renamed `n`):
`E[z_{n+1}²] ≤ exp(−2μ₁a_{n+1} + L₁²a_{n+1}²) E[z_n²] + a_{n+1}² σ²`.
Only the first line of (30) is stated; its second line is not well-typed as printed (its
right-hand side is random) and is not needed for the next display.
**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`). -/
theorem eq_30
{Ω : 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 + 1) ω - ubsr μ ℓ lam X) ^ 2 ∂μ ≤
Real.exp (-2 * μ₁ * a (n + 1) + L₁ ^ 2 * a (n + 1) ^ 2) *
∫ ω, (iterate ℓ lam tl tu t₀ a ξ n ω - ubsr μ ℓ lam X) ^ 2 ∂μ +
a (n + 1) ^ 2 * σ ^ 2 := by sorry
end OnlineUBSR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.