Theorem 3 — exact coverage of the optimal value
ProvedGenEmpLik.Coverage.theorem_3confidence-regionempirical-likelihoodp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-optimization
Let be nonempty and compact, let the losses be measurable and satisfy Assumption B with , and suppose for some . Let satisfy Assumption A, let the observations be i.i.d. with law , and suppose the population optimizer is unique with . For ,
The theorem calibrates the empirical likelihood confidence set for the optimal value with a one degree of freedom chi square law.
Formalization Note The variance condition is needed for the result to hold: a deterministic loss has coverage one but a nontrivial chi square target. The set uses weights on the sample, and is outer probability.
Preamble
import Mathlib import Definitions.Def_GenEmpLik_Coverage_AssumptionA import Definitions.Def_GenEmpLik_Coverage_AssumptionB import Definitions.Def_GenEmpLik_Coverage_optimalValue import Definitions.Def_GenEmpLik_Coverage_empiricalOptimalValue import Definitions.Def_GenEmpLik_Coverage_divergenceBall import Definitions.Def_GenEmpLik_Coverage_confidenceSet import Definitions.Def_GenEmpLik_Coverage_influence import Definitions.Def_GenEmpLik_Coverage_remainder import Definitions.Def_GenEmpLik_Coverage_robustUpper import Definitions.Def_GenEmpLik_Coverage_uniqueOptimizer import Definitions.Def_VarianceRegularization_Expansion_empMean import Definitions.Def_VarianceRegularization_Expansion_empVar open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace GenEmpLik.Coverage
/-- Theorem 3, p. 8: asymptotically exact coverage of the optimal value. -/
theorem theorem_3
{Ω Ξ : Type*} [MeasurableSpace Ω] [MeasurableSpace Ξ]
(μ : Measure Ω) [IsProbabilityMeasure μ]
(ξ : ℕ → Ω → Ξ) (d : ℕ)
(X : Set (EuclideanSpace ℝ (Fin d)))
(ℓ : EuclideanSpace ℝ (Fin d) → Ξ → ℝ)
(M : Ξ → ℝ) (f : ℝ → EReal) (ρ : ℝ)
(hρ : 0 ≤ ρ) (hA : AssumptionA f)
(hX : X.Nonempty) (hB : AssumptionB X ℓ M)
(hℓmeas : ∀ x, Measurable (ℓ x))
(hM2 : Integrable (fun z => M z ^ 2) (μ.map (ξ 0)))
(hℓ2 : ∃ x0 ∈ X, Integrable (fun z => ℓ x0 z ^ 2) (μ.map (ξ 0)))
(hξmeas : ∀ i, Measurable (ξ i))
(hξindep : iIndepFun ξ μ)
(hξident : ∀ i, IdentDistrib (ξ i) (ξ 0) μ μ)
(hunique : HasUniqueOptimizer X ℓ (μ.map (ξ 0)))
(hvar : 0 < variance (ℓ (uniqueOptimizer X ℓ (μ.map (ξ 0)) hunique))
(μ.map (ξ 0))) :
Tendsto (fun n : ℕ => μ {ω |
optimalValue X ℓ (μ.map (ξ 0)) ∈
confidenceSet X ℓ f ρ (fun i : Fin n => ξ i ω)})
atTop (𝓝 (gaussianReal 0 1 {x : ℝ | x ^ 2 ≤ ρ})) := by sorry
end GenEmpLik.Coverage
Source
Duchi, Glynn & Namkoong, Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach, arXiv:1610.03425v3, p. 8, Theorem 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.