Lemma 2.31 — one projected subgradient step
ProvedModernOnlineLearning.OGD.lemma_2_31online-learningonline-subgradient-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret
Let be nonempty, closed, and convex; let and . If is a subgradient of at and , then
This extends the per-round OGD estimate to subgradient choices.
Formalization Note Losses are real valued on , and the subgradient inequality is required only against points of . A full-space subgradient as in Definition 2.20 implies this relative condition.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_OGD_Defs
Formal statement
namespace ModernOnlineLearning.OGD
/-- Orabona, Lemma 2.31, p. 19: the projected subgradient step obeys the
same one-step regret inequalities. -/
theorem lemma_2_31 {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
[CompleteSpace E] (V : Set E) (hV : V.Nonempty) (hc : IsClosed V)
(hv : Convex ℝ V) (loss : E → ℝ) (x xn g u : E) (η : ℝ)
(hx : x ∈ V) (hu : u ∈ V) (hη : 0 < η)
(hg : IsSubgradientOn V loss x g)
(hxn : OnlineConvexOpt.FirstOrder.IsMetricProjection V (x - η • g) xn) :
η * (loss x - loss u) ≤ η * inner ℝ g (x - u) ∧
η * inner ℝ g (x - u) ≤
(1 / 2 : ℝ) * ‖x - u‖ ^ 2 - (1 / 2 : ℝ) * ‖xn - u‖ ^ 2 +
(η ^ 2 / 2) * ‖g‖ ^ 2 := by sorry
end ModernOnlineLearning.OGD
Source
Orabona, arXiv:1912.13213v10, Lemma 2.31, p. 19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.