Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem

Abstract

Deep learning (DL) has had unprecedented success and is now entering scientific computing with full force. However, current DL methods typically suffer from instability, even when universal approximation properties guarantee the existence of stable neural networks (NNs). We address this paradox by demonstrating basic well-conditioned problems in scientific computing where one can prove the existence of NNs with great approximation qualities, however, there does not exist any algorithm, even randomised, that can train (or compute) such a NN. For any positive integers $K>2$ and $L$, there are cases where simultaneously: (a) no randomised training algorithm can compute a NN correct to $K$ digits with probability greater than $1/2$, (b) there exists a deterministic training algorithm that computes a NN with $K-1$ correct digits, but any such (even randomised) algorithm needs arbitrarily many training data, (c) there exists a deterministic training algorithm that computes a NN with $K-2$ correct digits using no more than $L$ training samples. These results imply a classification theory describing conditions under which (stable) NNs with a given accuracy can be computed by an algorithm. We begin this theory by establishing sufficient conditions for the existence of algorithms that compute stable NNs in inverse problems. We introduce Fast Iterative REstarted NETworks (FIRENETs), which we both prove and numerically verify are stable. Moreover, we prove that only $\mathcal{O}(|\log (\epsilon )|)$ layers are needed for an $\epsilon$-accurate solution to the inverse problem.

14 pages + SI Appendix

References in corpus (6)

• Results of the 2020 fastMRI Challenge for Machine Learning MR Image Reconstruction
• Advancing machine learning for MR image reconstruction with an open competition: Overview of the 2019 fastMRI challenge
• Solving Inverse Problems With Deep Neural Networks -- Robustness Included?
• The Numerics of Phase Retrieval
• On Adversarial Examples and Stealth Attacks in Artificial Intelligence Systems
• Improving Robustness of Deep-Learning-Based Image Reconstruction

Cited by in corpus (14)

• The Free Energy Principle for Perception and Action: A Deep Learning Perspective
• Physical Activation Functions (PAFs): An Approach for More Efficient Induction of Physics into Physics-Informed Neural Networks (PINNs)
• Convergence Rates for Learning Linear Operators from Noisy Data
• Limitations of Deep Learning for Inverse Problems on Digital Hardware
• Physics-informed compressed sensing for PC-MRI: an inverse Navier-Stokes problem
• Insurance pricing with hierarchically structured data: An illustration with a workers' compensation insurance portfolio
• High-dimensional separability for one- and few-shot learning
• The Feasibility and Inevitability of Stealth Attacks
• A Comparative Study of Deep Learning and Iterative Algorithms for Joint Channel Estimation and Signal Detection in OFDM Systems
• NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems
• Bayesian inverse Navier-Stokes problems: joint flow field reconstruction and parameter learning
• Dual Accuracy-Quality-Driven Neural Network for Prediction Interval Generation
• Localized adversarial artifacts for compressed sensing MRI
• The limit of human intelligence