A Convergence Theory for Deep Learning via Over-Parameterization

Abstract

Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a long line of works has been focusing on training neural networks with one hidden layer. The theory of multi-layer networks remains largely unsettled. In this work, we prove why stochastic gradient descent (SGD) can find $\text{global minima}$ on the training objective of DNNs in $\text{polynomial time}$. We only make two assumptions: the inputs are non-degenerate and the network is over-parameterized. The latter means the network width is sufficiently large: $\text{polynomial}$ in $L$, the number of layers and in $n$, the number of samples. Our key technique is to derive that, in a sufficiently large neighborhood of the random initialization, the optimization landscape is almost-convex and semi-smooth even with ReLU activations. This implies an equivalence between over-parameterized neural networks and neural tangent kernel (NTK) in the finite (and polynomial) width setting. As concrete examples, starting from randomly initialized weights, we prove that SGD can attain 100% training accuracy in classification tasks, or minimize regression loss in linear convergence speed, with running time polynomial in $n,L$. Our theory applies to the widely-used but non-smooth ReLU activation, and to any smooth and possibly non-convex loss functions. In terms of network architectures, our theory at least applies to fully-connected neural networks, convolutional neural networks (CNN), and residual neural networks (ResNet).

arXiv commentV2 adds citation and V3/V4/V5 polish writing

References in corpus (28)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Continuous control with deep reinforcement learning
• Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
• Wide Residual Networks
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Qualitatively characterizing neural network optimization problems
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Gradient Descent Learns Linear Dynamical Systems
• On the Convergence Rate of Training Recurrent Neural Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• On the Sample Complexity of the Linear Quadratic Regulator
• 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
• Identity Matters in Deep Learning
• Neon2: Finding Local Minima via First-Order Oracles
• Reliably Learning the ReLU in Polynomial Time
• Learning One Convolutional Layer with Overlapping Patches
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Learning Long Term Dependencies via Fourier Recurrent Units
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
• The Computational Complexity of Training ReLU(s)
• A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
• Robust Spectral Filtering and Anomaly Detection

Cited by in corpus (369)

• LoRA: Low-Rank Adaptation of Large Language Models
• On Exact Computation with an Infinitely Wide Neural Net
• FedBN: Federated Learning on Non-IID Features via Local Batch Normalization
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Theory of overparametrization in quantum neural networks
• Scaling description of generalization with number of parameters in deep learning
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Stabilizing the Lottery Ticket Hypothesis
• Ensemble Kalman Inversion: A Derivative-Free Technique For Machine Learning Tasks
• Optimization for deep learning: theory and algorithms
• The Modern Mathematics of Deep Learning
• A Theoretical Analysis of Deep Q-Learning
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• On the Convergence Rate of Training Recurrent Neural Networks
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• Are All Layers Created Equal?
• One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Generalisation error in learning with random features and the hidden manifold model
• Enhanced Convolutional Neural Tangent Kernels
• The Global Landscape of Neural Networks: An Overview
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Deep Unsupervised Learning for Joint Antenna Selection and Hybrid Beamforming
• Adaptive dynamic programming for nonaffine nonlinear optimal control problem with state constraints
• Towards Understanding the Spectral Bias of Deep Learning
• Batch Normalization Biases Residual Blocks Towards the Identity Function in Deep Networks
• Compressing GANs using Knowledge Distillation
• Learning Transferable Parameters for Unsupervised Domain Adaptation
• Analyzing Upper Bounds on Mean Absolute Errors for Deep Neural Network Based Vector-to-Vector Regression
• Neural Tangents: Fast and Easy Infinite Neural Networks in Python
• Kernel and Rich Regimes in Overparametrized Models
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Convergence of Adversarial Training in Overparametrized Neural Networks
• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• Strong error analysis for stochastic gradient descent optimization algorithms
• The learnability scaling of quantum states: restricted Boltzmann machines
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• Breaking Adiabatic Quantum Control with Deep Learning
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Winning the Lottery with Continuous Sparsification
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• On the linearity of large non-linear models: when and why the tangent kernel is constant
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Asymptotics of Wide Networks from Feynman Diagrams
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• A Priori Estimates of the Population Risk for Residual Networks
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Gradient Starvation: A Learning Proclivity in Neural Networks
• ExpandNets: Linear Over-parameterization to Train Compact Convolutional Networks
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• A Selective Overview of Deep Learning
• Elimination of All Bad Local Minima in Deep Learning
• PocketNet: A Smaller Neural Network for Medical Image Analysis
• Stochastic AUC Maximization with Deep Neural Networks
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Orthogonal Gradient Descent for Continual Learning
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Finite Versus Infinite Neural Networks: an Empirical Study
• Relaxed Actor-Critic with Convergence Guarantees for Continuous-Time Optimal Control of Nonlinear Systems
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• A Fine-Grained Spectral Perspective on Neural Networks
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Do Wider Neural Networks Really Help Adversarial Robustness?
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• PAD: Towards Principled Adversarial Malware Detection Against Evasion Attacks
• Neural Thompson Sampling
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Expressive power of complex-valued restricted Boltzmann machines for solving non-stoquastic Hamiltonians
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Multiple Descent: Design Your Own Generalization Curve
• Frequency Bias in Neural Networks for Input of Non-Uniform Density
• Towards Understanding Label Smoothing
• Active Learning for Graph Neural Networks via Node Feature Propagation
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• Distillation $\approx$ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• From Symmetry to Geometry: Tractable Nonconvex Problems
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Mathematical Models of Overparameterized Neural Networks
• A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions
• Theory-Inspired Path-Regularized Differential Network Architecture Search
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Dynamical Isometry and a Mean Field Theory of LSTMs and GRUs
• A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth
• Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• How does Weight Correlation Affect the Generalisation Ability of Deep Neural Networks
• Feature Learning in Infinite-Width Neural Networks
• Asymptotics of Ridge (less) Regression under General Source Condition
• KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey
• Tensor Programs III: Neural Matrix Laws
• Data-Independent Neural Pruning via Coresets
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Network size and weights size for memorization with two-layers neural networks
• Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)
• Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Structure Probing Neural Network Deflation
• How degenerate is the parametrization of neural networks with the ReLU activation function?
• Integrating Deep Neural Networks with Full-waveform Inversion: Reparametrization, Regularization, and Uncertainty Quantification
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Avoiding local minima in Variational Quantum Algorithms with Neural Networks
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Asymptotics of Wide Convolutional Neural Networks
• Towards NNGP-guided Neural Architecture Search
• Exploring Memorization in Adversarial Training
• Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics
• Entanglement Diagnostics for Efficient Quantum Computation
• On Convergence and Generalization of Dropout Training
• Directional convergence and alignment in deep learning
• Memory capacity of neural networks with threshold and ReLU activations
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• On the Neural Tangent Kernel of Deep Networks with Orthogonal Initialization
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• WeMix: How to Better Utilize Data Augmentation
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• On the Similarity between the Laplace and Neural Tangent Kernels
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Decoupling Gating from Linearity
• Fixed-Dimensional and Permutation Invariant State Representation of Autonomous Driving
• Convergence Rates of Variational Inference in Sparse Deep Learning
• Path Length Bounds for Gradient Descent and Flow
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Understanding Overparameterization in Generative Adversarial Networks
• AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks
• Learning Parities with Neural Networks
• Limitations of Lazy Training of Two-layers Neural Networks
• Depth creates no more spurious local minima
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Gradients as Features for Deep Representation Learning
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• Neural tangent kernels, transportation mappings, and universal approximation
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits
• Order and Chaos: NTK views on DNN Normalization, Checkerboard and Boundary Artifacts
• Reproducing Activation Function for Deep Learning
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Graph Neural Bandits
• Initialization Matters: Regularizing Manifold-informed Initialization for Neural Recommendation Systems
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• Large-time asymptotics in deep learning
• The Local Elasticity of Neural Networks
• Early-stopped neural networks are consistent
• On the Convergence and Calibration of Deep Learning with Differential Privacy
• Deep Learning is Singular, and That's Good
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Logarithmic Pruning is All You Need
• Strength of Minibatch Noise in SGD
• On the Global Convergence of Training Deep Linear ResNets
• SALR: Sharpness-aware Learning Rate Scheduler for Improved Generalization
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Solving PDEs on Unknown Manifolds with Machine Learning
• Policy Search with Rare Significant Events: Choosing the Right Partner to Cooperate with
• Hardness of Learning Neural Networks with Natural Weights
• Linear Convergence of Adaptive Stochastic Gradient Descent
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Economy Statistical Recurrent Units For Inferring Nonlinear Granger Causality
• Leveraging Non-uniformity in First-order Non-convex Optimization
• On Connected Sublevel Sets in Deep Learning
• Deep ReLU Networks Preserve Expected Length
• Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
• Distributionally Robust Deep Learning using Hardness Weighted Sampling
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
• Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting
• Approximation power of random neural networks
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• Towards Deepening Graph Neural Networks: A GNTK-based Optimization Perspective
• The asymptotic spectrum of the Hessian of DNN throughout training
• GradSign: Model Performance Inference with Theoretical Insights
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Enhancing Adversarial Defense by k-Winners-Take-All
• Shift Invariance Can Reduce Adversarial Robustness
• Auxiliary Learning for Deep Multi-task Learning
• Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization
• Implicit Regularization via Neural Feature Alignment
• Reinforcement Learning with Function Approximation: From Linear to Nonlinear
• Predicting Training Time Without Training
• A global convergence theory for deep ReLU implicit networks via over-parameterization
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• On generalization bounds for deep networks based on loss surface implicit regularization
• Sparse Deep Learning: A New Framework Immune to Local Traps and Miscalibration
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy
• Adaptive Precision Training (AdaPT): A dynamic fixed point quantized training approach for DNNs
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• AutoLRS: Automatic Learning-Rate Schedule by Bayesian Optimization on the Fly
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Continuous vs. Discrete Optimization of Deep Neural Networks
• Distributed Optimization for Over-Parameterized Learning
• Global Convergence of Three-layer Neural Networks in the Mean Field Regime
• FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysis
• The Discovery of Dynamics via Linear Multistep Methods and Deep Learning: Error Estimation
• Integrated Decision and Control: Towards Interpretable and Computationally Efficient Driving Intelligence
• On the Double Descent of Random Features Models Trained with SGD
• Learning with Gradient Descent and Weakly Convex Losses
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Neural Bandit with Arm Group Graph
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
• Neural Tangent Kernel Maximum Mean Discrepancy
• Orthogonal Over-Parameterized Training
• A Deep Conditioning Treatment of Neural Networks
• The critical locus of overparameterized neural networks
• A Geometric Approach of Gradient Descent Algorithms in Linear Neural Networks
• Supervised Deep Neural Networks (DNNs) for Pricing/Calibration of Vanilla/Exotic Options Under Various Different Processes
• Explicit Explore, Exploit, or Escape ($E^4$): near-optimal safety-constrained reinforcement learning in polynomial time
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Understanding over-parameterized deep networks by geometrization
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Wider Networks Learn Better Features
• Which Minimizer Does My Neural Network Converge To?
• Convergence rates for gradient descent in the training of overparameterized artificial neural networks with piecewise affine activation
• Neural Combinatorial Clustered Bandits for Recommendation Systems
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Plateau Phenomenon in Gradient Descent Training of ReLU networks: Explanation, Quantification and Avoidance
• Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Abstraction Mechanisms Predict Generalization in Deep Neural Networks
• BINet: Learning to Solve Partial Differential Equations with Boundary Integral Networks
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Learning Diverse-Structured Networks for Adversarial Robustness
• Distinguishing rule- and exemplar-based generalization in learning systems
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Extreme Memorization via Scale of Initialization
• Iterative regularization for convex regularizers
• On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime
• Scaling Neural Tangent Kernels via Sketching and Random Features
• Distribution of Classification Margins: Are All Data Equal?
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Embedding Principle of Loss Landscape of Deep Neural Networks
• Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Are wider nets better given the same number of parameters?
• The Future is Log-Gaussian: ResNets and Their Infinite-Depth-and-Width Limit at Initialization
• Towards Understanding the Benefits of Neural Network Parameterizations in Geophysical Inversions: A Study With Neural Fields
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• Provable Regret Bounds for Deep Online Learning and Control
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• A finite sample analysis of the benign overfitting phenomenon for ridge function estimation
• Low Dimensional Landscape Hypothesis is True: DNNs can be Trained in Tiny Subspaces
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Optimization Landscapes of Wide Deep Neural Networks Are Benign
• A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay
• Revisiting minimum description length complexity in overparameterized models
• Learning and Generalization in RNNs
• Rethinking Gauss-Newton for learning over-parameterized models
• Blind Adversarial Pruning: Balance Accuracy, Efficiency and Robustness
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Making Method of Moments Great Again? -- How can GANs learn distributions
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Global Convergence and Geometric Characterization of Slow to Fast Weight Evolution in Neural Network Training for Classifying Linearly Non-Separable Data
• Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• Deep Networks Provably Classify Data on Curves
• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets
• Impact of GPU uncertainty on the training of predictive deep neural networks
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Implicit Bias of Linear RNNs
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Quantifying Epistemic Uncertainty in Deep Learning
• Experiments with Rich Regime Training for Deep Learning
• Task-Projected Hyperdimensional Computing for Multi-Task Learning
• Partition and Code: learning how to compress graphs
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models
• Deep Residual Networks Learn the Geodesic Curve in the Wasserstein Space
• Learning Boolean Circuits with Neural Networks
• Properties of the After Kernel
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• On the Provable Generalization of Recurrent Neural Networks
• Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Asymptotics of Ridge Regression in Convolutional Models
• A Theoretical Analysis of Learning with Noisily Labeled Data
• Rapid training of deep neural networks without skip connections or normalization layers using Deep Kernel Shaping
• Stationary Density Estimation of Itô Diffusions Using Deep Learning
• Associative Convolutional Layers
• Inverse Problem of Nonlinear Schrödinger Equation as Learning of Convolutional Neural Network
• Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation
• Adaptive norms for deep learning with regularized Newton methods
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• Regularized OFU: an Efficient UCB Estimator forNon-linear Contextual Bandit
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• When Are Solutions Connected in Deep Networks?
• Painless step size adaptation for SGD
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths
• Vanishing Curvature and the Power of Adaptive Methods in Randomly Initialized Deep Networks
• Unintended Effects on Adaptive Learning Rate for Training Neural Network with Output Scale Change
• On Symmetry and Initialization for Neural Networks
• Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond
• Tensorization of neural networks for improved privacy and interpretability
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• Training Deep Neural Networks via Branch-and-Bound
• A method of supervised learning from conflicting data with hidden contexts
• One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Implicit regularization of deep residual networks towards neural ODEs
• On Generalization of Adaptive Methods for Over-parameterized Linear Regression
• SGD Through the Lens of Kolmogorov Complexity
• About contrastive unsupervised representation learning for classification and its convergence
• The duality structure gradient descent algorithm: analysis and applications to neural networks
• BN-invariant sharpness regularizes the training model to better generalization
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Directional Convergence Analysis under Spherically Symmetric Distribution
• Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise
• Over-parametrized neural networks as under-determined linear systems
• Associated Learning: Decomposing End-to-end Backpropagation based on Auto-encoders and Target Propagation
• Why Does Multi-Epoch Training Help?
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• A note on regularised NTK dynamics with an application to PAC-Bayesian training