Proof of Theorem 4.1, p. 27: inequalities of the schedule
ProvedKatyushaNs.tau_schedule_inequalitiesconvex-optimizationstochastic-optimizationvariance-reduction
Let for and . Then for every :
- ;
- ;
- .
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