Theorem 1, p. 5 — UCB calibration: with probability ≥ 1 − δ the selected λ̂ has R(λ̂) ≤ α
ProvedRiskControl.UCB.theorem_1Theorem 1 (Validity of UCB calibration). Let be a probability distribution on and let be an i.i.d. sample from . Let be closed and let , , be nested on :
Let be a loss with
such that is integrable for each , and write . Assume that for some and that is continuous on . Let be a function of the sample satisfying, for every ,
and let as in (4). Then
that is, is an -risk-controlling prediction set.
This is the paper's main guarantee: a confidence bound that holds for each fixed separately suffices for the data-dependent choice , with no uniform convergence, because the risk is monotone in .
Formalization Note The conclusion is written as a failure bound: the -outer measure of the event "the set in (4) is nonempty and " is at most ; for a measurable event this is the page's statement, and no measurability of or is assumed. When the set in (4) is empty, the page's need not lie in and is undefined; that event is excluded (the safe output there is , of risk ). The space of predictions is ; is a closed subset of the extended reals and is continuous in its subspace topology. The integrability of the loss, the nonnegativity of , the closedness of and the point are the standing assumptions of §2.1 (p. 4). The i.i.d. sample is the product measure . The monotonicity of is not assumed; it follows from (1) and (2). No range is placed on or , as on the page.
import Mathlib import Definitions.Def_RiskControl_UCB_Setting open MeasureTheory
namespace RiskControl.UCB
/-- Theorem 1 (Validity of UCB calibration), arXiv:2101.02703v3, p. 5, in the setting of §2.1:
an i.i.d. calibration sample `D = ((X₁, Y₁), …, (Xₙ, Yₙ))` from `P`, a closed `Λ ⊆ ℝ ∪ {±∞}`,
nested set predictors (1), a nonnegative loss with (2), integrable losses, some `λ_max ∈ Λ`
with `R(λ_max) = 0`, a continuous risk, and a pointwise UCB (3). Then
`P(R(𝒯_λ̂) > α) ≤ δ` on the event that the calibration set of (4) is nonempty. -/
theorem theorem_1 {𝒳 𝒴 𝒵 : Type*} [MeasurableSpace 𝒳] [MeasurableSpace 𝒴]
(P : Measure (𝒳 × 𝒴)) [IsProbabilityMeasure P] (n : ℕ)
(Λ : Set EReal) (hΛ : IsClosed Λ)
(T : EReal → 𝒳 → Set 𝒵)
(hnest : ∀ l₁ ∈ Λ, ∀ l₂ ∈ Λ, l₁ < l₂ → ∀ x, T l₁ x ⊆ T l₂ x)
(L : 𝒴 → Set 𝒵 → ℝ) (hL0 : ∀ y S, 0 ≤ L y S)
(hLmono : ∀ y S S', S ⊆ S' → L y S' ≤ L y S)
(hint : ∀ l ∈ Λ, Integrable (fun p : 𝒳 × 𝒴 => L p.2 (T l p.1)) P)
(hmax : ∃ lmax ∈ Λ, risk P L T lmax = 0)
(hcont : ContinuousOn (risk P L T) Λ)
(Rhat : (Fin n → 𝒳 × 𝒴) → EReal → ℝ) (α δ : ℝ)
(hucb : ∀ l ∈ Λ,
(Measure.pi fun _ : Fin n => P) {D | Rhat D l < risk P L T l} ≤ ENNReal.ofReal δ) :
(Measure.pi fun _ : Fin n => P)
{D | (calSet Λ (Rhat D) α).Nonempty ∧ α < risk P L T (lambdaHat Λ (Rhat D) α)}
≤ ENNReal.ofReal δ := by sorry
end RiskControl.UCB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.