Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting, counterexamples exist and prevent Nesterov's momentum from providing similar acceleration, even if the underlying problem is convex and fin…
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.
169,051 papers · 148 categories
Trend · papers per month
14 results for “Katyusha”
Unified analysis of SVRG and Katyusha using dissipativity theory.
problem Accelerating variance reduction in stochastic optimization.
method Dissipativity theory applied to SVRG and Katyusha.
result Unified convergence analysis of SVRG and Katyusha.
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcs.LG
Loopless SVRG and Katyusha methods outperform their counterparts in practical applications.
problem Training supervised machine learning models efficiently.
method Designing loopless variants of SVRG and Katyusha methods.
result Loopless variants of SVRG and Katyusha have superior practical behavior.
Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learningcs.LG
Recently, research on accelerated stochastic gradient descent methods (e.g., SVRG) has made exciting progress (e.g., linear convergence for strongly convex problems). However, the best-known methods (e.g., Katyusha) requires at least two auxiliary variables and two momentum parameters. In this paper, we propose a fast …
The problem of minimizing sum-of-nonconvex functions (i.e., convex functions that are average of non-convex ones) is becoming increasingly important in machine learning, and is the core machinery for PCA, SVD, regularized Newton's method, accelerated non-convex optimization, and more. We show how to provably obtain an …
Paper accelerates SAGA using sampled negative momentum.
problem Directly accelerating SAGA for optimization problems.
method Proposes SSNM for direct acceleration of SAGA.
result Achieves best known oracle complexity for strongly convex problems.
ASVRG accelerates stochastic variance reduction methods with simplicity and efficiency.
problem Efficiently solving convex and non-convex optimization problems.
method Accelerated proximal stochastic variance reduced gradient (ASVRG) method with momentum acceleration.
result ASVRG achieves best known oracle complexities for strongly and non-strongly convex objectives.
Paper develops momentum schemes with variance reduction for non-convex composition optimization.
problem Lack of convergence guarantee and efficient momentum design in existing algorithms.
method Develops various momentum schemes with SPIDER-based variance reduction.
result Achieves near-optimal sample complexity and linear convergence rate.
Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscs.LG
New algorithms improve distributed optimization under specific conditions.
problem Distributed optimization problems with high communication costs.
method SVRS and AccSVRS algorithms combining gradient sliding and variance reduction.
result Achieved better communication complexity in distributed optimization.
A new simple algorithm reduces variance for fast convergence.
problem Improving convergence rates for stochastic variance reduced algorithms.
method Introducing a simple stochastic variance reduced algorithm (MiG) with fast convergence rates.
result MiG achieves best-known convergence rates for both strongly and non-strongly convex problems.
New lower bounds for gradient methods in strongly convex finite-sum optimization.
problem Developing tight lower bounds for randomized gradient methods in finite-sum optimization.
method Deriving tight lower complexity bounds for SAG, SAGA, SVRG, SARAH, and related methods.
result Tight matches between lower bounds and upper bounds for various methods under specific conditions.
New optimal step sizes and mini-batch sizes for SAGA.
problem Finding optimal step sizes and mini-batch sizes for SAGA.
method Provided closed-form expressions for expected smoothness constant and suggested new step sizes and mini-batch sizes.
result Total complexity of SAGA decreases linearly with mini-batch size up to an optimal value.
In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respecti…
In this paper, we propose a simple variant of the original stochastic variance reduction gradient (SVRG), where hereafter we refer to as the variance reduced stochastic gradient descent (VR-SGD). Different from the choices of the snapshot point and starting point in SVRG and its proximal variant, Prox-SVRG, the two vec…