arXiv cs.AI· Kang Liu·· 11 小时前AI 评分18
弱凸优化的随机并行复杂度研究
Randomized Parallel Complexity of Weakly Convex Optimization
AI 导读
研究聚焦非光滑弱凸函数近似稳定点的查询轮数下界：在给定参数区间内，即使每轮并行发起多项式数量查询的随机算法，标准次梯度速率在高维下仍为最优。利用实数轴序结构，仅用函数值的确定性算法可将轮复杂度降至对数级，并行查询还能进一步减少；即使每次查询返回整个次微分，匹配下界依然成立。
正文 · AI 翻译
摘要：我们研究寻找非光滑弱凸函数近似驻点所需的最少查询轮数，以 Moreau 包络的梯度来衡量。每一轮允许多个同时查询。在所述参数范围内，标准次梯度速率在足够高的维度下是最优的，即使对于每轮进行多项式数量并行查询的随机算法也是如此。随后我们展示实数轴的序结构如何实现更快的搜索：一种仅使用函数值的确定性算法实现了对数轮复杂度，并通过并行查询进一步降低。即使每次查询返回整个次微分，匹配的下界仍然成立。综合来看，这些结果阐明了维度在决定弱凸优化中并行查询收益方面的作用。
| 学科： | 优化与控制（math.OC）；人工智能（cs.AI）；计算复杂性（cs.CC） |
| 引用为： | arXiv:2611.07675 [math.OC] |
| （或 arXiv:2611.07675v1 [math.OC] 查看此版本） | |
| https://doi.org/10.48550/arXiv.2611.07675 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Kang Liu [查看邮箱]
[v1]
2026年11月5日星期四 09:04:17 UTC（28 KB）
来源：arXiv cs.AI · arxiv.org