Proof of Theorem 3.1, p. 345 — C_k := 1/Σᵢ(L/(L−μ))ⁱ = μ/(L((1+μ/(L−μ))ᵏ − 1)) for μ > 0, and C_k = 1/k for μ = 0
ProvedRelSmoothFOM.PrimalGrad.ck_identityconvergence-rategeometric-seriesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1primal-gradient-method
Let and , and define
Then:
- if ,
- if , then .
The parameter is the normalising constant that converts the weighted inequality (30) into the bound (31) on the optimality gap; the closed form follows from summing a geometric series.
Formalization Note The hypothesis is added because divides by ; and are where the paper uses .
Preamble
import Mathlib import Definitions.Def_RelSmoothFOM_PrimalGrad_Setting
Formal statement
namespace RelSmoothFOM.PrimalGrad
theorem ck_identity (L μ : ℝ) (hL : 0 < L) (hμ : 0 ≤ μ) (hμL : μ < L)
(k : ℕ) (hk : 1 ≤ k) :
(0 < μ → 1 / ∑ i ∈ Finset.Icc 1 k, (L / (L - μ)) ^ i
= μ / (L * ((1 + μ / (L - μ)) ^ k - 1))) ∧
(μ = 0 → 1 / ∑ i ∈ Finset.Icc 1 k, (L / (L - μ)) ^ i = 1 / (k : ℝ)) := by sorry
end RelSmoothFOM.PrimalGrad
Source
Lu, Freund & Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), p. 345, proof of Theorem 3.1, definition of C_k
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.