(37), p. 45 — Le Cam: |R_k(P₀) − R_k(P₁)| ≥ 2δ > 0 implies 𝔐ₙ(𝒫, f_k) ≥ (δ/2)(1 − ‖P₀ⁿ − P₁ⁿ‖_TV)
ProvedUniformDRO.LowerBound.le_cam_37distributionally-robust-optimizationle-camminimax-lower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and . Let be laws on with masses at , and let denote the Cressie–Read robust risk of . If
then the minimax risk (16) satisfies
This is Le Cam's reduction from estimation to testing: an estimator accurate to within under both laws would distinguish them from samples, which the total variation between the product laws forbids. Both branches of Theorem 3 are obtained by applying (37) to two well-chosen laws.
Formalization Note. and the total variation are those of the mission's definition file (finite sums over ; in ). The left side is embedded in with negative values sent to , which loses nothing since .
Preamble
import Mathlib import Definitions.Def_UniformDRO_LowerBound_Setting
Formal statement
namespace UniformDRO.LowerBound
theorem le_cam_37 (k ρ : ℝ) (hk : 1 < k) (hρ : 0 < ρ) (M : ℝ) (hM : 0 < M) (n : ℕ)
(p₀ p₁ δ : ℝ) (hp₀ : p₀ ∈ Set.Icc (0 : ℝ) 1) (hp₁ : p₁ ∈ Set.Icc (0 : ℝ) 1) (hδ : 0 < δ)
(hsep : 2 * δ ≤ |UniformDRO.Concentration.robustRisk k ρ (twoPointLaw 0 M p₀) id -
UniformDRO.Concentration.robustRisk k ρ (twoPointLaw 0 M p₁) id|) :
ENNReal.ofReal (δ / 2 * (1 - tvDist n p₀ p₁)) ≤ minimaxRisk k ρ M n := by sorry
end UniformDRO.LowerBound
Source
Duchi & Namkoong, arXiv:1810.08750v6, proof of Theorem 3 (App. D.1), p. 45, (37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.