In numerical optimization, the bottleneck is often not the number of CPU or GPU cycles required, but the physical memory available. When scaling optimization algorithms to millions of variables or data points, classical methods hit a "memory wall." This wall arises because standard algorithms frequently require the explicit materialization and manipulation of large matrices—such as Hessians, covariance matrices, kernel dictionaries, or constraint matrices—whose storage requirements scale quadratically ($O(n^2)$) or cubically ($O(n^3)$) with the problem size.
To bypass this bottleneck, a major research direction focuses on memory-constrained matrix optimization. The core intuition behind this field is that we can often optimize over high-dimensional spaces without ever explicitly storing the underlying large matrices. Instead, researchers leverage matrix-free operators, randomized sketching, low-rank approximations, and first-order splitting methods to keep the memory footprint strictly manageable.
The Quadratic Memory Wall
To understand why standard optimization fails at scale, consider Semidefinite Programming (SDP) or second-order Newton methods. An SDP optimization problem over an $n \times n$ matrix variable requires tracking $O(n^2)$ entries. As highlighted by Alp Yurtsever et al. in Scalable Semidefinite Programming, if the problem dimension reaches a million variables, a standard solver would require a trillion entries of memory—an absolute non-starter for modern hardware.
Similarly, second-order optimization methods require computing and storing curvature or Hessian matrices. In high-dimensional portfolio optimization involving skewness and kurtosis matrices, the storage requirements for dense higher-order structures quickly exhaust physical RAM (Daniel P. Palomar et al., Solving High-Order Portfolios via Successive Convex Approximation Algorithms). Even on massively parallel architectures, individual processors often lack the local memory needed to store dense curvature matrices, forcing a reliance on more memory-efficient alternatives (Alan H. Kramer et al., Efficient Parallel Learning Algorithms for Neural Networks).
Matrix-Free and Abstract Linear Operators
The first major breakthrough in overcoming the memory wall is the realization that we rarely need to store a matrix; we only need to compute its action on a vector. For an optimization algorithm, knowing the result of the matrix-vector product $Ax$ is functionally identical to having explicit access to the matrix $A$.
By treating linear functions as abstract mathematical operators rather than concrete data arrays, solvers can bypass matrix materialization entirely. Stephen P. Boyd et al. formalized this paradigm in Convex Optimization with Abstract Linear Operators. They demonstrated that by preserving fast transforms (such as the Fast Fourier Transform) within the optimization loop, problems with millions of variables can be solved efficiently without generating explicit sparse or dense matrices that would otherwise crash the system.
This matrix-free approach is equally vital in large-scale engineering simulations. For instance, Carlo Janna demonstrated in Parallel Energy-Minimization Prolongation for Algebraic Multigrid that advanced multigrid solvers can avoid constructing massive auxiliary prolongation matrices by utilizing a matrix-free implementation, enabling high-fidelity structural optimization within standard hardware constraints.
Compression via Sketching and Low-Rank Structures
When matrices cannot be completely avoided, they can often be compressed. Many real-world datasets and optimization variables exhibit a high degree of redundancy, meaning their information can be compressed into a lower-dimensional subspace.
Two primary techniques dominate this space:
- Randomized Sketching: When the number of observations far exceeds the number of features, the data matrix can be multiplied by a random projection matrix. As shown by Alexander Munteanu et al. in Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression, this "oblivious sketching" compresses the data matrix to a fraction of its size while strictly preserving the underlying geometric structure necessary for accurate optimization.
- Low-Rank Approximations: In kernel methods, such as Least Squares Support Vector Machines (LS-SVMs), computing exact solutions requires inverting massive dense matrices. Weikuo Wang et al. broke this bottleneck in Nyström-Accelerated Primal LS-SVMs: Breaking the $O(an^3)$ Complexity Bottleneck for Scalable ODEs Learning by integrating the Nyström method to approximate the dense kernel matrix, dropping the memory and computational overhead significantly.
Furthermore, choice of algorithm dictates memory behavior. Standard matrix completion or rank minimization methods often produce high-rank intermediate iterates that cause memory bloat. By utilizing projection-free methods like the Frank-Wolfe algorithm, the authors of Efficient Structured Matrix Rank Minimization (Adams Wei Yu et al.) showed that optimization can proceed by updating low-rank factors directly, keeping memory consumption strictly linear relative to the data size.
Trading Iterations for Memory: First-Order Solvers
Another core strategy is changing the mathematical engine of the solver. Second-order methods converge in very few iterations but require $O(n^2)$ memory to store the Hessian matrix. First-order methods, by contrast, rely only on gradient information, requiring vectors of size $O(n)$. This represents a fundamental trade-off: you perform more iterations, but each iteration requires orders of magnitude less memory.
For massive linear programming problems, traditional interior-point methods fail due to the memory cost of dense matrix factorizations. To solve this, David Applegate et al. developed PDLP in Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient, utilizing a first-order, matrix-free framework that handles millions of variables within standard hardware limits.
For general convex optimization, Moise Blanchard et al. designed recursive cutting-plane algorithms in Memory-Constrained Algorithms for Convex Optimization that provide a mathematically tunable dial between memory usage and query complexity. Similarly, when optimizing over complex geometric manifolds, Simon Vary demonstrated in Optimization without Retraction on the Random Generalized Stiefel Manifold that replacing expensive matrix factorizations (retractions) with simple matrix multiplications avoids the need to form and store full dense covariance structures in streaming data contexts.
Domain Decomposition
When a matrix problem is simply too massive to fit onto a single accelerator or machine, the final line of defense is domain decomposition—breaking the optimization problem into localized, independent chunks.
[ Massive Global Optimization Problem ]
│
┌──────────┼──────────┐ (Stochastic Domain Decomposition)
▼ ▼ ▼
[Block 1] [Block 2] [Block 3] --> Managed independently in memory
This technique is highly effective in computer vision tasks like city-scale 3D reconstruction, which generate billions of residuals and massive Hessian matrices. In DeepLM: Large-Scale Nonlinear Least Squares on Deep Learning Frameworks Using Stochastic Domain Decomposition, Jingwei Huang 0001 et al. introduced a stochastic domain decomposition strategy that partitions these massive problems into localized subproblems. By isolating the heavy matrix operations to smaller, independent blocks, high-performance second-order solvers like Levenberg-Marquardt can be executed within the tight memory constraints of standard deep learning frameworks.
Key Foundational Work
Active Support Vector Machine Classification (2000) — contributed 1 concept elements to this direction.
Efficient Parallel Learning Algorithms for Neural Networks (1988) — contributed 1 concept elements to this direction.