On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths

• URL: http://arxiv.org/abs/2101.09612v1
• Date: Sun, 24 Jan 2021 00:29:19 GMT
• Title: On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• Authors: Quynh Nguyen
• Abstract summary: We show that gradient descent converges to a global optimum if the widths of all the hidden layers scale at least as $Omega(N8)$ ($N$ being the number of training samples)
• Score: 9.42944841156154
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the global convergence of gradient descent for deep ReLU networks under the square loss. For this setting, the current state-of-the-art results show that gradient descent converges to a global optimum if the widths of all the hidden layers scale at least as $\Omega(N^8)$ ($N$ being the number of training samples). In this paper, we discuss a simple proof framework which allows us to improve the existing over-parameterization condition to linear, quadratic and cubic widths (depending on the type of initialization scheme and/or the depth of the network).

Related papers

• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  We study the type of solutions to which gradient descent converges when used to train a single hidden-layer multivariate ReLU network with the quadratic loss. We prove that although shallow ReLU networks are universal approximators, stable shallow networks are not.
  arXiv  Detail & Related papers  (2023-06-30T09:17:39Z)
• Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data [63.34506218832164]
  In this work, we investigate the implicit bias of gradient flow and gradient descent in two-layer fully-connected neural networks with ReLU activations. For gradient flow, we leverage recent work on the implicit bias for homogeneous neural networks to show that leakyally, gradient flow produces a neural network with rank at most two. For gradient descent, provided the random variance is small enough, we show that a single step of gradient descent suffices to drastically reduce the rank of the network, and that the rank remains small throughout training.
  arXiv  Detail & Related papers  (2022-10-13T15:09:54Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Gradient Descent Optimizes Infinite-Depth ReLU Implicit Networks with Linear Widths [25.237054775800164]
  This paper studies the convergence of gradient flow and gradient descent for nonlinear ReLU activated implicit networks. We prove that both GF and GD converge to a global minimum at a linear rate if the width $m$ of the implicit network is textitlinear in the sample size.
  arXiv  Detail & Related papers  (2022-05-16T06:07:56Z)
• Improved Overparametrization Bounds for Global Convergence of Stochastic Gradient Descent for Shallow Neural Networks [1.14219428942199]
  We study the overparametrization bounds required for the global convergence of gradient descent algorithm for a class of one hidden layer feed-forward neural networks.
  arXiv  Detail & Related papers  (2022-01-28T11:30:06Z)
• Convergence of gradient descent for learning linear neural networks [2.209921757303168]
  We show that gradient descent converges to a critical point of the loss function, i.e., the square loss in this article. In the case of three or more layers we show that gradient descent converges to a global minimum on the manifold matrices of some fixed rank.
  arXiv  Detail & Related papers  (2021-08-04T13:10:30Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• On the Global Convergence of Training Deep Linear ResNets [104.76256863926629]
  We study the convergence of gradient descent (GD) and gradient descent (SGD) for training $L$-hidden-layer linear residual networks (ResNets) We prove that for training deep residual networks with certain linear transformations at input and output layers, both GD and SGD can converge to the global minimum of the training loss.
  arXiv  Detail & Related papers  (2020-03-02T18:34:49Z)
• Revealing the Structure of Deep Neural Networks via Convex Duality [70.15611146583068]
  We study regularized deep neural networks (DNNs) and introduce a convex analytic framework to characterize the structure of hidden layers. We show that a set of optimal hidden layer weights for a norm regularized training problem can be explicitly found as the extreme points of a convex set. We apply the same characterization to deep ReLU networks with whitened data and prove the same weight alignment holds.
  arXiv  Detail & Related papers  (2020-02-22T21:13:44Z)
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology [28.49901662584467]
  We prove that, for deep networks, a single layer of width $N$ following the input layer suffices to ensure a similar guarantee. All the remaining layers are allowed to have constant widths, and form a pyramidal topology.
  arXiv  Detail & Related papers  (2020-02-18T20:21:27Z)

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.