# Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization

arXiv: https://arxiv.org/abs/1908.09375 · HTML: https://mlsanity.com/paper/1908.09375/

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2019.

## Built on by (most cited first, 30 of 72)

- [KAN: Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2404.19756/) (2024)
- [Tabular Data: Deep Learning is Not All You Need](https://mlsanity.com/paper/2106.03253/) (2021)
- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [Deep physical neural networks enabled by a backpropagation algorithm for arbitrary physical systems](https://mlsanity.com/paper/2104.13386/) (2021)
- [On the Role of Neural Collapse in Transfer Learning](https://mlsanity.com/paper/2112.15121/) (2021)
- [Kolmogorov Arnold Informed neural network: A physics-informed deep learning framework for solving forward and inverse problems based on Kolmogorov Arnold Networks](https://mlsanity.com/paper/2406.11045/) (2024)
- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [On the influence of over-parameterization in manifold based surrogates and deep neural operators](https://mlsanity.com/paper/2203.05071/) (2022)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [Implicit regularization in Heavy-ball momentum accelerated stochastic gradient descent](https://mlsanity.com/paper/2302.00849/) (2023)
- [Theory of Deep Convolutional Neural Networks III: Approximating Radial Functions](https://mlsanity.com/paper/2107.00896/) (2021)
- [Quantum Policy Gradient Algorithm with Optimized Action Decoding](https://mlsanity.com/paper/2212.06663/) (2022)
- [Deep Learning Meets Sparse Regularization: A Signal Processing Perspective](https://mlsanity.com/paper/2301.09554/) (2023)
- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [Information Bottleneck: Exact Analysis of (Quantized) Neural Networks](https://mlsanity.com/paper/2106.12912/) (2021)
- [Order parameters and phase transitions of continual learning in deep neural networks](https://mlsanity.com/paper/2407.10315/) (2024)
- [Quantum Variational Activation Functions Empower Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2509.14026/) (2025)
- [Efficient Neural Networks for Tiny Machine Learning: A Comprehensive Review](https://mlsanity.com/paper/2311.11883/) (2023)
- [The Tensor Brain: A Unified Theory of Perception, Memory and Semantic Decoding](https://mlsanity.com/paper/2109.13392/) (2021)
- [The wall confronting large language models](https://mlsanity.com/paper/2507.19703/) (2025)
- [Cutting-edge 3D Medical Image Segmentation Methods in 2020: Are Happy Families All Alike?](https://mlsanity.com/paper/2101.00232/) (2021)
- [Measuring and modeling the motor system with machine learning](https://mlsanity.com/paper/2103.11775/) (2021)
- [Conditionally Gaussian PAC-Bayes](https://mlsanity.com/paper/2110.11886/) (2021)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)
- [Towards Understanding Theoretical Advantages of Complex-Reaction Networks](https://mlsanity.com/paper/2108.06711/) (2021)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Performance Limits of a Deep Learning-Enabled Text Semantic Communication under Interference](https://mlsanity.com/paper/2302.14702/) (2023)
- [Estimation of a regression function on a manifold by fully connected deep neural networks](https://mlsanity.com/paper/2107.09532/) (2021)
- [Homological Neural Networks: A Sparse Architecture for Multivariate Complexity](https://mlsanity.com/paper/2306.15337/) (2023)
- [Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Space](https://mlsanity.com/paper/2307.01177/) (2023)

## Abstract (arXiv)

While deep learning is successful in a number of applications, it is not yet well understood theoretically. A satisfactory theoretical characterization of deep learning however, is beginning to emerge. It covers the following questions: 1) representation power of deep networks 2) optimization of the empirical risk 3) generalization properties of gradient descent techniques --- why the expected error does not suffer, despite the absence of explicit regularization, when the networks are overparametrized? In this review we discuss recent advances in the three areas. In approximation theory both shallow and deep networks have been shown to approximate any continuous functions on a bounded domain at the expense of an exponential number of parameters (exponential in the dimensionality of the function). However, for a subset of compositional functions, deep networks of the convolutional type can have a linear dependence on dimensionality, unlike shallow networks. In optimization we discuss the loss landscape for the exponential loss function and show that stochastic gradient descent will find with high probability the global minima. To address the question of generalization for classification tasks, we use classical uniform convergence results to justify minimizing a surrogate exponential-type loss function under a unit norm constraint on the weight matrix at each layer -- since the interesting variables for classification are the weight directions rather than the weights. Our approach, which is supported by several independent new results, offers a solution to the puzzle about generalization performance of deep overparametrized ReLU networks, uncovering the origin of the underlying hidden complexity control.