Online gradient descent has regret at most for linear losses
ProvedApproachRegret.Calibration.ogd_regret_boundonline-gradient-descentonline-learningp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let be nonempty, closed and convex, let , and let . Let with for every , and let be loss vectors with . If are produced by online gradient descent with step size , , then
This is Zinkevich's regret bound for online gradient descent, which the proof of Theorem 22 invokes for the cube and the losses .
Formalization Note The page states the bound with "the ℓ₂ diameter of the set". The statement assumes only on , which the diameter implies because ; this is the form Theorem 22 needs, with about . The step size is pinned to , the tuning under which the bound holds; the page's Algorithm 4 says only . The minimum is sInf of the image of , which is bounded.
Preamble
import Mathlib import Definitions.Def_ApproachRegret_Calibration_Game import Definitions.Def_ApproachRegret_Calibration_Algorithms
Formal statement
namespace ApproachRegret.Calibration
/-- Proof of Theorem 22 (p. 44): Online Gradient Descent guarantees regret at most `D G √T`.
For a nonempty closed convex `K ⊆ ℝⁿ`, a start `θ₁ ∈ K` with `‖θ − θ₁‖ ≤ D` on `K`, linear
losses with `‖g_t‖ ≤ G`, and step size `η = D / (G √T)`, the OGD iterates satisfy
`∑_{t=1}^T ⟨g_t, θ_t⟩ − min_{θ ∈ K} ∑_{t=1}^T ⟨g_t, θ⟩ ≤ D G √T`. -/
theorem ogd_regret_bound {n : ℕ} (K : Set (ApproachRegret.ToOLO.E n)) (hKne : K.Nonempty) (hKc : IsClosed K)
(hKcvx : Convex ℝ K) (T : ℕ) (hT : 1 ≤ T) (D G : ℝ) (hD : 0 < D) (hG : 0 < G)
(g θ : ℕ → ApproachRegret.ToOLO.E n) (hθ1 : θ 1 ∈ K) (hdiam : ∀ x ∈ K, ‖x - θ 1‖ ≤ D)
(hg : ∀ t, 1 ≤ t → t ≤ T → ‖g t‖ ≤ G)
(hrun : IsOGDRun K (D / (G * Real.sqrt T)) T g θ) :
linRegret K T g θ ≤ D * G * Real.sqrt T := by sorry
end ApproachRegret.Calibration
Source
Abernethy, Bartlett, Hazan (COLT 2011, JMLR W&CP 19), Algorithm 4 and proof of Theorem 22, p. 44
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.