(13) — Σₜ‖gₜ‖²_{ψₜ*} ≤ 2 Σᵢ‖g_{1:T,i}‖₂ for every δ ≥ 0
ProvedAdaGrad.Diag.eq_13adaptive-methodsonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any sequence, , and . For AdaGrad's proximal functions the squared dual norm is , and for every
This bounds the gradient term of the composite mirror descent regret bound (Proposition 3) for diagonal AdaGrad.
Formalization Note The dual norm uses Lean's division with ; a zero weight occurs only when and , in which case , matching the paper's remark that "if then ".
Preamble
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
Formal statement
namespace AdaGrad.Diag
/-- Duchi, Hazan, Singer, JMLR 12 (2011), §3, inequality (13), p. 2131: for any `δ ≥ 0`, the
squared dual norms of the subgradients for AdaGrad's proximal functions
`ψ_t(x) = ½⟨x, (δI + diag(s_t)) x⟩` satisfy
`∑_{t=1}^T ‖g_t‖²_{ψ_t*} = ∑_{t=1}^T ∑_i g_{t,i}² / (δ + s_{t,i}) ≤ 2 ∑_{i=1}^d ‖g_{1:T,i}‖₂`. -/
theorem eq_13 {d : ℕ} (g : ℕ → EuclideanSpace ℝ (Fin d)) (δ : ℝ) (hδ : 0 ≤ δ) (T : ℕ) :
∑ t ∈ Finset.Icc 1 T, dualNormSq (adaWeights δ g t) (g t) ≤ 2 * ∑ 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. 2131, §3, (13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.