Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(31), p. 425 — β₀ > 0 iff m > (4θLρ_w² + 2θLρ_w√(1+3ρ_w²))/(1−ρ_w²), and then β_k > 0 for all k

Proved
StochGradTrack.Dimin.beta_positive

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

diminishing-stepsizedistributed-optimizationgradient-trackingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let θ,L,m>0\theta,L,m>0θ,L,m>0 and 0<ρ<10<\rho<10<ρ<1, and set

β0=1−ρ22ρ2−4θLm−2θ2L2m2.\beta_0=\frac{1-\rho^2}{2\rho^2}-\frac{4\theta L}{m}-\frac{2\theta^2L^2}{m^2}.β0​=2ρ21−ρ2​−m4θL​−m22θ2L2​.

Then

β0>0  ⟺  m>4θLρ2+2θLρ1+3ρ21−ρ2,\beta_0>0\iff m>\frac{4\theta L\rho^2+2\theta L\rho\sqrt{1+3\rho^2}}{1-\rho^2},β0​>0⟺m>1−ρ24θLρ2+2θLρ1+3ρ2​​,

and if β0>0\beta_0>0β0​>0 then βk=1−ρ22ρ2−4αkL−2αk2L2>0\beta_k=\frac{1-\rho^2}{2\rho^2}-4\alpha_kL-2\alpha_k^2L^2>0βk​=2ρ21−ρ2​−4αk​L−2αk2​L2>0 for every k≥0k\ge0k≥0, where αk=θ/(m+k)\alpha_k=\theta/(m+k)αk​=θ/(m+k).

This turns the requirement βk>0\beta_k>0βk​>0 of the linear system (29) into the first condition (14) on mmm.

Formalization Note In the theorems ρ=ρw\rho=\rho_wρ=ρw​; here ρ\rhoρ is a free real number with 0<ρ<10<\rho<10<ρ<1, which is what Lemma 1 gives for ρw\rho_wρw​ together with the standing addition ρw>0\rho_w>0ρw​>0.

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
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me