Lower Bounds for Parallel and Randomized Convex Optimization
This work addresses a foundational question in optimization theory, providing nearly tight lower bounds that are more general than prior results, though it is incremental in extending known limitations to broader settings.
The paper tackles the problem of whether parallelization can speed up convex optimization in the local oracle model, showing that it cannot achieve significant speedups for most geometries and objective functions, with lower bounds nearly matching sequential complexity.
We study the question of whether parallelization in the exploration of the feasible set can be used to speed up convex optimization, in the local oracle model of computation. We show that the answer is negative for both deterministic and randomized algorithms applied to essentially any of the interesting geometries and nonsmooth, weakly-smooth, or smooth objective functions. In particular, we show that it is not possible to obtain a polylogarithmic (in the sequential complexity of the problem) number of parallel rounds with a polynomial (in the dimension) number of queries per round. In the majority of these settings and when the dimension of the space is polynomial in the inverse target accuracy, our lower bounds match the oracle complexity of sequential convex optimization, up to at most a logarithmic factor in the dimension, which makes them (nearly) tight. Prior to our work, lower bounds for parallel convex optimization algorithms were only known in a small fraction of the settings considered in this paper, mainly applying to Euclidean ($\ell_2$) and $\ell_\infty$ spaces. Our work provides a more general approach for proving lower bounds in the setting of parallel convex optimization.