math.OCNov 5, 2026

Randomized Parallel Complexity of Weakly Convex Optimization

Authors: Kang Liu

Organizations: School of Future Technology, Xi’an Jiaotong University

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.

Explore similar work

May 13, 2026

Min-Max Optimization Requires Exponentially Many Queries

We study the query complexity of min-max optimization of a nonconvex-nonconcave function ff over [0,1]d×[0,1]d[0,1]^d \times [0,1]^d. We show that, given oracle access to ff and to its gradient ∇f\nabla f, any algorithm that finds an ε\varepsilon-approximate stationary point must make a number of queries that is exponential in 1/ε1/\varepsilon or dd.
Jul 21, 2026

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

We prove two lower bounds for the first order oracle complexity of minimizing a dd-dimensional 11-Lipschitz convex function over the unit ball with mm bits of memory. We first show that any such (possibly randomized) algorithm must make Ω~(d2m)\tildeΩ(\frac{d^2}{\sqrt{m}}) oracle queries. For deterministic optimization algorithms, we show that Ω~(min⁡{d1.6,d8/3m2/3})\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\}) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of Ω~(max⁡{d8/3m4/3,d4/3m1/6})\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\}) and Ω~(d5/3m1/3)\tildeΩ(\frac{d^{5/3}}{m^{1/3}}) for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around m≈d2m\approx d^2, where a polylogarithmic change in memory leads to a poly(d)\mathsf{poly}(d) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in dd, our lower bound randomized algorithms is the first to show that Ω~(d2)\tildeΩ(d^2) memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in dd.
Oct 4, 2026

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is Θ~(n+min⁡{n κ,n3/4κ} LΔε−2)\tildeΘ(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2}) throughout κ=L/μ≥1κ=L/μ\ge1, under exact dual initialization and for 0<ε2≤c0LΔ0<\varepsilon^2\le c_0LΔ, where c0>0c_0>0 is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for κ≥nκ\ge\sqrt{n}. For 1≤κ≤n1\leκ\le\sqrt{n}, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains O~(n+n κLΔε−2)\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2}) with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most ε2\varepsilon^2. Under individual smoothness, we also prove Ω(n+min⁡{κ,nκ} LΔε−2)Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2}) for every κ≥1κ\ge1. It matches the polynomial upper rate for a bilinear subclass when κ≥nκ\ge n; the intermediate-condition-number gap remains open.