Lemma 4.1 of [44], p. 427 — ∏(1 − θμ/(m+t)) ≤ m^{θμ}/(m+k)^{θμ} and ∏_{j=t+1}^{k−1}(1 − θμ/(m+j)) ≤ (m+t+1)^{θμ}/(m+k)^{θμ}
ProvedStochGradTrack.Dimin.product_boundsdiminishing-stepsizeinequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
Let and . For every ,
and for every ,
an empty product being .
These bounds control the products that appear when the recursion is unrolled.
Formalization Note The page quotes the bounds from Lemma 4.1 of reference [44] without hypotheses on ; holds in Theorem 2 (from and ) and keeps every factor nonnegative, without which the bounds fail. Powers with exponent are real powers.
Preamble
import Mathlib
Formal statement
namespace StochGradTrack.Dimin
/-- The product bounds quoted from Lemma 4.1 of [44] (p. 427), for `0 ≤ θμ ≤ m` and `m > 0`. -/
theorem product_bounds (θ μ m : ℝ) (h0 : 0 ≤ θ * μ) (hle : θ * μ ≤ m) (hm : 0 < m) (k : ℕ) :
∏ t ∈ Finset.range k, (1 - θ * μ / (m + t)) ≤ m ^ (θ * μ) / (m + k) ^ (θ * μ) ∧
∀ t : ℕ, t < k →
∏ j ∈ Finset.Ico (t + 1) k, (1 - θ * μ / (m + j)) ≤ (m + t + 1) ^ (θ * μ) / (m + k) ^ (θ * μ) := by sorry
end StochGradTrack.Dimin
Source
Pu & Nedić, Math. Program. 187 (2021), §3.3, p. 427 (product bounds, citing Lemma 4.1 of [44])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.