Abstract: Current deep learning methods can suffer from instability, even for inverse problems where the universal approximation theorem guarantees the existence of stable neural networks (NNs). We address this paradox by demonstrating well-conditioned optimisation problems where NNs with great approximation qualities exist; however, there does not exist any algorithm, even randomised, that can train such a NN. These results imply a classification theory describing conditions under which an algorithm can compute (stable) NNs with a given accuracy. We establish such sufficient conditions and introduce Fast Iterative REstarted NETworks (FIRENETs), which we prove and verify are stable. We then discuss approximate sharpness conditions. Sharpness conditions directly control the recovery performance of restart schemes for first-order methods without the need for assumptions such as strong convexity. However, they can be challenging to apply in the presence of noise or approximate model classes (e.g., approximate sparsity). We provide a first-order method: Weighted, Accelerated and Restarted Primal-dual (WARPd), based on primal-dual iterations and a novel restart-reweight scheme. Under a generic approximate sharpness condition, WARPd achieves stable linear convergence to the desired vector.

This talk is based on the following two papers:
[1] M.J. Colbrook, V. Antun, A.C. Hansen, “The difficulty of computing stable and accurate neural
networks: On the barriers of deep learning and Smale’s 18th problem”, Proc. Natl. Acad. USA, to
appear.
[2] M.J. Colbrook, “WARPd: A linearly convergent first-order method for inverse problems with
approximate sharpness conditions.” arXiv:2110.12437 (2021).