Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(37), p. 45 — Le Cam: |R_k(P₀) − R_k(P₁)| ≥ 2δ > 0 implies 𝔐ₙ(𝒫, f_k) ≥ (δ/2)(1 − ‖P₀ⁿ − P₁ⁿ‖_TV)

Proved
UniformDRO.LowerBound.le_cam_37

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributionally-robust-optimizationle-camminimax-lower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let k>1k > 1k>1, ρ>0\rho > 0ρ>0, M>0M > 0M>0 and n≥0n \ge 0n≥0. Let P0,P1P_0, P_1P0​,P1​ be laws on {0,M}\{0, M\}{0,M} with masses p0,p1∈[0,1]p_0, p_1 \in [0,1]p0​,p1​∈[0,1] at MMM, and let Rk(Pv)\mathcal R_k(P_v)Rk​(Pv​) denote the Cressie–Read robust risk of Z∼PvZ \sim P_vZ∼Pv​. If

∣Rk(P0)−Rk(P1)∣≥2δ>0,|\mathcal R_k(P_0) - \mathcal R_k(P_1)| \ge 2\delta > 0,∣Rk​(P0​)−Rk​(P1​)∣≥2δ>0,

then the minimax risk (16) satisfies

Mn(P,fk)≥δ2(1−∥P0n−P1n∥TV).(37)\mathfrak M_n(\mathcal P, f_k) \ge \frac{\delta}{2}\bigl(1 - \|P_0^n - P_1^n\|_{\mathrm{TV}}\bigr). \qquad (37)Mn​(P,fk​)≥2δ​(1−∥P0n​−P1n​∥TV​).(37)

This is Le Cam's reduction from estimation to testing: an estimator accurate to within δ\deltaδ under both laws would distinguish them from nnn 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. Mn\mathfrak M_nMn​ and the total variation are those of the mission's definition file (finite sums over {0,M}n\{0,M\}^n{0,M}n; Mn\mathfrak M_nMn​ in [0,∞][0,\infty][0,∞]). The left side is embedded in [0,∞][0,\infty][0,∞] with negative values sent to 000, which loses nothing since ∥⋅∥TV≤1\|\cdot\|_{\mathrm{TV}} \le 1∥⋅∥TV​≤1.

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
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me