Home / Curated / Algorithms / SpiderBoost and Proximal SpiderBoost with Momentum for Non-Convex Optimization

SpiderBoost and Proximal SpiderBoost with Momentum for Non-Convex Optimization

Algorithms AIMech:SpiderBoostAndProximalSpiderBoostWithMomentumForNonconvexOptimization DRAFT

Aliases: SpiderBoost, Prox-SpiderBoost, Prox-SpiderBoost-M, Proximal SpiderBoost with Momentum

A family of stochastic path-integrated variance reduction algorithms (Wang, Ji, Zhou, Liang, & Tarokh 2019) for smooth and composite non-convex optimization min_x Psi(x) = f(x) + h(x) (where f is L-smooth non-convex and h is proper closed convex) that maintains the SPIDER recursive gradient estimator v_k = (1/|S|) sum_{i in S} (nabla f_i(x_k) - nabla f_i(x_{k-1})) + v_{k-1} with epoch period q = |S| = ceil(n^{1/2}), replaces SPIDER's accuracy-dependent normalized update x_{k+1} = x_k - (varepsilon / (L * n_0)) * (v_k / ||v_k||_2) with an unnormalized large constant step size eta = 1 / (2L) via an epoch-grouped telescoping analysis (SpiderBoost), and extends directly to proximal composite mappings x_{k+1} = prox_{eta*h}(x_k - eta*v_k) (Prox-SpiderBoost), Bregman proximal mappings, and Nesterov-style momentum coupling (Prox-SpiderBoost-M), achieving optimal O(min(n + n^{1/2} * varepsilon^{-2}, varepsilon^{-3})) stochastic first-order oracle (SFO) complexity and O(varepsilon^{-2}) proximal oracle (PO) complexity.

Identity Notes & Concept Scope Distinct from original SPIDER (Fang et al. 2018, AIMech:SPIDERStochasticPathIntegratedDifferentialEstimatorForNonConvexOptimization), which uses a tiny accuracy-dependent step size eta = O(varepsilon / L) and normalized gradient directions that prevent direct extension to composite proximal mappings prox_{eta*h}; from SARAH (Nguyen et al. 2017, AIMech:SARAHStochasticRecursiveGradientForFiniteSumOptimization), which uses b = 1 and sub-optimal O(n + n^{2/3}/varepsilon^2) non-convex complexity; and from loopless PAGE (Li et al. 2021, AIMech:PageProbabilisticGradientEstimatorForNonconvexOptimization), which replaces deterministic q-periodic epochs with Bernoulli coin flips for unconstrained smooth problems.

Claims & Grounded Evidence

3 Claims

Mechanism #r376-claim-epoch-grouped-telescoping-and-constant-step-size

Whereas original SPIDER bounds single-step descent by enforcing ||v_k - nabla f(x_k)||_2 <= varepsilon at every step via a tiny step size eta = O(varepsilon / L), SpiderBoost (Algorithm 1, Theorem 1) telescopically sums the accumulated recursive variance E||v_k - nabla f(x_k)||_2^2 <= sum_{j=(n_k-1)q}^{k-1} (L^2 / |S|) E||x_{j+1} - x_j||_2^2 across each entire epoch of length q = |S| = ceil(n^{1/2}), yielding a positive per-step descent coefficient beta_1 = 1/(2*eta) - L/2 - (eta * L^2 / 2) * (q / |S|) = L/4 > 0 at the large accuracy-independent constant step size eta = 1 / (2L) and achieving E||nabla f(x_out)||_2 <= varepsilon in O(n + n^{1/2} * varepsilon^{-2}) stochastic gradient evaluations.

supports Source: SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms · Locator: Section 2, Algorithm 1, Theorem 1, Remark 1; Appendix G-H, Lemma 1 and Theorem 10

Mechanism #r376-claim-prox-spiderboost-composite-and-pl-convergence

For composite non-convex problems min_x Psi(x) = f(x) + h(x), Prox-SpiderBoost (Algorithm 2, Theorems 2 and 6) applies the unnormalized proximal gradient mapping G_eta(x_k, v_k) = (1/eta) * (x_k - prox_{eta*h}(x_k - eta*v_k)) with constant step size eta = 1 / (2L), achieving E||G_eta(x_xi, nabla f(x_xi))||_2 <= varepsilon in O(n + n^{1/2} * varepsilon^{-2}) finite-sum (or O(varepsilon^{-3}) online) SFO calls and O(varepsilon^{-2}) proximal oracle (PO) calls, improving upon ProxSVRG/ProxSAGA's O(n + n^{2/3} * varepsilon^{-2}) SFO complexity by n^{1/6}; under the composite Polyak-Lojasiewicz condition ||G_eta(x, nabla f(x))||_2^2 >= (1/tau) * (Psi(x) - Psi^*), Prox-SpiderBoost-PL (Theorem 5) achieves linear convergence O((n + L^2 * tau^2) * log(1/varepsilon)) SFO and O(L * tau * log(1/varepsilon)) PO calls without restarting when L*tau <= n^{1/2}.

supports Source: SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms · Locator: Section 1, Table 1; Section 3.1-3.3, Algorithm 2, Theorems 2, 4, 5, 6, and 7; Appendix H-I

Mechanism #r376-claim-momentum-coupling-prox-spiderboost-m

Prox-SpiderBoost-M (Algorithm 3, Theorems 3 and 8) couples three iterate sequences {x_k, y_k, z_k} with epoch-synchronized momentum weight alpha_k = 2 / (ceil(k / q) + 1), evaluating the SPIDER estimator v_k at the extrapolated point z_k = (1 - alpha_{k+1}) y_k + alpha_{k+1} x_k while bounding the momentum drift ||z_{k+1} - z_k||_2^2 <= 2*(1 + alpha_{k+2})^2 ||y_{k+1} - x_k||_2^2 + 2*alpha_{k+1}^2 ||x_k - y_k||_2^2 via the decreasing product sequence Gamma_k = 2 / (ceil(k/q) * (ceil(k/q) + 1)) (Lemma 5), preserving optimal O(n + n^{1/2} * varepsilon^{-2}) finite-sum and O(varepsilon^{-3}) online SFO complexity with faster empirical convergence on non-convex classification and robust image denoising.

supports Source: SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms · Locator: Section 4, Algorithm 3, Theorem 3; Section 5, Figures 1-2; Appendix J, Lemmas 3-6, Proof of Theorem 3

⚠️ Curated Limitations & Negative Results

Requires periodic full-batch (size n) or large-minibatch (size O(varepsilon^{-2})) checkpoint gradient evaluations at the start of every q-step epoch, and under the composite PL condition requires the condition number L*tau to be known to set the epoch length q = |S| = Theta(L*tau) (Theorem 5, Appendix I).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LassoRegression` Lasso Regression	related_match	Prox-SpiderBoost directly optimizes l1-regularized and composite non-convex sparsity-inducing objectives via the proximal operator prox_{eta*h}.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r376-primary-pdf`	SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, Vahid Tarokh	primary paper full_text	ID: https://papers.nips.cc/paper/2019/hash/512c5cad6c37edb98ae91c8a76c3a291-Abstract.html sha256:9add66957c88…
`r376-arxiv-abs`	SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms (arXiv abstract) Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, Vahid Tarokh	primary paper abstract_only	ID: https://arxiv.org/abs/1810.10690 sha256:9af5198d3c4b…
`r376-metadata-cr`	SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms (Crossref metadata) Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, Vahid Tarokh	primary paper abstract_only	ID: https://papers.nips.cc/paper/2019/hash/512c5cad6c37edb98ae91c8a76c3a291-Abstract.html sha256:4c52bc57835f…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T07:39:00Z

Updated: 2026-10-19T07:39:00Z

Source File: data/curated/SpiderBoostAndProximalSpiderBoostWithMomentumForNonconvexOptimization.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories