§5, p. 189 — the average loss of a fixed hypothesis is unbiased for its risk
ProvedOnlineLearningOCO.OnlineToBatch.comparator_identityonline-learningonline-to-batchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-learning
Let , let be independent examples, each with law , and let be an admissible cost on with risk . For every fixed ,
This identity turns the comparator term of the regret into the risk of the comparator; it is the step from Theorem 5.1 to Corollary 5.2.
Formalization Note Rounds are numbered . " any vector" is read as , where is defined.
Preamble
import Mathlib import Definitions.Def_OnlineLearningOCO_OnlineToBatch_Setting open MeasureTheory
Formal statement
namespace OnlineLearningOCO.OnlineToBatch
/-- Shalev-Shwartz, FnT ML 4(2) (2011), §5, p. 189, the line before Corollary 5.2:
for a fixed hypothesis `u ∈ S` and an i.i.d. sample `ψ₀, …, ψ_{T-1}` with law `Q`,
`𝔼[(1/T) ∑_t c(u, ψ_t)] = C(u)`. -/
theorem comparator_identity {d : ℕ} {Ψ : Type*} [MeasurableSpace Ψ]
(S : Set (EuclideanSpace ℝ (Fin d)))
(Q : Measure Ψ) [IsProbabilityMeasure Q] (c : EuclideanSpace ℝ (Fin d) → Ψ → ℝ)
(hc : IsCost S Q c) (T : ℕ) (hT : 0 < T) (u : EuclideanSpace ℝ (Fin d)) (hu : u ∈ S) :
∫ ψ, (1 / (T : ℝ)) * ∑ t : Fin T, c u (ψ t) ∂(sampleLaw Q T) = risk Q c u := by sorry
end OnlineLearningOCO.OnlineToBatch
Source
Shalev-Shwartz, Online Learning and Online Convex Optimization, Found. Trends Mach. Learn. 4(2) (2011) 107–194, p. 189, §5, the sentence before Corollary 5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.