Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2(b) — under Assumption 2, CGD with the restricted Gauss–Seidel rule and Armijo steps: Fc(xk)↓−∞F_c(x^k)\downarrow-\inftyFc​(xk)↓−∞ or Q-/R-linear convergence along T\mathcal TT

Proved
TsengCGD.Linear.theorem2_b

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

coordinate-descenterror-boundlinear-convergencenonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider problem (1): minimize Fc(x)=f(x)+cP(x)F_c(x)=f(x)+cP(x)Fc​(x)=f(x)+cP(x) with c>0c>0c>0, P:ℜn→(−∞,∞]P:\Re^n\to(-\infty,\infty]P:ℜn→(−∞,∞] proper, convex and lower semicontinuous, and fff continuously differentiable on an open set containing dom⁡P\operatorname{dom}PdomP. Assume that ∇f\nabla f∇f is LLL-Lipschitz on dom⁡P\operatorname{dom}PdomP for some L≥0L\ge0L≥0 (22).

Let {xk},{Hk},{dk}\{x^k\},\{H^k\},\{d^k\}{xk},{Hk},{dk} be generated by the CGD method under Assumption 1 (λˉI⪰Hk⪰λ‾I\bar\lambda I\succeq H^k\succeq\underline\lambda IλˉI⪰Hk⪰λ​I, 0<λ‾≤λˉ0<\underline\lambda\le\bar\lambda0<λ​≤λˉ), where {Jk}\{\mathcal J^k\}{Jk} is chosen by the restricted Gauss–Seidel rule (12) with T⊆{0,1,… }\mathcal T\subseteq\{0,1,\dots\}T⊆{0,1,…}. Suppose further that

  1. FcF_cFc​ satisfies Assumption 2: the local Lipschitzian error bound (35) dist⁡(x,Xˉ)≤τ∥dI(x)∥\operatorname{dist}(x,\bar X)\le\tau\|d_I(x)\|dist(x,Xˉ)≤τ∥dI​(x)∥ on each level set near Xˉ\bar XXˉ, with Xˉ≠∅\bar X\ne\emptysetXˉ=∅ the set of stationary points, and the proper separation of the isocost surfaces of FcF_cFc​ on Xˉ\bar XXˉ;
  2. PPP is block-separable with respect to Jk\mathcal J^kJk for all kkk;
  3. {αk}\{\alpha^k\}{αk} is chosen by the Armijo rule with sup⁡kαinitk≤1\sup_k\alpha^k_{\rm init}\le1supk​αinitk​≤1 and inf⁡kαinitk>0\inf_k\alpha^k_{\rm init}>0infk​αinitk​>0.

Then either {Fc(xk)}\{F_c(x^k)\}{Fc​(xk)} decreases to −∞-\infty−∞, or

{Fc(xk)}k∈T converges at least Q-linearlyand{xk}k∈T converges at least R-linearly.\{F_c(x^k)\}_{k\in\mathcal T}\ \text{converges at least Q-linearly}\quad\text{and}\quad\{x^k\}_{k\in\mathcal T}\ \text{converges at least R-linearly.}{Fc​(xk)}k∈T​ converges at least Q-linearlyand{xk}k∈T​ converges at least R-linearly.

This is the paper's linear convergence theorem for the CGD method with cyclic (Gauss–Seidel-type) coordinate selection; it requires neither convexity of fff nor strong convexity, only the error bound and the separation property of Assumption 2 (§6 of the paper gives sufficient conditions for the error bound).

Formalization Note "{Fc(xk)}↓−∞\{F_c(x^k)\}\downarrow-\infty{Fc​(xk)}↓−∞" is stated as: the values are nonincreasing and tend to −∞-\infty−∞. The rates are along T={t0<t1<⋯ }\mathcal T=\{t_0<t_1<\cdots\}T={t0​<t1​<⋯}, i.e. for the sequences i↦Fc(xti)i\mapsto F_c(x^{t_i})i↦Fc​(xti​) and i↦xtii\mapsto x^{t_i}i↦xti​. Q-linear convergence includes convergence to a limit vvv and eventually ∣si+1−v∣≤q∣si−v∣|s_{i+1}-v|\le q|s_i-v|∣si+1​−v∣≤q∣si​−v∣ with q<1q<1q<1; R-linear convergence is ∥xti−xˉ∥≤Cqi\|x^{t_i}-\bar x\|\le Cq^i∥xti​−xˉ∥≤Cqi for some xˉ\bar xxˉ, CCC and q<1q<1q<1. "sup⁡kαinitk≤1\sup_k\alpha^k_{\rm init}\le1supk​αinitk​≤1" is αinitk≤1\alpha^k_{\rm init}\le1αinitk​≤1 for all kkk, "inf⁡kαinitk>0\inf_k\alpha^k_{\rm init}>0infk​αinitk​>0" a positive lower bound. In Assumption 2, dist⁡\operatorname{dist}dist is Metric.infDist and "for any ζ≥min⁡Fc\zeta\ge\min F_cζ≥minFc​" is "for every real ζ\zetaζ". PPP is the pair (effective domain, finite values); coordinates are 0-based.

Preamble
import Mathlib
import Definitions.Def_TsengCGD_Linear_Basic
open Filter Topology Finset Matrix
open scoped RealInnerProductSpace
Formal statement
namespace TsengCGD.Linear

theorem theorem2_b {n : ℕ} (f : TsengCGD.Global.Vec n → ℝ) (D : Set (TsengCGD.Global.Vec n)) (P : TsengCGD.Global.Vec n → ℝ) (c : ℝ)
    (hs : TsengCGD.Global.Standing f D P c) (J : ℕ → Finset (Fin n)) (H : ℕ → Matrix (Fin n) (Fin n) ℝ)
    (x d : ℕ → TsengCGD.Global.Vec n) (α : ℕ → ℝ) (hrun : TsengCGD.Global.IsCGDRun f D P c J H x d α)
    (lam lamBar : ℝ) (hA1 : TsengCGD.Global.Assumption1 H lam lamBar)
    (L : ℝ) (hL : GradLipOn f D L)
    (t : ℕ → ℕ) (hRGS : RestrictedGaussSeidel J t)
    (hA2a : Assumption2a f D P c) (hA2b : Assumption2b f D P c)
    (hsep : ∀ k, TsengCGD.Global.BlockSeparable D P (J k))
    (β σ γ : ℝ) (αinit : ℕ → ℝ) (harm : TsengCGD.Global.IsArmijo f D P c β σ γ αinit H x d α)
    (hinit1 : ∀ k, αinit k ≤ 1) (hinit : ∃ a > 0, ∀ k, a ≤ αinit k) :
    (Antitone (fun k => TsengCGD.Global.Fc f P c (x k)) ∧ Tendsto (fun k => TsengCGD.Global.Fc f P c (x k)) atTop atBot) ∨
      (QLinear (fun i => TsengCGD.Global.Fc f P c (x (t i))) ∧ RLinear (fun i => x (t i))) := by sorry

end TsengCGD.Linear
Source
Tseng and Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B 117 (2009), pp. 405–409, Theorem 2(b), with Assumption 2 (p. 404)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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