In optimization, second-order methods—which leverage the curvature of the loss landscape via the Hessian matrix—offer a compelling promise: faster convergence, better stability, and a resistance to the ill-conditioned landscapes that plague first-order gradient descent.
Yet, in large-scale machine learning and optimization, second-order methods face a notorious bottleneck. Computing and inverting a $d \times d$ Hessian matrix incurs a prohibitive $O(d^3)$ computational cost and $O(d^2)$ memory footprint. When $d$ represents millions of neural network parameters or massive semidefinite programming constraints, direct inversion becomes impossible.
A powerful family of techniques bypasses this bottleneck entirely. The core insight is simple: we rarely need to compute a new Hessian from scratch. Instead, as an optimization algorithm progresses, the changes to the curvature matrix can be modeled as low-rank perturbations. By pairing this structural property with classical algebraic identities—specifically the Sherman-Morrison-Woodbury formula—researchers can maintain and update the inverse Hessian analytically in quadratic ($O(d^2)$) or even linear ($O(d)$) time.
The Core Mechanism: The Woodbury Identity
To understand why this direction works, we must look at the mathematics of the Sherman-Morrison-Woodbury identity. Suppose we have a base matrix $A$ whose inverse $A^{-1}$ is already known. If we perturb $A$ by adding a low-rank correction $U V^T$ (where $U$ and $V$ are $d \times k$ matrices with $k \ll d$), the Woodbury identity allows us to compute the new inverse analytically:
$$(A + U V^T)^{-1} = A^{-1} - A^{-1} U (I_k + V^T A^{-1} U)^{-1} V^T A^{-1}$$
The computational magic lies in the term $(I_k + V^T A^{-1} U)^{-1}$. Instead of inverting a massive $d \times d$ matrix, we only need to invert a small $k \times k$ matrix. When $k=1$ (a rank-1 update), this reduces to the Sherman-Morrison formula, requiring only a scalar division.
By framing optimization steps as low-rank corrections to an existing curvature estimate, we can propagate updates to the inverse Hessian instantly, completely avoiding the $O(d^3)$ matrix inversion loop.
Accelerating Quasi-Newton Methods
Quasi-Newton algorithms, such as BFGS and Symmetric Rank-1 (SR1), are built entirely on this principle. Instead of calculating the true Hessian, they construct a running approximation using successive gradient evaluations.
Recent work has focused on making these updates more robust and scalable. For instance, Dachao Lin et al. and Zhuanghua Liu et al. demonstrated that greedy or randomized SR1 updates can exactly recover the Hessian matrix of a quadratic function in a finite number of steps. Crucially, they proved that these methods achieve "condition-number-free" superlinear convergence, meaning their speed does not degrade even when the optimization landscape is highly stretched or poorly scaled.
To bring these benefits to distributed and structured optimization, researchers embed the Sherman-Morrison formula directly into complex algorithmic frameworks:
- Distributed Optimization: Yichuan Li et al. introduced BFGS-ADMM, utilizing the Sherman-Morrison formula to update an approximate inverse Hessian across distributed nodes without expensive inner communication loops.
- Hybrid Curvature: Minghan Yang et al. proposed splitting the Hessian into a "cheap" known base matrix and an "expensive" low-rank quasi-Newton update, using the Woodbury formula to efficiently invert their sum.
- Min-Max and Online Settings: For highly unstable optimization landscapes like Generative Adversarial Networks (GANs), Bamdev Mishra et al. structured the Hessian approximation as an identity matrix plus a rank-one update. This allowed them to compute second-order updates with the speed of first-order methods. Similarly, Jianhao He et al. leveraged the formula to achieve logarithmic regret bounds in quantum online optimization.
Speeding Up Semidefinite Programming via Slack Matrices
The utility of low-rank updates extends beyond machine learning into classical mathematical optimization, particularly Interior Point Methods (IPMs) for Semidefinite Programming (SDP).
In an SDP, the Hessian matrix exhibits a rigid mathematical structure: it is formed by the Kronecker product of inverse slack matrices ($S^{-1} \otimes S^{-1}$). Recomputing and inverting this matrix at every iteration is the primary computational bottleneck of solving an SDP.
[Standard IPM] Iterative Slack Matrix S ──> Full Recomputation ──> O(n^6) Inverse Hessian
│
[Low-Rank IPM] Small Changes to S ──> Low-Rank Perturbation ──> Woodbury ─┴─> O(m^ω) Lazy Update
To break this bottleneck, Haotian Jiang et al. observed that the slack matrix $S$ does not change drastically between iterations; its variation can be bounded by a low-rank update.
Building on this, Baihe Huang et al. showed that these low-rank modifications to the slack matrix map directly to low-rank updates of the full Kronecker-structured Hessian. By applying the Woodbury identity, the authors implemented a "lazy" updating scheme. Instead of recomputing the entire Hessian, they propagate the low-rank slack updates directly to the inverse Hessian, dropping the per-iteration complexity to the cost of standard matrix multiplication.
Scaling to Deep Learning and Large Language Models
As models grow to billions of parameters, calculating curvature becomes a massive challenge. However, low-rank inverse updates have enabled second-order methods to scale effectively to Large Language Models (LLMs), particularly for model compression and analysis.
Neural Network Pruning
Pruning algorithms aim to remove redundant weights without hurting model accuracy. The optimal weights to prune are determined by their "brain surgeon" scores, which depend directly on the inverse Hessian (or Empirical Fisher) matrix.
The WoodFisher framework, developed by Sidak Pal Singh et al., utilizes the Sherman-Morrison formula to build the inverse Hessian iteratively, sample by sample. This approach scales seamlessly to large models like ResNet-50. For even larger architectures, Eldar Kurtic et al. introduced oBERT, scaling second-order pruning to BERT and LLM architectures by leveraging the Woodbury identity to update curvature matrices efficiently.
Influence Functions and Policy Optimization
Beyond pruning, low-rank updates allow researchers to probe model behavior and optimize policies efficiently:
- Influence Functions: To calculate how much a specific training data point influenced a model's prediction, one must compute an inverse Hessian-gradient product. Adrian Weller et al. applied rank-$k$ Woodbury corrections to evaluate multiple test points simultaneously, avoiding full recalculations.
- Policy Optimization: In high-dimensional gradient-free optimization, Junbin Qiu et al. utilized the Woodbury identity within a zeroth-order Hessian framework (ZoVH), achieving up to a 22x speedup when fine-tuning LLMs.
- Weight Decomposition: When compressing models via Singular Value Decomposition (SVD), Xiangxiang Gao et al. demonstrated that updating only the minor singular components preserves an isotropic Hessian structure, accelerating convergence during post-compression recovery.
Conclusion
Whether training a GAN, pruning an LLM, or solving a massive semidefinite program, the underlying challenge remains the same: handling the computational weight of curvature. By recognizing that optimization is a continuous process where information changes incrementally, low-rank updates transform matrix inversion from a prohibitive bottleneck into a highly efficient, scalable asset.
Key Foundational Work
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation (2021) — contributed 3 concept elements to this direction.
A Faster Interior Point Method for Semidefinite Programming (2020) — contributed 2 concept elements to this direction.
WoodFisher: Efficient Second-Order Approximation for Neural Network Compression (2020) — contributed 1 concept elements to this direction.