Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1 — SAG with αk=1/(2nL)\alpha_k=1/(2nL)αk​=1/(2nL): E∥xk−x∗∥2≤(1−μ8Ln)k[3∥x0−x∗∥2+9σ24L2]\mathbb E\|x^k-x^*\|^2\le(1-\frac{\mu}{8Ln})^k[3\|x^0-x^*\|^2+\frac{9\sigma^2}{4L^2}]E∥xk−x∗∥2≤(1−8Lnμ​)k[3∥x0−x∗∥2+4L29σ2​]

Proved
SAG.SmallStep.proposition_1

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

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

Let f1,…,fn:Rp→Rf_1,\dots,f_n:\mathbb R^p\to\mathbb Rf1​,…,fn​:Rp→R, n≥1n\ge1n≥1, be convex and differentiable with gradients fi′f'_ifi′​ that are Lipschitz continuous with constant L>0L>0L>0, ∥fi′(x)−fi′(y)∥≤L∥x−y∥\|f'_i(x)-f'_i(y)\|\le L\|x-y\|∥fi′​(x)−fi′​(y)∥≤L∥x−y∥. Assume that the average g=1n∑i=1nfig=\frac1n\sum_{i=1}^nf_ig=n1​∑i=1n​fi​ is strongly convex with constant μ>0\mu>0μ>0, meaning that x↦g(x)−μ2∥x∥2x\mapsto g(x)-\frac\mu2\|x\|^2x↦g(x)−2μ​∥x∥2 is convex, and let x∗x^*x∗ be the minimizer of ggg. Put σ2=1n∑i=1n∥fi′(x∗)∥2\sigma^2=\frac1n\sum_{i=1}^n\|f'_i(x^*)\|^2σ2=n1​∑i=1n​∥fi′​(x∗)∥2.

Run the SAG iterations with the constant step size αk=12nL\alpha_k=\frac1{2nL}αk​=2nL1​ from x0∈Rpx^0\in\mathbb R^px0∈Rp and the zero table yi0=0y^0_i=0yi0​=0 for all iii, with indices i1,i2,…i_1,i_2,\dotsi1​,i2​,… independent and uniform on {1,…,n}\{1,\dots,n\}{1,…,n}. Then for every k≥1k\ge1k≥1,

E[∥xk−x∗∥2]≤(1−μ8Ln)k[3∥x0−x∗∥2+9σ24L2].\mathbb E\big[\|x^k-x^*\|^2\big]\le\Big(1-\frac{\mu}{8Ln}\Big)^k\Big[3\|x^0-x^*\|^2+\frac{9\sigma^2}{4L^2}\Big].E[∥xk−x∗∥2]≤(1−8Lnμ​)k[3∥x0−x∗∥2+4L29σ2​].

This is the first main result of the paper: an incremental method that evaluates a single component gradient per iteration converges linearly in expectation for strongly convex finite sums, unlike stochastic gradient methods, whose rate is sublinear.

Formalization Note Rp\mathbb R^pRp is EuclideanSpace ℝ (Fin p) and the indices are Fin n. The expectation is SAGA.Convex.expectIdx n k, the uniform average over all index sequences in {1,…,n}k\{1,\dots,n\}^k{1,…,n}k, i.e. the law of kkk i.i.d. uniform indices; the expectation is over the algorithm's randomness only. x∗x^*x∗ is a minimizer of ggg (∀ x, g x* ≤ g x); its uniqueness is a consequence. Each fif_ifi​ is convex as assumed in §A.1 (p. 13) and needed by the proof's co-coercivity step. The run is SAG.SmallStep.runFrom with step 1/(2nL)1/(2nL)1/(2nL) from (0,x0)(0,x^0)(0,x0). No restriction μ≤L\mu\le Lμ≤L is assumed (it follows when p≥1p\ge1p≥1).

Preamble
import Mathlib
import Definitions.Def_SAGA_Convex_finiteSum
import Definitions.Def_SAGA_Convex_sagaRun
import Definitions.Def_SAG_SmallStep_run
Formal statement
namespace SAG.SmallStep

/-- Proposition 1 (Le Roux–Schmidt–Bach, arXiv:1202.6258v4, p. 5). With the constant step size
`α = 1/(2nL)` and the table initialized to `y⁰ = 0`, the SAG iterates satisfy, for `k ≥ 1`,
`E‖xᵏ − x*‖² ≤ (1 − μ/(8Ln))ᵏ [3‖x⁰ − x*‖² + 9σ²/(4L²)]`, where `σ² = (1/n) ∑ᵢ ‖f'ᵢ(x*)‖²` and the
expectation is over `k` i.i.d. uniform indices. -/
theorem proposition_1 {p n : ℕ} (hn : 0 < n)
    (f : Fin n → EuclideanSpace ℝ (Fin p) → ℝ)
    (f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p)) (L μ : ℝ)
    (hL : 0 < L) (hμ : 0 < μ)
    (hgrad : ∀ i x, HasGradientAt (f i) (f' i x) x)
    (hconv : ∀ i, ConvexOn ℝ Set.univ (f i))
    (hlip : ∀ i x y, ‖f' i x - f' i y‖ ≤ L * ‖x - y‖)
    (hsc : ConvexOn ℝ Set.univ (fun x => SAGA.Convex.fAvg f x - μ / 2 * ‖x‖ ^ 2))
    (xstar : EuclideanSpace ℝ (Fin p))
    (hmin : ∀ x, SAGA.Convex.fAvg f xstar ≤ SAGA.Convex.fAvg f x)
    (x0 : EuclideanSpace ℝ (Fin p)) (k : ℕ) (hk : 1 ≤ k) :
    SAGA.Convex.expectIdx n k
        (fun js => ‖(runFrom f' (1 / (2 * (n : ℝ) * L)) (fun _ => 0, x0) js).2 - xstar‖ ^ 2)
      ≤ (1 - μ / (8 * L * (n : ℝ))) ^ k
        * (3 * ‖x0 - xstar‖ ^ 2 + 9 * ((1 / (n : ℝ)) * ∑ i, ‖f' i xstar‖ ^ 2) / (4 * L ^ 2)) := by sorry

end SAG.SmallStep
Source
Le Roux, Schmidt & Bach, A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets, arXiv:1202.6258v4, p. 5, Proposition 1 (standing assumptions p. 5, §3, and p. 13, §A.1; proof pp. 19–23, §A.5)
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