Appendix B, p. 40 — eight consecutive ε² < ε̄² (ε̄ = r − 2) force ε²_k < ε̄² for the whole tail
ProvedIQCAlg.HeavyBall.tail_boundheavy-ballinductionlimit-cyclep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy (B.1), let , and let , the distance from the cycle (B.3) to the nearest transition point or of (4.11). If for some
then for every .
Once eight consecutive iterates are within of the cycle, all later iterates stay on the cycle's pieces, so the linear perturbation recursion applies forever after.
Formalization Note The page first says "some " and then fixes ; the statement uses that value.
Preamble
import Mathlib import Definitions.Def_IQCAlg_HeavyBall_Setting
Formal statement
namespace IQCAlg.HeavyBall
/-- Tail argument, p. 40: if `x` satisfies (B.1) and eight consecutive perturbations
`ε_i, …, ε_{i+7}` have `ε² < ε̄²` with `ε̄ = r − 2`, then `ε_k² < ε̄²` for every `k ≥ i`. -/
theorem tail_bound (x : ℕ → ℝ) (hx : IsB1Traj x) (i : ℕ)
(h8 : ∀ j : ℕ, j < 8 → eps x (i + j) ^ 2 < epsBar ^ 2) :
∀ k : ℕ, i ≤ k → eps x k ^ 2 < epsBar ^ 2 := by sorry
end IQCAlg.HeavyBall
Source
Lessard, Recht & Packard, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, arXiv:1408.3595v7, p. 40, the paragraph after (B.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.