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 $(\delta,\epsilon)$-Goldstein stationary point. The best existing algorithm achieves $O(\delta^{-1}(\epsilon^{-3}+d\epsilon^{-1}))$ sample complexity and $\widetilde{O}(\gamma^{-1/2}\delta^{-1}(\epsilon^{-3}+d\epsilon^{-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(\delta^{-1}\epsilon^{-3})$ sample complexity and $\widetilde{O}(\gamma^{-1/2}\delta^{-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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2610.05789 [math.OC]

(or arXiv:2610.05789v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2610.05789 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.