Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
read the original abstract
We study the problem of training deep neural networks with Rectified Linear Unit (ReLU) activation function using gradient descent and stochastic gradient descent. In particular, we study the binary classification problem and show that for a broad family of loss functions, with proper random weight initialization, both gradient descent and stochastic gradient descent can find the global minima of the training loss for an over-parameterized deep ReLU network, under mild assumption on the training data. The key idea of our proof is that Gaussian random initialization followed by (stochastic) gradient descent produces a sequence of iterates that stay inside a small perturbation region centering around the initial weights, in which the empirical loss function of deep ReLU networks enjoys nice local curvature properties that ensure the global convergence of (stochastic) gradient descent. Our theoretical results shed light on understanding the optimization for deep learning, and pave the way for studying the optimization dynamics of training modern deep neural networks.
This paper has not been read by Pith yet.
Forward citations
Cited by 11 Pith papers
-
Limitations of Lazy Training of Two-layers Neural Networks
For quadratic targets in d dimensions, two-layer quadratic networks achieve lower risk when fully trained than in random features or neural tangent regimes if hidden units < d.
-
Generalization in Deep Neural Networks: Minimax Rates for Gradient Methods
The paper derives the first minimax-optimal excess population risk rates for gradient descent and stochastic gradient descent on over-parameterized DNNs by linking their dynamics to kernel methods under polynomial wid...
-
Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks
Establishes first minimax-optimal generalization rates for GD and SGD on deep ReLU networks under polynomial width scaling in the NTK regime.
-
Mild Over-Parameterization Benefits Asymmetric Tensor PCA
A three-phase alternating-update method for asymmetric tensor PCA achieves d to the power of k-minus-2 sample complexity with d-squared memory and improves when signal vectors align.
-
A Theory on Flow Matching with Neural Networks
Establishes convergence guarantees for overparameterized 2-layer ReLU networks in flow matching, generalization bounds for the velocity-field objective, and Wasserstein guarantees for generated samples, using multi-ta...
-
Dual-Stream MLP is All You Need for CTR Prediction
DS-MLP achieves state-of-the-art CTR prediction on three benchmarks using a final vanilla MLP structure trained via knowledge distillation and two alignment strategies.
-
Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models
SPIN lets weak LLMs become strong by self-generating training data from previous model versions and training to prefer human-annotated responses over its own outputs, outperforming DPO even with extra GPT-4 data on be...
-
On Symmetry and Initialization for Neural Networks
For symmetric target functions, chosen initial conditions in one-hidden-layer networks enable SGD to produce generalization guarantees, unlike random initialization.
-
Convergence rates for gradient descent in the training of overparameterized artificial neural networks with piecewise affine activation
Batch gradient descent achieves linear convergence to zero MSE with high probability for sufficiently wide shallow NNs with non-affine piecewise affine activations and distinct inputs.
-
Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
Provides Hessian-based theoretical characterizations of SGD dynamics and a scale-invariant generalization bound for deep nets, backed by experiments on synthetic data, MNIST, and CIFAR-10.
-
Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
Empirical study finds multi-block ADMM outperforms two-block ADMM on optimization and prediction in multi-task learning across all tested datasets and dual step sizes.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.