Theorem 1 — with an explicit constant (corrected: Assumption 3 on , Assumption 4 from , )
ProvedOnlineUBSR.theorem_1Let be a probability space and a random variable with a.s. (Assumption 2). Let be convex and differentiable, , , and the utility-based shortfall risk. Assume:
- (Assumption 1) , and ;
- (Assumption 3, corrected) and for all ;
- are independent random variables, each distributed as ;
- is deterministic, satisfies , and with ;
- (Assumption 4, corrected) with and , there is with a.s. for all .
Then for every
The projected stochastic approximation estimator therefore has mean-squared error , with an explicit constant, using one sample of per step; the initial error is forgotten at rate , faster than .
Formalization Note The iterates are OnlineUBSR.iterate with a k = c / k, is OnlineUBSR.noise, is OnlineUBSR.iterSigma, and is the real infimum OnlineUBSR.ubsr (finite here by OnlineUBSR.sr_is_root). Expectations are Bochner integrals and conditional expectations are condExp; all integrands are bounded a.s. The powers and are real powers. follows from and .
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
- 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: step size a_k = c/k → a k = c / k for k ≥ 1, a 0 unread; reason: the recursion never reads a 0
- encoding: "for all n" (Remark 2) → n ≥ 1; reason: (6) divides by n; at n = 0 the right side is undefined on the page
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
/-- **Theorem 1 (mean-squared error of the projected SA estimator of shortfall risk).**
Hegde, Menon, Prashanth & Jagannathan, arXiv:2111.08805v3, Theorem 1, p.5: "Suppose Assumptions 1 to 4 hold. Setting the step size ak = c/k with
1/2 < µ1c, we have E[(tn − SRλ(X))²] ≤ exp(L1²c²π²/6) [ (t0 − SRλ(X))²/n^{2µ1c} +
σ²2^{2µ1c}c²/((2µ1c − 1)n) ]. (6)" Proof: §7.1, pp.18–19.
Let `t_n` be the recursion (5) (`OnlineUBSR.iterate`) with step sizes `a_k = c/k`. Then for every
`n ≥ 1`,
`E[(t_n − SR_λ(X))²] ≤ exp(L₁²c²π²/6) ((t₀ − SR_λ(X))²/n^{2μ₁c} + σ²2^{2μ₁c}c²/((2μ₁c − 1)n))`.
**Formalization Note.** Hypotheses: `(Ω, μ)` 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 equals `g′(t)` only when `X ≡ 0`;
the proof uses `g′`); `σ > 0` with `E[ε_n² | 𝓕_n] ≤ σ²` a.s. for every `n ≥ 0` (Assumption 4,
corrected from `n ≥ 1`: the proof uses `n = 0`); `t₀ ∈ [t_l, t_u]` (corrected: the page leaves
`t₀` free). `ε_n` uses the fresh sample `ξ_{n+1}` (`OnlineUBSR.noise`); `𝓕_n` is the σ-field
generated by `t_0, …, t_n` (`OnlineUBSR.iterSigma`). `SR_λ(X)` is the real infimum (2)
(`OnlineUBSR.ubsr`), finite here by `OnlineUBSR.sr_is_root`. `t₀` is deterministic, samples are
indexed from `1` (`ξ 0`, `a 0` unread), the powers `n^{2μ₁c}` and `2^{2μ₁c}` are real powers, and
`n ≥ 1` because the bound divides by `n`. Monotonicity of `ℓ` and "λ in the interior of the
range of ℓ" are not assumed. `c > 0` follows from `μ₁ > 0` and `μ₁c > 1/2`. -/
theorem theorem_1
{Ω : 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)
(c : ℝ) (hc : 1 / 2 < μ₁ * c)
(hA4 : ∀ n : ℕ, μ[fun ω => noise μ ℓ lam X (iterate ℓ lam tl tu t₀ (fun k : ℕ => c / (k : ℝ)) ξ) ξ n ω ^ 2 |
iterSigma (iterate ℓ lam tl tu t₀ (fun k : ℕ => c / (k : ℝ)) ξ) n] ≤ᵐ[μ] fun _ => σ ^ 2)
(n : ℕ) (hn : 1 ≤ n) :
∫ ω, (iterate ℓ lam tl tu t₀ (fun k : ℕ => c / (k : ℝ)) ξ n ω - ubsr μ ℓ lam X) ^ 2 ∂μ ≤
Real.exp (L₁ ^ 2 * c ^ 2 * π ^ 2 / 6) *
((t₀ - ubsr μ ℓ lam X) ^ 2 / (n : ℝ) ^ (2 * μ₁ * c) +
σ ^ 2 * (2 : ℝ) ^ (2 * μ₁ * c) * c ^ 2 / ((2 * μ₁ * c - 1) * n)) := by sorry
end OnlineUBSR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.