SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums

Jiabin Chen, Rui Yuan, Guillaume Garrigos, Robert M. Gower
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:279-318, 2022.

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).

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-chen22a, title = { SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums }, author = {Chen, Jiabin and Yuan, Rui and Garrigos, Guillaume and Gower, Robert M.}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {279--318}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/chen22a/chen22a.pdf}, url = {https://proceedings.mlr.press/v151/chen22a.html}, 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). } }
Endnote
%0 Conference Paper %T SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums %A Jiabin Chen %A Rui Yuan %A Guillaume Garrigos %A Robert M. Gower %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-chen22a %I PMLR %P 279--318 %U https://proceedings.mlr.press/v151/chen22a.html %V 151 %X 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).
APA
Chen, J., Yuan, R., Garrigos, G. & Gower, R.M.. (2022). SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:279-318 Available from https://proceedings.mlr.press/v151/chen22a.html.

Related Material