Lemma 9, p. 39 — for Z ∈ [0, M], inf over η ∈ ℝ of g(η; P) equals the inf over η ∈ [−M/(c_k−1), M]
ProvedUniformDRO.Concentration.lemma_9cressie-readdistributionally-robust-optimizationdualityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a probability measure on , , , , , and let be measurable. With ,
Restricting the dual variable to a compact interval is what makes a finite grid of values, and hence a union bound, sufficient in the proof of Theorem 2.
Formalization Note Since and give , the interval is nonempty (), and , so both infima are real infima of sets bounded below. Measurability of is added. No condition is imposed: Lemma 9 holds for any (and forces ).
Preamble
import Mathlib import Definitions.Def_UniformDRO_Concentration_RobustRisk open MeasureTheory
Formal statement
namespace UniformDRO.Concentration
/-- Lemma 9 (Duchi & Namkoong, arXiv:1810.08750v6, App. C.1, p. 39): if `Z ∈ [0, M]`, then for any
probability measure `P`,
`inf_{η ∈ ℝ} g_k(η; P) = inf { g_k(η; P) : η ∈ [-M/(c_k - 1), M] }`.
Both infima are of functions bounded below (`g_k(η; P) ≥ E_P[Z] ≥ 0`), and the interval is
nonempty because `c_k > 1`, so `-M/(c_k - 1) ≤ 0 ≤ M`. -/
theorem lemma_9 {X : Type*} [MeasurableSpace X] (P : Measure X) [IsProbabilityMeasure P]
(k ρ : ℝ) (hk : 1 < k) (hρ : 0 < ρ) (Z : X → ℝ) (hZm : Measurable Z) (M : ℝ)
(hZ : ∀ x, Z x ∈ Set.Icc 0 M) :
⨅ η : ℝ, dualObjective k ρ P Z η =
⨅ η : Set.Icc (-(M / (ck k ρ - 1))) M, dualObjective k ρ P Z η := by sorry
end UniformDRO.Concentration
Source
Duchi & Namkoong, arXiv:1810.08750v6, Lemma 9, App. C.1, p. 39; proof pp. 39–40
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.