We investigate the finite-time analysis of finding ($\delta,\epsilon$)-stationary points for nonsmooth nonconvex objectives in decentralized stochastic optimization. A set of agents aim at minimizing a global function using only their local information by interacting over a network. We present a novel algorithm, called Multi Epoch Decentralized Online Learning (ME-DOL), for which we establish the sample complexity in various settings. First, using a recently proposed online-to-nonconvex technique, we show that our algorithm recovers the optimal convergence rate of smooth nonconvex objectives. We then extend our analysis to the nonsmooth setting, building on properties of randomized smoothing and Goldstein-subdifferential sets. We establish the sample complexity of $O(\delta^{-1}\epsilon^{-3})$, which to the best of our knowledge is the first finite-time guarantee for decentralized nonsmooth nonconvex stochastic optimization in the first-order setting (without weak-convexity), matching its optimal centralized counterpart. We further prove the same rate for the zero-order oracle setting without using variance reduction.

我们研究了非光滑非凸目标在分散随机优化中找到($\delta,\epsilon$)-稳定点的有限时间分析。我们提出了一种称为ME-DOL的新算法，并在不同环境中建立了样本复杂性。我们证明了该算法在光滑非凸目标中恢复了最优收敛速度的在线至非凸技术，并扩展了分析到非光滑设置，建立在随机平滑和Goldstein-次微分集的属性上。我们在一阶设置中建立了$O(\delta^{-1}\epsilon^{-3})$的样本复杂度，这是我们所知道的第一次对于分散非光滑非凸随机优化的有限时间保证（无弱凸性），与其最优集中对应。我们进一步证明了在不使用方差减少的零阶预言机设置时相同的速率。

分布式非光滑非凸随机优化的一阶和零阶在线优化视角