p. 427 — Σ(m+t)^{θμ−3} ≤ max{(m+k)^{θμ−2}/(θμ−2), (m−1)^{θμ−2}/(2−θμ)} and Σ(m+t)^{θμ−2} ≤ (m+k)^{θμ−1}/(θμ−1)
ProvedStochGradTrack.Dimin.sum_boundsdiminishing-stepsizeinequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
Let and . For every ,
and, if ,
These comparisons of sums with integrals give the final rate of in Theorem 2.
Formalization Note The page states the first bound without excluding , where both branches of the maximum involve (the true bound is logarithmic); the hypothesis is added for that bound. The intermediate integrals of the page are not stated. Powers are real powers.
Preamble
import Mathlib
Formal statement
namespace StochGradTrack.Dimin
/-- The sum–integral bounds (p. 427), for `m > 1` and `θμ > 1`; the first one (disclosed) for `θμ ≠ 2`. -/
theorem sum_bounds (θ μ m : ℝ) (hm : 1 < m) (hθμ : 1 < θ * μ) (k : ℕ) :
(θ * μ ≠ 2 →
∑ t ∈ Finset.range k, (m + t) ^ (θ * μ - 3)
≤ max (1 / (θ * μ - 2) * (m + k) ^ (θ * μ - 2)) (1 / (2 - θ * μ) * (m - 1) ^ (θ * μ - 2))) ∧
∑ t ∈ Finset.range k, (m + t) ^ (θ * μ - 2) ≤ 1 / (θ * μ - 1) * (m + k) ^ (θ * μ - 1) := by sorry
end StochGradTrack.Dimin
Source
Pu & Nedić, Math. Program. 187 (2021), §3.3, p. 427 ("Note that" display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.