# Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization

arXiv: https://arxiv.org/abs/1808.03880 · HTML: https://mlsanity.com/paper/1808.03880/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2018.

## Built on by (most cited first, 12 of 12)

- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)
- [Scen-Opt: A Scenario Optimization Toolbox for Data-Driven Convex Programming](https://mlsanity.com/paper/2610.07846/) (2026)

## Abstract (arXiv)

In this paper we study the limitations of parallelization in convex optimization. A convenient approach to study parallelization is through the prism of adaptivity which is an information theoretic measure of the parallel runtime of an algorithm [BS18]. 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. For the problem of minimizing a non-smooth convex function f:[0,1]n→ ℝ over the unit Euclidean ball, we give a tight lower bound that shows that even when textttpoly(n) queries can be executed in parallel, there is no randomized algorithm with tildeo(n1/3) rounds of adaptivity that has convergence rate that is better than those achievable with a one-query-per-round algorithm. A similar lower bound was obtained by Nemirovski [Nem94], however that result holds for the ℓ∞-setting instead of ℓ2. In addition, we also show a tight lower bound that holds for Lipschitz and strongly convex functions. At the time of writing this manuscript we were not aware of Nemirovski's result. The construction we use is similar to the one in [Nem94], though our analysis is different. Due to the close relationship between this work and [Nem94], we view the research contribution of this manuscript limited and it should serve as an instructful approach to understanding lower bounds for parallel optimization.