§3.2, proof of Theorem 3.3, p. 269 — ωδ_s² + δ_{s+1} ≤ δ_s for all s ≥ 1 implies 1/δ_t ≥ ω(t − 1)
ProvedConvexOptAlg.SmoothGD.thm_3_3_sequence_rateconvex-optimizationgradient-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1sequences
Let be a sequence of non-negative reals and , and suppose that for every ,
Then for every ,
i.e. whenever .
This is the purely numerical step of the proof of Theorem 3.3: applied with to the optimality gaps, it gives the rate .
Formalization Note The page divides by and ; the Lean conclusion is multiplied through by so that it also covers . The page defines in the nontrivial case; this lemma carries that positivity explicitly.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs open scoped InnerProductSpace
Formal statement
namespace ConvexOptAlg.SmoothGD
/-- Proof of Theorem 3.3, first display on p. 269 (Bubeck, arXiv:1405.4980v2), as a lemma on real
sequences: if `ω > 0`, `δ_s ≥ 0` and `ω δ_s² + δ_{s+1} ≤ δ_s` for every `s ≥ 1`, then for every `t ≥ 2`,
`ω (t − 1) δ_t ≤ 1`, i.e. `1/δ_t ≥ ω(t − 1)` whenever `δ_t > 0`. Stated without division so
that it also covers `δ_t = 0`. -/
theorem thm_3_3_sequence_rate (δ : ℕ → ℝ) (ω : ℝ) (hω : 0 < ω)
(hδ : ∀ s : ℕ, 1 ≤ s → 0 ≤ δ s)
(hrec : ∀ s : ℕ, 1 ≤ s → ω * δ s ^ 2 + δ (s + 1) ≤ δ s) (t : ℕ) (ht : 2 ≤ t) :
ω * ((t : ℝ) - 1) * δ t ≤ 1 := by sorry
end ConvexOptAlg.SmoothGD
Source
Bubeck, arXiv:1405.4980v2, §3.2, proof of Theorem 3.3, first display on p. 269
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.