mlsanityData to 7 Oct 2026

Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis

arXiv 2206.12802 ↗First posted 26 Jun 2022cs.LG cs.DS stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

A common method in training neural networks is to initialize all the weights to be independent Gaussian vectors. We observe that by instead initializing the weights into independent pairs, where each pair consists of two identical Gaussian vectors, we can significantly improve the convergence analysis. While a similar technique has been studied for random inputs [Daniely, NeurIPS 2020], it has not been analyzed with arbitrary inputs. Using this technique, we show how to significantly reduce the number of neurons required for two-layer ReLU networks, both in the under-parameterized setting with logistic loss, from roughly γ-8 [Ji and Telgarsky, ICLR 2020] to γ-2, where γ denotes the separation margin with a Neural Tangent Kernel, as well as in the over-parameterized setting with squared loss, from roughly n4 [Song and Yang, 2019] to n2, implicitly also improving the recent running time bound of [Brand, Peng, Song and Weinstein, ITCS 2021]. For the under-parameterized setting we also prove new lower bounds that improve upon prior work, and that under certain assumptions, are best possible.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 35 of its 56 references that are in the map. First posted on arXiv 26 Jun 2022.

Builds on

35 of 56 references.

References · 35

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2014Going Deeper with Convolutionscited by 4,231
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  8. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  9. 2021FedBN: Federated Learning on Non-IID Features via Local Batch Normalizationcited by 565
  10. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  11. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  12. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
23 more
  1. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  2. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  3. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  4. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  5. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  6. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  7. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  8. 2019Dynamics of Deep Neural Networks and Neural Tangent Hierarchycited by 96
  9. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  10. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  11. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  12. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  13. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  14. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 58
  15. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  16. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  17. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  18. 2019Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizescited by 29
  19. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  20. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  21. 2019Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problemscited by 23
  22. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  23. 2017Learning Non-overlapping Convolutional Neural Networks with Multiple Kernelscited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 1; 2025: 2; 2026: 1.

15 papers.

Sort:

By area:

  1. 2023An Over-parameterized Exponential Regressioncited by 45
  2. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  3. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  4. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  5. 2022A Sublinear Adversarial Training Algorithmcited by 22
  6. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  7. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  8. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  9. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  10. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  11. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  12. 2023Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTKcited by 2
3 more
  1. 2025Random feature approximation for general spectral methodscited by 2
  2. 2023Random feature approximation for general spectral methodscited by 0
  3. 2026Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operatorscited by 0