Technical Summary: Stronger Memory-Query Tradeoffs for Convex Optimization

Problem Statement

This paper investigates the fundamental limitations of minimizing a $d$-dimensional 1-Lipschitz convex function over the unit ball when the optimization algorithm is constrained by limited memory. Specifically, the authors analyze the oracle complexity (the number of first-order oracle queries required) for algorithms that possess only $m$ bits of memory. The goal is to find a point $\hat{w}$ such that $F(\hat{w}) - \min_{w \in B(1)} F(w) \leq \alpha$.

While the oracle complexity without memory constraints is well-understood ($\Theta(\min\{1/\alpha^2, d \log(1/\alpha)\})$), the interplay between memory and query complexity in the high-accuracy regime (where $\alpha < 1/\sqrt{d}$) remains a challenging open problem. Previous work established lower bounds, but gaps remained regarding the sharpness of the transition between memory regimes and the necessity of quadratic memory for near-optimal query complexity.

Methodology

The authors introduce a new theoretical primitive, the Marked Subspace Game with Hint (MSGH), to analyze the limitations of memory-constrained strategies.

The Marked Subspace Game with Hint (MSGH)

The MSGH is a game played between a Player and an Adversary involving a random matrix $A \in \mathbb{R}^{d' \times d}$:

1. Message Phase: The Player chooses a function $h_1$ to encode a message of size $m_1$ bits about $A$.
2. Marking Phase: The Adversary, knowing $A$ and the message, selects ("marks") a $k$-dimensional linear subspace $L$.
3. Hint Phase: The Player receives a small "hint" $q$ (size $m_2$ bits) which can depend on the marked subspace $L$ and $A$.
4. Query Phase: The Player makes $T$ row queries to $A$.
5. Win Condition: The Player wins if they find a query vector $u$ that is nearly orthogonal to $A$ (i.e., $\|Au\|_\infty$ is small) but far from the marked subspace $L$.

Key Insight: The authors prove that for any strategy with limited memory (small $m_1$), the Adversary can choose a subspace $L$ such that any query nearly orthogonal to $A$ must lie within a small neighborhood of $L$. This mimics the behavior of an algorithm that stores a specific subspace to avoid the "barrier" term in the loss function.

Hard Instance Construction

To apply the MSGH to convex optimization, the authors construct a hard loss function $F(w)$ composed of three parts:

1. Nemirovski Function: A max of linear terms $\langle w, x_j \rangle - j\gamma$, designed to force the algorithm to discover specific vectors $x_j$.
2. Barrier Function: A term involving $\|Aw\|_\infty$ that penalizes queries not orthogonal to the random matrix $A$.
3. Wall Function (for Randomized case): A modified term from prior work that forces queries to have small norms outside the span of discovered vectors, tightening the correlation requirements.

The construction is adaptive for deterministic algorithms (using a "resisting oracle") and non-adaptive for randomized algorithms. The core proof technique involves showing that to make progress on the Nemirovski function, the optimizer must effectively play the MSGH (or the related Orthogonal Correlated Vector Game, OCVG) to find vectors orthogonal to $A$.

Key Contributions

1. New Lower Bounds for Randomized Algorithms

The authors prove that any randomized algorithm with $m$ bits of memory requires:
$$\tilde{\Omega}\left( \frac{d^2}{\sqrt{m}} \right)$$
oracle queries to find a solution with suboptimality polynomially small in $d$ (i.e., $\alpha = 1/\text{poly}(d)$).

• Significance: This improves upon the previous best bound of $\tilde{\Omega}(d^{8/3}/m^{4/3})$. Crucially, it demonstrates that $\tilde{\Omega}(d^2)$ memory is necessary to achieve the optimal $\tilde{O}(d)$ query complexity (which is achievable without memory constraints). Previous results only established this necessity for quasipolynomially small suboptimality ($\alpha \leq 2^{-\log^5 d}$).

2. New Lower Bounds for Deterministic Algorithms

For deterministic algorithms, the authors establish a lower bound of:
$$\tilde{\Omega}\left( \min\left\{ d^{1.6}, \frac{d^{8/3}}{m^{2/3}} \right\} \right)$$
This improves upon the previous best bound of $\tilde{\Omega}(d^{5/3}/m^{1/3})$.

• Significance: This bound reveals a sharp phase transition around $m \approx d^2$.
  • When $m = O(d^2 \log(1/\alpha))$, algorithms like Vaidya's method achieve $O(d \log(1/\alpha))$ query complexity.
  • When $m = \Omega(d^2 / \log(d))$, the required query complexity jumps by a polynomial factor to $\tilde{\Omega}(d^{4/3})$.
  • This implies that any deterministic algorithm improving the memory complexity of Vaidya's method (even by a polylogarithmic factor) must suffer a polynomial loss in query complexity. Previous bounds did not exhibit such a sharp transition.

3. Improved Analysis of the Orthogonal Correlated Vector Game (OCVG)

The authors use the MSGH to provide a tighter analysis of the OCVG introduced in [CP23]. They show that the correlation threshold required to win the game can be lowered from $(k/d)^{1/4}$ to $\sqrt{k/d}$. This tighter bound is instrumental in deriving the improved lower bounds for both randomized and deterministic settings.

Results Summary

Algorithm Type	Memory Regime	Previous Best Lower Bound	New Lower Bound
Randomized	General $m$	$\tilde{\Omega}(d^{8/3}/m^{4/3})$	$\tilde{\Omega}(d^2/\sqrt{m})$
Deterministic	General $m$	$\tilde{\Omega}(d^{5/3}/m^{1/3})$	$\tilde{\Omega}(\min\{d^{1.6}, d^{8/3}/m^{2/3}\})$

Note: The bounds hold for suboptimality $\alpha = 1/\text{poly}(d)$.

Significance and Claims

The paper claims to resolve the COLT 2019 open problem regarding memory-query tradeoffs in convex optimization by providing the first lower bounds that:

1. Establish a Sharp Phase Transition: For deterministic algorithms, the work identifies a precise memory threshold ($m \approx d^2$) where the query complexity undergoes a polynomial jump. This clarifies the fundamental cost of reducing memory below the quadratic threshold required by cutting-plane methods.
2. Extend Necessity of Quadratic Memory: For randomized algorithms, the result extends the necessity of $\tilde{\Omega}(d^2)$ memory to achieve near-optimal query complexity from the quasipolynomial regime to the polynomial regime. This suggests that memory constraints are a more severe bottleneck than previously understood for high-accuracy convex optimization.
3. Introduce a Robust Primitive: The Marked Subspace Game with Hint (MSGH) is presented as a powerful new tool for analyzing information-theoretic limitations in optimization, capable of handling adaptive vector sampling and leakage of information about the barrier matrix.

The authors emphasize that these results are derived through rigorous lower-bound proofs using Yao's minimax principle and do not propose new algorithms or experimental validations. The findings suggest that the gap between the memory requirements of gradient descent ($O(d)$) and cutting plane methods ($\tilde{\Omega}(d^2)$) is intrinsic to the problem structure in the high-accuracy regime.