SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
arXiv:2106.10520
Abstract
We present a principled approach for designing stochastic Newton methods for solving finite sum optimization problems. Our approach has two steps. First, we re-write the stationarity conditions as a system of nonlinear equations that associates each data point to a new row. Second, we apply a Subsampled Newton Raphson method to solve this system of nonlinear equations. Using our approach, we develop a new Stochastic Average Newton (SAN) method, which is incremental by design, in that it requires only a single data point per iteration. It is also cheap to implement when solving regularized generalized linear models, with a cost per iteration of the order of the number of the parameters. We show through extensive numerical experiments that SAN requires no knowledge about the problem, neither parameter tuning, while remaining competitive as compared to classical variance reduced gradient methods (e.g. SAG and SVRG), incremental Newton and quasi-Newton methods (e.g. SNM, IQN).
arXiv commentAccepted at AISTATS 2022
References in corpus (10)
- Scikit-learn: Machine Learning in Python
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Global Convergence of Online Limited Memory BFGS
- The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
- Convergence rates of sub-sampled Newton methods
- Stochastic Dual Ascent for Solving Linear Systems
- SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
- Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
- Convergence of Newton-MR under Inexact Hessian Information