Theorem 1 — Dual Averaging: δ_k(D) ≤ Δ_k(β_{k+1}, D) ≤ β_{k+1}D + (1/2σ)Σλᵢ²‖gᵢ‖²_*/βᵢ, bounded iterates, bounded averaged subgradients
ProvedPrimalDualSubgrad.DA.theorem_1Fix a prox setting in a finite-dimensional normed space with dual (so is -strongly convex on , , and is the prox-center with ), an argmin map , and let be generated by the Dual Averaging scheme (2.14): , , and for , , , , , starting from . Write and . Then:
- for every and ,
- if is a solution in the sense (2.8), i.e. for all , then for every
- if such a solution is interior, for some and , then for every
This is the main theorem of the paper: one bound on the gap of the generic Dual Averaging scheme, from which the convergence rates of all its instances (simple and weighted averages, saddle points, variational inequalities, stochastic versions) are derived. Part 2 shows that the iterates stay bounded even when is unbounded.
Formalization Note The oracle answers are free data (more general than ), and the run starts at the prox-center, in (2.14) being the paper's . The norm on is arbitrary and is the operator norm. Part 3 keeps the hypothesis (2.8) on : "solution" on the page means a solution in the sense (2.8), and the proof uses it.
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_DualAveraging
namespace PrimalDualSubgrad.DA
open Finset
/-- Theorem 1 (p. 9). Let `x_k, g_k, λ_k, β_k` be generated by the DA-scheme (2.14). Then
1. (2.15) for all `k ≥ 0`, `D ≥ 0`:
`δ_k(D) ≤ Δ_k(β_{k+1}, D) ≤ β_{k+1} D + (1/(2σ)) ∑_{i=0}^k λ_i²‖g_i‖²_*/β_i`;
2. (2.16) if `x* ∈ Q` satisfies (2.8), `⟨g_i, x_i − x*⟩ ≥ 0` for all `i`, then
`(σ/2)‖x_{k+1} − x*‖² ≤ d(x*) + (1/(2σβ_{k+1})) ∑_{i=0}^k λ_i²‖g_i‖²_*/β_i`;
3. (2.17) if moreover `B_r(x*) ⊆ F_D` for some `r > 0`, `D > 0`, then
`‖ŝ_{k+1}‖_* ≤ (1/(r S_k)) [β_{k+1} D + (1/(2σ)) ∑_{i=0}^k λ_i²‖g_i‖²_*/β_i]`,
where `ŝ_{k+1} = s_{k+1}/S_k`. -/
theorem theorem_1 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (π : ℝ → StrongDual ℝ E → E) (hπ : IsProxMap P π)
(lam β : ℕ → ℝ) (g : ℕ → StrongDual ℝ E) (x : ℕ → E) (hrun : IsDARun P π lam β g x) :
(∀ k : ℕ, ∀ D : ℝ, 0 ≤ D →
delta P lam g x k D ≤ Delta P lam g x k (β (k + 1)) D ∧
Delta P lam g x k (β (k + 1)) D ≤
β (k + 1) * D + 1 / (2 * P.σ) * ∑ i ∈ range (k + 1), lam i ^ 2 / β i * ‖g i‖ ^ 2) ∧
(∀ xstar ∈ P.Q, (∀ i, 0 ≤ g i (x i - xstar)) → ∀ k : ℕ,
P.σ / 2 * ‖x (k + 1) - xstar‖ ^ 2 ≤
P.d xstar + 1 / (2 * P.σ * β (k + 1)) *
∑ i ∈ range (k + 1), lam i ^ 2 / β i * ‖g i‖ ^ 2) ∧
(∀ xstar ∈ P.Q, (∀ i, 0 ≤ g i (x i - xstar)) → ∀ r : ℝ, 0 < r → ∀ D : ℝ, 0 < D →
Metric.closedBall xstar r ⊆ FD P D → ∀ k : ℕ,
‖(1 / Ssum lam k) • sAgg lam g (k + 1)‖ ≤
1 / (r * Ssum lam k) *
(β (k + 1) * D + 1 / (2 * P.σ) * ∑ i ∈ range (k + 1), lam i ^ 2 / β i * ‖g i‖ ^ 2)) := by sorry
end PrimalDualSubgrad.DA
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.