Theorem 5.1 — the average online loss bounds the expected risk of the converted hypothesis
ProvedOnlineLearningOCO.OnlineToBatch.theorem_5_1Let , 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 .
- Randomization. Let , where is uniform on and independent of the sample. Then, with the expectation over and ,
- Averaging. If moreover is convex, is convex on , and every online loss has finite expectation, then for ,
The theorem turns any online learner into a stochastic learner whose expected risk is at most the expected average online loss.
Formalization Note The randomized output is modelled genuinely: the expectation on the left of part 1 is over the product of the sample law and the uniform law of . Convexity of is added in part 2 so that , where is defined. Integrability of the online losses in part 2 is added: when the expected online loss is infinite the paper's inequality holds trivially, while Lean's Bochner integral would return for it.
import Mathlib import Definitions.Def_OnlineLearningOCO_OnlineToBatch_Setting open MeasureTheory
namespace OnlineLearningOCO.OnlineToBatch
/-- Theorem 5.1 (Shalev-Shwartz, FnT ML 4(2) (2011), §5, p. 188).
Let `ψ₀, …, ψ_{T-1}` be i.i.d. with law `Q`, and let `w_t` be the predictions of a
non-anticipating online algorithm run on the losses `f_t = c(·, ψ_t)`.
(a) For the conversion with randomization, `w̄ = w_r` with `r` uniform on `[T]` and independent
of the sample: `𝔼_{ψ,r}[C(w̄)] = 𝔼_ψ[(1/T) ∑_t f_t(w_t)]`.
(b) If moreover `S` is convex and `C` is convex on `S`, then for the conversion with averaging,
`w̄ = (1/T) ∑_t w_t`: `𝔼[C(w̄)] ≤ 𝔼[(1/T) ∑_t f_t(w_t)]`.
Formalization Note: in (b) the online losses `c(w_t, ψ_t)` are assumed integrable (finite
expected online loss); otherwise the right side is `+∞` and the inequality has no content. -/
theorem theorem_5_1 {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) :
(∫ p, risk Q c (randomizedOutput A p.1 p.2) ∂((sampleLaw Q T).prod (uniformIndex T)) =
∫ ψ, avgOnlineLoss c A ψ ∂(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) ≤
∫ ψ, avgOnlineLoss c A ψ ∂(sampleLaw Q T)) := by sorry
end OnlineLearningOCO.OnlineToBatch
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.