(2.5) — V_β(s + δ) ≤ V_β(s) + ⟨δ, ∇V_β(s)⟩ + ‖δ‖²_*/(2σβ)
ProvedPrimalDualSubgrad.DA.eq_2_5convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space , an argmin map , and . For all ,
where by Lemma 1.
This upper quadratic model of is the one-step inequality of the Dual Averaging analysis.
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_ProxSetting
Formal statement
namespace PrimalDualSubgrad.DA
/-- (2.5), p. 7: for `β > 0` and all `s, δ ∈ E*`,
`V_β(s + δ) ≤ V_β(s) + ⟨δ, ∇V_β(s)⟩ + ‖δ‖²_*/(2σβ)`, with `∇V_β(s) = π_β(s) − x0` (2.4). -/
theorem eq_2_5 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (π : ℝ → StrongDual ℝ E → E) (hπ : IsProxMap P π)
(β : ℝ) (hβ : 0 < β) (s δ : StrongDual ℝ E) :
V P β (s + δ) ≤ V P β s + δ (π β s - P.x0) + 1 / (2 * P.σ * β) * ‖δ‖ ^ 2 := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), §2, (2.5), p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.