We consider the optimization problem of minimizing the sum-of-nonconvex
function, i.e., a convex function that is the average of nonconvex components.
The existing stochastic algorithms for such a problem only focus on a single
machine and the centralized scenario. In this paper, we study the
sum-of-nonconvex optimization in the decentralized setting. We present a new
theoretical analysis of the PMGT-SVRG algorithm for this problem and prove the
linear convergence of their approach. However, the convergence rate of the
PMGT-SVRG algorithm has a linear dependency on the condition number, which is
undesirable for the ill-conditioned problem. To remedy this issue, we propose
an accelerated stochastic decentralized first-order algorithm by incorporating
the techniques of acceleration, gradient tracking, and multi-consensus mixing
into the SVRG algorithm. The convergence rate of the proposed method has a
square-root dependency on the condition number. The numerical experiments
validate the theoretical guarantee of our proposed algorithms on both synthetic
and real-world datasets.

本文研究分散设置中的非凸函数求和最小化优化问题，提出了 PMGT-SVRG 算法的新的理论分析，证明了其方法的线性收敛性。然而，PMGT-SVRG 算法的收敛速度与条件数呈线性依赖关系，这对于病态问题而言是不理想的。为了解决这个问题，我们提出了一种结合加速、梯度跟踪和多共识混合技术的加速随机分散一阶算法，该方法的收敛速度与条件数呈平方根依赖关系。数值实验验证了我们提出算法在合成和真实数据集上理论保证的有效性。