Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 14 — a subgradient descent sequence of a convex KL function converges strongly to a minimizer, with ‖x_k − x*‖ ≤ (b/a)φ(f(x_k)) + √(f(x_{k−1})/a)

Proved
ErrBoundCplx.Cplx.theorem_14

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

convex-optimizationfirst-order-methodskurdyka-lojasiewiczp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let HHH be a real Hilbert space and f:H→(−∞,+∞]f : H \to (-\infty, +\infty]f:H→(−∞,+∞] a proper, lower semicontinuous, convex function with argmin⁡f≠∅\operatorname{argmin} f \neq \emptysetargminf=∅ and min⁡f=0\min f = 0minf=0. Suppose fff has the KL property on [0<f<rˉ][0 < f < \bar r][0<f<rˉ] with desingularizing function φ∈K(0,rˉ)\varphi \in \mathcal K(0, \bar r)φ∈K(0,rˉ). Let (xk)k∈N(x_k)_{k\in\mathbb N}(xk​)k∈N​ be a subgradient descent sequence for fff with constants a,b>0a, b > 0a,b>0, i.e. x0∈dom⁡fx_0 \in \operatorname{dom} fx0​∈domf and, for each k≥1k \ge 1k≥1,

  • (H1) f(xk)+a∥xk−xk−1∥2≤f(xk−1)f(x_k) + a\|x_k - x_{k-1}\|^2 \le f(x_{k-1})f(xk​)+a∥xk​−xk−1​∥2≤f(xk−1​);
  • (H2) there is ωk∈∂f(xk)\omega_k \in \partial f(x_k)ωk​∈∂f(xk​) with ∥ωk∥≤b∥xk−xk−1∥\|\omega_k\| \le b\|x_k - x_{k-1}\|∥ωk​∥≤b∥xk​−xk−1​∥;

and suppose f(x0)≤r0<rˉf(x_0) \le r_0 < \bar rf(x0​)≤r0​<rˉ. Then xkx_kxk​ converges strongly to some x∗∈argmin⁡fx^* \in \operatorname{argmin} fx∗∈argminf, and

∥xk−x∗∥≤ba φ(f(xk))+f(xk−1)a,∀k≥1.(19)\|x_k - x^*\| \le \frac{b}{a}\,\varphi(f(x_k)) + \sqrt{\frac{f(x_{k-1})}{a}}, \qquad \forall k \ge 1. \tag{19}∥xk​−x∗∥≤ab​φ(f(xk​))+af(xk−1​)​​,∀k≥1.(19)

The bound (19) converts a rate for the values f(xk)f(x_k)f(xk​) into a rate for the iterates; Theorem 16 combines it with the majorization f(xk)≤ψ(αk)f(x_k) \le \psi(\alpha_k)f(xk​)≤ψ(αk​) to obtain (25).

Formalization Note The values f(xk)f(x_k)f(xk​) lie in [0,r0][0, r_0][0,r0​] (by (H1) the sequence f(xk)f(x_k)f(xk​) is nonincreasing) and enter φ\varphiφ and the square root through toReal. Strong convergence is convergence in the norm topology of HHH; x∗∈argmin⁡fx^* \in \operatorname{argmin} fx∗∈argminf is f(x∗)=0f(x^*) = 0f(x∗)=0. Completeness of HHH is an explicit instance (CompleteSpace H).

Preamble
import Mathlib
import Definitions.Def_MoreauProx_Characterization_GammaZero
import Definitions.Def_NonconvexSplitting_ADMMKL_KLProperty
import Definitions.Def_ErrBoundCplx_Cplx_DescentSeq
open MoreauProx.Characterization NonconvexSplitting.ADMMKL
open Filter Topology
Formal statement
namespace ErrBoundCplx.Cplx

/-- arXiv:1510.08234v3, Theorem 14, p. 16 (with the standing assumptions of §4, p. 14:
`argmin f ≠ ∅`, `min f = 0`). A subgradient descent sequence of a proper lsc convex function
that has the KL property on `[0 < f < r̄]` with `φ ∈ K(0, r̄)`, started with `f(x₀) ≤ r₀ < r̄`,
converges strongly to a minimizer `x*`, and (19) holds for every `k ≥ 1`. -/
theorem theorem_14 {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
    (f : H → EReal) (hf : GammaZero f) (hmin : IsMinZero f)
    (rbar : ℝ) (φ : ℝ → ℝ) (hφ : IsDesingularizer rbar φ) (hKL : KLOnBand f rbar φ)
    (a b : ℝ) (ha : 0 < a) (hb : 0 < b) (x : ℕ → H) (hx : IsSubgradDescentSeq f a b x)
    (r0 : ℝ) (hx0 : f (x 0) ≤ (r0 : EReal)) (hr0 : r0 < rbar) :
    ∃ xstar : H, f xstar = 0 ∧ Tendsto x atTop (𝓝 xstar) ∧
      ∀ k ≥ 1, ‖x k - xstar‖
        ≤ b / a * φ (f (x k)).toReal + Real.sqrt ((f (x (k - 1))).toReal / a) := by sorry

end ErrBoundCplx.Cplx
Source
arXiv:1510.08234v3, Theorem 14, p. 16, (19); standing assumptions of §4, p. 14 (S = argmin f ≠ ∅, min f = 0)
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).

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