Matrix-Free First-Order Optimization

32 concepts22 papers1 proposal

When scaling convex optimization to modern, web-scale datasets or high-resolution imaging, classical algorithms hit a hard mathematical wall. Traditional second-order methods (like Newton's method) and standard interior-point methods require computing, storing, and manipulating explicit matrices—such as Hessians or constraint matrices.

This creates two severe bottlenecks: a quadratic space complexity $O(n^2)$ to store the matrix, and a cubic time complexity $O(n^3)$ to invert or factorize it (via Cholesky or spectral decompositions). As Ho et al. and Zhang et al. observe, when a problem involves millions of variables, explicitly instantiating these matrices is completely intractable.

The core insight of matrix-free optimization is that optimization algorithms rarely need to know what the matrix is; they only need to know what the matrix does. By shifting the computational paradigm from explicit matrix storage to on-the-fly operator evaluation, matrix-free methods bypass the memory wall, trading memory capacity for raw arithmetic throughput.

Interacting via Linear Oracles

To understand why matrix-free optimization works, consider a standard linear constraint $Ax = b$. In a traditional solver, $A$ is stored as a dense or sparse array. In a matrix-free framework, $A$ is treated as an abstract linear operator.

As Boyd et al. demonstrate, a solver can be decoupled entirely from the data representation by interacting with the problem exclusively through two routine interfaces, or "oracles":

  1. A forward oracle that computes the matrix-vector product (MVP) $y = Ax$.
  2. An adjoint oracle that computes the transposed product $x = A^T y$.
Traditional Solver:
[ Explicit Matrix A ] ---> [ Direct Matrix Inversion / Factorization ] ---> O(n³) Time, O(n²) Memory

Matrix-Free Solver:
[ Vector x ] ---> [ Forward/Adjoint Oracles (e.g., FFT, Convolution) ] ---> O(n) or O(n log n) Memory

This abstraction is incredibly powerful because many large-scale operators have underlying structures—such as convolutions, graphs, or Fourier transforms—that can be computed in $O(n \log n)$ or even $O(n)$ time without ever writing down the matrix elements. Wu et al. show that this shift allows massive semidefinite programs (SDPs) to be solved directly on GPUs, where high arithmetic throughput compensates for limited physical memory.

First-Order Splitting and Primal-Dual Frameworks

If we can only interact with our problem via matrix-vector products, we must use optimization algorithms designed to thrive on this constraint. First-order primal-dual splitting methods are the natural choice.

Algorithms like the Primal-Dual Hybrid Gradient (PDHG) or the Alternating Direction Method of Multipliers (ADMM) split the objective function into independent pieces. For instance, Ko et al. show that by utilizing only gradients and proximity operators, primal-dual algorithms can eliminate the cubic complexity of matrix inversions entirely, bounding the per-iteration cost strictly to the cost of an MVP.

This framework has been adapted across several domains:

  • Linear Programming (LP): Applegate et al. developed PDLP, a first-order LP solver that scales to web-scale datasets by replacing traditional simplex or barrier factorizations with iterative MVPs.
  • Affine Constraints: Salim et al. designed an optimal fully split algorithm for strongly convex minimization under affine constraints, matching theoretical lower bounds for both gradient steps and MVPs.
  • Complex Regularization: Sankaran et al. leverage strictly first-order steps to solve machine learning problems with subquadratic norms, avoiding expensive proximal operators.

Bypassing Inversions with Iterative Subspace Solvers

Some optimization frameworks, such as the Augmented Lagrangian Method (ALM) or Newton-type methods, inherently require solving a linear system $(A^T A + \rho I)x = r$ at each step. Even here, we can avoid explicit matrix factorization by embedding an inner iterative linear solver, such as a Krylov subspace method (e.g., Conjugate Gradient).

Krylov methods approximate the solution to a linear system by successively applying the matrix operator to a residual vector, building up a subspace ($r, Ar, A^2r, \dots$). Wang et al. demonstrate this in the context of spherically constrained least squares, showing that Krylov methods avoid the cubic cost of spectral decompositions and scale linearly with the number of non-zero entries.

For large-scale linear programming, Li et al. introduced SNIPAL, a semismooth Newton augmented Lagrangian method that handles constraints defined implicitly via linear operators. Even within interior-point methods—traditionally the most matrix-heavy solvers—Mladenov et al. showed that the inner loop can be refactored to run matrix-free by executing iterative linear solvers directly over compressed symbolic representations.

Exploiting Structural Sparsity

Beyond abstract operators, matrix-free optimization works by exploiting the structural or geometric properties of specific problem domains to avoid storing second-order data.

Coordinate and Analytical Reductions

Instead of updating all variables simultaneously, which couples them via a massive Hessian matrix, algorithms can isolate minimal subsets. Platt pioneered this with Sequential Minimal Optimization (SMO) for Support Vector Machines, breaking a massive quadratic program into analytical two-variable sub-problems. This completely eliminated the need to store a large second-order derivative matrix. Similarly, Marecek et al. utilize coordinate descent to bypass massive matrix inversions in semidefinite programming relaxations for power grid optimization.

Domain Transformations and Approximations

If a problem can be mapped to a domain where the operator becomes diagonal, matrix operations simplify dramatically. Bibi et al. exploit this in FFTLasso by "lifting" large-scale LASSO problems into the Fourier domain. Because circulant matrices become diagonal under the Fourier transform, expensive linear system solvers are replaced by highly parallelizable 1D FFTs.

Where exact transformations are unavailable, analytical approximations can suffice. In city-scale 3D reconstruction, Cremers et al. use a power series expansion to approximate the inverse Schur complement on the fly, eliminating the need to store dense intermediate matrices.

Discrete and Streaming Representations

For combinatorial or highly constrained problems, structure can be maintained via graph-based or algorithmic oracles:

  • Decision Diagrams: Lange et al. decompose 0-1 integer linear programs using Binary Decision Diagrams (BDDs), replacing matrix factorizations with dynamic programming on directed acyclic graphs to achieve linear iteration complexity.
  • Streaming Oracles: In memory-constrained data streams, Cormode et al. apply the Multiplicative Weight Update framework to correlation clustering. By treating a rounding algorithm as an oracle, they navigate the optimization landscape without ever explicitly storing the full, massive constraint set.

Key Foundational Work

Using Analytic QP and Sparseness to Speed Training of Support Vector Machines (1998) — contributed 1 concept elements to this direction.
A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_matrix_free_optimization_9ddca352,
  title = {matrix-free optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matrix-free-optimization/rdr_9ddca352137a4e189e01d8851c0693bd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_matrix_free_optimization_9ddca352_v1,
  title = {matrix-free optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matrix-free-optimization/rdr_9ddca352137a4e189e01d8851c0693bd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake