mlsanityData to 7 Oct 2026

On the Computational Efficiency of Training Neural Networks

arXiv 1410.1141 ↗First posted 5 Oct 2014cs.LG cs.AI stat.MLcited by 71

Not on the map. Why?

Abstract (arXiv)

It is well-known that neural networks are computationally hard to train. On the other hand, in practice, modern day neural networks are trained efficiently using SGD and a variety of tricks that include different activation functions (e.g. ReLU), over-specification (i.e., train networks which are larger than needed), and regularization. In this paper we revisit the computational complexity of training neural networks from a modern perspective. We provide both positive and negative results, some of them yield new provably efficient and practical algorithms for training certain types of neural networks.

Key facts. Cited by 71 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Oct 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 19; 2023: 12; 2024: 19; 2025: 4; 2026: 5.

71 papers.

Sort:

  1. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
  2. 2023Predicting Grokking Long Before it Happens: A look into the loss landscape of models which grokcited by 31
  3. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  4. 2021Augmenting Deep Classifiers with Polynomial Neural Networkscited by 21
  5. 2021On Expressivity and Trainability of Quadratic Networkscited by 19
  6. 2023FedVS: Straggler-Resilient and Privacy-Preserving Vertical Federated Learning for Split Modelscited by 17
  7. 2024On Computationally Efficient Multi-Class Calibrationcited by 16
  8. 2021Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Timecited by 14
  9. 2021Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networkscited by 14
  10. 2022A Convergence Theory for Over-parameterized Variational Quantum Eigensolverscited by 14
  11. 2022Learning a Single Neuron for Non-monotonic Activation Functionscited by 13
  12. 2021Landscape analysis for shallow neural networks: complete classification of critical points for affine target functionscited by 11
38 more
  1. 2023Temporal Supervised Contrastive Learning for Modeling Patient Risk Progressioncited by 10
  2. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  3. 2022Annihilation of Spurious Minima in Two-Layer ReLU Networkscited by 9
  4. 2025Hadamard product in deep learning: Introduction, Advances and Challengescited by 9
  5. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  6. 2022Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian datacited by 8
  7. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  8. 2023Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernelscited by 8
  9. 2024No Free Prune: Information-Theoretic Barriers to Pruning at Initializationcited by 8
  10. 2021A spectral-based analysis of the separation between two-layer neural networks and linear methodscited by 7
  11. 2024A Survey of Privacy Threats and Defense in Vertical Federated Learning: From Model Life Cycle Perspectivecited by 7
  12. 2022An Information-Theoretic Framework for Supervised Learningcited by 6
  13. 2023Towards NeuroAI: Introducing Neuronal Diversity into Artificial Neural Networkscited by 6
  14. 2024Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embeddingcited by 6
  15. 2024Early Directional Convergence in Deep Homogeneous Neural Networks for Small Initializationscited by 6
  16. 2022Quadratic Neuron-empowered Heterogeneous Autoencoder for Unsupervised Anomaly Detectioncited by 5
  17. 2022Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networkscited by 5
  18. 2021A Convergence Theory Towards Practical Over-parameterized Deep Neural Networkscited by 4
  19. 2023Efficient CNNs via Passive Filter Pruningcited by 4
  20. 2023Criticality versus uniformity in deep neural networkscited by 3
  21. 2024Towards Narrowing the Generalization Gap in Deep Boolean Networkscited by 3
  22. 2024Neural Networks Generalize on Low Complexity Datacited by 3
  23. 2021Ladder Polynomial Neural Networkscited by 2
  24. 2022SoK: Privacy Preserving Machine Learning using Functional Encryption: Opportunities and Challengescited by 2
  25. 2022Towards Theoretical Analysis of Transformation Complexity of ReLU DNNscited by 2
  26. 2022Blind Estimation of a Doubly Selective OFDM Channel: A Deep Learning Algorithm and Theorycited by 2
  27. 2022Is Stochastic Gradient Descent Near Optimal?cited by 2
  28. 2023Gradient Descent Fails to Learn High-frequency Functions and Modular Arithmeticcited by 2
  29. 2024Improving conversion rate prediction via self-supervised pre-training in online advertisingcited by 2
  30. 2024Efficient Quantum Circuits for Machine Learning Activation Functions including Constant T-depth ReLUcited by 2
  31. 2024Generalized Population-Based Training for Hyperparameter Optimization in Reinforcement Learningcited by 2
  32. 2024Simmering: Sufficient is better than optimal for training neural networkscited by 2
  33. 2025Training Large Neural Networks With Low-Dimensional Error Feedbackcited by 2
  34. 2025Is In-Context Learning Learning?cited by 2
  35. 2026Deep Networks Learn Deep Hierarchical Modelscited by 2
  36. 2022Effective training-time stacking for ensembling of deep neural networkscited by 1
  37. 2022On the Study of Sample Complexity for Polynomial Neural Networkscited by 1
  38. 2022Efficient Similarity-based Passive Filter Pruning for Compressing CNNscited by 1

50 most cited of 71 All 71 (JSON)