Theorem 2 (Strong LDP), (9), p. 13 — ℙ^∞(ℙ̂_T ∈ 𝒟) ≤ (T+1)^d e^{−T inf_{ℙ′∈𝒟} I(ℙ′,ℙ)} for all T ≥ 1
ProvedDROOptimal.Predictor.theorem_2large-deviationsmethod-of-typesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrelative-entropy
Let be drawn independently from a distribution on , and let be the empirical distribution of . Then for every Borel set and every ,
where is the relative entropy and .
This is the finite-sample (method of types) form of Sanov's theorem; it gives the finite-sample guarantee of Theorem 5.
Formalization Note The infimum is taken in the extended reals (it is for empty ). The bound is stated for every real as ; this is the displayed inequality when the infimum is finite, and forces probability when it is . Borel means MeasurableSet D in the simplex subtype. The paper writes ; the empirical distribution is defined for only, so is assumed.
Preamble
import Mathlib import Definitions.Def_DROOptimal_Predictor_Setting
Formal statement
namespace DROOptimal.Predictor
/-- Theorem 2 (Strong LDP), (9), p. 13: if the samples are drawn independently from ℙ ∈ 𝒫, then for
every Borel set 𝒟 ⊆ 𝒫 and every T ≥ 1,
ℙ^∞(ℙ̂_T ∈ 𝒟) ≤ (T + 1)^d e^{−T inf_{ℙ′ ∈ 𝒟} I(ℙ′, ℙ)}.
The infimum lives in `EReal` (it is +∞ when 𝒟 is empty or I(·, ℙ) ≡ ∞ on 𝒟, and then the bound is 0);
the bound is stated for every real s ≤ inf_{ℙ′ ∈ 𝒟} I(ℙ′, ℙ). -/
theorem theorem_2 {d : ℕ} (ℙ : Δ d) (D : Set (Δ d)) (hD : MeasurableSet D)
(T : ℕ) (hT : 1 ≤ T) (s : ℝ)
(hs : (s : EReal) ≤ ⨅ ℙ' ∈ D, relEntropy ℙ' ℙ) :
empProb ℙ T D ≤ ((T : ℝ) + 1) ^ d * Real.exp (-((T : ℝ) * s)) := by sorry
end DROOptimal.Predictor
Source
Van Parys, Mohajerin Esfahani & Kuhn, From Data to Decisions: Distributionally Robust Optimization is Optimal, arXiv:1704.04118v3, p. 13, Theorem 2, (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.