arXiv cs.AI· Kang Liu·· 12 小时前AI 评分18
弱凸优化的随机并行复杂度研究
Randomized Parallel Complexity of Weakly Convex Optimization
AI 导读
研究聚焦非光滑弱凸函数近似稳定点的查询轮数下界：在给定参数区间内，即使每轮并行发起多项式数量查询的随机算法，标准次梯度速率在高维下仍为最优。利用实数轴序结构，仅用函数值的确定性算法可将轮复杂度降至对数级，并行查询还能进一步减少；即使每次查询返回整个次微分，匹配下界依然成立。
正文 · 原文
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