Second Order Stochastic Optimization in Linear Time

By Naman Agarwal, Brian Bullins, Elad Hazan. 2016

104 citations recorded by the source corpus.

Stochastic optimization and, in particular, first-order stochastic methods are a cornerstone of modern machine learning due to their extremely efficient per-iteration computational cost. Second-order methods, while able to provide faster per-iteration convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we develop a second-order stochastic method for optimization problems arising in machine learning based on novel matrix randomization techniques that match the per-iteration cost of gradient descent, yet enjoy the linear-convergence properties of second-order optimization. We also consider the special case of self-concordant functions where we show that a first order method can achieve linear convergence with guarantees independent of the condition number. We demonstrate significant speedups for training linear classifiers over several convex benchmarks.

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

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

Citations in the corpus

Stronger data poisoning attacks break data sanitization defenses (2018, methodology): “Computing inverse Hessian-vector products To efficiently compute ∂?̂? ∂x̃ in (10), we follow Koh and Liang (2017) and use a combination of fast Hessian-vector products (Pearlmutter 1994) and a conjugate gradient solver (Martens, 2010); see also Agarwal et al. (2016) and Muñoz-González et al.”
Automatic differentiation in machine learning: a survey (2015, background): “lotti (2007) C# AutoDiﬀ LIB R George Mason Univ., Dept. of Computer Science Shtof et al. (2013) http://autodiff.codeplex.com/ F#, C# DiﬀSharp OO F, R Maynooth University, Microsoft Research Cambridge Baydin et al. (2016a) http://diffsharp.github.io Fortran ADIFOR ST F, R Argonne National Laboratory ”
Estimating the Spectral Density of Large Implicit Matrices (2018, methodology): “More recently, these series have been proposed as an eﬃcient way to solve linear systems with the Hessian in support of second-order stochastic optimization (Agarwal et al., 2016), using a very similar procedure to that described in Section 3 but with Neumann series.”
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., 2016; Xu et al., 2016).”
A Generic Approach for Escaping Saddle points (2017, background): “In many practical settings that arise in machine learning, the time complexity of these oracle calls is linear in d [4, 29].”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “(Quasi-)Newton (second-order) methods [2, 3, 8, 14, 39, 41, 42] have been extensively explored for convex optimization problems [9].”
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage (2017, background): “There are also several papers [1, 12, 27] in which researchers try to improve the computational or storage footprint of convex optimization methods by sketching internal variables, such as Hessians.”
Approximation Methods for Bilevel Programming (2018, background): “It should be mentioned that such approximation has been previously used in diﬀerent forms (see e.g., [1]).”
Understanding Black-box Predictions via Influence Functions (2017, methodology): “We note that the original method of Agarwal et al. (2016) dealt only with generalized linear models, for which [ ∇ 2 θ L ( z i , ˆ θ )] v can be efﬁciently computed in O ( p ) time.”
Exact and Inexact Subsampled Newton Methods for Optimization (2016, methodology): “LiSSA is the method proposed in [1], wherein the inner solver is a semi-stochastic gradient iteration; i.”
A Swiss Army Infinitesimal Jackknife (2018, methodology): “In more high-dimensional examples with dense Hessian matrices, such as neural networks, one may need to turn to approximations such as stochastic second-order methods (Koh and Liang, 2017; Agarwal et al., 2017) and conjugate gradient (Wright and Nocedal, 1999).”
Optimization Methods for Large-Scale Machine Learning (2016, background): “If done appropriately, Hessian subsampling is robust and effective [2, 29, 122, 132].”
Influence Functions in Deep Learning Are Fragile (2020, methodology): “The Effect of Stochastic Estimation on inverse-Hessian Vector Product: For large deep networks, the inverse-Hessian Vector product is computed using stochastic estimation[10], as the exact Hessian matrix cannot be computed and inverted.”
Sub-sampled Newton Methods with Non-uniform Sampling (2016, methodology): “Also, in the presence of high non-uniformity among {Ai(w)}ni=1, factors κ̄ and κ̂ (see Definition (6)) which appear in SSN (uniform) [19], and LiSSA [1], can potentially be as large as Ω(nκ); see Section 3.5 for detailed discussions.”
Uncertainty Estimation with Infinitesimal Jackknife, Its Distribution and Mean-Field Approximation (2020, methodology): “(9 ), using either of the following two approaches Compute H − 1 ( W ∗ ) on D and the inverse Hessian-vector product exactly H Hessian-vector Compute the inverse Hessian-vector product approximately [1] Compute e k via mean-ﬁeld approximation eq.”
Cross-Loss Influence Functions to Explain Deep Network Representations (2020, methodology): “Koh and Liang (2017) leverage recent work (Agarwal et al., 2016) to eﬃciently estimate the inverse Hessian-vector product (HVP).”
An investigation of Newton-Sketch and subsampled Newton methods (2017, methodology): “4) LiSSA, a method similar to SSN-SGI, is analyzed in [1], and [3] compares the complexity of LiSSA, SSN-CG and Newton-Sketch.”