§7.2.1 — closest-point bound:
ProvedSOSInference.Means.closest_point_boundconvex-analysisoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For :
- , and the infimum is a minimum;
- the minimum is attained at the optimizer ;
- consequently, for every finite nonempty family of points of ,
It identifies the centre around which the nearest sample points determine the constraints of the dual problem (22).
Preamble
import Mathlib import Definitions.Def_SOSInference_Means_sos
Formal statement
namespace SOSInference.Means
open scoped RealInnerProductSpace
/-- **Closest-point bound**, §7.2.1, p. 38 (Blanchet, Kang, Sample Out-of-Sample Inference Based on
Wasserstein Distance, arXiv:1605.01340v4, p. 38, Step 1).
For `x, λ ∈ ℝ^l`:
1. `inf_{a ∈ ℝ^l} {−λᵀa + ‖x − a‖₂²} = −λᵀx − ‖λ‖₂²/4`, and the infimum is a minimum;
2. it is attained at the optimizer `a*(x, λ) = x + λ/2`;
3. hence for every finite nonempty family `(z_j)`,
`inf_j {−λᵀz_j + ‖x − z_j‖₂²} ≥ −λᵀx − ‖λ‖₂²/4`. -/
theorem closest_point_bound {l : ℕ} (x lam : E l) :
IsLeast (Set.range fun a : E l => -⟪lam, a⟫ + ‖x - a‖ ^ 2) (-⟪lam, x⟫ - ‖lam‖ ^ 2 / 4) ∧
-⟪lam, x + (1 / 2 : ℝ) • lam⟫ + ‖x - (x + (1 / 2 : ℝ) • lam)‖ ^ 2 =
-⟪lam, x⟫ - ‖lam‖ ^ 2 / 4 ∧
∀ {ι : Type} [Fintype ι] [Nonempty ι] (z : ι → E l),
-⟪lam, x⟫ - ‖lam‖ ^ 2 / 4 ≤ ⨅ j, (-⟪lam, z j⟫ + ‖x - z j‖ ^ 2) := by sorry
end SOSInference.Means
Source
Blanchet, Kang, Sample Out-of-Sample Inference Based on Wasserstein Distance, arXiv:1605.01340v4, p. 38, §7.2.1 (Step 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.