Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(63), Appendix H, p. 23 — E[F(x_{k+1})] ≤ F(x_k) − (1/(2Ld)) D_g(x_k, L) under uniform coordinate choice

Proved
KarimiPL.ProxCD.expected_descent_63

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

coordinate-descentexpected-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-gradient

Let d≥1d\ge1d≥1, let f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R be differentiable and satisfy the coordinate-wise LLL-Lipschitz upper bound (5), L>0L>0L>0, let g(x)=∑igi(xi)g(x)=\sum_i g_i(x_i)g(x)=∑i​gi​(xi​) with each gi:R→Rg_i:\mathbb R\to\mathbb Rgi​:R→R convex, and F=f+gF=f+gF=f+g. Let sel(x,i)\mathrm{sel}(x,i)sel(x,i) be any coordinate proximal-gradient step (16) from xxx along coordinate iii, i.e. sel(x,i)=x+t⋆ei\mathrm{sel}(x,i)=x+t^\star e_isel(x,i)=x+t⋆ei​ with t⋆t^\start⋆ a minimizer of t↦t∇if(x)+L2t2+gi(xi+t)−gi(xi)t\mapsto t\nabla_i f(x)+\frac L2t^2+g_i(x_i+t)-g_i(x_i)t↦t∇i​f(x)+2L​t2+gi​(xi​+t)−gi​(xi​). Then for every xxx,

1d∑i=1dF(sel(x,i)) ≤ F(x)−12Ld Dg(x,L).\frac1d\sum_{i=1}^d F\big(\mathrm{sel}(x,i)\big)\ \le\ F(x)-\frac{1}{2Ld}\,\mathcal D_g(x,L).d1​i=1∑d​F(sel(x,i)) ≤ F(x)−2Ld1​Dg​(x,L).

The left side is E[F(xk+1)]\mathbb E[F(x_{k+1})]E[F(xk+1​)] given xk=xx_k=xxk​=x when iki_kik​ is uniform on {1,…,d}\{1,\dots,d\}{1,…,d}.

This expected-descent inequality, combined with the proximal-PL inequality, gives the contraction factor 1−μ/(dL)1-\mu/(dL)1−μ/(dL) of Theorem 6.

Formalization Note The conditional expectation over a uniform coordinate is written as the average over the ddd coordinates. The page writes nnn for ddd and Dg(L,x)\mathcal D_g(L,x)Dg​(L,x) for Dg(x,L)\mathcal D_g(x,L)Dg​(x,L).

Preamble
import Mathlib
import Definitions.Def_KarimiPL_ProxCD_Setting

open InnerProductSpace
Formal statement
namespace KarimiPL.ProxCD

theorem expected_descent_63 {d : ℕ} (hd : 0 < d) (f : KarimiPL.Rel.E d → ℝ) (hdiff : Differentiable ℝ f)
    (L : ℝ) (hL : 0 < L)
    (hCoord : ∀ (x : KarimiPL.Rel.E d) (i : Fin d) (t : ℝ),
      f (x + t • EuclideanSpace.single i (1 : ℝ)) ≤ f x + t * gradient f x i + L / 2 * t ^ 2)
    (gs : Fin d → ℝ → ℝ) (hgs : ∀ i, ConvexOn ℝ Set.univ (gs i))
    (sel : KarimiPL.Rel.E d → Fin d → KarimiPL.Rel.E d) (hsel : ∀ x i, IsProxCoordStep f gs L x i (sel x i)) :
    ∀ x : KarimiPL.Rel.E d, (1 / (d : ℝ)) * ∑ i, (f (sel x i) + sepSum gs (sel x i))
      ≤ (f x + sepSum gs x) - 1 / (2 * L * d) * Dg f (sepSum gs) x L := by sorry

end KarimiPL.ProxCD
Source
Karimi, Nutini, Schmidt, arXiv:1608.04636v4, Appendix H, (63), p. 23
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