Proposition 3 — regret of composite mirror descent with time-varying quadratic proximal functions, (11)
ProvedAdaGrad.Full.proposition_3mirror-descentonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let be closed and convex, and convex, , , and let be generated by the composite mirror descent update (4) with , where for the matrix is positive semidefinite and lies in its range. Assume minimizes over . Then for every ,
with .
This reduces the regret of every adaptive mirror-descent method to the growth of its proximal terms and a sum of dual norms.
Formalization Note Specialised to quadratic proximal functions, with the range condition as in Lemma 16. The paper's "assume w.l.o.g. that " (with , p. 2123) is stated as: minimizes over . No monotonicity of is assumed (the proof does not use it). The number of rounds is (at nothing would constrain in the term ).
Preamble
import Mathlib import Definitions.Def_AdaGrad_Full_Algorithm2 open scoped MatrixOrder InnerProductSpace
Formal statement
namespace AdaGrad.Full
/-- Proposition 3, inequality (11) (p. 2129), specialised to quadratic proximal functions
`ψ_t(x) = ½⟨x, H_t x⟩` with `H_t` positive semidefinite and `g_t` in the range of `H_t`, over `T ≥ 1` rounds. -/
theorem proposition_3 {d : ℕ} (η : ℝ) (hη : 0 < η) (X : Set (EuclideanSpace ℝ (Fin d)))
(hXc : Convex ℝ X) (hXcl : IsClosed X)
(f : ℕ → EuclideanSpace ℝ (Fin d) → ℝ) (hf : ∀ t, ConvexOn ℝ Set.univ (f t))
(ϕ : EuclideanSpace ℝ (Fin d) → ℝ) (hϕ : ConvexOn ℝ Set.univ ϕ)
(H : ℕ → Matrix (Fin d) (Fin d) ℝ) (x g : ℕ → EuclideanSpace ℝ (Fin d)) (T : ℕ) (hT : 1 ≤ T)
(hH : ∀ t ∈ Finset.Icc 1 T, (H t).PosSemidef)
(hrange : ∀ t ∈ Finset.Icc 1 T, g t ∈ LinearMap.range (Matrix.toEuclideanLin (H t)))
(hrun : IsQuadMirrorDescentRun η X ϕ f H x g T)
(hx1 : x 1 ∈ X) (hϕx1 : ∀ y ∈ X, ϕ (x 1) ≤ ϕ y)
(xstar : EuclideanSpace ℝ (Fin d)) (hstar : xstar ∈ X) :
AdaGrad.Diag.regret f ϕ x xstar T ≤
1 / η * bregman (H 1) xstar (x 1)
+ 1 / η * ∑ t ∈ Finset.Ico 1 T,
(bregman (H (t + 1)) xstar (x (t + 1)) - bregman (H t) xstar (x (t + 1)))
+ η / 2 * ∑ t ∈ Finset.Icc 1 T, dualNormSq (H t) (g t) := by sorry
end AdaGrad.Full
Source
Duchi, Hazan, Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 12 (2011), p. 2129, Proposition 3, (11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.