Lower bounds for parallel and randomized convex optimization
From MaRDI portal
Abstract: 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 () and spaces. Our work provides a more general approach for proving lower bounds in the setting of parallel convex optimization.
Recommendations
- On parallel complexity of nonsmooth convex optimization
- Parallel coordinate descent methods for big data optimization
- Parallel algorithms and probability of large deviation for stochastic convex optimization problems
- On lower complexity bounds for large-scale smooth convex optimization
- Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent
Cites work
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 194093 (Why is no real title available?)
- A new approach to computing maximum flows using electrical flows
- Accelerated methods for nonconvex optimization
- An algorithm for variable density sampling with block-constrained acquisition
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Area-convexity, _ regularization, and undirected multicommodity flow
- High-dimensional statistics. A non-asymptotic viewpoint
- Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
- On lower complexity bounds for large-scale smooth convex optimization
- On parallel complexity of nonsmooth convex optimization
- Optimal Affine-Invariant Smooth Minimization Algorithms
- Optimal methods of smooth convex minimization
- Preserving statistical validity in adaptive data analysis (extended abstract)
- Randomized smoothing for stochastic optimization
- Sharp uniform convexity and smoothness inequalities for trace norms
- Smooth Optimization with Approximate Gradient
- The best constants in the Khintchine inequality
Cited in
(8)- Parallel algorithms and probability of large deviation for stochastic convex optimization problems
- Optimization on a finer scale: bounded local subgradient variation perspective
- Lower bounds for non-convex stochastic optimization
- Complementary composite minimization, small gradients in general norms, and applications
- Vaidya's method for convex stochastic optimization problems in small dimension
- On parallel complexity of nonsmooth convex optimization
- Generalized momentum-based methods: a Hamiltonian perspective
- Lower bounds for maximal and convex layers problems
This page was built for publication: Lower bounds for parallel and randomized convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969036)
