Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — RCDM(α,x0)(\alpha,x_0)(α,x0​): φk−f∗≤2k+4[∑jLjα]R1−α2(x0)\varphi_k-f^*\le\frac2{k+4}\big[\sum_jL_j^\alpha\big]R^2_{1-\alpha}(x_0)φk​−f∗≤k+42​[∑j​Ljα​]R1−α2​(x0​)

Proved
NesterovRCD.Sublinear.theorem1

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

convergence-rateconvex-optimizationcoordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithms

Let 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 carrying a norm ∥⋅∥(i)\|\cdot\|_{(i)}∥⋅∥(i)​. Let f:RN→Rf:\mathbb R^N\to\mathbb Rf:RN→R be convex and differentiable, with coordinate-wise Lipschitz continuous gradient (2.2) with constants L1,…,Ln>0L_1,\dots,L_n>0L1​,…,Ln​>0, and let x∗x_*x∗​ be a minimizer of fff, f∗=f(x∗)f^*=f(x_*)f∗=f(x∗​). Fix α∈R\alpha\in\mathbb Rα∈R and a starting point x0x_0x0​, and let R≥R1−α(x0)R\ge R_{1-\alpha}(x_0)R≥R1−α​(x0​), where

Rβ(x0)=max⁡x{max⁡x∗∈X∗∥x−x∗∥β: f(x)≤f(x0)}.R_\beta(x_0)=\max_x\Big\{\max_{x_*\in X_*}\|x-x_*\|_\beta:\ f(x)\le f(x_0)\Big\}.Rβ​(x0​)=xmax​{x∗​∈X∗​max​∥x−x∗​∥β​: f(x)≤f(x0​)}.

Run the random coordinate descent method RCDM(α,x0)(\alpha,x_0)(α,x0​): at step kkk draw iki_kik​ independently with Pr⁡(ik=i)=Liα/∑jLjα\Pr(i_k=i)=L_i^\alpha/\sum_jL_j^\alphaPr(ik​=i)=Liα​/∑j​Ljα​ and set xk+1=Tik(xk)=xk−1LikUikfik′(xk)#x_{k+1}=T_{i_k}(x_k)=x_k-\frac1{L_{i_k}}U_{i_k}f'_{i_k}(x_k)^\#xk+1​=Tik​​(xk​)=xk​−Lik​​1​Uik​​fik​′​(xk​)#, where s#s^\#s# is any vector of Arg max⁡x[⟨s,x⟩−12∥x∥2]\operatorname{Arg\,max}_x[\langle s,x\rangle-\frac12\|x\|^2]Argmaxx​[⟨s,x⟩−21​∥x∥2]. Then the expected value φk=Eξk−1f(xk)\varphi_k=E_{\xi_{k-1}}f(x_k)φk​=Eξk−1​​f(xk​) satisfies, for every k≥0k\ge0k≥0,

φk−f∗≤2k+4⋅[∑j=1nLjα]⋅R2.\varphi_k-f^*\le\frac2{k+4}\cdot\Big[\sum_{j=1}^nL_j^\alpha\Big]\cdot R^2 .φk​−f∗≤k+42​⋅[j=1∑n​Ljα​]⋅R2.

This is the paper's first global efficiency estimate: random coordinate descent converges in expectation at the rate O(1/k)O(1/k)O(1/k), with a constant governed by the sum SαS_\alphaSα​ of powers of the coordinate Lipschitz constants rather than by the global Lipschitz constant. For α=0\alpha=0α=0 (uniform sampling) it gives 2nk+4R12(x0)\frac{2n}{k+4}R_1^2(x_0)k+42n​R12​(x0​), and for α=1\alpha=1α=1 it gives 2k+4S1R02(x0)\frac2{k+4}S_1R_0^2(x_0)k+42​S1​R02​(x0​).

Formalization Note The paper states the bound with R1−α(x0)R_{1-\alpha}(x_0)R1−α​(x0​) itself; we state it for every upper bound RRR of R1−α(x0)R_{1-\alpha}(x_0)R1−α​(x0​), which is equivalent whenever the max is finite (the paper assumes X∗X_*X∗​ bounded) and avoids a junk value of a supremum. The standing assumptions of §2 (p. 4: fff convex and differentiable, X∗X_*X∗​ nonempty) are hypotheses; Li>0L_i>0Li​>0 and n≥1n\ge1n≥1 are implicit in the paper (the method divides by LiL_iLi​ and samples from {1,…,n}\{1,\dots,n\}{1,…,n}) and stated explicitly. α\alphaα ranges over all of R\mathbb RR as in (2.5). The blocks are Fin n with 0-based indices, each a finite-dimensional real normed space; the dual norm is the operator norm; the choice of s#s^\#s# is arbitrary (IsSharpSelection); φk\varphi_kφk​ is the finite sum over all index sequences of length kkk weighted by the product of their probabilities.

Preamble
import Mathlib
import Definitions.Def_NesterovRCD_Sublinear_Basic
Formal statement
namespace NesterovRCD.Sublinear

variable {n : ℕ} {E : Fin n → Type*} [∀ i, NormedAddCommGroup (E i)] [∀ i, NormedSpace ℝ (E i)]
  [∀ i, FiniteDimensional ℝ (E i)]

theorem theorem1 (hn : 0 < n) (f : Blocks E → ℝ) (hconv : ConvexOn ℝ Set.univ f)
    (L : Fin n → ℝ) (hL : CoordLipschitz f L)
    (sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : IsSharpSelection sharp)
    (α : ℝ) (x0 xs : Blocks E) (hxs : IsMinimizer f xs)
    (R : ℝ) (hR : LevelRadiusLE f L (1 - α) x0 R) (k : ℕ) :
    expect (prob L α) k (fun idx => f (rcdm f L sharp x0 k idx)) - f xs
      ≤ 2 / ((k : ℝ) + 4) * S L α * R ^ 2 := by sorry

end NesterovRCD.Sublinear
Source
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper 2010/2, p. 7, Theorem 1, (2.12)
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