Lemma 2 — ξ_D(s) ≤ βD + V_β(s)
ProvedPrimalDualSubgrad.DA.lemma_2convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space . For every , and ,
It compares the support function of the level set with the smoothed function , and turns bounds on into bounds on the gap.
Formalization Note The page states the lemma for ; is defined in (2.1) only for (for and unbounded it is ), so the statement is for .
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_ProxSetting
Formal statement
namespace PrimalDualSubgrad.DA
/-- Lemma 2 (p. 8), (2.7): for `D ≥ 0`, `β > 0` and `s ∈ E*`, `ξ_D(s) ≤ βD + V_β(s)`.
(The page says `β ≥ 0`; `V_0` is not defined by (2.1) and is `+∞` on unbounded `Q`.) -/
theorem lemma_2 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (D β : ℝ) (hD : 0 ≤ D) (hβ : 0 < β) (s : StrongDual ℝ E) :
xi P D s ≤ β * D + V P β s := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), p. 8, Lemma 2, (2.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.