Theorem 6, p. 15 — the bootstrap disappointment of the entropic robust budget is at most Σⱼ exp(−n·max{r, r^j_n})
ProvedBootRobust.Perf.theorem_6Let be the finite support of the training data, its empirical distribution (all entries positive), , the nested neighbourhoods of the context, the weights, the robustness radius and a real loss for each decision . Let
- be the estimator (18): the -weighted average of the loss over the smallest neighbourhood holding at least of the observations of ;
- be the robust budget (26), where and is the bootstrap distance (27);
- be the minimum radii (29);
- be the empirical distribution of independent draws from (14).
Then for every decision the bootstrap disappointment (17) satisfies
with when 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 at rate at least .
Formalization Note The budget is the formulation (26), , 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 ; the proof fixes an arbitrary decision, so it is stated for every . is not required to lie in and may be any real (both generalizations). Losses are real-valued (Assumption 1 allows ); nonnegativity and convexity in are not used. Definition 2's neighbourhoods are abstracted to a nested chain, and covariates and distances do not appear.
import Mathlib import Definitions.Def_BootRobust_Perf_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.