Id: arxiv/2611.07675 Url: https://arxiv.org/abs/2611.07675 Tags: math.OC, cs.AI, cs.CC Score: 0 Title: Randomized Parallel Complexity of Weakly Convex Optimization Domain: math.OC Source: arxiv Authors: Kang Liu Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-05 Page: https://delphi.science/r/arxiv/2611.07675 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…