Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound

Abstract

We improve the over-parametrization size over two beautiful results [Li and Liang' 2018] and [Du, Zhai, Poczos and Singh' 2019] in deep learning theory.

References in corpus (16)

• Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
• Wide Residual Networks
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Training Very Deep Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• On the Convergence Rate of Training Recurrent Neural Networks
• Learning ReLUs via Gradient Descent
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• On the Computational Efficiency of Training Neural Networks
• SGD Learns the Conjugate Kernel Class of the Network
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Width Provably Matters in Optimization for Deep Linear Neural Networks

Cited by in corpus (33)

• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• On Convergence and Generalization of Dropout Training
• Memory capacity of neural networks with threshold and ReLU activations
• Learning Parities with Neural Networks
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
• Generalized Leverage Score Sampling for Neural Networks
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Hardness of Learning Neural Networks with Natural Weights
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Enhancing Adversarial Defense by k-Winners-Take-All
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Subquadratic Overparameterization for Shallow Neural Networks
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Quadratic number of nodes is sufficient to learn a dataset via gradient descent