Proposition 2 — regret of primal-dual subgradient (dual averaging) with time-varying proximal functions, (10)
ProvedAdaGrad.Diag.proposition_2Let , let be closed and convex with , and let and every be convex functions , with minimized over at . For let have positive entries, non-decreasing in (), and let , so that , with squared dual norm . Let and let be a run of the primal-dual subgradient update (3): is a subgradient of at and minimizes
over , for every . Then for every and every ,
This is the regret bound of dual averaging when the proximal function may grow from round to round; note that round 's subgradient is measured in the dual norm of the previous round's proximal function.
Formalization Note Specialised to diagonal quadratic proximal functions; the standing assumptions of §2 (p. 2129), and 1-strong convexity of with respect to , are the monotonicity of the weights and the quadratic form. The weights are taken strictly positive, so every dual norm is finite. The proof's "recalling that " (p. 2153) and the identity it uses are made explicit, with Figure 1's initialization, as and for .
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
namespace AdaGrad.Diag
/-- Duchi, Hazan, Singer, JMLR 12 (2011), Proposition 2, (10), p. 2129, specialised to diagonal
quadratic proximal functions `ψ_t(y) = ½ ∑_i h_{t,i} y_i²` (`t = 0, 1, 2, …`) with positive weights
that are non-decreasing in `t` (so `ψ_{t+1} ≥ ψ_t`, the standing assumption of §2). Let the `f_t`
and `ϕ` be convex, `X` closed and convex with `0 ∈ X`, let `x_1 = 0` minimize `ϕ` over `X`, and let
`x_1, x_2, …` be a run of the primal-dual subgradient update (3) with subgradients `g_t` of `f_t` at
`x_t`. Then for every `T` and every `x* ∈ X`,
`∑_{t=1}^T [f_t(x_t) + ϕ(x_t) − f_t(x*) − ϕ(x*)] ≤ (1/η) ψ_T(x*) + (η/2) ∑_{t=1}^T ‖g_t‖²_{ψ_{t−1}*}`,
with `‖g‖²_{ψ*} = ∑_i g_i² / h_i`. -/
theorem proposition_2 {d : ℕ} (η : ℝ) (hη : 0 < η) (X : Set (EuclideanSpace ℝ (Fin d)))
(hXc : Convex ℝ X) (hXcl : IsClosed X) (hX0 : (0 : EuclideanSpace ℝ (Fin d)) ∈ X)
(ϕ : EuclideanSpace ℝ (Fin d) → ℝ) (hϕ : ConvexOn ℝ Set.univ ϕ)
(hϕ0 : ∀ y ∈ X, ϕ 0 ≤ ϕ y)
(f : ℕ → EuclideanSpace ℝ (Fin d) → ℝ) (hf : ∀ t, ConvexOn ℝ Set.univ (f t))
(h : ℕ → Fin d → ℝ) (hpos : ∀ t i, 0 < h t i) (hmono : ∀ t i, h t i ≤ h (t + 1) i)
(x g : ℕ → EuclideanSpace ℝ (Fin d)) (hx1 : x 1 = 0)
(hrun : IsDualAveragingRun η X ϕ f h x g)
(T : ℕ) (xstar : EuclideanSpace ℝ (Fin d)) (hxstar : xstar ∈ X) :
regret f ϕ x xstar T
≤ 1 / η * prox (h T) xstar
+ η / 2 * ∑ t ∈ Finset.Icc 1 T, dualNormSq (h (t - 1)) (g t) := by sorry
end AdaGrad.Diag
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.