Lemma 13 — distance to a convex cone
ProvedApproachRegret.ToOLO.lemma13_dist_coneconic-dualityconvex-analysisp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonempty convex cone, and let . With the polar defined by nonpositive inner products and the Euclidean unit ball,
The maximum is attained. This identity converts a geometric distance into a linear optimization over a polar cone.
Formalization Note Nonemptiness is explicit because Definition 11 permits the empty cone, while the source's distance formula does not cover that case. Closedness is not assumed.
Preamble
import Mathlib import Definitions.Def_ApproachRegret_ToOLO_Cones open scoped RealInnerProductSpace
Formal statement
namespace ApproachRegret.ToOLO
/-- Lemma 13, p. 35, including attainment of the maximum. -/
theorem lemma13_dist_cone {d : ℕ} (C : Set (E d)) (x : E d)
(hC : Convex ℝ C) (hcone : ∀ z ∈ C, ∀ α : ℝ, 0 ≤ α → α • z ∈ C)
(hne : C.Nonempty) :
IsGreatest ((fun θ : E d => ⟪θ, x⟫) ''
(polar C ∩ Metric.closedBall 0 1)) (Metric.infDist x C) := 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, Lemma 13, p. 35 (PDF p. 9), equation (3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.