Training complex machine learning models often involves navigating highly irregular "loss landscapes." While first-order optimization methods like Stochastic Gradient Descent (SGD) are the industry standard due to their simplicity, they often struggle with ill-conditioned problems—scenarios where the landscape contains narrow, steep valleys that cause the optimizer to oscillate. Second-order methods, which leverage the Hessian matrix to understand the landscape's curvature, offer a more direct path to the optimum but have historically been sidelined due to extreme computational costs and difficulties with nonconvexity.
This paper, recently published in Information and Inference: A Journal of the IMA, provides a rigorous theoretical foundation for Newton-MR, a second-order algorithm designed to be both computationally efficient and robust in nonconvex settings, even when using highly approximated (inexact) Hessian information.
The Challenge of Second-Order Optimization
Second-order methods face two primary hurdles in deep learning:
- Computational Overhead: Calculating, storing, and inverting a full Hessian matrix for a model with millions of parameters is mathematically prohibitive.
- Nonconvexity: In deep learning, the landscape is "bumpy." Standard Newton methods typically assume the Hessian is positive definite (all curvature is upward). In nonconvex regions, curvature can be flat or downward, which can cause standard algorithms to diverge or fail.
To mitigate the computational cost, researchers often use "inexact" Hessians—approximations created by sub-sampling only a small fraction of the training data. However, until now, there has been a lack of clear theoretical understanding regarding how these approximations affect convergence in nonconvex landscapes.
The Newton-MR Approach
The authors extend the Newton-MR algorithm, which distinguishes itself by using the MINRES (Minimum Residual) solver rather than the more common Conjugate Gradient (CG) method. MINRES is fundamentally better suited for nonconvexity because it does not require the Hessian to be positive definite to function correctly.
Key Innovations
- Inexact Hessian Modeling: The algorithm is designed to handle an approximated Hessian $\bar{H}(x) = H(x) + E$, where $E$ represents the error from sub-sampling. The authors prove that the algorithm remains stable even when this error is significant.
- $\sigma$-Limited Curvature (LC) Detection: The algorithm includes a mechanism to detect when the search direction is heading into a region of negative or near-zero curvature. When an "LC direction" is detected, the algorithm intelligently switches strategies to ensure it continues to find a descent path.
- Avoiding Damping: Many Newton variants use "damping" (adding a term like $\lambda I$ to the Hessian) to force it to be positive definite. This paper demonstrates that damping often distorts the very curvature information the algorithm needs. Newton-MR avoids this, preserving the integrity of the second-order information.
Theoretical and Empirical Results
The paper establishes several landmark complexity guarantees:
- Optimal Complexity: For general nonconvex functions, Newton-MR achieves an iteration complexity of $O(\epsilon_g^{-2})$, which is theoretically optimal for this class of second-order methods.
- Global Linear Convergence: For functions satisfying the Polyak-Łojasiewicz (PL) condition—a class of nonconvex functions that behave globally like convex functions—the algorithm achieves a global linear convergence rate.
- Robustness to Noise: Remarkably, the algorithm is shown to converge regardless of how "noisy" the Hessian approximation is or how loosely the sub-problem is solved.
Experimental Validation
The authors tested Newton-MR on benchmarks including MNIST, CIFAR-10, and Gas Sensor Array datasets (using both Feed-Forward and Recurrent Neural Networks). Their experiments revealed that using only 1% to 10% of the data to estimate the Hessian provided nearly the same convergence per iteration as using the full dataset, but with a massive reduction in computational effort. Furthermore, Newton-MR consistently reached lower loss values faster than Newton-CG and standard Trust-Region methods.
Conclusion
This research bridges the gap between theoretical optimization and practical machine learning engineering. By proving that Newton-MR is robust to inexact Hessian information, the authors provide a path forward for using sophisticated second-order information in large-scale, nonconvex problems. Future work will look to extend these guarantees to "fully stochastic" settings where the gradient itself is also a noisy sample.
Summary updated