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

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

cs.LG stat.ML Neural Networks and Applications Stochastic Gradient Optimization Techniques Gaussian Processes and Bayesian Inference Computer Science Mathematics

Paper

Similar papers

Neural Networks Learning and Memorization with (almost) no Over-ParameterizationAmit Daniely2020 · Neural Information Processing Systems In Library

Neural Networks Learning and Memorization with (almost) no Over-ParameterizationAmit Daniely2019 · Neural Information Processing Systems · 37 citations In Library

Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower BoundsS. Vempala, John Wilmes2018 · Annual Conference Computational Learning Theory · 51 citations In Library

An Exponential Improvement on the Memorization Capacity of Deep Threshold NetworksShashank Rajput, Kartik K. Sreenivasan, Dimitris Papailiopoulos et al.2021 · arXiv (Cornell University) · 28 citations In Library

Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent AlgorithmDavid Gamarnik, Eren C. Kızıldağ, Ilias Zadik2024 · Mathematics of Operations Research · 10 citations In Library

Learning One-hidden-layer neural networks via Provable Gradient Descent with Random InitializationShuhao Xia, Yuanming Shi2019 · arXiv.org · 0 citations In Library

Gradient Descent Provably Optimizes Over-parameterized Neural NetworksS. Du, Xiyu Zhai, B. Póczos et al.2018 · International Conference on Learning Representations · 1.4k citations In Library

How Two-Layer Neural Networks Learn, One (Giant) Step at a TimeYatin Dandi, Florent Krząkała, Bruno Loureiro et al.2023 · arXiv (Cornell University) · 69 citations In Library

Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single NeuronWeihang Xu, Simon S. Du2023 · arXiv (Cornell University) · 24 citations In Library

Gradient Descent Quantizes ReLU Network FeaturesHartmut Maennel, O. Bousquet, S. Gelly2018 · arXiv.org · 95 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal