# Lecture - Theories of Deep Learning MT25, IV, Data classes for which DNNs can overcome the curse of dimensionality

> Source: https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/lectures/dimensionality/ · Updated: 2025-11-05 · Tags: uni, lecture

- [Course - Theories of Deep Learning MT25](https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/)

Visualise the figure in Hein (2020) describing the "hidden manifold model".::

![Screenshot 2025-10-19 at 21.56.47.png](https://ollybritton.com/assets/attachments/img/Screenshot 2025-10-19 at 21.56.47.png)

@Define the hidden manifold model as in Hein (2020) for generating datasets.::

$$
X = f(CF / \sqrt d) \in \mathbb R^{p,n}
$$
where

- $F \in \mathbb R^{d, n}$ are the $d$ features used to represent the data
- $C \in \mathbb R^{p, d}$ combines the $d < n < p$ features
- $f$ is a nonlinear function

How does Pascanu (2014) make an argument for the expressivity of ReLU DNNs based on hyperplane arrangements?::

Since ReLU is piecewise linear, the output of a ReLU DNN is a piecewise linear function. They show that the number of possible regions of the input where the function can take on a different linear function is at least
$$
\prod^L_{\ell = 0} n_\ell^{\text{min}\{n_0, n_\ell / 2\}}
$$
where the input is $\mathbb R^{n_0}$ and the hidden layers are of width $n_1, \ldots, n_L$.

![Screenshot 2025-10-19 at 22.12.14.png](https://ollybritton.com/assets/attachments/img/Screenshot 2025-10-19 at 22.12.14.png)

How does Raghu (2016) make an argument for the expressivity of DNNs based on trajectory lengths?::

![Screenshot 2025-10-19 at 22.13.12.png](https://ollybritton.com/assets/attachments/img/Screenshot 2025-10-19 at 22.13.12.png)

They show that a circle passed through a random DNN with an increasing number of layers can draw more and more complicated shapes, formalised as a growing arc length in expectation.

### Other notes
- Often nets are unnecessarily wide (in terms of expressivity) because this makes them feasible to train

### Papers mentioned
- [Paper - Error bounds for approximations with deep ReLU networks, Yarotsky (2016)](https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/reading/paper-error-bounds-for-approximations-with-deep-relu-networks-yarotsky-2016/)
- [Paper - When and when can deep networks avoid the curse of dimensionality, Poggio (2016)](https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/reading/paper-when-and-when-can-deep-networks-avoid-the-curse-of-dimensionality-poggio-2016/) [Why and When Can Deep – but Not Shallow – Networks Avoid the Curse of Dimensionality: a Review](https://arxiv.org/pdf/1611.00740)
- [Intrinsic Dimensionality Estimation of Submanifolds in $\mathbb R^d$](https://icml.cc/Conferences/2005/proceedings/papers/037_Intrinsic_HeinAudibert.pdf)
- [Modeling the Influence of Data Structure on Learning in Neural Networks: The Hidden Manifold Model](https://cea.hal.science/cea-02529246/document)
- [Deep Neural Network Approximation Theory](https://www.mins.ee.ethz.ch/pubs/files/deep-it-2019.pdf)
- [On the number of response regions of deep feedforward networks with piecewise linear activations](https://arxiv.org/pdf/1312.6098)
- [On the Expressive Power of Deep Neural Networks](https://arxiv.org/abs/1606.05336)
- [Trajectory growth lower bounds for random sparse deep ReLU networks](https://arxiv.org/abs/1911.10651)
- [Survey of Expressivity in Deep Neural Networks](https://arxiv.org/pdf/1611.08083)
- [Paper - Attention Is All You Need (2017)](https://ollybritton.com/notes/uni/part-c/mt25/theories-of-deep-learning/reading/paper-attention-is-all-you-need-2017/)
- [Language Models are Few-Shot Learners](https://arxiv.org/abs/2005.14165)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://arxiv.org/abs/2010.11929)

### Other resources
- [Telgarsky’s “Deep Learning Theory” course](http://mjt.cs.illinois.edu/courses/dlt-f20/)
- [Matthew Hirn’s “Mathematics of Deep Learning” course: lectures 20-24](https://matthewhirn.com/teaching/spring-2020-cmse-890-002/)

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt