SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objec…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
6 results for “SpiderBoost”
New sparsity operator reduces variance reduction methods' computational cost.
problem Reduce computational cost of variance reduction methods.
method Introduce random-top-k operator to estimate gradient sparsity and reduce operations per update.
result Our algorithm consistently outperforms SpiderBoost in various tasks.
Improved algorithm finds second-order stationary points in non-convex optimization.
problem Minimizing non-convex objectives while preserving training data privacy.
method SpiderBoost framework with two gradient oracles: precise and less precise.
result Improved rates for finding second-order stationary points.
Improved method finds second-order stationary points privately with better efficiency.
problem Finding second-order stationary points privately under differential privacy constraints.
method Adaptive batch sizes and binary tree mechanism.
result Improved bound for privately finding SOSP, matching state-of-the-art for FOSP.
A new biased gradient descent method for conditional stochastic optimization.
problem Challenges in constructing unbiased gradient estimators for conditional stochastic optimization.
method Proposes a biased stochastic gradient descent (BSGD) algorithm and analyzes its sample complexities.
result Establishes sample complexities of BSGD for various objectives and shows that BSpiderBoost matches the lower bound complexity.
Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifoldmath.OC
Two new methods solve nonsmooth optimization on Riemannian Stiefel manifold.
problem Optimization over nonsmooth, non-differentiable functions on Riemannian manifolds.
method R-ProxSGD and R-ProxSPB, generalizing proximal SGD and SpiderBoost.
result R-ProxSPB finds ε-stationary points with IFO complexity of Ø(ε^(-3)) in online and Ø(n + √nε^(-2)) in finite-sum cases.