Proposition 5, p. 7 — the Waudby-Smith–Ramdas bound R̂⁺_WSR is a (1 − δ) upper confidence bound for the mean loss
ProvedRiskControl.WSR.proposition_5This is Proposition 5 of Bates, Angelopoulos, Lei, Malik and Jordan (the Waudby-Smith–Ramdas bound), for one fixed parameter .
Let be a probability measure on concentrated on , the law of the loss , and let be its mean, the risk . Let , let , and let be i.i.d. with law (the losses of the calibration points). With the bound of Proposition 5 computed from (see the definition RiskControl.WSR.Process),
That is, is a upper confidence bound for in the sense of display (3) of the paper. Combined with the paper's Theorem 1, it yields Theorem 4: UCB calibration with this bound gives a risk-controlling prediction set.
Formalization Note is fixed and dropped from the notation: is the law of , which lies in by the standing assumption of §3.1 (loss nonnegative and bounded by one), so the calibration losses are i.i.d. with law and the probability is the product measure on . The statement bounds the failure event by ; it is evaluated by the outer measure, which for a measurable event is the page's . Two hypotheses implicit on the page are added: ( is the sample size and appears in a denominator of ) and (so that ; for the claim is trivial). The infimum defining is taken in the extended reals, so it is (and the bound holds) when no qualifies.
import Mathlib import Definitions.Def_RiskControl_WSR_Process open MeasureTheory
namespace RiskControl.WSR
/-- Proposition 5 (Waudby-Smith–Ramdas bound), p. 7 (arXiv:2101.02703v3): for `n ≥ 1` i.i.d.
losses with law `Q` on `[0, 1]` and `δ ∈ (0, 1)`, `R̂⁺_WSR` is a `(1 − δ)` upper confidence
bound for the mean `R = ∫ x dQ`: `Qⁿ(R̂⁺_WSR < R) ≤ δ`. -/
theorem proposition_5 (Q : Measure ℝ) [IsProbabilityMeasure Q]
(hQ : ∀ᵐ x ∂Q, x ∈ Set.Icc (0 : ℝ) 1) (n : ℕ) (hn : 1 ≤ n)
(δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1) :
(Measure.pi fun _ : Fin n => Q)
{ω | wsrUCB n δ ω < ((∫ x, x ∂Q : ℝ) : EReal)} ≤ ENNReal.ofReal δ := by sorry
end RiskControl.WSR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.