Information on the Lecture: Mathematics of Deep Learning (SS 2020)

General information

• Lecturer: JProf. Dr. Philipp Harms, Room 244, Ernst-Zermelo-Straße 1, philipp.harms@stochastik.uni-freiburg.de¹
• Assistant: Jakob Stiefel
• Short videos and slides: available on ILIAS² every Tuesday night
• Discussion and further reading: Wednesdays 14:15-14:45 in our virtual meeting room. 
• Exercises: Instruction sheets available on ILIAS³. Solutions to be handed in every 2nd Wednesday on ILIAS³. Discussion of solutions every 2nd Friday at 10:15 in our virtual meeting room.
• Virtual meeting room: Zoom meeting 916 6576 1668⁴ or, as a backup option, BigBlueButton meeting vHarms⁵ (passwords available on ILIAS²). 

Instructional Development Award

• This lecture is part of an initiative led by Philipp Harms, Frank Hutter, and Thorsten Schmidt⁶ to develop a modular and interdisciplinary teaching concept in the areas of machine learning and deep learning.
• This initiative is supported by the University of Freiburg in the form an Instructional Development Award⁷. 

Overview

• Statistical learning theory: generalization and approximation error, bias-variance decomposition
• Universal approximation theorems: density of shallow neural networks in various function spaces
• Nonlinear approximation theory: dictionary learning and transfer-of-approximation results
• Hilbert's 13th problem and Kolmogorov-Arnold representation: some caveats about the choice of activation function
• Harmonic analysis: lower bounds on network approximation rates via affine systems of Banach frames
• Information theory: upper bounds on network approximation rates via binary encoders and decoders
• ReLU networks and the role of network depth: exponential as opposed to polynomial approximation rates 

Slides and Videos

All lectures: slides⁸

1. Deep learning as statistical learning slides⁹ video¹⁰
   
   1. Motivation for Deep Learning  video¹¹ 
   2. Introduction to Statistical Learning video¹² 
   3. Empirical risk minimization and related algorithms video¹³ 
   4. Error decompositions video¹⁴ 
   5. Error trade-offs video¹⁵ 
   6. Error bounds video¹⁶ 
   7. Organizational Issues video¹⁷ 
   8. Wrapup video¹⁸
2. Neural networks slides¹⁹ video²⁰ 
   1. Multilayer Perceptrons video²¹ 
   2. A Brief History of Deep Learning video²² 
   3. Deep Learning as Representation Learning video²³ 
   4. Definition of Neural Networks video²⁴ 
   5. Operations on Neural Networks video²⁵ 
   6. Universality of Neural Networks video²⁶ 
   7. Discriminatory Activation Functions video²⁷ 
   8. Wrapup video²⁸
3. Dictionary learning slides²⁹ video³⁰
   1. Introduction to Dictionary Learning video³¹ 
   2. Approximating Hölder Functions by Splines video³² 
   3. Approximating Univariate Splines by Multi-Layer Perceptrons video³³ 
   4. Approximating Products by Multi-Layer Perceptrons video³⁴ 
   5. Approximating Multivariate Splines by Multi-Layer Perceptrons video³⁵ 
   6. Approximating Hölder Functions by Multi-Layer Perceptrons video³⁶ 
   7. Wrapup video³⁷
4. Kolmogorov-Arnold representation: slides³⁸ video³⁹
   1. Hilbert’s 13th Problem video⁴⁰ 
   2. Kolmogorov–Arnold Representation  video⁴¹ 
   3. Approximate Hashing for Specific Functions video⁴² 
   4. Approximate Hashing for Generic Functions video⁴³ 
   5. Proof of the Kolmogorov–Arnold Theorem video⁴⁴ 
   6. Approximation by Networks of Bounded Size video⁴⁵ 
   7. Wrapup video⁴⁶ 
5. Harmonic analysis: slides⁴⁷ video⁴⁸
   
   1. Banach frames video⁴⁹
   2. Group representations video⁵⁰
   3. Signal representations video⁵¹
   4. Regular Coorbit Spaces video⁵²
   5. Duals of Coorbit Spaces video⁵³
   6. General Coorbit Spaces video⁵⁴
   7. Discretization video⁵⁵
   8. Wrapup video⁵⁶
6. Signal analysis: slides⁵⁷ video⁵⁸
   
   1. Coorbit Theory, Signal Analysis, and Deep Learning video⁵⁹ 
   2. Heisenberg Group video⁶⁰
   3. Modulation Spaces video⁶¹
   4. Affine Group video⁶²
   5. Wavelet Spaces video⁶³
   6. Shearlet Group video⁶⁴
   7. Shearlet Coorbit Spaces video⁶⁵
   8. Wrapup video⁶⁶
7. Sparse data representation: slides⁶⁷ video⁶⁸
   
   1. Rate-Distortion Theory video⁶⁹
   2. Hypercube Embeddings and Ball Coverings video⁷⁰
   3. Dictionaries as Encoders video⁷¹
   4. Frames as Dictionaries video⁷²
   5. Networks as Encoders video⁷³
   6. Dictionaries as Networks video⁷⁴
   7. Wrapup video⁷⁵
8. ReLU networks and the role of depth: slides⁷⁶ video⁷⁷ 
   1. Operations on ReLU Networks video⁷⁸
   2. ReLU Representation of Saw-Tooth Functions video⁷⁹
   3. Saw-Tooth Approximation of the Square Function video⁸⁰
   4. ReLU Approximation of Multiplication video⁸¹
   5. ReLU Approximation of Analytic Functions video⁸²
   6. Wrapup video⁸³

Literature

Courses on deep learning

• Frank Hutter and Joschka Boedecker (Department of Computer Science, University of Freiburg): Foundations of Deep Learning. ILIAS⁸⁴
• Philipp C. Petersen (University of Vienna): Neural Network Theory. pdf⁸⁵

Effectiveness of deep learning

• Sejnowski (2020): The unreasonable effectiveness of deep learning in artificial intelligence
• Donoho (2000): High-Dimensional Data Analysis—the Curses and Blessings of Dimensionality

Statistical learning theory

• Bousquet, Boucheron, and Lugosi (2003): Introduction to statistical learning theory.
• Vapnik (1999): An overview of statistical learning theory.

Universal approximation theorems

• Hornik (1989): Multilayer Feedforward Networks are Universal Approximators
• Cybenko (1989): Approximation by superpositions of a sigmoidal function
• Hornik (1991): Approximation capabilities of multilayer feedforward networks

Nonlinear approximation theory

• Oswald (1990): On the degree of nonlinear spline approximation in Besov-Sobolev spaces
• DeVore (1998): Nonlinear approximation

Hilbert's 13th problem and Kolmogorov-Arnold representation

• Arnold (1958): On the representation of functions of several variables
• Torbjörn Hedberg: The Kolmogorov Superposition Theorem. In Shapiro (1971): Topics in Approximation Theory
• Bar-Natan (2009): Hilberts 13th problem, in full color
• Hecht-Nielsen (1987): Kolmogorov’s mapping neural network existence theorem

Harmonic analysis

• Christensen (2016): An introduction to frames and Riesz bases
• Dahlke, De Mari, Grohs, Labatte (2015): Harmonic and Applied Analysis
• Feichtinger Gröchenig (1988): A unified approach to atomic decompositions
• Gröchenig (2001): Foundations of Time-Frequency Analysis
• Mallat (2009): A Wavelet Tour of Signal Processing
• Kutyniok and Labate (2012): Shearlets - Multiscale Analysis for Multivariate Data

Information theory

• Bölcskei, Grohs, Kutyniok, Petersen (2017): Optimal approximation with sparsely connected deep neural networks. In: SIAM Journal on Mathematics of Data Science 1.1, pp. 8–45
• Dahlke, De Mari, Grohs, Labatte (2015): Harmonic and Applied Analysis. Birkhäuser.
• Donoho (2001): Sparse Components of Images and Optimal Atomic Decompositions. In: Constructive Approximation 17, pp. 353–382
• Shannon (1959): Coding Theorems for a Discrete Source with a Fidelity Criterion. In: International Convention Record 7, pp. 325–350

ReLU networks and the role of depth

• Perekrestenko, Grohs, Elbrächter, Bölcskei (2018): The universal approximation power of finite-width deep ReLU Networks. arXiv:1806.01528
• E, Wang (2018): Exponential convergence of the deep neural approximation for analytic functions. arXiv:1807.00297
• Yarotsky (2017): Error bounds for approximations with deep ReLU networks. Neural Networks 94, pp. 103–114.