The Quadratic Memory Barrier in Convex Optimization

73 concepts22 papers1 proposal

In the landscape of convex optimization, practitioners have long navigated a stark divide between two types of algorithms. On one side are First-Order Methods like Gradient Descent: they are lean, requiring memory only linear in the dimension ($d$), but they are slow to converge to high precision. On the other side are Cutting-Plane Methods: they converge with extreme speed (logarithmic in accuracy), but they are "memory hogs," requiring space proportional to $d^2$.

For years, researchers wondered if a "best of both worlds" algorithm existed—one that could achieve the lightning-fast convergence of second-order methods while maintaining the tiny memory footprint of first-order methods. Recent theoretical breakthroughs have finally provided an answer: for high-precision optimization, this middle ground is mathematically impossible.

The Spectrum of Solvers

To understand this trade-off, we must view optimization as a process of information gathering. Every time an algorithm queries an "oracle" (like calculating a gradient), it learns something about the geometry of the function.

As Woodworth et al. formalize in their 2019 open problem, the efficiency of an algorithm is defined by two costs:

  1. Oracle Complexity: How many queries are needed to reach a target accuracy?
  2. Memory Complexity: How many bits of information must be stored between queries?

Standard Gradient Descent is at one extreme of this Pareto frontier. It is highly memory-efficient but requires a number of queries that scales polynomially with the desired accuracy ($1/\epsilon$). Cutting-plane methods, which maintain a "localization set" (like an ellipsoid) that contains the optimum, sit at the other extreme. They achieve logarithmic query complexity ($O(d \log(1/\epsilon))$) but require $O(d^2)$ memory to store the matrix describing that ellipsoid.

The Geometry of Forgetting

Why is memory so critical for speed? The intuition lies in the "state" of the search. To narrow down the location of an optimum in high-dimensional space, an algorithm must remember the constraints it has already discovered.

Marsden et al. argue in their COLT 2022 paper that when an algorithm's memory is restricted, it literally "forgets" the geometry of the function. Because it cannot store the full history of its queries or a complex model of the search space, it is forced to re-query the oracle to re-learn information it previously possessed. This lack of state prevents the algorithm from making the aggressive, informed steps that characterize second-order methods.

The authors proved that any algorithm using less than $d^{1.25}$ bits of memory is mathematically incapable of reaching the theoretical minimum number of queries. Below this threshold, performance degrades from linear query complexity to a polynomially worse rate.

The $d^2$ Phase Transition

While the $d^{1.25}$ bound was a major step, a gap remained between that lower bound and the $d^2$ memory used by optimal methods. In 2023, Blanchard et al. resolved this by proving that quadratic memory ($\Omega(d^2)$) is a fundamental requirement for optimal query complexity.

This result establishes a sharp phase transition in optimization efficiency:

  • Sub-quadratic Memory: If you have less than $d^2$ space, your query complexity is forced to be polynomial in the accuracy ($1/\epsilon$).
  • Quadratic Memory: Once you can store a full second-order summary of the space (like a Hessian or an ellipsoid matrix), your query complexity drops to logarithmic.

Blanchard further demonstrated in subsequent work that Gradient Descent is actually Pareto-optimal. This means that for feasibility problems, you cannot improve upon Gradient Descent's query efficiency without significantly increasing memory toward the quadratic limit.

Practical Implications for Large-Scale Models

This theoretical "no-go" theorem explains why, despite their slow convergence, first-order methods remain the dominant choice for training massive language models. In a model with billions of parameters ($d$), $d^2$ memory is physically impossible to provide.

However, researchers continue to look for ways to push the boundaries of this trade-off in specific contexts:

  • Low-Rank Projections: Methods like GUM, proposed by Luo et al., attempt to maintain the theoretical rigor of full-rank updates while using low-rank projections to keep the memory footprint manageable.
  • Randomized Approaches: Peng and Chen investigated whether randomization could break these limits. They found that even with stochasticity, the quadratic memory requirement for optimal query efficiency remains a rigid barrier.
  • Recursive Methods: Blanchard et al. have developed recursive cutting-plane algorithms that allow for a tunable trade-off, bridging the gap between the two extremes, though they still face exponential scaling when trying to balance these resources.

Ultimately, the research suggests that the high memory cost of fast optimization is not a flaw in our current algorithms, but an inherent property of high-dimensional geometry. To move fast, an algorithm must remember where it has been.

Key Foundational Work

Randomized Low-Memory Singular Value Projection (2013) — contributed 1 concept elements to this direction.
Playing Mastermind with Constant-Size Memory (2014) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 24 papers
  2. Version 1 · 2026-10-04 · 30 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_memory_query_complexity_trade_off_98572407,
  title = {memory-query complexity trade-off},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-query-complexity-trade-off/rdr_985724079f6e43d0b05aff9a3062be27},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_memory_query_complexity_trade_off_98572407_v2,
  title = {memory-query complexity trade-off},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-query-complexity-trade-off/rdr_985724079f6e43d0b05aff9a3062be27/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake