Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6, p. 10 — randomized proximal coordinate descent (16) satisfies E[F(x_k) − F*] ≤ (1 − μ/(dL))^k [F(x_0) − F*] under proximal-PL

Proved
KarimiPL.ProxCD.theorem_6

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

coordinate-descentlinear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyak-lojasiewiczproximal-gradient

Consider min⁡x∈RdF(x)=f(x)+g(x)\min_{x\in\mathbb R^d}F(x)=f(x)+g(x)minx∈Rd​F(x)=f(x)+g(x) with d≥1d\ge1d≥1, where

  1. fff is differentiable and its gradient is LLL-Lipschitz, L>0L>0L>0: ∥∇f(x)−∇f(y)∥≤L∥x−y∥\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|∥∇f(x)−∇f(y)∥≤L∥x−y∥;
  2. g(x)=∑i=1dgi(xi)g(x)=\sum_{i=1}^d g_i(x_i)g(x)=∑i=1d​gi​(xi​) is separable, each gi:R→Rg_i:\mathbb R\to\mathbb Rgi​:R→R convex;
  3. FFF has a minimizer x∗x^*x∗, and F∗=F(x∗)F^*=F(x^*)F∗=F(x∗);
  4. FFF satisfies the proximal-PL inequality with constant μ>0\mu>0μ>0: for all xxx, 12Dg(x,L)≥μ(F(x)−F∗)\frac12\mathcal D_g(x,L)\ge\mu(F(x)-F^*)21​Dg​(x,L)≥μ(F(x)−F∗), where Dg(x,α)=−2αmin⁡y[⟨∇f(x),y−x⟩+α2∥y−x∥2+g(y)−g(x)]\mathcal D_g(x,\alpha)=-2\alpha\min_y[\langle\nabla f(x),y-x\rangle+\frac\alpha2\|y-x\|^2+g(y)-g(x)]Dg​(x,α)=−2αminy​[⟨∇f(x),y−x⟩+2α​∥y−x∥2+g(y)−g(x)].

Run the coordinate-wise proximal-gradient method from x0x_0x0​: at step kkk draw iki_kik​ uniformly from {1,…,d}\{1,\dots,d\}{1,…,d}, independently of the past, and set xk+1=xk+α⋆eikx_{k+1}=x_k+\alpha^\star e_{i_k}xk+1​=xk​+α⋆eik​​ with

α⋆∈argmin⁡α[α∇ikf(xk)+L2α2+gik(xik+α)−gik(xik)].\alpha^\star\in\operatorname*{argmin}_{\alpha}\Big[\alpha\nabla_{i_k}f(x_k)+\frac L2\alpha^2+g_{i_k}(x_{i_k}+\alpha)-g_{i_k}(x_{i_k})\Big].α⋆∈αargmin​[α∇ik​​f(xk​)+2L​α2+gik​​(xik​​+α)−gik​​(xik​​)].

Then for every k≥0k\ge0k≥0,

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

This extends the linear rate of randomized coordinate descent under PL (Theorem 3) and of proximal-gradient under proximal-PL (Theorem 5) to the proximal coordinate method, without strong convexity.

Formalization Note The expectation is the exact average over all dkd^kdk index words (i0,…,ik−1)(i_0,\dots,i_{k-1})(i0​,…,ik−1​), each of probability d−kd^{-k}d−k. The update is any step selection sel(x,i)\mathrm{sel}(x,i)sel(x,i) satisfying (16); since the one-dimensional minimizer is unique there is exactly one. Equation (16) as printed assigns the minimizing step to xk+1x_{k+1}xk+1​; the iterate xk+α⋆eikx_k+\alpha^\star e_{i_k}xk​+α⋆eik​​ (Appendix H) is encoded. The gig_igi​ are real-valued; extended-valued gig_igi​ such as box indicators (§4.4) are outside this formalization. The minimum in Dg\mathcal D_gDg​ is a real infimum, attained for convex gig_igi​ and L>0L>0L>0.

Preamble
import Mathlib
import Definitions.Def_KarimiPL_ProxCD_Setting

open InnerProductSpace
Formal statement
namespace KarimiPL.ProxCD

theorem theorem_6 {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (hdiff : Differentiable ℝ f)
    (L : ℝ) (hL : 0 < L) (hLip : ∀ x y : KarimiPL.Rel.E d, ‖gradient f x - gradient f y‖ ≤ L * ‖x - y‖)
    (gs : Fin d → ℝ → ℝ) (hgs : ∀ i, ConvexOn ℝ Set.univ (gs i))
    (xstar : KarimiPL.Rel.E d) (hxstar : ∀ y, f xstar + sepSum gs xstar ≤ f y + sepSum gs y)
    (μ : ℝ) (hμ : 0 < μ) (hPPL : ProxPL f (sepSum gs) L μ (f xstar + sepSum gs xstar))
    (sel : KarimiPL.Rel.E d → Fin d → KarimiPL.Rel.E d) (hsel : ∀ x i, IsProxCoordStep f gs L x i (sel x i))
    (x0 : KarimiPL.Rel.E d) :
    ∀ k : ℕ, expectedGap (fun x => f x + sepSum gs x) sel x0 (f xstar + sepSum gs xstar) k
      ≤ (1 - μ / (d * L)) ^ k * ((f x0 + sepSum gs x0) - (f xstar + sepSum gs xstar)) := by sorry

end KarimiPL.ProxCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Theorem 6 (17), p. 10; setup of Theorem 5, p. 8
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