(3.18) and p. 13, proof of Theorem 3.2 — P(ℳ_N^c) ≤ Σ_i P(f̂_N(x_i) ≥ f(x_i)+ε) + Σ_j P(f̂_N(x_j) ≤ f(x_j)−ε)
ProvedSAARate.Polyhedral.union_bound_p13Let and be the true and sample average functions of the mission's setting, built on a sample defined on a probability space . Let and be their optimal sets on , and let
Let and be such that, for every sample path and every , condition (2.13) () implies , and such that for all . Then there is , not depending on , with
The step combines (3.18), , with a union bound. It reduces the rate of Theorem 3.2 to the deviations of finitely many one-dimensional sample means.
Formalization Note The points are given through the hypotheses that Lemma 2.4 (c) provides. The standing assumptions (i)–(iv) are not needed for this step and are not assumed. is not shown to be measurable, so is its outer measure; an upper bound on it is the stronger statement. Indices are 0-based in Lean.
import Mathlib import Definitions.Def_SAARate_Polyhedral_Setting open MeasureTheory ProbabilityTheory
namespace SAARate.Polyhedral
/-- Proof of Theorem 3.2, (3.18) and p. 13: given points `x_1, …, x_q` for which condition (2.13)
forces `A_N` to be a nonempty face of `A` (Lemma 2.4 (c)) and `f(x_i) < f(x_j)` for
`i ≤ ℓ < j`, there is `ε > 0` (independent of `N`) with
`P(ℳ_N^c) ≤ Σ_{i ≤ ℓ} P(f̂_N(x_i) ≥ f(x_i) + ε) + Σ_{j > ℓ} P(f̂_N(x_j) ≤ f(x_j) − ε)`.
Indices are 0-based. Failure events are measured by the outer measure `Q`. -/
theorem union_bound_p13 {m : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
(h : SAARate.Sharp.E m → Ω → ℝ) (Θ : Set (SAARate.Sharp.E m))
{S : Type*} [MeasurableSpace S] (Q : Measure S) (ω : ℕ → S → Ω)
(q ℓ : ℕ) (x : Fin q → SAARate.Sharp.E m)
(hc : ∀ (s : ℕ → Ω) (N : ℕ),
(∀ i j : Fin q, i.val < ℓ → ℓ ≤ j.val → SAARate.Sharp.saaObj h s N (x i) < SAARate.Sharp.saaObj h s N (x j)) →
(SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h s N) Θ).Nonempty ∧
IsFace (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ) (SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h s N) Θ))
(hgap : ∀ i j : Fin q, i.val < ℓ → ℓ ≤ j.val →
SAARate.Sharp.expectedObj P h (x i) < SAARate.Sharp.expectedObj P h (x j)) :
∃ ε > 0, ∀ N : ℕ,
Q {s | ¬ ((SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h (fun k => ω k s) N) Θ).Nonempty ∧
IsFace (SAARate.Sharp.argminOn (SAARate.Sharp.expectedObj P h) Θ) (SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h (fun k => ω k s) N) Θ))} ≤
(∑ i ∈ Finset.univ.filter (fun i : Fin q => i.val < ℓ),
Q {s | SAARate.Sharp.expectedObj P h (x i) + ε ≤ SAARate.Sharp.saaObj h (fun k => ω k s) N (x i)}) +
∑ j ∈ Finset.univ.filter (fun j : Fin q => ℓ ≤ j.val),
Q {s | SAARate.Sharp.saaObj h (fun k => ω k s) N (x j) ≤ SAARate.Sharp.expectedObj P h (x j) - ε} := by sorry
end SAARate.Polyhedral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.