Lemma 12.2, fourth claim — subdifferential outside the set
ProvedModernOnlineLearning.Reductions.lemma_12_2_subdiffconvex-analysisdistance-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1subgradient
Let be nonempty, closed, and convex. If and , then a continuous linear functional is a full-space subgradient of at exactly when
This characterizes the distance subgradients used by the linear surrogate choices.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_Reductions_Setting
Formal statement
namespace ModernOnlineLearning.Reductions
/-- Orabona, Lemma 12.2, fourth claim, p. 193. -/
theorem lemma_12_2_subdiff {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (V : Set E) (hV : V.Nonempty)
(hclosed : IsClosed V) (hconv : Convex ℝ V)
(x y : E) (hx : x ∉ V) (hy : IsProjection V x y) :
∀ g : E →L[ℝ] ℝ,
IsSubgradient (distance V) x g ↔
‖g‖ = 1 ∧ g (x - y) = ‖x - y‖ ∧ ∀ u ∈ V, g (u - y) ≤ 0 := by sorry
end ModernOnlineLearning.Reductions
Source
Orabona, arXiv:1912.13213v10, Lemma 12.2, fourth claim, p. 193
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.