8th International Conference on
Computational Harmonic Analysis

September 12-16, 2022

Ingolstadt, Germany

"Which neural networks can be computed by algorithms? - Expressivity meets Turing in Deep Learning"

Thesing, Laura

Deep neural networks show great performance in a variety of applications and are now also used in security and safety-sensitive areas like self-driving cars and medical health care. However, besides all the success stories of the last decade, there is overwhelming empirical evidence suggesting that modern AI is often non-robust (unstable), may generate hallucinations, and thus can produce nonsensical output with high levels of prediction confidence. Instability and untrustworthiness are the Achilles' heel of modern AI and a paradox, with training algorithms finding unstable neural networks despite the existence of stable ones. Indeed, there is a vast collection of approximation results guaranteeing the existence of stable and accurate neural networks. Hence, the problem does not lie in their expressivity. However, recent results -- obtained by expanding methodologies initiated by Gödel and Turing -- demonstrate that stable and accurate neural networks can be proven to exist, yet they may not be trainable by an algorithm. Thus, approximation results alone cannot provide the foundations of deep learning -- we need a classification theory on which neural networks can actually be trained and computed by algorithms. We present the beginning of such a program.

« back