Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized? In this wor…
Learning TheoryVocal Bursts Valence PredictionAchieving Small Test Error in Mildly Overparameterized Neural Networks
Recent theoretical works on over-parameterized neural nets have focused on two aspects: optimization and generalization. Many existing works that study optimization and generalization together are based on neural tangent…
Binary ClassificationIs Importance Weighting Incompatible with Interpolating Classifiers?
Importance weighting is a classic technique to handle distribution shifts. However, prior work has presented strong empirical and theoretical evidence demonstrating that importance weights can have little to no effect on…
Efficiently Learning Any One Hidden Layer ReLU Network From Queries
Model extraction attacks have renewed interest in the classic problem of learning neural networks from queries. In this work we give the first polynomial-time algorithm for learning arbitrary one hidden layer neural netw…
Model extractionDeep Double Descent via Smooth Interpolation
The ability of overparameterized deep networks to interpolate noisy data, while at the same time showing good generalization performance, has been recently characterized in terms of the double descent curve for the test …