Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.1, p. 27: inequalities of the schedule τ1,s=2/(s+4)\tau_{1,s} = 2/(s+4)τ1,s​=2/(s+4)

Proved
KatyushaNs.tau_schedule_inequalities

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

convex-optimizationstochastic-optimizationvariance-reduction

Let τ1,s=2s+4\tau_{1,s} = \frac{2}{s+4}τ1,s​=s+42​ for s=0,1,2,…s = 0, 1, 2, \dotss=0,1,2,… and τ2=12\tau_2 = \frac12τ2​=21​. Then for every s≥0s \ge 0s≥0:

  1. τ1,s≤12\tau_{1,s} \le \frac12τ1,s​≤21​;
  2. 1τ1,s2≥1−τ1,s+1τ1,s+12\displaystyle \frac{1}{\tau_{1,s}^2} \ge \frac{1 - \tau_{1,s+1}}{\tau_{1,s+1}^2}τ1,s2​1​≥τ1,s+12​1−τ1,s+1​​;
  3. τ1,s+τ2τ1,s2≥τ2τ1,s+12\displaystyle \frac{\tau_{1,s}+\tau_2}{\tau_{1,s}^2} \ge \frac{\tau_2}{\tau_{1,s+1}^2}τ1,s2​τ1,s​+τ2​​≥τ1,s+12​τ2​​.

These two inequalities let the recursions (C.3) and (C.2) be chained over all epochs.

Differences from the source: none.

Preamble
import Mathlib
import Definitions.Def_KatyushaNs_tau1
Formal statement
namespace KatyushaNs

/-- **The two inequalities satisfied by `τ_{1,s} = 2/(s+4)`.**
Allen-Zhu, *Katyusha: The First Direct Acceleration of Stochastic Gradient Methods*,
arXiv:1603.05953v6, proof of Theorem 4.1 (App. C.1), unnumbered display, p. 27 (PDF p. 28):
"At this point, if we choose τ_{1,s} = 2/(s+4) ≤ 1/2, it satisfies
1/τ²_{1,s} ≥ (1 − τ_{1,s+1})/τ²_{1,s+1} and (τ_{1,s} + τ₂)/τ²_{1,s} ≥ τ₂/τ²_{1,s+1}."

Conclusion: for every epoch `s ≥ 0`, with `τ₂ = 1/2`: `τ_{1,s} ≤ 1/2`,
`(1 − τ_{1,s+1})/τ²_{1,s+1} ≤ 1/τ²_{1,s}` and `τ₂/τ²_{1,s+1} ≤ (τ_{1,s} + τ₂)/τ²_{1,s}`.

**Formalization Note.** `τ₂ = 1/2` (Algorithm 2, line 2) is written as `1/2`. -/
theorem tau_schedule_inequalities (s : ℕ) :
    tau1 s ≤ 1 / 2 ∧
      (1 - tau1 (s + 1)) / tau1 (s + 1) ^ 2 ≤ 1 / tau1 s ^ 2 ∧
      (1 / 2) / tau1 (s + 1) ^ 2 ≤ (tau1 s + 1 / 2) / tau1 s ^ 2 := by sorry

end KatyushaNs
Source
Allen-Zhu, Katyusha: The First Direct Acceleration of Stochastic Gradient Methods, arXiv:1603.05953v6, proof of Theorem 4.1 (App. C.1), unnumbered display, p. 27

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