Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract)

Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory ValiantIJCAI 2023 · OpenReview

Abstract

Minimizing a convex function with access to a first order oracle---that returns the function evaluation and (sub)gradient at a query point---is a canonical optimization problem and a fundamental primitive in machine learning. Gradient-based methods are the most popular approaches used for solving the problem, owing to their simplicity and computational efficiency. These methods, however, do not achieve the information-theoretically optimal query complexity for minimizing the underlying function to small error, which are achieved by more expensive techniques based on cutting-plane methods. Is it possible to achieve the information-theoretically query complexity without using these more complex and computationally expensive methods? In this work, we use memory as a lens to understand this, and show that is is not possible to achieve optimal query complexity without using significantly more memory than that used by gradient descent.

Introduction: The Memory-Query Gap

In the field of convex optimization, a persistent gap exists between theoretical query optimality and practical memory efficiency. Two primary families of algorithms define this landscape:

  1. Gradient-based methods (e.g., SGD): These are the workhorses of modern machine learning. They are memory-efficient, requiring only $O(d)$ memory (where $d$ is the dimension), but they exhibit sub-optimal query complexity, requiring many more steps to reach high precision.
  2. Cutting-plane methods (e.g., the Ellipsoid method): These are query-optimal but require $O(d^2)$ memory and involve high computational overhead per step, making them rare in large-scale applications.

This research addresses a fundamental question: Is it possible to design an algorithm that achieves the optimal query complexity of cutting-plane methods while maintaining the low memory footprint of gradient descent?

Methodology: Memory as a Complexity Lens

The authors prove that such an ideal algorithm is impossible by establishing a formal trade-off between memory and query complexity. Their approach utilizes several novel theoretical components:

The Orthogonal Vector Game (OVG)

The core of the proof relies on the OVG, where a player must find vectors approximately orthogonal to the rows of a random matrix $A$ using limited memory. If memory is significantly less than the size of the matrix, the player must repeatedly "re-learn" the matrix, leading to high query counts.

Memory-Sensitive Function Class

The authors construct a specific distribution of "hard" convex functions based on the "Nemirovski function." This construction is designed so that making progress toward the minimum forces an algorithm to solve instances of the OVG.

The subgradient oracle construction used to prove the memory-query trade-off.

Key Results: The $d^{1.25}$ Threshold

The study identifies a critical polynomial threshold for memory. If an algorithm uses significantly less than $d^{1.25}$ bits of memory, its query complexity must suffer significantly.

Trade-off between memory and oracle complexity, highlighting the forbidden region established by the lower bound.

The main result, summarized in Theorem 1, states that for a $d$-dimensional problem, any algorithm finding an $\epsilon$-approximate minimizer must either:

  1. Use at least $d^{1.25 - \delta}$ bits of memory, or
  2. Make $\Omega(d^{1 + \text{poly}(\delta)})$ queries.

This proves that the "optimal" query complexity of $O(d \log(1/\epsilon))$ is physically impossible to reach with near-linear memory. The paper maps out a "forbidden region" (the solid red area in Figure 1) where no algorithm can exist, showing that we cannot "cheat" the memory requirements of high-precision optimization.

Discussion and Future Work

This work provides the first unconditional separation between simple gradient-like techniques and complex cutting-plane methods. It demonstrates that the high memory usage of cutting-plane methods is a requirement for their query efficiency, not just a design choice.

However, a theoretical gap remains: while the paper proves a lower bound of $d^{1.25}$, cutting-plane methods use $d^2$ memory. Future research may aim to close this gap or explore how these bounds change with different types of function access, such as stochastic oracles or second-order information. The authors suggest their information-theoretic framework could be applied to other areas of machine learning to prove similar fundamental trade-offs.

Summary updated

Abstract

Minimizing a convex function with access to a first order oracle---that returns the function evaluation and (sub)gradient at a query point---is a canonical optimization problem and a fundamental primitive in machine learning. Gradient-based methods are the most popular approaches used for solving the problem, owing to their simplicity and computational efficiency. These methods, however, do not achieve the information-theoretically optimal query complexity for minimizing the underlying function to small error, which are achieved by more expensive techniques based on cutting-plane methods. Is it possible to achieve the information-theoretically query complexity without using these more complex and computationally expensive methods? In this work, we use memory as a lens to understand this, and show that is is not possible to achieve optimal query complexity without using significantly more memory than that used by gradient descent.
BibTeX
@inproceedings{marsden2023efficient,
  author = {Annie Marsden and Vatsal Sharan and Aaron Sidford and Gregory Valiant},
  title = {{Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=lbqyDCXYBx},
}
Figure