Theorem 16.4 — online linear regret bounds empirical Rademacher complexity
ProvedModernOnlineLearning.ToX.theorem_16_4online-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1rademacher-complexityregret
Let be symmetric under negation, let , and let be nonempty, bounded and closed. Suppose a deterministic online algorithm chooses using only past gradients and has regret at most for every sequence of linear loss gradients in . For the class ,
This reduction turns any uniform online linear regret bound into a bound on the complexity of the same linear class.
Formalization Note The algorithm is deterministic and nonanticipating; the book also permits independent internal randomization. The sample is indexed from one and . The real supremum is taken over exactly ; boundedness and nonemptiness rule out default values on unbounded or empty sets.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_ToX_Algorithms
Formal statement
namespace ModernOnlineLearning.ToX
/-- Theorem 16.4, p. 272: a deterministic non-anticipating online linear
algorithm with worst-case regret at most `R T` bounds the empirical
Rademacher complexity of the linear class indexed by `V`. -/
theorem theorem_16_4 {d T : ℕ} (hT : 1 ≤ T)
(Z V : Set (Fin d → ℝ)) (z : ℕ → Fin d → ℝ)
(hZsym : ∀ a ∈ Z, -a ∈ Z)
(hz : ∀ t ∈ Finset.Icc 1 T, z t ∈ Z)
(hVne : V.Nonempty) (hVbd : Bornology.IsBounded V) (hVclosed : IsClosed V)
(R : ℕ → ℝ) (A : (ℕ → Fin d → ℝ) → ℕ → Fin d → ℝ)
(hA : IsOnlineAlgorithm T Z V (R T) A) :
empiricalRadLinear (T := T) V hT ⟨hVne, hVbd⟩ z ≤ R T / (T : ℝ) := by sorry
end ModernOnlineLearning.ToX
Source
Orabona, arXiv:1912.13213v10, Theorem 16.4, p. 272, displays (16.3)–(16.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.