(2.13) — δ_k(D) ≤ Δ_k(β, D)
ProvedPrimalDualSubgrad.DA.eq_2_13convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space and arbitrary sequences , , . For every , and ,
The gap is thus controlled by the upper gap function, which is what Theorem 1 bounds along the scheme.
Formalization Note The page says "for any non-negative and "; , and so , is defined only for . The page considers and ; the statement holds, and is stated, for arbitrary sequences.
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_DualAveraging
Formal statement
namespace PrimalDualSubgrad.DA
/-- (2.13), p. 9: for any sequences `x_i ∈ E`, `g_i ∈ E*`, `λ_i ∈ ℝ`, any `D ≥ 0` and
`β > 0`, `δ_k(D) ≤ Δ_k(β, D)`. (The page says "non-negative β"; `V_0` is undefined.) -/
theorem eq_2_13 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (lam : ℕ → ℝ) (g : ℕ → StrongDual ℝ E) (x : ℕ → E)
(k : ℕ) (β D : ℝ) (hβ : 0 < β) (hD : 0 ≤ D) :
delta P lam g x k D ≤ Delta P lam g x k β D := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), §2, (2.13), p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.