Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3, pp. 21–22 β€” 𝔐ₙ(𝒫, f_k) β‰₯ M max{(1/(8k*p_k))(√(p_k(1βˆ’p_k)/(16n)) ∧ Β½(1βˆ’p_k) ∧ p_k), β…›Ξ²_k^{1/k}c_k(ρ)(1/(4n) ∧ p_k ∧ (1βˆ’(1βˆ’Ξ²_k)^{1βˆ’k*}p_k))^{1/k*}}

Proved
UniformDRO.LowerBound.theorem_3

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

cressie-readdistributionally-robust-optimizationestimationminimax-lower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let k∈(1,∞)k \in (1,\infty)k∈(1,∞), kβˆ—=k/(kβˆ’1)k_* = k/(k-1)kβˆ—β€‹=k/(kβˆ’1), let ρ>0\rho > 0ρ>0 be arbitrary but fixed, and define

ck(ρ)=(1+k(kβˆ’1)ρ)1/k,pk=(1+k(kβˆ’1)ρ)βˆ’1/(kβˆ’1),Ξ²k=k(kβˆ’1)ρ2(1+k(kβˆ’1)ρ).c_k(\rho) = (1 + k(k-1)\rho)^{1/k}, \qquad p_k = (1 + k(k-1)\rho)^{-1/(k-1)}, \qquad \beta_k = \frac{k(k-1)\rho}{2(1+k(k-1)\rho)} .ck​(ρ)=(1+k(kβˆ’1)ρ)1/k,pk​=(1+k(kβˆ’1)ρ)βˆ’1/(kβˆ’1),Ξ²k​=2(1+k(kβˆ’1)ρ)k(kβˆ’1)ρ​.

Fix M>0M > 0M>0, let P\mathcal PP be the set of all distributions on {0,M}\{0, M\}{0,M}, and let Mn(P,fk)\mathfrak M_n(\mathcal P, f_k)Mn​(P,fk​) be the minimax risk (16) of estimating the Cressie–Read robust risk Rk(Z)\mathcal R_k(Z)Rk​(Z), Z∼P0Z \sim P_0Z∼P0​, from nβ‰₯1n \ge 1nβ‰₯1 i.i.d. observations Z1,…,Zn∼P0Z_1, \dots, Z_n \sim P_0Z1​,…,Znβ€‹βˆΌP0​, over all estimators R^:{0,M}nβ†’R\widehat R : \{0, M\}^n \to \mathbb RR:{0,M}nβ†’R and all P0∈PP_0 \in \mathcal PP0β€‹βˆˆP. Then

Mn(P,fk)β‰₯Mmax⁑{18kβˆ—pk(pk(1βˆ’pk)16n∧12(1βˆ’pk)∧pk),Β Β 18Ξ²k1/kck(ρ)(14n∧pk∧(1βˆ’(1βˆ’Ξ²k)1βˆ’kβˆ—pk))1/kβˆ—}.\mathfrak M_n(\mathcal P, f_k) \ge M \max\Biggl\{ \frac{1}{8 k_* p_k}\Bigl( \sqrt{\frac{p_k(1-p_k)}{16 n}} \wedge \tfrac12(1-p_k) \wedge p_k \Bigr),\ \ \frac18 \beta_k^{1/k} c_k(\rho) \Bigl( \frac{1}{4n} \wedge p_k \wedge \bigl(1 - (1-\beta_k)^{1-k_*} p_k\bigr) \Bigr)^{1/k_*} \Biggr\}.Mn​(P,fk​)β‰₯Mmax{8kβˆ—β€‹pk​1​(16npk​(1βˆ’pk​)β€‹β€‹βˆ§21​(1βˆ’pk​)∧pk​),Β Β 81​βk1/k​ck​(ρ)(4n1β€‹βˆ§pkβ€‹βˆ§(1βˆ’(1βˆ’Ξ²k​)1βˆ’kβˆ—β€‹pk​))1/kβˆ—β€‹}.

The two branches scale as nβˆ’1/2n^{-1/2}nβˆ’1/2 and nβˆ’1/kβˆ—n^{-1/k_*}nβˆ’1/kβˆ—β€‹, so no estimator of the robust risk can converge faster than nβˆ’1/(kβˆ—βˆ¨2)n^{-1/(k_* \vee 2)}nβˆ’1/(kβˆ—β€‹βˆ¨2) uniformly over distributions on two points. This matches the rate of the concentration upper bound for the plug-in robust risk (Theorem 2 of the paper), showing that the slow nβˆ’1/kβˆ—n^{-1/k_*}nβˆ’1/kβˆ—β€‹ rate for small kkk is unavoidable.

Formalization Note. (1) The class P\mathcal PP, the estimators and the expectation EP0n\mathbb E_{P_0^n}EP0n​​ are encoded on the finite sample space {0,M}n\{0,M\}^n{0,M}n, and Mn\mathfrak M_nMn​ takes values in [0,∞][0,\infty][0,∞]; the robust risk is the likelihood-ratio form (3) of sup⁑{EQ[Z]:Dfk(Qβˆ₯P0)≀ρ}\sup\{\mathbb E_Q[Z] : D_{f_k}(Q\|P_0) \le \rho\}sup{EQ​[Z]:Dfk​​(Qβˆ₯P0​)≀ρ}. (2) Correction of the print: the page has 8n8n8n inside the square root of the first branch. The paper's argument (p. 46) bounds Dkl≀1/nD_{\mathrm{kl}} \le 1/nDkl​≀1/n and applies Pinsker in the form βˆ₯β‹…βˆ₯TV2≀n2Dkl\|\cdot\|_{\mathrm{TV}}^2 \le \tfrac n2 D_{\mathrm{kl}}βˆ₯β‹…βˆ₯TV2​≀2n​Dkl​, which yields βˆ₯β‹…βˆ₯TV≀1/2\|\cdot\|_{\mathrm{TV}} \le 1/\sqrt2βˆ₯β‹…βˆ₯TV​≀1/2​, not the 12\tfrac1221​ that the constant 18kβˆ—pk\tfrac{1}{8k_*p_k}8kβˆ—β€‹pk​1​ requires. With 16n16n16n the same argument gives Dkl≀1/(2n)D_{\mathrm{kl}} \le 1/(2n)Dkl​≀1/(2n), βˆ₯β‹…βˆ₯TV≀12\|\cdot\|_{\mathrm{TV}} \le \tfrac12βˆ₯β‹…βˆ₯TV​≀21​, and exactly the printed constant. The second branch is as printed. (3) The hypothesis nβ‰₯1n \ge 1nβ‰₯1 is implicit on the page (the bound contains 1/n1/n1/n). (4) The minimax risk agrees, for these laws, with the platform's general HighDimStat.Minimax.minimaxRisk.

Preamble
import Mathlib
import Definitions.Def_UniformDRO_LowerBound_Setting
Formal statement
namespace UniformDRO.LowerBound

theorem theorem_3 (k ρ M : ℝ) (hk : 1 < k) (hρ : 0 < ρ) (hM : 0 < M) (n : β„•) (hn : 0 < n) :
    ENNReal.ofReal (M * max
        (1 / (8 * UniformDRO.Concentration.kstar k * pk k ρ) *
          min (min (Real.sqrt (pk k ρ * (1 - pk k ρ) / (16 * n))) ((1 - pk k ρ) / 2)) (pk k ρ))
        (1 / 8 * βk k ρ ^ (1 / k) * UniformDRO.Concentration.ck k ρ *
          (min (min (1 / (4 * (n : ℝ))) (pk k ρ))
            (1 - (1 - Ξ²k k ρ) ^ (1 - UniformDRO.Concentration.kstar k) * pk k ρ)) ^ (1 / UniformDRO.Concentration.kstar k))) ≀
      minimaxRisk k ρ M n := by sorry

end UniformDRO.LowerBound
Source
Duchi & Namkoong, arXiv:1810.08750v6, Theorem 3, pp. 21–22 (with (16), p. 21); proof App. D.1, pp. 45–46
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