Theorem 2, p. 7 — liminf_n P(μ_x̂ ≤ G_n(x̂) + z_α s_n(x*_n)/√n) ≥ 1 − α for the SRP (needs σ²_x̂(x*_max) > 0 when α > 1/2)
ProvedSolutionQuality.SRP.theorem2_srp_validConsider the stochastic program under assumptions (A1)–(A3), a candidate solution with optimality gap , and observations i.i.d. as . The single replication procedure (SRP) solves the sampled problem (SP) once, obtaining an optimal solution , and computes
- the gap estimate of (2), with ;
- the sample variance .
Given and with , the one-sided interval of (5) is asymptotically valid:
The theorem shows that a single sample-average problem gives enough information for a valid statistical upper bound on the optimality gap of a candidate solution, even though need not be asymptotically normal.
Formalization Note. The decision dimension is ; the sample is the first terms ξ 0, …, ξ (n-1) of one i.i.d. sequence. is a measurable map that, almost surely, minimizes over on the same sample. is measurable for each , and (A2) is read as the existence of an integrable majorant of . is any real with cdf (gaussianReal 0 1) zα = 1 - α. Probabilities are in ℝ≥0∞, where liminf is genuine. At the factors , and take Lean's junk value , which a liminf ignores.
Correction of the page. The statement carries one hypothesis the page does not print: , or for some (equivalently ). The page's proof of the case replaces by and fails when on , where (6) itself is false: for , , , and one has , , and the coverage tends to .
import Mathlib import Definitions.Def_SolutionQuality_SRP_Setting
namespace SolutionQuality.SRP
open MeasureTheory ProbabilityTheory Filter
/-- Theorem 2 (p. 7), display (6), with the one correction recorded in the moderation:
the hypothesis `hdeg` (`α ≤ 1/2`, or some optimal `x` has `σ²_x̂(x) > 0`, i.e.
`σ²_x̂(x*_max) > 0`). The page states (6) for every `0 < α < 1`, but its proof of the case
`α > 1/2` ("replace `x*_min` with `x*_max`") breaks down when `σ²_x̂ ≡ 0` on `X*`, and (6) is
then false: `X = [-1, 1]`, `f(x, ξ) = x² - 2xξ`, `ξ̃ ~ N(0, 1)`, `x̂ = 0`, `α = 0.9` gives
coverage `→ P(|N(0,1)| ≥ 2·z_{0.1}) ≈ 0.010 < 0.1`. -/
theorem theorem2_srp_valid {d : ℕ} {Ξ : Type*} [MeasurableSpace Ξ]
(μ : Measure Ξ) [IsProbabilityMeasure μ]
(f : E d → Ξ → ℝ) (hfm : ∀ x, Measurable (f x))
(X : Set (E d)) (hA : Assumptions μ f X)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ξ : ℕ → Ω → Ξ) (hξ : IsIIDSample P μ ξ)
(xhat : E d) (hxhat : xhat ∈ X)
(xn : ℕ → Ω → E d) (hxn : IsSAAMinimizerSeq P f X ξ xn)
(α : ℝ) (hα0 : 0 < α) (hα1 : α < 1)
(zα : ℝ) (hzα : cdf (gaussianReal 0 1) zα = 1 - α)
(hdeg : α ≤ 1 / 2 ∨ ∃ x ∈ optSet μ f X, 0 < gapVar μ f xhat x) :
ENNReal.ofReal (1 - α) ≤
liminf (fun n : ℕ => P {ω | optGap μ f X xhat ≤
gapEstimate f X xhat (fun i => ξ i ω) n +
zα * Real.sqrt (sampleVar f xhat (fun i => ξ i ω) n (xn n ω)) / Real.sqrt n}) atTop := by sorry
end SolutionQuality.SRP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.