Quadratic inequality, supp. p. 10 — cost bound after introducing x
ProvedRegLearnGames.FirstOrder.quadratic_inequalityalgorithmic-game-theoryfirst-order-regretp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-games
In the finite cost game of Theorem 23, suppose costs lie in , , the game is -smooth, the play through is mixed, and the first-order bound (21) holds with . Set
Then
This is the paper's inequality from which its quadratic bound on follows.
Formalization Note The assumptions and make the theorem's divisions meaningful; is needed by the preceding Cauchy–Schwarz step. Smoothness and nonnegative costs imply that the expression under the square root is nonnegative. The paper writes both log and ln; both mean the natural logarithm.
Preamble
import Mathlib import Definitions.Def_RegLearnGames_FirstOrder_Setting
Formal statement
namespace RegLearnGames.FirstOrder
open Finset
/-- The quadratic inequality on the quantity `x` defined in Appendix H. -/
theorem quadratic_inequality {n d : ℕ} [NeZero d]
(c : Fin n → (Fin n → Fin d) → ℝ)
(hc : ∀ i s, c i s ∈ Set.Icc (0 : ℝ) 1)
(lam mu : ℝ) (hmu₀ : 0 < mu) (hmu₁ : mu < 1)
(hsmooth : IsSmoothCost c lam mu)
(A₁ A₂ : ℝ) (hA₁ : 0 ≤ A₁)
(T : ℕ) (hT : 1 ≤ T)
(w : ℕ → Fin n → Fin d → ℝ)
(hw : ∀ t ∈ Finset.Icc 1 T, AGT.IsMixedProfile (w t))
(hreg : HasFirstOrderRegret c w T A₁ A₂) :
let x : ℝ := Real.sqrt (lam * (T : ℝ) * optCost c +
mu * (∑ t ∈ Finset.Icc 1 T, socialCost c (w t)))
(1 / mu) * (x ^ 2 - lam * (T : ℝ) * optCost c) ≤
x ^ 2 + A₁ * Real.sqrt ((n : ℝ) * Real.log (d : ℝ)) * x +
A₂ * (n : ℝ) * Real.log (d : ℝ) := by sorry
end RegLearnGames.FirstOrder
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, supp. p. 10 (PDF p. 19), quadratic display following equation (22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.