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

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 176 references that are in the map.
- First posted on arXiv 20 Jan 2021.

## Builds on (most cited first, 30 of 40)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Fully Convolutional Networks for Semantic Segmentation](https://mlsanity.com/paper/1411.4038/) (2014)
- [Rich feature hierarchies for accurate object detection and semantic segmentation](https://mlsanity.com/paper/1311.2524/) (2013)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (2018)
- [Deep Convolutional Neural Network for Inverse Problems in Imaging](https://mlsanity.com/paper/1611.03679/) (2016)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Learning a Variational Network for Reconstruction of Accelerated MRI Data](https://mlsanity.com/paper/1704.00447/) (2017)
- [Deep Learning Techniques for Inverse Problems in Imaging](https://mlsanity.com/paper/2005.06001/) (2020)
- [Audio Adversarial Examples: Targeted Attacks on Speech-to-Text](https://mlsanity.com/paper/1801.01944/) (2018)
- [Image reconstruction by domain transform manifold learning](https://mlsanity.com/paper/1704.08841/) (2017)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds](https://mlsanity.com/paper/1808.10038/) (2018)
- [A Review of Convolutional Neural Networks for Inverse Problems in Imaging](https://mlsanity.com/paper/1710.04011/) (2017)
- [Rational neural networks](https://mlsanity.com/paper/2004.01902/) (2020)
- [A Deep Cascade of Convolutional Neural Networks for MR Image Reconstruction](https://mlsanity.com/paper/1703.00555/) (2017)
- [Advancing machine learning for MR image reconstruction with an open competition: Overview of the 2019 fastMRI challenge](https://mlsanity.com/paper/2001.02518/) (2020)
- [Solving Inverse Problems With Deep Neural Networks -- Robustness Included?](https://mlsanity.com/paper/2011.04268/) (2020)
- [The gap between theory and practice in function approximation with deep neural networks](https://mlsanity.com/paper/2001.07523/) (2020)
- [Convolutional Neural Networks Analyzed via Convolutional Sparse Coding](https://mlsanity.com/paper/1607.08194/) (2016)
- [Nonlinear Approximation and (Deep) ReLU Networks](https://mlsanity.com/paper/1905.02199/) (2019)
- [Deep Unfolded Robust PCA with Application to Clutter Suppression in Ultrasound](https://mlsanity.com/paper/1811.08252/) (2018)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [A formal proof of the Kepler conjecture](https://mlsanity.com/paper/1501.02155/) (2015)
- [Neural networks and rational functions](https://mlsanity.com/paper/1706.03301/) (2017)
- [On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamics](https://mlsanity.com/paper/2007.15623/) (2020)

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

- [Convergence Rates for Learning Linear Operators from Noisy Data](https://mlsanity.com/paper/2108.12515/) (2021)
- [The Free Energy Principle for Perception and Action: A Deep Learning Perspective](https://mlsanity.com/paper/2207.06415/) (2022)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Limits for Learning with Language Models](https://mlsanity.com/paper/2306.12213/) (2023)
- [The mathematics of adversarial attacks in AI -- Why deep learning is unstable despite the existence of stable neural networks](https://mlsanity.com/paper/2109.06098/) (2021)
- [The Feasibility and Inevitability of Stealth Attacks](https://mlsanity.com/paper/2106.13997/) (2021)
- [Physical Activation Functions (PAFs): An Approach for More Efficient Induction of Physics into Physics-Informed Neural Networks (PINNs)](https://mlsanity.com/paper/2205.14630/) (2022)
- [Limitations of Deep Learning for Inverse Problems on Digital Hardware](https://mlsanity.com/paper/2202.13490/) (2022)
- [On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples](https://mlsanity.com/paper/2203.13908/) (2022)
- [To be or not to be stable, that is the question: understanding neural networks for inverse problems](https://mlsanity.com/paper/2211.13692/) (2022)
- [Recognizing Rigid Patterns of Unlabeled Point Clouds by Complete and Continuous Isometry Invariants with no False Negatives and no False Positives](https://mlsanity.com/paper/2303.15385/) (2023)
- [Implicit-explicit Integrated Representations for Multi-view Video Compression](https://mlsanity.com/paper/2311.17350/) (2023)
- [Learning smooth functions in high dimensions: from sparse polynomials to deep neural networks](https://mlsanity.com/paper/2404.03761/) (2024)
- [Physics-informed compressed sensing for PC-MRI: an inverse Navier-Stokes problem](https://mlsanity.com/paper/2207.01466/) (2022)
- [Glimpse: Generalized Locality for Scalable and Robust CT](https://mlsanity.com/paper/2401.00816/) (2024)
- [NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems](https://mlsanity.com/paper/2203.00804/) (2022)
- [Dual Accuracy-Quality-Driven Neural Network for Prediction Interval Generation](https://mlsanity.com/paper/2212.06370/) (2022)
- [Computability of Optimizers](https://mlsanity.com/paper/2301.06148/) (2023)
- [Towards Combinatorial Generalization for Catalysts: A Kohn-Sham Charge-Density Approach](https://mlsanity.com/paper/2310.18702/) (2023)
- [On the consistent reasoning paradox of intelligence and optimal trust in AI: The power of 'I don't know'](https://mlsanity.com/paper/2408.02357/) (2024)
- [On the uncertainty principle of neural networks](https://mlsanity.com/paper/2205.01493/) (2022)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [Quantum-Inspired Analysis of Neural Network Vulnerabilities: The Role of Conjugate Variables in System Attacks](https://mlsanity.com/paper/2402.10983/) (2024)
- [Bayesian inverse Navier-Stokes problems: joint flow field reconstruction and parameter learning](https://mlsanity.com/paper/2406.18464/) (2024)
- [Deep neural networks can stably solve high-dimensional, noisy, non-linear inverse problems](https://mlsanity.com/paper/2206.00934/) (2022)
- [Singular value decomposition based matrix surgery](https://mlsanity.com/paper/2302.11446/) (2023)
- [A phase transition for finding needles in nonlinear haystacks with LASSO artificial neural networks](https://mlsanity.com/paper/2201.08652/) (2022)
- [Localized adversarial artifacts for compressed sensing MRI](https://mlsanity.com/paper/2206.05289/) (2022)
- [Limitations of neural network training due to numerical instability of backpropagation](https://mlsanity.com/paper/2210.00805/) (2022)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)

## Abstract (arXiv)

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 O(|log(ε)|) layers are needed for an ε-accurate solution to the inverse problem.