§15.5, p. 262 — summed player regrets with smoothness coefficients
ProvedModernOnlineLearning.SaddlePoint.regret_sum_15_26online-learningoptimistic-ftrlp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1saddle-point
Let both players run Algorithm 15.6 on nonempty closed convex sets . Assume is convex in and concave in , its partial gradients satisfy (15.7)–(15.10), and the regularizers are respectively - and -strongly convex, with positive parameters. For every and ,
This is the intermediate estimate immediately preceding Theorem 15.26; its two stability coefficients determine the theorem's required lower bounds on and .
Formalization Note The dual norms are operator norms. The sequence starts at round one, and the stability sums start at round two. The run is constrained only on rounds ; the statement involves no iterate after .
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_SaddlePoint_Setting set_option autoImplicit false
Formal statement
namespace ModernOnlineLearning.SaddlePoint
/-- The summed-regret display in §15.5, p. 262, immediately before Theorem 15.26. -/
theorem regret_sum_15_26 {EX EY : Type*}
[NormedAddCommGroup EX] [NormedSpace ℝ EX] [FiniteDimensional ℝ EX]
[NormedAddCommGroup EY] [NormedSpace ℝ EY] [FiniteDimensional ℝ EY]
(X : Set EX) (Y : Set EY) (f : EX → EY → ℝ)
(gx : EX → EY → EX →L[ℝ] ℝ) (gy : EX → EY → EY →L[ℝ] ℝ)
(ψX : EX → ℝ) (ψY : EY → ℝ) (x : ℕ → EX) (y : ℕ → EY)
(LXX LXY LYY lamX lamY : ℝ) (T : ℕ)
(hT : 1 ≤ T) (hXne : X.Nonempty) (hYne : Y.Nonempty)
(hXclosed : IsClosed X) (hYclosed : IsClosed Y)
(hX : Convex ℝ X) (hY : Convex ℝ Y)
(hfx : ∀ v ∈ Y, ConvexOn ℝ X (fun w => f w v))
(hfy : ∀ u ∈ X, ConcaveOn ℝ Y (f u))
(hLXX : 0 ≤ LXX) (hLXY : 0 ≤ LXY) (hLYY : 0 ≤ LYY)
(hlamX : 0 < lamX) (hlamY : 0 < lamY)
(hψX : StrongConvexOn X lamX ψX) (hψY : StrongConvexOn Y lamY ψY)
(hsmooth : IsSmoothSaddleOn X Y f gx gy LXX LXY LYY)
(hrun : IsOptFTRLSaddleRun X Y ψX ψY gx gy x y T) :
∀ u ∈ X, ∀ v ∈ Y,
(∑ t ∈ Finset.Icc 1 T, (f (x t) v - f u (y t))) ≤
ψX u - ψX (x 1) + ψY v - ψY (y 1) +
‖gx (x 1) (y 1)‖ ^ 2 / lamX + ‖gy (x 1) (y 1)‖ ^ 2 / lamY +
(∑ t ∈ Finset.Icc 2 T,
((2 * LXX ^ 2 / lamX + 2 * LXY ^ 2 / lamY - lamX / 4) *
‖x t - x (t - 1)‖ ^ 2)) +
(∑ t ∈ Finset.Icc 2 T,
((2 * LYY ^ 2 / lamY + 2 * LXY ^ 2 / lamX - lamY / 4) *
‖y t - y (t - 1)‖ ^ 2)) := by sorry
end ModernOnlineLearning.SaddlePoint
Source
Orabona, arXiv:1912.13213v10, §15.5, summed-regret display before Theorem 15.26, p. 262
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.