Display (8) — distance to Algorithm 1’s target
ProvedApproachRegret.ToOLO.display8_distanceblackwell-approachabilityconic-dualityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be nonempty, compact, and convex, with . Let . For every ,
The maximum is attained. Substituting the average payoff of Algorithm 1 yields the paper's displayed identity for its approachability rate.
Formalization Note The display's means the cone of the lifted set ; its ball is in , although the display labels it with dimension .
Preamble
import Mathlib import Definitions.Def_ApproachRegret_ToOLO_AlgorithmOne open scoped RealInnerProductSpace
Formal statement
namespace ApproachRegret.ToOLO
/-- Display (8), p. 37, for an arbitrary point in the lifted Euclidean space. -/
theorem display8_distance {d : ℕ} (K : Set (E d)) (z : E (d + 1))
(hK : IsCompact K) (hconv : Convex ℝ K) (hne : K.Nonempty)
(hk : 0 < kappa K) :
IsGreatest ((fun w : E (d + 1) => ⟪z, w⟫) ''
(cone (lift (kappa K) '' K) ∩ Metric.closedBall 0 1))
(Metric.infDist z (target K)) := by sorry
end ApproachRegret.ToOLO
Source
Abernethy, Bartlett, Hazan, Blackwell Approachability and No-Regret Learning are Equivalent, COLT 2011, JMLR W&CP 19, https://proceedings.mlr.press/v19/abernethy11b.html, proof of Theorem 16, display (8), p. 37 (PDF p. 11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.