§2.1, pp. 4–5 — under nesting (1) and loss monotonicity (2), the risk λ ↦ R(λ) is nonincreasing on Λ
ProvedRiskControl.UCB.risk_antitonemonotonicityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prediction-setsrisk-control
Let be a measure on , let , and let be a family of set-valued predictors that is nested on ,
and let be a loss on sets satisfying
Suppose that is -integrable for every . Then the risk is nonincreasing on :
This monotonicity of the risk is what lets the paper turn a pointwise confidence bound into a guarantee for the data-driven choice (p. 5); Theorem A.1 assumes it, and Theorem 1 obtains it from (1) and (2).
Formalization Note The paper names this property on p. 5 without a separate statement. The integrability hypothesis is needed because the Bochner integral returns for a non-integrable integrand.
Preamble
import Mathlib import Definitions.Def_RiskControl_UCB_Setting open MeasureTheory
Formal statement
namespace RiskControl.UCB
/-- §2.1, pp. 4–5: under the nesting property (1) of `{𝒯_λ}` and the monotonicity (2) of the
loss, the risk `λ ↦ R(λ)` is nonincreasing on `Λ`. -/
theorem risk_antitone {𝒳 𝒴 𝒵 : Type*} [MeasurableSpace 𝒳] [MeasurableSpace 𝒴]
(P : Measure (𝒳 × 𝒴)) (Λ : Set EReal)
(T : EReal → 𝒳 → Set 𝒵)
(hnest : ∀ l₁ ∈ Λ, ∀ l₂ ∈ Λ, l₁ < l₂ → ∀ x, T l₁ x ⊆ T l₂ x)
(L : 𝒴 → Set 𝒵 → ℝ)
(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) :
AntitoneOn (risk P L T) Λ := by sorry
end RiskControl.UCB
Source
Bates, Angelopoulos, Lei, Malik & Jordan, arXiv:2101.02703v3, §2.1, (1), (2) and the risk R(𝒯), p. 4; monotonicity of the risk named on p. 5, paragraph after Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.