Lemma 1 — V_β is convex and differentiable with 1/(βσ)-Lipschitz gradient π_β(s) − x₀
ProvedPrimalDualSubgrad.DA.lemma_1convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space , an argmin map , and . Then the function is convex and differentiable on , its gradient at is (2.4), where , and the gradient is Lipschitz continuous with constant :
This is the smoothness of the dual function on which the Dual Averaging analysis rests.
Formalization Note The gradient, an element of , is identified with a vector of : the Fréchet derivative of at is the functional . The page says " belongs to ", which is true only for ; what holds and what is stated is (this conjunct follows directly from the argmin-map hypothesis).
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_ProxSetting
Formal statement
namespace PrimalDualSubgrad.DA
/-- Lemma 1 (p. 7). For `β > 0`, `V_β` is convex and differentiable on `E*`, its gradient at
`s` is the evaluation at `π_β(s) − x0` (the identification `E** = E`), the gradient is
Lipschitz with constant `1/(βσ)` (2.3), and `π_β(s) ∈ Q` (2.4). -/
theorem lemma_1 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (π : ℝ → StrongDual ℝ E → E) (hπ : IsProxMap P π)
(β : ℝ) (hβ : 0 < β) :
ConvexOn ℝ Set.univ (V P β) ∧
(∀ s : StrongDual ℝ E,
HasFDerivAt (V P β) (ContinuousLinearMap.apply ℝ ℝ (π β s - P.x0)) s) ∧
(∀ s₁ s₂ : StrongDual ℝ E, ‖π β s₁ - π β s₂‖ ≤ 1 / (β * P.σ) * ‖s₁ - s₂‖) ∧
(∀ s : StrongDual ℝ E, π β s ∈ P.Q) := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), p. 7, Lemma 1, (2.3), (2.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.