Theorem 10.1 — Dynamic regret of OGD, (corrected display)
ProvedOnlineConvexOpt.ChangingEnv.dynamic_regret_bound_v2Statement (Theorem 10.1, explicit form). Let be a nonempty convex set of diameter at most in a real Hilbert space and cost functions convex on with gradients of norm at most on . Run online gradient descent (Algorithm 8) with a constant step size . Then for every comparator sequence and every ,
With this is the book's headline , the path length.
Formalization Note. The retired statement transcribed the final display of the book's proof, . That display is not scale-invariant ( adds a length to the constant ) and is false for : the chain's step silently assumes . The statement here is the inequality the chain actually establishes (after halving) before that step: with . The path sum equals PathLength u T - 1. Rounds are -indexed; the standing assumptions on and are as in Chapter III. The file imports the _v2 definition modules (DynamicRegretT is unchanged there).
import Mathlib import Definitions.Def_OnlineConvexOpt_ChangingEnv_Regret_v2 import Definitions.Def_OnlineConvexOpt_FirstOrder_Protocol_v2 open OnlineConvexOpt.FirstOrder
namespace OnlineConvexOpt.ChangingEnv
/-- Theorem 10.1 (Hazan, *Introduction to Online Convex Optimization*, 2nd ed.,
arXiv:1909.05207v3, p. 170, PDF p. 192), explicit form. Online gradient descent (Algorithm 8)
with a constant step size `η > 0` guarantees, for every comparator sequence `u_1,...,u_T ∈ K`,
`DynamicRegret_T(A,u) ≤ (D² + 2D Σ_{t=1}^{T-1} ‖u_t - u_{t+1}‖)/(2η) + (η/2) G² T`,
the inequality the book's proof establishes ("following the steps of the proof of Theorem
3.1"); with `η ≈ √(P/T)` this gives the headline `DynamicRegret_T = O(√(T·P(u_1,...,u_T)))`.
`K` (convex, nonempty, diameter `≤ D`) and `f`, convex with gradient norm `≤ G` on `K`, are
this section's standing hypotheses (reused from Chapter III), stated explicitly. In the
0-indexed convention the path sum is `Σ_{t < T-1} ‖u t - u (t+1)‖ = PathLength u T - 1`.
Corrected version: the retired statement transcribed the book's final display
`(3D²/(2η))·P(u) + (η/2)G²T` with `P(u) = Σ‖u_t - u_{t+1}‖ + 1`, which is not scale-invariant
(it adds a length to the constant `1`) and is false for `D < 2/3`: the step
`D·Σ‖u_{t-1} - u_t‖ ≤ D²·Σ‖…‖` in the book's chain silently assumes `D ≥ 1`. The bound stated
here is the one the chain actually proves, after halving, before that step. -/
theorem dynamic_regret_bound_v2
{E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
(K : Set E) (hKconv : Convex ℝ K) (hKne : K.Nonempty)
(D G : ℝ) (hDpos : 0 < D) (hGpos : 0 < G) (hD : ∀ x ∈ K, ∀ y ∈ K, dist x y ≤ D)
(f : ℕ → E → ℝ) (hfconv : ∀ t, ConvexOn ℝ K (f t))
(hfG : ∀ t, ∀ x ∈ K, ∀ v, HasGradientAt (f t) v x → ‖v‖ ≤ G)
(η : ℝ) (hηpos : 0 < η)
(u : ℕ → E) (hu : ∀ t, u t ∈ K)
(x g : ℕ → E) (hOGD : IsOnlineGradientDescent K f (fun _ => η) x g)
(T : ℕ) (hT : 1 ≤ T) :
DynamicRegretT f x u T ≤
(D ^ 2 + 2 * D * ∑ t ∈ Finset.range (T - 1), ‖u t - u (t + 1)‖) / (2 * η) +
(η / 2) * G ^ 2 * T := by sorry
end OnlineConvexOpt.ChangingEnv