论文标题
解决数据异质性：带有样品诱导拓扑的分散SGD的新统一框架
Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology
论文作者
论文摘要
我们开发了一个通用框架，统一了几种基于梯度的随机优化方法，用于在集中式和分布式场景中，用于经验风险最小化问题。该框架取决于引入的增强图的引入，该图形由模拟样品和边缘建模设备间交流和设备内随机梯度计算的边缘。通过正确设计增强图的拓扑结构，我们能够作为特殊情况恢复著名的本地SGD和DSGD算法，并为方差还原（VR）和梯度跟踪（GT）方法提供统一的透视图（GT）方法，例如Saga，local-SVRG和GT-Saga。我们还提供了统一的收敛分析，用于依靠适当的结构化lyapunov函数的平滑和（强烈）凸目标，并且获得的速率可以恢复许多现有算法的最著名结果。速率结果进一步表明，VR和GT方法可以有效地消除设备内部和跨设备内的数据异质性，从而使算法与最佳解决方案的确切收敛性。数值实验证实了本文的发现。
We develop a general framework unifying several gradient-based stochastic optimization methods for empirical risk minimization problems both in centralized and distributed scenarios. The framework hinges on the introduction of an augmented graph consisting of nodes modeling the samples and edges modeling both the inter-device communication and intra-device stochastic gradient computation. By designing properly the topology of the augmented graph, we are able to recover as special cases the renowned Local-SGD and DSGD algorithms, and provide a unified perspective for variance-reduction (VR) and gradient-tracking (GT) methods such as SAGA, Local-SVRG and GT-SAGA. We also provide a unified convergence analysis for smooth and (strongly) convex objectives relying on a proper structured Lyapunov function, and the obtained rate can recover the best known results for many existing algorithms. The rate results further reveal that VR and GT methods can effectively eliminate data heterogeneity within and across devices, respectively, enabling the exact convergence of the algorithm to the optimal solution. Numerical experiments confirm the findings in this paper.
