An investigation of Newton-Sketch and subsampled Newton methods

ABSTRACT

Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.

Keywords:

• Sketching
• subsampling
• Newton's method
• machine learning
• stochastic optimization

2010 Mathematics Subject Classifications:

• 49M15
• 90C30
• 65K05

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 $b=\{n/100,n/50,n/10,n/5,n/2,n,2n,5n,10n\}$

Additional information

Funding

This firsr and second author was supported by the Defense Advanced Research Projects Agency (DARPA). This third author was supported by the Office of Naval Research grant N00014-14-1-0313 P00003, and by National Science Foundation grant DMS-1620022.

Notes on contributors

Albert S. Berahas

Albert S. Berahas is currently a Postdoctoral Research Fellow in the Industrial & Systems Engineering department at Lehigh University working with Professors Katya Scheinberg (Cornell University), Frank E. Curtis and Martin Takáǎ. Prior to this appointment, he was a Postdoctoral Research Fellow in the Industrial Engineering and Management Sciences department at Northwestern University working under the supervision of Professor Jorge Nocedal. Berahas completed his PhD studies in Applied Mathematics in 2018, advised by Professor Jorge Nocedal. The title of his dissertation was ‘Methods for Large Scale Nonlinear and Stochastic Optimization’. Berahas has received the ESAM Outstanding Teaching Assistant Award, the Walter P. Murphy Fellowship and the John N. Nicholson Fellowship. His research interests include optimization algorithms for machine learning, convex optimization and analysis, derivative-free optimization and distributed optimization.

Raghu Bollapragada

Raghu Bollapragada is currently a Postdoctoral Researcher in the Mathematics and Computer Science Division at Argonne National Laboratory working with Dr Stefan Wild. He completed his PhD studies in Industrial Engineering and Management Sciences in 2019, advised by Professor Jorge Nocedal. During his graduate study, he was a visiting researcher at INRIA, Paris, hosted by Professor Alexandre d'Aspremont. His research interests include nonlinear optimization and its applications in machine learning. He has received the IEMS Nemhauser Dissertation Award, the IEMS Arthur P. Hurter Award, the Royal E. Cabell terminal year fellowship and the Walter P. Murphy Fellowship at Northwestern University.

Jorge Nocedal

Jorge Nocedal is the Walter P. Murphy Professor in the department of Industrial Engineering and Management Sciences (IEMS) at Northwestern University. He also holds an appointment in the department of Engineering Sciences and Applied Mathematics. His interests are in optimization, both deterministic and stochastic, with emphasis on large-scale problems. He has served as editor-in-chief of the SIAM Journal and Optimization, and as chairman of the IEMS department. Currently, he directs the Center for Optimization and Statistical Learning at Northwestern University.