Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§A.5 Step 2, pp. 22–23 — Q(θ)≥13∥x−x∗∥2Q(\theta)\ge\frac13\|x-x^*\|^2Q(θ)≥31​∥x−x∗∥2

Proved
SAG.SmallStep.lyapunov_dominates

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

lyapunov-functionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-form

Let n≥1n\ge1n≥1, let f1′,…,fn′:Rp→Rpf'_1,\dots,f'_n:\mathbb R^p\to\mathbb R^pf1′​,…,fn′​:Rp→Rp, x∗∈Rpx^*\in\mathbb R^px∗∈Rp and α>0\alpha>0α>0, and let QQQ be the Lyapunov function of §A.5 with step size α\alphaα. Then for every SAG state θ=(y,x)\theta=(y,x)θ=(y,x),

Q(θ)≥13∥x−x∗∥2.Q(\theta)\ge\frac13\|x-x^*\|^2 .Q(θ)≥31​∥x−x∗∥2.

Equivalently, P−(00013I)P-\begin{pmatrix}0&0\\0&\frac13I\end{pmatrix}P−(00​031​I​) is positive semidefinite.

This domination converts the linear convergence of EQ(θk)\mathbb EQ(\theta^k)EQ(θk) into the convergence of E∥xk−x∗∥2\mathbb E\|x^k-x^*\|^2E∥xk−x∗∥2 in Proposition 1.

Formalization Note The page shows it for α=12nL\alpha=\frac1{2nL}α=2nL1​ and writes "≻ 0 for n⩾2n\geqslant2n⩾2" at the end of its Schur-complement computation; its exact expression 23I−n(1−1/n)23n+1/n−2ee⊤n\frac23I-\frac{n(1-1/n)^2}{3n+1/n-2}\frac{ee^\top}{n}32​I−3n+1/n−2n(1−1/n)2​nee⊤​ is positive definite for every n≥1n\ge1n≥1, and neither it nor the claim depends on the value of α>0\alpha>0α>0. The statement is therefore made for every n≥1n\ge1n≥1 and every α>0\alpha>0α>0. No hypothesis on f′f'f′ or x∗x^*x∗ is needed.

Preamble
import Mathlib
import Definitions.Def_SAG_SmallStep_blockForm
import Definitions.Def_SAG_SmallStep_lyapunov
Formal statement
namespace SAG.SmallStep

/-- §A.5 Step 2 (arXiv:1202.6258v4, pp. 22–23): the Lyapunov function of §A.5 dominates
`⅓‖x − x*‖²`, `Q(θ) ≥ ⅓‖x − x*‖²` for every state `θ = (y, x)` and every step size `α > 0`. -/
theorem lyapunov_dominates {p n : ℕ} (hn : 0 < n)
    (f' : Fin n → EuclideanSpace ℝ (Fin p) → EuclideanSpace ℝ (Fin p))
    (xstar : EuclideanSpace ℝ (Fin p)) (α : ℝ) (hα : 0 < α)
    (θ : (Fin n → EuclideanSpace ℝ (Fin p)) × EuclideanSpace ℝ (Fin p)) :
    (1 / 3) * ‖θ.2 - xstar‖ ^ 2 ≤ lyapunov f' α xstar θ := 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, pp. 22–23, §A.5 Step 2
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