Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

arXiv:2610.05789v1 Announce Type: cross Abstract: We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of n nodes, with the goal of finding an (elta,epsilon)-Goldstein stationary point. The best existing algorithm achieves O(elta^{-1}(epsilon^{-3}+depsilon^{-1})) sample complexity and widetilde{O}(gamma^{-1/2}elta^{-1}(epsilon^{-3}+depsilon^{-1})) communication complexity, where d is the problem dimension and gamma 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(elta^{-1}epsilon^{-3}) sample complexity and widetilde{O}(gamma^{-1/2}elta^{-1}epsilon^{-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

• The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
• Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems
• Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity
• Generalized Geometry Block Proximal Linearized Method for Multiblock Nonconvex and Nonsmooth Optimization
• An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization

Source: arXiv cs.LG | 2026-10-06