(3.34) — the combined stochastic prox inequality under α_kλ_k ≤ β_k
ProvedNonconvexAG.StochComposite.eq_3_34accelerated-gradientcomposite-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the setting of (3.32)–(3.33), for every with and every ,
It combines the two three-point inequalities through the convexity of and the definition (2.2) of .
Formalization Note Pathwise, for . At the term carries the factor , so is not needed (the Lean X is a real-valued function on all of whose values off are irrelevant).
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model import Definitions.Def_NonconvexAG_StochComposite_ProxMap import Definitions.Def_NonconvexAG_StochComposite_RSAG open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
Formal statement
namespace NonconvexAG.StochComposite
open GhadimiLan.RSG (E)
open ConvexOptAlg.SmoothGD
/-- (3.34), p. 22 (outer ends of the chain), along Algorithm 4, for every realization `ω`, every
`k ≥ 1` with `αₖλₖ ≤ βₖ` and every `x` in the domain `K` of `𝒳`. -/
theorem eq_3_34 {n : ℕ} (gΨ : E n → E n) (K : Set (E n)) (X : E n → ℝ)
(hX : ConvexOn ℝ K X) (P : E n → E n → ℝ → E n) (hP : IsProxMap K X P)
{Ξ : Type*} (G : E n → Ξ → E n)
(α β lam : ℕ → ℝ) (m : ℕ → ℕ) (hstep : RSAGStepsizes α β lam m) (x0 : E n)
{Ω : Type*} (ξ : ℕ → Ω → Ξ) :
let xk : ℕ → Ω → E n := xSeq G P α β lam m x0 ξ
let xag : ℕ → Ω → E n := xagSeq G P α β lam m x0 ξ
let xmd : ℕ → Ω → E n := xmdSeq G P α β lam m x0 ξ
let δ : ℕ → Ω → E n := deltaBar G gΨ P α β lam m x0 ξ
∀ ω : Ω, ∀ k, 1 ≤ k → α k * lam k ≤ β k → ∀ x ∈ K,
inner ℝ (gΨ (xmd k ω) + δ k ω) (xag k ω - α k • x - (1 - α k) • xag (k - 1) ω) +
X (xag k ω) ≤
(1 - α k) * X (xag (k - 1) ω) + α k * X x +
α k / (2 * lam k) * (‖xk (k - 1) ω - x‖ ^ 2 - ‖xk k ω - x‖ ^ 2) -
1 / (2 * β k) * ‖xag k ω - xmd k ω‖ ^ 2 := by sorry
end NonconvexAG.StochComposite
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 22, (3.34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.