Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4, (3.11) — RCDM(1,x0)(1,x_0)(1,x0​) on fμf_\mufμ​, μ=ϵ/(4R02(x0))\mu=\epsilon/(4R_0^2(x_0))μ=ϵ/(4R02​(x0​)): Prob(f(xk)−f∗≤ϵ)≥β\mathrm{Prob}(f(x_k)-f^*\le\epsilon)\ge\betaProb(f(xk​)−f∗≤ϵ)≥β

Proved
NesterovRCD.HighProb.theorem4

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

convex-optimizationcoordinate-descenthigh-probabilityp2o-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 carrying Euclidean norms ∥h(i)∥(i)2=⟨Bih(i),h(i)⟩\|h^{(i)}\|_{(i)}^2=\langle B_ih^{(i)},h^{(i)}\rangle∥h(i)∥(i)2​=⟨Bi​h(i),h(i)⟩ (3.4), and ∥h∥02=∑i∥h(i)∥(i)2\|h\|_0^2=\sum_i\|h^{(i)}\|_{(i)}^2∥h∥02​=∑i​∥h(i)∥(i)2​ (3.9). Let f:RN→Rf:\mathbb R^N\to\mathbb Rf:RN→R be convex with coordinate-wise Lipschitz gradient, constants Li>0L_i>0Li​>0 (2.2), and S1(f)=∑iLiS_1(f)=\sum_iL_iS1​(f)=∑i​Li​. Let x∗x_*x∗​ be a minimizer, f∗=f(x∗)f^*=f(x_*)f∗=f(x∗​), and let R>0R>0R>0 bound the size of the initial level set in ∥⋅∥0\|\cdot\|_0∥⋅∥0​:

∥x−x∗∥0≤Rwhenever f(x)≤f(x0) and x∗ minimizes f,\|x-x_*\|_0\le R\quad\text{whenever }f(x)\le f(x_0)\text{ and }x_*\text{ minimizes }f,∥x−x∗​∥0​≤Rwhenever f(x)≤f(x0​) and x∗​ minimizes f,

that is, R0(x0)≤RR_0(x_0)\le RR0​(x0​)≤R. Fix the accuracy ϵ>0\epsilon>0ϵ>0 and the confidence level β∈(0,1)\beta\in(0,1)β∈(0,1), define μ=ϵ/(4R2)\mu=\epsilon/(4R^2)μ=ϵ/(4R2) and the regularized objective fμ(x)=f(x)+μ2∥x−x0∥02f_\mu(x)=f(x)+\frac\mu2\|x-x_0\|_0^2fμ​(x)=f(x)+2μ​∥x−x0​∥02​, and choose kkk with

k ≥ 2[n+4S1(f)R2ϵ]⋅(ln⁡11−β+ln⁡(12+2S1(f)R2ϵ)).k\ \ge\ 2\Big[n+\frac{4S_1(f)R^2}{\epsilon}\Big]\cdot\Big(\ln\frac1{1-\beta}+\ln\Big(\frac12+\frac{2S_1(f)R^2}{\epsilon}\Big)\Big).k ≥ 2[n+ϵ4S1​(f)R2​]⋅(ln1−β1​+ln(21​+ϵ2S1​(f)R2​)).

Let xkx_kxk​ be generated by RCDM(1,x0)(1,x_0)(1,x0​) as applied to fμf_\mufμ​: block iii is drawn with probability (Li+μ)/(S1(f)+nμ)(L_i+\mu)/(S_1(f)+n\mu)(Li​+μ)/(S1​(f)+nμ), independently at each step, and xs+1=xs−1Lis+μUis(fμ)is′(xs)#x_{s+1}=x_s-\frac1{L_{i_s}+\mu}U_{i_s}(f_\mu)'_{i_s}(x_s)^\#xs+1​=xs​−Lis​​+μ1​Uis​​(fμ​)is​′​(xs​)#, with any choice of the vectors s#s^\#s# of (1.8). Then

Prob(f(xk)−f∗≤ϵ) ≥ β.\mathrm{Prob}\big(f(x_k)-f^*\le\epsilon\big)\ \ge\ \beta .Prob(f(xk​)−f∗≤ϵ) ≥ β.

A single run of randomized coordinate descent on the regularized problem therefore returns an ϵ\epsilonϵ-solution of the original problem with high probability, after a number of iterations that depends only logarithmically on the confidence level.

Formalization Note The paper takes R=R0(x0)R=R_0(x_0)R=R0​(x0​); here RRR is any positive upper bound of R0(x0)R_0(x_0)R0​(x0​) and μ=ϵ/(4R2)\mu=\epsilon/(4R^2)μ=ϵ/(4R2) is defined from it. The proof uses R0(x0)R_0(x_0)R0​(x0​) only through ∥x−x∗∥0≤R\|x-x_*\|_0\le R∥x−x∗​∥0​≤R on the level set, so the paper's statement is the case R=R0(x0)R=R_0(x_0)R=R0​(x0​); R>0R>0R>0 excludes R0(x0)=0R_0(x_0)=0R0​(x0​)=0, where the paper's μ\muμ is undefined. Explicit hypotheses: n≥1n\ge1n≥1, Li>0L_i>0Li​>0, fff convex, existence of a minimizer (standing assumptions of §2). The event concerns fff and f∗f^*f∗ of the original problem, while xkx_kxk​ comes from the run on fμf_\mufμ​ with fμf_\mufμ​'s constants Li+μL_i+\muLi​+μ (step and sampling). The probability is the finite sum ∑(i0,…,ik−1)∏sp(is) 1[f(xk)−f∗≤ϵ]\sum_{(i_0,\dots,i_{k-1})}\prod_sp(i_s)\,\mathbf 1[f(x_k)-f^*\le\epsilon]∑(i0​,…,ik−1​)​∏s​p(is​)1[f(xk​)−f∗≤ϵ] over draw sequences; blocks are Fin n, 0-based; Euclidean blocks are inner-product spaces EiE_iEi​.


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

open Classical
Formal statement
namespace NesterovRCD.HighProb

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

theorem theorem4 (hn : 0 < n) (f : NesterovRCD.Sublinear.Blocks E → ℝ) (hconv : ConvexOn ℝ Set.univ f)
    (L : Fin n → ℝ) (hL : NesterovRCD.Sublinear.CoordLipschitz f L)
    (sharp : ∀ i, (E i →L[ℝ] ℝ) → E i) (hsharp : NesterovRCD.Sublinear.IsSharpSelection sharp)
    (x0 xs : NesterovRCD.Sublinear.Blocks E) (hxs : NesterovRCD.Sublinear.IsMinimizer f xs)
    (R : ℝ) (hRpos : 0 < R) (hR : NesterovRCD.Sublinear.LevelRadiusLE f L 0 x0 R)
    (ε β : ℝ) (hε : 0 < ε) (hβ0 : 0 < β) (hβ1 : β < 1)
    (μ : ℝ) (hμ : μ = ε / (4 * R ^ 2)) (k : ℕ)
    (hk : 2 * ((n : ℝ) + 4 * NesterovRCD.Sublinear.S L 1 * R ^ 2 / ε) *
        (Real.log (1 / (1 - β)) + Real.log (1 / 2 + 2 * NesterovRCD.Sublinear.S L 1 * R ^ 2 / ε)) ≤ k) :
    β ≤ NesterovRCD.Sublinear.expect (NesterovRCD.Sublinear.prob (fun i => L i + μ) 1) k
      (fun idx => if f (NesterovRCD.Sublinear.rcdm (fReg f L μ x0) (fun i => L i + μ) sharp x0 k idx) - f xs ≤ ε
        then 1 else 0) := by sorry

end NesterovRCD.HighProb
Source
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper 2010/2, p. 11, Theorem 4, (3.11); ϵ > 0 and β ∈ (0,1) fixed on p. 10
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