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

Matthew J. Colbrook; Vegard Antun; Anders C. Hansen

Source-linked AI summary

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

Matthew J. Colbrook, Vegard Antun, Anders C. Hansen

arXiv:2101.08286v2Jan 20, 2021cs.LGcs.CVcs.NEmath.NA

TL;DR

The paper asks why unstable deep-learning methods arise even when stable and accurate neural networks exist. It proves accuracy-dependent barriers to computing such networks, then constructs FIRENETs that are stable and exponentially convergent under suitable inverse-problem conditions. The results support a classification perspective on when stable neural networks can be computed, while leaving the optimal stability–accuracy trade-off open.

Problem
Current deep-learning methods can be unstable even when universal approximation guarantees the existence of stable neural networks, raising the question of when those networks can actually be computed.
Method
The paper proves computational impossibility and accuracy-dependent training theorems, then establishes sufficient conditions and constructs FIRENETs for stable inverse-problem solutions.
Results
The paper proves that suitable networks may exist without being computable at a requested accuracy, while FIRENETs withstand adversarial attacks and converge exponentially with depth.
Takeaways & Limitations
Stable neural networks require conditions beyond existence proofs, and practical performance involves a stability–accuracy trade-off.
Takeaways & Limitations
Unrolling iterative methods does not generally produce an accurate network without additional assumptions, and the optimal stability–accuracy trade-off remains open.

Abstract

from arXiv · show

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

Foundations of AI for inverse problems.

The paper frames stable and accurate neural networks as a central scientific-computing challenge because stability and accuracy can conflict. It argues that useful networks must achieve both properties, unlike trivially stable but inaccurate networks.

Scientific computing relies on both stability and accuracy, but methods may face barriers that prevent achieving them simultaneously.The paper identifies a possible trade-off in which accuracy may need to be sacrificed to secure stability.

Main results.

The paper establishes computational barriers showing that accurate neural networks may exist for well-conditioned inverse problems without being computable from training data at the same accuracy. It also gives accuracy-dependent impossibility results and introduces FIRENETs as stable, exponentially convergent networks under suitable conditions.

Main results.: Well-conditioned inverse problems can admit suitable neural networks even when no training algorithm can compute accurate approximations from training data.The relevant condition numbers are bounded by 1, so the barrier is not attributed to poor conditioning.
Main results.: For any K > 2 and L, K-digit computation can be impossible, K−1 digits can require arbitrarily many samples, and K−2 digits can be achieved with L samples.These guarantees concern deterministic and randomized algorithms under the theorem’s stated accuracy convention.
Main results.: FIRENETs provide algorithms for computing stable neural networks under conditions typical of inverse problems such as MRI.They are presented as a constructive response to the impossibility results under additional assumptions.
Main results.: FIRENETs converge exponentially with the number of hidden layers and withstand adversarial perturbations, while also stabilizing unstable neural networks.The paper presents adversarial robustness and stabilization of existing networks as key properties of the construction.
Main results.: The results identify a stability–accuracy trade-off that limits how well a stable neural network can perform.The paper presents this trade-off as a broader constraint requiring further techniques and problem-specific assumptions.

Numerical example.

The numerical example tests whether FIRENETs and LISTA can compute existing neural-network solutions for (P3) to arbitrary accuracy. Both networks reproduce the accuracy barrier predicted by Theorem 2.

K = 1, 3, 6 are used to illustrate the impossibility of computing FIRENET and LISTA approximations to arbitrary accuracy.The experiment uses input classes ΩK and sets N = 20, m = N − 1, with 6-sparse minimisers.
10^-K digits cannot be reached, whereas 10^(-K+1) digits can be achieved by both FIRENETs and LISTA.This matches Theorem 2 for the input class ΩK.
R = 8000 training samples are used to train both network types to high accuracy on the specified training data.The network depth n is selected as reported in Table 1.

The subtlety and difficulty of removing instabilities, and the need for additional assumptions.

The paper argues that stable and accurate reconstruction requires assumptions linking the sampling operator to the signal model. Under a weighted robust null space property, FIRENETs provide stable, accurate recovery with logarithmic depth.

The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: Kernel awareness is necessary because measurements of signals differing near the null space can be arbitrarily close while their reconstructions remain far apart.For m < N, a small measurement perturbation can make a reconstruction map return the wrong image.
The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: Adversarial training may avoid a reconstruction instability condition but can yield poor performance.The paper frames stability and accuracy as competing requirements for the general inverse problem.
The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: The construction uses sparsity in levels, weighted wavelet representations, and probabilistic Fourier or Walsh sampling to obtain kernel-aware measurements.The framework targets approximately sparse wavelet coefficients and supports stable recovery of such vectors.
The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: The weighted robust null space property in levels prevents large signal differences from producing sufficiently small measurement differences.This property supplies the kernel-aware condition needed for stable and accurate recovery of sparse-in-levels vectors.
The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: FIRENETs recover signals with error controlled by measurement error and model mismatch, while converging exponentially with network depth.The measurement-error coefficient acts as an asymptotic local Lipschitz constant, and σs,M(x)l1w measures distance from the model class.
The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: Unrolling iterative methods does not generally produce an accurate network without assumptions such as the robust null space property.The paper presents these assumptions as necessary for the algorithmic guarantees discussed here.
The subtlety and difficulty of removing instabilities, and the need for additional assumptions.: FIRENETs are reported as stable and accurate for wavelet-sparse images, while current reconstruction methods can suffer instability or loss of small details.The paper also reports generalisation properties for unseen images under the stated conditions.

Adversarial perturbations for AUTOMAP and FIRENETs.

The adversarial-perturbation experiment contrasts unstable AUTOMAP reconstructions with stable FIRENET reconstructions. FIRENET stability persists across tested images and perturbation searches.

AUTOMAP reconstructions severely deform under a sequence of increasingly large adversarial perturbations.The test uses MRI reconstruction with 60% subsampling.
Figure 3 uses a 25-layer FIRENET with p = 5 and n = 5, taking AUTOMAP’s output as the initial guess.The concatenated mapping is y 7→Φ(y, Ψ(y)).
FIRENET reconstructions remain stable despite adversarial perturbation searches designed for the new networks.The perturbations used for FIRENET are distinct from AUTOMAP’s adversarial perturbations.
The stability test is applied across a range of images to examine generalisation under the paper’s structural conditions.The authors connect this generalisation to conditions such as Definition 2.

Stabilising unstable NNs with FIRENETs.

FIRENETs can stabilize an unstable AUTOMAP reconstruction when used after AUTOMAP. The concatenated network remains stable under adversarial attacks.

FIRENETs fix AUTOMAP’s adversarial output and stabilize the reconstruction when AUTOMAP supplies the initial guess.The construction uses FIRENETs as approximations of unrolled and restarted iterative methods.
The concatenated AUTOMAP–FIRENET network remains stable to adversarial attacks.

The stability vs. accuracy trade-off and false negatives.

Stable neural networks can sacrifice reconstruction detail, while FIRENETs are presented as a way to balance stability and accuracy in inverse problems. The optimal trade-off remains unresolved and application-dependent.

Experimental setting: 15% sampling with N = 10242 is used to reconstruct ellipse images from subsampled Fourier measurements, with noisy data generated as y = Ax + ce.The noise is generated during training, and the measurement operator is a subsampled discrete Fourier transform.
False negatives: Stable U-nets can produce false negatives by washing out small image details, despite resisting worst-case measurement perturbations.The figure compares reconstruction networks trained with noise-free and noisy measurements, including a FIRENET and two U-nets.
FIRENETs: FIRENETs offer a blend of stability and accuracy, with guaranteed performance and stability under specific sampling conditions for wavelet-sparse images.The paper contrasts this with U-nets that may be stable but fail to reconstruct details outside the training set.
Open problem: An intrinsic stability–accuracy trade-off exists in inverse-problem machine learning, and tracing its optimum remains largely open.The paper expects this trade-off to matter increasingly in real-world implementations of machine learning for inverse problems.

1. STATEMENT OF THEOREMS AND RESULTS

The theorems separate the existence of accurate neural networks from their algorithmic computability, then give sufficient conditions for constructing stable networks for inverse problems. FIRENETs provide exponentially convergent, uniform, stable recovery, requiring only logarithmically many layers for a target precision.

Problem formulation: The inverse problem recovers x from noisy measurements y = Ax + e, where A is typically undersampled.The framework includes subsampled discrete Fourier transforms used in MRI.
Existence versus computability: Universal approximation guarantees neural networks solving the optimisation problems, but does not imply that training algorithms can compute them.Theorem 1 maps admissible training data to networks whose outputs lie among the optimisation problem’s minimisers.
Constructive stable networks: Theorem 3 constructs networks under a weighted robust null space property, with exponentially convergent, uniform, and stable recovery guarantees.The construction accepts approximations to A and specified algorithmic parameters, and produces a network with an explicitly controlled architecture.
Constructive stable networks: O(|log(δ)|) layers suffice when the iterative error term is reduced to the target precision δ.This logarithmic layer dependence follows from exponential convergence and is applied to compressive imaging examples.
Image-recovery examples: For Fourier and Walsh sampling with Haar wavelets, the recovery theory gives sampling requirements by sparsity level, with Walsh bounds omitting cross-level sparsity terms.The stated Fourier estimates match the best-known oracle estimator up to logarithmic factors.

2. FURTHER EXAMPLES OF FIRENET

FIRENETs generalise across image types and reconstruct images from highly undersampled noisy measurements without parameter tuning. Their objective and reconstruction errors converge exponentially before reaching a noise- and model-limited plateau.

FIRENETs show stability across different image types and avoid retraining for different image classes.The passage also states that they are rigorously proven stable and accurate.
Figure 3 compares the true image with noisy Fourier and Walsh reconstructions, including full-image and zoomed views.Both reconstructions use n = p = 5 and the sampling patterns from Figure 1.
15% sampling with 2% Gaussian noise is used to reconstruct images from Fourier and Walsh measurements with Haar wavelets.The experiment deliberately avoids parameter tuning; weights come from a standard phantom image rather than the test image.
The objective values and reconstructed images converge exponentially with inner iterations until the error reaches the order of ∥c − c∗∥l2.The dashed line in Figure 4 marks the relative coefficient error bound.
The plateau reflects inexact noisy measurements and model mismatch, while the objective gap continues decreasing slightly beyond it.The robust null space property controls the local l2 difference down to the reconstruction error.

3. PROOF OF THEOREM 2 AND TOOLS FROM THE SCI HIERARCHY

The proof of Theorem 2 formalises computational problems and general algorithms broadly enough to cover deterministic and randomised computation. It then uses impossibility propositions to show that well-conditioned inverse problems can still resist accurate NN computation under specified information constraints.

Algorithmic framework: The proof introduces a general computational-problem framework comprising a domain, evaluation set, metric-space output, and problem function.Multivalued solution sets are handled through distance to the solution set.
Algorithmic framework: A general algorithm reads only a finite, potentially adaptive set of evaluations, and its output and subsequent evaluations depend only on the information read.The framework is intended to capture broad notions of deterministic computation.
Algorithmic framework: Randomised general algorithms add random-number generation to computation, while probabilistic Turing machines halt with probability one and output a single result.This model is used to cover randomised training procedures such as stochastic-gradient methods.
Impossibility tools: For any sequential general algorithm and finite sample budget M, some input forces either error greater than κ/2 or more than M evaluations.The randomised analogue gives an input whose failure probability exceeds any p < 1/2.
Theorem 2: Theorem 2 constructs a well-conditioned class with condition numbers bounded by 1 where accurate NN computation remains impossible under the stated accuracy and sample regimes.The proof derives the K-digit contradiction from Proposition 3.13 and the K−1-digit sample lower bound from Proposition 3.14.
Numerical example: The numerical example uses LISTA and FIRENETs on three classes indexed by K, and neither network reaches K-digit accuracy although both achieve K−1 digits.The experiment is designed to agree with Theorem 2.

4. PROOF OF THEOREM 3

Theorem 3 constructs FIRENETs by unrolling and approximating Chambolle–Pock primal-dual iterations with neural networks. Weighted robust null space properties then connect objective bounds to reconstruction accuracy and stability, with exponential error decay in network depth.

Stability and accuracy: Weighted robust null space properties convert objective-function bounds into l2-distance bounds for the reconstructed vector.The proof develops both weighted l1 and l2 distance consequences of the robust null space property.
Construction: The network approximates proximal maps using affine operations, modulus squaring, comparisons, arithmetic, and bounded square-root approximations.The square-root approximation can be implemented with standard nonlinear activations on bounded inputs.
Stability and accuracy: The unrolled networks achieve an exponentially decaying objective error, with depth repeated across the unrolled iterations.The construction bounds the objective gap by a term of the form ϵ_n ≤ 2υδ.
Construction: The construction rewrites the inverse problem as a real saddle-point problem and approximates Chambolle–Pock primal-dual iterations with a neural network.The resulting iterations are treated as proximal-point updates that are non-expansive in a suitable norm.
Depth requirement: The proof selects the iteration count so the exponential term reaches the target tolerance, with the ceiling function ensuring an integer depth parameter.This yields the stated logarithmic layer-growth relationship.
Stability and accuracy: The resulting reconstruction error is bounded by approximation, measurement, and operator-perturbation terms.The displayed bound combines weighted sparsity, measurement residual, operator error, and a remaining approximation term.

5. PROOF OF THEOREM 4

Theorem 4 applies the FIRENET construction to Fourier- and Walsh-sampled Haar-wavelet recovery. Local coherence estimates provide sampling conditions under which weighted robust null space properties hold, yielding uniform recovery guarantees for the wavelet coefficients.

Sampling structure: The proof represents Fourier and Walsh measurements together with Haar wavelets through multilevel frequency bands and orthonormal bases.The discrete wavelet transform is orthonormal, with inverse Ψ−1 = Ψ∗.
Coherence estimates: Local coherence is bounded separately for Fourier–Haar and Walsh–Haar matrices using their block structure across frequency and wavelet levels.The Fourier case yields a decay estimate involving 2^-k and 2^-|k−j|, while the Walsh case is controlled by level relationships.
Sampling guarantees: The multilevel sampling proposition converts coherence bounds into a weighted robust null space property with probability at least 1 − ϵP.The resulting constants include ρ = 1/2 and a γ determined by the sampling bound.
Recovery: Theorem 3 then gives uniform recovery of Haar-wavelet coefficients from the resulting subsampled measurements.The conclusion applies to x = Ψc in C^N.
Recovery: The final network composes the FIRENET with an approximation of Ψ∗ to recover approximations of the coefficient vector c.The construction uses the isometry of Ψ to control the input norm and approximation errors.