Limitations of Deep Learning for Inverse Problems on Digital Hardware

Abstract

Deep neural networks have seen tremendous success over the last years. Since the training is performed on digital hardware, in this paper, we analyze what actually can be computed on current hardware platforms modeled as Turing machines, which would lead to inherent restrictions of deep learning. For this, we focus on the class of inverse problems, which, in particular, encompasses any task to reconstruct data from measurements. We prove that finite-dimensional inverse problems are not Banach-Mazur computable for small relaxation parameters. Even more, our results introduce a lower bound on the accuracy that can be obtained algorithmically.

arXiv commentTo be published in IEEE Transactions on Information Theory

References in corpus (19)

• Deep Convolutional Neural Network for Inverse Problems in Imaging
• Image reconstruction by domain transform manifold learning
• NESTA: A Fast and Accurate First-order Method for Sparse Recovery
• On instabilities of deep learning in image reconstruction - Does AI come at a cost?
• Deep Learning Microscopy
• Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
• Solving ill-posed inverse problems using iterative deep neural networks
• A Deep Learning Approach to Structured Signal Recovery
• Linear convergence of iterative soft-thresholding
• The Modern Mathematics of Deep Learning
• Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem
• Learning The Invisible: A Hybrid Deep Learning-Shearlet Framework for Limited Angle Computed Tomography
• Computability and analysis: the legacy of Alan Turing
• Memory effects can make the transmission capability of a communication channel uncomputable
• Computing Spectra -- On the Solvability Complexity Index Hierarchy and Towers of Algorithms
• The troublesome kernel -- On hallucinations, no free lunches and the accuracy-stability trade-off in inverse problems
• Computability and Analysis, a Historical Approach
• Inverse Problems Are Solvable on Real Number Signal Processing Hardware
• Turing meets Moore-Penrose: Computing the Pseudoinverse on Turing Machines

Cited by in corpus (2)

• Optimizing a DIscrete Loss (ODIL) to solve forward and inverse problems for partial differential equations using machine learning tools
• NESTANets: Stable, accurate and efficient neural networks for analysis-sparse inverse problems