Proposition 2.11 — projection decreases distance to feasible points
ProvedModernOnlineLearning.OGD.proposition_2_11convex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1projection
Let be a nonempty closed convex subset of a real inner-product space. If is a nearest point of to , then every satisfies
This projection inequality is the geometric step behind the one-round regret estimate. The nearest-point predicate records both and its distance minimality.
Preamble
import Mathlib import Definitions.Def_OnlineConvexOpt_FirstOrder_Protocol
Formal statement
namespace ModernOnlineLearning.OGD
/-- Orabona, Proposition 2.11, p. 12: a metric projection onto a nonempty closed
convex set cannot increase the distance to any point of the set. -/
theorem proposition_2_11 {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
[CompleteSpace E] (V : Set E) (hV : V.Nonempty) (hc : IsClosed V)
(hv : Convex ℝ V) (x p y : E) (hp : OnlineConvexOpt.FirstOrder.IsMetricProjection V x p)
(hy : y ∈ V) : ‖p - y‖ ≤ ‖x - y‖ := by sorry
end ModernOnlineLearning.OGD
Source
Orabona, arXiv:1912.13213v10, Proposition 2.11, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.