Theorem 5.2 — abstract convergence: finite length, convergence, stationarity and linear rates
ProvedFracPSG.Abstract.theorem_5_2Let be finite-dimensional real Hilbert spaces, proper and lower semicontinuous, in and in , , with for , integers , , and weights summing to . Suppose that (H1), (H2), (H3), (H4) hold and that is bounded. Let be the set of cluster points of , suppose that is constant on and has the KL property at each point of , let and for . Then:
- .
- If (H5) holds, then and converges.
- If , then for all .
- If moreover has the KL property at every point of with an exponent , , and (21), then there are and with
and if additionally (H5) holds and , then there are and with
with the same .
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 , linear rates. The paper applies it to the extrapolated proximal subgradient method for fractional programs.
Formalization Note EuclideanSpace ℝ (Fin N), EuclideanSpace ℝ (Fin P); is indexed by . Distances to are encoded by quantifying over subgradients, never with Metric.infDist. The infima and are encoded by positive lower bounds ( over pairs with , where is defined). Each hypothesis is "there is such that eventually ". is for : the value bound is stated for every , and the tail-of-errors hypothesis for some (equivalent, since and is constant on it). The KL property is the published HasKLProperty with real and without the requirement ; this makes the hypothesis at most as strong as the paper's.
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.