Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1, p. 16 — a distance R > B(·, D_tr) near some D with B(D, D_tr) = r admits a nominal formulation with bootstrap disappointment rate > −r

Proved
BootRobust.Optimality.proposition_1

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

bootstrapdistributionally-robust-optimizationlarge-deviationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1relative-entropy

Let RRR be a distribution distance function on Dn\mathcal D_nDn​ (Definition 4). Let D,Dtr∈DnD,D_{\rm tr}\in\mathcal D_nD,Dtr​∈Dn​, with DtrD_{\rm tr}Dtr​ of full support, and B(D,Dtr)=rB(D,D_{\rm tr})=rB(D,Dtr​)=r. Suppose that R(D′,Dtr)>rR(D',D_{\rm tr})>rR(D′,Dtr​)>r for all D′D'D′ in some neighbourhood N⊆Dn\mathcal N\subseteq\mathcal D_nN⊆Dn​ of DDD, open in Dn\mathcal D_nDn​. Then there is a nominal formulation — a nonnegative loss G:ι→R+G:\iota\to\mathbb R_+G:ι→R+​ with cost estimator D↦ED[G]=∑iDiGiD\mapsto\mathbb E_D[G]=\sum_iD_iG_iD↦ED​[G]=∑i​Di​Gi​ — whose disappointment set under the robust counterpart (24) with distance RRR and radius rrr,

R={D∈Dn: ED[G]>sup⁡D′∈Dn, R(D′,Dtr)≤rED′[G]},\mathcal R=\Big\{D\in\mathcal D_n:\ \mathbb E_D[G]>\sup_{D'\in\mathcal D_n,\ R(D',D_{\rm tr})\le r}\mathbb E_{D'}[G]\Big\},R={D∈Dn​: ED​[G]>D′∈Dn​, R(D′,Dtr​)≤rsup​ED′​[G]},

satisfies

−r<lim inf⁡n→∞1nlog⁡Dtr∞[Dbs[n]∈R].-r<\liminf_{n\to\infty}\frac1n\log D^\infty_{\rm tr}\big[D_{{\rm bs}[n]}\in\mathcal R\big].−r<n→∞liminf​n1​logDtr∞​[Dbs[n]​∈R].

Equivalently: there is ε>0\varepsilon>0ε>0 such that, for all sufficiently large nnn,

Dtrn[Dbs[n]∈R]≥exp⁡(−n(r−ε)).D_{\rm tr}^n\big[D_{{\rm bs}[n]}\in\mathcal R\big]\ge\exp\big(-n(r-\varepsilon)\big).Dtrn​[Dbs[n]​∈R]≥exp(−n(r−ε)).

Theorem 6 shows that with the bootstrap distance BBB the disappointment decays at rate at least rrr. Proposition 1 says that BBB is the smallest distance function with this guarantee: any distance function that exceeds BBB on an open set around some DDD loses the rate −r-r−r for some nominal formulation.

Formalization Note The statement is in the equivalent explicit-ε\varepsilonε form, which avoids log⁡0\log 0log0 and an extended-real limit inferior. The support Ωn\Omega_nΩn​ is a finite type and only support points enter; with w≡1w\equiv1w≡1 and k(n)=nk(n)=nk(n)=n the estimator (18) of a loss GGG is ED[G]\mathbb E_D[G]ED​[G], so the decision ztrr(x0)z^r_{\rm tr}(x_0)ztrr​(x0​) plays no role. G≥0G\ge 0G≥0 makes the loss admissible under Assumption 1. The neighbourhood is open relative to Dn\mathcal D_nDn​, and Dtr>0D_{\rm tr}>0Dtr​>0 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

/-- Proposition 1, p. 16. Let `R` be a distribution distance function, `D, D_tr ∈ 𝒟ₙ` with
`B(D, D_tr) = r`, and `N ⊆ 𝒟ₙ` a relatively open neighbourhood of `D` on which `R(·, D_tr) > r`.
Then there is a nominal formulation (cost estimator `D ↦ 𝔼_D[G]` with a nonnegative loss `G`) whose
disappointment set `ℛ` under the robust counterpart (24) with distance `R` satisfies
`-r < liminf (1/n) log D^∞_tr[D_bs[n] ∈ ℛ]`, stated equivalently as: for some `ε > 0`, eventually
`Dⁿ_tr(D_bs[n] ∈ ℛ) ≥ exp(-n (r - ε))`. -/
theorem proposition_1 {ι : Type*} [Fintype ι] [DecidableEq ι]
    [MeasurableSpace ι] [MeasurableSingletonClass ι]
    (R : (ι → ℝ) → (ι → ℝ) → EReal) (hR : IsDistributionDistance R)
    (D Dtr : ι → ℝ) (hD : D ∈ stdSimplex ℝ ι) (hDtr : Dtr ∈ stdSimplex ℝ ι)
    (hDtrpos : ∀ i, 0 < Dtr i) (r : ℝ) (hB : BootRobust.Perf.bootDist D Dtr = (r : EReal))
    (N : Set (ι → ℝ)) (hN : relOpen N) (hDN : D ∈ N)
    (hRN : ∀ D' ∈ N, (r : EReal) < R D' Dtr) :
    ∃ G : ι → ℝ, (∀ i, 0 ≤ G i) ∧ ∃ ε : ℝ, 0 < ε ∧ ∀ᶠ n : ℕ in Filter.atTop,
      ENNReal.ofReal (Real.exp (-((n : ℝ) * (r - ε)))) ≤
        bootLaw Dtr n {ω | empDist ω ∈ linDisapp R Dtr r G} := by sorry

end BootRobust.Optimality
Source
Bertsimas and Van Parys, Bootstrap robust prescriptive analytics, arXiv:1711.09974v2, Proposition 1, p. 16; proof in B.2, p. 27
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