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})$ 的样本复杂度，这是我们所知道的第一次对于分散非光滑非凸随机优化的有限时间保证（无弱凸性），与其最优集中对应。我们进一步证明了在不使用方差减少的零阶预言机设置时相同的速率。

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

Online Optimization Perspective on First-Order and Zero-Order  Decentralized Nonsmooth Nonconvex Stochastic Optimization

This paper considers decentralized stochastic optimization over a network of
$n$ nodes, where each node possesses a smooth non-convex local cost function
and the goal of the networked nodes is to find an $\epsilon$-accurate
first-order stationary point of the sum of the local costs. We focus on an
online setting, where each node accesses its local cost only by means of a
stochastic first-order oracle that returns a noisy version of the exact
gradient. In this context, we propose a novel single-loop decentralized hybrid
variance-reduced stochastic gradient method, called GT-HSGD, that outperforms
the existing approaches in terms of both the oracle complexity and practical
implementation. The GT-HSGD algorithm implements specialized local hybrid
stochastic gradient estimators that are fused over the network to track the
global gradient. Remarkably, GT-HSGD achieves a network topology-independent
oracle complexity of $O(n^{-1}\epsilon^{-3})$ when the required error tolerance
$\epsilon$ is small enough, leading to a linear speedup with respect to the
centralized optimal online variance-reduced approaches that operate on a single
node. Numerical experiments are provided to illustrate our main technical
results.

本文研究了分散式随机优化的网络问题，提出了一种新的单循环分散式混合降低方差随机梯度下降算法 GT-HSGD，并度量了其优化性能。

分散式随机非凸优化问题的混合方差缩减方法

A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex  Optimization

We consider decentralized stochastic optimization with the objective function
(e.g. data samples for machine learning task) being distributed over $n$
machines that can only communicate to their neighbors on a fixed communication
graph. To reduce the communication bottleneck, the nodes compress (e.g.
quantize or sparsify) their model updates. We cover both unbiased and biased
compression operators with quality denoted by $\omega \leq 1$ ($\omega=1$
meaning no compression). We (i) propose a novel gossip-based stochastic
gradient descent algorithm, CHOCO-SGD, that converges at rate
$\mathcal{O}\left(1/(nT) + 1/(T \delta^2 \omega)^2\right)$ for strongly convex
objectives, where $T$ denotes the number of iterations and $\delta$ the
eigengap of the connectivity matrix. Despite compression quality and network
connectivity affecting the higher order terms, the first term in the rate,
$\mathcal{O}(1/(nT))$, is the same as for the centralized baseline with exact
communication. We (ii) present a novel gossip algorithm, CHOCO-GOSSIP, for the
average consensus problem that converges in time
$\mathcal{O}(1/(\delta^2\omega) \log (1/\epsilon))$ for accuracy $\epsilon >
0$. This is (up to our knowledge) the first gossip algorithm that supports
arbitrary compressed messages for $\omega > 0$ and still exhibits linear
convergence. We (iii) show in experiments that both of our algorithms do
outperform the respective state-of-the-art baselines and CHOCO-SGD can reduce
communication by at least two orders of magnitudes.

提出了一种基于 gossip 的分散随机优化算法 CHOCO-SGD 和解决平均一致性问题的新型 gossip 算法 CHOCO-GOSSIP，旨在在机器学习任务上实现数据分布和优化，有效降低通信成本并能提高算法效率。