(2.48)–(2.49) — three-point inequalities for the prox steps of Algorithm 2
ProvedNonconvexAG.Composite.eq_2_48_2_49accelerated-gradientcomposite-optimizationnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-methods
Let be convex on its domain and let be a prox map for as in (2.37). Run Algorithm 2 with any gradient map , step sizes with , (), , and any . Then for every and every :
These are the optimality conditions of the subproblems (2.40) and (2.41), in the three-point form of Lemma 2 of Lan's reference [11].
Formalization Note The paper says "for any "; for the right-hand side is and the inequality is void, so the statement quantifies over .
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_NonconvexAG_Composite_ProxMap import Definitions.Def_NonconvexAG_Composite_AGRun
Formal statement
namespace NonconvexAG.Composite
open ConvexOptAlg.SmoothGD
/-- (2.48) and (2.49), p. 12: the three-point inequalities for the prox subproblems (2.40) and
(2.41) of Algorithm 2, for every `k ≥ 1` and every `x` in the domain `K` of `𝒳`. -/
theorem eq_2_48_2_49 {n : ℕ} (gΨ : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n) (K : Set (NonconvexAG.Smooth.E n)) (X : NonconvexAG.Smooth.E n → ℝ)
(hX : ConvexOn ℝ K X) (P : NonconvexAG.Smooth.E n → NonconvexAG.Smooth.E n → ℝ → NonconvexAG.Smooth.E n) (hP : IsProxMap K X P)
(α β lam : ℕ → ℝ) (hstep : NonconvexAG.Smooth.AGStepsizes α β lam) (x0 : NonconvexAG.Smooth.E n) :
let xk : ℕ → NonconvexAG.Smooth.E n := xSeq gΨ P α β lam x0
let xag : ℕ → NonconvexAG.Smooth.E n := xagSeq gΨ P α β lam x0
let xmd : ℕ → NonconvexAG.Smooth.E n := xmdSeq gΨ P α β lam x0
∀ k, 1 ≤ k → ∀ x ∈ K,
inner ℝ (gΨ (xmd k)) (xk k - x) + X (xk k) ≤
X x + 1 / (2 * lam k) * (‖xk (k - 1) - x‖ ^ 2 - ‖xk k - x‖ ^ 2 - ‖xk k - xk (k - 1)‖ ^ 2) ∧
inner ℝ (gΨ (xmd k)) (xag k - x) + X (xag k) ≤
X x + 1 / (2 * β k) * (‖xmd k - x‖ ^ 2 - ‖xag k - x‖ ^ 2 - ‖xag k - xmd k‖ ^ 2) := by sorry
end NonconvexAG.Composite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 12, (2.48) and (2.49)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.