A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
arXiv:2101.04243
Abstract
Deep neural networks' remarkable ability to correctly fit training data when optimized by gradient-based algorithms is yet to be fully understood. Recent theoretical results explain the convergence for ReLU networks that are wider than those used in practice by orders of magnitude. In this work, 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 widths quadratic 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. This construction can be viewed as a novel technique to accelerate training, while its tight finite-width equivalence to Neural Tangent Kernel (NTK) suggests it can be utilized to study generalization as well.
References in corpus (39)
- Language Models are Few-Shot Learners
- Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
- Empirical Evaluation of Rectified Activations in Convolutional Network
- Wide Residual Networks
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Training Very Deep Networks
- Understanding deep learning requires rethinking generalization
- Binarized Neural Networks
- Quantizing deep convolutional networks for efficient inference: A whitepaper
- The Loss Surfaces of Multilayer Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- How Does Batch Normalization Help Optimization?
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Scaling description of generalization with number of parameters in deep learning
- ReZero is All You Need: Fast Convergence at Large Depth
- Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
- Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
- Representation Benefits of Deep Feedforward Networks
- On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
- Deep ReLU Networks Have Surprisingly Few Activation Patterns
- A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
- To understand deep learning we need to understand kernel learning
- Enhanced Convolutional Neural Tangent Kernels
- DiracNets: Training Very Deep Neural Networks Without Skip-Connections
- Risk and parameter convergence of logistic regression
- Global optimality conditions for deep neural networks
- Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
- Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
- Learning One-hidden-layer ReLU Networks via Gradient Descent
- Understanding the Loss Surface of Neural Networks for Binary Classification
- Spurious Valleys in Two-layer Neural Network Optimization Landscapes
- Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
- Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
- Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
- How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
- Faster Least Squares Optimization