Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7, item 2, (6.2) — RACDM satisfies φk−f∗≤8nR12(x0)/(16+3k)\varphi_k-f^*\le 8nR_1^2(x_0)/(16+3k)φk​−f∗≤8nR12​(x0​)/(16+3k)

Proved
NesterovRCD.Adaptive.theorem7_rate

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

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

Let n≥1n\ge1n≥1 and let f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R be convex and differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants L1,…,LnL_1,\dots,L_nL1​,…,Ln​:

∣∇if(x+uei)−∇if(x)∣≤Li∣u∣(x∈Rn, u∈R, i=1,…,n).|\nabla_i f(x+ue_i)-\nabla_i f(x)|\le L_i|u|\qquad(x\in\mathbb R^n,\ u\in\mathbb R,\ i=1,\dots,n).∣∇i​f(x+uei​)−∇i​f(x)∣≤Li​∣u∣(x∈Rn, u∈R, i=1,…,n).

Assume fff attains its minimum f∗=f(x∗)f^*=f(x^*)f∗=f(x∗). Let ∥x∥1=(∑iLixi2)1/2\|x\|_1=\big(\sum_iL_ix_i^2\big)^{1/2}∥x∥1​=(∑i​Li​xi2​)1/2 be the norm (2.7) with α=1\alpha=1α=1, and let R≥R1(x0)R\ge R_1(x_0)R≥R1​(x0​), that is, ∥x−y∗∥1≤R\|x-y^*\|_1\le R∥x−y∗∥1​≤R for every xxx with f(x)≤f(x0)f(x)\le f(x_0)f(x)≤f(x0​) and every minimizer y∗y^*y∗ of fff. Run RACDM(x0)(x_0)(x0​) (6.1) with initial estimates Li0∈(0,Li]L_i^0\in(0,L_i]Li0​∈(0,Li​] and coordinates i0,i1,…i_0,i_1,\dotsi0​,i1​,… drawn independently and uniformly from {1,…,n}\{1,\dots,n\}{1,…,n}, and let φk=Ef(xk)\varphi_k=\mathbb E f(x_k)φk​=Ef(xk​) be the expectation over the first kkk draws. Then for every k≥0k\ge0k≥0,

φk−f∗ ≤ 8nR216+3k.\varphi_k-f^*\ \le\ \frac{8nR^2}{16+3k}.φk​−f∗ ≤ 16+3k8nR2​.

This is item 2 of Theorem 7, the main result of §6.1: a coordinate descent method that only has lower bounds Li0L_i^0Li0​ on the coordinate Lipschitz constants, and adjusts them by doubling and halving without computing function values, keeps the O(nR12(x0)/k)O(nR_1^2(x_0)/k)O(nR12​(x0​)/k) rate of RCDM(0,x0)(0,x_0)(0,x0​) (compare (2.14), φk−f∗≤2nR12(x0)/(k+4)\varphi_k-f^*\le 2nR_1^2(x_0)/(k+4)φk​−f∗≤2nR12​(x0​)/(k+4)) at the cost of a constant factor.

Formalization Note Rn\mathbb R^nRn is EuclideanSpace ℝ (Fin n) (scalar coordinates: the paper sets N=nN=nN=n in §6.1), coordinates are indexed 0,…,n−10,\dots,n-10,…,n−1 for the paper's 1,…,n1,\dots,n1,…,n, and the gradient is an explicit map ggg with g(x)=∇f(x)g(x)=\nabla f(x)g(x)=∇f(x), as in the published definition ConvexOptAlg_CoordDescent_Defs that this mission reuses (its IsCoordSmooth f g L is (2.2) with one-dimensional blocks and ∣⋅∣|\cdot|∣⋅∣ as block norm; it includes differentiability). The expectation is the published rcdExpect L 0 k, a finite sum over all draws (i0,…,ik−1)(i_0,\dots,i_{k-1})(i0​,…,ik−1​) weighted by ∏sp0(is)\prod_s p_0(i_s)∏s​p0​(is​), p0≡1/np_0\equiv1/np0​≡1/n; no measure theory is involved. The paper's R1(x0)=max⁡x{max⁡x∗∈X∗∥x−x∗∥1:f(x)≤f(x0)}R_1(x_0)=\max_x\{\max_{x^*\in X^*}\|x-x^*\|_1: f(x)\le f(x_0)\}R1​(x0​)=maxx​{maxx∗∈X∗​∥x−x∗∥1​:f(x)≤f(x0​)} is not computed: the theorem takes any upper bound RRR of it (when the maximum is finite it is the least such RRR, so the statement is the paper's). The paper's standing assumption "X∗X^*X∗ nonempty" is the hypothesis that x∗x^*x∗ minimizes fff; "X∗X^*X∗ bounded" is implied by the existence of RRR. The initial estimates are positive and at most LiL_iLi​ as in the setup of (6.1); n≥1n\ge1n≥1 is implicit in the paper. Step 3 of (6.1) is read as L^ik:=12L^ik\hat L_{i_k}:=\frac12\hat L_{i_k}L^ik​​:=21​L^ik​​ (a typo in the paper; see the definition).

Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_CoordDescent_Defs
import Definitions.Def_NesterovRCD_Adaptive_RACDM
Formal statement
namespace NesterovRCD.Adaptive

open ConvexOptAlg.CoordDescent

/-- Theorem 7, item 2, (6.2), p. 18: for convex, coordinate-wise smooth `f` with a minimizer
`x*`, initial estimates `L⁰_i ∈ (0, L_i]`, and `R ≥ R_1(x₀)` (every point of the level set
`{f ≤ f(x₀)}` is within `‖·‖_1`-distance `R` of every minimizer), RACDM(x₀) with uniform draws
satisfies `φ_k − f* ≤ 8 n R² / (16 + 3k)` for every `k ≥ 0`, where `φ_k = E f(x_k)`. -/
theorem theorem7_rate {n : ℕ} (hn : 0 < n) (f : Vec n → ℝ) (g : Vec n → Vec n)
    (hconv : ConvexOn ℝ Set.univ f) (L : Fin n → ℝ) (hL : IsCoordSmooth f g L)
    (L0 : Fin n → ℝ) (hL0 : ∀ i, 0 < L0 i ∧ L0 i ≤ L i) (x0 xs : Vec n)
    (hxs : ∀ y, f xs ≤ f y) (R : ℝ)
    (hR : ∀ x, f x ≤ f x0 → ∀ ys, (∀ y, f ys ≤ f y) → wnorm L 1 (x - ys) ≤ R) (k : ℕ) :
    rcdExpect L 0 k (fun idx => f (racdm g L0 x0 k idx).1) - f xs ≤
      8 * n * R ^ 2 / (16 + 3 * k) := by sorry

end NesterovRCD.Adaptive
Source
Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, CORE Discussion Paper 2010/2, p. 18, Theorem 7, item 2, (6.2); R_1(x_0) as defined in Theorem 1, p. 7
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