3 ms·

Theoretically yes, but: typically with neural networks, and esp. deep networks with millions or billions of parameters, 2nd order methods which require calculat

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.

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.