(31), p. 425 — β₀ > 0 iff m > (4θLρ_w² + 2θLρ_w√(1+3ρ_w²))/(1−ρ_w²), and then β_k > 0 for all k
ProvedStochGradTrack.Dimin.beta_positivediminishing-stepsizedistributed-optimizationgradient-trackingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and , and set
Then
and if then for every , where .
This turns the requirement of the linear system (29) into the first condition (14) on .
Formalization Note In the theorems ; here is a free real number with , which is what Lemma 1 gives for together with the standing addition .
Preamble
import Mathlib import Definitions.Def_StochGradTrack_Dimin_StepSystem
Formal statement
namespace StochGradTrack.Dimin
/-- (31) (p. 425): for `0 < ρ < 1`, `β₀ > 0` is equivalent to the lower bound (31) on `m`, and it implies
`β_k > 0` for every `k`. -/
theorem beta_positive (θ L m ρ : ℝ) (hθ : 0 < θ) (hL : 0 < L) (hm : 0 < m) (hρ0 : 0 < ρ) (hρ1 : ρ < 1) :
(0 < (1 - ρ ^ 2) / (2 * ρ ^ 2) - 4 * θ * L / m - 2 * θ ^ 2 * L ^ 2 / m ^ 2 ↔
(4 * θ * L * ρ ^ 2 + 2 * θ * L * ρ * Real.sqrt (1 + 3 * ρ ^ 2)) / (1 - ρ ^ 2) < m) ∧
(0 < (1 - ρ ^ 2) / (2 * ρ ^ 2) - 4 * θ * L / m - 2 * θ ^ 2 * L ^ 2 / m ^ 2 →
∀ k : ℕ, 0 < betaK θ m L ρ k) := by sorry
end StochGradTrack.Dimin
Source
Pu & Nedić, Math. Program. 187 (2021), §3.3, β₀ and (31), p. 425
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.