Towards Settling the Complexity of Non-Euclidean Parallel Convex Optimization

In this paper, we provide improved bounds on the complexity of solving $\ell_p$-Lipchitz convex optimization problem in parallel. We lower bound the depth of highly-parallel algorithms, i.e., the number of rounds required by a parallel algorithm making $O(\mathrm{poly}(d))$ queries per round to compute an $\epsilon$-approximate minimizer of a $\ell_p$-Lipschitz, $d$-dimensional convex function over the unit $\ell_p$ ball. We provide a framework for proving lower bounds for parallel $\ell_p$-Lipschitz convex optimization that generalizes prior lower bound proofs and for all $p \in (1,\infty)$ (other than 2) improves the depth for which it can be shown that no super-polylogarithmic improvement over sequential algorithms is possible. We also prove a variety of new lower bounds for $p>2$. Notably, for $p=\infty$, we establish the near optimal parallel complexity of the class of ball-acceleration methods up to depth $\tilde{O}(\sqrt{d})$, which is the first near-optimality result in the parallel convex optimization setting for an algorithm other than mirror descent. Additionally, by providing new algorithms we characterize the optimal depth needed to solve to accuracy $\epsilon = d^{-1/4}$ for all $p \geq 2$ (up to polylogarithmic factors). We also provide extensions of our lower bounds to parallel quantum $\ell_p$-Lipschitz convex optimization.