Corollary 4.2 — Optimised regret bound for Euclidean FTRL
ProvedSubquadCutReach.Faster.Supplement.corollary_4_2online-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let , let and let be an integer. Run Euclidean FTRL in from with the update and the step
If the loss vectors satisfy in every round , then simultaneously for every comparator with ,
The losses may be arbitrary, including adaptively chosen ones. This bound drives the averaging guarantee of Lemma 3.7 and hence the warm-up protocol of Theorem 1.1. The paper derives it from a cited regret bound (Theorem 4.1, from Shalev-Shwartz), which is not assumed here.
Differences from the source:
- encoding: rounds with → 0-based rounds with
ftrlIter η ℓ 0 = 0; reason: index shift only - encoding: vectors in with and →
EuclideanSpace ℝ (Fin n)with Mathlib's inner product and norm; reason: the same inner product and norm - encoding: loss vectors that may depend on the history → an arbitrary sequence
ℓ : ℕ → ℝ^n, quantified universally; reason: each adaptive run is one fixed sequence, and the iterates use only past losses
Preamble
import Definitions.Def_SubquadCutReach_Faster_Supplement_FTRL set_option autoImplicit false
Formal statement
namespace SubquadCutReach.Faster.Supplement
/-- Corollary 4.2, p. 13 (PDF 15). Rounds `1..T` are `t ∈ range T`; the loss sequence is
arbitrary, which covers adaptively chosen losses. -/
theorem corollary_4_2 (n : ℕ) (D L : ℝ) (hD : 0 < D) (hL : 0 < L) (T : ℕ) (hT : 1 ≤ T)
(ℓ : ℕ → EuclideanSpace ℝ (Fin n)) (hℓ : ∀ t < T, ‖ℓ t‖ ≤ L) :
∀ u : EuclideanSpace ℝ (Fin n), ‖u‖ ≤ D →
ftrlRegret (D / (L * Real.sqrt (2 * (T : ℝ)))) ℓ T u ≤ D * L * Real.sqrt (2 * (T : ℝ)) := by sorry
end SubquadCutReach.Faster.Supplement
Source
Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal, STOC 2027 submission #503 (October 2026), p. 13, Corollary 4.2 (PDF p. 15)