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)
ProvedErrBoundCplx.Cplx.theorem_14convex-optimizationfirst-order-methodskurdyka-lojasiewiczp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space and a proper, lower semicontinuous, convex function with and . Suppose has the KL property on with desingularizing function . Let be a subgradient descent sequence for with constants , i.e. and, for each ,
- (H1) ;
- (H2) there is with ;
and suppose . Then converges strongly to some , and
The bound (19) converts a rate for the values into a rate for the iterates; Theorem 16 combines it with the majorization to obtain (25).
Formalization Note The values lie in (by (H1) the sequence is nonincreasing) and enter and the square root through toReal. Strong convergence is convergence in the norm topology of ; is . Completeness of 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.