Abstract
Second-order optimization methods are among the most widely used optimization approaches for convex optimization problems, and have recently been used to optimize non-convex optimization problems such as deep learning models. The widely used second-order optimization methods such as quasi-Newton methods generally provide curvature information by approximating the Hessian using the secant equation. However, the secant equation becomes insipid in approximating the Newton step owing to its use of the first-order derivatives. In this study, we propose an approximate Newton sketch-based stochastic optimization algorithm for large-scale empirical risk minimization. Specifically, we compute a partial column Hessian of size ($d\times m$) with $m\ll d$ randomly selected variables, then use the Nyström method to better approximate the full Hessian matrix. To further reduce the computational complexity per iteration, we directly compute the update step ($\Delta\boldsymbol{w}$) without computing and storing the full Hessian or its inverse. We then integrate our approximated Hessian with stochastic gradient descent and stochastic variance-reduced gradient methods. The results of numerical experiments on both convex and non-convex functions show that the proposed approach was able to obtain a better approximation of Newton's method, exhibiting performance competitive with that of state-of-the-art first-order and stochastic quasi-Newton methods. Furthermore, we provide a theoretical convergence analysis for convex functions.
Introduction
In the landscape of large-scale machine learning, optimization algorithms generally fall into two categories: first-order and second-order methods. First-order methods, such as Stochastic Gradient Descent (SGD), Adam, and SVRG, are the industry standard due to their low computational cost per iteration. However, these methods often suffer from slow convergence, high sensitivity to hyperparameter tuning, and difficulties navigating ill-conditioned loss surfaces.
Second-order methods, specifically Newton’s method, utilize the Hessian matrix to incorporate curvature information, allowing for much more direct paths to the minimum. The primary bottleneck for these methods is the Hessian matrix itself; for a model with $d$ parameters, the Hessian is a $d \times d$ matrix. Storing and inverting this matrix requires $O(d^2)$ space and $O(d^3)$ time, which is infeasible for modern neural networks with millions of parameters. While quasi-Newton methods like L-BFGS attempt to approximate this curvature using the secant equation, they often rely on "insipid" first-order information that fails to capture the true geometry of the loss surface. This paper introduces Nys-Newton, a framework that leverages the Nyström method to provide a high-quality Hessian approximation at a fraction of the traditional cost.
The Nys-Newton Framework
Nyström Hessian Approximation
The core innovation of Nys-Newton is the application of the Nyström method—traditionally used for approximating large kernel matrices—to the Hessian. Instead of computing the full $d \times d$ matrix, the algorithm:
- Samples $m$ random variables where $m \ll d$.
- Computes a partial Hessian, resulting in a thin $d \times m$ matrix.
- Reconstructs a low-rank approximation of the full Hessian using the Nyström formula.
This approach captures more robust curvature information than the secant equations used in quasi-Newton methods, as it directly samples the second-order derivatives of the objective function.
Computational Efficiency via Woodbury Identity
To ensure the method is viable for high-dimensional problems, the authors avoid the explicit construction of the full approximated Hessian. By utilizing the Woodbury Matrix Identity (also known as the Matrix Inversion Lemma), the Newton update step ($\Delta\boldsymbol{w}$) can be computed using only small matrix operations. This reduces the per-iteration complexity to $O(dm)$, making it linearly scalable with respect to the number of parameters. Unlike previous "Newton Sketch" methods, Nys-Newton does not require the computationally expensive square root of the Hessian, further streamlining the optimization process.
Algorithmic Integration
The framework is versatile and can be integrated into existing stochastic optimization routines. The paper specifically details two implementations:
- Nyström-SGD: Enhances standard SGD with Nyström curvature information.
- Nyström-SVRG: Combines the approximation with Stochastic Variance-Reduced Gradient methods to achieve even more precise convergence near the optimum.
Empirical Evaluation
The authors evaluated Nys-Newton against state-of-the-art first-order and stochastic quasi-Newton methods (such as SQN and oBFGS) across various tasks:
- Convex Optimization: On datasets like real-sim, adult, and mnist, Nys-Newton reached lower optimization errors significantly faster than Adam and other second-order approximations. It demonstrated remarkable stability across different regularization parameters ($\lambda$), where other methods often failed or slowed down.
- Large-Scale Deep Learning: The method was tested on ImageNet using ResNet152 and EfficientNet architectures. In these non-convex settings, Nys-Newton outperformed both SGD and KFAC (a popular Kronecker-factored approximate second-order optimizer), achieving lower training loss and higher test accuracy within the same number of training epochs.
Theoretical Contributions
Beyond empirical success, the paper provides a rigorous mathematical foundation for the method. The authors prove that Nys-Newton achieves linear convergence when paired with SVRG and linear-quadratic convergence when paired with SGD for convex functions. This theoretical guarantee confirms that the Nyström sketch retains enough curvature information to maintain the superior convergence properties of second-order optimization.
Conclusion and Future Work
Nys-Curve presents a scalable bridge between first-order efficiency and second-order precision. By utilizing the Nyström method to sketch the Hessian, it provides a robust, stable, and computationally efficient alternative to standard optimizers. While the method currently achieves linear-quadratic convergence, future research may explore ways to reach superlinear convergence—the gold standard of Newton methods—within the Nyström framework. Additionally, further optimization of the sampling frequency for the partial Hessian could further reduce the computational overhead, making it even more competitive for ultra-large-scale deep learning tasks.
Summary updated