Complexity of Highly Parallel Non-Smooth Convex Optimization

Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford

Abstract: 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 $\mathrm{poly}(d)$ gradient queries in parallel. We show that in this case gradient descent is optimal only up to $\tilde{O}(\sqrt{d})$ rounds of interactions with the oracle. The lower bound improves upon a decades old construction by Nemirovski which proves optimality only up to $d^{1/3}$ rounds (as recently observed by Balkanski and Singer), and the suboptimality of gradient descent after $\sqrt{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.

1. Introduction

In the landscape of convex optimization, non-smooth problems—where functions exhibit sharp "kinks" or discontinuities in their gradients—represent a fundamental challenge. For decades, the sequential oracle model has dictated our understanding of these problems: an algorithm queries a gradient, receives a response, and iterates. In this sequential regime, Gradient Descent (GD) is known to be optimal until the number of iterations approaches the dimension $d$ of the problem.

However, the rise of massive parallel computing necessitates a re-evaluation of these limits. This paper investigates the "highly parallel" setting, where an algorithm can query $\mathrm{poly}(d)$ gradients simultaneously in each round. The central question is identifying the "critical depth"—the point at which simple local search strategies like Gradient Descent fail to be optimal and more sophisticated accelerated methods must take over.

2. The Parallel Oracle Model

We consider a setting where an algorithm interacts with a highly parallel gradient oracle. In each round $t$, the algorithm provides a batch of query points $x_{t,1}, \dots, x_{t,q}$ where $q = \mathrm{poly}(d)$. The oracle returns the gradients $\nabla f(x_{t,i})$ for all points in the batch. The goal is to minimize a non-smooth convex function $f$ using the minimum number of rounds (depth), regardless of the total number of queries (work).

3. The $\sqrt{d}$ Barrier for Gradient Descent

A significant contribution of this work is the discovery that in the parallel regime, Gradient Descent remains optimal only for $\tilde{O}(\sqrt{d})$ rounds. This shatters the previous intuition derived from the sequential model, where GD was considered optimal for up to $d$ rounds. This quadratic reduction in the optimality window suggests that parallelization allows for much faster convergence than previously believed, provided one moves beyond simple gradient-based updates.

4. Lower Bound: The Shielded Nemirovski Function

To establish the fundamental limits of any randomized algorithm in this setting, the authors construct a "Shielded Nemirovski function." This construction addresses a weakness in previous lower bounds, which often "leaked" too much information to parallel algorithms.

By surrounding a classic "hard" optimization function with a "wall" or shield function, the authors ensure that unless an algorithm queries points with very specific, low-norm properties, the resulting gradients provide negligible information about the hidden direction of the function's minimum. This shielding proves that parallelism does not provide an immediate shortcut to the solution in the early stages of optimization, effectively pushing the lower bound to $\tilde{O}(\sqrt{d})$.

5. Upper Bound: Smoothing and Acceleration

In the regime where $t > \sqrt{d}$, the paper proposes a new acceleration framework that outperforms Gradient Descent. The method bridges the gap between non-smooth optimization and recent breakthroughs in "highly smooth" optimization through three key components:

  1. Gaussian Smoothing: The non-smooth objective is convolved with a Gaussian distribution to create a differentiable, smooth approximation.
  2. Parallel Sampling: The algorithm utilizes its parallel query capacity to take numerous samples of this smoothed function simultaneously.
  3. Approximate Proximal Oracles: By building a local model from these samples, the algorithm implements a proximal step strategy. This allows the solver to take larger, more informed leaps toward the global minimum than the local steps of Gradient Descent.

This approach achieves a depth complexity of $\tilde{O}(d^{1/3}/\epsilon^{2/3})$, providing a significant improvement over both standard GD and the Center of Gravity method when the target accuracy $\epsilon$ falls between $d^{-1}$ and $d^{-1/2}$.

6. Conclusion and Future Work

This research redefines the complexity classes of parallel non-smooth optimization. While the authors have successfully narrowed the gap between the lower bound ($\sqrt{d}$) and the upper bound ($d^{1/3}$), a theoretical disparity remains. The authors conjecture that the rate of $d^{1/3}/\epsilon^{2/3}$ is the true optimal complexity, though a matching lower bound remains an open problem.

Furthermore, while the proposed algorithm is depth-efficient, it is not necessarily work-efficient, as it requires a massive number of queries to perform Gaussian smoothing. Future research into algorithms that optimize both depth and total query count, as well as extensions into non-convex landscapes, remains a vital frontier for parallel optimization.

Summary updated

Abstract

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 $\mathrm{poly}(d)$ gradient queries in parallel. We show that in this case gradient descent is optimal only up to $\tilde{O}(\sqrt{d})$ rounds of interactions with the oracle. The lower bound improves upon a decades old construction by Nemirovski which proves optimality only up to $d^{1/3}$ rounds (as recently observed by Balkanski and Singer), and the suboptimality of gradient descent after $\sqrt{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.
BibTeX
@inproceedings{bubeck2019complexity,
  author = {Sébastien Bubeck and Qijia Jiang and Yin Tat Lee and Yuanzhi Li and Aaron Sidford},
  title = {{Complexity of Highly Parallel Non-Smooth Convex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=UqMLKanuXHN},
}
Figure