Proposition 1 — strong duality for the worst-case expected loss over an optimal-transport ball
DisprovedRWPI.Classif.proposition_1Let and let be a lower semicontinuous cost function with for every . Let be an upper semicontinuous nonnegative loss. Let with , let be their empirical distribution, and let . For put
Then
and the minimum on the right is attained: there is at which the right-hand expression equals the left-hand side, and the left-hand side is at most the right-hand expression for every . Both sides take values in .
This strong duality turns the supremum over infinitely many distributions into a one-dimensional minimization, and is the first step in recovering regularized estimators as distributionally robust ones. The paper quotes it from Blanchet & Murthy (Math. Oper. Res. 2019, Theorem 1).
Formalization Note The loss is a fixed function (the parameter of the paper plays no role in the identity; the paper's consequence (12) follows by taking the infimum over on both sides). Two restrictions relative to the page are recorded: the loss is nonnegative, so expectations are lower Lebesgue integrals in , and the radius is strictly positive, as in Blanchet & Murthy's theorem (at the minimum need not be attained). is computed in with the convention .
import Mathlib import Definitions.Def_WassersteinDRO_Regularization_empiricalDistribution import Definitions.Def_RWPI_SqrtLasso_worstCase import Definitions.Def_RWPI_Classif_phi open MeasureTheory open scoped ENNReal
namespace RWPI.Classif
/-- Proposition 1, p. 10 (from Blanchet & Murthy, Math. Oper. Res. 2019, Theorem 1): for a
lower semicontinuous cost `c : ℝ^{d+1} × ℝ^{d+1} → [0, ∞]` vanishing on the diagonal, an upper
semicontinuous nonnegative loss `l` and a radius `δ > 0`, the worst-case expected loss over
`{P : D_c(P, P_n) ≤ δ}` equals `min_{γ ≥ 0} { γδ + (1/n) Σᵢ φ_γ(Xᵢ, Yᵢ) }`, the minimum being
attained. -/
theorem proposition_1 {d n : ℕ} (hn : 0 < n) (X : Fin n → Fin d → ℝ) (Y : Fin n → ℝ)
(c : (Fin d → ℝ) × ℝ → (Fin d → ℝ) × ℝ → ℝ≥0∞)
(hc : LowerSemicontinuous (Function.uncurry c)) (hc0 : ∀ z, c z z = 0)
(l : (Fin d → ℝ) × ℝ → ℝ) (hl : UpperSemicontinuous l) (hl0 : ∀ z, 0 ≤ l z)
(δ : ℝ) (hδ : 0 < δ) :
∃ γ : ℝ, 0 ≤ γ ∧
RWPI.SqrtLasso.worstCase c δ
(WassersteinDRO.Regularization.empiricalDistribution (fun i => (X i, Y i))) l =
ENNReal.ofReal (γ * δ) + (n : ℝ≥0∞)⁻¹ * ∑ i, phi c l γ (X i, Y i) ∧
∀ γ' : ℝ, 0 ≤ γ' →
RWPI.SqrtLasso.worstCase c δ
(WassersteinDRO.Regularization.empiricalDistribution (fun i => (X i, Y i))) l ≤
ENNReal.ofReal (γ' * δ) + (n : ℝ≥0∞)⁻¹ * ∑ i, phi c l γ' (X i, Y i) := by sorry
end RWPI.Classif
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.