Theorem 3.1, p. 11 — under (A) and (B), ∃ β > 0 with limsup_N N⁻¹ log P(ℰ^c_N) ≤ −β
ProvedSAARate.SharpLD.theorem_3_1Let be a probability measure on a measurable space , let , and let . Write for the true objective (1.1) and for the sample average objective (1.2) built from an i.i.d. sample with law . The assumptions of Theorem 2.1 are: (i) is convex for every ; (ii) is well defined and finite valued; (iii) is closed and convex; (iv) Assumption (A): has the unique minimizer on and there is with for all . Assumption (B) asks for a with for -almost every , where is the directional derivative of at in direction and is the unit sphere.
Let be the set of optimal solutions of the SAA problem and let be the event that is nonempty and (3.7), i.e. that the SAA problem has the unique optimal solution .
Theorem 3.1. Suppose that the assumptions (i)–(iv) of Theorem 2.1 are satisfied and that Assumption (B) holds. Then there is a constant such that
So at a sharp minimum the probability that the sample average approximation fails to return exactly the true solution decays exponentially in the sample size.
Formalization Note The sample is one i.i.d. sequence of -valued maps on a separate probability space , each with law ; uses its first terms. The rate is stated in the equivalent -form: there is such that for every , eventually in , ; this avoids the logarithm of a probability that may be . is not shown to be measurable, so is its outer measure, which makes the upper bound stronger. "f finite valued" is the hypothesis that each is -integrable. The directional derivatives in (B) are true limits because is convex.
import Mathlib import Definitions.Def_SAARate_SharpLD_Setting open MeasureTheory ProbabilityTheory Filter Topology
namespace SAARate.SharpLD
theorem theorem_3_1 {m : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (h : SAARate.Sharp.E m → Ω → ℝ)
(hconv : ∀ ω, ConvexOn ℝ Set.univ (fun x => h x ω))
(hint : ∀ x, Integrable (h x) P)
(Θ : Set (SAARate.Sharp.E m)) (hΘc : IsClosed Θ) (hΘv : Convex ℝ Θ)
(xbar : SAARate.Sharp.E m) (hA : SAARate.Sharp.AssumptionA P h Θ xbar)
(κ : ℝ) (hB : AssumptionB P h xbar κ)
{S : Type*} [MeasurableSpace S] (Q : Measure S) [IsProbabilityMeasure Q]
(ω : ℕ → S → Ω) (hω : IsIIDSample Q P ω) :
∃ β > 0, ∀ ε > 0, ∀ᶠ N : ℕ in atTop,
Q {s | SAARate.Sharp.argminOn (SAARate.Sharp.saaObj h (fun j => ω j s) N) Θ ≠ {xbar}} ≤
ENNReal.ofReal (Real.exp (-(β - ε) * N)) := by sorry
end SAARate.SharpLD
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.