Title: Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization,
Abstract: In this paper we study the limitations of parallelization in convex
optimization. A convenient approach to study parallelization is through the
prism of \emph{adaptivity} which is an information theoretic measure of the
parallel runtime of an algorithm. Informally, adaptivity is the number of
sequential rounds an algorithm needs to make when it can execute
polynomially-many queries in parallel at every round. For combinatorial
optimization with black-box oracle access, the study of adaptivity has recently
led to exponential accelerations in parallel runtime and the natural question
is whether dramatic accelerations are achievable for convex optimization.
Our main result is a spoiler. We show that, in general, parallelization does
not accelerate convex optimization. In particular, for the problem of
minimizing a non-smooth Lipschitz and strongly convex function with black-box
oracle access we give information theoretic lower bounds that indicate that the
number of adaptive rounds of any randomized algorithm exactly match the upper
bounds of single-query-per-round (i.e. non-parallel) algorithms.