SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums

We present a principled approach for designing stochastic Newton methods for solving finite sum optimization problems. Our approach has two steps. First, we rewrite 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. By design, methods developed using our approach are incremental, in that they require only a single data point per iteration. Using our approach, we develop a new Stochastic Average Newton (SAN) method, which is incremental and cheap to implement when solving regularized generalized linear models. 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, such as SAG and SVRG.