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 $ϵ$-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 $ϵ=d^{-1/4}$ for all $p\ge 2$ (up to polylogarithmic factors). We also provide extensions of our lower bounds to parallel quantum ${\ell }_p$-Lipschitz convex optimization.