(14) — the Bregman drift of diagonal AdaGrad is at most ½ maxₜ‖x* − xₜ‖∞² Σᵢ‖g_{1:T,i}‖₂ − ½‖x* − x₁‖∞²⟨s₁, 1⟩
ProvedAdaGrad.Diag.eq_14adaptive-methodsonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be arbitrary, , , and the Bregman divergence of AdaGrad's . For every ,
This bounds the Bregman-divergence drift term of the composite mirror descent regret bound (Proposition 3) for diagonal AdaGrad.
Formalization Note Both inequalities are stated, as a conjunction. cancels from the left-hand side and is arbitrary. The maximum is over (Finset.sup', well defined because ). .
Preamble
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
Formal statement
namespace AdaGrad.Diag
/-- Duchi, Hazan, Singer, JMLR 12 (2011), §3, inequality (14), p. 2131: for AdaGrad's diagonal
proximal functions `ψ_t(x) = ½⟨x, (δI + diag(s_t)) x⟩`, any points `x_1, x_2, … , x* ∈ ℝ^d`,
any subgradients `g_t` and any `T ≥ 1`,
`∑_{t=1}^{T−1} [B_{ψ_{t+1}}(x*, x_{t+1}) − B_{ψ_t}(x*, x_{t+1})]
≤ ½ ∑_{t=1}^{T−1} ‖x* − x_{t+1}‖∞² ⟨s_{t+1} − s_t, 1⟩
≤ ½ max_{t≤T} ‖x* − x_t‖∞² ∑_{i=1}^d ‖g_{1:T,i}‖₂ − ½ ‖x* − x_1‖∞² ⟨s_1, 1⟩`.
The maximum is over `t ∈ {1, …, T}`. -/
theorem eq_14 {d : ℕ} (δ : ℝ) (x g : ℕ → EuclideanSpace ℝ (Fin d))
(xstar : EuclideanSpace ℝ (Fin d)) (T : ℕ) (hT : 1 ≤ T) :
∑ t ∈ Finset.Ico 1 T,
(bregman (adaWeights δ g (t + 1)) xstar (x (t + 1))
- bregman (adaWeights δ g t) xstar (x (t + 1)))
≤ (1 / 2) * ∑ t ∈ Finset.Ico 1 T,
supNorm (xstar - x (t + 1)) ^ 2 * ∑ i, (s g (t + 1) i - s g t i) ∧
(1 / 2) * ∑ t ∈ Finset.Ico 1 T,
supNorm (xstar - x (t + 1)) ^ 2 * ∑ i, (s g (t + 1) i - s g t i)
≤ (1 / 2) * (Finset.Icc 1 T).sup' (Finset.nonempty_Icc.mpr hT)
(fun t => supNorm (xstar - x t) ^ 2) * ∑ i, s g T i
- (1 / 2) * supNorm (xstar - x 1) ^ 2 * ∑ i, s g 1 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, (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.