Theorem 3.2 — Ω(DG√T) worst-case regret lower bound (corrected regret definition, Lipschitz costs)
ProvedOnlineConvexOpt.FirstOrder.online_gradient_descent_lower_bound_v2Statement (Theorem 3.2). Any algorithm for online convex optimization incurs regret in the worst case. Formally: there is an absolute constant such that for every dimension there is a convex, complete, nonempty decision set of diameter at most and a constant such that, for every non-anticipating algorithm playing in and every horizon , there is a cost sequence — each convex on , -Lipschitz on and with every gradient at a point of of norm at most (the chapter's standing assumption " bounds the (sub)gradient norms over ", p. 20) — chosen after and , against which 's regret is at least .
Formalization Note. The retired statement was proved only through two junk routes: its regret RegretT (from OnlineConvexOpt_FirstOrder_Protocol) returned the junk value for the comparator term outside , so constant costs on gave "regret" ; and its only constraint on the adversary's costs was a bound on gradients where they exist, which is vacuous for costs with no gradient on . The new statement imports OnlineConvexOpt_FirstOrder_Protocol_v2 (RegretT subtracts the real infimum of the cumulative cost over ; genuine here since is nonempty and bounded and the costs are Lipschitz on ) and requires the adversary's costs to be -Lipschitz on in addition to convex with -bounded gradients, exactly the class the book's hard instance (linear costs on the hypercube) belongs to. The quantifier order (instance, then algorithm and horizon, then costs) is unchanged; the parenthetical "even for costs drawn from a fixed stationary distribution" is not formalized, as before.
import Mathlib import Definitions.Def_OnlineConvexOpt_FirstOrder_Protocol_v2 import Definitions.Def_OnlineConvexOpt_FirstOrder_Algorithm open OnlineConvexOpt.FirstOrder
namespace OnlineConvexOpt.FirstOrder
/-- Theorem 3.2 (Hazan, *Introduction to Online Convex Optimization*, 2nd ed.,
arXiv:1909.05207v3, p. 45, PDF p. 67). Any online algorithm for online convex optimization
incurs `Ω(DG√T)` regret in the worst case: for every dimension `n` there is a decision set `K`
(convex, complete, nonempty, diameter `≤ D`) such that **for every** non-anticipating algorithm
`A` playing in `K` and every horizon `T ≥ 1`, there is a cost sequence `f` (chosen against `A`)
satisfying the chapter's standing assumptions — each `f_t` convex on `K`, `G`-Lipschitz on `K`
and with every gradient at a point of `K` of norm `≤ G` (book p. 20: `G` bounds the subgradient
norms over `K`, which implies `G`-Lipschitzness) — forcing regret at least `c · D · G · √T`,
for an absolute constant `c > 0`. The quantifier order is load-bearing: the cost sequence is
chosen *after* the algorithm and the horizon. (The parenthetical strengthening "even if the cost
functions are generated from a fixed stationary distribution" is not captured here.)
Corrected version: `RegretT` is now the `OnlineConvexOpt_FirstOrder_Protocol_v2` regret (genuine
infimum over `K`; the retired one returned the junk value `0` outside `K`, which let constant
costs on a singleton `K` "prove" the bound), and the adversary's costs must be `G`-Lipschitz on
`K` and not merely have `G`-bounded gradients where differentiable (the retired hypothesis was
vacuous for costs that are nowhere differentiable on `K`, e.g. on a `K` with empty interior). -/
theorem online_gradient_descent_lower_bound_v2 :
∃ c : ℝ, 0 < c ∧ ∀ n : ℕ, 0 < n →
∃ (K : Set (EuclideanSpace ℝ (Fin n))) (D G : ℝ), 0 < D ∧ 0 < G ∧
Convex ℝ K ∧ IsComplete K ∧ K.Nonempty ∧ (∀ x ∈ K, ∀ y ∈ K, dist x y ≤ D) ∧
∀ (A : (ℕ → EuclideanSpace ℝ (Fin n) → ℝ) → ℕ → EuclideanSpace ℝ (Fin n)),
IsOnlineAlgorithm K A →
∀ T : ℕ, 1 ≤ T →
∃ f : ℕ → EuclideanSpace ℝ (Fin n) → ℝ,
(∀ t, ConvexOn ℝ K (f t)) ∧
(∀ t, ∀ x ∈ K, ∀ y ∈ K, |f t x - f t y| ≤ G * dist x y) ∧
(∀ t, ∀ x ∈ K, ∀ v, HasGradientAt (f t) v x → ‖v‖ ≤ G) ∧
c * D * G * Real.sqrt T ≤ RegretT K f (fun t => A f t) T := by sorry
end OnlineConvexOpt.FirstOrder