Theorem 5.4 — unprojected OSD with t^(−α) steps can incur order T^(2−α) regret
ProvedModernOnlineLearning.LowerBounds.theorem_5_4lower-boundsonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1subgradient-descent
Fix a Euclidean dimension , , and define as above. If the horizon satisfies , then there is a sequence of convex, -Lipschitz losses for which unprojected online subgradient descent, initialized at and using step size , has
This shows that the same decaying steps can perform much worse when there is no bounded feasible domain.
Formalization Note The losses are represented by linear functions with , as in the book's construction. Their convexity and Lipschitz property follow from this form. The displayed limit is a separate claim and is outside this item.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_LowerBounds_phi
Formal statement
namespace ModernOnlineLearning.LowerBounds
/-- The existence and regret-bound part of Theorem 5.4, printed p. 52.
The adversarial losses are linear along one coordinate, as in the source proof;
the limit statement about `φ` is not part of this declaration. -/
theorem theorem_5_4 {d : ℕ} (hd : 0 < d)
(α : ℝ) (hαpos : 0 < α) (hαlt : α < 1)
(T : ℕ) (hT : 2 / ((1 - α) * phi α) ≤ (T : ℝ)) :
∃ (g x : ℕ → EuclideanSpace ℝ (Fin d)),
x 1 = 0 ∧
(∀ t ∈ Finset.Icc 1 T, ‖g t‖ ≤ 1) ∧
(∀ t ∈ Finset.Icc 1 T,
x (t + 1) = x t - ((t : ℝ) ^ (-α)) • g t) ∧
(1 / 2 : ℝ) * phi α * (T : ℝ) ^ (2 - α) ≤
∑ t ∈ Finset.Icc 1 T, inner ℝ (g t) (x t) := by sorry
end ModernOnlineLearning.LowerBounds
Source
Orabona, arXiv:1912.13213v10, Theorem 5.4 and its construction, p. 52
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.