In the hierarchy of optimization, first-order methods like Stochastic Gradient Descent (SGD) are the workhorses of modern machine learning. They are computationally cheap, scaling linearly with the number of parameters. However, they are "blind" to the landscape's curvature, often requiring tedious hyperparameter tuning to find a stable learning rate.
Second-order methods, such as Newton’s method, use the Hessian matrix (the second derivative) to understand this curvature. This allows them to take more direct steps toward the optimum, often achieving "superlinear" convergence. The catch is the "matrix inversion tax": calculating and inverting a $d \times d$ Hessian matrix costs $O(d^3)$ time, which is catastrophic for models with millions of parameters.
A growing body of research suggests we can bypass this tax. By recognizing that most updates in machine learning are low-rank, we can use clever matrix identities to maintain an inverse Hessian in $O(d^2)$ or even $O(d)$ time.
The Geometry of a Single Data Point
The core intuition starts with the structure of the Hessian in Generalized Linear Models (GLMs). When we process a single new data point $x$, the change to the Hessian matrix is not arbitrary; it is typically a rank-1 update (an outer product of the feature vector, $xx^T$).
As Francis Bach and Eric Moulines demonstrated in Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n), we can build a local quadratic model of the objective function by incrementally incorporating these rank-1 updates. Because the update is so simple, we don't need to re-invert the whole matrix from scratch.
The Sherman-Morrison Shortcut
The mathematical engine behind this efficiency is the Sherman-Morrison-Woodbury formula. This identity allows us to calculate the inverse of a matrix after a low-rank perturbation using only the previous inverse.
In Online Newton Step Algorithm with Estimated Gradient, Binbin Liu and Huan Liu use this trick to reduce the complexity of the Online Newton Step (ONS) from cubic to quadratic. Instead of a full inversion, the update becomes a series of matrix-vector multiplications. This same principle is applied by Mrinmay Sen and Chalavadi Krishna Mohan in pFedSOP to bring second-order convergence to resource-constrained devices in Federated Learning.
Scaling to High Dimensions
While $O(d^2)$ is better than $O(d^3)$, it is still too slow for the massive parameter counts of deep learning. Researchers have developed several strategies to push this toward linear $O(d)$ complexity:
- Kronecker Factorization: In MKOR, M. Hamed Mozaffari and colleagues exploit the fact that Hessians in neural networks often have a Kronecker product structure. By applying rank-1 updates to these smaller factors, they achieve significant speedups over standard optimizers like LAMB.
- Matrix Sketching: Dongxie Wen and Shuai Li introduce FORKS, which uses incremental matrix sketching to maintain a compressed version of the Hessian. This allows second-order online learning to run in linear time relative to the model's budget.
- Hessian Averaging: Sen Na and Michael W. Mahoney show in Hessian Averaging in Stochastic Newton Methods that simply aggregating past noisy Hessian estimates can reclaim superlinear convergence without increasing per-iteration costs.
Applications Across the Spectrum
This "low-rank" philosophy is not limited to standard supervised learning. It has proven transformative in several niche areas:
- Reinforcement Learning: Mohamad Amin Sharifi Kolarijani and Peyman Mohajerin Esfahani developed Quasi-Policy Iteration, which uses the Woodbury identity to update value functions in quadratic time, bypassing the cubic cost of policy evaluation.
- Active Learning: In Fast Bayesian Updates for Deep Learning, Marek Herde and colleagues treat the last layer of a network as a Bayesian model. By using low-rank updates for the inverse Hessian, they update models 1,700 times faster than full retraining.
- Sparse Regression: Johan Larsson and Jonas Wallin use the sweep operator and Schur complements in The Hessian Screening Rule to incrementally update the Hessian as predictors are added or removed, speeding up Lasso-style problems.
Why It Works: The Stability of Curvature
The fundamental reason these methods succeed is that curvature often changes more slowly than the gradient. As Oren Mangoubi notes in Faster Sampling from Log-Concave Densities, the Hessian of certain log-concave densities is stable enough to allow for incremental updates rather than full recomputation.
By treating the optimization process as a continuous path of low-rank perturbations—rather than a series of disconnected, expensive inversions—researchers like Yuting Ye and Lihua Lei in their work on HONES have shown that we can maintain high-precision, second-order updates even in high-speed, large-scale environments.