弱凸优化的随机并行复杂度研究
Randomized Parallel Complexity of Weakly Convex Optimization
AI 导读
一篇 arXiv 论文研究了求非光滑弱凸函数近似驻点所需的最少查询轮数，以 Moreau 包络梯度衡量，每轮允许多个并行查询。结果证明在高维情形下标准次梯度速率是最优的，即使随机算法每轮做多项次并行查询也是如此；而利用实直线的序结构，仅用函数值的确定性算法可实现轮数复杂度。结论阐明了维度在并行查询收益中的作用。
正文 · 原文
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.
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC) |
| Cite as: | arXiv:2611.07675 [math.OC] |
| (or arXiv:2611.07675v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2611.07675 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kang Liu [view email]
[v1]
Thu, 5 Nov 2026 09:04:17 UTC (28 KB)
来源：arXiv cs.AI · arxiv.org