Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6 (5.3) — ACDM: ϕk−f∗≤(nk+1)2[2∥x0−x∗∥12+1n2(f(x0)−f∗)]\phi_k-f^*\le\big(\frac n{k+1}\big)^2\big[2\|x_0-x^*\|_1^2+\frac1{n^2}(f(x_0)-f^*)\big]ϕk​−f∗≤(k+1n​)2[2∥x0​−x∗∥12​+n21​(f(x0​)−f∗)]

Proved
NesterovRCD.Accelerated.theorem6

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

accelerated-methodscomplexity-boundsconvex-optimizationcoordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let f:RN→Rf:\mathbb R^N\to\mathbb Rf:RN→R, RN=Rn1×⋯×Rnn\mathbb R^N=\mathbb R^{n_1}\times\cdots\times\mathbb R^{n_n}RN=Rn1​×⋯×Rnn​ with n≥1n\ge1n≥1 blocks, each Rni\mathbb R^{n_i}Rni​ carrying a Euclidean norm (3.4), and let ∥⋅∥1\|\cdot\|_1∥⋅∥1​ be the norm (3.5), ∥x∥12=∑iLi∥x(i)∥(i)2\|x\|_1^2=\sum_iL_i\|x^{(i)}\|_{(i)}^2∥x∥12​=∑i​Li​∥x(i)∥(i)2​. Assume:

  1. fff has a coordinate-wise Lipschitz gradient (2.2) with constants Li>0L_i>0Li​>0;
  2. fff is strongly convex (3.1) in ∥⋅∥1\|\cdot\|_1∥⋅∥1​ with a known parameter σ\sigmaσ, 0≤σ<n20\le\sigma<n^20≤σ<n2 (σ=0\sigma=0σ=0 meaning convexity);
  3. x∗x^*x∗ is a minimizer of fff and f∗=f(x∗)f^*=f(x^*)f∗=f(x∗);
  4. s↦s#s\mapsto s^\#s↦s# is any selection of (1.8) on each block.

Let ACDM(x0)(x_0)(x0​) (5.1) run with independent uniform draws, ϕk=Eξk−1f(xk)\phi_k=\mathbb E_{\xi_{k-1}}f(x_k)ϕk​=Eξk−1​​f(xk​), and

D=2∥x0−x∗∥12+1n2(f(x0)−f∗).D=2\|x_0-x^*\|_1^2+\frac1{n^2}\big(f(x_0)-f^*\big).D=2∥x0​−x∗∥12​+n21​(f(x0​)−f∗).

Then for every k≥0k\ge0k≥0:

  1. if σ>0\sigma>0σ>0,
ϕk−f∗≤σD⋅[(1+σ2n)k+1−(1−σ2n)k+1]−2≤(nk+1)2D;\phi_k-f^*\le\sigma D\cdot\Big[\Big(1+\frac{\sqrt\sigma}{2n}\Big)^{k+1}-\Big(1-\frac{\sqrt\sigma}{2n}\Big)^{k+1}\Big]^{-2}\le\Big(\frac n{k+1}\Big)^2D;ϕk​−f∗≤σD⋅[(1+2nσ​​)k+1−(1−2nσ​​)k+1]−2≤(k+1n​)2D;
  1. in all cases (σ≥0\sigma\ge0σ≥0),
ϕk−f∗≤(nk+1)2D.\phi_k-f^*\le\Big(\frac n{k+1}\Big)^2D.ϕk​−f∗≤(k+1n​)2D.

The accelerated scheme thus improves the O(n/k)O(n/k)O(n/k) expected rate of the plain random coordinate descent method to O(n2/k2)O(n^2/k^2)O(n2/k2), and for σ>0\sigma>0σ>0 the first bound decreases geometrically, asymptotically by the factor (1+σ/(2n))−2(1+\sqrt\sigma/(2n))^{-2}(1+σ​/(2n))−2 per iteration.

Formalization Note The paper states (5.3) as one chain for every σ≥0\sigma\ge0σ≥0. At σ=0\sigma=0σ=0 the middle expression is 0⋅[0]−20\cdot[0]^{-2}0⋅[0]−2, which the paper reads as its limit (n/(k+1))2D(n/(k+1))^2D(n/(k+1))2D, while Lean evaluates it to 000; so the chain is stated for σ>0\sigma>0σ>0, and the outer bound separately for all σ≥0\sigma\ge0σ≥0. The standing assumptions of §2 (convexity, a nonempty optimal set, Li>0L_i>0Li​>0, n≥1n\ge1n≥1), the Euclidean block norms and σ<n2\sigma<n^2σ<n2 (implicit in (5.1), whose αk\alpha_kαk​ divides by n2−σn^2-\sigman2−σ) are explicit hypotheses; σ\sigmaσ is any valid convexity parameter. Blocks are inner-product spaces E i indexed by Fin n; the draws are explicit sequences and ϕk\phi_kϕk​ is the finite average acdmPhi over all nkn^knk draw sequences with weight n−kn^{-k}n−k.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Mathlib
import Definitions.Def_NesterovRCD_HighProb_Basic
import Definitions.Def_NesterovRCD_Accelerated_ACDM
Formal statement
namespace NesterovRCD.Accelerated

theorem theorem6 {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)]
    [∀ i, InnerProductSpace ℝ (E i)] [∀ i, FiniteDimensional ℝ (E i)] (hn : 0 < n)
    (f : NesterovRCD.Sublinear.Blocks E → ℝ) (L : Fin n → ℝ) (hL : NesterovRCD.Sublinear.CoordLipschitz f L)
    (σ : ℝ) (hσ0 : 0 ≤ σ) (hσn : σ < (n : ℝ) ^ 2) (hsc : NesterovRCD.HighProb.StronglyConvexW f L 1 σ)
    (sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : NesterovRCD.Sublinear.IsSharpSelection sharp)
    (x0 xs : NesterovRCD.Sublinear.Blocks E) (hxs : NesterovRCD.Sublinear.IsMinimizer f xs) (k : ℕ) :
    (0 < σ →
      acdmPhi f L sharp σ x0 k - f xs
        ≤ σ * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs))
          / ((1 + Real.sqrt σ / (2 * n)) ^ (k + 1) - (1 - Real.sqrt σ / (2 * n)) ^ (k + 1)) ^ 2 ∧
      σ * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs))
          / ((1 + Real.sqrt σ / (2 * n)) ^ (k + 1) - (1 - Real.sqrt σ / (2 * n)) ^ (k + 1)) ^ 2
        ≤ ((n : ℝ) / (k + 1)) ^ 2 * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs))) ∧
    acdmPhi f L sharp σ x0 k - f xs
      ≤ ((n : ℝ) / (k + 1)) ^ 2 * (2 * NesterovRCD.Sublinear.wnorm L 1 (x0 - xs) ^ 2 + 1 / (n : ℝ) ^ 2 * (f x0 - f xs)) := by sorry

end NesterovRCD.Accelerated
Source
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper 2010/2, p. 15, Theorem 6, (5.3)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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