Theorem 1 (Weak LDP), (7a), p. 12 — limsup (1/T) log ℙ^∞(ℙ̂_T ∈ 𝒟) ≤ −inf_{ℙ′∈𝒟} I(ℙ′,ℙ)
ProvedDROOptimal.Predictor.theorem_1_upperlarge-deviationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrelative-entropysanov-theorem
Let be drawn independently from a distribution on , and let be the empirical distribution of the first samples. Then for every Borel set ,
This large deviation upper bound is what makes feasible in (5) (Theorem 3).
Formalization Note The statement is logarithm-free: for every real (an extended real), eventually . This is equivalent to the displayed bound with , including the case of an infinite infimum. Borel means MeasurableSet D in the simplex subtype.
Preamble
import Mathlib import Definitions.Def_DROOptimal_Predictor_Setting
Formal statement
namespace DROOptimal.Predictor
/-- Theorem 1 (Weak LDP), (7a), p. 12: if the samples are drawn independently from ℙ ∈ 𝒫, then for
every Borel set 𝒟 ⊆ 𝒫,
limsup_{T→∞} (1/T) log ℙ^∞(ℙ̂_T ∈ 𝒟) ≤ − inf_{ℙ′ ∈ 𝒟} I(ℙ′, ℙ),
stated without logarithms: for every real s below the (`EReal`) infimum, eventually
ℙ^∞(ℙ̂_T ∈ 𝒟) ≤ e^{−sT}. -/
theorem theorem_1_upper {d : ℕ} (ℙ : Δ d) (D : Set (Δ d)) (hD : MeasurableSet D) (s : ℝ)
(hs : (s : EReal) < ⨅ ℙ' ∈ D, relEntropy ℙ' ℙ) :
∀ᶠ T : ℕ in Filter.atTop, empProb ℙ T D ≤ Real.exp (-(s * (T : ℝ))) := by sorry
end DROOptimal.Predictor
Source
Van Parys, Mohajerin Esfahani & Kuhn, From Data to Decisions: Distributionally Robust Optimization is Optimal, arXiv:1704.04118v3, p. 12, Theorem 1, (7a); proof in Appendix A, pp. 27–28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.