Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time

• URL: http://arxiv.org/abs/2107.10868v1
• Date: Thu, 22 Jul 2021 18:06:33 GMT
• Title: Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Abstract summary: Local (S)GD (or FedAvg) can optimize two-layer neural networks with Rectified Linear Unit (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.
• Score: 15.04034188283642
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we prove that Local (S)GD (or FedAvg) can optimize two-layer 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.

Related papers

• Non-Singularity of the Gradient Descent map for Neural Networks with Piecewise Analytic Activations [53.348574336527854]
  We investigate the neural network map as a function on the space of weights and biases.<n>We prove, for the first time, the non-singularity of the gradient descent (GD) map on the loss landscape of realistic neural network architectures.
  arXiv  Detail & Related papers  (2025-10-28T14:34:33Z)
• Langevin Dynamics: A Unified Perspective on Optimization via Lyapunov Potentials [15.718093624695552]
  We analyze the convergence of Gradient Langevin Dynamics (SGLD) to global minima based on Lyapunov potentials and optimization. We provide 1) improved in the setting of previous works SGLD for optimization, 2) first finite gradient complexity for SGLD, and 3) prove if continuous-time Langevin Dynamics succeeds for optimization, then discrete-time SGLD succeeds under mild regularity assumptions.
  arXiv  Detail & Related papers  (2024-07-05T05:34:10Z)
• Equidistribution-based training of Free Knot Splines and ReLU Neural Networks [0.0]
  We show that the $L$ based approximation problem is ill-conditioned using shallow neural networks (NNs) with a rectified linear unit (ReLU) activation function. We propose a two-level procedure for training the FKS by first solving the nonlinear problem of finding the optimal knot locations. We then determine the optimal weights and knots of the FKS by solving a nearly linear, well-conditioned problem.
  arXiv  Detail & Related papers  (2024-07-02T10:51:36Z)
• GD doesn't make the cut: Three ways that non-differentiability affects neural network training [5.439020425819001]
  This paper critically examines the distinctions between methods applied to non-differentiable functions (NGDMs) and classical gradient descents (GDs) for differentiable functions. Our work identifies critical misunderstandings of algorithms in influential literature, stemming from an overreliance on strong assumptions.
  arXiv  Detail & Related papers  (2024-01-16T15:11:29Z)
• Efficient and Flexible Neural Network Training through Layer-wise Feedback Propagation [49.44309457870649]
  We present Layer-wise Feedback Propagation (LFP), a novel training principle for neural network-like predictors. LFP decomposes a reward to individual neurons based on their respective contributions to solving a given task. Our method then implements a greedy approach reinforcing helpful parts of the network and weakening harmful ones.
  arXiv  Detail & Related papers  (2023-08-23T10:48:28Z)
• Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction [49.66486092259376]
  The mean-field Langevin dynamics (MFLD) is a nonlinear generalization of the Langevin dynamics that incorporates a distribution-dependent drift. Recent works have shown that MFLD globally minimizes an entropy-regularized convex functional in the space of measures. We provide a framework to prove a uniform-in-time propagation of chaos for MFLD that takes into account the errors due to finite-particle approximation, time-discretization, and gradient approximation.
  arXiv  Detail & Related papers  (2023-06-12T16:28:11Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  We show that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification. Our results indicate that interpolating with smoother functions leads to better generalization.
  arXiv  Detail & Related papers  (2023-05-30T19:37:44Z)
• Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
  The linearized-Laplace approximation (LLA) has been shown to be effective and efficient in constructing Bayesian neural networks. We study the usefulness of the LLA in Bayesian optimization and highlight its strong performance and flexibility.
  arXiv  Detail & Related papers  (2023-04-17T14:23:43Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  We study weight decay regularized training problems of deep neural networks with threshold activations. We derive a simplified convex optimization formulation when the dataset can be shattered at a certain layer of the network.
  arXiv  Detail & Related papers  (2023-03-06T18:59:13Z)
• Implicit Stochastic Gradient Descent for Training Physics-informed Neural Networks [51.92362217307946]
  Physics-informed neural networks (PINNs) have effectively been demonstrated in solving forward and inverse differential equation problems. PINNs are trapped in training failures when the target functions to be approximated exhibit high-frequency or multi-scale features. In this paper, we propose to employ implicit gradient descent (ISGD) method to train PINNs for improving the stability of training process.
  arXiv  Detail & Related papers  (2023-03-03T08:17:47Z)
• Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions [47.276004075767176]
  We develop software for convex optimization of two-layer neural networks with ReLU activation functions. We show that convex gated ReLU models obtain data-dependent algorithms for the ReLU training problem.
  arXiv  Detail & Related papers  (2022-02-02T23:50:53Z)
• Non-Gradient Manifold Neural Network [79.44066256794187]
  Deep neural network (DNN) generally takes thousands of iterations to optimize via gradient descent. We propose a novel manifold neural network based on non-gradient optimization.
  arXiv  Detail & Related papers  (2021-06-15T06:39:13Z)
• FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis [27.022551495550676]
  This paper presents a new class of convergence analysis for FL, Learning Neural Kernel (FL-NTK), which corresponds to overterized Reparamterized ReLU neural networks trained by gradient descent in FL. Theoretically, FL-NTK converges to a global-optimal solution at atrivial rate with properly tuned linear learning parameters.
  arXiv  Detail & Related papers  (2021-05-11T13:05:53Z)
• An improved convergence analysis for decentralized online stochastic non-convex optimization [17.386715847732468]
  In this paper, we show that a technique called GT-Loakjasiewics (GT-Loakjasiewics) satisfies the existing condition GT-Loakjasiewics (GT-Loakjasiewics) satisfies the current best convergence rates. The results are not only immediately applicable but also the currently known best convergence rates.
  arXiv  Detail & Related papers  (2020-08-10T15:29:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.