Equation (12.2) — split linearized regret at the unconstrained prediction
ProvedModernOnlineLearning.Reductions.eq_12_2online-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1reductionregret
In a projected run of Algorithm 12.1, let be fixed and let satisfy the subgradient inequality for at on . For ,
This isolates the term that the surrogate loss must compensate when lies outside .
Formalization Note The loss subgradient inequality is restricted to , which suffices because the comparator lies in . The ambient space is finite-dimensional, and the book's round index starts at one.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Reductions_Setting
Formal statement
namespace ModernOnlineLearning.Reductions
/-- Orabona, equation (12.2), p. 196: first-order ModernOnlineLearning.OGD.regret and its split at `z_t`. -/
theorem eq_12_2 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (V W : Set E) (hV : V.Nonempty)
(hclosed : IsClosed V) (hconv : Convex ℝ V) (hVW : V ⊆ W)
(loss : ℕ → E → ℝ) (z x : ℕ → E) (g q : ℕ → E →L[ℝ] ℝ)
(T : ℕ) (hT : 1 ≤ T) (hRun : IsProjectedRun V W loss z x g q T)
(u : E) (hu : u ∈ V) :
ModernOnlineLearning.OGD.regret loss x u T ≤ ∑ t ∈ Finset.Icc 1 T, g t (x t - u) ∧
(∑ t ∈ Finset.Icc 1 T, g t (x t - u)) =
∑ t ∈ Finset.Icc 1 T, (g t (z t - u) + g t (x t - z t)) := by sorry
end ModernOnlineLearning.Reductions
Source
Orabona, arXiv:1912.13213v10, equation (12.2), proof of Theorem 12.5, p. 196
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.