Lemma 2.12 — one projected gradient step
ProvedModernOnlineLearning.OGD.lemma_2_12online-gradient-descentonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1regret
Let be nonempty, closed, and convex; let be convex and differentiable on an open set containing ; let , , , and . Then
This is the per-round estimate summed in the regret theorem.
Formalization Note Membership of in is explicit, as required by Algorithm 2.1. The ambient space is a complete real inner-product space.
Preamble
import Mathlib import Definitions.Def_OnlineConvexOpt_FirstOrder_Protocol
Formal statement
namespace ModernOnlineLearning.OGD
/-- Orabona, Lemma 2.12, p. 13: the two one-step inequalities for projected
online gradient descent. -/
theorem lemma_2_12 {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 < η)
(hopen : ∃ U : Set E, IsOpen U ∧ V ⊆ U ∧ ConvexOn ℝ U loss ∧ DifferentiableOn ℝ loss U)
(hg : HasGradientAt loss g x)
(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.12, p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.