Proposition 3 — regret of composite mirror descent with time-varying proximal functions, (11)
ProvedAdaGrad.Diag.proposition_3Let , let be closed and convex, and let and every be convex functions . For each round let have nonnegative entries, with proximal function , Bregman divergence and squared dual norm . Let be a run of the composite mirror descent update (4): is a subgradient of at , with whenever , and minimizes over . Assume minimizes over . Then for every and every ,
This reduces the regret of composite mirror descent with adaptive proximal functions to two terms: the drift of the Bregman divergences and the dual norms of the subgradients.
Formalization Note Specialised to diagonal quadratic proximal functions; their strong convexity with respect to is implied by the quadratic form, and no monotonicity of is needed. The paper's "assume w.l.o.g. that " is used in its proof as ; here it is the hypothesis that minimizes over (without it the inequality fails). The condition "" makes Lean's agree with the paper's dual norm.
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
namespace AdaGrad.Diag
/-- Duchi, Hazan, Singer, JMLR 12 (2011), Proposition 3, (11), p. 2129, specialised to diagonal
quadratic proximal functions `ψ_t(y) = ½ ∑_i h_{t,i} y_i²` with weights `h_{t,i} ≥ 0`. Let the
`f_t` and `ϕ` be convex, `X` convex, and let `x_1, x_2, …` be a run of the composite mirror descent
update (4) with subgradients `g_t` of `f_t` at `x_t`, where `h_{t,i} = 0` forces `g_{t,i} = 0`.
Assume `x_1 ∈ X` minimizes `ϕ` over `X` (the paper's "w.l.o.g. `ϕ(x_1) = 0`", see the
Formalization Note). Then for every `T` and every `x* ∈ X`,
`∑_{t=1}^T [f_t(x_t) + ϕ(x_t) − f_t(x*) − ϕ(x*)]
≤ (1/η) B_{ψ_1}(x*, x_1) + (1/η) ∑_{t=1}^{T−1} [B_{ψ_{t+1}}(x*, x_{t+1}) − B_{ψ_t}(x*, x_{t+1})]
+ (η/2) ∑_{t=1}^T ‖g_t‖²_{ψ_t*}`. -/
theorem proposition_3 {d : ℕ} (η : ℝ) (hη : 0 < η) (X : Set (EuclideanSpace ℝ (Fin d)))
(hXc : Convex ℝ X) (hXcl : IsClosed X)
(ϕ : EuclideanSpace ℝ (Fin d) → ℝ) (hϕ : ConvexOn ℝ Set.univ ϕ)
(f : ℕ → EuclideanSpace ℝ (Fin d) → ℝ) (hf : ∀ t, ConvexOn ℝ Set.univ (f t))
(h : ℕ → Fin d → ℝ) (x g : ℕ → EuclideanSpace ℝ (Fin d))
(hh : ∀ t, 1 ≤ t → ∀ i, 0 ≤ h t i)
(hhg : ∀ t, 1 ≤ t → ∀ i, h t i = 0 → g t i = 0)
(hrun : IsCompositeMDRun η X ϕ f h x g)
(hx1 : x 1 ∈ X) (hϕx1 : ∀ y ∈ X, ϕ (x 1) ≤ ϕ y)
(T : ℕ) (xstar : EuclideanSpace ℝ (Fin d)) (hxstar : xstar ∈ X) :
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.Diag
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.