Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(47) — Hölder bound on the deviation of a reweighted mean from E_{P₀}[ℓ]

Proved
GenEmpLik.Consistency.eq_47

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

f-divergenceholder-inequalityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let ϵ>0\epsilon>0ϵ>0 and set q=min⁡{2,1+ϵ}q=\min\{2,1+\epsilon\}q=min{2,1+ϵ}, r=max⁡{2,1+1/ϵ}r=\max\{2,1+1/\epsilon\}r=max{2,1+1/ϵ} (conjugate exponents: 1/r+1/q=11/r+1/q=11/r+1/q=1). Let n≥1n\ge1n≥1, let z=(z1,…,zn)z=(z_1,\dots,z_n)z=(z1​,…,zn​) be real numbers (the losses ℓ(x;ξi)\ell(x;\xi_i)ℓ(x;ξi​)), m∈Rm\in\mathbb Rm∈R (standing for EP0[ℓ(x;ξ)]E_{P_0}[\ell(x;\xi)]EP0​​[ℓ(x;ξ)]), and let www be a weight vector in the ball {w≥0:∑iwi=1, ∑if(nwi)≤ρ}\{w\ge0:\sum_i w_i=1,\ \sum_i f(nw_i)\le\rho\}{w≥0:∑i​wi​=1, ∑i​f(nwi​)≤ρ}, i.e. a distribution P≪P^nP\ll\widehat P_nP≪Pn​ with likelihood ratio L(ξi)=nwiL(\xi_i)=nw_iL(ξi​)=nwi​. Writing EP^n[g]=1n∑igiE_{\widehat P_n}[g]=\frac1n\sum_i g_iEPn​​[g]=n1​∑i​gi​ and zˉ=1n∑izi\bar z=\frac1n\sum_i z_izˉ=n1​∑i​zi​,

∣∑i=1nwizi−m∣ ≤ 1n∑i=1n∣nwi−1∣ ∣zi∣+∣zˉ−m∣ ≤ (1n∑i=1n∣nwi−1∣r)1/r(1n∑i=1n∣zi∣q)1/q+∣zˉ−m∣.\Big|\sum_{i=1}^n w_i z_i-m\Big| \ \le\ \frac1n\sum_{i=1}^n|nw_i-1|\,|z_i|+|\bar z-m| \ \le\ \Big(\frac1n\sum_{i=1}^n|nw_i-1|^{r}\Big)^{1/r}\Big(\frac1n\sum_{i=1}^n|z_i|^{q}\Big)^{1/q}+|\bar z-m| .​i=1∑n​wi​zi​−m​ ≤ n1​i=1∑n​∣nwi​−1∣∣zi​∣+∣zˉ−m∣ ≤ (n1​i=1∑n​∣nwi​−1∣r)1/r(n1​i=1∑n​∣zi​∣q)1/q+∣zˉ−m∣.

In the paper's notation this is ∣EP[ℓ]−EP0[ℓ]∣≤EP^n[∣L−1∣∣ℓ∣]+∣EP^n[ℓ]−EP0[ℓ]∣≤EP^n[∣L−1∣r]1/rEP^n[∣ℓ∣q]1/q+∣EP^n[ℓ]−EP0[ℓ]∣|E_P[\ell]-E_{P_0}[\ell]|\le E_{\widehat P_n}[|L-1||\ell|]+|E_{\widehat P_n}[\ell]-E_{P_0}[\ell]|\le E_{\widehat P_n}[|L-1|^r]^{1/r}E_{\widehat P_n}[|\ell|^q]^{1/q}+|E_{\widehat P_n}[\ell]-E_{P_0}[\ell]|∣EP​[ℓ]−EP0​​[ℓ]∣≤EPn​​[∣L−1∣∣ℓ∣]+∣EPn​​[ℓ]−EP0​​[ℓ]∣≤EPn​​[∣L−1∣r]1/rEPn​​[∣ℓ∣q]1/q+∣EPn​​[ℓ]−EP0​​[ℓ]∣; taking suprema over the ball gives the printed form of (47). It splits the robust deviation into a reweighting term, controlled by Lemma 13 and Assumption E, and the ordinary empirical deviation, controlled by the Glivenko–Cantelli property.

Formalization Note The paper's exponent ppp is called rrr here to avoid a clash with the weights. The middle term uses ∣ℓ∣|\ell|∣ℓ∣: the page prints ∣L(ξ)−1∣ ℓ(x;ξ)|L(\xi)-1|\,\ell(x;\xi)∣L(ξ)−1∣ℓ(x;ξ), a typo (the bound fails for signed ℓ\ellℓ otherwise). The statement is per distribution; the printed version takes the supremum over the ball on both sides.

Preamble
import Mathlib
import Definitions.Def_PhiDivRobust_Counterpart_uncertaintySet
import Definitions.Def_VarianceRegularization_Expansion_empMean
Formal statement
namespace GenEmpLik.Consistency

/-- Inequality (47) (arXiv:1610.03425v3, App. E.1, p. 46), for one distribution `P` of the
ball `𝒫_{n,ρ}`. Let `ε > 0`, `q = min{2, 1 + ε}`, `r = max{2, 1 + 1/ε}` (the paper's `p`), let
`z = (ℓ(x; ξ₁), …, ℓ(x; ξₙ))` and `m` a real number (standing for `E_{P₀}[ℓ(x; ξ)]`). For every
weight vector `w` in the ball, with likelihood ratio `L(ξᵢ) = n wᵢ`,
`|E_P[ℓ] − m| ≤ E_{P̂n}[|L − 1| |ℓ|] + |E_{P̂n}[ℓ] − m|
  ≤ E_{P̂n}[|L − 1|^r]^{1/r} E_{P̂n}[|ℓ|^q]^{1/q} + |E_{P̂n}[ℓ] − m|`. -/
theorem eq_47 (f : ℝ → EReal) (ρ ε : ℝ) (hε : 0 < ε) (n : ℕ) (hn : 0 < n)
    (z : Fin n → ℝ) (m : ℝ)
    (w : Fin n → ℝ) (hw : w ∈ PhiDivRobust.Counterpart.probUncertaintySet f
      (fun _ : Fin n => (1 : ℝ) / n) (ρ / n)) :
    |∑ i, w i * z i - m| ≤
        (1 / (n : ℝ)) * ∑ i, |(n : ℝ) * w i - 1| * |z i|
          + |VarianceRegularization.Expansion.empMean z - m| ∧
      (1 / (n : ℝ)) * ∑ i, |(n : ℝ) * w i - 1| * |z i|
          + |VarianceRegularization.Expansion.empMean z - m| ≤
        ((1 / (n : ℝ)) * ∑ i, |(n : ℝ) * w i - 1| ^ max 2 (1 + 1 / ε)) ^ (1 / max 2 (1 + 1 / ε))
          * ((1 / (n : ℝ)) * ∑ i, |z i| ^ min 2 (1 + ε)) ^ (1 / min 2 (1 + ε))
          + |VarianceRegularization.Expansion.empMean z - m| := by sorry

end GenEmpLik.Consistency
Source
Duchi, Glynn & Namkoong, Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach, arXiv:1610.03425v3, p. 46, App. E.1, proof of Theorem 7, (47)
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