Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, p. 5 — randomized coordinate descent under PL

Proved
KarimiPL.RCD.theorem_3

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

coordinate-descentlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewiczrandomized-algorithms

Let d≥1d\ge1d≥1. Let f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R be differentiable, obey the coordinate-wise upper bound (5) with L>0L>0L>0, attain its minimum f∗=f(x∗)f^*=f(x^*)f∗=f(x∗), and satisfy the PL inequality 12∥∇f(x)∥2≥μ(f(x)−f∗)\frac12\|\nabla f(x)\|^2\ge\mu(f(x)-f^*)21​∥∇f(x)∥2≥μ(f(x)−f∗) for some μ>0\mu>0μ>0. From any x0x_0x0​, independently draw iti_tit​ uniformly from the ddd coordinates at each step and set xt+1=xt−L−1∇itf(xt)eitx_{t+1}=x_t-L^{-1}\nabla_{i_t}f(x_t)e_{i_t}xt+1​=xt​−L−1∇it​​f(xt​)eit​​. Then, for every k≥0k\ge0k≥0,

E[f(xk)−f∗]≤(1−μdL)k(f(x0)−f∗).\mathbb E[f(x_k)-f^*] \le\left(1-\frac\mu{dL}\right)^k(f(x_0)-f^*).E[f(xk​)−f∗]≤(1−dLμ​)k(f(x0​)−f∗).

This is the expected linear rate of Theorem 3. It covers differentiable objectives satisfying PL without requiring convexity.

Formalization Note Independent uniform draws are represented by averaging over all words of length kkk, each with weight d−kd^{-k}d−k. The minimum value is fixed by an explicit global minimizer. The one-sided coordinate bound (5), rather than a full gradient-Lipschitz assumption, is the smoothness hypothesis.

Preamble
import Mathlib
import Definitions.Def_KarimiPL_RCD_Setting
import Definitions.Def_ShiOptrates_FunctionClass
Formal statement
namespace KarimiPL.RCD

/-- Theorem 3, p. 5: the expected rate of randomized coordinate descent under PL. -/
theorem theorem_3 {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ)
    (hdiff : Differentiable ℝ f) (L : ℝ) (hL : 0 < L)
    (hcoord : CoordLipschitz f L)
    (xstar : KarimiPL.Rel.E d) (hxstar : ∀ y, f xstar ≤ f y)
    (mu : ℝ) (hmu : 0 < mu)
    (hPL : ShiOptRates.PolyakLojasiewicz f (gradient f) mu (f xstar))
    (x0 : KarimiPL.Rel.E d) :
    ∀ k : ℕ,
      expectedGap f L x0 (f xstar) k ≤
        (1 - mu / ((d : ℝ) * L)) ^ k * (f x0 - f xstar) := by sorry

end KarimiPL.RCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Theorem 3, p. 5
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

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