Stochastic analogue of (2.22) — α_k⟨G(x^md_k, ξ_k), x_{k−1} − x⟩ identity (p. 17)
ProvedNonconvexAG.Stoch.eq_2_22_stochaccelerated-gradientconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation
Run the RSAG method (Algorithm 3) from with step sizes , (), , any oracle and any noise sequence; let be any map (in the paper ) and . Then for every sample point, every and every ,
It is the three-point identity for the step (3.2), , which produces the telescoping distance terms of the convex analysis.
Formalization Note The identity is pathwise; is the oracle output .
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_SmoothGD_Defs import Definitions.Def_GhadimiLan_RSG_Model import Definitions.Def_NonconvexAG_Stoch_RSAG open MeasureTheory ProbabilityTheory open scoped InnerProductSpace
Formal statement
namespace NonconvexAG.Stoch
open GhadimiLan.RSG (E)
/-- The stochastic analogue of (2.22) (proof of Theorem 3 b), p. 17, display "Similar to
(2.22)"), pathwise for every sample point `ω`, every `k ≥ 1` and every `x ∈ ℝⁿ`:
`αₖ⟨∇Ψ(x^md_k) + δₖ, x_{k−1} − x⟩ = (αₖ/(2λₖ))[‖x_{k−1} − x‖² − ‖xₖ − x‖²]
+ (αₖλₖ/2)‖∇Ψ(x^md_k) + δₖ‖²`. -/
theorem eq_2_22_stoch {n : ℕ} (g : E n → E n)
{Ω Ξ : Type*} (G : E n → Ξ → E n) (ξ : ℕ → Ω → Ξ)
(α β lam : ℕ → ℝ) (hstep : RSAGStepsizes α β lam) (x0 : E n) :
∀ k, 1 ≤ k → ∀ ω : Ω, ∀ x : E n,
α k * ⟪g (xmdSeq G α β lam x0 ξ k ω) + delta G g α β lam x0 ξ k ω,
xSeq G α β lam x0 ξ (k - 1) ω - x⟫_ℝ =
α k / (2 * lam k) *
(‖xSeq G α β lam x0 ξ (k - 1) ω - x‖ ^ 2 - ‖xSeq G α β lam x0 ξ k ω - x‖ ^ 2)
+ α k * lam k / 2 *
‖g (xmdSeq G α β lam x0 ξ k ω) + delta G g α β lam x0 ξ k ω‖ ^ 2 := by sorry
end NonconvexAG.Stoch
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 17, §3.1, display "Similar to (2.22)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.