Memory-Query Tradeoffs for Randomized Convex Optimization

We show that any randomized first-order algorithm which minimizes a d-dimensional, 1-Lipschitz convex function over the unit ball must either use Ω(d 2-δ ) bits of memory or make Ω(d 1+δ/6-o(1) ) queries, for any constant δ ∈ (0, 1) and when the precision ǫ is quasipolynomially small in d. Our result implies that cutting plane methods, which use Õ(d 2 ) bits of memory and Õ(d) queries, are Pareto-optimal among randomized first-order algorithms, and quadratic memory is required to achieve optimal query complexity for convex optimization.

Warm up: Encoding in the bit model Our encoding argument is delicate and we first illustrate the basic idea in a simpler "bit model" of the correlated orthogonal vector game: Alice sends n bits (instead rows) in the third round. This is strictly weaker than the original model because n rows can transmit at least n bits of message (even when they are required to be row vectors of A).

In this model, Bob's output vector x, is a function of the first round message M ∈ 0, 1 kd , the third round message b ∈ 0, 1 n and its input vector v ∈ 1 √ d H d , and we denote as x M,v,b . Fix a matrix A ∈ -1, 1 (d/2)×d and the first round message M A , the choice of v is still uniformly at random, and we observe that the collection x M A ,v,b v∈ 1 √ d H d ,b∈0,1 n should contain at least s linearly independent vectors that are orthogonal to A, and this continues to hold w.h.p. when one restricts to a subset V * ⊆ H d of size O(s). That is to say, using a probabilistic argument, there exists a set V * ⊆ 1

such that x M A ,v,b v∈V * ,b∈0,1 n contains at least s linearly independent vectors that are orthogonal to A, for at least 1/2-fraction of matrices A ∈ 0, 1 (d/2)×d . We denote this set as A nice

Consider the following (one-shot) encoding strategy: Fix a message M ∈ 0, 1 kd , a s-tuple x 1 , . . . , x s ∈ x M,v,b v∈V * ,b∈0,1 n that are linearly independent, include all matrices A ∈ -1, 1 (d/2)×d whose rows are orthogonal to x 1 , . . . , x s . The above argument implies that all matrices A ∈ A nice are included, but on the hand, the encoding scheme only encodes

Here the first term of LHS is the number of message M, the second term is the number of s-tuple x 1 , . . . , x s (note this is the place we need |V * | ≤ O(s)) and the third term is the number of matrices A that are orthogonal to the s-tuple.

Encoding in the row model We next design an encoding strategy based on the (too-goodto-be-true) communication protocol that sends n rows instead of n bits, which turns out to be much more challenging and requires an iterative encoding. In the row model, the output x of Bob depends on the message M ∈ 0, 1 kd , the vector v ∈ 1 √ d