Theorem 15.12, pp. 248–249 — player regrets bound the averaged duality gap
ProvedModernOnlineLearning.SaddlePoint.theorem_15_12duality-gaponline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1saddle-point
Let be nonempty closed convex sets, and let , be the simultaneous outputs of Algorithm 15.1 for , where . Player receives and player receives . Their regret identities say, for and ,
If is convex in its first argument and concave in its second, and minimizes while maximizes on their respective sets, then
The inequality converts two online regret bounds into a bound on the attained duality gap.
Formalization Note The two regret expressions are expanded as finite sums. The attained extrema appear as point witnesses, and the average uses the book's one-based index.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_SaddlePoint_Setting set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.SaddlePoint
/-- Theorem 15.12, pp. 248–249: the two regret identities and the
online-to-saddle-point duality-gap inequality. -/
theorem theorem_15_12 {EX EY : Type*}
[NormedAddCommGroup EX] [NormedSpace ℝ EX] [FiniteDimensional ℝ EX]
[NormedAddCommGroup EY] [NormedSpace ℝ EY] [FiniteDimensional ℝ EY]
(X : Set EX) (Y : Set EY) (f : EX → EY → ℝ)
(x : ℕ → EX) (y : ℕ → EY) (T : ℕ)
(hT : 1 ≤ T) (hXne : X.Nonempty) (hYne : Y.Nonempty)
(hXclosed : IsClosed X) (hYclosed : IsClosed Y)
(hX : Convex ℝ X) (hY : Convex ℝ Y)
(hx : ∀ t ∈ Finset.Icc 1 T, x t ∈ X)
(hy : ∀ t ∈ Finset.Icc 1 T, y t ∈ Y)
(hfx : ∀ v ∈ Y, ConvexOn ℝ X (fun w => f w v))
(hfy : ∀ u ∈ X, ConcaveOn ℝ Y (f u))
(xm : EX) (ym : EY)
(hmin : IsMinOn X (fun w => f w (avg T y)) xm)
(hmax : IsMaxOn Y (f (avg T x)) ym) :
(∀ u ∈ X,
(∑ t ∈ Finset.Icc 1 T, f (x t) (y t)) / T -
(∑ t ∈ Finset.Icc 1 T, f u (y t)) / T =
(∑ t ∈ Finset.Icc 1 T, (f (x t) (y t) - f u (y t))) / T) ∧
(∀ v ∈ Y,
(∑ t ∈ Finset.Icc 1 T, f (x t) v) / T -
(∑ t ∈ Finset.Icc 1 T, f (x t) (y t)) / T =
(∑ t ∈ Finset.Icc 1 T, (f (x t) v - f (x t) (y t))) / T) ∧
(f (avg T x) ym - f xm (avg T y) ≤
((∑ t ∈ Finset.Icc 1 T, (f (x t) (y t) - f xm (y t))) +
(∑ t ∈ Finset.Icc 1 T, (f (x t) ym - f (x t) (y t)))) / T) := by sorry
end ModernOnlineLearning.SaddlePoint
Source
Orabona, arXiv:1912.13213v10, Theorem 15.12, pp. 248–249
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.