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 study a variant of a recently introduced min-max optimization framework
where the max-player is constrained to update its parameters in a greedy manner
until it reaches a first-order stationary point. Our equilibrium definition for
this framework depends on a proposal distribution which the min-player uses to
choose directions in which to update its parameters. We show that, given a
smooth and bounded nonconvex-nonconcave objective function, access to any
proposal distribution for the min-player's updates, and stochastic gradient
oracle for the max-player, our algorithm converges to the aforementioned
approximate local equilibrium in a number of iterations that does not depend on
the dimension. The equilibrium point found by our algorithm depends on the
proposal distribution, and when applying our algorithm to train GANs we choose
the proposal distribution to be a distribution of stochastic gradients. We
empirically evaluate our algorithm on challenging nonconvex-nonconcave
test-functions and loss functions arising in GAN training. Our algorithm
converges on these test functions and, when used to train GANs, trains stably
on synthetic and real-world datasets and avoids mode collapse

研究了一种新型的 min-max 优化框架，其中 max-player 在贪心策略下更新参数至一阶稳定点；给出了在平稳性要求下的定理证明，提出了一种利用随机梯度估计的 GAN 训练算法，成功地避免了模式崩溃的问题。

一种收敛且与维度无关的极小 - 极大优化算法

A Convergent and Dimension-Independent Min-Max Optimization Algorithm

We study finite-sum nonconvex optimization problems, where the objective
function is an average of $n$ nonconvex functions. We propose a new stochastic
gradient descent algorithm based on nested variance reduction. Compared with
conventional stochastic variance reduced gradient (SVRG) algorithm that uses
two reference points to construct a semi-stochastic gradient with diminishing
variance in each iteration, our algorithm uses $K+1$ nested reference points to
build a semi-stochastic gradient to further reduce its variance in each
iteration. For smooth nonconvex functions, the proposed algorithm converges to
an $\epsilon$-approximate first-order stationary point (i.e., $\|\nabla
F(\mathbf{x})\|_2\leq \epsilon$) within $\tilde O(n\land
\epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$ number of stochastic
gradient evaluations. This improves the best known gradient complexity of SVRG
$O(n+n^{2/3}\epsilon^{-2})$ and that of SCSG $O(n\land
\epsilon^{-2}+\epsilon^{-10/3}\land n^{2/3}\epsilon^{-2})$. For gradient
dominated functions, our algorithm also achieves better gradient complexity
than the state-of-the-art algorithms. Thorough experimental results on
different nonconvex optimization problems back up our theory.

我们提出了一种基于嵌套方差降低的新随机梯度下降算法，可用于解决有限个数个、非凸函数的优化问题，并且在平滑非凸函数上具有比现有算法更好的梯度复杂度。