Theorem 4.2 — under µ-strong convexity, E[φ(x̄_T) − φ(x*)] ≤ µ‖x₀−x*‖²/(T+2)² + 16𝖫²/(µ(T+2))
ProvedStochModelWC.StrongCvx.theorem_4_2Setting. Minimize over , where is closed with nonempty domain and is locally Lipschitz. Suppose Assumption B holds with and with the functions -strongly convex for some (): stochastic models , exact in expectation at the base point and lower-bounding in expectation, with a random Lipschitz constant satisfying . Run Algorithm 4.1 from with ,
on i.i.d. samples . Let be any minimizer of .
Conclusion. For every integer , the function inside the expectation below is integrable and
The weights , , sum to one, so the averaged point lies in .
The theorem gives the function-gap rate for stochastic model-based minimization (stochastic proximal point, prox-linear and proximal subgradient methods) under strong convexity, extending the nonuniform averaging technique of Schmidt, Le Roux and Bach to the fully proximal setting.
Formalization Note The paper prints in place of . Its proof sums the first display of the proof (p. 23), which comes from (4.8); the proof of (4.8) yields the constant , not the printed , and this doubles the term of the final bound. The statement is what the proof establishes; whether the printed bound with also holds was not settled. Expectations are integrals against ; the minimizer is a point of with for all . The paper's of Algorithm 4.1 does not affect the iterates: any satisfies for every . -strong convexity is encoded as -weak convexity, which in a Euclidean space is the same notion. The constant is L in Lean and is Lfun.
import Mathlib import Definitions.Def_StochModelWC_ModelBased_Basic import Definitions.Def_StochModelWC_ModelBased_AssumptionB open MeasureTheory Filter Topology
namespace StochModelWC.StrongCvx
/-- Theorem 4.2 (p. 23): in the strongly convex setting (`τ = 0`, `f_x(·, ξ) + r` `μ`-strongly convex for some
`μ > 0`, i.e. Assumption B with `η = -μ`), Algorithm 4.1 with `β_t = μ (t + 1) / 2`, run on `T + 1` i.i.d. samples
`ω = (ξ₀, …, ξ_T) ∼ P^{⊗(T+1)}`, satisfies, for every `T > 0` and any minimizer `x*` of `φ = f + r`,
`E[φ(x̄_T) − φ(x*)] ≤ μ‖x₀ − x*‖² / (T + 2)² + 16 L² / (μ (T + 2))`,
where `x̄_T = 2 / ((T + 2)(T + 3) − 2) · Σ_{t=1}^{T+1} (t + 1) x_t` (weights summing to one, so `x̄_T ∈ D`), and
`φ(x̄_T)` is integrable. The paper prints `8 L²`; its proof, run with the constant of (4.8) that the proof of
Lemma 4.2 (p. 21) establishes, yields `16 L²`. -/
theorem theorem_4_2 {d : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(U D : Set (EuclideanSpace ℝ (Fin d))) (f r : EuclideanSpace ℝ (Fin d) → ℝ)
(model : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d) → Ω → ℝ)
(L : ℝ) (Lfun : Ω → ℝ) (μ : ℝ) (hμ : 0 < μ)
(hD : D.Nonempty) (hr : StochModelWC.ModelBased.IsClosedFn D r) (hf : LocallyLipschitz f)
(hB : StochModelWC.ModelBased.AssumptionB P U D f r model 0 (-μ) L Lfun)
(upd : ℕ → EuclideanSpace ℝ (Fin d) → Ω → EuclideanSpace ℝ (Fin d))
(hupd : StochModelWC.ModelBased.IsAlg41Step P U D r model (fun t => μ * ((t : ℝ) + 1) / 2) upd)
(x0 : EuclideanSpace ℝ (Fin d)) (hx0 : x0 ∈ U)
(xstar : EuclideanSpace ℝ (Fin d)) (hxstar : xstar ∈ D)
(hmin : ∀ y ∈ D, f xstar + r xstar ≤ f y + r y)
(T : ℕ) (hT : 0 < T) :
Integrable (fun ω : Fin (T + 1) → Ω =>
f ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t)
+ r ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t))
(Measure.pi fun _ : Fin (T + 1) => P) ∧
∫ ω, (f ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t)
+ r ((2 / (((T : ℝ) + 2) * ((T : ℝ) + 3) - 2)) •
∑ t ∈ Finset.Icc 1 (T + 1), ((t : ℝ) + 1) • StochModelWC.ModelBased.run upd x0 ω t)
- (f xstar + r xstar)) ∂(Measure.pi fun _ : Fin (T + 1) => P) ≤
μ * ‖x0 - xstar‖ ^ 2 / ((T : ℝ) + 2) ^ 2 + 16 * L ^ 2 / (μ * ((T : ℝ) + 2)) := by sorry
end StochModelWC.StrongCvx
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.