Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks

2020/03/28 by Amit Daniely, Daniely, Amit · 7 citations
Computer Science · Mathematics · Psychology · #Artificial intelligence #Artificial neural network #Cognitive psychology #Computer science #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Memorization #Neural Networks and Applications #Psychology #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2003.12895

published in arXiv (Cornell University) (Cornell University)

arxiv created 2020/03/28 · openalex publication_date 2020/03/28 · arxiv updated 2020/03/31 · openalex created_date 2020/04/03 · openalex updated_date 2026/07/28

Abstract

We prove that a single step of gradient decent over depth two network, with q hidden neurons, starting from orthogonal initialization, can memorize Ω((dq)/(log⁴(d))) independent and randomly labeled Gaussians in ℝ^d. The result is valid for a large class of activation functions, which includes the absolute value.

Citations

• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization

Related

• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Memory capacity of neural networks with threshold and ReLU activations
• Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes