Theorem 5 — regret of diagonal AdaGrad in terms of Σᵢ‖g_{1:T,i}‖₂
ProvedAdaGrad.Diag.theorem_5Let be closed and convex with , let and be convex functions with minimized over at , let and . Let be generated by ADAGRAD with diagonal matrices (Algorithm 1, Figure 1), started at , with subgradients and ; write .
- If the are generated with the primal-dual subgradient update (3) and a parameter with , then for every
- If the are generated with the composite mirror descent update (4) and , then for every
Both bounds replace the -type dependence of non-adaptive subgradient methods by the per-coordinate quantity , 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 : the proof's step (p. 2132) drops , and for large the printed bound is false (e.g. , , , , , , , ). is the case the proof covers and the one Corollaries 1 and 6 use. (b) is assumed minimized over at ; the proofs of Propositions 2 and 3 use exactly this ("", p. 2153; "w.l.o.g. ", p. 2129), and without it the bounds fail (e.g. on with ). The maximum over is over . Losses and regularizer are real-valued, and runs are given by argmin predicates; see the definition item.
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.