Theorem 2.13, p. 13 — constant-step gradient bound for linear losses on all of Euclidean space
ProvedModernOnlineLearning.Classification.theorem_2_13gradient-descentonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret
Consider linear losses with gradient vectors . Let be fixed and let for rounds . For every ,
This is the constant-step part of Theorem 2.13 specialized to the unprojected linear losses used in the Perceptron analysis.
Formalization Note The book states the theorem for a closed convex feasible set and convex differentiable losses. The Lean statement uses the stated linear-loss, whole-space specialization, so the linear loss difference is exactly . No bounded diameter is needed in this part.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Classification_Perceptron
Formal statement
namespace ModernOnlineLearning.Classification
/-- Orabona, Theorem 2.13, constant-step linear-loss case on all of `ℝ^d`, p. 13.
The update is unprojected gradient descent. -/
theorem theorem_2_13 {d : ℕ} (T : ℕ) (η : ℝ) (hη : 0 < η)
(g x : ℕ → ModernOnlineLearning.Adaptive.Vec d)
(hrun : ∀ t ∈ Finset.Icc 1 T, x (t + 1) = x t - η • g t)
(u : ModernOnlineLearning.Adaptive.Vec d) :
(∑ t ∈ Finset.Icc 1 T, inner ℝ (g t) (x t - u)) ≤
‖u - x 1‖ ^ 2 / (2 * η) +
η / 2 * (∑ t ∈ Finset.Icc 1 T, ‖g t‖ ^ 2) -
‖x (T + 1) - u‖ ^ 2 / (2 * η) := by sorry
end ModernOnlineLearning.Classification
Source
Orabona, arXiv:1912.13213v10, Theorem 2.13, constant-step clause, p. 13; specialization used in proof of Theorem 8.2, p. 145
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.