Title: An Investigation of Newton-Sketch and Subsampled Newton Methods,
Abstract: The concepts of sketching and subsampling have recently received much
attention by the optimization and statistics communities. In this paper, we
study Newton-Sketch and Subsampled Newton (SSN) methods for the finite-sum
optimization problem. We consider practical versions of the two methods in
which the Newton equations are solved approximately using the conjugate
gradient (CG) method or a stochastic gradient iteration. We establish new
complexity results for the SSN-CG method that exploit the spectral properties
of CG. Controlled numerical experiments compare the relative strengths of
Newton-Sketch and SSN methods and show that for many finite-sum problems, they
are far more efficient than SVRG, a popular first-order method.