Second-Order Stochastic Optimization for Machine Learning in Linear Time

By Naman Agarwal, Brian Bullins, Elad Hazan. 2016

296 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Understanding the Origins of Bias in Word Embeddings (2018, methodology): “To overcome the computational barrier of using influence functions in large models, Koh & Liang (2017) use the LiSSA algorithm (Agarwal et al., 2017) to efficiently compute inverse Hessian vector products.”
Explaining Black Box Predictions and Unveiling Data Artifacts through Influence Functions (2020, methodology): “We also resort to the same stochastic estimation method, LiSSA (Agarwal et al., 2017), as in Koh and Liang (2017), and we deliberately reduce the size of our training sets.”
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.”
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.”
Machine Unlearning of Features and Labels (2021, background): “Overall, we find that the linear runtime bounds of the underlying algorithm hold in practice [47].”
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients (2018, background): “On the other hand, there has been recent efforts in performing efficient approximations of (2) in time comparable to that required for a gradient update ([2, 17, 22]).”
WoodFisher: Efficient Second-Order Approximation for Neural Network Compression (2020, methodology): “Neumann-series-based methods [35, 36] exploit the infinite series expression for the inverse of a matrix with eigenspectrum in [0, 1].”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, methodology): “References 279 [1] Naman Agarwal, Brian Bullins, and Elad Hazan.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “This can be improved with preconditioning to O((n+ √ dL/λ)d) for large n [2].”
An investigation of Newton-Sketch and subsampled Newton methods (2017, methodology): “We consider two iterative methods: the conjugate gradient method, and a stochastic gradient iteration [1] that is inspired by (but it not equivalent to) the stochastic gradient method of Robbins and Monro [17].”
WoodFisher: Efficient second-order approximations for model compression (2020, background): “These kind of methods (Krishnan et al., 2018; Agarwal et al., 2016) essentially exploit the following result in Eqn.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “If done appropriately, Hessian subsampling is robust and effective [2, 28, 122, 132].”
TRAK: Attributing Model Behavior at Scale (2023, unknown): “We use an existing PyTorch implementation14 that uses the stochastic approximation of inverse-Hessian-vector products using the LISSA (Agarwal et al., 2017) algorithm as done in Koh & Liang (2017).”
Regularization via Mass Transportation (2017, background): “For a comprehensive review of first- and the second-order stochastic gradient algorithms we refer to [2] and the references therein.”
Lower Bounds for Higher-Order Convex Optimization (2017, background): “Notably, the fastest theoretical running times for both convex (Agarwal et al., 2016; Xu et al., 2016; Bollapragada et al., 2016) and nonconvex (Agarwal et al.”