Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.2 — abstract convergence: finite length, convergence, stationarity and linear rates

Proved
FracPSG.Abstract.theorem_5_2

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

abstract-convergencedescent-methodskurdyka-lojasiewiczlinear-convergencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let H,K\mathcal H,\mathcal KH,K be finite-dimensional real Hilbert spaces, h:K→(−∞,+∞]h:\mathcal K\to(-\infty,+\infty]h:K→(−∞,+∞] proper and lower semicontinuous, (xn)(x_n)(xn​) in H\mathcal HH and (zn)(z_n)(zn​) in K\mathcal KK, αn,βn>0\alpha_n,\beta_n>0αn​,βn​>0, Δn,εn≥0\Delta_n,\varepsilon_n\ge0Δn​,εn​≥0 with Δk=0\Delta_k=0Δk​=0 for k<0k<0k<0, integers ı‾≤ıˉ\underline\imath\le\bar\imath​≤ˉ, I={ı‾,…,ıˉ}I=\{\underline\imath,\dots,\bar\imath\}I={​,…,ˉ}, and weights λi≥0\lambda_i\ge0λi​≥0 summing to 111. Suppose that (H1), (H2), (H3), (H4) hold and that (zn)(z_n)(zn​) is bounded. Let Ω\OmegaΩ be the set of cluster points of (zn)(z_n)(zn​), suppose that hhh is constant on Ω\OmegaΩ and has the KL property at each point of Ω\OmegaΩ, let Ω0={zˉ∈Ω:h(zn)→h(zˉ)}\Omega_0=\{\bar z\in\Omega:h(z_n)\to h(\bar z)\}Ω0​={zˉ∈Ω:h(zn​)→h(zˉ)} and hˉ:=h(zˉ)\bar h:=h(\bar z)hˉ:=h(zˉ) for zˉ∈Ω0\bar z\in\Omega_0zˉ∈Ω0​. Then:

  1. ∑n=0+∞Δn<+∞\displaystyle\sum_{n=0}^{+\infty}\Delta_n<+\inftyn=0∑+∞​Δn​<+∞.
  2. If (H5) holds, then ∑n=0+∞∥xn+1−xn∥<+∞\sum_{n=0}^{+\infty}\|x_{n+1}-x_n\|<+\infty∑n=0+∞​∥xn+1​−xn​∥<+∞ and (xn)(x_n)(xn​) converges.
  3. If inf⁡nβn>0\inf_n\beta_n>0infn​βn​>0, then 0∈∂Lh(zˉ)0\in\partial_L h(\bar z)0∈∂L​h(zˉ) for all zˉ∈Ω0\bar z\in\Omega_0zˉ∈Ω0​.
  4. If moreover hhh has the KL property at every point of Ω\OmegaΩ with an exponent a≤12a\le\tfrac12a≤21​, ı‾≤1\underline\imath\le1​≤1, δ:=inf⁡n,i∈Iαn−iβn2>0\delta:=\inf_{n,i\in I}\alpha_{n-i}\beta_n^2>0δ:=infn,i∈I​αn−i​βn2​>0 and εn/βn=O(h(zn−ıˉ)−h(zn+1−ı‾))\varepsilon_n/\beta_n=O\big(\sqrt{h(z_{n-\bar\imath})-h(z_{n+1-\underline\imath})}\big)εn​/βn​=O(h(zn−ˉ​)−h(zn+1−​​)​) (21), then there are γ1>0\gamma_1>0γ1​>0 and ρ∈(0,1)\rho\in(0,1)ρ∈(0,1) with
h(zn)−hˉ≤γ1ρnfor all n;h(z_n)-\bar h\le\gamma_1\rho^n\quad\text{for all }n;h(zn​)−hˉ≤γ1​ρnfor all n;

and if additionally (H5) holds and ∑k=n+∞εk=O(h(zn−ıˉ)−hˉ)\sum_{k=n}^{+\infty}\varepsilon_k=O\big(\sqrt{h(z_{n-\bar\imath})-\bar h}\big)∑k=n+∞​εk​=O(h(zn−ˉ​)−hˉ​), then there are xˉ∈H\bar x\in\mathcal Hxˉ∈H and γ2>0\gamma_2>0γ2​>0 with

∥xn−xˉ∥≤γ2ρn/2for all n,\|x_n-\bar x\|\le\gamma_2\rho^{n/2}\quad\text{for all }n,∥xn​−xˉ∥≤γ2​ρn/2for all n,

with the same ρ\rhoρ.

The theorem is an abstract convergence result for inexact multi-step descent methods: any algorithm whose iterates satisfy (H1)–(H5) for a KL merit function inherits finite length, global convergence, stationarity of the limit and, under exponent ≤12\le\tfrac12≤21​, linear rates. The paper applies it to the extrapolated proximal subgradient method for fractional programs.

Formalization Note H=\mathcal H=H= EuclideanSpace ℝ (Fin N), K=\mathcal K=K= EuclideanSpace ℝ (Fin P); Δ\DeltaΔ is indexed by Z\mathbb ZZ. Distances to ∂Lh\partial_L h∂L​h are encoded by quantifying over subgradients, never with Metric.infDist. The infima inf⁡βn>0\inf\beta_n>0infβn​>0 and δ>0\delta>0δ>0 are encoded by positive lower bounds (δ\deltaδ over pairs with n−i≥0n-i\ge0n−i≥0, where αn−i\alpha_{n-i}αn−i​ is defined). Each O(⋅)O(\cdot)O(⋅) hypothesis is "there is CCC such that eventually ⋯≤C⋯\cdots\le C\sqrt{\cdots}⋯≤C⋯​". hˉ\bar hhˉ is h(zˉ)h(\bar z)h(zˉ) for zˉ∈Ω0\bar z\in\Omega_0zˉ∈Ω0​: the value bound is stated for every zˉ∈Ω0\bar z\in\Omega_0zˉ∈Ω0​, and the tail-of-errors hypothesis for some zˉ∈Ω0\bar z\in\Omega_0zˉ∈Ω0​ (equivalent, since Ω0≠∅\Omega_0\ne\emptysetΩ0​=∅ and hhh is constant on it). The KL property is the published HasKLProperty with η\etaη real and without the requirement zˉ∈dom⁡∂Lh\bar z\in\operatorname{dom}\partial_L hzˉ∈dom∂L​h; this makes the hypothesis at most as strong as the paper's.

Preamble
import Mathlib
import Definitions.Def_NonconvexSplitting_Shared_StandingAssumptions
import Definitions.Def_NonconvexSplitting_Shared_LimitingSubdiff
import Definitions.Def_NonconvexSplitting_ADMMKL_KLProperty
import Definitions.Def_FracPSG_Abstract_Basic

open Filter Topology
Formal statement
namespace FracPSG.Abstract

open NonconvexSplitting.Shared NonconvexSplitting.ADMMKL

/-- Theorem 5.2 (Abstract convergence; Boţ–Dao–Li, arXiv:2003.04124v2, p. 15). Under (H1)–(H4), with
`(zₙ)` bounded and `h` constant on the set `Ω` of cluster points and having the KL property at each
point of `Ω`, and `h̄ = h(z̄)` for `z̄ ∈ Ω₀`:
(i) `∑ Δₙ < +∞`;
(ii) under (H5), `∑ ‖xₙ₊₁ - xₙ‖ < +∞` and `(xₙ)` converges;
(iii) if `inf βₙ > 0`, then `0 ∈ ∂_L h(z̄)` for all `z̄ ∈ Ω₀`;
(iv) if moreover `h` has the KL property on `Ω` with an exponent `a ≤ 1/2`, `ı̲ ≤ 1`, `δ > 0` and
(21) holds, there are `γ₁ > 0` and `ρ ∈ (0, 1)` with `h(zₙ) - h̄ ≤ γ₁ρⁿ` for all `n`; and if in
addition (H5) holds and `∑_{k ≥ n} ε_k = O(√(h(z_{n-ı̄}) - h̄))`, there are `x̄` and `γ₂ > 0` with
`‖xₙ - x̄‖ ≤ γ₂ρ^{n/2}` for all `n` (the same `ρ`). -/
theorem theorem_5_2 {N : ℕ} {x : ℕ → EuclideanSpace ℝ (Fin N)} {P : ℕ} {h : EuclideanSpace ℝ (Fin P) → EReal}
    {z : ℕ → EuclideanSpace ℝ (Fin P)} {α β ε : ℕ → ℝ} {Δ : ℤ → ℝ} {ilo ihi : ℤ}
    {lam : ℤ → ℝ}
    (hset : AbstractSetting h α β ε Δ ilo ihi lam)
    (hH1 : H1 h z α Δ) (hH2 : H2 h z β ε Δ ilo ihi lam) (hH3 : H3 h z) (hH4 : H4 α β ε)
    (hbdd : Bornology.IsBounded (Set.range z))
    (hconst : ∀ z₁ ∈ clusterSet z, ∀ z₂ ∈ clusterSet z, h z₁ = h z₂)
    (hKL : ∀ zbar ∈ clusterSet z, HasKLProperty h zbar) :
    Summable (fun n : ℕ => Δ n) ∧
    (H5 x Δ → Summable (fun n : ℕ => ‖x (n + 1) - x n‖) ∧
      ∃ xbar : EuclideanSpace ℝ (Fin N), Tendsto x atTop (𝓝 xbar)) ∧
    ((∃ b : ℝ, 0 < b ∧ ∀ n, b ≤ β n) →
      ∀ zbar ∈ omega0 h z, (0 : EuclideanSpace ℝ (Fin P)) ∈ LimitingSubdiff h zbar) ∧
    (∀ a : ℝ, a ≤ 1 / 2 → (∀ zbar ∈ clusterSet z, HasKLPropertyExp h zbar a) →
      ilo ≤ 1 → ∀ d : ℝ, DeltaLowerBound α β ilo ihi d →
      (∃ C : ℝ, ∀ᶠ n : ℕ in atTop,
        ε n / β n ≤ C * Real.sqrt ((h (z ((n : ℤ) - ihi).toNat)).toReal -
          (h (z ((n : ℤ) + 1 - ilo).toNat)).toReal)) →
      ∃ γ₁ : ℝ, 0 < γ₁ ∧ ∃ ρ : ℝ, 0 < ρ ∧ ρ < 1 ∧
        (∀ zbar ∈ omega0 h z, ∀ n : ℕ, (h (z n)).toReal - (h zbar).toReal ≤ γ₁ * ρ ^ n) ∧
        (H5 x Δ →
          (∃ zbar ∈ omega0 h z, ∃ C : ℝ, ∀ᶠ n : ℕ in atTop,
            ∑' k : ℕ, ε (n + k) ≤
              C * Real.sqrt ((h (z ((n : ℤ) - ihi).toNat)).toReal - (h zbar).toReal)) →
          ∃ xbar : EuclideanSpace ℝ (Fin N), ∃ γ₂ : ℝ, 0 < γ₂ ∧
            ∀ n : ℕ, ‖x n - xbar‖ ≤ γ₂ * ρ ^ ((n : ℝ) / 2))) := by sorry

end FracPSG.Abstract
Source
Boţ, Dao, Li, Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs, arXiv:2003.04124v2, p. 15, Theorem 5.2 (i)–(iv)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by iris · Nov 3, 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