Lemma 16 — one step of composite mirror descent (diagonal quadratic proximal functions)
ProvedAdaGrad.Diag.lemma_16Let , let be convex, and let and be convex functions . Let have nonnegative entries and write , so that and . Let be a subgradient of at with whenever , and let minimize over (one step of the composite mirror descent update (4)). Then for every ,
This is the one-step inequality that, summed over rounds, gives the regret bound of composite mirror descent with time-varying proximal functions (Proposition 3).
Formalization Note Specialised to diagonal quadratic proximal functions ; the paper's strong convexity of with respect to is implied by the quadratic form. The comparator is required to lie in : the page says "for any ", but its proof applies the optimality condition of , valid for points of , at . The condition "" makes Lean's agree with the paper's dual norm, which is otherwise.
import Mathlib import Definitions.Def_AdaGrad_Diag_Setup
namespace AdaGrad.Diag
open ShorNonsmooth.AlmostDiff
/-- Duchi, Hazan, Singer, JMLR 12 (2011), Lemma 16, p. 2154, specialised to diagonal quadratic
proximal functions `ψ_t(y) = ½ ∑_i h_i y_i²` with weights `h_i ≥ 0`: one step of the composite
mirror descent update (4). Let `g_t` be a subgradient of the convex `f_t` at `x_t`, and let
`x_{t+1} ∈ X` minimize `η⟨g_t, y⟩ + ηϕ(y) + B_{ψ_t}(y, x_t)` over the convex set `X`, where `ϕ` is
convex. If `h_i = 0` forces `g_{t,i} = 0`, then for every `x* ∈ X`,
`η(f_t(x_t) − f_t(x*)) + η(ϕ(x_{t+1}) − ϕ(x*))
≤ B_{ψ_t}(x*, x_t) − B_{ψ_t}(x*, x_{t+1}) + (η²/2) ‖g_t‖²_{ψ_t*}`,
with `‖g‖²_{ψ_t*} = ∑_i g_i² / h_i`. -/
theorem lemma_16 {d : ℕ} (η : ℝ) (hη : 0 < η) (X : Set (EuclideanSpace ℝ (Fin d)))
(hXc : Convex ℝ X) (ϕ : EuclideanSpace ℝ (Fin d) → ℝ) (hϕ : ConvexOn ℝ Set.univ ϕ)
(ft : EuclideanSpace ℝ (Fin d) → ℝ) (hft : ConvexOn ℝ Set.univ ft)
(h : Fin d → ℝ) (hh : ∀ i, 0 ≤ h i)
(xt xnext gt : EuclideanSpace ℝ (Fin d))
(hhg : ∀ i, h i = 0 → gt i = 0)
(hsub : IsSubgradient ft xt gt) (hmem : xnext ∈ X)
(hmin : IsMinOn (fun y => η * inner ℝ gt y + η * ϕ y + bregman h y xt) X xnext)
(xstar : EuclideanSpace ℝ (Fin d)) (hxstar : xstar ∈ X) :
η * (ft xt - ft xstar) + η * (ϕ xnext - ϕ xstar)
≤ bregman h xstar xt - bregman h xstar xnext + η ^ 2 / 2 * dualNormSq h gt := by sorry
end AdaGrad.Diag
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.