Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 13 β€” weights in the f-divergence ball satisfy β€–np βˆ’ πŸ™β€–β‚‚ ≀ √(ρ C_f)

Proved
GenEmpLik.Consistency.lemma_13

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

empirical-likelihoodf-divergencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let fff satisfy Assumption A and let ρβ‰₯0\rho\ge0ρβ‰₯0. Then there are constants Cfβ‰₯cf>0C_f\ge c_f>0Cf​β‰₯cf​>0, depending only on fff (and ρ\rhoρ), such that

ρcf ≀ sup⁑n∈NΒ sup⁑p∈Rn{βˆ₯npβˆ’1βˆ₯2β€…β€Š:β€…β€Šp⊀1=1,Β pβ‰₯0,Β βˆ‘i=1nf(npi)≀ρ} ≀ ρCf.\sqrt{\rho c_f}\ \le\ \sup_{n\in\mathbb N}\ \sup_{p\in\mathbb R^n}\Big\{\|np-\mathbb 1\|_2 \;:\; p^\top\mathbb 1=1,\ p\ge0,\ \sum_{i=1}^n f(np_i)\le\rho\Big\}\ \le\ \sqrt{\rho C_f}.ρcf​​ ≀ n∈Nsup​ p∈Rnsup​{βˆ₯npβˆ’1βˆ₯2​:p⊀1=1,Β pβ‰₯0,Β i=1βˆ‘n​f(npi​)≀ρ} ≀ ρCf​​.

Precisely: every nβ‰₯1n\ge1nβ‰₯1 and every feasible ppp satisfy βˆ₯npβˆ’1βˆ₯2≀ρCf\|np-\mathbb 1\|_2\le\sqrt{\rho C_f}βˆ₯npβˆ’1βˆ₯2​≀ρCf​​, and some nβ‰₯1n\ge1nβ‰₯1 and feasible ppp satisfy βˆ₯npβˆ’1βˆ₯2β‰₯ρcf\|np-\mathbb 1\|_2\ge\sqrt{\rho c_f}βˆ₯npβˆ’1βˆ₯2​β‰₯ρcf​​.

The lemma says that the likelihood ratios npinp_inpi​ of every distribution in the ball {Pβ‰ͺP^n:Df(Pβˆ₯P^n)≀ρ/n}\{P\ll\widehat P_n : D_f(P\|\widehat P_n)\le\rho/n\}{Pβ‰ͺPn​:Df​(Pβˆ₯Pn​)≀ρ/n} stay within a fixed β„“2\ell_2β„“2​-distance of the all-ones vector, uniformly in nnn; it is the quantitative input to the uniform convergence in Theorem 7.

Formalization Note The feasible set is the published probUncertaintySet f (1/n,…,1/n) (ρ/n), equal to the set displayed above. The page says "depending only on fff"; the constants are allowed to depend on ρ\rhoρ as well, as the proof does (it defines m,Mm,Mm,M through f(m)=f(M)=ρf(m)=f(M)=\rhof(m)=f(M)=ρ). The upper bound as proved is 2Cfρ\sqrt{2C_f\rho}2Cf​ρ​; the factor 2 is absorbed into the existential constant. The lower bound is stated with an attained witness, which implies the bound on the supremum. Mission 2 of this series states the same lemma in its own namespace.

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

/-- Lemma 13 (arXiv:1610.03425v3, p. 34): under Assumption A, for every `ρ β‰₯ 0` there are
constants `C_f β‰₯ c_f > 0` (depending only on `f` and `ρ`) such that
`√(ρ c_f) ≀ sup_n sup_p β€–n p βˆ’ πŸ™β€–β‚‚ ≀ √(ρ C_f)`, the supremum running over `n β‰₯ 1` and
`p ∈ ℝⁿ` with `pα΅€πŸ™ = 1`, `p β‰₯ 0`, `βˆ‘α΅’ f(n pα΅’) ≀ ρ`. The feasible set is written as the
Ο†-divergence ball `probUncertaintySet f (1/n, …, 1/n) (ρ/n)`; the upper bound holds for every
feasible `p`, and the lower bound is witnessed by some `n` and feasible `p`. -/
theorem lemma_13 (f : ℝ β†’ EReal) (hf : GenEmpLik.Coverage.AssumptionA f) (ρ : ℝ) (hρ : 0 ≀ ρ) :
    βˆƒ cf Cf : ℝ, 0 < cf ∧ cf ≀ Cf ∧
      (βˆ€ n : β„•, 0 < n β†’ βˆ€ p ∈ PhiDivRobust.Counterpart.probUncertaintySet f
          (fun _ : Fin n => (1 : ℝ) / n) (ρ / n),
        Real.sqrt (βˆ‘ i, ((n : ℝ) * p i - 1) ^ 2) ≀ Real.sqrt (ρ * Cf)) ∧
      (βˆƒ n : β„•, 0 < n ∧ βˆƒ p ∈ PhiDivRobust.Counterpart.probUncertaintySet f
          (fun _ : Fin n => (1 : ℝ) / n) (ρ / n),
        Real.sqrt (ρ * cf) ≀ Real.sqrt (βˆ‘ i, ((n : ℝ) * p i - 1) ^ 2)) := by sorry

end GenEmpLik.Consistency
Source
Duchi, Glynn & Namkoong, Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach, arXiv:1610.03425v3, p. 34, Lemma 13 (proof p. 35)
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