Theorem 7.47, pp. 129–130 — optimistic FTRL regret for linear losses and a fixed regularizer
ProvedModernOnlineLearning.SaddlePoint.theorem_7_47_linearLet be nonempty, closed and convex in a real normed space, let be -strongly convex on with , and let be an optimistic FTRL run for linear losses and the previous-vector hints , with . Let , and let be a minimizer over of (the next FTRL point with a zero hint); for , is the run's own iterate. For every , the specialization of Theorem 7.47 gives both bounds
and, separately,
This is the regret input for the two players in Algorithm 15.6.
Formalization Note This milestone states precisely the linear-loss, fixed-regularizer instance used on p. 262. The general theorem also treats time-varying nonlinear losses and regularizers. Given an already specified run, existence and uniqueness of its minimizers are not part of this instance. The theorem does not define ; its proof (p. 130) sets the hint of round equal to that of round . With that choice the first inequality is false: for , , , , , , , the left side is and the right side is . The proof's telescoping argument is correct when the hint at round is zero, so is the minimizer of . The second inequality does not involve .
import Mathlib import Definitions.Def_ModernOnlineLearning_SaddlePoint_Setting set_option autoImplicit false
namespace ModernOnlineLearning.SaddlePoint
/-- Theorem 7.47, p. 129–130, specialized to linear losses and a fixed regularizer.
For `t < T` the point `x_(t+1)` of the bound is the run's own iterate `z (t+1)`.
The look-ahead point `x_(T+1)` is `w`, a minimizer over `V` of `ψ + Σ_(i ≤ T) g_i`,
i.e. the hint at round `T + 1` is zero. The proof on p. 130 sets the hint at `T + 1` to the
hint at `T` instead; with that choice the first inequality fails (`V = ℝ`, `ψ z = z²/2`,
`λ = 1`, `T = 2`, `g₁ = 1`, `g₂ = 0`, `u = −1`: left side `1`, right side `1/2`), while with
the zero hint the proof goes through. -/
theorem theorem_7_47_linear {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(V : Set E) (ψ : E → ℝ) (g : ℕ → E →L[ℝ] ℝ) (z : ℕ → E)
(lam : ℝ) (T : ℕ) (u : E) (hT : 1 ≤ T)
(hVne : V.Nonempty) (hVclosed : IsClosed V) (hu : u ∈ V) (hlam : 0 < lam) (hstrong : StrongConvexOn V lam ψ)
(hrun : IsOptFTRLRun V ψ g z T) (w : E)
(hw : IsMinOn V (fun v => ψ v + ∑ i ∈ Finset.Icc 1 T, g i v) w) :
(∑ t ∈ Finset.Icc 1 T, g t (z t - u) ≤
ψ u - ψ (z 1) +
∑ t ∈ Finset.Icc 1 T,
((g t - g (t - 1)) (z t - (if t < T then z (t + 1) else w)) -
lam / 2 * ‖z t - (if t < T then z (t + 1) else w)‖ ^ 2)) ∧
(∑ t ∈ Finset.Icc 1 T, g t (z t - u) ≤
ψ u - ψ (z 1) +
∑ t ∈ Finset.Icc 1 T, ‖g t - g (t - 1)‖ ^ 2 / (2 * lam)) := by sorry
end ModernOnlineLearning.SaddlePoint
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.