Abstract
We study the question of whether parallelization in the exploration of thefeasible set can be used to speed up convex optimization, in the local oraclemodel of computation. We show that the answer is negative for bothdeterministic and randomized algorithms applied to essentially any of theinteresting geometries and nonsmooth, weakly-smooth, or smooth objectivefunctions. In particular, we show that it is not possible to obtain apolylogarithmic (in the sequential complexity of the problem) number ofparallel rounds with a polynomial (in the dimension) number of queries perround. In the majority of these settings and when the dimension of the space ispolynomial in the inverse target accuracy, our lower bounds match the oraclecomplexity of sequential convex optimization, up to at most a logarithmicfactor in the dimension, which makes them (nearly) tight. Prior to our work, lower bounds for parallel convex optimization algorithmswere only known in a small fraction of the settings considered in this paper,mainly applying to Euclidean ($\ell_2$) and $\ell_\infty$ spaces. It is unclearwhether the arguments used in this prior work can be extended to general$\ell_p$ spaces. Hence, our work provides a more general approach for provinglower bounds in the setting of parallel convex optimization. Moreover, as aconsequence of our proof techniques, we obtain new anti-concentration boundsfor convex combinations of Rademacher sequences that may be of independentinterest.