Proof of Theorem 3.2, p. 348 — μ + (1/a_{k+1})(1 + μA_k) = (1 + μA_{k+1})/a_{k+1} = (1/a_{k+1})(L/(L−μ))^{k+1} = L
ProvedRelSmoothFOM.DualAvg.weight_identityconvergence-ratedual-averagingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1step-size
Let , and . Then for every ,
The weights of Algorithm 2 are chosen exactly so that this coefficient equals the relative smoothness constant , which lets Definition 1.1 close the one-step recursion .
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_DualAvg_Setting
Formal statement
namespace RelSmoothFOM.DualAvg
/-- Proof of Theorem 3.2, p. 348: for `0 ≤ μ < L` and every `k`,
`μ + (1/a_{k+1})(1 + μA_k) = (1 + μA_{k+1})/a_{k+1} = (1/a_{k+1})(L/(L − μ))^{k+1} = L`. -/
theorem weight_identity (L μ : ℝ) (hμ : 0 ≤ μ) (hμL : μ < L) (k : ℕ) :
μ + 1 / daWeight L μ k * (1 + μ * daSum L μ k) =
(1 + μ * daSum L μ (k + 1)) / daWeight L μ k ∧
(1 + μ * daSum L μ (k + 1)) / daWeight L μ k =
1 / daWeight L μ k * (L / (L - μ)) ^ (k + 1) ∧
1 / daWeight L μ k * (L / (L - μ)) ^ (k + 1) = 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. 348, proof of Theorem 3.2, first display line
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.