Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Difference of consecutive Bregman divergences of diagonal AdaGrad (p. 2131)

Proved
AdaGradDHS.Diag.bregman_difference_bound

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

adagradconvex-optimizationonline-learningregret-bounds

Let δ∈R\delta \in \mathbb{R}δ∈R, g1,g2,⋯∈Rdg_1, g_2, \dots \in \mathbb{R}^dg1​,g2​,⋯∈Rd, st,i=∥g1:t,i∥2s_{t,i} = \|g_{1:t,i}\|_2st,i​=∥g1:t,i​∥2​ and ψt(x)=12∑i(δ+st,i)xi2\psi_t(x) = \tfrac12\sum_i (\delta + s_{t,i})x_i^2ψt​(x)=21​∑i​(δ+st,i​)xi2​. For every ttt and all x∗,y∈Rdx^*, y \in \mathbb{R}^dx∗,y∈Rd,

Bψt+1(x∗,y)−Bψt(x∗,y)=12⟨x∗−y,diag⁡(st+1−st)(x∗−y)⟩≤12∥x∗−y∥∞2 ∥st+1−st∥1.B_{\psi_{t+1}}(x^*, y) - B_{\psi_t}(x^*, y) = \tfrac12 \big\langle x^* - y, \operatorname{diag}(s_{t+1} - s_t)(x^* - y)\big\rangle \le \tfrac12 \|x^* - y\|_\infty^2 \, \|s_{t+1} - s_t\|_1 .Bψt+1​​(x∗,y)−Bψt​​(x∗,y)=21​⟨x∗−y,diag(st+1​−st​)(x∗−y)⟩≤21​∥x∗−y∥∞2​∥st+1​−st​∥1​.

In the paper y=xt+1y = x_{t+1}y=xt+1​; summing these differences over ttt gives (14), which controls the middle term of the mirror-descent bound (11).

Formalization Note The quadratic form is written ∑i(st+1,i−st,i)(xi∗−yi)2\sum_i (s_{t+1,i} - s_{t,i})(x^*_i - y_i)^2∑i​(st+1,i​−st,i​)(xi∗​−yi​)2 and ∥st+1−st∥1\|s_{t+1} - s_t\|_1∥st+1​−st​∥1​ as ∑i∣st+1,i−st,i∣\sum_i |s_{t+1,i} - s_{t,i}|∑i​∣st+1,i​−st,i​∣; max⁡i(xi∗−yi)2=∥x∗−y∥∞2\max_i (x^*_i - y_i)^2 = \|x^* - y\|_\infty^2maxi​(xi∗​−yi​)2=∥x∗−y∥∞2​.

Differences from the source:

  • generalization: evaluated at y = x_{t+1} → any y ∈ ℝ^d; reason: the identity and the bound are algebraic in y
  • reading: ψ_t(x) = ⟨x, H_t x⟩ (p. 2123, displays pp. 2131–2132) vs ψ_t(x) = ½⟨x, H_t x⟩ (Figure 1) → ψ_t = adagradPsi δ g t = ½ Σ_i (δ + s_{t,i}) x_i² (Figure 1); reason: Theorem 5 is about the sequence defined by Algorithm 1 (Figure 1); under this convention the ½ and 1/(2η) of the displays and of Theorem 5 are the paper's
  • encoding: ½⟨x∗ − y, diag(s_{t+1} − s_t)(x∗ − y)⟩, max_i (x∗i − y_i)², ‖s{t+1} − s_t‖₁ → 1/2 * ∑ i, (accNorm g (t+1) i − accNorm g t i) * (xstar i − y i)^2, supNorm (xstar − y)^2, ∑ i, |accNorm g (t+1) i − accNorm g t i|; reason: same quantities
Preamble
import Mathlib
import Definitions.Def_AdaGradDHS_Diag_bregman
import Definitions.Def_AdaGradDHS_Diag_accNorm
import Definitions.Def_AdaGradDHS_Diag_adagradPsi
import Definitions.Def_AdaGradDHS_Diag_supNorm
Formal statement
namespace AdaGradDHS.Diag

/-- **Difference of consecutive Bregman divergences of diagonal AdaGrad.**
Duchi, Hazan, Singer, *Adaptive Subgradient Methods for Online Learning and Stochastic
Optimization*, JMLR 12 (2011), §3, p. 2131 (unnumbered display): "Bψt+1(x∗, xt+1) − Bψt(x∗, xt+1) = ½⟨x∗ − xt+1,
diag(st+1 − st)(x∗ − xt+1)⟩ ≤ ½ maxi (x∗i − xt+1,i)² ‖st+1 − st‖1."

For every `δ`, every sequence `g`, every `t` and all `x*, y ∈ ℝ^d`, with `ψ_t = adagradPsi δ g t`
and `s_{t,i} = accNorm g t i`:
`B_{ψ_{t+1}}(x*, y) − B_{ψ_t}(x*, y) = ½ Σ_i (s_{t+1,i} − s_{t,i})(x*_i − y_i)²`
and this is at most `½ ‖x* − y‖∞² Σ_i |s_{t+1,i} − s_{t,i}|`.

**Formalization Note.** The paper evaluates at `y = x_{t+1}`; the identity and the bound hold for
every `y`. `ψ_t` is Figure 1's `½⟨x, H_t x⟩`, under which the display holds as printed.
`‖s_{t+1} − s_t‖₁` is `Σ_i |s_{t+1,i} − s_{t,i}|` and `max_i (x*_i − y_i)²` is `‖x* − y‖∞²`. -/
theorem bregman_difference_bound {d : ℕ} (δ : ℝ) (g : ℕ → EuclideanSpace ℝ (Fin d)) (t : ℕ) (xstar y : EuclideanSpace ℝ (Fin d)) :
    bregman (adagradPsi δ g (t + 1)) xstar y - bregman (adagradPsi δ g t) xstar y =
        1 / 2 * ∑ i, (accNorm g (t + 1) i - accNorm g t i) * (xstar i - y i) ^ 2 ∧
      1 / 2 * ∑ i, (accNorm g (t + 1) i - accNorm g t i) * (xstar i - y i) ^ 2 ≤
        1 / 2 * supNorm (xstar - y) ^ 2 * ∑ i, |accNorm g (t + 1) i - accNorm g t i| := by sorry

end AdaGradDHS.Diag
Source
Duchi, Hazan, Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011), §3, p. 2131 (unnumbered display before (14))

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