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
ProvedBootRobust.Optimality.proposition_1Let be a distribution distance function on (Definition 4). Let , with of full support, and . Suppose that for all in some neighbourhood of , open in . Then there is a nominal formulation — a nonnegative loss with cost estimator — whose disappointment set under the robust counterpart (24) with distance and radius ,
satisfies
Equivalently: there is such that, for all sufficiently large ,
Theorem 6 shows that with the bootstrap distance the disappointment decays at rate at least . Proposition 1 says that is the smallest distance function with this guarantee: any distance function that exceeds on an open set around some loses the rate for some nominal formulation.
Formalization Note The statement is in the equivalent explicit- form, which avoids and an extended-real limit inferior. The support is a finite type and only support points enter; with and the estimator (18) of a loss is , so the decision plays no role. makes the loss admissible under Assumption 1. The neighbourhood is open relative to , and is the paper's convention that is the support of the training data.
import Mathlib import Definitions.Def_BootRobust_Optimality_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.