Proof of Theorem 4, p. 13 — under (G₂dis), (G₃dis) from k₀ on, f(x_k) − min f ≤ E_{k₀}/δ_k for k ≥ k₀
ProvedHessianDamping.IPAHD.value_le_EK_div_deltaconvergence-ratehessian-dampinginertial-algorithmlyapunovp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space and a convex function with a minimizer . Let , , , let , be non-negative sequences, and let be generated by (IPAHD). Let and assume that for every
- : ;
- : ,
where is (9). Then, with the energy of the proof of Theorem 4, for every
This is the rate estimate behind Theorem 4 (i).
Formalization Note. The page writes and "for ". The growth conditions cannot hold at when ( reads ), so they are assumed from an index on, as in the paper's examples, and the energy is started at . is for a point with for all . , are implicit on the page and added.
Preamble
import Mathlib import Definitions.Def_GoldenRatioVI_Shared_IsProxPoint import Definitions.Def_HessianDamping_IPAHD_Setting
Formal statement
namespace HessianDamping.IPAHD
/-- Proof of Theorem 4, p. 13: `f(x_k) - min f ≤ E_{k₀}/δ_k` for `k ≥ k₀` when the growth
conditions hold from `k₀ ≥ 1` on. -/
theorem value_le_EK_div_delta
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(f : H → ℝ) (hfconv : ConvexOn ℝ Set.univ f) (hfC1 : ContDiff ℝ 1 f)
(xstar : H) (hxstar : ∀ y, f xstar ≤ f y)
(α : ℝ) (hα : 1 ≤ α)
(h s : ℝ) (hh : 0 < h) (hs : s = h ^ 2)
(β b : ℕ → ℝ) (hβ : ∀ k, 0 ≤ β k) (hb : ∀ k, 0 ≤ b k)
(x : ℕ → H) (hx : IsIPAHDRun f α s β b x)
(k₀ : ℕ) (hk₀ : 1 ≤ k₀)
(hG2 : ∀ k : ℕ, k₀ ≤ k → 0 < b k * h * k - β (k + 1) - k * (β (k + 1) - β k))
(hG3 : ∀ k : ℕ, k₀ ≤ k →
deltaK h β b (k + 1) - deltaK h β b k ≤ (α - 1) * deltaK h β b k / ((k : ℝ) + 1)) :
∀ k : ℕ, k₀ ≤ k → f (x k) - f xstar ≤ EK f α h β b x xstar k₀ / deltaK h β b k := by sorry
end HessianDamping.IPAHD
Source
Attouch, Chbani, Fadili, Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, arXiv:1907.10536v2, §3.1.1, proof of Theorem 4, p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.