5 ms·

This applies to convex optimization. I am wondering if it could also be extended to neural networks too?

rwilson4 5y ago
Theoretically yes, but: typically with neural networks, and esp. deep networks with millions or billions of parameters, 2nd order methods which require calculating and factoring the matrix of 2nd derivatives are prohibitively expensive. 1st order methods such as gradient descent skip this, albeit with a tradeoff in convergence. The method proposed in this paper is impractical for large systems such as computer vision or language models.
- kxyvr 5y ago
  As a note, 2nd order methods do not require calculating the entire Hessian nor do they require factorizing the matrix. A trust-region method using Steihaug-Toint (truncated) CG or a Newton-Krylov method simply require Hessian-vector products, which are not particularly costly to compute. In fact, a forward-mode automatic differentiation (AD) method on an existing gradient calculation, which could also be done using AD, will calculate the Hessian-vector product at a cost of twice the gradient calculation. Though, AD is not required and this can be done by hand. Even if only a single Krylov iteration is done, there are many benefits to using this methodology to help handle the scaling of the problem. These algorithms are described fully in a book such as Numerical Optimization by Nocedal and Wright. The current paper does not directly affect most ML algorithms because it speaks directly to convex optimization. Most ML models are highly nonlinear, so globalization of the optimization algorithm is required. Here, globalization means something like a line-search or a trust-region to ensure convergence to a local minima. Convex problems using an appropriate algorithm and under the correct assumptions do not necessarily require the use of a globalization technique and will converge directly to a local min, which is now global due to convexity. Normally, this discussion is done in the context of interior point methods for linear cone problems and helps explain why globalization is not done for these algorithms. An example of this can be found in Convex Optimization by Boyd and Vandenberghe in section 11.5.3, but it's a well researched topic. The algorithm in this paper discusses a technique where they also don't require a typical globalization technique. Anyway, mostly I'm commenting to dispel the misconception that 2nd order method can not be applied to large scale problems. I've applied them successfully to problems with hundreds of millions of variables and they work just fine. Largely, their success is tied to how complicated the spectrum of the Hessian is, but that's a longer discussion.
  - patrick451 5y ago
    > Largely, their success is tied to how complicated the spectrum of the Hessian is, but that's a longer discussion. What does the "complexity" of a spectrum mean? Is this a statement about the uniqueness (or not) of the eigenvalues or something else entirely?
    - kxyvr 5y ago
      It has to do with whether the eigenvalues of the Hessian are well clustered or not. Generally, to get fast convergence near an optimal solution, the Newton system needs to be solved well enough. What well enough is can be difficult to determine and practically it's not calculated. However, if the spectrum of the Hessian is well clustered, then it doesn't take that many Krylov iterations to get an accurate solution. To be clear, how Krylov methods perform is an area of study that sits independent of optimization algorithms, but those results are applicable here. In fact, it's a slightly easier situation than normal because the Hessian is symmetric, so the spectrum is real and more exotic topics like pseudospectra don't need to be considered.
abeppu 5y ago
Aside from the other note about 2nd order derivatives being a blocker for most of the models we work with these days, and the fact that DL encounters non-convex loss functions, the other big difference is that we're used to training with SGD which only needs unbiased estimates of a gradient based on samples / batches. This family of approaches requires _actual_ derivatives, i.e. from looking at the whole dataset. If you have estimates of the gradient only, I think basically none of the convergence arguments in this hold. This is basically also why we don't already use LBFGS (which doesn't hold onto the full hessian).
brrrrrm 5y ago
You’d need to be careful of overfitting the network.
WithinReason 5y ago
Unfortunately absolutely not, for many reasons: 1. A neural network with ReLU activations (the most common one) effectively has a piecewise linear optimisation surface, so the 2nd derivative is 0 almost everywhere. No curvature, no Hessian. 2. 2nd order methods make an assumption that the optimisation surface is (close to) convex, which is very much not the case with neural networks. 3. Even if the above were not true, to measure the Hessian you would have to iterate through the entire training set to measure it before you could make take an optimisation step. 4. Representing the entire Hessian for a network with N parameters needs O(N²) space, where N is on the order of 10⁹, so you couldn't use a method that needs the whole Hessian. There are so-called Quasi-Newton methods that need O(N) space though, like L-BFGS. Neural networks need completely different optimisation methods, and there is no practically useful application of any of the Newton or Quasi-Newton methods for their optimisation.
- shoyer 5y ago
  > Neural networks need completely different optimisation methods, and there is no practically useful application of any of the Newton or Quasi-Newton methods for their optimisation. I don't think this is quite fair. There are several variations of 2nd order methods, notably KFAC and Shampoo, that seem to quite effective for large-scale neural network training, e.g., see the intro of this paper for an overview: https://openreview.net/forum?id=-t9LPHRYKmi https://openreview.net/forum?id=-t9LPHRYKmi
  - WithinReason 5y ago
    One of the authors is Donald Goldfarb, who is the G in BFGS, so maybe they are onto something. But I'm always suspicious if the tests shown in a paper are fair.
  - WithinReason 5y ago
    I checked the paper. The 2nd order method actually achieves 10 times worse minimum (it's much worse at minimisation), and the reason the results are better is because the network overfits less (Figure 3). The reviewers should have caught this!

Theoretically yes, but: typically with neural networks, and esp. deep networks with millions or billions of parameters, 2nd order methods which require calculating and factoring the matrix of 2nd derivatives are prohibitively expensive. 1st order methods such as gradient descent skip this, albeit with a tradeoff in convergence. The method proposed in this paper is impractical for large systems such as computer vision or language models.

kxyvr 5y ago
As a note, 2nd order methods do not require calculating the entire Hessian nor do they require factorizing the matrix. A trust-region method using Steihaug-Toint (truncated) CG or a Newton-Krylov method simply require Hessian-vector products, which are not particularly costly to compute. In fact, a forward-mode automatic differentiation (AD) method on an existing gradient calculation, which could also be done using AD, will calculate the Hessian-vector product at a cost of twice the gradient calculation. Though, AD is not required and this can be done by hand. Even if only a single Krylov iteration is done, there are many benefits to using this methodology to help handle the scaling of the problem. These algorithms are described fully in a book such as Numerical Optimization by Nocedal and Wright. The current paper does not directly affect most ML algorithms because it speaks directly to convex optimization. Most ML models are highly nonlinear, so globalization of the optimization algorithm is required. Here, globalization means something like a line-search or a trust-region to ensure convergence to a local minima. Convex problems using an appropriate algorithm and under the correct assumptions do not necessarily require the use of a globalization technique and will converge directly to a local min, which is now global due to convexity. Normally, this discussion is done in the context of interior point methods for linear cone problems and helps explain why globalization is not done for these algorithms. An example of this can be found in Convex Optimization by Boyd and Vandenberghe in section 11.5.3, but it's a well researched topic. The algorithm in this paper discusses a technique where they also don't require a typical globalization technique. Anyway, mostly I'm commenting to dispel the misconception that 2nd order method can not be applied to large scale problems. I've applied them successfully to problems with hundreds of millions of variables and they work just fine. Largely, their success is tied to how complicated the spectrum of the Hessian is, but that's a longer discussion.
- patrick451 5y ago
  > Largely, their success is tied to how complicated the spectrum of the Hessian is, but that's a longer discussion. What does the "complexity" of a spectrum mean? Is this a statement about the uniqueness (or not) of the eigenvalues or something else entirely?
  - kxyvr 5y ago
    It has to do with whether the eigenvalues of the Hessian are well clustered or not. Generally, to get fast convergence near an optimal solution, the Newton system needs to be solved well enough. What well enough is can be difficult to determine and practically it's not calculated. However, if the spectrum of the Hessian is well clustered, then it doesn't take that many Krylov iterations to get an accurate solution. To be clear, how Krylov methods perform is an area of study that sits independent of optimization algorithms, but those results are applicable here. In fact, it's a slightly easier situation than normal because the Hessian is symmetric, so the spectrum is real and more exotic topics like pseudospectra don't need to be considered.

abeppu 5y ago

Aside from the other note about 2nd order derivatives being a blocker for most of the models we work with these days, and the fact that DL encounters non-convex loss functions, the other big difference is that we're used to training with SGD which only needs unbiased estimates of a gradient based on samples / batches. This family of approaches requires _actual_ derivatives, i.e. from looking at the whole dataset. If you have estimates of the gradient only, I think basically none of the convergence arguments in this hold. This is basically also why we don't already use LBFGS (which doesn't hold onto the full hessian).

brrrrrm 5y ago

You’d need to be careful of overfitting the network.

WithinReason 5y ago

Unfortunately absolutely not, for many reasons: 1. A neural network with ReLU activations (the most common one) effectively has a piecewise linear optimisation surface, so the 2nd derivative is 0 almost everywhere. No curvature, no Hessian. 2. 2nd order methods make an assumption that the optimisation surface is (close to) convex, which is very much not the case with neural networks. 3. Even if the above were not true, to measure the Hessian you would have to iterate through the entire training set to measure it before you could make take an optimisation step. 4. Representing the entire Hessian for a network with N parameters needs O(N²) space, where N is on the order of 10⁹, so you couldn't use a method that needs the whole Hessian. There are so-called Quasi-Newton methods that need O(N) space though, like L-BFGS. Neural networks need completely different optimisation methods, and there is no practically useful application of any of the Newton or Quasi-Newton methods for their optimisation.

shoyer 5y ago
> Neural networks need completely different optimisation methods, and there is no practically useful application of any of the Newton or Quasi-Newton methods for their optimisation. I don't think this is quite fair. There are several variations of 2nd order methods, notably KFAC and Shampoo, that seem to quite effective for large-scale neural network training, e.g., see the intro of this paper for an overview: https://openreview.net/forum?id=-t9LPHRYKmi https://openreview.net/forum?id=-t9LPHRYKmi
- WithinReason 5y ago
  One of the authors is Donald Goldfarb, who is the G in BFGS, so maybe they are onto something. But I'm always suspicious if the tests shown in a paper are fair.
- WithinReason 5y ago
  I checked the paper. The 2nd order method actually achieves 10 times worse minimum (it's much worse at minimisation), and the reason the results are better is because the network overfits less (Figure 3). The reviewers should have caught this!