Fast Exact Multiplication by the Hessian

By Barak A. Pearlmutter. 1994

Just storing the Hessian H (the matrix of second derivatives 2E/wiwj of the error E with respect to each pair of weights) of a large neural network is difficult. Since a common use of a large matrix like H is to compute its product with various vectors, we derive a technique that directly calculates Hv, where v is an arbitrary vector. To calculate Hv, we first define a differential operator Rv{f(w)} = (/r)f(w rv)|r=0, note that Rv{w} = Hv and Rv{w} = v, and then apply Rv{} to the equations used to compute w. The result is an exact and numerically stable procedure for computing Hv, which takes about as much computation, and is about as local, as a gradient evaluation. We then apply the technique to a one pass gradient calculation algorithm (backpropagation), a relaxation gradient calculation algorithm (recurrent backpropagation), and two stochastic gradient calculation algorithms (Boltzmann machines and weight perturbation). Finally, we show that this technique can be used at the heart of many iterative techniques for computing various properties of H, obviating any need to calculate the full Hessian.

Subfields: 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 Optimization & Training

Citations in the corpus

Revisiting Natural Gradient for Deep Networks (2013, methodology): “The core idea behind it is to make use of the forward pass (renamed to R-operator in Pearlmutter (1994)) and backward pass of automatic differentiation to compute efﬁcient products between Jacobian or Hessian matrices and vectors.”
Theano: new features and speed improvements (2012, methodology): “The pipeline relies on the “R-operator”, introduced by Pearlmutter (1994), which is a mathematical operator that given a function f ( θ ) , f : R M → R N , the current parameter conﬁguration θ t ∈ R M and a vector γ ∈ R M , efﬁciently computes the “Jacobian-vector” product θ = θ t γ , where θ = θ t…”
An Investigation into Neural Net Optimization via Hessian Eigenvalue Density (2019, methodology): “Explicit representation of the Hessian matrix is infeasible when n is large, but using Pearlmutter’s trick [22] we are able to compute Hessian-vector products for any chosen vector.”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “(2018), the Jacobian-vector product can be efficiently evaluated in tasks like training neural networks and the computation time of the gradient and the Jacobian-vector product is comparable (Pearlmutter, 1994).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “In this paper, we mainly restrict our attention to subsam-Stochastic pled Newton methods and consider problems of a moderate dimension where it is computationally eﬃcient to perform subsampled Hessian-vector operations (Wer-bos, 1988; Pearlmutter, 1994).”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “ et al.(2017) in the context of games, consensus optimization is a second-order yet ecient method, as it only uses a Hessian-vector multiplication whose cost is the same as two gradient evaluations (Pearlmutter, 1994). We dene the CO update as: ! t+1 = ! t (v(! t) + rH(! t)) (CO) where H(!) = 1 2 kv”
Theano: A Python framework for fast computation of mathematical expressions (2016, background): “It is also possible to clone with replacements, which make it possible to plug together different disconnected graphs, making inputs into intermediate Variable nodes.”
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization (2014, positive): “Algorithm 2 Obtaining the Lanczos vectors Require: g ← − Require: ∆ θ (The past weight update) ∂θ 2 (Implemented efﬁcient through L-Op (Pearlmutter, 1994))”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “ility to maintain classical convergence rate guarantees. Like many iterative linear system techniques, CG applied to (6.4b) does not require access to the Hessian itself, only Hessian-vector products [121]. It is in this sense that such a method may be called Hessian-free. This is ideal when such pr”
Distributional Smoothing with Virtual Adversarial Training (2015, background): “e. From now on, we refer to the training of the regularized likelihood (4) based on (12) as virtual adversarial training (VAT). 1For many models including neural networks, Hd can be computed exactly (Pearlmutter, 1994). We forgo this computation in this very paper, however, because the implementatio”
Empirical Analysis of the Hessian of Over-Parametrized Neural Networks (2017, methodology): “The computational complexity issues have been attempted to be resolved using the R -operator of Pearlmutter [1994].”
Understanding Black-box Predictions via Influence Functions (2017, methodology): “We discuss two techniques for approximating s test , both relying on the fact that the HVP of a single term in H ˆ θ , [ ∇ 2 θ L ( z i , ˆ θ )] v , can be computed for arbitrary v in the same time that ∇ θ L ( z i , ˆ θ ) would take, which is typically O ( p ) (Pearlmutter, 1994).”
Dataset Distillation (2018, background): “Speciﬁcally, back-gradient optimization formulates the necessary second order terms into efﬁcient Hessian-vector products (Pearlmutter, 1994), which can be easily calculated with modern automatic differentiation systems such as PyTorch (Paszke et al., 2017).”
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.”
Hyperparameter optimization with approximate gradient (2016, methodology): “Efﬁcient schemes for multiplication by the Hessian can be derived for least squares, logistic regression (Lin et al., 2008) and other general loss functions (Pearlmutter, 1994).”
Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization (2017, methodology): “The computation of the matrices ∇x c∇wL and ∇2 wL can also be avoided using Hessianvector products [30]:”
Deep learning in neural networks: An overview (2014, methodology): “19 2011: Hessian-Free Optimization for RNNs Also in 2011 it was shown (Martens and Sutskever, 2011) that Hessian-free optimization (e.g., Møller, 1993; Pearlmutter, 1994; Schraudolph, 2002) (Sec.”