Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

Yuanyu Wan, Lan Xue, Haomin Bai, Tong Wei, Mingli Song

arXivarxiv/2610.05789Oct 5, 2026math.OCscore 0

We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of $n$ nodes, with the goal of finding an $(δ,ε)$-Goldstein stationary point. The best existing algorithm achieves $O(δ^{-1}(ε^{-3}+dε^{-1}))$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))$ communication complexity, where $d$ is the problem dimension and $γ$ is the spectral gap of the communication matrix. However, the polynomial dependence on $d$ can be a major bottleneck in high-dimensional regimes. In this paper, we propose a novel algorithm that achieves $O(δ^{-1}ε^{-3})$ sample…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.05789
curl -X POST /api/v1/records/arxiv/2610.05789/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.05789/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'