Equation (5.1) — the expected average online loss equals the expected average risk of the iterates
ProvedOnlineLearningOCO.OnlineToBatch.eq_5_1online-learningonline-to-batchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-learning
Let , 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 . Then
The average online loss, which the regret of the online algorithm controls, is thus an unbiased estimate of the average risk of the iterates.
Formalization Note Rounds are numbered . No integrability of the online losses is assumed.
Preamble
import Mathlib import Definitions.Def_OnlineLearningOCO_OnlineToBatch_Setting open MeasureTheory
Formal statement
namespace OnlineLearningOCO.OnlineToBatch
/-- Equation (5.1) (Shalev-Shwartz, FnT ML 4(2) (2011), §5, proof of Theorem 5.1, p. 188).
For an i.i.d. sample `ψ₀, …, ψ_{T-1}` with law `Q` and the predictions `w_t` of a
non-anticipating online algorithm,
`𝔼[(1/T) ∑_t C(w_t)] = 𝔼[(1/T) ∑_t c(w_t, ψ_t)]`. -/
theorem eq_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) :
∫ ψ, (1 / (T : ℝ)) * ∑ t : Fin T, risk Q c (iterate A ψ t) ∂(sampleLaw Q T) =
∫ ψ, (1 / (T : ℝ)) * ∑ t : Fin T, c (iterate A ψ t) (ψ t) ∂(sampleLaw Q T) := by sorry
end OnlineLearningOCO.OnlineToBatch
Source
Shalev-Shwartz, Online Learning and Online Convex Optimization, Found. Trends Mach. Learn. 4(2) (2011) 107–194, p. 188, §5, proof of Theorem 5.1, Equation (5.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.