Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
Abstract
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 Õ(γ−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 complexity and Õ(γ−1/2δ−1ε−3) communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on d can be removed with only logarithmic additional communication.
Related
- Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- Proximal Limited-Memory Quasi-Newton Methods for Nonsmooth Nonconvex Optimization
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- A sequential regularized piecewise affine algorithm for nonconvex nonsmooth multicomposite optimization in RNN training
BibTeX
@misc{wan2026dimensionfree,
title = {{Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization}},
author = {Yuanyu Wan and Lan Xue and Haomin Bai and Tong Wei and Mingli Song},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05789},
eprint = {2610.05789},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05789},
}
RIS
TY - UNPB
TI - Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
AU - Yuanyu Wan
AU - Lan Xue
AU - Haomin Bai
AU - Tong Wei
AU - Mingli Song
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05789
UR - https://arxiv.org/abs/2610.05789
AB - 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 Õ(γ^−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 complexity and Õ(γ^−1/2δ^−1ε^−3) communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on d can be removed with only logarithmic additional communication.
ER -