mlsanityData to 7 Oct 2026

Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches

arXiv 2206.02702 ↗First posted 6 Jun 2022math.OC cs.LG stat.MLcited by 9

Not on the map. Why?

Abstract (arXiv)

Stochastic variance reduction has proven effective at accelerating first-order algorithms for solving convex finite-sum optimization tasks such as empirical risk minimization. Incorporating second-order information has proven helpful in further improving the performance of these first-order methods. Yet, comparatively little is known about the benefits of using variance reduction to accelerate popular stochastic second-order methods such as Subsampled Newton. To address this, we propose Stochastic Variance-Reduced Newton (SVRN), a finite-sum minimization algorithm that provably accelerates existing stochastic Newton methods from O(αlog(1/ε)) to Obig(fraclog(1/ε)log(n)big) passes over the data, i.e., by a factor of O(αlog(n)), where n is the number of sum components and α is the approximation factor in the Hessian estimate. Surprisingly, this acceleration gets more significant the larger the data size n, which is a unique property of SVRN. Our algorithm retains the key advantages of Newton-type methods, such as easily parallelizable large-batch operations and a simple unit step size. We use SVRN to accelerate Subsampled Newton and Iterative Hessian Sketch algorithms, and show that it compares favorably to popular first-order methods with variance~reduction.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 31 of its 58 references that are in the map. First posted on arXiv 6 Jun 2022.

Builds on

31 of 58 references.

References · 31

  1. 2021Convex optimizationcited by 2,479
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  3. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  4. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  5. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  6. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  7. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  8. 2020Determinantal Point Processes in Randomized Numerical Linear Algebracited by 41
  9. 2015A Linearly-Convergent Stochastic L-BFGS Algorithmcited by 39
  10. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  11. 2016Exact and Inexact Subsampled Newton Methods for Optimizationcited by 38
  12. 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
19 more
  1. 2014Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squarescited by 34
  2. 2015Convergence rates of sub-sampled Newton methodscited by 32
  3. 2016Stochastic Block BFGS: Squeezing More Curvature out of Datacited by 24
  4. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
  5. 2021Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Updatecited by 23
  6. 2014Competing with the Empirical Risk Minimizer in a Single Passcited by 20
  7. 2020Sparse sketches with small inversion biascited by 19
  8. 2017An Investigation of Newton-Sketch and Subsampled Newton Methodscited by 18
  9. 2019Distributed estimation of the inverse Hessian by determinantal averagingcited by 16
  10. 2016Solving Ridge Regression using Sketched Preconditioned SVRGcited by 15
  11. 2022Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergencecited by 14
  12. 2020Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularizationcited by 12
  13. 2017IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Ratecited by 11
  14. 2015Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Settingcited by 10
  15. 2015Weighted SGD for ℓp Regression with Randomized Preconditioningcited by 6
  16. 2017Tracking the gradients using the Hessian: A new look at variance reducing stochastic methodscited by 5
  17. 2019Acceleration of SVRG and Katyusha X by Inexact Preconditioningcited by 5
  18. 2017Batch-Expansion Training: An Efficient Optimization Frameworkcited by 4
  19. 2018Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularizationcited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 4; 2025: 3.

9 papers.

  1. 2024MARS: Unleashing the Power of Variance Reduction for Training Large Modelscited by 59
  2. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  3. 2023PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimatescited by 10
  4. 2025MARS-M: When Variance Reduction Meets Matricescited by 10
  5. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  6. 2024Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradientscited by 3
  7. 2024Distributed Least Squares in Small Space via Sketching and Bias Reductioncited by 3
  8. 2023Sharpened Lazy Incremental Quasi-Newton Methodcited by 1
  9. 2025SVRG and Beyond via Posterior Correctioncited by 0