# Complexity of Highly Parallel Non-Smooth Convex Optimization

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2019.

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

- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Never Go Full Batch (in Stochastic Convex Optimization)](https://mlsanity.com/paper/2107.00469/) (2021)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness](https://mlsanity.com/paper/2112.01118/) (2021)
- [The Sample Complexity of Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2404.04931/) (2024)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization](https://mlsanity.com/paper/2102.04259/) (2021)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization](https://mlsanity.com/paper/2406.07373/) (2024)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems](https://mlsanity.com/paper/2404.06720/) (2024)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)
- [Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints](https://mlsanity.com/paper/2610.13787/) (2026)

## Abstract (arXiv)

A landmark result of non-smooth convex optimization is that gradient descent is an optimal algorithm whenever the number of computed gradients is smaller than the dimension d. In this paper we study the extension of this result to the parallel optimization setting. Namely we consider optimization algorithms interacting with a highly parallel gradient oracle, that is one that can answer poly(d) gradient queries in parallel. We show that in this case gradient descent is optimal only up to tildeO(√d) rounds of interactions with the oracle. The lower bound improves upon a decades old construction by Nemirovski which proves optimality only up to d1/3 rounds (as recently observed by Balkanski and Singer), and the suboptimality of gradient descent after √d rounds was already observed by Duchi, Bartlett and Wainwright. In the latter regime we propose a new method with improved complexity, which we conjecture to be optimal. The analysis of this new method is based upon a generalized version of the recent results on optimal acceleration for highly smooth convex optimization.