Corollary 5.2 — online-to-batch conversion: excess risk is at most the expected average regret
ProvedOnlineLearningOCO.OnlineToBatch.corollary_5_2Let , let be independent examples, each with law , let be an admissible cost on with risk , and let be the predictions of an online learner run on the losses , where depends only on . Let be any comparator.
- Randomization. For with uniform on and independent of the sample,
- Averaging. If moreover is convex, is convex on , and every online loss has finite expectation, then the same inequality holds for .
The right-hand side is the expected regret of the online algorithm against , divided by . An online learner with low regret for losses of the form relative to therefore yields a hypothesis whose risk is close to the best risk in .
Formalization Note " any vector" is read as , where is defined. The conditions of Theorem 5.1 are carried over: convexity of and integrability of the online losses are added for the averaging part, and in the randomization part the expectation is over the product of the sample law and the uniform law of .
import Mathlib import Definitions.Def_OnlineLearningOCO_OnlineToBatch_Setting open MeasureTheory
namespace OnlineLearningOCO.OnlineToBatch
/-- Corollary 5.2 (Shalev-Shwartz, FnT ML 4(2) (2011), §5, p. 189).
Under the conditions of Theorem 5.1, for every `u ∈ S`,
`𝔼[C(w̄)] − C(u) ≤ 𝔼[(1/T) ∑_t (f_t(w_t) − f_t(u))]`, where `f_t = c(·, ψ_t)`:
(a) for the conversion with randomization (expectation over the sample and `r`);
(b) for the conversion with averaging, when `S` is convex and `C` is convex on `S`.
Formalization Note: in (b) the online losses `c(w_t, ψ_t)` are assumed integrable (finite
expected online loss), as in Theorem 5.1 (b). -/
theorem corollary_5_2 {d : ℕ} {Ψ : Type*} [MeasurableSpace Ψ] (S : Set (EuclideanSpace ℝ (Fin d)))
(Q : Measure Ψ) [IsProbabilityMeasure Q] (c : EuclideanSpace ℝ (Fin d) → Ψ → ℝ)
(hc : IsCost S Q c) (A : (t : ℕ) → (Fin t → Ψ) → EuclideanSpace ℝ (Fin d))
(hA : IsOnlineLearner S A)
(T : ℕ) (hT : 0 < T) (u : EuclideanSpace ℝ (Fin d)) (hu : u ∈ S) :
(∫ p, risk Q c (randomizedOutput A p.1 p.2) ∂((sampleLaw Q T).prod (uniformIndex T)) -
risk Q c u ≤ ∫ ψ, avgRegret c A ψ u ∂(sampleLaw Q T)) ∧
(Convex ℝ S → ConvexOn ℝ S (risk Q c) →
(∀ t : Fin T, Integrable (fun ψ => c (iterate A ψ t) (ψ t)) (sampleLaw Q T)) →
∫ ψ, risk Q c (averageOutput A ψ) ∂(sampleLaw Q T) - risk Q c u ≤
∫ ψ, avgRegret c A ψ u ∂(sampleLaw Q T)) := by sorry
end OnlineLearningOCO.OnlineToBatch
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.