Understanding the Essence of How Deep Learning Learns with Massive Over-parameterization

Introduction

Author's Motivation

Keywords for this article include:

• Universal Approximation Theorem
• Double Descent
• Over-parameterization
• Benefits of Depth

There are already many excellent Japanese resources explaining these topics:

https://qiita.com/mochimochidog/items/ca04bf3df7071041561a

https://ibis.t.u-tokyo.ac.jp/suzuki/lecture/2020/intensive2/Kyusyu_2020_Deep.pdf

https://ibisml.org/ibis2019/files/2019/11/slide_imaizumi.pdf

My goal is to write an article that lets you "get a feel for how to successfully train deep learning models just by reading this." Since the themes surrounding deep learning are vast, starting to read academic papers is still a daunting task, even with tools like NotebookLM, and you often need to read various individual articles to cover each topic. While tools like DeepResearch might provide more information, I believe that as of 2025, they don't yet reach the level of "getting a feel for successful deep learning training" when it comes to curated explanations with varying levels of detail and effective use of figures.^[1] Although I use the expression "get a feel for it," I aim for a level of understanding that goes one step beyond purely descriptive explanations.

Also, the generative AI boom has increased interest in AI. I want to share the exciting aspects of deep learning, which is the core of current generative AI, with those newcomers.

Most importantly, as output is the most effective way to learn, I am writing this article for my own study as well.

I have tried my best to write this while reading academic papers to ensure accuracy, but as this content was studied independently without a formal review process, there is a strong possibility that it contains errors. If you find any, I would appreciate it if you could let me know in the comments or via X.

The Mystery of Massive Parameters

As you are likely familiar with through generative AI, models like Transformer and Diffusion are realized by deep neural networks (deep learning). While the number of parameters used in state-of-the-art LLMs as of 2025 is often undisclosed, the open-source model Llama 3.1 has 405B (B: Billion, so 405B is 405 billion) parameters. Other undisclosed models like GPT-4 and Gemini 2.5 are said to have over a trillion parameters.

On the other hand, those who have learned classical statistical models should be familiar with the following fact:

As the number of parameters increases, overfitting becomes more likely.

In fact, in linear regression models, when the number of feature dimensions exceeds the number of data points, any set of labels can be perfectly reproduced. This is clear from a linear algebra perspective: if we explain $n$ data points using a $d$-dimensional vector, as long as $d \geq n$, the rank is $n$, and a coefficient vector that exactly matches any given output vector can be found. Furthermore, in classification, if the VC dimension is at least the number of data points $n$, any labels can be perfectly separated.^[2] This holds true regardless of the data distribution, even for randomly generated data.

Traditionally, statistics used the Akaike Information Criterion (AIC) for model selection, and in decision trees, we adjusted depth, or in regression, we adjusted regularization parameters to improve generalization performance while balancing the number of parameters. However, in recent neural networks, models with parameter counts far exceeding the number of data points have emerged^[3], and they boast remarkable generalization performance.

So, how do today's deep learning models, which boast astonishing performance, find appropriate parameters while avoiding overfitting? Does a model parameter set capable of performing complex tasks like language and image generation even exist? To help you understand these questions, I will explain what I have studied in this article.

Of course, there is no perfect answer to this.
Nevertheless, I will introduce what I have found through my own research as redtea.

Structure of This Article

This article is organized as follows:

1. Does a solution even exist? (Universal Approximation Theorem)
   • Learn that neural networks have strong expressive power and that parameters exist to approximate almost any function.
2. Can the existing solution be found? (Over-parameterization)
   • Now that we know appropriate parameters exist, can we discover them? We will understand that it can be discovered through over-parameterization.
3. Will the found solution generalize? (Double Descent)
   • Finding a point where training error is nearly 0 through over-parameterization is good, but a question arises: won't the "bias-variance tradeoff" occur, where generalization performance declines as the number of parameters increases? We will confirm "Double Descent," where the bias-variance tradeoff does not occur, and understand why generalization performance improves.
4. Why do deeper layers make it easier to find generalizing solutions? (Approximation Error Rate)
   • If we can improve generalization performance by excessively increasing the number of parameters, shallow neural networks might seem sufficient. We will consider why deep neural networks are necessary.

Expressive Power of Deep Learning

What level of expressive power do neural networks have, given that they can represent such complex functions as those seen in today's generative AI, going beyond image recognition and machine translation?

Universal Approximation Theorem

The Universal Approximation Theorem claims the following:

A neural network with two or more layers can approximate any continuous function with arbitrary precision.

However, the Universal Approximation Theorem is merely an existence theorem. It only states that good parameters exist for a sufficiently large neural network, but it says nothing about how to find those parameters. That is, it must be considered separately from learnability and generalization issues. In this chapter, we will not touch upon the part about finding parameters and will focus on existence.

For more detailed explanations, the following article is helpful.

https://qiita.com/mochimochidog/items/ca04bf3df7071041561a

It takes time to fully understand, but let's grasp the image that it seems to exist. I have created some animations showing how simple functions can approximate another simple function by superimposing them. As an intuitive understanding, if you keep increasing the width of a single layer of a neural network, the number of functions that can be superimposed increases. Then, if you tune the weights nicely, you can draw any shape.^[4]

Approximating a quadratic function with a step function.

Approximating a quadratic function with a ReLU function

Approximating a cubic function with a ReLU function

Talking about the mathematical image, if you use the difference of ReLU functions, you can create something like a step function.

$$\text{ReLU}(x) = \max(0, x) \\ \text{"step-like"}(x) = h \times (\text{ReLU}(x-a) - \text{ReLU}(x-b))$$

An image of creating a step-like function from ReLU. If you can make such step-like functions, it seems you could create any function by combining them.

Of course, not only continuous functions but also discontinuous functions can be approximated. There are many cases in the real world where data changes discontinuously.

Can Good Parameters Be Found?

In the previous chapter, we learned that good parameters exist, but can they be found in reality?

The Difficulty of Finding Parameters

In simple machine learning models such as logistic regression, the loss function is a convex function (figure below), and you can always find the optimal solution by descending the gradient.

If the loss function is a convex function, you can always find the optimal solution by moving parameters in the direction where the loss decreases. Cited from Convex function (Wikipedia).

On the other hand, the loss function of deep learning has a very complex structure. Since the number of parameters easily exceeds hundreds of millions, it is difficult to visualize the loss function or grasp the whole picture, but through techniques like dimension reduction, some visualizations have been made, like the one below.

Visualization of a deep learning loss function using dimension reduction (the $z$-axis represents loss, and the $x,y$-axes represent the parameter space). The left figure shows a neural network without skip connections, and the right side includes them. It is suggested that model architecture design significantly changes the ease of finding parameters. Cited from Visualizing the Loss Landscape of Neural Nets Figure 1.

As you can see, the shape of a neural network's loss function is typically very complex. Depending on luck with initial values, one must overcome several mountains due to stochastic fluctuations and find a deep valley.^[5] It is distinctly different from loss functions like logistic regression.

However, in reality, this Stochastic Gradient Descent finds "valleys" that are good enough for practical use with realistic computational resources and time, even for non-convex loss functions. In this chapter, I will introduce techniques to make it easier to find "valleys" that reduce training loss.

Flatness of the Loss Landscape

In this section, we focus on the geometric properties of the "loss landscape" of the parameter space to be explored. In various academic papers^[6], it has been researched that the flatter the convergence point of the loss function, the higher the generalization performance.^[7]

For an intuitive understanding, please see the visualization graph of the loss function below. In the figure on the left, where the loss function is low, it is flat, whereas on the right, it is relatively sharp.

Visualization graph of a loss function obtained from a simple experiment. The lower the $z$-axis, the lower the loss and the better the situation. The left side represents a section of the parameter space where convergence occurred when searching with a small mini-batch size, and the right side represents the case with a large mini-batch size.

Intuitively, if parameters are determined in a flat region of the loss function, the loss does not fluctuate significantly even if the parameters change. This is based on the idea that solutions in such regions are likely to be resilient to fluctuations in data, which are test data. Also, the relationship between mini-batch size and the region where parameters converge can be summarized as follows:

• When the mini-batch size is large: Because it calculates a stable gradient with little noise, it tends to fall straight into a sharp "valley" (Sharp Minima) of the loss function. This sharp "valley" is a solution specialized too much to the training data (overfitted), and there is a risk that the loss will deteriorate rapidly if the data shifts even slightly (becoming test data).

• When the mini-batch size is small: Because the gradient contains noise, this noise helps in the search, making it easier to find a wider "flat valley" (Flat Minima) without being trapped in a sharp valley bottom. A flat region is considered to have high generalization performance and to be robust against unknown data because the loss is stable even if the parameters change slightly.

As of 2025, the relationship between loss landscape flatness and generalization performance is not thought to be a simple causal relationship (if it's flat, it generalizes), but I believe it is considered to be deeply related. In this way, there is a way of thinking that overfitting is prevented by devising ways to find solutions that generalize easily.

Over-parameterized Parameters Find Points Where Loss is Almost 0

There are also efforts to make it easier to find solutions by increasing parameters more than necessary to achieve a certain performance (over-parameterization). This is what is called the blessing of dimensionality; even if loss cannot be reduced by updating some parameters, there is a high possibility that it can be reduced by increasing others. In other words, as an image, if there are excessive parameters, there exists a point where the loss is almost 0 that can be reached from any initial value of the parameters, and as a result, one can find appropriate parameters.

Also, according to research by Du et al., it is shown that if gradient descent is applied to an over-parameterized neural network, the training loss can achieve almost 0, even though the loss function is a non-convex objective function. If the loss function were a convex function, one could always move to the point with the lowest loss by repeating gradient descent, but if it is not, one should not be able to find it without luck or an enormous amount of time. The amazing thing about this study is that it shows that even if it has a non-convex shape, a point where the loss is almost 0 is always found in linear time.^[8] The feel is as follows^[9].

Let's define the loss as follows:

$$L(\theta) = \frac{1}{2} \sum_{i=1}^n (f(\theta,x_i) - y_i)^2$$

Where:

• $f(\theta, x_i)$ is the predicted value of the neural network for data $x_i$.
• $y_i$ is the ground-truth label of data $x_i$.
• $\theta$ is all the parameters of the neural network.

When gradient descent is applied, the change in the residual (the difference between the truth and prediction) $y - u(k)$ at each step (iteration) $k$ during training can be approximately expressed by the following equation:

$$y - u(k+1) \approx (I - \eta G(k)) (y - u(k))$$

This equation shows that the residual at the next step is obtained by multiplying the current residual by a matrix $(I - \eta G(k))$.

• $I$ is the identity matrix
• $\eta$ is the learning rate (step size of gradient descent)
• $G(k)$ is the Gram matrix induced by the neural network parameters $\theta(k)$ during training

Each element of this Gram matrix $G(k)$ is defined by the inner product of the gradients (directions of change) with respect to parameters of the predicted values for different data points. Simply put, this matrix can be thought of as an indicator showing how similarly the predicted values for different data points change in the direction of change when the neural network's parameters are changed slightly during training.

And the characteristic of this Gram matrix $G(k)$ is that when the neural network's "width" $m$ (number of neurons in the hidden layers) is sufficiently large, $G(k)$ remains in a state very close to a fixed matrix $K^{(H)}$ that depends only on the training data and network structure throughout the training process. In other words, it can be approximated as $G(k) \approx K^{(H)}$.

The stability of this Gram matrix is explained mainly in two stages:

1. Stability during initialization: The Gram matrix $G(0)$ of a randomly initialized network is close to a fixed matrix $K^{(H)}$.
2. Stability during training: As training progresses, the Gram matrix $G(k)$ maintains a state close to the initial $G(0)$.

Due to this stability, the residual dynamics behave approximately linearly as in the previous equation. Due to this approximate linear dynamics, the training loss $L(\theta(k))$ decreases at a linear rate corresponding to the minimum eigenvalue $\lambda_{\min}(K^{(H)})$ of the Gram matrix $K^{(H)}$.

In the paper, it is proven that if the network width $m$ is sufficiently large and the learning rate $\eta$ is set appropriately, $\lambda_{\min}(K^{(H)})$ is maintained at a constant strictly greater than zero (e.g., $\lambda_0/2$) or higher. This shows that the training loss decreases at a linear rate and finally converges to almost zero.

In other words, even if the loss function as a whole is non-convex, due to over-parameterization, the decrease in loss due to gradient descent behaves as if it were optimizing a linear system, so one can reach a global minimum solution (= a point with zero training loss).^[10]

The Contradiction of Generalizing with Massive Parameters

With countless solutions achieving zero training error, why can learning algorithms find a "good" solution even for unknown test data? We will focus on Double Descent to unravel this.

Statistics textbooks often say that generalization performance deteriorates when the number of parameters becomes massive, and this can be explained by the bias-variance tradeoff.

In this chapter, we will first understand the bias-variance tradeoff, then confirm that "Double Descent," where it does not hold, is established both experimentally and mathematically, and aim to know why overfitting does not occur with massive parameters.

Bias-Variance Tradeoff

Many of you have likely heard the term itself.

Overview

In machine learning, a model's prediction error can be decomposed into three components: bias, variance, and noise. Noise is the uncertainty included in the data, which is a fundamentally unremovable error, so we will explain without noise this time. On top of that, decomposing it into bias and variance is called bias-variance decomposition. This is an important concept for understanding model performance, and the image is as follows:

$$E[(y - \hat{f}(x))^2] = \text{Bias}^2 + \text{Variance}$$

Here, bias represents the deviation from the true function $f(x)$. High bias means a lack of model expressive power. On the other hand, variance represents the variability of predictions for different training datasets. This means instability caused by model complexity (number of parameters). The two have a tradeoff relationship; since the property is that lowering one raises the other, traditional statistics textbooks write that balancing them is important.

I have illustrated states of high bias, high variance, and a balanced state in order from left to right.

This is an example with simple polynomial regression. The faint approximation curves represent model curves for each resampling.

Organizing the content of this figure gives the following:

State	Model Complexity and Characteristics	Training Error	Test Error
High Bias (Underfitting)	The model is too simple and cannot capture the data features.	High	High
High Variance (Overfitting)	The model is too complex and has even learned data noise.	Low	High
Good Balance (Good Fit)	The model complexity is appropriate and captures major data features.	Low	Low

As a point of understanding, when estimating multiple times with different datasets, if the variance is high, the model is not stable, and one ends up estimating widely different models. Comparing the faint approximation curves in the upper (left) and (middle) of the figure, you can see that the variability of the model is larger in the middle. This is the point of understanding for a state where variance (model variability) is large.

Double Descent

Double Descent is the shocking content that the previous bias-variance tradeoff collapses.

A figure representing double descent. Left (a) shows the behavior in classical models with relatively few parameters, and right (b) is the behavior in modern models with a large number of parameters. The horizontal axis is model expressive power (i.e., number of parameters), and the vertical axis represents something like prediction error on test data. In left (a), performance improves as the number of parameters increases in the beginning, like the traditional bias-variance tradeoff, but once the parameters can completely remember the learning data, generalization performance declines (variance rises), taking a U-shape. On the other hand, right (b), while drawing a U-shape like (a) in the beginning, exhibits a two-stage error phenomenon (Double Descent) where generalization performance improves if you continue to increase the number of parameters after that. Cited from Reconciling modern machine learning practice and the bias-variance trade-off Figure 1.

Double Descent, which runs counter to the common sense of traditional statistics that prediction performance (generalization performance) improves when the number of parameters is far larger than the number of data points (over-parameterization region), can be quantitatively explained using mathematical formulas in high-dimensional linear regression models, not just as a mere empirical rule.

https://arxiv.org/abs/1903.08560

1. Definition and Decomposition of Generalization Performance (Prediction Risk)

First, generalization performance is evaluated by the "prediction risk" $R_X(\hat{\beta};\beta)$. This indicates how accurately the estimator $\hat{\beta}$ learned with the training feature matrix $X$ makes predictions for new (unobserved) test data $(x_0, y_0)$.

Prediction risk is defined by the following equation:

$$R_X(\hat{\beta};\beta) = E[{({x_0}^T\hat{\beta} − {x_0}^T \beta)^2 |X] = E[ ||\hat{\beta} − \beta ||^2}_\Sigma |X ]$$

As is well-known in statistics, this prediction risk can be decomposed into two components: bias and variance.

$$R_X(\hat{\beta};\beta) = \underbrace{||E[\hat{\beta}]|X)− \beta||^2_{\Sigma}}_{Bias term B_X(\hat{\beta};\beta)} + \underbrace{\text{Tr}[\text{Cov}(\hat{\beta}|X))\Sigma]}_{Variance term V_X(\hat{\beta};\beta)}$$

Details of these formula expansions

Formula Expansion of Prediction Risk

$$R_X(\hat{\beta};\beta) = E[({x_0}^T\hat{\beta} - {x_0}^T \beta)^2 |X] \\ R_X(\hat{\beta};\beta) = E[({x_0}^T(\hat{\beta} - \beta))^2 |X]$$

Let $v = \hat{\beta} - \beta$, and let the inner product (scalar) be $a=x_0^T v$.
$(x_0^Tv)^2=(x_0^Tv)(x_0^Tv)=v^T x_0 x_0^T v$
Since $\hat{\beta}$ and $\beta$ are conditioned on $X$, they are considered constants, so $v$ is also a constant vector. Therefore, they can be pulled out of the expectation.

$$R_X(\hat{\beta};\beta) = v^T E[{x_0} {x_0}^T |X] v$$

Since $x_0$ is independently and identically distributed (iid) with training data $x_i$, $E[x_i]=0, \text{Cov}[x_i]=\Sigma$ can be used. Substituting this,

$$v^T E[{x_0} {x_0}^T |X] v = v^T \Sigma v = E[(\hat{\beta} - \beta)^T \Sigma \hat{\beta} - \beta))|X]$$

If we write notation as $||x||^2_\Sigma = x^T\Sigma x$, then

$$E[||\hat{\beta} - \beta||^2_\Sigma|X]$$

is obtained.

Bias-Variance Decomposition

Decompose $||\hat{\beta} - \beta||^2_\Sigma$ into bias-variance.
First, consider the part $\hat{\beta} - \beta$, and as is common in this type of calculation, insert $E[\hat{\beta}|X]$ in the middle.

$$\hat{\beta} - \beta = (\hat{\beta} - E[\hat{\beta}|X]) + (E[\hat{\beta}|X] - \beta)$$

Substitute into the original equation and expand.

$$\begin{aligned} R_X(\hat{\beta};\beta) &= ||\hat{\beta} - \beta||^2_\Sigma \\ &= ((\hat{\beta} - E[\hat{\beta}|X]) + (E[\hat{\beta}|X] - \beta))^T \Sigma ((\hat{\beta} - E[\hat{\beta}|X]) + (E[\hat{\beta}|X] - \beta)) \\ &= ||E[\hat{\beta}|X] - \beta||^2_{\Sigma} + \text{Tr}[\text{Cov}(\hat{\beta}|X)\Sigma] \end{aligned}$$

Here:

• Bias term $||E[\hat{\beta}|X] - \beta||^2_{\Sigma}$: Indicates how far the estimator's mean is from the true value $\beta$. This relates to the capability of how accurately the model can represent the true function.
• Variance term $\text{Tr}[\text{Cov}(\hat{\beta}|X)\Sigma]$: Indicates how much the estimator varies across different training datasets. This relates to how sensitive the model is to noise in the training data.

2. Bias and Variance of Ridgeless Least Squares Estimator

To capture the property of models that "perfectly interpolate data (training error becomes zero)," which is widely used, especially in deep learning models, we focus on minimum $L_2$-norm ("ridgeless") least squares interpolation. This selects the solution with the minimum $L_2$-norm in the over-parameterized situation ($p > n$^[11]) where many solutions exist.

Bias $||E[\hat{\beta}|X] - \beta||^2_{\Sigma}$ and variance $\text{Tr}[\text{Cov}(\hat{\beta}|X)\Sigma]$ can be transformed as follows for this ridgeless least squares estimator $\hat{\beta}$:

• Bias: $B_X(\hat{\beta};\beta)=\beta^T \Pi \Sigma \Pi \beta$
• Variance: $V_X(\hat{\beta};\beta)= \sigma^2/n \text{Tr}[\hat{\Sigma}^+ \hat{\Sigma}]$

Here, $\hat{\Sigma}=X^T X /n$ is the sample covariance matrix of the training data, and $\Pi = I - \hat{\Sigma}^+ \hat{\Sigma}$ ^[12] is the projection matrix onto the Null Space of the training feature matrix $X$. $σ^2$ is the variance of noise included in $y$.

Understand the meaning of this formula with a feel

Note that in the paper, it is assumed $E(x_i)=0$ (centralized).

Bias

Confirm that $||E[\hat{\beta}|X] - \beta||^2_{\Sigma}$ becomes $\beta^T \Pi \Sigma \Pi \beta$.

The parameter estimation for linear regression is given by the unbiased estimator as follows^[13].

$$E[\hat{\beta}|X] = (X^T X)^{-1} X^T Y$$

Here, replacing the inverse matrix part with a generalized inverse matrix,

$$\begin{aligned} E[\hat{\beta}|X] &= (X^T X)^{+} X^T Y \\ &= (X^T X)^{+} X^T X \beta \\ &= \hat{\Sigma}^{+}\Sigma \beta \end{aligned}$$

becomes. Therefore,

$$\begin{aligned} B_X(\hat{\beta};\beta) &= \lVert E[\hat{\beta}|X] - \beta \rVert^2_{\Sigma} \\ &= \lVert \hat{\Sigma}^{+}\Sigma \beta - \beta \rVert^2_{\Sigma} \\ &= \lVert (\hat{\Sigma}^{+}\Sigma - I)\beta \rVert^2_{\Sigma} \\ &= \beta^T \Pi \Sigma \Pi \beta \end{aligned}$$

However, we let $\Pi = I - \hat{\Sigma}^{+}\Sigma$. Be careful as this formula is easy to mistake the handling of $\Sigma$ and $\hat{\Sigma}$.

Variance

Confirm that $\text{Tr}[\text{Cov}(\hat{\beta}|X)\Sigma]$ becomes $V_X(\hat{\beta};\beta)= \sigma^2/n \text{Tr}[\hat{\Sigma}^+ \hat{\Sigma}]$.

First, calculate the covariance matrix of $\hat{\beta}$ conditioned on $X$.
Note that when $X$ is given, the randomness of $\hat{\beta}$ originates only from noise $\varepsilon$ ($y = X\beta + \varepsilon$).

$$\begin{aligned} \text{Cov}(\hat{\beta}|X) &= \text{Cov}((X^T X)^+ X^T y | X) \\ &= (X^T X)^+ X^T \text{Cov}(y|X) ((X^T X)^+ X^T)^T \\ &= (X^T X)^+ X^T \text{Cov}(\varepsilon|X) X ((X^T X)^+)^T \end{aligned}$$

Here, the noise covariance is $\text{Cov}(\varepsilon|X) = \sigma^2 I_n$, and using the property of generalized inverse matrix $(A^+)^T = (A^T)^+$ and that $X^TX$ is a symmetric matrix,

$$\begin{aligned} \text{Cov}(\hat{\beta}|X) &= (X^T X)^+ X^T (\sigma^2 I_n) X (X^T X)^+ \\ &= \sigma^2 (X^T X)^+ X^T X (X^T X)^+ \end{aligned}$$

Using the Moore-Penrose generalized inverse matrix property $A^+ A A^+ = A^+$, it can be simplified to $(X^T X)^+ X^T X (X^T X)^+ = (X^T X)^+$. Therefore,

$$\text{Cov}(\hat{\beta}|X) = \sigma^2 (X^T X)^+$$

becomes. Substituting this into the variance term $\text{Tr}[\text{Cov}(\hat{\beta}|X)\Sigma]$,

$$V_X(\hat{\beta};\beta) = \sigma^2 \text{Tr}[(X^T X)^+ \Sigma]$$

is obtained. On the other hand, the final variance formula shown in the text was $V_X(\hat{\beta};\beta) = \sigma^2/n \text{Tr}[\hat{\Sigma}^+ \hat{\Sigma}]$.
Using the text's notation $\hat{\Sigma} = X^T X/n$, this can be expanded as follows:

$$\begin{aligned} \frac{\sigma^2}{n} \text{Tr}[\hat{\Sigma}^+ \hat{\Sigma}] &= \frac{\sigma^2}{n} \text{Tr}[ (X^T X / n)^+ (X^T X/n) ] \\ &= \frac{\sigma^2}{n} \text{Tr}[ n(X^T X)^+ (X^T X/n) ] \\ &= \frac{\sigma^2}{n} \text{Tr}[ (X^T X)^+ X^T X ] \end{aligned}$$

Comparing this result with our derived $\sigma^2 \text{Tr}[(X^T X)^+ \Sigma]$, this equality holds under the assumption that $\Sigma = \frac{1}{n}X^T X = \hat{\Sigma}$, meaning the population covariance matrix equals the sample covariance matrix.
This is a setting often used in high-dimensional analysis, and by placing this assumption, the variance term can be expressed in a more concise form.

Supplementary notes on viewing bias

• In the case of $p < n$ (underparametrized: parameter count < data point count)

Since $X$ usually has full column rank, $\Pi = 0$, and the bias term becomes zero. This is consistent with standard linear regression being an unbiased estimator (bias 0).

• In the case of $p > n$ (overparametrized: parameter count > data point count)

$X$ has full row rank (generally) and $\Pi$ is non-zero, so the bias term is not zero. Regularized linear regression was not an unbiased estimator, was it?

3. Change in Prediction Risk in Over-parameterization

So far has been the preamble, and this is the crux. How prediction risk changes in the region of "over-parameterization" where the number of parameters $p$ becomes far larger than the number of data points $n$ (situation where $\gamma = p/n > 1$ as a constant, $p \rightarrow \infty, n \rightarrow \infty$) depends greatly on the assumption of feature distribution. In this term, for simplicity, we consider the case of Isotropic Features (where $\Sigma = I_p$, i.e., features are iid and the covariance matrix is the identity matrix).

First, let

• $r^2 = ||\beta||^2_2$ (squared norm of the estimated parameters)
• $\gamma = p/n$
• $\gamma > 1$

We have already shown in the previous term that the bias term is $\text{B}_X(\hat{\beta};\beta) = \beta^T\Pi\Sigma\Pi\beta$ and the variance term is $\text{V}_X(\hat{\beta};\beta) = \sigma^2/n\text{Tr}[\hat{\Sigma}^+\Sigma]$. Taking the limit of this in the "over-parameterization" region,

$$R_X(\hat{\beta};\beta) \rightarrow r^2 (1 - 1/ \gamma) + \sigma^2 / (\gamma - 1)$$

is obtained, and the behavior of the bias term and variance term can be analyzed separately from this equation.

Deriving the asymptotic prediction risk $R_X(\hat{\beta};\beta) \rightarrow r^2 (1 - 1/ \gamma) + \sigma^2 / (\gamma - 1)$ that suddenly appeared is very difficult, so I apologize, but I will omit it...

Behavior of the Bias Term $r^2 (1 - 1/ \gamma)$

As $\gamma$ becomes greater than 1 (as $p$ exceeds $n$), $1/\gamma$ decreases and $1 - 1/\gamma$ increases. This means that bias increases as $\gamma$ increases.

Intuitively, when $p \gt n$, the minimum-norm estimator $\hat{\beta}$ is constrained to the row space of the training data matrix $X$ (an $n$-dimensional subspace).^[14] (Because it fits to perfectly interpolate all training data, it deviates from the true $\beta$). As $p$ increases, the proportion of the entire $p$-dimensional space occupied by this $n$-dimensional row space becomes smaller, so the deviation (bias) from the true $\beta$ increases.

To rephrase, even if the model becomes very complex and $p$ increases, the estimator can only learn within the limited $n$-dimensional subspace spanned by the training data. As this subspace becomes relatively smaller with respect to the total space ($p$-dimensional), the probability that the true $\beta$ lies outside this space increases, resulting in increased bias.

Behavior of the Variance Term $\sigma^2 / (\gamma - 1)$

As $\gamma$ becomes greater than 1, $\gamma - 1$ increases and $1 / (\gamma - 1)$ decreases. This means that variance decreases as $\gamma$ increases.

This phenomenon might seem counterintuitive to those who have the image that if parameters increase, one can draw prediction curves passing through all training data points in various ways, but it can be explained as follows: As $p$ increases, the minimum-norm least squares solution can distribute the coefficients across more dimensions. This generally reduces the squared norm of the solution, which acts as if the model were more "regularized," resulting in a decrease in variance.

With this, in the simple linear regression case for the isotropic features model, we have mathematically confirmed the phenomenon where prediction risk diverges at the interpolation threshold $\gamma=1$, and subsequently decreases in the $\gamma \gt 1$ region. Let's look at the state of this setting.

Confirming the double descent where prediction risk (generalization performance) recovers after deteriorating at $\gamma=1$. The difference in lines is the SNR (Signal to Noise Ratio) (relative magnitude of data noise). Cited from Surprises in High-Dimensional Ridgeless Least Squares Interpolation Figure 2.

Since the setting here is too simple, the $\gamma \gt 1$ region does not reach the global minimum risk. In the next section, we will look at the latent space model with slightly changed conditions.

Double Descent in Latent Space Models

The basic settings for this model are as follows:

$$y_i = \theta^T z_i + \xi_i \quad (24) \\ x_{ij} = w_j^T z_i + u_{ij}$$

• $y_i \in \mathbb{R}$: The response variable (target variable) for the $i$-th data point.
• $z_i \in \mathbb{R}^d$: The latent feature vector for the $i$-th data point. This is not directly observed.
• $\theta \in \mathbb{R}^d$: The true coefficient vector corresponding to the latent feature $z_i$. This shows a linear relationship between $y_i$ and $z_i$ in the latent space.
• $\xi_i \sim N(0, \sigma_\xi^2)$: The noise in the response variable $y_i$. Follows a Gaussian distribution with mean zero and variance $\sigma_\xi^2$.
• $x_{ij}$: The $j$-th element of the observed feature vector $x_i \in \mathbb{R}^p$ for the $i$-th data point.
• $w_j \in \mathbb{R}^d$: The weight vector indicating how the $j$-th observed feature $x_{ij}$ is generated from the latent feature $z_i$. In this case, $w_j^T$ denotes the $j$-th row of matrix $W$, and $x_{ij}$ is the inner product of the $j$-th row of $W$ and $z_i$ plus noise.
• $u_{ij} \sim N(0, 1)$: The noise in the observed feature $x_{ij}$. Follows an iid Gaussian distribution with mean zero and variance 1.

In this model, data is generated from a low-dimensional latent space ($z_i$), and observed features ($x_i$) have a structure where they are noisy transformations of those latent features.

Deriving the limit of prediction risk in this case is also extremely difficult, so I will omit it, but it becomes a complex formula like the following (from Surprises in High-Dimensional Ridgeless Least Squares Interpolation Corollary 4.).

$$\begin{align} R_X(\hat{\beta};\beta)&\to \mathscr{B}_{\text{lat}}(\psi, \gamma) + \mathscr{V}_{\text{lat}}(\psi, \gamma) \\ \mathscr{B}_{\text{lat}}(\psi, \gamma) &:= \left\{1 + \frac{\gamma c_0}{\frac{\mathscr{E}_1(\psi, \gamma)}{\mathscr{E}_2(\psi, \gamma)}}\right\} \cdot \frac{r_\theta^2}{(1 + \psi)(1 + c_0\gamma(1 + \psi^{-1}))^2} \\ \mathscr{V}(\psi, \gamma) &:= \sigma^2\gamma c_0 \frac{\mathscr{E}_1(\psi, \gamma)}{\mathscr{E}_2(\psi, \gamma)} \\ \mathscr{E}_1(\psi, \gamma) &:= \frac{1 - \psi}{(1 + c_0\gamma)^2} + \frac{\psi(1 + \psi^{-1})^2}{(1 + c_0(1 + \psi^{-1})\gamma)^2} \\ \mathscr{E}_2(\psi, \gamma) &:= \frac{1 - \psi}{(1 + c_0\gamma)^2} + \frac{1 + \psi}{(1 + c_0(1 + \psi^{-1})\gamma)^2} \\ 1 - \frac{1}{\gamma} &= \frac{1 - \psi}{1 + c_0\gamma} + \frac{\psi}{1 + c_0(1 + \psi^{-1})\gamma} \end{align}$$

As a result, in the latent space model, prediction risk monotonically decreases from where $\gamma = p/n$ exceeds 1, and reaches the global minimum at the asymptotic limit of $\gamma \to \infty$.

Cited from Surprises in High-Dimensional Ridgeless Least Squares Interpolation Figure 6.

This is partly my interpretation, but under conditions like the latent space model, two things can be considered:

Intuitive Understanding of Monotonic Decrease in Prediction Risk under Over-parameterization

In this setting, each feature vector $x_i$ can be seen as a noisy measurement of the latent variable $z_i$. If there were no noise $u_{ij}$, minimum-norm regression on observed features $x_i$ would be equivalent to minimum-norm regression on latent variables $z_i$. Even if noise $u_{ij}$ exists, it is thought that "as $p$ increases, the noise is effectively 'averaged out', approaching the ideal situation where $z_i$ is directly observed." In other words, by increasing the dimensionality of input features, more information regarding the latent feature $z_i$ is extracted, and as a result, prediction performance improves. This corresponds to the case of AI that utilizes weak information.

Intuitive Understanding of Regularization Parameter $\lambda \to 0$

In large-scale over-parameterization, it is explained in the paper that the optimal regularization parameter^[15] value becomes $\lambda \to 0$. Let's consider the intuitive understanding of this.

As learning parameters increase (note the color representing the ratio of parameter count to training data count), the optimal regularization parameter $\lambda$ approaches 0. Cited from Surprises in High-Dimensional Ridgeless Least Squares Interpolation Figure 10.

This phenomenon is explained by the idea that when input noise is intrinsically contained in the model, that noise functions as an additional regularization term. If the feature matrix $X$ is viewed as the sum of a true noise-free matrix $\bar{X} = ZW^T$ and a noise matrix $U$ ($X = \bar{X} + U$), the ridge regression kernel matrix $K(X,X) = XX^T/n$ is approximately $K(\bar{X},\bar{X}) + U U^T/n$. If $U U^T/n$ is approximately proportional to $I_n$, it acts as an effective regularization term, so there is no need to set a large ridge parameter $\lambda$ explicitly (implicit regularization). This is the intuitive explanation.

However, this idea of implicit regularization has been viewed with skepticism in recent years. For example, research by Nagarajan et al. states that implicit regularization alone cannot explain the superior generalization performance of over-parameterized neural networks.

The second figure from the left shows how the squared norm of weight parameters increases as training data increases. If implicit regularization were effective (as in the situation where test error decreases, as in the third figure from the left), the norm of the weight parameters should approach 0, but this is an example where that is not happening. Cited from Deep Double Descent: Where Bigger Models and More Data Hurt Figure 1. Cited from Uniform convergence may be unable to explain generalization in deep learning Figure 1.

Double Descent in Multi-layer Neural Networks

Double descent is observed as a phenomenon not only in ridgeless regression with shallow layers but also in models with deep layers. For example, as shown in the figure below, double descent is also confirmed when continuously increasing the number of parameters in multi-layer neural networks like ResNet18.

Cited from Deep Double Descent: Where Bigger Models and More Data Hurt Figure 1.

Does performance deteriorate when increasing training data?

Recalling the idea of double descent, prediction risk drops again when the number of parameters becomes massive relative to the number of data points. Therefore, given the same number of parameters, returning to the region where generalization performance worsens due to an increase in data points can occur. This phenomenon is explained in the world of multi-layer neural networks by EMC (Effective Model Complexity) (corresponding to $\gamma = p/n$ in the previous linear regression example).

EMC is an indicator defined aiming to explain double descent seen in various deep learning tasks in a unified way (but note that it is an empirical indicator and has task dependency). Details are in this paper.

https://arxiv.org/abs/1912.02292

The EMC of a training procedure $T$ is defined as the maximum number of training samples $n$ that can, on average, achieve nearly zero training error. Mathematically, for a distribution $D$ and a parameter $\epsilon \gt 0$:

$$\text{EMC}_{D,\epsilon}(T) := \max \{n | E_{S \sim D^n} [\text{Error}_S(T (S))] \leq \epsilon \}$$

Here, $\text{Error}_S(M)$ shows the average error of model $M$ for training sample $S$. For the value of $\epsilon$, a small value such as 0.1 is usually used empirically.

In the critically parameterized regime where EMC is approximately the number of training samples $n$, it is said that peculiar behavior is shown when changing the model or training procedure. Organized below:

Region	Condition	Change in Test Error when complicating model or training
Under-parameterized regime	$\text{EMC} \ll n$	Decreases
Over-parameterized regime	$\text{EMC} \gg n$	Decreases
Critically parameterized regime	$\text{EMC} \approx n$	Increases or Decreases

With the introduction of EMC, it became possible to explain double descent that occurs even outside of just model parameter count.

• Epoch-wise double descent (even if the model is fixed, EMC increases by increasing training time, and test performance double descends)
• Non-monotonicity of sample count (the effect of the point where data count nears EMC (where test error reaches a peak) shifting to the right by increasing training samples, and the effect of lowering the entire error)

Figure (a) on the left represents double descent per model when changing dataset size of a 5-layer CNN. The upper side has a range of model sizes where test error does not improve even if training with twice the sample size (green shading). The lower side has a range of model sizes where test error does not improve even if learning with 4 times the sample size (red shading). Figure (b) on the right shows that there is a region where performance declines as the number of samples increases. Cited from Deep Double Descent: Where Bigger Models and More Data Hurt Figure 11.

Summary of Double Descent

• Even in simple linear regression models, the phenomenon where prediction risk decreases after crossing the interpolation threshold ($p=n$) can be shown strictly by mathematical formulas.
• The counter-intuitive phenomenon that variance decreases as the number of parameters increases can be explained by the property that the L2 norm is minimized.
• It is suggested that findings from this linear model can be applied to non-linear and complex neural networks, and that phenomenon is experimentally confirmed.

(Reference) Triple Descent / Multiple Descent

In ensemble models that combine different random features, under certain conditions, a drop in prediction risk 3 or more times is also confirmed (this is for reference only).

Triple descent. Cited from Multiple Descent in the Multiple Random Feature Model Figure 1.

Scaling Laws

Although it deviates from the main subject, I have a feeling that I cannot avoid touching on scaling laws, so I will briefly digress.

In double descent, we have seen non-monotonicity: "performance worsens once after the model exceeds a certain scale, and improves again beyond that." However, in practice, there are situations where we want to quantitatively decide how large a model should be and how long it is desirable to train it.

Therefore, in recent years, an empirical rule called Neural Scaling Laws (NSL) is being established from both large-scale experiments and theoretical aspects.

Parameter Count and Data Count Work Separately

Research by Kaplan et al. targeting language models considered language models limited by model size $N$, training tokens $D$, and total computation $C$ as independent variables, and the loss $L$ is:

$$L(N) = \left(\frac{N_c}{N}\right)^{\alpha_N} \\ L(D) = \left(\frac{D_c}{D}\right)^{\alpha_D} \\ L(C) = \left(\frac{C_c^{\min}}{C_{\min}}\right)^{\alpha_c^{\min}}$$

Here, $\alpha_N \approx 0.076, N_c \approx 8.8\times 10^{13}, \alpha_D \approx 0.095, D_c \approx 5.4 \times 10{13}, \alpha^{\min}_c \approx 0.050, C^{\min}_c \approx 3.1 \times 10^8$.

Furthermore, by combining these, they derive the impact on performance when both model size $N$ and data size $D$ are simultaneously changed.

$$L(N,D) = \left[ \left(\frac{N_c}{N}\right)^{\frac{\alpha_N}{\alpha_D}} + \frac{D_c}{D} \right]^{\alpha_D}$$

From this, because the exponent $\frac{\alpha_N}{\alpha_D}$ takes effect, if the computational budget $C$ is fixed, it might be appropriate to prioritize building a model slightly larger and use data (tokens) to a certain extent.

Chinchilla Scaling Laws

Research by Hoffmann et al. trained over 400 models with 70M to 70B parameters and 5B to 500B tokens, and demonstrated:

• For the same FLOPS^[16], it is best to scale $N$ and $D$ equally.
• Chinchilla^[17] with $N=70B, D=1.4T$ actually outperformed Gopher^[18] with $N=280B, D=300B$ in all benchmarks.

This is not a situation where the number of parameters is excessive compared to the training data size, but it claims that under excessive parameterization that does not match computational resources, the model's potential is not being drawn out.

The Mystery of Deepening

Up to this point, we have seen signs that generalizing parameters seem to be findable under over-parameterization. However, in the discussion so far, there should have been a method of having a large number of parameters per layer and configuring them with 2-3 layers. On the other hand, the history of deep learning evolution is a history of deepening, starting from the 8 layers of AlexNet, to dozens or hundreds in ResNet, and now models with over 1000 layers are appearing. In this chapter, we will explain this mystery of deepening from the perspective of efficiency.

Expressive Efficiency through Hierarchical Composition

Qualitative Explanation

The biggest difference between shallow and deep networks lies in how functions are constructed; deep networks are more efficient at representing complex functions (they can express them with fewer parameters).

Shallow networks increase expressive power by widening. By placing many neurons in a single hidden layer and adding them up, they express functions. This is the image of building a target function little by little by lining up many simple functions (e.g., visualization of ReLU function superposition checked in the first half of the article). This allows the complexity of representable functions to increase additively.

Deep networks increase expressive power by stacking layers. Mathematically, stacking one layer corresponds to composing one function. In other words, by nesting functions such that $f(x) = g_L(\ldots g_2(g_1 (x)) \ldots)$, using the output of the previous layer as the input for the next layer, very complex functions are generated. This allows the complexity of representation to increase multiplicatively.

This structure of function composition unique to deep networks works very advantageously in solving real-world problems. For example, in image recognition, pixels form edges, edges form shapes, and shapes form objects. Neural networks with deep layers can learn these intermediate features at each layer and reuse them in subsequent layers. This reuse of features is one of the reasons why neural networks with deep layers can achieve high expressive efficiency.

Shows features being extracted in the first half of a neural network. Cited from DeepFace: Closing the Gap to Human-Level Performance in Face Verification Figure 2.

Mathematical Explanation

This expressive efficiency is also shown mathematically. According to Benefits of depth in neural networks, a deep neural network with $\Theta(k^3)$ layers, where each layer has $\Theta(1)$ nodes and parameters, can represent very complex functions (functions with $\Theta(2^{k^3})$ order oscillations). On the other hand, for a shallow neural network with $O(k)$ layers to represent a function with the same complexity, $\Omega(2^k)$ parameters are required. That is, by increasing layers in proportion to $k^3$, it is shown that one can acquire complexity equivalent to increasing $\Omega(2^k)$ (exponential) parameters in a shallow neural network.

If you are not familiar with notation like $\Theta$, please open "About Asymptotic Notation" below to check.

About Asymptotic Notation

I am writing in a way that would make people who see it angry, but since this article's motto is to understand the feel, I am writing by feel. Please see Wikipedia for formal definitions.

• $\Theta$ (big-theta: bounded from both above and below)
• $O$ (big-o: bounded from above if you choose a constant)
• $o$ (small-o: bounded from above no matter what constant multiplier)
• $\Omega$ (big-omega: bounded from below)

From Wikipedia Landau Symbols: Other Asymptotic Notations

The feeling of this claim is:

• Neural networks with few layers can express few oscillations.
• Neural networks with many layers can express many oscillations.
• Functions with few oscillations cannot approximate functions with many oscillations.

Therefore, deep neural networks are far easier to approximate complex (many-oscillation) functions compared to shallow neural networks.

To grasp that oscillations increase with deepening, consider a function $f$ like the following:

$$f(z) = \sigma_R(2\sigma_R(z) - 4\sigma_R(z-1/2)) \\ \sigma_R(z) = \max(0, z)$$

($\sigma_R$ is ReLU). This has a shape like a triangular wave as in the figure below (in step.6 on the lower right, it is a triangular wave).

Visualization of $f(z) = \sigma_R(2\sigma_R(z) - 4\sigma_R(z-1/2))$. You can make a triangular wave by passing the difference of ReLU functions shifted in the $x$ direction further through a ReLU function.

Since this function can be expressed with a constant number of parameters, it can be realized with 1 layer, $\Theta(1)$ nodes, and $\Theta(1)$ parameters.

The Situation of Deep Neural Networks

By repeatedly composing this function $f$ $k$ times ($f^k(z) = f(f(\cdots f(z) \cdots)$), its number of oscillations increases exponentially ($f^k(z)$ has $2^k + 1$ oscillations).

Since a neural network calculating $f^k$ can be constructed by stacking the layer calculating $f$ $k$ times, this neural network has $k$ layers, each layer is composed of $\Theta(1)$ nodes, and the entire network only requires $\Theta(1)$ parameters (because it reuses the same function $f$). Composition functions are hard to imagine, and it might not ring a bell even if written only in words, but it is possible to get a feel by visualizing it.

Visualization of $f(f(\cdots f(z) \cdots)$ composed $k$ times. From left to right: $k=0,1,2$, and the lower row shows $k=3,5,10$ from left to right. Indeed, oscillations increase exponentially in response to $k$. ※The way to count oscillations is the number of times the direction of the straight line changes.^[19] Try counting that it is $2^k + 1$ times.

The Situation of Shallow Neural Networks

Define the oscillation of a function as the number of times it crosses a certain threshold.

$C_r(f)$ (Crossing Number): Represents the number of times function $f$ crosses a certain specific threshold (1/2 in this paper).

In a shallow neural network, if function $f$ is a $(t, \alpha)$-poly (piecewise polynomial, i.e., a function divided into $t$ segments where each segment is a polynomial of degree at most $\alpha$), there is an upper bound of $C_r(f) \leq t(1 + \alpha)$. Therefore, to increase the frequency of oscillations, one must increase $t$ (number of segments) or $\alpha$ (degree of polynomial).

And it is not easy to increase the degree in a single layer. Increasing nodes within the same layer corresponds to the addition (or linear combination) of functions. Adding two polynomials by operating such as increasing nodes in one layer results in a polynomial where the number of terms is at most doubled, and the polynomial degree does not exceed the maximum degree of either. For this reason, the term contributing to the oscillation count ($t$) increases only linearly, and no exponential increase is seen.^[20]

To efficiently obtain high oscillation counts (many bends), it is necessary to further stack and compose these piecewise linear functions, which "depth" simply cannot reach.

Summary

The oscillation count $C_r(g)$ a neural network can make is expressed using the number of layers $l$ and the total number of nodes $m$ as follows:

$$C_r(g \circ h) \leq 2(2tm\alpha/l)^l \beta^{l^2}$$

Its relationship is characterized by the number of layers $l$ appearing in the exponent and the number of nodes $m$ appearing in the base, meaning a shallow neural network with few layers must exponentially compensate for that portion with width (number of nodes). This is the important role of depth.

In my opinion, the essence of deep learning is not the Universal Approximation Theorem, but the architecture that deep learning has. The compositional structure by multi-layered neural networks functions as a strong inductive bias^[21], and it is suitable for learning functions with hierarchical or compositional structures that are frequently seen in the real world. The architecture of deep learning itself is a kind of prior knowledge that guides learning to solutions that utilize compositionality.

Improvement of Approximation Error Rate

Let's also think from the perspective of Approximation Error Rate. Since the feel is similar to the discussion on expressive efficiency, I will stop this section with just a simple introduction.

Approximation error rate represents the rate of reduction in error when parameters are increased as a neural network approximates a function. The approximation error rate in a situation where a neural network function $g_{\theta}(x)$ with a parameter set $\theta$ of $W$ items approximates a function $f(x)$ is expressed as:

$$\inf_{\theta} ||f - g_{\theta}|| = O(W^{-\alpha})$$

(where $O$ is Landau's symbol, and I have already conveyed the feel in this article). A larger $\alpha$ means that functions can be approximated efficiently when increasing parameter count $W$. Let's look at the relationship between this approximation error rate and the depth of the network.

Approximation of Smooth Functions

First, consider the case where the function $f(x)$ to be approximated is sufficiently smooth^[22]. In this case, research by Barron showed that the approximation error rate for a 1-layer neural network is $\alpha=1/2$. This does not depend directly on the feature dimensionality $d$, meaning that even in a shallow neural network, if you increase the number of parameters, you can approximate smooth functions regardless of the size of the dimension. While shallow neural networks are sufficient when dealing with smooth functions, the functions one wants to approximate in the real world are not necessarily smooth. We will look at the approximation of complex functions in the next section and beyond.

Approximation of Non-Smooth Functions

Functions with discontinuous points, such as edge parts of images, or functions with sharp points, such as audio waveforms, are not smooth. To represent discontinuous or sharp points, it is necessary to concentrate a very large number of parameters in the vicinity of those points, which significantly lowers parameter efficiency. In this case, Yarotsky's research showed that the approximation error rate is strongly affected by the input feature dimensionality $d$, deteriorating to about $\alpha \approx 2/d$.

However, it was shown that deep neural networks (with ReLU as an activation function), as seen in the previous section, efficiently create "bends" by stacking layers, capturing singular points^[23] of non-smooth functions, and improving the approximation error rate.

$$\text{Error (Shallow Net)} \propto W^{-2/d} \\ \text{Error (Deep Net)} \propto W^{-c})$$

Since $c$ is a constant not dependent on dimensionality, deep neural networks are advantageous in approximation error rate.

Approximation of Functions with Non-Uniform Smoothness

Finally, consider the approximation of functions with non-uniform smoothness. These are functions where most of the function is very smooth, but only a part changes abruptly or has a complex structure. For example, the contour of a person in focus in a photograph with a blurred background corresponds to this.

Deep networks leverage their hierarchical structure to efficiently allocate resources (parameters) according to the smoothness at each location of the function. Thanks to this "adaptability," deep networks can maintain a high approximation error rate even for complex functions with non-uniform smoothness.

Deep neural networks can change smoothness locally. Cited from Approximation Performance and Complexity Analysis for Generalization Error of Deep Learning slide p.14.

Conclusion

You can set an eye-catching emoji for Zenn articles. I rack my brains every time about which emoji to use, but this time it was an immediate decision because "Dolphins are synonymous with Deep Learning!"^[24] Topics like this are not immediately useful in many practical applications, but they are very fun to study. I repeat myself, but I would appreciate it if you could point out errors, etc., in the comments section or X.

Note that figures and animations for which the source is not specified in this article were created from Python scripts generated by the author instructed by Claude Code. The author has visually confirmed the validity of the source code.

Summary of this Article

• Neural networks have powerful expressive power that approximates any function (Universal Approximation Theorem)
• And by devising learning methods and models in over-parameterized situations, one can find "valleys" where training error is nearly 0
• The phenomenon where generalization occurs due to over-parameterization, double descent, has been confirmed partially mathematically and empirically
• By multi-layering, expressive power increases exponentially, which can also be explained from the perspective of approximation error rate

References

• A Survey on Universal Approximation Theorems, Midhun T Augustine, 2024.
• Benefits of depth in neural networks, Matus Telgarsky, 2016.
• DeepFace: Closing the Gap to Human-Level Performance in Face Verification, Yaniv Taigman, et al., 2014.
• Reconciling modern machine learning practice and the bias-variance trade-off, Mikhail Belkin, et al., 2018.
• Surprises in High-Dimensional Ridgeless Least Squares Interpolation, Trevor Hastie, et al., 2019.
• Deep Double Descent: Where Bigger Models and More Data Hurt Preetum Nakkiran, et al., 2019.
• Visualizing the Loss Landscape of Neural Nets, Hao Li, et al., 2017.
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima, Shirish Keskar et al., 2016.
• Fantastic Generalization Measures and Where to Find Them, Yiding Jiang et al., 2019.
• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks, Jonathan Frankle, et al., 2018.
• Gradient Descent Finds Global Minima of Deep Neural Networks, Simon S. Du, et al., 2018.
• Universal approximation bounds for superpositions of a sigmoidal function, Andrew R. Barron, 1993.
• Error bounds for approximations with deep ReLU networks, Dmitry Yarotsky, 2017.
• Multiple Descent in the Multiple Random Feature Model, Xuran Meng, et al., 2024.
• Training Compute-Optimal Large Language Models, Jordan Hoffmann, et al., 2022.
• Scaling Laws for Neural Language Models, Jared Kaplan, et al., 2023.
• Uniform convergence may be unable to explain generalization in deep learning, Vaishnavh Nagarajan, J. Zico Kolter, 2019.
• Approximating Principles of Deep Learning, Masaaki Imaizumi, Iwanami Shoten, 2021.

脚注

1. Actually, I felt that researching with Gemini 2.5 Pro and ChatGPT o3 Pro didn't quite reach that level, so I wrote this article while investigating various things myself.

2. Please ignore the objection that it cannot be separated if points with different labels overlap for now.

3. The relationship between the number of parameters and data points is not so simple, and inductive bias plays a role. This is just for the sake of the "feel" of the explanation.

4. I have an image of this like Fourier transforms or Taylor expansions.

5. If you have read this far with interest, you should know that deep learning explores the parameter space using Stochastic Gradient Descent.

6. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima and Fantastic Generalization Measures and Where to Find Them

7. However, it does not correlate perfectly, and cases showing the opposite correlation have also been reported.

8. Note that there are several preconditions.

9. I could not follow the strict proof.

10. In the paper, it is explained that especially for ResNet architectures with residual connections, the dependence on the layers $H$ of the necessary width $m$ is improved from exponential to polynomial compared to general fully-connected neural networks.

11. $p$ is dimensionality, $n$ is number of data

12. $\hat{\Sigma}^+$ is called the minimum-norm generalized inverse matrix solution. General matrices do not necessarily have inverse matrices, but this is used when you want to find something like an inverse matrix even in such cases. This article is detailed.

13. Please check your statistical textbook for the derivation of this estimator.

14. Since the training data has $p$ columns but fewer than $n$ data points, I understand it as being constrained to an $n$-dimensional space.

15. This is a hyperparameter.

16. An index value of how many floating-point operations can be done per second.

17. A large-scale language model made by DeepMind before the appearance of Gemini.

18. A large-scale language model made by DeepMind before the appearance of Gemini.

19. In the paper, it is defined as the number of times it crosses a certain threshold.

20. Rephrasing. Each ReLU gate introduces one "bend" into the input space, but even if you linearly combine many ReLU gates in one layer, the result is a piecewise linear function, and the number of bends only increases in proportion to the number of nodes.

21. Things like assumptions or structures that machine learning models have. When predicting the trajectory of a thrown ball, using a quadratic function allows for accuracy improvement not dependent on data, but this is a fine inductive bias. Please also refer to Wikipedia.

22. Understanding it as differentiable infinite times.

23. Discontinuous points or sharp points.

24. Comes from the book Deep Learning. It has been a long time since the revised 2nd edition was published.