Theorem 3.3 — Logarithmic regret of OGD for strongly convex losses (corrected regret definition)
ProvedOnlineConvexOpt.FirstOrder.online_gradient_descent_strongly_convex_regret_v2Statement (Theorem 3.3). Let be a convex, complete, nonempty subset of a real Hilbert space and let be cost functions that are convex and -strongly convex on (for a common ), with every gradient at a point of of norm at most . Run online gradient descent (Algorithm 8) with step sizes (the book's under the -indexed shift). Then for every ,
Formalization Note. The retired version used OnlineConvexOpt.FirstOrder.RegretT of OnlineConvexOpt_FirstOrder_Protocol, whose comparator ⨅ y ∈ K, … evaluates to the junk value at every , so the subtracted term was for every bounded and the statement was false. The new statement imports OnlineConvexOpt_FirstOrder_Protocol_v2, whose RegretT subtracts the real infimum of . Under the hypotheses this infimum is genuine: is -strongly convex on with gradient at , so is bounded below on without any diameter bound (matching the book, which does not mention in Theorem 3.3). StrongConvexOn K α is Mathlib's -strong convexity; rounds are -indexed; bounds the gradient norm at every point of where is differentiable. No other change from the retired statement.
import Mathlib
import Definitions.Def_OnlineConvexOpt_FirstOrder_Protocol_v2
open OnlineConvexOpt.FirstOrder
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (K : Set E) (G : ℝ) (f : ℕ → E → ℝ)
namespace OnlineConvexOpt.FirstOrder
/-- Theorem 3.3 (Hazan, *Introduction to Online Convex Optimization*, 2nd ed.,
arXiv:1909.05207v3, p. 47, PDF p. 69). For `α`-strongly convex loss functions, online gradient
descent (Algorithm 8) with step sizes `η_t = 1/(αt)` (`t ∈ [T]` in the book's 1-indexed rounds;
here `η` at round `t`, in the 0-indexed convention of `RegretT`, is the book's
`η_{t+1} = 1 / (α(t+1))`) achieves, for every `T ≥ 1`,
`Regret_T ≤ (G² / (2α)) (1 + log T)`.
`K` (convex, complete, nonempty) and the costs `f`, convex with gradient norm bounded by `G`
on `K` (book p. 20, PDF 42) and `α`-strongly convex on `K`, are the chapter-wide standing
hypotheses of §2.1/§2.2 (the diameter bound `D` is not needed for this bound, matching the book,
which does not mention `D` in Theorem 3.3). Corrected version: `RegretT` is now the
`OnlineConvexOpt_FirstOrder_Protocol_v2` regret, whose comparator is the genuine infimum over
`K` (the retired definition's `⨅ y ∈ K` binder returned the junk value `0` outside `K`). Under
these hypotheses the cumulative cost is bounded below on `K` (strong convexity at `x_0 ∈ K`
plus the gradient bound there), so the infimum is the book's `min`. -/
theorem online_gradient_descent_strongly_convex_regret_v2
(hKconv : Convex ℝ K) (hKcomplete : IsComplete K) (hKne : K.Nonempty) (hGpos : 0 < G)
(hfconv : ∀ t, ConvexOn ℝ K (f t))
(hG : ∀ t, ∀ x ∈ K, ∀ v, HasGradientAt (f t) v x → ‖v‖ ≤ G)
(α : ℝ) (hα : 0 < α) (hfSC : ∀ t, StrongConvexOn K α (f t))
(η : ℕ → ℝ) (hη : ∀ t : ℕ, η t = 1 / (α * (t + 1)))
(x g : ℕ → E) (hOGD : IsOnlineGradientDescent K f η x g)
(T : ℕ) (hT : 1 ≤ T) :
RegretT K f x T ≤ (G ^ 2 / (2 * α)) * (1 + Real.log T) := by sorry
end OnlineConvexOpt.FirstOrder