mlsanityData to 7 Oct 2026

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

arXiv 2101.08286 ↗First posted 20 Jan 2021cs.LG cs.CV cs.NAcited by 53

Not on the map. Why?

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.

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

Builds on

40 of 176 references.

References · 40

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2013Intriguing properties of neural networkscited by 5,114
  3. 2014Fully Convolutional Networks for Semantic Segmentationcited by 4,845
  4. 2013Rich feature hierarchies for accurate object detection and semantic segmentationcited by 2,160
  5. 2015DeepFool: a simple and accurate method to fool deep neural networkscited by 1,315
  6. 2016Universal adversarial perturbationscited by 774
  7. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  8. 2018Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Surveycited by 459
  9. 2016Deep Convolutional Neural Network for Inverse Problems in Imagingcited by 431
  10. 2019Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processingcited by 411
  11. 2017Learning a Variational Network for Reconstruction of Accelerated MRI Datacited by 340
  12. 2020Deep Learning Techniques for Inverse Problems in Imagingcited by 290
28 more
  1. 2018Audio Adversarial Examples: Targeted Attacks on Speech-to-Textcited by 268
  2. 2017Image reconstruction by domain transform manifold learningcited by 231
  3. 2019On instabilities of deep learning in image reconstruction - Does AI come at a cost?cited by 211
  4. 2017Optimal Approximation with Sparsely Connected Deep Neural Networkscited by 90
  5. 2018Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholdscited by 83
  6. 2017A Review of Convolutional Neural Networks for Inverse Problems in Imagingcited by 81
  7. 2020Rational neural networkscited by 75
  8. 2017A Deep Cascade of Convolutional Neural Networks for MR Image Reconstructioncited by 74
  9. 2020Advancing machine learning for MR image reconstruction with an open competition: Overview of the 2019 fastMRI challengecited by 59
  10. 2020Solving Inverse Problems With Deep Neural Networks -- Robustness Included?cited by 58
  11. 2020The gap between theory and practice in function approximation with deep neural networkscited by 53
  12. 2016Convolutional Neural Networks Analyzed via Convolutional Sparse Codingcited by 51
  13. 2019Nonlinear Approximation and (Deep) ReLU Networkscited by 45
  14. 2018Deep Unfolded Robust PCA with Application to Clutter Suppression in Ultrasoundcited by 43
  15. 2015A formal proof of the Kepler conjecturecited by 42
  16. 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 42
  17. 2017Neural networks and rational functionscited by 40
  18. 2020On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamicscited by 39
  19. 2018Learning The Invisible: A Hybrid Deep Learning-Shearlet Framework for Limited Angle Computed Tomographycited by 29
  20. 2020Improving Robustness of Deep-Learning-Based Image Reconstructioncited by 23
  21. 2020Ada-LISTA: Learned Solvers Adaptive to Varying Modelscited by 22
  22. 2018On Multi-Layer Basis Pursuit, Efficient Algorithms and Convolutional Neural Networkscited by 20
  23. 2020The Numerics of Phase Retrievalcited by 20
  24. 2020Results of the 2020 fastMRI Challenge for Machine Learning MR Image Reconstructioncited by 14
  25. 2020On Adversarial Examples and Stealth Attacks in Artificial Intelligence Systemscited by 13
  26. 2020Learned SPARCOM: Unfolded Deep Super-Resolution Microscopycited by 11
  27. 2020Total Deep Variation: A Stable Regularizer for Inverse Problemscited by 9
  28. 2015Computational Complexity versus Statistical Performance on Sparse Recovery Problemscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 16; 2023: 13; 2024: 11; 2025: 5; 2026: 3.

53 papers.

Sort:

By area:

  1. 2021Convergence Rates for Learning Linear Operators from Noisy Datacited by 55
  2. 2022The Free Energy Principle for Perception and Action: A Deep Learning Perspectivecited by 24
  3. 2022Theoretical Perspectives on Deep Learning Methods in Inverse Problemscited by 22
  4. 2023Limits for Learning with Language Modelscited by 17
  5. 2021The mathematics of adversarial attacks in AI -- Why deep learning is unstable despite the existence of stable neural networkscited by 16
  6. 2021The Feasibility and Inevitability of Stealth Attackscited by 12
  7. 2022Limitations of Deep Learning for Inverse Problems on Digital Hardwarecited by 9
  8. 2022Physical Activation Functions (PAFs): An Approach for More Efficient Induction of Physics into Physics-Informed Neural Networks (PINNs)cited by 9
  9. 2022On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samplescited by 8
  10. 2022To be or not to be stable, that is the question: understanding neural networks for inverse problemscited by 8
  11. 2023Implicit-explicit Integrated Representations for Multi-view Video Compressioncited by 8
  12. 2023Recognizing Rigid Patterns of Unlabeled Point Clouds by Complete and Continuous Isometry Invariants with no False Negatives and no False Positivescited by 7
38 more
  1. 2024Learning smooth functions in high dimensions: from sparse polynomials to deep neural networkscited by 7
  2. 2022Physics-informed compressed sensing for PC-MRI: an inverse Navier-Stokes problemcited by 6
  3. 2024Glimpse: Generalized Locality for Scalable and Robust CTcited by 6
  4. 2022NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problemscited by 5
  5. 2022Dual Accuracy-Quality-Driven Neural Network for Prediction Interval Generationcited by 5
  6. 2023Computability of Optimizerscited by 5
  7. 2023Towards Combinatorial Generalization for Catalysts: A Kohn-Sham Charge-Density Approachcited by 5
  8. 2024On the consistent reasoning paradox of intelligence and optimal trust in AI: The power of 'I don't know'cited by 5
  9. 2022On the uncertainty principle of neural networkscited by 4
  10. 2023Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networkscited by 4
  11. 2024Quantum-Inspired Analysis of Neural Network Vulnerabilities: The Role of Conjugate Variables in System Attackscited by 4
  12. 2024Bayesian inverse Navier-Stokes problems: joint flow field reconstruction and parameter learningcited by 4
  13. 2022Deep neural networks can stably solve high-dimensional, noisy, non-linear inverse problemscited by 3
  14. 2023Singular value decomposition based matrix surgerycited by 3
  15. 2022A phase transition for finding needles in nonlinear haystacks with LASSO artificial neural networkscited by 2
  16. 2022Localized adversarial artifacts for compressed sensing MRIcited by 2
  17. 2022Limitations of neural network training due to numerical instability of backpropagationcited by 2
  18. 2023Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methodscited by 2
  19. 2023Delay-SDE-net: A deep learning approach for time series modelling with memory and uncertainty estimatescited by 2
  20. 2023Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbationscited by 2
  21. 2023When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximationcited by 2
  22. 2024Do stable neural networks exist for classification problems? -- A new view on stability in AIcited by 2
  23. 2024Deceptive Diffusion: Generating Synthetic Adversarial Examplescited by 2
  24. 2025How many measurements are enough? Bayesian recovery in inverse problems with general distributionscited by 2
  25. 2026Is Task-Specific Training Necessary for Anomaly Detection?cited by 2
  26. 2021WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditionscited by 1
  27. 2021A Simplicity Bubble Problem in Formal-Theoretic Learning Systemscited by 1
  28. 2022Beyond NaN: Resiliency of Optimization Layers in The Face of Infeasibilitycited by 1
  29. 2023Training Neural Networks Using Reproducing Kernel Space Interpolation and Model Reductioncited by 1
  30. 2024Mathematical Algorithm Design for Deep Learning under Societal and Judicial Constraints: The Algorithmic Transparency Requirementcited by 1
  31. 2024Weakly Supervised Learners for Correction of AI Errors with Provable Performance Guaranteescited by 1
  32. 2024Geometrical structures of digital fluctuations in parameter space of neural networks trained with adaptive momentum optimizationcited by 1
  33. 2025Deep greedy unfolding: Sorting out argsorting in greedy sparse recovery algorithmscited by 1
  34. 2022Achieve Optimal Adversarial Accuracy for Adversarial Deep Learning using Stackelberg Gamecited by 0
  35. 2023A Comparative Study of Deep Learning and Iterative Algorithms for Joint Channel Estimation and Signal Detection in OFDM Systemscited by 0
  36. 2024Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantizationcited by 0
  37. 2025Explaining Neural Networks with Reasonscited by 0
  38. 2025Approach to Finding a Robust Deep Learning Modelcited by 0

50 most cited of 53 All 53 (JSON)