§3.3, proof of Theorem 3.8, p. 273 — the induction with γ_s = 2/(s + 1) gives δ_t ≤ 2βR²/(t + 1)
ProvedConvexOptAlg.FrankWolfe.thm_3_8_inductionconvex-optimizationfrank-wolfep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1recursion
Let and , and let be a sequence of real numbers with
Then for every ,
This is the "simple induction using that " that finishes the proof of Theorem 3.8 once the one-step recursion and the initialization are known. It is a statement about real sequences only.
Formalization Note The recursion is assumed only from on, since the induction starts at step 2. is the usual reading of "β-smooth"; without it the base case of the bound can fail.
Preamble
import Mathlib
Formal statement
namespace ConvexOptAlg.FrankWolfe
/-- Bubeck, arXiv:1405.4980v2, proof of Theorem 3.8, p. 273 ("A simple induction using that
`γ_s = 2/(s+1)` finishes the proof"): a real sequence with `δ₂ ≤ (β/2)R²` and
`δ_{s+1} ≤ (1 − γ_s)δ_s + (β/2)γ_s²R²`, `γ_s = 2/(s+1)`, for every `s ≥ 2` satisfies
`δ_t ≤ 2βR²/(t + 1)` for every `t ≥ 2`. -/
theorem thm_3_8_induction (δ : ℕ → ℝ) (β R : ℝ) (hβ : 0 ≤ β)
(h2 : δ 2 ≤ β / 2 * R ^ 2)
(hrec : ∀ s : ℕ, 2 ≤ s →
δ (s + 1) ≤ (1 - 2 / ((s : ℝ) + 1)) * δ s + β / 2 * (2 / ((s : ℝ) + 1)) ^ 2 * R ^ 2)
(t : ℕ) (ht : 2 ≤ t) :
δ t ≤ 2 * β * R ^ 2 / ((t : ℝ) + 1) := by sorry
end ConvexOptAlg.FrankWolfe
Source
Bubeck, arXiv:1405.4980v2, §3.3, proof of Theorem 3.8, p. 273 ("A simple induction using that γ_s = 2/(s+1) finishes the proof")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.