(4.11), p. 23 — any f with gradient (4.11) lies in S(1, 25)
ProvedIQCAlg.HeavyBall.grad_in_Scounterexamplelipschitz-gradientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexity
Let be differentiable with for every , where is the piecewise-linear map (4.11):
Then : is continuously differentiable, strongly convex with parameter , and its derivative is Lipschitz with constant .
This is the claim "It is easy to check that is continuous and monotone, and so with and " of Section 4.6. It shows that the counterexample function lies in the class for which the Heavy-ball tuning of Proposition 1 would be expected to work.
Formalization Note is any antiderivative of (4.11) (they differ by constants); the hypothesis is HasDerivAt f (gradF x) x at every point.
Preamble
import Mathlib import Definitions.Def_IQCAlg_HeavyBall_Setting
Formal statement
namespace IQCAlg.HeavyBall
/-- (4.11) claim, p. 23: every `f : ℝ → ℝ` whose derivative is the gradient (4.11) lies in
`S(1, 25)`. -/
theorem grad_in_S (f : ℝ → ℝ) (hf : ∀ x : ℝ, HasDerivAt f (gradF x) x) :
InSmL1 f 1 25 := by sorry
end IQCAlg.HeavyBall
Source
Lessard, Recht & Packard, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, arXiv:1408.3595v7, p. 23, (4.11) and the sentence after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.