Theorem 2.22 — normalized EG has regret at most log(d)/η + η Σₜ Σᵢ wₜ[i]zₜ[i]² when ηzₜ[i] ≥ −1
ProvedOnlineLearningOCO.NormalizedEG.theorem_2_22Let and . The normalized Exponentiated Gradient algorithm on linear losses , , starts from and updates ; equivalently
Assume for all and . Then for every and every in the probability simplex ,
This is the local-norm refinement of the regret bound of normalized EG: the usual term is replaced by with the local norm . Losses may be negative, down to . It is the tool behind the analyses of Hedge-type algorithms in the later sections of the survey.
Formalization Note is the natural logarithm. The page leaves the comparator unquantified; it ranges over the probability simplex, the competing set of the normalized-entropy regularizer (the bound is false for outside it). Rounds are numbered from : wmWeights η z t (the published weighted-majority weights, which put no restriction on the sign of the losses) is the paper's , so wmWeights η z 0 is the uniform vector , and the sums run over .
import Mathlib import Definitions.Def_UnderstandingML_Online
namespace OnlineLearningOCO.NormalizedEG
open UnderstandingML
/-- Theorem 2.22, p. 153. Run normalized EG (box on p. 144; closed form (2.10), p. 143) with
parameter `η > 0` on linear losses `f_t(w) = ⟨w, z_t⟩` with `η z_t[i] ≥ −1` for all `t, i`. Then
for every `u` in the probability simplex of `ℝ^d`,
`∑_{t=1}^T ⟨w_t − u, z_t⟩ ≤ log(d)/η + η ∑_{t=1}^T ∑_i w_t[i] z_t[i]²`.
Rounds are 0-based: `wmWeights η z t` is the paper's `w_{t+1}` (`wmWeights η z 0` is uniform). -/
theorem theorem_2_22 {d : ℕ} (hd : 0 < d) (η : ℝ) (hη : 0 < η) (z : ℕ → Fin d → ℝ)
(hz : ∀ t i, -1 ≤ η * z t i) (u : Fin d → ℝ) (hu0 : ∀ i, 0 ≤ u i) (hu1 : ∑ i, u i = 1)
(T : ℕ) :
∑ t ∈ Finset.range T, ∑ i, (wmWeights η z t i - u i) * z t i ≤
Real.log d / η + η * ∑ t ∈ Finset.range T, ∑ i, wmWeights η z t i * z t i ^ 2 := by sorry
end OnlineLearningOCO.NormalizedEG
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.