Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence

By Mert Pilanci, Martin J. Wainwright. 2015

294 citations recorded by the source corpus.

We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, with convergence and complexity guarantees that are independent of condition numbers and related problem-dependent quantities. Given a suitable initialization, similar guarantees also hold for strongly convex and smooth objectives without self-concordance. When implemented using randomized projections based on a sub-sampled Hadamard basis, the algorithm typically has substantially lower complexity than Newton's method. We also describe extensions of our methods to programs involving convex constraints that are equipped with self-concordant barriers. We discuss and illustrate applications to linear programs, quadratic programs with convex constraints, logistic regression and other generalized linear models, as well as semidefinite programs.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “In order to further scale these methods to high-dimensional datasets or models with a large number of parameters, there has been a rich body of research in developing computationally efficient approximations to the Hessian matrix (Becker et al., 1988; Liu and Nocedal, 1989; Martens and Grosse, 2015;”
Optimization Methods for Large-Scale Machine Learning (2016, background): “If done appropriately, Hessian subsampling is robust and effective [2, 28, 122, 132].”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Our GIANT method is motivated by the subsampled Newton method [33, 42, 25].”
Shampoo: Preconditioned Stochastic Tensor Optimization (2018, background): “, 2011; Kingma and Ba, 2014), a sketched version (Gonen and Shalev-Shwartz, 2015; Pilanci and Wainwright, 2017), or various estimations thereof (Erdogdu and Montanari, 2015; Agarwal et al.”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “[41] Mert Pilanci and Martin J Wainwright.”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “The philosophy also differs from stochastic second order methods such as subsampled Newton [9,25,28,29], incremental Hessian [10], stochastic dual Newton ascent [26], and stochastic quasi-Newton methods [14, 17–19, 21, 31].”
DUAL-LOCO: Distributing Statistical Estimation Using Random Projections (2015, methodology): “They have been extensively used to construct e cient algorithms when the samplesize is large in a variety of domains such as: nearest neighbours [8], matrix factorization [9], least squares [10, 11] and recently in the context of optimization [12].”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “In this paper, we argue that the three reasons above for not using Newton method can be circumvented to obtain competitive algorithms: (1) high absolute precisions are indeed not needed for machine learning, but faced with strongly ill-conditioned problems, even a low-precision solution requires sec”
Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, methodology): “A different approach is to use momentum methods [60] or random projections [44]–[46], [56] to accelerate convergence.”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, background): “On the other hand several papers investigate the use of second order methods in this framework and demonstrate advantages in some important problems if the second order methods are correctly implemented, [4, 7, 5, 10, 11, 18, 36, 37, 34, 40, 41].”
Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms (2016, methodology): “he problem of nding the inverse of an n ninvertible matrix Acan be characterized as nding the solution to either of the inverse equations1 AX = I or XA= I:Our methods make use of randomized sketching [30, 15, 29, 31] to reduce the dimension of the inverse equations in an iterative fashion. To the be”
Sub-Sampled Newton Methods II: Local Convergence Rates (2016, unknown): “For example, one can formulate the problem of low-rank distance metric learning as the following convex programming (this formulation has been adopted from an example in [36])”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, methodology): “Our work here, however, is more closely related to a recent work [18](Newton Sketch), which considers a similar class of problems and proposes sketching the Hessian using random sub-Gaussian matrices or randomized orthonormal systems.”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “that fis strongly convex and the Hessians ∇2fiare Lipschitz continuous (with a uniform constant). Based on the existence of a suitable square-root decomposition of the Hessian, Pilanci and Wainwright [62] propose a Newton sketch method for general convex, smooth programs. In [10], the numerical perf”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, methodology): “To be more specific, recall that quasi-Newton rules aim to maintain an estimate of the inverse Hessian Xk, adjusting it every iteration so that the inverse Hessian acts appropriately in a particular direction, while enforcing symmetry: Xk(∇f(wk)−∇f(wk−1)) = wk − wk−1, Xk = X>k .”
Sub-Sampled Newton Methods I: Globally Convergent Algorithms (2016, background): “In such regime (where n, p 1 but n is not too large), similar results can be found in [10, 31, 38, 21].”