Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6, p. 15 — the bootstrap disappointment of the entropic robust budget is at most Σⱼ exp(−n·max{r, r^j_n})

Proved
BootRobust.Perf.theorem_6

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

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

Let Ωn\Omega_nΩn​ be the finite support of the training data, Dtr∈DnD_{\mathrm{tr}}\in\mathcal D_nDtr​∈Dn​ its empirical distribution (all entries positive), 1≤k≤n1\le k\le n1≤k≤n, ∅=N0⊆N1⊆⋯⊆Nn=Ωn\emptyset=N^0\subseteq N^1\subseteq\dots\subseteq N^n=\Omega_n∅=N0⊆N1⊆⋯⊆Nn=Ωn​ the nested neighbourhoods of the context, w>0w>0w>0 the weights, r∈Rr\in\mathbb Rr∈R the robustness radius and L(z,⋅)L(z,\cdot)L(z,⋅) a real loss for each decision zzz. Let

  1. EDn[L(z,y)∣x=x0]E^n_D[L(z,y)|x=x_0]EDn​[L(z,y)∣x=x0​] be the estimator (18): the www-weighted average of the loss over the smallest neighbourhood holding at least kkk of the nnn observations of DDD;
  2. cˉn(z)=max⁡j∈[n]cnj(z)\bar c_n(z)=\max_{j\in[n]}c^j_n(z)cˉn​(z)=maxj∈[n]​cnj​(z) be the robust budget (26), where cnj(z)=sup⁡{EDn,j[L(z,y)∣x=x0]:D∈Dn, B(D,Dtr)≤r}c^j_n(z)=\sup\{E^{n,j}_D[L(z,y)|x=x_0]: D\in\mathcal D_n,\ B(D,D_{\mathrm{tr}})\le r\}cnj​(z)=sup{EDn,j​[L(z,y)∣x=x0​]:D∈Dn​, B(D,Dtr​)≤r} and BBB is the bootstrap distance (27);
  3. rnj=inf⁡{B(D,Dtr):D∈Dnj}r^j_n=\inf\{B(D,D_{\mathrm{tr}}):D\in\mathcal D^j_n\}rnj​=inf{B(D,Dtr​):D∈Dnj​} be the minimum radii (29);
  4. Dbs[n]D_{\mathrm{bs}[n]}Dbs[n]​ be the empirical distribution of nnn independent draws from DtrD_{\mathrm{tr}}Dtr​ (14).

Then for every decision zzz the bootstrap disappointment (17) satisfies

P[EDbs[n]n[L(z,y)∣x=x0]>cˉn(z)] ≤ ∑j∈[n]exp⁡(−n⋅max⁡{r,rnj}),\mathbb P\Big[E^n_{D_{\mathrm{bs}[n]}}[L(z,y)|x=x_0]>\bar c_n(z)\Big]\ \le\ \sum_{j\in[n]}\exp\big(-n\cdot\max\{r,r^j_n\}\big),P[EDbs[n]​n​[L(z,y)∣x=x0​]>cˉn​(z)] ≤ j∈[n]∑​exp(−n⋅max{r,rnj​}),

with exp⁡(−n⋅(+∞))=0\exp(-n\cdot(+\infty))=0exp(−n⋅(+∞))=0 when Dnj\mathcal D^j_nDnj​ is empty.

The theorem shows that the entropic robust budget is a bootstrap robust counterpart (Definition 1) of the nearest-neighbours-type estimator, with a disappointment decaying exponentially in nnn at rate at least rrr.

Formalization Note The budget is the formulation (26), max⁡jcnj\max_j c^j_nmaxj​cnj​, which the paper computes (Lemma 1) and which is never larger than (24); with it the theorem is the stronger statement. The page states the bound for the robust prescriptor ztr[n]r(x0)z^r_{\mathrm{tr}[n]}(x_0)ztr[n]r​(x0​); the proof fixes an arbitrary decision, so it is stated for every zzz. DtrD_{\mathrm{tr}}Dtr​ is not required to lie in Dn,n\mathcal D_{n,n}Dn,n​ and rrr may be any real (both generalizations). Losses are real-valued (Assumption 1 allows +∞+\infty+∞); nonnegativity and convexity in zzz are not used. Definition 2's neighbourhoods are abstracted to a nested chain, and covariates and distances do not appear.

Preamble
import Mathlib
import Definitions.Def_BootRobust_Perf_Setting
Formal statement
namespace BootRobust.Perf

/-- Theorem 6, p. 15: the robust formulation with bootstrap distance `B` and radius `r`
suffers bootstrap disappointment (17) at most `∑_{j ∈ [n]} exp(−n · max{r, r^j_n})`: for any
decision `z`, the probability that the estimate (18) on the bootstrap data exceeds the robust
budget (26) computed on the training data is at most that sum. -/
theorem theorem_6 {ι : Type*} [Fintype ι] [DecidableEq ι] [MeasurableSpace ι]
    [MeasurableSingletonClass ι] (n k : ℕ) (hn : 1 ≤ n) (hk : 1 ≤ k) (hkn : k ≤ n)
    (N : ℕ → Finset ι) (hNmono : Monotone N) (hN0 : N 0 = ∅) (hNn : N n = Finset.univ)
    (w : ι → ℝ) (hw : ∀ i, 0 < w i) (Dtr : ι → ℝ) (hDtr : Dtr ∈ stdSimplex ℝ ι)
    (hDtrpos : ∀ i, 0 < Dtr i) (r : ℝ) {Z : Type*} (L : Z → ι → ℝ) (z : Z) :
    bootLaw Dtr n
        {ω | robustBudget n k N w (L z) Dtr r <
          ((nominalEst n k N w (L z) (empDist ω) : ℝ) : EReal)} ≤
      ∑ j ∈ Finset.Icc 1 n, expNeg n (max (r : EReal) (rj n k N Dtr j)) := by sorry

end BootRobust.Perf
Source
Bertsimas and Van Parys, Bootstrap robust prescriptive analytics, arXiv:1711.09974v2, Theorem 6, p. 15
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