On the Computational Efficiency of Training Neural Networks

Abstract

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.

arXiv commentSection 2 is revised due to a mistake

References in corpus (1)

• Visualizing and Understanding Convolutional Networks

Cited by in corpus (67)

• A Survey on Visual Transformer
• A Convergence Theory for Deep Learning via Over-Parameterization
• PPINN: Parareal Physics-Informed Neural Network for time-dependent PDEs
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Provable approximation properties for deep neural networks
• Generalization in Deep Learning
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Learning Constitutive Relations using Symmetric Positive Definite Neural Networks
• Locating earthquakes with a network of seismic stations via a deep learning method
• Neural Entity Linking: A Survey of Models Based on Deep Learning
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Low-Quality Training Data Only? A Robust Framework for Detecting Encrypted Malicious Network Traffic
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Adding One Neuron Can Eliminate All Bad Local Minima
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Effect of Depth and Width on Local Minima in Deep Learning
• Expressiveness of Rectifier Networks
• From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees
• Meta-learning Pseudo-differential Operators with Deep Neural Networks
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• A Closer Look at Deep Policy Gradients
• Market Driven Multi-domain Network Service Orchestration in 5G Networks
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Multimodal Polynomial Fusion for Detecting Driver Distraction
• Learning from Multi-View Multi-Way Data via Structural Factorization Machines
• On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks
• Complexity of Training ReLU Neural Network
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
• Standardized Non-Intrusive Reduced Order Modeling Using Different Regression Models With Application to Complex Flow Problems
• Partially Encrypted Machine Learning using Functional Encryption
• Statistical-Query Lower Bounds via Functional Gradients
• Implementation of quantum stochastic walks for function approximation, two-dimensional data classification, and sequence classification
• Learnability and Robustness of Shallow Neural Networks Learned With a Performance-Driven BP and a Variant PSO For Edge Decision-Making
• Logarithmic Pruning is All You Need
• On Connected Sublevel Sets in Deep Learning
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Universal Approximation with Quadratic Deep Networks
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Projection-based model reduction of dynamical systems using space-time subspace and machine learning
• Outsourcing Private Machine Learning via Lightweight Secure Arithmetic Computation
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• On the average-case complexity of learning output distributions of quantum circuits
• On Expressivity and Trainability of Quadratic Networks
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Interpreting and Disentangling Feature Components of Various Complexity from DNNs
• Neural Machine Translation: A Review and Survey
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• Efficient Projection-Free Algorithms for Saddle Point Problems
• Optimization Landscapes of Wide Deep Neural Networks Are Benign
• Quadratic Autoencoder (Q-AE) for Low-dose CT Denoising
• Fuzzy Logic Interpretation of Quadratic Networks
• Beyond Lazy Training for Over-parameterized Tensor Decomposition
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• RNN Architecture Learning with Sparse Regularization
• Nonparametric Learning of Two-Layer ReLU Residual Units
• Neural Network Based Qubit Environment Characterization
• TATi-Thermodynamic Analytics ToolkIt: TensorFlow-based software for posterior sampling in machine learning applications
• Learning the mapping $\mathbf{x}\mapsto {\sum }_{i=1}^d{x}_i^2$: the cost of finding the needle in a haystack
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Learning in Gated Neural Networks