Proof of Theorem 3.2, p. 347 — A_k = (1/μ)[(1 + μ/(L−μ))^k − 1] for μ > 0, and A_k = k/L for μ = 0
ProvedRelSmoothFOM.DualAvg.a_k_closed_formconvergence-ratedual-averaginggeometric-seriesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be the weights of the dual averaging scheme, with partial sums . Then for every :
- if ,
- if , then .
This closed form converts the bound produced by the proof of Theorem 3.2 into the explicit rate (32).
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_DualAvg_Setting
Formal statement
namespace RelSmoothFOM.DualAvg
/-- Proof of Theorem 3.2, p. 347: the closed form of `A_k = Σ_{i=0}^{k−1} a_{i+1}`.
For `0 < μ < L`, `A_k = (1/μ)((1 + μ/(L − μ))^k − 1)`; for `μ = 0 < L`, `A_k = k/L`. -/
theorem a_k_closed_form (L μ : ℝ) :
(0 < μ → μ < L → ∀ k : ℕ, daSum L μ k = ((1 + μ / (L - μ)) ^ k - 1) / μ) ∧
(μ = 0 → 0 < L → ∀ k : ℕ, daSum L μ k = (k : ℝ) / L) := by sorry
end RelSmoothFOM.DualAvg
Source
Lu, Freund & Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), p. 347, proof of Theorem 3.2, definition of A_k following (34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.