§5, p. 188 — the online loss of round t is unbiased for the risk of w_t
ProvedOnlineLearningOCO.OnlineToBatch.round_identityonline-learningonline-to-batchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-learning
Let be independent examples, each with law , let be an admissible cost on with risk , and let be the prediction of an online learner in round . Then for every round ,
This is the step of the proof of Theorem 5.1 where the non-anticipation of the online algorithm enters: is a function of the earlier examples only, and is a fresh draw from .
Formalization Note Rounds are numbered from . No integrability of is assumed; both sides are Bochner integrals of nonnegative functions.
Preamble
import Mathlib import Definitions.Def_OnlineLearningOCO_OnlineToBatch_Setting open MeasureTheory
Formal statement
namespace OnlineLearningOCO.OnlineToBatch
/-- Shalev-Shwartz, FnT ML 4(2) (2011), §5, proof of Theorem 5.1, display after (5.2), p. 188.
Let `ψ₀, …, ψ_{T-1}` be i.i.d. with law `Q`, and let `w_t` be the prediction of a
non-anticipating online algorithm in round `t` of the online-to-batch conversion. Then
`𝔼[c(w_t, ψ_t)] = 𝔼[C(w_t)]`. -/
theorem round_identity {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 : ℕ} (t : Fin T) :
∫ ψ, c (iterate A ψ t) (ψ t) ∂(sampleLaw Q T) =
∫ ψ, risk Q c (iterate A ψ 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, display after (5.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.