Proof of Theorem 9, p. 24 — v_{k+1} − v_k = −√µ(x_{k+1} − x_k) − √s∇f(x_{k+1})
ProvedHessianDamping.IPAHDSC.vK_succ_subconvex-optimizationhessian-dampinginertial-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-algorithmstrong-convexity
Let be convex and , , , , let and let be a run of (IPAHD-SC). With , for every ,
This identity is the first step of the Lyapunov analysis: it expresses the change of the velocity-like vector through the step and the new gradient.
Formalization Note is an arbitrary point here; minimality is not needed for this identity. is the page's implicit positive step size.
Preamble
import Mathlib import Definitions.Def_HessianDamping_IPAHDSC_Setting
Formal statement
namespace HessianDamping.IPAHDSC
/-- Proof of Theorem 9, p. 24: along a run of (IPAHD-SC), for `k ≥ 1`,
`v_{k+1} - v_k = -√μ(x_{k+1} - x_k) - √s∇f(x_{k+1})`. -/
theorem vK_succ_sub {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(f : H → ℝ) (hfconv : ConvexOn ℝ Set.univ f) (hfC1 : ContDiff ℝ 1 f)
(μ : ℝ) (hμ : 0 < μ) (β s : ℝ) (hs : 0 < s) (hβ0 : 0 ≤ β)
(xstar : H) (x : ℕ → H) (hrun : IsIPAHDSCRun f μ β s x) (k : ℕ) (hk : 1 ≤ k) :
vK f μ β s x xstar (k + 1) - vK f μ β s x xstar k =
-(Real.sqrt μ • (x (k + 1) - x k)) - Real.sqrt s • gradient f (x (k + 1)) := by sorry
end HessianDamping.IPAHDSC
Source
Attouch, Chbani, Fadili, Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, arXiv:1907.10536v2, p. 24, proof of Theorem 9, display after "Using successively the definition of v_k and (20)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.