Theorem 1.2 — anytime error lower bound at exponent
OpenSilverRateLB.Supplement.theorem_1_2convex-optimizationgradient-descentlower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let
and let be one infinite sequence of nonnegative stepsizes, fixed across all horizons, with . There is an absolute constant , independent of , such that for every ambient smoothness constant ,
for infinitely many .
Thus no single nonnegative stepsize schedule can have worst-case error asymptotically better than the anytime silver exponent at every stopping time.
Formalization Note H t represents , schedulePrefix H n is , and the infinite set of horizons is stated with Set.Infinite. The worst-case rate is the published -valued definition.
Differences from the source:
- generalization: for one ambient smoothness constant → , quantified after and ; reason: the same absolute works for every , and this specializes to any fixed by the paper's rescaling convention
- reading: (base not stated) → natural logarithm
Real.log; reason: another fixed base changes only the absolute constant - encoding: and →
H : ℕ → ℝwithH t = h_{t+1}andschedulePrefix H n; reason: the same infinite schedules and prefixes, with a zero-based index - encoding: for infinitely many →
Set.Infiniteof the horizons satisfying the bound; reason: literal Lean expression of the paper's quantifier - encoding: a real supremum →
worstCaseRatein and the lower bound embedded byENNReal.ofReal; reason: the published rate uses the extended codomain to avoid a junk real supremum, and is finite on these schedules
Preamble
import Mathlib import Definitions.Def_SilverRateLB_Supplement_pAny import Definitions.Def_SilverRateLB_worstCaseRate open scoped ENNReal
Formal statement
namespace SilverRateLB.Supplement
/-- **Theorem 1.2 (anytime error lower bound).** There is an absolute constant `C > 0` such
that every infinite nonnegative schedule `H = (h_t)_{t≥1}` satisfies
`ℛ_n(H_n) ≥ n^{−(p_any + C√(log log n / log n))}` for infinitely many `n`.
Ye, Liu, *Silver Rate Is (Almost) Optimal for Gradient Descent*, arXiv:2609.09152,
Theorem 1.2, (3), p. 5.
**Formalization Note** `C` is chosen before `H` and `L`, hence is uniform over all schedules
and ambient smoothness constants. `H t` is the 1-based paper entry `h_{t+1}`, and
`schedulePrefix H n` is the single schedule's prefix `H_n`. "Infinitely many" is expressed
literally by `Set.Infinite`. `log` is the natural logarithm, and `worstCaseRate` is valued in
`ℝ≥0∞`. -/
theorem theorem_1_2 :
∃ C : ℝ, 0 < C ∧ ∀ H : ℕ → ℝ, (∀ t, 0 ≤ H t) → ∀ L : ℝ, 0 < L →
Set.Infinite {n : ℕ |
ENNReal.ofReal ((n : ℝ) ^ (-(pAny + C * Real.sqrt
(Real.log (Real.log n) / Real.log n)))) ≤
SilverRateLB.worstCaseRate L (schedulePrefix H n)} := by sorry
end SilverRateLB.Supplement
Source
Ye, Liu, Silver Rate Is (Almost) Optimal for Gradient Descent, arXiv:2609.09152 (sha256 6797dde3…), Theorem 1.2, (3), p. 5; proof §C.2, pp. 32–33