(2.6) — V_β(δ) ≤ ‖δ‖²_*/(2σβ)
ProvedPrimalDualSubgrad.DA.eq_2_6convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space (so and minimizes on ) and . For every ,
It bounds the first term of the telescoped sum in the proof of Theorem 1.
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_ProxSetting
Formal statement
namespace PrimalDualSubgrad.DA
/-- (2.6), p. 7: for `β > 0` and every `δ ∈ E*`, `V_β(δ) ≤ ‖δ‖²_*/(2σβ)`. -/
theorem eq_2_6 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (β : ℝ) (hβ : 0 < β) (δ : StrongDual ℝ E) :
V P β δ ≤ 1 / (2 * P.σ * β) * ‖δ‖ ^ 2 := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), §2, (2.6), p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.