# On the Computational Efficiency of Training Neural Networks

arXiv: https://arxiv.org/abs/1410.1141 · HTML: https://mlsanity.com/paper/1410.1141/

## Key facts

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

## Built on by (most cited first, 30 of 71)

- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [Predicting Grokking Long Before it Happens: A look into the loss landscape of models which grok](https://mlsanity.com/paper/2306.13253/) (2023)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Augmenting Deep Classifiers with Polynomial Neural Networks](https://mlsanity.com/paper/2104.07916/) (2021)
- [On Expressivity and Trainability of Quadratic Networks](https://mlsanity.com/paper/2110.06081/) (2021)
- [FedVS: Straggler-Resilient and Privacy-Preserving Vertical Federated Learning for Split Models](https://mlsanity.com/paper/2304.13407/) (2023)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers](https://mlsanity.com/paper/2205.12481/) (2022)
- [Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time](https://mlsanity.com/paper/2101.02429/) (2021)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Learning a Single Neuron for Non-monotonic Activation Functions](https://mlsanity.com/paper/2202.08064/) (2022)
- [Landscape analysis for shallow neural networks: complete classification of critical points for affine target functions](https://mlsanity.com/paper/2103.10922/) (2021)
- [Temporal Supervised Contrastive Learning for Modeling Patient Risk Progression](https://mlsanity.com/paper/2312.05933/) (2023)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [Annihilation of Spurious Minima in Two-Layer ReLU Networks](https://mlsanity.com/paper/2210.06088/) (2022)
- [Hadamard product in deep learning: Introduction, Advances and Challenges](https://mlsanity.com/paper/2504.13112/) (2025)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian data](https://mlsanity.com/paper/2207.03615/) (2022)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels](https://mlsanity.com/paper/2303.14844/) (2023)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [A spectral-based analysis of the separation between two-layer neural networks and linear methods](https://mlsanity.com/paper/2108.04964/) (2021)
- [A Survey of Privacy Threats and Defense in Vertical Federated Learning: From Model Life Cycle Perspective](https://mlsanity.com/paper/2402.03688/) (2024)
- [Early Directional Convergence in Deep Homogeneous Neural Networks for Small Initializations](https://mlsanity.com/paper/2403.08121/) (2024)
- [An Information-Theoretic Framework for Supervised Learning](https://mlsanity.com/paper/2203.00246/) (2022)
- [Towards NeuroAI: Introducing Neuronal Diversity into Artificial Neural Networks](https://mlsanity.com/paper/2301.09245/) (2023)
- [Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embedding](https://mlsanity.com/paper/2402.05626/) (2024)
- [Quadratic Neuron-empowered Heterogeneous Autoencoder for Unsupervised Anomaly Detection](https://mlsanity.com/paper/2204.01707/) (2022)
- [Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks](https://mlsanity.com/paper/2206.02139/) (2022)
- [Efficient CNNs via Passive Filter Pruning](https://mlsanity.com/paper/2304.02319/) (2023)

## 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.