In this paper, we propose a distributed algorithm for stochastic smooth,
non-convex optimization. We assume a worker-server architecture where $N$
nodes, each having $n$ (potentially infinite) number of samples, collaborate
with the help of a central server to perform the optimization task. The global
objective is to minimize the average of local cost functions available at
individual nodes. The proposed approach is a non-trivial extension of the
popular parallel-restarted SGD algorithm, incorporating the optimal
variance-reduction based SPIDER gradient estimator into it. We prove
convergence of our algorithm to a first-order stationary solution. The proposed
approach achieves the best known communication complexity $O(\epsilon^{-1})$
along with the optimal computation complexity. For finite-sum problems (finite
$n$), we achieve the optimal computation (IFO) complexity
$O(\sqrt{Nn}\epsilon^{-1})$. For online problems ($n$ unknown or infinite), we
achieve the optimal IFO complexity $O(\epsilon^{-3/2})$. In both the cases, we
maintain the linear speedup achieved by existing methods. This is a massive
improvement over the $O(\epsilon^{-2})$ IFO complexity of the existing
approaches. Additionally, our algorithm is general enough to allow
non-identical distributions of data across workers, as in the recently proposed
federated learning paradigm.

本文提出了一种基于 SPIDER 梯度估计器的分布式算法，可用于处理随机的平滑、非凸优化问题，该算法结合了最优化方差减少技术与并行 SGD 算法，优化了可以用于联邦学习的非相同分布的数据的模型，提出的算法具有最优迭代复杂度复杂度，并实现了与现有方法相同的线性加速。

并行重启 SPIDER -- 与最优计算复杂度的通信高效分布式非凸优化

Parallel Restarted SPIDER -- Communication Efficient Distributed  Nonconvex Optimization with Optimal Computation Complexity

We consider the problem of minimizing the composition of a smooth (nonconvex)
function and a smooth vector mapping, where the inner mapping is in the form of
an expectation over some random variable or a finite sum. We propose a
stochastic composite gradient method that employs an incremental
variance-reduced estimator for both the inner vector mapping and its Jacobian.
We show that this method achieves the same orders of complexity as the best
known first-order methods for minimizing expected-value and finite-sum
nonconvex functions, despite the additional outer composition which renders the
composite gradient estimator biased. This finding enables a much broader range
of applications in machine learning to benefit from the low complexity of
incremental variance-reduction methods.

本文提出了一种基于随机复合梯度法和增量方差缩减估计器的方法来最小化非凸函数的期望值和有限和，尽管丧失了复合梯度估计器的无偏性，但该方法达到了最佳已知一阶方法的复杂度，扩大了增量方差缩减方法在机器学习中的应用范围。