Theorem 4.14, p. 40 — adaptive OSD regret in accumulated squared gradient norm
ProvedModernOnlineLearning.Adaptive.theorem_4_14Let be nonempty, closed, and convex, with for all . For , let be convex losses, and run projected online subgradient descent from any . At round , use a subgradient and step size ; leave the point unchanged when . Then every competitor satisfies
The bound adapts to the observed subgradient magnitudes and supplies the first step toward the self-bounded-loss guarantee.
Formalization Note The identity with the minimum over constant positive step sizes is stated only when , as the existence of a least value of on whose -multiple equals : when every the infimum is not attained, so the printed "min" is not literally true there. Losses are real-valued and subgradients are full-space subgradients. The diameter condition uses , as in Theorem 4.14; the run predicate requires .
import Mathlib import Definitions.Def_ModernOnlineLearning_Adaptive_Defs
namespace ModernOnlineLearning.Adaptive
/-- Orabona, Theorem 4.14, p. 40: the regret inequality, and the displayed
identity `D√(2Σ‖g_t‖²) = √2 min_{η>0}(D²/(2η) + (η/2)Σ‖g_t‖²)`. The minimum is
attained only when `Σ‖g_t‖² > 0`, so the identity is stated under that case. -/
theorem theorem_4_14 {d : ℕ} (V : Set (Vec d)) (ℓ : ℕ → Vec d → ℝ)
(D : ℝ) (T : ℕ) (x g : ℕ → Vec d)
(hT : 1 ≤ T) (hVne : V.Nonempty) (hVclosed : IsClosed V)
(hVconv : Convex ℝ V)
(hdiam : ∀ a ∈ V, ∀ b ∈ V, ‖a - b‖ ≤ D)
(hconv : ∀ t ∈ Finset.Icc 1 T, ConvexOn ℝ Set.univ (ℓ t))
(hrun : IsAdaptiveOSDRun V ℓ D T x g) :
(∀ u ∈ V, regret ℓ x u T ≤ D * Real.sqrt (2 * gradientEnergy g T)) ∧
(0 < gradientEnergy g T → ∃ m : ℝ,
IsLeast ((fun η : ℝ => D ^ 2 / (2 * η) + η / 2 * gradientEnergy g T) ''
Set.Ioi 0) m ∧
D * Real.sqrt (2 * gradientEnergy g T) = Real.sqrt 2 * m) := by sorry
end ModernOnlineLearning.Adaptive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.