Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 — regret of diagonal AdaGrad in terms of Σᵢ‖g_{1:T,i}‖₂

Proved
AdaGrad.Diag.theorem_5

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

adaptive-methodsonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Let X⊆Rd\mathcal X\subseteq\mathbb R^dX⊆Rd be closed and convex with 0∈X0\in\mathcal X0∈X, let f1,f2,…f_1,f_2,\dotsf1​,f2​,… and φ\varphiφ be convex functions Rd→R\mathbb R^d\to\mathbb RRd→R with φ\varphiφ minimized over X\mathcal XX at 000, let η>0\eta>0η>0 and T≥1T\ge1T≥1. Let xtx_txt​ be generated by ADAGRAD with diagonal matrices (Algorithm 1, Figure 1), started at x1=0x_1=0x1​=0, with subgradients gt∈∂ft(xt)g_t\in\partial f_t(x_t)gt​∈∂ft​(xt​) and ∥g1:T,i∥2=(∑t=1Tgt,i2)1/2\|g_{1:T,i}\|_2=\big(\sum_{t=1}^Tg_{t,i}^2\big)^{1/2}∥g1:T,i​∥2​=(∑t=1T​gt,i2​)1/2; write Rφ(T)=∑t=1T[ft(xt)+φ(xt)−ft(x∗)−φ(x∗)]R_\varphi(T)=\sum_{t=1}^T[f_t(x_t)+\varphi(x_t)-f_t(x^*)-\varphi(x^*)]Rφ​(T)=∑t=1T​[ft​(xt​)+φ(xt​)−ft​(x∗)−φ(x∗)].

  1. If the xtx_txt​ are generated with the primal-dual subgradient update (3) and a parameter δ≥0\delta\ge0δ≥0 with δ≥max⁡t≤T∥gt∥∞\delta\ge\max_{t\le T}\|g_t\|_\inftyδ≥maxt≤T​∥gt​∥∞​, then for every x∗∈Xx^*\in\mathcal Xx∗∈X
Rφ(T)≤δη∥x∗∥22+1η∥x∗∥∞2∑i=1d∥g1:T,i∥2+η∑i=1d∥g1:T,i∥2.R_\varphi(T)\le\frac\delta\eta\|x^*\|_2^2+\frac1\eta\|x^*\|_\infty^2\sum_{i=1}^d\|g_{1:T,i}\|_2+\eta\sum_{i=1}^d\|g_{1:T,i}\|_2 .Rφ​(T)≤ηδ​∥x∗∥22​+η1​∥x∗∥∞2​i=1∑d​∥g1:T,i​∥2​+ηi=1∑d​∥g1:T,i​∥2​.
  1. If the xtx_txt​ are generated with the composite mirror descent update (4) and δ=0\delta=0δ=0, then for every x∗∈Xx^*\in\mathcal Xx∗∈X
Rφ(T)≤12ηmax⁡t≤T∥x∗−xt∥∞2∑i=1d∥g1:T,i∥2+η∑i=1d∥g1:T,i∥2.R_\varphi(T)\le\frac1{2\eta}\max_{t\le T}\|x^*-x_t\|_\infty^2\sum_{i=1}^d\|g_{1:T,i}\|_2+\eta\sum_{i=1}^d\|g_{1:T,i}\|_2 .Rφ​(T)≤2η1​t≤Tmax​∥x∗−xt​∥∞2​i=1∑d​∥g1:T,i​∥2​+ηi=1∑d​∥g1:T,i​∥2​.

Both bounds replace the T\sqrt TT​-type dependence of non-adaptive subgradient methods by the per-coordinate quantity ∑i∥g1:T,i∥2\sum_i\|g_{1:T,i}\|_2∑i​∥g1:T,i​∥2​, which is much smaller when the gradients are sparse; this is the paper's main theorem for diagonal AdaGrad.

Formalization Note Two restrictions relative to the printed statement. (a) The mirror-descent part is stated for δ=0\delta=0δ=0: the proof's step Bψ1(x∗,x1)≤12∥x∗−x1∥∞2⟨1,s1⟩B_{\psi_1}(x^*,x_1)\le\frac12\|x^*-x_1\|_\infty^2\langle\mathbf 1,s_1\rangleBψ1​​(x∗,x1​)≤21​∥x∗−x1​∥∞2​⟨1,s1​⟩ (p. 2132) drops δ2∥x∗−x1∥22\frac\delta2\|x^*-x_1\|_2^22δ​∥x∗−x1​∥22​, and for large δ>0\delta>0δ>0 the printed bound is false (e.g. d=1d=1d=1, φ=0\varphi=0φ=0, X=R\mathcal X=\mathbb RX=R, ft(x)=xf_t(x)=xft​(x)=x, η=1\eta=1η=1, x∗=−1x^*=-1x∗=−1, δ=106\delta=10^6δ=106, T=100T=100T=100). δ=0\delta=0δ=0 is the case the proof covers and the one Corollaries 1 and 6 use. (b) φ\varphiφ is assumed minimized over X\mathcal XX at x1=0x_1=0x1​=0; the proofs of Propositions 2 and 3 use exactly this ("x1=argmin⁡x∈Xφ(x)x_1=\operatorname{argmin}_{x\in\mathcal X}\varphi(x)x1​=argminx∈X​φ(x)", p. 2153; "w.l.o.g. φ(x1)=0\varphi(x_1)=0φ(x1​)=0", p. 2129), and without it the bounds fail (e.g. φ(x)=−x\varphi(x)=-xφ(x)=−x on X=[−1,1]\mathcal X=[-1,1]X=[−1,1] with ft=0f_t=0ft​=0). The maximum over t≤Tt\le Tt≤T is over t∈{1,…,T}t\in\{1,\dots,T\}t∈{1,…,T}. Losses and regularizer are real-valued, and runs are given by argmin predicates; see the definition item.

Preamble
import Mathlib
import Definitions.Def_AdaGrad_Diag_Setup
Formal statement
namespace AdaGrad.Diag

/-- Duchi, Hazan, Singer, JMLR 12 (2011), Theorem 5, p. 2132: the regret of AdaGrad with diagonal
matrices (Figure 1, p. 2130). Let `X ⊆ ℝ^d` be closed and convex with `0 ∈ X`, the losses `f_t` and
the regularizer `ϕ` convex, with `ϕ` minimized over `X` at `x_1 = 0`, let `η > 0` and `T ≥ 1`.

1. For every `δ ≥ 0` and every run of Figure 1 with the primal-dual subgradient update (3) such
   that `δ ≥ max_{t≤T} ‖g_t‖∞`, and every `x* ∈ X`,
   `R_φ(T) ≤ (δ/η)‖x*‖₂² + (1/η)‖x*‖∞² ∑_i ‖g_{1:T,i}‖₂ + η ∑_i ‖g_{1:T,i}‖₂`.
2. For every run of Figure 1 with `δ = 0` and the composite mirror descent update (4), and every
   `x* ∈ X`,
   `R_φ(T) ≤ (1/(2η)) max_{t≤T} ‖x* − x_t‖∞² ∑_i ‖g_{1:T,i}‖₂ + η ∑_i ‖g_{1:T,i}‖₂`.

Here `‖g_{1:T,i}‖₂ = s g T i`, and `‖·‖` on `EuclideanSpace ℝ (Fin d)` is the Euclidean norm. -/
theorem theorem_5 {d : ℕ} (X : Set (EuclideanSpace ℝ (Fin d))) (hXc : Convex ℝ X)
    (hXcl : IsClosed X) (hX0 : (0 : EuclideanSpace ℝ (Fin d)) ∈ X)
    (ϕ : EuclideanSpace ℝ (Fin d) → ℝ) (hϕ : ConvexOn ℝ Set.univ ϕ)
    (hϕ0 : ∀ y ∈ X, ϕ 0 ≤ ϕ y)
    (f : ℕ → EuclideanSpace ℝ (Fin d) → ℝ) (hf : ∀ t, ConvexOn ℝ Set.univ (f t))
    (η : ℝ) (hη : 0 < η) (T : ℕ) (hT : 1 ≤ T) :
    (∀ (δ : ℝ) (x g : ℕ → EuclideanSpace ℝ (Fin d)), 0 ≤ δ →
        IsPrimalDualRun η δ X ϕ f x g →
        (∀ t ∈ Finset.Icc 1 T, supNorm (g t) ≤ δ) →
        ∀ xstar ∈ X,
          regret f ϕ x xstar T
            ≤ δ / η * ‖xstar‖ ^ 2 + 1 / η * supNorm xstar ^ 2 * ∑ i, s g T i
              + η * ∑ i, s g T i) ∧
    (∀ (x g : ℕ → EuclideanSpace ℝ (Fin d)),
        IsMirrorDescentRun η 0 X ϕ f x g →
        ∀ xstar ∈ X,
          regret f ϕ x xstar T
            ≤ 1 / (2 * η) * (Finset.Icc 1 T).sup' (Finset.nonempty_Icc.mpr hT)
                  (fun t => supNorm (xstar - x t) ^ 2) * ∑ i, s g T i
              + η * ∑ i, s g T i) := by sorry

end AdaGrad.Diag
Source
Duchi, Hazan, Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011), p. 2132, Theorem 5 (Algorithm 1 = Figure 1, p. 2130)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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