Inequality (16) — telescoping the trace increments against max_{t≤T}‖x*−x_t‖₂²
ProvedAdaGrad.Full.eq_16adagradmatrix-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be arbitrary sequences in , , , and . Then
Together with the previous display it bounds the divergence terms of Proposition 3 for full-matrix ADAGRAD.
Preamble
import Mathlib import Definitions.Def_AdaGrad_Full_Algorithm2 open scoped MatrixOrder InnerProductSpace
Formal statement
namespace AdaGrad.Full
/-- Inequality (16) (p. 2134):
`∑_{t=1}^{T−1} ‖x* − x_{t+1}‖₂² (tr G_{t+1}^{1/2} − tr G_t^{1/2})
≤ max_{t≤T} ‖x* − x_t‖₂² tr G_T^{1/2} − ‖x* − x_1‖₂² tr G_1^{1/2}`. -/
theorem eq_16 {d : ℕ} (g x : ℕ → EuclideanSpace ℝ (Fin d)) (xstar : EuclideanSpace ℝ (Fin d))
(T : ℕ) (hT : 1 ≤ T) :
∑ t ∈ Finset.Ico 1 T, ‖xstar - x (t + 1)‖ ^ 2 * ((S g (t + 1)).trace - (S g t).trace) ≤
(Finset.Icc 1 T).sup' (Finset.nonempty_Icc.mpr hT) (fun t => ‖xstar - x t‖ ^ 2)
* (S g T).trace
- ‖xstar - x 1‖ ^ 2 * (S g 1).trace := by sorry
end AdaGrad.Full
Source
Duchi, Hazan, Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011), p. 2134, (16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.