Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4 — descent inequality F(xk+1)≤F(xk)−ηUk2∥dk∥2F(x_{k+1})\le F(x_k)-\frac{\eta_{U_k}}2\|d_k\|^2F(xk+1​)≤F(xk​)−2ηUk​​​∥dk​∥2

Proved
StochCoordProx.lemma_4_descent

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

high-probability-boundsnonconvex-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1proximal-gradientstochastic-coordinate-descent

Let F=f+ψF=f+\psiF=f+ψ with fff differentiable and LUL_ULU​ smooth along a matrix U∈UU\in\mathcal UU∈U (display (2)). Let η>0\eta>0η>0, let H=Hf,UH=H_{f,U}H=Hf,U​ be the step parameter of Algorithm 1 (in either of its two cases), and let ddd be a global minimizer over Rp\mathbb R^pRp of the subproblem (9) at a point x∈Rnx\in\mathbb R^nx∈Rn. Then

F(x+Ud)≤F(x)−η2∥d∥2.F(x+Ud)\le F(x)-\frac{\eta}{2}\|d\|^2 .F(x+Ud)≤F(x)−2η​∥d∥2.

Applied at every iteration of SCPG (x=xkx=x_kx=xk​, U=UkU=U_kU=Uk​, η=ηUk\eta=\eta_{U_k}η=ηUk​​, d=dkd=d_kd=dk​), this is the descent inequality F(xk+1)≤F(xk)−ηUk2∥dk∥2F(x_{k+1})\le F(x_k)-\frac{\eta_{U_k}}{2}\|d_k\|^2F(xk+1​)≤F(xk​)−2ηUk​​​∥dk​∥2 for all k≥0k\ge0k≥0. It makes FFF a Lyapunov function for SCPG and keeps all iterates in LF(x0)\mathcal L_F(x_0)LF​(x0​).

Differences from the source:

  • generalization: the iterates of SCPG, for all k ≥ 0 → any point x, any U ∈ 𝒰, any η > 0 and any global minimizer d of (9) at (x, U, H_{f,U}); reason: every iteration of every run is an instance
  • generalization: Assumption 1 (A.1 for 𝒰, ψ C² and simple, A.3) → f differentiable with (2) for this U; no regularity of ψ; no solution of (1); reason: the proof uses only (3) for U, the optimality of d, and convexity along subspaces in the first case; Assumption 1 implies these
  • generalization: f is L_U smooth along U (A.1) → f differentiable on ℝⁿ and (2) for U with constant L_U; reason: the paper defines the term by (2) and uses nothing else; any smooth f satisfying (2) is an instance
  • encoding: vectors of ℝⁿ, ℝᵖ and matrices U ∈ ℝ^{n×p} → EuclideanSpace ℝ (Fin n), EuclideanSpace ℝ (Fin p), U acting through Matrix.toEuclideanLin; reason: Lean convention; the Euclidean norm and inner product of the paper, same instances
  • generalization: the set 𝒰 bounded (standing assumption, p.4); 𝓛_F(x₀) bounded (standing assumption, p.7: "Throughout the paper, we also assume boundedness of the level set") → not assumed; reason: the proof does not use them; they serve only to make H_{F,max} finite, which this statement does not involve; every instance satisfying them is covered
Preamble
import Mathlib
import Definitions.Def_StochCoordProx_IsSmoothAlong
import Definitions.Def_StochCoordProx_Hf
import Definitions.Def_StochCoordProx_model

open Matrix
Formal statement
namespace StochCoordProx

/-- **Lemma 4 (descent inequality).** One step of SCPG decreases `F = f + ψ`: if `U ∈ 𝒰`, `f` is
differentiable and `L_U` smooth along `U`, `η > 0`, `H = H_{f,U}` is the step parameter of
Algorithm 1 (both cases of the rule), and `d` is a global minimizer of the subproblem (9) at `x`,
then for `x⁺ = x + U d`
`F(x⁺) ≤ F(x) − (η/2) ‖d‖²`  (16).

Necoara & Chorobura, arXiv:2104.13370v3, Lemma 4, display (16), p.9.

**Formalization Note.** Stated for one step at an arbitrary point `x`; every iteration `k` of
every SCPG run is an instance (`x = x_k`, `U = U_k`, `η = η_{U_k}`, `d = d_k`). No regularity of
`ψ` and no solution of (1) is assumed. -/
theorem lemma_4_descent {n p : ℕ} (f ψ : EuclideanSpace ℝ (Fin n) → ℝ)
    (𝒰 : Set (Matrix (Fin n) (Fin p) ℝ)) (U : Matrix (Fin n) (Fin p) ℝ) (hU : U ∈ 𝒰)
    (LU η : ℝ) (hf : Differentiable ℝ f) (hL : IsSmoothAlong f U LU) (hη : 0 < η)
    (x : EuclideanSpace ℝ (Fin n)) (d : EuclideanSpace ℝ (Fin p))
    (hd : ∀ d' : EuclideanSpace ℝ (Fin p),
      model f ψ x U (Hf ψ 𝒰 LU η) d ≤ model f ψ x U (Hf ψ 𝒰 LU η) d') :
    f (x + Matrix.toEuclideanLin U d) + ψ (x + Matrix.toEuclideanLin U d) ≤
      f x + ψ x - η / 2 * ‖d‖ ^ 2 := by sorry

end StochCoordProx
Source
Necoara & Chorobura, Efficiency of stochastic coordinate proximal gradient methods on nonseparable composite optimization, arXiv:2104.13370v3, Lemma 4, display (16), p.9
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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