Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(31), p. 16 β€” Sanov's lower bound: βˆ’inf_{int π’ž} B(D, D_tr) ≀ liminf (1/n) log D^∞_tr[D_bs[n] ∈ π’ž]

Proved
BootRobust.Optimality.eq_31_sanov_lower

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

bootstraplarge-deviationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relative-entropysanov

Let Dtr∈DnD_{\rm tr}\in\mathcal D_nDtrβ€‹βˆˆDn​ have all coordinates positive, let CβŠ†RΞΉ\mathcal C\subseteq\mathbb R^\iotaCβŠ†RΞΉ be any set, and let D∈DnD\in\mathcal D_nD∈Dn​ lie in the interior of C\mathcal CC relative to Dn\mathcal D_nDn​. Then for every Ξ΅>0\varepsilon>0Ξ΅>0, for all sufficiently large nnn,

Dtrn[Dbs[n]∈C]Β β‰₯Β exp⁑ ⁣(βˆ’n (B(D,Dtr)+Ξ΅)),D_{\rm tr}^n\big[D_{{\rm bs}[n]}\in\mathcal C\big]\ \ge\ \exp\!\big(-n\,(B(D,D_{\rm tr})+\varepsilon)\big),Dtrn​[Dbs[n]β€‹βˆˆC]Β β‰₯Β exp(βˆ’n(B(D,Dtr​)+Ξ΅)),

where DtrnD_{\rm tr}^nDtrn​ is the law of nnn independent draws from DtrD_{\rm tr}Dtr​ and Dbs[n]D_{{\rm bs}[n]}Dbs[n]​ is their empirical distribution.

Holding for every D∈int CD\in{\rm int}\,\mathcal CD∈intC and every Ξ΅\varepsilonΞ΅, this is Sanov's lower bound (31) on a finite alphabet:

βˆ’inf⁑D∈int CB(D,Dtr)≀lim inf⁑nβ†’βˆž1nlog⁑Dtr∞[Dbs[n]∈C].-\inf_{D\in{\rm int}\,\mathcal C}B(D,D_{\rm tr})\le\liminf_{n\to\infty}\frac1n\log D^\infty_{\rm tr}\big[D_{{\rm bs}[n]}\in\mathcal C\big].βˆ’D∈intCinf​B(D,Dtr​)≀nβ†’βˆžliminf​n1​logDtrβˆžβ€‹[Dbs[n]β€‹βˆˆC].

It shows that the bootstrap inequality of Theorem 6 is exact in the exponential rate.

Formalization Note The pointwise form with an explicit Ξ΅\varepsilonΞ΅ is equivalent to (31) and avoids log⁑0\log 0log0. Since Dtr>0D_{\rm tr}>0Dtr​>0, B(D,Dtr)B(D,D_{\rm tr})B(D,Dtr​) is finite and is used as a real number. Only the first nnn coordinates of the infinite bootstrap process enter the event, so its law is the nnn-fold product. Full support of DtrD_{\rm tr}Dtr​ is the paper's convention that Ξ©n\Omega_nΞ©n​ is the support of the training data.

Preamble
import Mathlib
import Definitions.Def_BootRobust_Optimality_Setting
Formal statement
namespace BootRobust.Optimality

open MeasureTheory

/-- Sanov's lower bound, Eq. (31), p. 16, in pointwise form: for every set `C`, every `D` in the
interior of `C` relative to `π’Ÿβ‚™` and every `Ξ΅ > 0`, eventually in `n`,
`Dⁿ_tr(D_bs[n] ∈ C) β‰₯ exp(-n (B(D, D_tr) + Ξ΅))`. Over all such `D` this is
`-inf_{D ∈ int C} B(D, D_tr) ≀ liminf (1/n) log D^∞_tr[D_bs[n] ∈ C]`. The training distribution has
full support, so `B(D, D_tr)` is finite and `EReal.toReal` returns its value. -/
theorem eq_31_sanov_lower {ΞΉ : Type*} [Fintype ΞΉ] [DecidableEq ΞΉ]
    [MeasurableSpace ΞΉ] [MeasurableSingletonClass ΞΉ]
    (Dtr : ΞΉ β†’ ℝ) (hDtr : Dtr ∈ stdSimplex ℝ ΞΉ) (hDtrpos : βˆ€ i, 0 < Dtr i)
    (C : Set (ΞΉ β†’ ℝ)) (D : ΞΉ β†’ ℝ) (hDC : D ∈ relInt C) :
    βˆ€ Ξ΅ : ℝ, 0 < Ξ΅ β†’ βˆ€αΆ  n : β„• in Filter.atTop,
      ENNReal.ofReal (Real.exp (-((n : ℝ) * ((BootRobust.Perf.bootDist D Dtr).toReal + Ξ΅)))) ≀
        bootLaw Dtr n {Ο‰ | empDist Ο‰ ∈ C} := by sorry

end BootRobust.Optimality
Source
Bertsimas and Van Parys, Bootstrap robust prescriptive analytics, arXiv:1711.09974v2, (31), p. 16 (citing Dembo and Zeitouni 2009, Theorem 6.2.10)
Human review
  • Endorsed by Shuze Chen Β· Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Oct 8, 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