Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 — for n ≥ 8L/μ, SAG with α = 1/(2nμ) after an SG pass satisfies E[g(xᵏ) − g(x*)] ≤ C(1 − 1/(8n))ᵏ for k ≥ n

Proved
SAG.LargeStep.proposition_2

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

finite-sumlinear-convergencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-optimizationvariance-reduction

Throughout, f1,…,fn:Rp→Rf_1,\dots,f_n:\mathbb R^p\to\mathbb Rf1​,…,fn​:Rp→R (n≥1n\ge1n≥1) are convex and differentiable with LLL-Lipschitz gradients fi′f_i'fi′​, the average g=1n∑ifig=\frac1n\sum_i f_ig=n1​∑i​fi​ is μ\muμ-strongly convex (x↦g(x)−μ2∥x∥2x\mapsto g(x)-\frac\mu2\|x\|^2x↦g(x)−2μ​∥x∥2 is convex, μ>0\mu>0μ>0), x∗x^*x∗ minimizes ggg, g′=1n∑ifi′g'=\frac1n\sum_i f_i'g′=n1​∑i​fi′​ and σ2=1n∑i∥fi′(x∗)∥2\sigma^2=\frac1n\sum_i\|f_i'(x^*)\|^2σ2=n1​∑i​∥fi′​(x∗)∥2.

Assume n≥8Lμn\ge\frac{8L}{\mu}n≥μ8L​. Consider the run in which the first nnn iterations use stochastic gradient from x0x^0x0 with step sizes γj=1/(2L+μ2j)\gamma_j=1/(2L+\frac\mu2j)γj​=1/(2L+2μ​j), SAG is then initialized with the average xn=1n∑j=0n−1x~jx^n=\frac1n\sum_{j=0}^{n-1}\tilde x^jxn=n1​∑j=0n−1​x~j of the stochastic gradient iterates and with all yiy_iyi​ set to zero, and the subsequent SAG iterations use step size αk=12nμ\alpha_k=\frac1{2n\mu}αk​=2nμ1​; all indices are independent and uniform on {1,…,n}\{1,\dots,n\}{1,…,n}. Then for every k≥nk\ge nk≥n

E[g(xk)−g(x∗)]≤C(1−18n)k,C=16L3n∥x0−x∗∥2+4σ23nμ(8log⁡(1+μn4L)+1).\mathbb E\big[g(x^k)-g(x^*)\big]\le C\Big(1-\frac1{8n}\Big)^k,\qquad C=\frac{16L}{3n}\|x^0-x^*\|^2+\frac{4\sigma^2}{3n\mu}\Big(8\log\Big(1+\frac{\mu n}{4L}\Big)+1\Big).E[g(xk)−g(x∗)]≤C(1−8n1​)k,C=3n16L​∥x0−x∗∥2+3nμ4σ2​(8log(1+4Lμn​)+1).

The paper explains: "We state this result for k≥nk\ge nk≥n because we assume that the first nnn iterations of the algorithm use an SG method and that we initialize the subsequent SAG iterations with the average of the iterates, which leads to an O((log⁡n)/k)O((\log n)/k)O((logn)/k) rate. In contrast, using the SAG iterations from the beginning gives the same rate but with a constant proportional to nnn. Note that this bound is obtained when initializing all yiy_iyi​ to zero after the SG phase."

When n≥8L/μn\ge8L/\mun≥8L/μ, each pass through the data thus reduces the expected suboptimality by the factor (1−18n)n≤e−1/8(1-\frac1{8n})^n\le e^{-1/8}(1−8n1​)n≤e−1/8, independently of μ\muμ and LLL.

Formalization Note The run is hybrid (see its definition for the index bookkeeping: kkk indices are drawn, the stochastic gradient phase uses the first n−1n-1n−1, index nnn is unused, SAG uses the last k−nk-nk−n). The expectation is the uniform average over all nkn^knk index sequences.

Preamble
import Mathlib
import Definitions.Def_SAGA_Convex_finiteSum
import Definitions.Def_SAGA_Convex_sagaRun
import Definitions.Def_SAG_LargeStep_setting
import Definitions.Def_SAG_LargeStep_hybrid
Formal statement
namespace SAG.LargeStep

/-- Proposition 2, p. 6: if `n ≥ 8L/μ`, the run of `hybrid` (one pass of stochastic gradient
with `γ_j = 1/(2L + μj/2)`, average of its iterates, table reset to `0`, then SAG with
`α = 1/(2nμ)`) satisfies, for `k ≥ n`, `E[g(xᵏ) − g(x*)] ≤ C (1 − 1/(8n))ᵏ` with
`C = 16L/(3n)‖x⁰ − x*‖² + 4σ²/(3nμ)(8 log(1 + μn/(4L)) + 1)`. -/
theorem proposition_2 {p n : ℕ} (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
    (f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L μ : ℝ)
    (xstar : EuclideanSpace ℝ (Fin p)) (h : Assumptions f f' L μ xstar)
    (hn : 8 * L / μ ≤ (n : ℝ)) (x0 : EuclideanSpace ℝ (Fin p)) (k : ℕ) (hk : n ≤ k) :
    SAGA.Convex.expectIdx n k (fun js =>
        SAGA.Convex.fAvg f (hybrid f' L μ x0 js) - SAGA.Convex.fAvg f xstar)
      ≤ (16 * L / (3 * (n : ℝ)) * ‖x0 - xstar‖ ^ 2
          + 4 * sigmaSq f' xstar / (3 * (n : ℝ) * μ)
            * (8 * Real.log (1 + μ * (n : ℝ) / (4 * L)) + 1))
        * (1 - 1 / (8 * (n : ℝ))) ^ k := by sorry

end SAG.LargeStep
Source
Le Roux, Schmidt & Bach, A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets, arXiv:1202.6258v4, p. 6, Proposition 2 (and the paragraph after it); proof pp. 14–15 (§A.3), 23–30 (§A.6)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me