Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Yuyang Deng;M. Mahdavi
中科院分区：
文献类型：
--
作者：
Yuyang Deng;M. Mahdavi
在本文中，我们证明 Local (S)GD（或 FedAvg）可以在多项式时间内优化具有修正线性单元（ReLU）激活函数的深度神经网络。尽管在通信高效的分布式优化中，局部 SGD 已经建立了优化一般平滑函数的收敛理论，但其在非平滑 ReLU 网络上的收敛仍然缺乏充分的理论理解。许多平滑函数的局部 SGD 分析中使用的关键属性是梯度 Lipschitzness，这样局部模型上的梯度不会与平均模型上的梯度相差太远。然而，这种良好的性质在具有非平滑 ReLU 激活函数的网络中并不成立。我们发现，即使 ReLU 网络不承认梯度 Lipschitzness 属性，在 Local SGD 的动态作用下，局部模型和平均模型上的梯度之间的差异也不会发生太大变化。我们通过大量的实验验证了我们的理论结果。这项工作首次展示了局部 SGD 在非平滑函数上的收敛性，并将阐明深度神经网络联合训练的优化理论。
In this paper we prove that Local (S)GD (or FedAvg) can optimize deep neural networks with Rectified Linear Unit (ReLU) activation function in polynomial time. Despite the established convergence theory of Local SGD on optimizing general smooth functions in communication-efficient distributed optimization, its convergence on non-smooth ReLU networks still eludes full theoretical understanding. The key property used in many Local SGD analysis on smooth function is gradient Lipschitzness, so that the gradient on local models will not drift far away from that on averaged model. However, this decent property does not hold in networks with non-smooth ReLU activation function. We show that, even though ReLU network does not admit gradient Lipschitzness property, the difference between gradients on local models and average model will not change too much, under the dynamics of Local SGD. We validate our theoretical results via extensive experiments. This work is the first to show the convergence of Local SGD on non-smooth functions, and will shed lights on the optimization theory of federated training of deep neural networks.