A hybrid variance-reduced method for decentralized stochastic non-convex optimization
A hybrid variance-reduced method for decentralized stochastic non-convex optimization
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Ran Xin;U. Khan;S. Kar
中科院分区：
文献类型：
--
作者：
Ran Xin;U. Khan;S. Kar
本文研究了n个节点网络上的分散随机优化问题，其中每个节点具有一个光滑的非凸局部代价函数，网络节点的目标是找到一个精确的局部代价和的一阶平稳点。我们关注在线设置，其中每个节点只能通过随机一阶oracle访问其本地成本，该oracle返回精确梯度的带噪声版本。在这种情况下，我们提出了一种新的单环分散混合方差减少随机梯度方法，称为GT-HSGD，它在oracle复杂性和实际实现方面都优于现有方法。GT-HSGD算法实现了专门的局部混合随机梯度估计，这些梯度估计在网络上融合以跟踪全局梯度。值得注意的是，当所需的容错性$\epsilon$足够小时，GT-HSGD实现了与网络拓扑无关的oracle复杂度$O(n^{-1}\epsilon^{-3})$，导致相对于在单个节点上操作的集中式最优在线方差减少方法的线性加速。数值实验说明了我们的主要技术成果。
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.