Proof of Corollary 3 (B.5), p. 42 — from W ≤ κ log(1/δ0) w.p. 1 − δ0/2 to E W ≤ κ/2
ProvedSubsetShrink.BIC.tail_to_expectationexpectationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitytail-bound
Let be a probability space, a random variable and . Suppose that for every ,
Then for every , and
The proof of Theorem 5 applies this with a universal multiple of and the excess of over times the oracle term, turning the high-probability bounds (56) and (58) into the expectation bounds of Theorem 5.
Formalization Note The page writes but bounds it through for only, which is a bound on ; the statement's lower Lebesgue integral of (∫⁻ ofReal W) is exactly , and it bounds whenever the latter is defined. In the paper .
Preamble
import Mathlib import Definitions.Def_SubsetShrink_BIC_Model
Formal statement
namespace SubsetShrink.BIC
open MeasureTheory ProbabilityTheory
/-- Proof of Corollary 3 (B.5), p. 42: if `W ≤ κ log(1/δ0)` with probability at least `1 − δ0/2`
for every `δ0 ∈ (0, 1)`, then `2 P(W > w) ≤ e^{−w/κ}` for every `w ≥ 0`, and
`E[W⁺] ≤ κ/2` (here `κ = c0 σ²`). -/
theorem tail_to_expectation {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (W : Ω → ℝ) (hW : Measurable W) (κ : ℝ) (hκ : 0 < κ)
(h : ∀ δ0 : ℝ, 0 < δ0 → δ0 < 1 →
1 - δ0 / 2 ≤ (μ {ω | W ω ≤ κ * Real.log (1 / δ0)}).toReal) :
(∀ w : ℝ, 0 ≤ w → 2 * (μ {ω | w < W ω}).toReal ≤ Real.exp (-w / κ)) ∧
∫⁻ ω, ENNReal.ofReal (W ω) ∂μ ≤ ENNReal.ofReal (κ / 2) := by sorry
end SubsetShrink.BIC
Source
Mazumder, Radchenko & Dedieu, Subset Selection with Shrinkage, arXiv:1708.03288v4, p. 42, proof of Corollary 3 (B.5), displays 2P(W > w) ≤ e^{−w/[c0σ²]} and EW ≤ … ≤ c0σ²/2; invoked in B.13, p. 50
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.