In large-scale machine learning, we are often caught between two extremes. On one hand, first-order methods like Stochastic Gradient Descent (SGD) are computationally cheap but struggle with "ill-conditioned" landscapes—narrow, winding valleys where the gradient points almost anywhere except toward the minimum. On the other hand, second-order methods like Newton’s method navigate these valleys effortlessly by using the Hessian matrix (the curvature), but they are prohibitively expensive, requiring $O(d^2)$ memory and $O(d^3)$ computation for $d$ parameters.
Recent research has converged on a powerful middle ground: the low-rank curvature hypothesis. This perspective suggests that in high-dimensional models like Transformers, the vast majority of the Hessian’s information is concentrated in a tiny fraction of its dimensions. By capturing only these dominant directions, we can achieve the convergence speed of second-order methods with the efficiency of first-order ones.
The Geometry of Low-Rank Landscapes
The intuition behind this direction starts with the observation that most directions in a model's parameter space are "flat" or redundant. Aryan Mokhtari, Alejandro Ribeiro, and Mark Eisen demonstrate in Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method that the Hessian matrix in high-dimensional datasets often exhibits a low-rank structure.
If the Hessian is low-rank, we don't need to invert a massive $d \times d$ matrix. Instead, we only need to identify the top $k$ eigenvalues and eigenvectors. This "truncated" approach allows the optimizer to focus on the directions of highest curvature—the walls of the narrow valley—while ignoring the flat directions where SGD typically wanders.
Capturing Curvature Without the Matrix
How do we find these dominant directions without ever constructing the full Hessian? The field has moved toward randomized sketching and iterative methods.
- Sketching and Nyström Methods: Zachary Frangella, Madeleine Udell, and colleagues show in SketchySGD and PROMISE that we can use the Nyström method to estimate the Hessian. By multiplying the Hessian by a small number of random vectors (Hessian-vector products), we can "sketch" its most important features. This allows for efficient inversion via the Woodbury matrix identity, providing a preconditioner that fixes ill-conditioning at a marginal cost.
- Krylov Subspaces: For even larger models, researchers like Andrea Schioppa and David Vilar utilize Arnoldi iteration in Scaling Up Influence Functions. This technique builds a low-rank subspace that captures the essential curvature, enabling complex tasks like influence estimation (tracing predictions back to training data) for models with hundreds of millions of parameters.
- Subspace Optimization: Dongyoon Kim and Wonjin Lee argue in ZO-SAH that even 2D subspaces are often sufficient to capture the off-diagonal interactions between parameters, allowing optimizers to navigate tilted valleys more effectively than diagonal-only methods.
Application to Large Language Models
The low-rank property is particularly salient in Large Language Models (LLMs). Because LLMs often have a low "effective rank" in their loss landscapes, we can optimize them using only forward passes (Zeroth-Order Optimization).
Yanjun Zhao and Haishan Ye introduce HiZOO in Second-Order Fine-Tuning without Pain for LLMs, which uses a single extra forward pass to estimate the Hessian diagonal. Similarly, Zhe Li and Bicheng Ying develop HiSo in Converge Faster, Talk Less, demonstrating that because the effective rank is low, zeroth-order methods can achieve convergence rates that are nearly independent of the total number of parameters. This is a crucial breakthrough for fine-tuning 60B+ parameter models on resource-constrained hardware.
Efficiency in Distributed and Constrained Settings
The low-rank approach also solves the communication bottleneck in Federated Learning (FL). Instead of sending massive gradients or Hessians between clients and servers, we can send compressed "sketches."
- FLECS: Artem Agafonov and Martin Takác propose FLECS, which moves Hessian storage to the server and uses sketching to reduce worker memory to zero.
- Basis Learn: Rustem Islamov and Peter Richtárik show in Basis Matters that representing local Hessians in a custom basis tailored to the data's intrinsic dimensionality can slash communication costs by orders of magnitude.
- FedMeZO: Zhenqing Ling and Daoyuan Chen extend these ideas to edge devices in FedMeZO, allowing memory-efficient tuning of LLMs without backpropagation.
Summary
The core insight of this research direction is that high dimensionality does not imply high complexity. While the parameter space of modern models is vast, the geometric features that dictate optimization performance are concentrated in low-dimensional subspaces. By using randomized sketching, Krylov iterations, and zeroth-order approximations to target these subspaces, we can bring the mathematical rigor of second-order optimization to the largest models in existence.