BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Talks.cam//talks.cam.ac.uk// X-WR-CALNAME:Talks.cam BEGIN:VEVENT SUMMARY:Can stable and accurate neural networks be computed? - On the barr iers of deep learning and Smale's 18th problem - Matthew Colbrook (Univers ity of Cambridge) DTSTART:20211026T080000Z DTEND:20211026T090000Z UID:TALK164635@talks.cam.ac.uk DESCRIPTION:

Deep learning (DL) has had unprecedented success and is now entering scientific computing with full force. However\, DL suffers from a universal phenomenon: instability\, despite universal approximating prop erties that often guarantee the existence of stable neural networks (NNs). We show the following paradox. There are basic well-conditioned problems in scientific computing where one can prove the existence of NNs with grea t approximation qualities\, however\, there does not exist any algorithm\, even randomised\, that can train (or compute) such a NN. Indeed\, for any positive integers K > 2 and L\, there are cases where simultaneously: (a) no randomised algorithm can compute a NN correct to K digits with probabi lity greater than 1/2\, (b) there exists a deterministic algorithm that co mputes a NN with K-1 correct digits\, but any such (even randomised) algor ithm needs arbitrarily many training data\, (c) there exists a determinist ic algorithm that computes a NN with K-2 correct digits using no more than L training samples. These results provide basic foundations for Smale's 1 8th problem and imply a potentially vast\, and crucial\, classification th eory describing conditions under which (stable) NNs with a given accuracy can be computed by an algorithm. We begin this theory by initiating a unif ied theory for compressed sensing and DL\, leading to sufficient condition s for the existence of algorithms that compute stable NNs in inverse probl ems. We introduce Fast Iterative REstarted NETworks (FIRENETs)\, which we prove and numerically verify are stable. Moreover\, we prove that only O(| \\log(\\epsilon)|) layers are needed for an \\epsilon accurate solution to the inverse problem (exponential convergence)\, and that the inner dimens ions in the layers do not exceed the dimension of the inverse problem. Thu s\, FIRENETs are computationally very efficient. The reference for this ta lk is: https://arxiv.org/abs/21 01.08286

LOCATION:Seminar Room 1\, Newton Institute END:VEVENT END:VCALENDAR