Lemma 4 — Σₜ⟨gₜ, diag(sₜ)⁻¹gₜ⟩ ≤ 2 Σᵢ‖g_{1:T,i}‖₂
ProvedAdaGrad.Diag.lemma_4adaptive-methodsonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any sequence of (sub)gradients, and let as in Algorithm 1. Then for every ,
Here , and is the pseudo-inverse: if then and the term is .
The lemma is the source of the per-coordinate quantity in AdaGrad's regret bound.
Formalization Note The pseudo-inverse is Lean's division with . The lemma is stated for an arbitrary sequence : it does not depend on how the subgradients were generated.
Preamble
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
Formal statement
namespace AdaGrad.Diag
/-- Duchi, Hazan, Singer, JMLR 12 (2011), Lemma 4, p. 2131: for any sequence of (sub)gradients
`g_1, g_2, … ∈ ℝ^d` and `s_{t,i} = ‖g_{1:t,i}‖₂`,
`∑_{t=1}^T ⟨g_t, diag(s_t)⁻¹ g_t⟩ ≤ 2 ∑_{i=1}^d ‖g_{1:T,i}‖₂`.
`⟨g_t, diag(s_t)⁻¹ g_t⟩ = ∑_i g_{t,i}² / s_{t,i}` is `dualNormSq (s g t) (g t)`; `diag(s_t)⁻¹` is the
pseudo-inverse, i.e. `0/0 = 0` (if `s_{t,i} = 0` then `g_{t,i} = 0`). -/
theorem lemma_4 {d : ℕ} (g : ℕ → EuclideanSpace ℝ (Fin d)) (T : ℕ) :
∑ t ∈ Finset.Icc 1 T, dualNormSq (s 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, Lemma 4 (proof p. 2149, Appendix C)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.