Stochastic analogue of (2.17) — ‖x^ag_{k−1} − x_{k−1}‖² ≤ Γ_{k−1} Σ_τ ((λ_τ − β_τ)²/(Γ_τα_τ))‖∇Ψ(x^md_τ) + δ_τ‖² (p. 16)
ProvedNonconvexAG.Stoch.eq_2_17_stochaccelerated-gradientnonconvex-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 and every ,
It bounds the gap between the two sequences of the method by the past stochastic gradients ; combined with the one-step inequality it yields the summed bound of the proof of Theorem 3 a).
Formalization Note The inequality is pathwise. At both sides are . The paper prints in the first line of its display; the index of there is , as the second line of the same display shows, and the Lean states the second line.
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.17) (proof of Theorem 3 a), p. 16, display "Noting that
similar to (2.17)", outer ends, with the printed `δₖ` inside the first sum read as `δ_τ`),
pathwise for every sample point `ω` and every `k ≥ 1`:
`‖x^ag_{k−1} − x_{k−1}‖² ≤ Γ_{k−1} Σ_{τ=1}^{k−1} ((λ_τ − β_τ)²/(Γ_τα_τ))
[‖∇Ψ(x^md_τ)‖² + ‖δ_τ‖² + 2⟨∇Ψ(x^md_τ), δ_τ⟩]`. -/
theorem eq_2_17_stoch {n : ℕ} (g : E n → E n)
{Ω Ξ : Type*} (G : E n → Ξ → E n) (ξ : ℕ → Ω → Ξ)
(α β lam : ℕ → ℝ) (hstep : RSAGStepsizes α β lam) (x0 : E n) :
∀ k, 1 ≤ k → ∀ ω : Ω,
‖xagSeq G α β lam x0 ξ (k - 1) ω - xSeq G α β lam x0 ξ (k - 1) ω‖ ^ 2 ≤
NonconvexAG.Smooth.Gamma α (k - 1) * ∑ τ ∈ Finset.Icc 1 (k - 1),
(lam τ - β τ) ^ 2 / (NonconvexAG.Smooth.Gamma α τ * α τ) *
(‖g (xmdSeq G α β lam x0 ξ τ ω)‖ ^ 2 + ‖delta G g α β lam x0 ξ τ ω‖ ^ 2
+ 2 * ⟪g (xmdSeq G α β lam x0 ξ τ ω), delta G g α β lam x0 ξ τ ω⟫_ℝ) := by sorry
end NonconvexAG.Stoch
Source
Ghadimi & Lan, Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming, arXiv:1310.3787v1, p. 16, §3.1, display "Noting that similar to (2.17)"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.