Randomized Parallel Complexity of Weakly Convex Optimization
Abstract
We study the minimum number of query rounds needed to find approximate stationary points of nonsmooth weakly convex functions, measured by the gradient of the Moreau envelope. Each round permits multiple simultaneous queries. In the stated parameter regime, the standard subgradient rate is optimal in sufficiently high dimensions, even for randomized algorithms making polynomially many parallel queries per round. We then show how the order structure of the real line enables faster search: a deterministic algorithm using only function values achieves logarithmic round complexity, with a further reduction through parallel queries. Matching lower bounds hold even when each query returns the entire subdifferential. Together, these results clarify the role of dimension in determining the benefits of parallel queries for weakly convex optimization.
Related
- Global solutions for the sensors placement problem via weakly convex optimization
- Weakly Quasar-Convex Optimization
- Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
BibTeX
@misc{liu2026randomized,
title = {{Randomized Parallel Complexity of Weakly Convex Optimization}},
author = {Kang Liu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07675},
eprint = {2611.07675},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07675},
}
RIS
TY - UNPB
TI - Randomized Parallel Complexity of Weakly Convex Optimization
AU - Kang Liu
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07675
UR - https://arxiv.org/abs/2611.07675
AB - We study the minimum number of query rounds needed to find approximate stationary points of nonsmooth weakly convex functions, measured by the gradient of the Moreau envelope. Each round permits multiple simultaneous queries. In the stated parameter regime, the standard subgradient rate is optimal in sufficiently high dimensions, even for randomized algorithms making polynomially many parallel queries per round. We then show how the order structure of the real line enables faster search: a deterministic algorithm using only function values achieves logarithmic round complexity, with a further reduction through parallel queries. Matching lower bounds hold even when each query returns the entire subdifferential. Together, these results clarify the role of dimension in determining the benefits of parallel queries for weakly convex optimization.
ER -