(2.18) — telescoped bound Σλᵢ⟨gᵢ, xᵢ − x₀⟩ ≤ V_{β₁}(−s₁) − V_{β_{k+1}}(−s_{k+1}) + (1/2σ)Σ_{i=1}^k λᵢ²‖gᵢ‖²_*/βᵢ
ProvedPrimalDualSubgrad.DA.eq_2_18convex-optimizationdual-averagingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a prox setting in a finite-dimensional normed space and an argmin map , and let be generated by the Dual Averaging scheme (2.14). Then for every
Note that the sum on the right starts at . This is the core estimate of the proof of Theorem 1, from which all three parts follow.
Preamble
import Mathlib import Definitions.Def_PrimalDualSubgrad_DA_DualAveraging
Formal statement
namespace PrimalDualSubgrad.DA
open Finset
/-- (2.18), p. 10 (proof of Theorem 1, item 1): for a run of the DA-scheme (2.14) and every
`k ≥ 0`,
`∑_{i=0}^k λ_i⟨g_i, x_i − x0⟩ ≤ V_{β_1}(−s_1) − V_{β_{k+1}}(−s_{k+1}) + (1/(2σ)) ∑_{i=1}^k λ_i²‖g_i‖²_*/β_i`. -/
theorem eq_2_18 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(P : ProxSetting E) (π : ℝ → StrongDual ℝ E → E) (hπ : IsProxMap P π)
(lam β : ℕ → ℝ) (g : ℕ → StrongDual ℝ E) (x : ℕ → E) (hrun : IsDARun P π lam β g x)
(k : ℕ) :
∑ i ∈ range (k + 1), lam i * g i (x i - P.x0) ≤
V P (β 1) (-(sAgg lam g 1)) - V P (β (k + 1)) (-(sAgg lam g (k + 1))) +
1 / (2 * P.σ) * ∑ i ∈ Icc 1 k, lam i ^ 2 / β i * ‖g i‖ ^ 2 := by sorry
end PrimalDualSubgrad.DA
Source
Nesterov, Primal-dual subgradient methods for convex problems, Math. Program. 120 (2009), §2, proof of Theorem 1, (2.18), p. 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.