Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — Dual Averaging: δ_k(D) ≤ Δ_k(β_{k+1}, D) ≤ β_{k+1}D + (1/2σ)Σλᵢ²‖gᵢ‖²_*/βᵢ, bounded iterates, bounded averaged subgradients

Proved
PrimalDualSubgrad.DA.theorem_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1subgradient-methods

Fix a prox setting (Q,d,σ,x0)(Q, d, \sigma, x_0)(Q,d,σ,x0​) in a finite-dimensional normed space EEE with dual E∗E^*E∗ (so ddd is σ\sigmaσ-strongly convex on QQQ, σ>0\sigma > 0σ>0, and x0x_0x0​ is the prox-center with d(x0)=0d(x_0) = 0d(x0​)=0), an argmin map π\piπ, and let (xk,gk,λk,βk)(x_k, g_k, \lambda_k, \beta_k)(xk​,gk​,λk​,βk​) be generated by the Dual Averaging scheme (2.14): s0=0s_0 = 0s0​=0, β0>0\beta_0 > 0β0​>0, and for k≥0k \ge 0k≥0, λk>0\lambda_k > 0λk​>0, sk+1=sk+λkgks_{k+1} = s_k + \lambda_k g_ksk+1​=sk​+λk​gk​, βk+1≥βk\beta_{k+1} \ge \beta_kβk+1​≥βk​, xk+1=πβk+1(−sk+1)x_{k+1} = \pi_{\beta_{k+1}}(-s_{k+1})xk+1​=πβk+1​​(−sk+1​), starting from x0x_0x0​. Write Sk=∑i=0kλiS_k = \sum_{i=0}^k \lambda_iSk​=∑i=0k​λi​ and s^k+1=sk+1/Sk\hat s_{k+1} = s_{k+1}/S_ks^k+1​=sk+1​/Sk​. Then:

  1. for every k≥0k \ge 0k≥0 and D≥0D \ge 0D≥0,
δk(D)≤Δk(βk+1,D)≤βk+1D+12σ∑i=0kλi2βi∥gi∥∗2;(2.15)\delta_k(D) \le \Delta_k(\beta_{k+1}, D) \le \beta_{k+1} D + \frac{1}{2\sigma}\sum_{i=0}^k \frac{\lambda_i^2}{\beta_i}\|g_i\|_*^2; \qquad (2.15)δk​(D)≤Δk​(βk+1​,D)≤βk+1​D+2σ1​i=0∑k​βi​λi2​​∥gi​∥∗2​;(2.15)
  1. if x∗∈Qx^* \in Qx∗∈Q is a solution in the sense (2.8), i.e. ⟨gi,xi−x∗⟩≥0\langle g_i, x_i - x^*\rangle \ge 0⟨gi​,xi​−x∗⟩≥0 for all i≥0i \ge 0i≥0, then for every k≥0k \ge 0k≥0
12σ∥xk+1−x∗∥2≤d(x∗)+12σβk+1∑i=0kλi2βi∥gi∥∗2;(2.16)\tfrac12\sigma\|x_{k+1} - x^*\|^2 \le d(x^*) + \frac{1}{2\sigma\beta_{k+1}}\sum_{i=0}^k \frac{\lambda_i^2}{\beta_i}\|g_i\|_*^2; \qquad (2.16)21​σ∥xk+1​−x∗∥2≤d(x∗)+2σβk+1​1​i=0∑k​βi​λi2​​∥gi​∥∗2​;(2.16)
  1. if such a solution x∗x^*x∗ is interior, Br(x∗)={y:∥y−x∗∥≤r}⊆FDB_r(x^*) = \{y : \|y - x^*\| \le r\} \subseteq F_DBr​(x∗)={y:∥y−x∗∥≤r}⊆FD​ for some r>0r > 0r>0 and D>0D > 0D>0, then for every k≥0k \ge 0k≥0
∥s^k+1∥∗≤1rSk[βk+1D+12σ∑i=0kλi2βi∥gi∥∗2].(2.17)\|\hat s_{k+1}\|_* \le \frac{1}{r S_k}\Big[\beta_{k+1} D + \frac{1}{2\sigma}\sum_{i=0}^k \frac{\lambda_i^2}{\beta_i}\|g_i\|_*^2\Big]. \qquad (2.17)∥s^k+1​∥∗​≤rSk​1​[βk+1​D+2σ1​i=0∑k​βi​λi2​​∥gi​∥∗2​].(2.17)

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 QQQ is unbounded.

Formalization Note The oracle answers gkg_kgk​ are free data (more general than gk=G(xk)g_k = \mathcal G(x_k)gk​=G(xk​)), and the run starts at the prox-center, x0x_0x0​ in (2.14) being the paper's x0x_0x0​. The norm on EEE is arbitrary and ∥⋅∥∗\|\cdot\|_*∥⋅∥∗​ is the operator norm. Part 3 keeps the hypothesis (2.8) on x∗x^*x∗: "solution" on the page means a solution in the sense (2.8), and the proof uses it.

Preamble
import Mathlib
import Definitions.Def_PrimalDualSubgrad_DA_DualAveraging
Formal statement
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
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), p. 9, Theorem 1, (2.15)–(2.17), with (2.8) p. 8 and (2.14) p. 9
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me