Proof of Theorem 2.22 — D_{R⋆}(−z_{1:t} ‖ −z_{1:t−1}) ≤ η Σᵢ wₜ[i]zₜ[i]² when ηzₜ[i] ≥ −1
ProvedOnlineLearningOCO.NormalizedEG.bregman_step_boundexponentiated-gradientonline-convex-optimizationonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let , , let be loss vectors, let be the normalized-EG weights , and let . If at round we have for every , then
This is the per-round bound that, summed over and combined with Lemma 2.20, gives the local-norm regret bound of Theorem 2.22. The right-hand side is for the local norm (p. 153).
Formalization Note Rounds are numbered from : wmWeights η z t is the paper's , and cumSum z t is the paper's . The Bregman divergence is that of with the softmax as its gradient (bregmanLSE).
Preamble
import Mathlib import Definitions.Def_OnlineLearningOCO_NormalizedEG_Duality import Definitions.Def_UnderstandingML_Online
Formal statement
namespace OnlineLearningOCO.NormalizedEG
open UnderstandingML
/-- §2.8, proof of Theorem 2.22, pp. 153–154. If `η > 0` and `η z_t[i] ≥ −1` for every `i`, the
Bregman divergence of the log-sum-exp conjugate `R⋆(θ) = (1/η) log ∑_i e^{η θ[i]}` along the
normalized-EG run is bounded by the local norm of `z_t`:
`D_{R⋆}(−z_{1:t} ‖ −z_{1:t−1}) ≤ η ∑_i w_t[i] z_t[i]²`.
Rounds are 0-based: `wmWeights η z t` is the paper's `w_{t+1}`. -/
theorem bregman_step_bound {d : ℕ} (hd : 0 < d) (η : ℝ) (hη : 0 < η) (z : ℕ → Fin d → ℝ) (t : ℕ)
(hz : ∀ i, -1 ≤ η * z t i) :
bregmanLSE η (-(cumSum z (t + 1))) (-(cumSum z t)) ≤
η * ∑ i, wmWeights η z t i * z t i ^ 2 := by sorry
end OnlineLearningOCO.NormalizedEG
Source
Shalev-Shwartz, Online Learning and Online Convex Optimization, Found. Trends Mach. Learn. 4(2) (2011) 107–194, pp. 153–154, §2.8, proof of Theorem 2.22 (claim on p. 153, last display on p. 154)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.