Memory-Query Tradeoffs for Randomized Convex Optimization

Xi Chen, Binghui Peng

Abstract

In the field of mathematical optimization, a fundamental tension exists between memory efficiency and query complexity. While Gradient Descent requires minimal memory but converges slowly, Cutting-Plane Methods offer rapid convergence at the cost of quadratic memory. This paper investigates whether randomized algorithms can bypass this tradeoff. We establish a lower bound proving that any randomized algorithm for convex optimization requires $\Omega(d^2)$ memory to achieve optimal query efficiency, confirming that classic cutting-plane methods are Pareto-optimal and that the memory-query bottleneck is a fundamental property of the problem's geometry.

Introduction

Convex optimization serves as the foundational engine for modern machine learning and mathematical programming. For decades, practitioners have navigated a stark choice between two algorithmic paradigms. On one end, first-order methods like Gradient Descent (GD) are lean on memory, requiring only $O(d)$ space, but suffer from slow convergence rates ($O(1/\epsilon^2)$). On the other end, Cutting-Plane Methods (CPM) converge in near-linear queries ($O(d \log 1/\epsilon)$) but are "memory hogs," requiring $O(d^2)$ space to store the geometry of the feasible region.

A long-standing open question in the field, formalized in 2019, asked whether randomization could provide a "middle ground"—an algorithm that maintains the query efficiency of CPM while utilizing the near-linear memory of GD. This research definitively answers that question in the negative, establishing a rigorous lower bound for randomized algorithms.

The Optimization Landscape

To understand the significance of this result, one must consider the two primary metrics of efficiency in $d$-dimensional convex optimization:

  1. Query Complexity: The number of times an algorithm must consult an "oracle" for the function's value and gradient at a specific point.
  2. Memory Complexity: The amount of information (in bits) the algorithm must store between queries to determine the next point of interest.

While deterministic algorithms were previously shown to be bound by a quadratic memory requirement for optimal query complexity, randomized algorithms often find ways to bypass such lower bounds by avoiding worst-case scenarios. However, this work demonstrates that the geometric constraints of convex optimization are too rigid for randomization to overcome.

Methodology: The Correlated Orthogonal Vector Game

The researchers establish their lower bound through a sophisticated reduction to a novel communication problem termed the Correlated Orthogonal Vector Game. This approach involves three key components:

1. Hard Instance Construction

The authors define a "nasty" convex function designed to be the worst-case scenario for any optimizer. This function combines a Nemirovski function, which forces the algorithm to discover dimensions one by one, with a projection term that prevents query points from entering a hidden subspace without sufficient information.

2. Communication Game Reduction

The optimization problem is transformed into a game between two players, Alice and Bob. Alice holds a secret matrix $A$, and Bob holds a secret vector $v$. For Bob to solve the optimization problem, he must eventually output a vector that is both highly correlated with his secret $v$ and nearly orthogonal to Alice's matrix $A$.

3. Iterative Encoding

The core technical contribution is an iterative encoding scheme. The authors prove that if Bob could solve the optimization game using sub-quadratic memory, he would effectively be compressing a random matrix beyond the limits allowed by information theory. This proves that memory acts as a strict bottleneck for storing the geometric information necessary to navigate the function's landscape.

Key Results

The research provides a definitive lower bound for randomized convex optimization. The primary findings include:

  • The Fundamental Tradeoff: For a $d$-dimensional problem requiring high precision, any randomized algorithm faces a tradeoff: it must use either $\Omega(d^{2-\delta})$ bits of memory or $\Omega(d^{1+\delta/6})$ queries.
  • Pareto Optimality of CPM: The results prove that Cutting-Plane Methods, which operate at the $d^2$ memory and $d$ query threshold, are mathematically optimal. There is no "magic" algorithm capable of significantly improving one metric without a corresponding loss in the other.
  • Memory as Geometry: The paper suggests that memory in optimization is not merely storage, but a representation of geometric subspaces. To achieve a near-linear number of queries, an algorithm must store the equivalent of a $d \times d$ matrix to track where it has been and where the optimum may lie.

Limitations and Future Work

While the lower bound is robust, two primary areas remain for further exploration:

  1. The Precision Gap: The current proof requires the precision parameter ($\epsilon$) to be "quasipolynomially small." It remains an open question whether these strict tradeoffs persist at lower, polynomial levels of accuracy ($1/poly(d)$).
  2. The Exponent Gap: There remains a small technical gap between the query lower bound ($\Omega(d^{1+\delta/6})$) and the known upper bound ($O(d)$). Future research may tighten this relationship to a perfect $d^2$ vs. $d$ correspondence.

Conclusion

For practitioners, the implications are clear: when dealing with high-dimensional datasets where $d^2$ memory is computationally prohibitive, first-order methods like Gradient Descent are not just a choice, but a mathematical necessity. The search for a linear-memory, linear-query optimizer is effectively over; the laws of information theory and geometry dictate that we must choose between speed and space.

Summary updated

BibTeX
@inproceedings{chen2023memory,
  author = {Xi Chen and Binghui Peng},
  title = {{Memory-Query Tradeoffs for Randomized Convex Optimization}},
  booktitle = {FOCS},
  year = {2023},
  doi = {10.1109/focs57990.2023.00086},
}
Figure