Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7, item 3, (6.3) — Nk≤2(k+1)+∑ilog⁡2(Li/Li0)N_k\le 2(k+1)+\sum_i\log_2(L_i/L_i^0)Nk​≤2(k+1)+∑i​log2​(Li​/Li0​)

Proved
NesterovRCD.Adaptive.theorem7_count

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

backtrackingcomplexitycoordinate-descentp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R be differentiable with coordinate-wise Lipschitz partial derivatives (2.2) with constants L1,…,LnL_1,\dots,L_nL1​,…,Ln​, and let the initial estimates satisfy Li0∈(0,Li]L_i^0\in(0,L_i]Li0​∈(0,Li​]. Run RACDM(x0)(x_0)(x0​) (6.1) from any x0x_0x0​ along any sequence of drawn coordinates i0,…,iki_0,\dots,i_ki0​,…,ik​, and let NkN_kNk​ be the total number of computations of directional derivatives in iterations 0,…,k0,\dots,k0,…,k: iteration jjj, which performs djd_jdj​ doublings in its loop, computes ∇ijf\nabla_{i_j}f∇ij​​f at dj+1d_j+1dj​+1 trial points. Then

Nk ≤ 2(k+1)+∑i=1nlog⁡2LiLi0.N_k\ \le\ 2(k+1)+\sum_{i=1}^n\log_2\frac{L_i}{L_i^0}.Nk​ ≤ 2(k+1)+i=1∑n​log2​Li0​Li​​.

This is item 3 of Theorem 7: on average the adaptive method costs about two directional derivatives per iteration, plus a one-time overhead logarithmic in the ratio of the true constants to the initial guesses.

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 count per iteration, pij(j)=dj+1p_{i_j}(j)=d_j+1pij​​(j)=dj​+1, is the one fixed by the paper's proof ("L^i′=12⋅2pi(j)−1⋅L^i\hat L'_i=\frac12\cdot2^{p_i(j)-1}\cdot\hat L_iL^i′​=21​⋅2pi​(j)−1⋅L^i​, in other words pi(j)=2+log⁡2[L^i′/L^i]p_i(j)=2+\log_2[\hat L'_i/\hat L_i]pi​(j)=2+log2​[L^i′​/L^i​]"): it counts the evaluations of ∇ijf\nabla_{i_j}f∇ij​​f at the trial points and not the evaluation of ∇ijf(xj)\nabla_{i_j}f(x_j)∇ij​​f(xj​); counting that one too would give 3(k+1)+∑ilog⁡2(Li/Li0)3(k+1)+\sum_i\log_2(L_i/L_i^0)3(k+1)+∑i​log2​(Li​/Li0​). The statement holds for every sequence of draws. The standing convexity of fff and the existence of a minimizer are not used and not assumed. log⁡2\log_2log2​ is Real.logb 2, applied to Li/Li0≥1L_i/L_i^0\ge1Li​/Li0​≥1.

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 3, (6.3), p. 18: after iteration `k` (iterations `0, …, k`, draws `idx`),
the total number `N_k` of computations of directional derivatives in RACDM (6.1) satisfies
`N_k ≤ 2(k + 1) + Σ_i log₂(L_i / L⁰_i)`. -/
theorem theorem7_count {n : ℕ} (f : Vec n → ℝ) (g : Vec n → Vec n) (L : Fin n → ℝ)
    (hL : IsCoordSmooth f g L) (L0 : Fin n → ℝ) (hL0 : ∀ i, 0 < L0 i ∧ L0 i ≤ L i)
    (x0 : Vec n) (k : ℕ) (idx : Fin (k + 1) → Fin n) :
    (numDerivs g L0 x0 k idx : ℝ) ≤ 2 * (k + 1) + ∑ i, Real.logb 2 (L i / L0 i) := 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 3, (6.3); p_i(j) and M_i in its proof, p. 19
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