Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(2.16)–(2.18) — the Bregman term of the log-sum-exp conjugate along normalized EG

Proved
OnlineLearningOCO.NormalizedEG.eq_2_16_2_18

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

exponentiated-gradientonline-convex-optimizationonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Let d≥1d \ge 1d≥1, η>0\eta > 0η>0, and let z1,z2,⋯∈Rdz_1, z_2, \dots \in \mathbb R^dz1​,z2​,⋯∈Rd be loss vectors. Let wtw_twt​ be the normalized-EG weights,

wt[i]=e−ηz1:t−1[i]∑je−ηz1:t−1[j],w_t[i] = \frac{e^{-\eta z_{1:t-1}[i]}}{\sum_j e^{-\eta z_{1:t-1}[j]}},wt​[i]=∑j​e−ηz1:t−1​[j]e−ηz1:t−1​[i]​,

and let R⋆(θ)=1ηlog⁡(∑ieηθ[i])R^\star(\theta) = \frac1\eta \log\big(\sum_i e^{\eta\theta[i]}\big)R⋆(θ)=η1​log(∑i​eηθ[i]). Then:

  1. R⋆R^\starR⋆ is differentiable on Rd\mathbb R^dRd with gradient ∇R⋆(θ)[i]=eηθ[i]/∑jeηθ[j]\nabla R^\star(\theta)[i] = e^{\eta\theta[i]} / \sum_j e^{\eta\theta[j]}∇R⋆(θ)[i]=eηθ[i]/∑j​eηθ[j];
  2. wt=∇R⋆(−z1:t−1)w_t = \nabla R^\star(-z_{1:t-1})wt​=∇R⋆(−z1:t−1​);
  3. for every round ttt,
DR⋆(−z1:t ∥ −z1:t−1)=R⋆(−z1:t)−R⋆(−z1:t−1)+⟨wt,zt⟩(2.16)=1ηlog⁡(∑ie−ηz1:t[i]∑ie−ηz1:t−1[i])+⟨wt,zt⟩(2.17)=1ηlog⁡(∑iwt[i] e−ηzt[i])+⟨wt,zt⟩.(2.18)\begin{aligned} D_{R^\star}(-z_{1:t}\,\|\,-z_{1:t-1}) &= R^\star(-z_{1:t}) - R^\star(-z_{1:t-1}) + \langle w_t, z_t\rangle && (2.16)\\ &= \frac1\eta \log\left(\frac{\sum_i e^{-\eta z_{1:t}[i]}}{\sum_i e^{-\eta z_{1:t-1}[i]}}\right) + \langle w_t, z_t\rangle && (2.17)\\ &= \frac1\eta \log\Big(\sum_i w_t[i]\, e^{-\eta z_t[i]}\Big) + \langle w_t, z_t\rangle. && (2.18)\end{aligned}DR⋆​(−z1:t​∥−z1:t−1​)​=R⋆(−z1:t​)−R⋆(−z1:t−1​)+⟨wt​,zt​⟩=η1​log(∑i​e−ηz1:t−1​[i]∑i​e−ηz1:t​[i]​)+⟨wt​,zt​⟩=η1​log(i∑​wt​[i]e−ηzt​[i])+⟨wt​,zt​⟩.​​(2.16)(2.17)(2.18)​

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 000: wmWeights η z t (the published normalized-EG / weighted-majority weights) is the paper's wt+1w_{t+1}wt+1​, and cumSum z t =∑s<tzs= \sum_{s<t} z_s=∑s<t​zs​ is the paper's z1:tz_{1:t}z1:t​ for the paper's 1-based indexing of zzz. The gradient is stated as a Fréchet derivative, the linear map v↦∑i∇R⋆(θ)[i] v[i]v \mapsto \sum_i \nabla R^\star(\theta)[i]\, v[i]v↦∑i​∇R⋆(θ)[i]v[i], because Fin d → ℝ is not an inner product space in Mathlib. No restriction on the sign of ztz_tzt​ 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
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me