Proof of Theorem 2, p. 31 — the outer minimisation over λ for the hinge-loss SVM
ProvedRWPI.Classif.hinge_outer_mindistributionally-robust-optimizationdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1support-vector-machine
Let satisfy . Let with , let and . Then
The paper observes that it suffices to restrict the outer minimization to (elsewhere the inner suprema are infinite) and evaluates the restricted infimum; the statement combines the two. With Proposition 1 the left-hand side is the worst-case expected hinge loss over , so this is the per- form of the SVM half of Theorem 2.
Formalization Note Norms are in Theorem 2's convention (the page writes the threshold as ). Values are in .
Preamble
import Mathlib import Definitions.Def_RWPI_Classif_losses open scoped ENNReal
Formal statement
namespace RWPI.Classif
/-- App. A.1, proof of Theorem 2, p. 31: for labels `Yᵢ ∈ {−1, +1}` and `δ ≥ 0`, the outer
minimisation of the dual over `λ ≥ 0` (where it suffices to take `λ ≥ ‖β‖_p`) gives
`inf_{λ ≥ 0} { δλ + (1/n) Σᵢ sup_Δ { (1 − Yᵢβᵀ(Xᵢ + Δ))⁺ − λ‖Δ‖_q } }
= (1/n) Σᵢ (1 − Yᵢβᵀ Xᵢ)⁺ + δ‖β‖_p`. -/
theorem hinge_outer_min {d n : ℕ} (hn : 0 < n) (X : Fin n → Fin d → ℝ) (Y : Fin n → ℝ)
(hY : ∀ i, Y i = 1 ∨ Y i = -1) (p q : ℝ≥0∞) (hpq : p.HolderConjugate q)
(β : Fin d → ℝ) (δ : ℝ) (hδ : 0 ≤ δ) :
(⨅ (lam : ℝ) (_ : 0 ≤ lam), (ENNReal.ofReal (δ * lam) + (n : ℝ≥0∞)⁻¹ *
∑ i, ⨆ Δ : Fin d → ℝ, (ENNReal.ofReal (hingeLoss β (X i + Δ, Y i)) -
ENNReal.ofReal lam * ENNReal.ofReal ‖WithLp.toLp q Δ‖))) =
ENNReal.ofReal ((1 / (n : ℝ)) * ∑ i, hingeLoss β (X i, Y i) + δ * ‖WithLp.toLp p β‖) := by sorry
end RWPI.Classif
Source
Blanchet, Kang & Murthy, Robust Wasserstein Profile Inference and Applications to Machine Learning, arXiv:1610.05627v4, App. A.1, proof of Theorem 2, p. 31 (display after 'it is sufficient to restrict to λ ≥ ‖β‖')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.