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