Proof of Theorem 4, p. 13 — ½‖v_{k+1}‖² − ½‖v_k‖² ≤ −(α − 1)hC_k(f(x⋆) − f(x_{k+1})) − hC_k(k + 1)(f(x_k) − f(x_{k+1}))
ProvedHessianDamping.IPAHD.half_sq_vK_succ_sub_lehessian-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). With and , if and the growth condition holds at , i.e. , then
This is the key estimate on the quadratic part of the Lyapunov energy of Theorem 4.
Formalization Note. The minimizer is carried as a point with for all (the paper's "Given "). and are implicit on the page and added; is what makes the dropped coefficient of non-positive.
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: the bound on `½‖v_{k+1}‖² - ½‖v_k‖²` under (G₂dis) at `k`. -/
theorem half_sq_vK_succ_sub_le
{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 : 0 < b k * h * k - β (k + 1) - k * (β (k + 1) - β k)) :
1 / 2 * ‖vK f α h β x xstar (k + 1)‖ ^ 2 - 1 / 2 * ‖vK f α h β x xstar k‖ ^ 2
≤ -(α - 1) * h * CK h β b k * (f xstar - f (x (k + 1)))
- h * CK h β b k * ((k : ℝ) + 1) * (f (x k) - f (x (k + 1))) := 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.