In high-dimensional optimization, practitioners often face a frustrating binary choice. On one hand, first-order methods like Gradient Descent are extremely memory-efficient, requiring only $O(d)$ space to store the current position and gradient. However, they are "slow," requiring many iterations (queries) to reach high precision. On the other hand, cutting-plane methods are "fast" in terms of query count but require $O(d^2)$ memory to maintain a representation of the search space.
For years, the space between these two extremes was a theoretical "missing link." Recent research has begun to map this landscape, proving that the relationship between memory and speed is not just a matter of algorithmic design, but a fundamental information-theoretic limit.
The Quadratic Barrier
The most significant recent discovery in this field is that "having it all" is mathematically impossible. Annie Marsden, Aaron Sidford, and their colleagues proved in Efficient Convex Optimization Requires Superlinear Memory that any algorithm achieving optimal query complexity must use superlinear memory.
This was further refined by Moise Blanchard, Junhui Zhang, and Patrick Jaillet, who resolved a long-standing open problem by showing that Quadratic Memory is Necessary for Optimal Query Complexity. They demonstrated that classic "center-of-mass" methods are actually Pareto-optimal: you cannot reduce their memory footprint without forcing a corresponding increase in the number of queries needed to solve the problem.
Bridging the Gap with Recursion
If the extremes are fixed, how do we navigate the middle ground? Moise Blanchard and Patrick Jaillet proposed a solution in Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes.
The intuition is to use a "divide and conquer" strategy on the variables themselves. By partitioning the $d$ dimensions into blocks and optimizing them recursively, they created a family of algorithms that allow for a tunable trade-off. If you have a bit more memory than Gradient Descent but not enough for a full Hessian, these recursive methods can utilize that extra space to reduce the total number of oracle calls. This bridges the gap between the $O(d)$ and $O(d^2)$ regimes, though the trade-off remains exponential: saving memory typically leads to a significant increase in required queries.
Memory in Quasi-Newton Methods
In the world of smooth optimization, the trade-off manifests in how much "curvature" information we store. Standard L-BFGS uses a sliding window of past gradients to approximate the Hessian. However, Erik Berglund argues in Novel Limited Memory Quasi-Newton Methods Based On Optimal Matrix Approximation that simply discarding old data is inefficient. Instead, he proposes "reducing" the Hessian approximation to its closest limited-memory form using optimal matrix projections, squeezing more utility out of the same memory budget.
Furthermore, Aryan Mokhtari and his team developed LG-BFGS, the first limited-memory method to provide a provable, non-asymptotic superlinear convergence rate. This work provides a mathematically grounded framework for exactly how much memory is needed to achieve specific acceleration targets.
Practical Constraints in Large Models
The theoretical limits of memory are becoming a primary bottleneck in training massive language models. Standard optimizers like Adam require storing multiple states for every parameter, which is often unfeasible.
Researchers are applying these memory-constrained insights to create more efficient training loops:
- GUM: Yang Luo and Yang You introduced Unbiased Gradient Low-Rank Projection, which uses layerwise sampling to maintain the convergence of full-parameter training while using a fraction of the memory.
- IO-Adam: Yiting Chen and Junchi Yan developed IO-Adam, which reduces memory by tracking input activations and output gradients separately, exploiting the mathematical structure of backpropagation to avoid storing full-matrix states.
These developments suggest that while the "quadratic barrier" discovered by Marsden and Blanchard is a hard physical limit for general convex problems, we can still find significant efficiencies by tailoring our memory usage to the specific structure of the functions we optimize.