§4, proof of Theorem 7 — the increment of the Bregman divergences is at most ½‖x*−y‖₂² tr(G_{t+1}^{1/2}−G_t^{1/2})
ProvedAdaGrad.Full.display_bregman_incrementadagradmatrix-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , and . For every and all ,
Applied with it bounds the middle sum of Proposition 3 for full-matrix ADAGRAD.
Formalization Note The page passes through ; that intermediate quantity is not stated, only the equality and the outer inequality.
Preamble
import Mathlib import Definitions.Def_AdaGrad_Full_Algorithm2 open scoped MatrixOrder InnerProductSpace
Formal statement
namespace AdaGrad.Full
/-- §4, proof of Theorem 7, first display (p. 2134): for ADAGRAD's proximal matrices
`H_t = δI + G_t^{1/2}`, `B_{ψ_{t+1}}(x*, y) − B_{ψ_t}(x*, y) = ½⟨x* − y, (G_{t+1}^{1/2} − G_t^{1/2})(x* − y)⟩`
and this is at most `½‖x* − y‖₂² tr(G_{t+1}^{1/2} − G_t^{1/2})`. -/
theorem display_bregman_increment {d : ℕ} (δ : ℝ) (g : ℕ → EuclideanSpace ℝ (Fin d)) (t : ℕ)
(xstar y : EuclideanSpace ℝ (Fin d)) :
bregman (H δ g (t + 1)) xstar y - bregman (H δ g t) xstar y
= 1 / 2 * mInner (S g (t + 1) - S g t) (xstar - y) (xstar - y) ∧
1 / 2 * mInner (S g (t + 1) - S g t) (xstar - y) (xstar - y)
≤ 1 / 2 * ‖xstar - y‖ ^ 2 * (S g (t + 1) - S g t).trace := by sorry
end AdaGrad.Full
Source
Duchi, Hazan, Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011), p. 2134, §4, proof of Theorem 7, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.