(2.16)–(2.18) — the Bregman term of the log-sum-exp conjugate along normalized EG
ProvedOnlineLearningOCO.NormalizedEG.eq_2_16_2_18exponentiated-gradientonline-convex-optimizationonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let , , and let be loss vectors. Let be the normalized-EG weights,
and let . Then:
- is differentiable on with gradient ;
- ;
- for every round ,
These identities turn the Bregman term of Lemma 2.20, for the entropic regularizer, into the logarithm of a weighted average of exponentials, which is then bounded in the next step of the proof of Theorem 2.22.
Formalization Note Rounds are numbered from : wmWeights η z t (the published normalized-EG / weighted-majority weights) is the paper's , and cumSum z t is the paper's for the paper's 1-based indexing of . The gradient is stated as a Fréchet derivative, the linear map , because Fin d → ℝ is not an inner product space in Mathlib. No restriction on the sign of is needed.
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, (2.16)–(2.18), p. 153. For `R⋆(θ) = (1/η) log ∑_i e^{η θ[i]}`
(the conjugate of the normalized entropy, Table 2.1): `R⋆` is differentiable with gradient the
softmax `softmaxEG η`; the normalized-EG weights are `w_t = ∇R⋆(−z_{1:t−1})`; and the Bregman
divergence of `R⋆` along the normalized-EG run satisfies
`D_{R⋆}(−z_{1:t} ‖ −z_{1:t−1}) = R⋆(−z_{1:t}) − R⋆(−z_{1:t−1}) + ⟨w_t, z_t⟩` (2.16)
`= (1/η) log (∑_i e^{−η z_{1:t}[i]} / ∑_i e^{−η z_{1:t−1}[i]}) + ⟨w_t, z_t⟩` (2.17)
`= (1/η) log (∑_i w_t[i] e^{−η z_t[i]}) + ⟨w_t, z_t⟩`. (2.18)
Rounds are 0-based: `wmWeights η z t` is the paper's `w_{t+1}` and `cumSum z t = z_{1:t}` in
the paper's 1-based indexing of `z`. -/
theorem eq_2_16_2_18 {d : ℕ} (hd : 0 < d) (η : ℝ) (hη : 0 < η) (z : ℕ → Fin d → ℝ) (t : ℕ) :
(∀ θ : Fin d → ℝ, HasFDerivAt (logSumExpConj η)
(∑ i, softmaxEG η θ i • ContinuousLinearMap.proj (R := ℝ) (φ := fun _ : Fin d ↦ ℝ) i) θ) ∧
softmaxEG η (-(cumSum z t)) = wmWeights η z t ∧
bregmanLSE η (-(cumSum z (t + 1))) (-(cumSum z t)) =
logSumExpConj η (-(cumSum z (t + 1))) - logSumExpConj η (-(cumSum z t)) +
∑ i, wmWeights η z t i * z t i ∧
logSumExpConj η (-(cumSum z (t + 1))) - logSumExpConj η (-(cumSum z t)) +
∑ i, wmWeights η z t i * z t i =
(1 / η) * Real.log ((∑ i, Real.exp (-η * cumSum z (t + 1) i)) /
∑ i, Real.exp (-η * cumSum z t i)) +
∑ i, wmWeights η z t i * z t i ∧
(1 / η) * Real.log ((∑ i, Real.exp (-η * cumSum z (t + 1) i)) /
∑ i, Real.exp (-η * cumSum z t i)) +
∑ i, wmWeights η z t i * z t i =
(1 / η) * Real.log (∑ i, wmWeights η z t i * Real.exp (-η * z t i)) +
∑ i, wmWeights η z t i * z t i := by sorry
end OnlineLearningOCO.NormalizedEG
Source
Shalev-Shwartz, Online Learning and Online Convex Optimization, Found. Trends Mach. Learn. 4(2) (2011) 107–194, p. 153, §2.8, proof of Theorem 2.22, (2.16)–(2.18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.