# Local Linear Recovery Guarantee of Deep Neural Networks at
Overparameterization

Yaoyu Zhanga<EMAIL_ADDRESS>
Leyang Zhangb<EMAIL_ADDRESS>
Zhongwang Zhanga<EMAIL_ADDRESS>
Zhiwei Baia<EMAIL_ADDRESS>
aSchool of Mathematical Sciences, Institute of Natural Sciences and MOE-LSC,
Shanghai Jiao Tong University, Shanghai, 200240, China
b Department of Mathematics, University of Illinois Urbana-Champaign, Urbana,
IL 61801, United States Corresponding author

###### Abstract

Determining whether deep neural network (DNN) models can reliably recover
target functions at overparameterization is a critical yet complex issue in
the theory of deep learning. To advance understanding in this area, we
introduce a concept we term “local linear recovery” (LLR), a weaker form of
target function recovery that renders the problem more amenable to theoretical
analysis. In the sense of LLR, we prove that functions expressible by narrower
DNNs are guaranteed to be recoverable from fewer samples than model
parameters. Specifically, we establish upper limits on the optimistic sample
sizes, defined as the smallest sample size necessary to guarantee LLR, for
functions in the space of a given DNN. Furthermore, we prove that these upper
bounds are achieved in the case of two-layer tanh neural networks. Our
research lays a solid groundwork for future investigations into the recovery
capabilities of DNNs in overparameterized scenarios.

Keywords: deep learning theory, recovery at overparameterization, local linear
recovery guarantee, optimistic sample size.

##  1 Introduction

Determining the requisite number of data points for a model to recover a
target function is a fundamental problem in regression. This issue is
particularly pertinent for deep neural network (DNN) models, where the
question arises: Can these models recover target functions using fewer data
points than their parameter count, thereby operating effectively in an
overparameterized regime? Traditional wisdom suggests that a linear model with
$M$ parameters typically needs $M$ data points to reconstruct a linear
function. Particularly, in band-limited signal recovery, the Nyquist-Shannon
sampling theorem posits that a periodic signal with a maximum frequency of $f$
(represented by $M=2f$ coefficients) can be perfectly reconstructed from
$n\geqslant 2f$ uniformly sampled points (Shannon, 1984). These precedents
imply that linear models lack recovery guarantee when overparameterized. In
contrast, nonlinear DNN models have been empirically shown to generalize
effectively even when overparameterized (Zhang et al., 2017). Subsequent
experiments reinforce this observation, indicating that DNNs can achieve zero
generalization error in recovering target functions under overparameterization
(Zhang et al., 2023b). This study delves into the theoretical underpinnings of
target function recovery for DNNs, with the goal of establishing a recovery
guarantee in overparameterized scenarios.

Within the spectrum of recovery guarantees, the global recovery
guarantee—ensuring target recovery through comprehensive training—is the most
robust and practically relevant, especially in overparameterized contexts.
However, the intricate and highly nonlinear training dynamics of DNNs render
this global guarantee theoretically elusive. To navigate this complexity, we
propose a more attainable goal: establishing a weaker form of recovery
guarantee for DNNs in overparameterized conditions. Specifically, we introduce
the concept of local linear recovery (LLR) guarantee, which scales back the
expectation from global recovery from a random initialization to local
recovery in the vicinity of an optimal point within the parameter space. While
local linear fitting of data is not practically feasible in general, the LLR-
guarantee sheds light on the optimistic (i.e., best-possible) performance for
global recovery of DNNs, suggesting that without an LLR-guarantee at
overparameterization, stronger forms of recovery are unlikely.

Our main contributions are threefold: (i) We introduce the LLR-guarantee and
formulate its theoretical framework for both differentiable and analytic
models, demonstrating that linear models do not possess an LLR-guarantee when
overparameterized. (ii) Employing the Embedding Principle (Zhang et al.,
2021b, 2022), we derive upper bounds for the optimistic sample sizes—defined
as the smallest sample sizes that ensure an LLR guarantee—for general DNNs.
These bounds affirm the LLR-guarantee at overparameterization for all
functions expressible by narrower DNNs. (iii) We pinpoint the exact optimistic
sample sizes for two-layer fully-connected and convolutional tanh neural
networks, which meet their respective upper bounds, thereby illustrating the
exactitude of our upper bounds.

##  2 Related works

In our research, we introduce the concept of optimistic sample size, which
quantifies the minimum number of training samples necessary to recover a
target function under a best-possible condition. This approach diverges
significantly from traditional sample complexity, which typically estimates
the sample requirement for achieving a specified performance level in the
worst-case scenarios (Shalev-Shwartz and Ben-David, 2014). Recognizing that
DNNs often perform substantially better in practice than theoretical worst-
case predictions suggest (Zhang et al., 2017, 2021a), our LLR analysis
pioneers a framework for estimating sample sizes under the best-possible
conditions. Furthermore, our empirical findings reveal that the practical
performance of a finely-tuned DNN can approach this optimistic threshold, even
in scenarios of substantial overparameterization. Moreover, as demonstrated in
Zhang and Xu (2024), techniques such as dropout can further enhance the
network’s performance to recover target functions.

Our theoretical LLR framework, which is predicated on the linearization of
DNNs, stands in stark contrast to linear analyses based on the NTK/lazy
training/linear regime (Jacot et al., 2018; Arora et al., 2019; Chizat et al.,
2019; Luo et al., 2021). The main differences are as follows: (i) NTK analysis
linearizes around a random initial point, whereas LLR analysis considers
linearization around a target point, i.e., a global minimizer with zero
generalization error. (ii) NTK pertains to the linear training behavior of
DNNs with large initial weights, whereas the optimistic sample sizes from LLR
analysis are empirically linked to the performance of nonlinear training
dynamics exhibited at small initializations. According to the phase diagrams
in Refs. (Luo et al., 2021; Zhou et al., 2022), NTK analysis corresponds to
the linear regimes, while our LLR results associate to the condensed regimes,
where nonlinear condensation dynamics are instrumental in achieving near-
optimism performance.

The discovery of the embedding principle (Zhang et al., 2021b, 2022; Fukumizu
et al., 2019; Simsek et al., 2021; Bai et al., 2022) has shed light on the
analysis of critical points within the loss landscapes of DNNs and has forged
connections between the loss landscapes of networks of varying widths.
Notably, Zhang et al. (2022) introduces a comprehensive suite of critical
embedding operators that map the parameter space of a narrower DNN to that of
a wider one while preserving both the output function and the criticality of
the network. This powerful analytical tool further illuminates the
hierarchical model rank structure inherent in DNNs. Leveraging these critical
embeddings, which inherently maintain the model rank, we derive in this work
an upper bound for the optimistic sample size applicable to general DNNs.

##  3 Theory of local linear recovery

###  3.1 Assumptions and definitions

######  Assumption.

(i) We consider differentiable (w.r.t. both inputs and parameters) models with
$1$-d output
$f_{\bm{\theta}}(\cdot)=f(\cdot;\bm{\theta}):\mathbb{R}^{d}\times\mathbb{R}^{M}\to\mathbb{R}$.
(ii) We consider target functions $f^{*}$ expressible by the model
$f_{\bm{\theta}}$, i.e.,
$f^{*}\in\mathcal{F}:=\\{f_{\bm{\theta}}(\cdot)|\bm{\theta}\in\mathbb{R}^{M}\\}$.
And the training data
$S=\\{(\bm{x}_{i}\in\mathbb{R}^{d},y_{i}=f^{*}(\bm{x}_{i})\in\mathbb{R})\\}_{i=1}^{n}$
is sampled from $f^{*}$.
(iii) The loss function $\ell(\cdot,\cdot)$ is a continuously differentiable
distance function and the empirical loss
$L_{S}(\bm{\theta})=\mathbb{E}_{S}\ell(f_{\bm{\theta}}(\bm{x}),y)=\frac{1}{n}\sum_{i=1}^{n}\ell(f(\bm{x}_{i};\bm{\theta}),y_{i})$.

Under the above general assumptions, this work focuses on the recovery of
target function $f^{*}$ for the following regression problem when $n\leqslant
M$:

$\mathrm{min}_{\bm{\theta}\in\mathbb{R}^{M}}\frac{1}{n}\sum_{i=1}^{n}\ell(f_{\bm{\theta}}(\bm{x}_{i}),f^{*}(\bm{x}_{i})).$
(1)

We say $f^{*}$ is successfully recovered when the solution $\bm{\theta}^{*}$
obtained by an algorithm satisfies $f_{\bm{\theta}^{*}}=f^{*}$. For
convenience, we define the target set $\mathcal{M}_{f^{*}}$ as follows, by
which $f^{*}$ is recovered when $\bm{\theta}^{*}\in\mathcal{M}_{f^{*}}$.

######  Definition 1 (target set).

Suppose we have a model
$f_{\bm{\theta}}(\cdot)=f(\cdot;\bm{\theta}):\mathbb{R}^{d}\times\mathbb{R}^{M}\to\mathbb{R}$
with model function space
$\mathcal{F}=\\{f_{\bm{\theta}}(\cdot)|\bm{\theta}\in\mathbb{R}^{M}\\}$. For
any target function $f^{\prime}\in\mathcal{F}$, the target set
$\mathcal{M}_{f^{\prime}}:=\\{\bm{\theta}|f(\cdot;\bm{\theta})=f^{\prime}\\}$.

We note that analyzing the recovery of $f^{*}$ at overparameterization through
global training presents significant difficulties due to two primary
challenges: (i) the optimization challenge, where it remains uncertain whether
the training process can avoid local minima and saddle points to converge to a
global minimum (Sun et al., 2020); (ii) the challenge of infinite solutions,
where the target set $\mathcal{M}_{f^{*}}$ is embedded within an approximately
$(M-n)$-dimensional manifold of global minima with complex geometry (Cooper,
2021; Zhang et al., 2023a), making it difficult to ascertain if global
training can precisely reach $\mathcal{M}_{f^{*}}$. To bypass these obstacles,
we introduce a more theoretically tractable variant of recovery as follows.

######  Definition 2 (local linear recovery (LLR) guarantee).

Suppose we have a differentiable model $f_{\bm{\theta}}(\cdot)$ with $M$
parameters, a target function
$f^{*}\in\mathcal{F}:=\\{f_{\bm{\theta}}(\cdot)\\}$ and training data
$S=\\{(\bm{x}_{i},f^{*}(\bm{x}_{i}))\\}_{i=1}^{n}$.
(a) LLR-guarantee: We say $f^{*}$ has local linear recovery (LLR) guarantee
(by model $f_{\bm{\theta}}$ from $S$) if the following condition holds: There
exists $\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$ such that

$f^{*}=\mathrm{argmin}_{g\in\widetilde{\mathcal{T}}_{\bm{\theta}^{\prime}}}\frac{1}{n}\sum_{i=1}^{n}\ell(g(\bm{x}_{i}),f^{*}(\bm{x}_{i})),$
(2)

where
$\widetilde{\mathcal{T}}_{\bm{\theta}^{\prime}}=\\{f(\cdot;\bm{\theta}^{\prime})+\bm{a}^{\text{T}}\nabla_{\bm{\theta}}f(\cdot;\bm{\theta}^{\prime})|\bm{a}\in\mathbb{R}^{M}\\}$
is the tangent function hyperplane at $\bm{\theta}^{\prime}$. If the above
condition holds, we say $f^{*}$ has LLR-guarantee at $\bm{\theta}^{\prime}$
(by model $f_{\bm{\theta}}$ from $S$).
(b) $n$-sample LLR-guarantee: We say a function $f^{*}\in\mathcal{F}$ has
$n$-sample LLR-guarantee if there exists a $n$-sample dataset
$S=\\{(\bm{x}_{i}\in\mathbb{R}^{d},f^{*}(\bm{x}_{i})\in\mathbb{R})\\}_{i=1}^{n}$
such that $f^{*}$ has LLR-guarantee. Furthermore, if $n<M$, then we say
$f^{*}$ has LLR-guarantee at overparameterization.
(c) $n$-sample LLR-guarantee a.e.: We say a function $f^{*}\in\mathcal{F}$ has
$n$-sample LLR-guarantee a.e. (almost everywhere) if the following condition
holds: For inputs $X=[\bm{x}_{1},\cdots,\bm{x}_{n}]\in\mathbb{R}^{d\times n}$
a.e. with respect to $\mathcal{L}^{d\times m}$ Lebesgue measure, $f^{*}$ has
LLR-guarantee from $S=\\{(\bm{x}_{i},f^{*}(\bm{x}_{i}))\\}_{i=1}^{n}$.

######  Remark 3 (LLR-guarantee vs. LLR-guarantee a.e.).

(i) Although $n$-sample LLR-guarantee seems to be significantly weaker than
$n$-sample LLR-guarantee a.e., we will show later that any $n$-sample LLR-
guarantee automatically upgrades to $n$-sample LLR-guarantee a.e. for analytic
models, e.g., neural networks with tanh, sigmoid or GELU activation. For the
pursuit of generality, we mainly focus on the $n$-sample LLR-guarantee in this
work. (ii) In general, $n$-sample LLR-guarantee informs the potential of
recovering the target from $n$ samples in practice, whereas no $n$-sample LLR-
guarantee is a strong indication that $n$ samples are not sufficient to
recover the target.

######  Proposition 1.

Suppose we have a differentiable model $f_{\bm{\theta}}(\cdot)$ with $M$
parameters. For any target function $f^{*}\in\mathcal{F}$, if it has
$n$-sample LLR-guarantee, then it has $n^{\prime}$-sample LLR-guarantee for
any $n^{\prime}\geqslant n$.

###### Proof.

When $f^{*}$ has $n$-sample LLR-guarantee, there exists
$S=\\{(\bm{x}_{i},f^{*}(\bm{x}_{i}))\\}_{i=1}^{n}$ and
$\bm{\theta}^{*}\in\mathcal{M}_{f^{*}}$ such that the solution set

$\phi_{S}^{*}:=\mathrm{argmin}_{f\in\widetilde{\mathcal{T}}_{\bm{\theta}^{*}}}\mathbb{E}_{(\bm{x},y)\in
S}\ell(f(\bm{x}),y)=\\{f^{*}\\}.$

For
$S^{\prime}=S\cup\\{(\bm{x}^{\prime}_{i},f^{*}(\bm{x}^{\prime}_{i}))\\}_{i=n+1}^{n^{\prime}}$
with any $\bm{x}^{\prime}_{i}\in\mathbb{R}^{M}$ for $i\in[n+1:n^{\prime}]$,
let

$\phi_{S^{\prime}}^{*}:=\mathrm{argmin}_{f\in\widetilde{\mathcal{T}}_{\bm{\theta}^{*}}}\mathbb{E}_{(\bm{x},y)\in
S^{\prime}}\ell(f(\bm{x}),y).$

Obvious, $f^{*}\in\phi_{S^{\prime}}^{*}$, by which the empirical loss attains
$0$ on $S^{\prime}$. Then, any global minimizer $f\in\phi_{S^{\prime}}^{*}$
also attains $0$ empirical loss on $S^{\prime}$, thus $0$ empirical loss on
$S$. Therefore, $\phi_{S^{\prime}}^{*}\subset\phi_{S}^{*}=\\{f^{*}\\}$, which
yields

$\phi_{S^{\prime}}^{*}=\phi_{S}^{*}=\\{f^{*}\\}.$

By Definition 2, $f^{*}$ has $n^{\prime}$-sample LLR-guarantee. ∎

Proposition. 1 signifies the importance of understanding the minimum sample
size with LLR-guarantee for a target function, which is rigorously defined
below as an optimistic sample size.

######  Definition 4 (optimistic sample size).

Suppose we have a differentiable model $f_{\bm{\theta}}(\cdot)$. For any
function $f^{*}\in\mathcal{F}$, if $f^{*}$ has LLR-guarantee from $n$ samples
but not $n-1$ samples, then its optimistic sample size

$O_{f_{\bm{\theta}}}(f^{*})=n.$

###  3.2 General LLR theory

In this section, we present the theoretical results of LLR for the regression
problem of general differentiable models. In particular, we establish the
quantitative relation between the LLR-guarantee and the model rank, by which
estimating the optimistic sample size of a target converts to an estimation of
its model rank.

######  Definition 5 (model rank).

Given any differentiable (in parameters) model $f_{\bm{\theta}}$, the model
rank for any $\bm{\theta}^{*}\in\mathbb{R}^{M}$ is defined as

$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*}):=\textnormal{dim}\left(\textnormal{span}\left\\{\partial_{\theta_{i}}f(\cdot;\bm{\theta}^{*})\right\\}_{i=1}^{M}\right),$
(3)

where
$\textnormal{span}\left\\{\phi_{i}(\cdot)\right\\}_{i=1}^{M}=\\{\sum_{i=1}^{M}a_{i}\phi_{i}(\cdot)|a_{1},\cdots,a_{M}\in\mathbb{R}\\}$
and $\textnormal{dim}(\cdot)$ returns the dimension of a linear function
space.

######  Definition 6 (empirical tangent matrix and empirical model rank).

Given any differentiable model $f_{\bm{\theta}}$ and training data
$S=\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{n}$, at any parameter point
$\bm{\theta}^{*}$,
$\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})=[\nabla_{\bm{\theta}}f(\bm{x}_{1};\bm{\theta}^{*}),\cdots,\nabla_{\bm{\theta}}f(\bm{x}_{n};\bm{\theta}^{*})]$
is referred to as the empirical tangent matrix. Then the empirical model rank
is defined as follows

$\textnormal{rank}_{S}(\bm{\theta}^{*})=\textnormal{rank}(\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})).$

######  Lemma 7 (LLR condition).

$f^{*}$ has local linear recovery guarantee at $\bm{\theta}^{*}$ by model
$f_{\bm{\theta}}$ from $S$ if and only if
$\textnormal{rank}_{S}(\bm{\theta}^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})$.

###### Proof.

Define

$\tilde{R}_{S}(\bm{a})=\frac{1}{n}\sum_{i=1}^{n}\ell(f(\bm{x}_{i},\bm{\theta}^{*})+\bm{a}^{\text{T}}\nabla_{\bm{\theta}}f(\bm{x}_{i};\bm{\theta}^{*}),f^{*}(\bm{x}_{i})).$

First assume that $f^{*}$ has LLR guarantee at $\bm{\theta}^{*}$ by model
$f_{\bm{\theta}}$ from $S$. Then $f(\cdot;\bm{\theta}^{*})=f^{*}$ by
Definition 2, and this function is unique. This uniqueness implies that for
any $\bm{a}\in\ker\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})$ we must have

$f(\cdot;\bm{\theta}^{*})+\bm{a}^{\text{T}}\nabla_{\bm{\theta}}f(\cdot;\bm{\theta}^{*})=f^{*}.$

Equivalently, $\bm{a}\in\ker\nabla_{\bm{\theta}}f(\cdot;\bm{\theta}^{*})$.
This shows
$\ker\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})\subseteq\ker\nabla_{\bm{\theta}}f(\cdot;\bm{\theta}^{*})$.
But clearly
$\ker\nabla_{\bm{\theta}}f(\cdot;\bm{\theta}^{*})\subseteq\ker\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})$,
so the two kernels are equal. It follows that

$\textnormal{rank}_{S}(\bm{\theta}^{*})=\textnormal{rank}\left(\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})\right)=\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})$

Conversely, assume that
$\textnormal{rank}_{S}(\bm{\theta}^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})$.
Then, similar as above, we have
$\ker\nabla_{\bm{\theta}}f(\cdot;\bm{\theta}^{*})=\ker\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})$.
Because $\ell$ is a distance function, for any $\bm{a}\in\mathbb{R}^{M}$ with
$\tilde{R}_{S}(\bm{a})=R_{S}(\bm{\theta}^{*})=0$, we must have

$\bm{a}^{\text{T}}\nabla_{\bm{\theta}}f(\bm{x}_{i};\bm{\theta}^{*})=0,\quad\forall\,1\leqslant
i\leqslant n.$

Equivalently, $\bm{a}\in\ker\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})$ and
thus $\bm{a}^{\text{T}}f(\cdot;\bm{\theta}^{*})=0$. This shows

$f^{*}=f(\cdot;\bm{\theta}^{*})=\mathrm{argmin}_{g\in\widetilde{\mathcal{T}}_{\bm{\theta}^{\prime}}}\frac{1}{n}\sum_{i=1}^{n}\ell(g(\bm{x}_{i}),f^{*}(\bm{x}_{i}))$

is well-defined, i.e., $f^{*}$ has LLR guarantee at $\bm{\theta}^{*}$.

∎

######  Corollary 1 (phase transition of LLR-guarantee at a target point).

For any $\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$, if training data size
$n<\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$, $f^{*}$ has no
local linear recovery guarantee at $\bm{\theta}^{\prime}$. Otherwise, if
$n\geqslant\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$, $f^{*}$
has $n$-sample LLR-guarantee, i.e., there exits an $n$-sample dataset
$S^{\prime}=\\{(\bm{x}_{i},f^{*}(\bm{x}_{i}))\\}_{i=1}^{n}$ such that $f^{*}$
has local linear recovery guarantee at $\bm{\theta}^{\prime}$.

###### Proof.

For $n<\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$,
$\textnormal{rank}_{S}(\bm{\theta}^{\prime})\leqslant
n<\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$. By Lemma 7,
$f^{*}$ has no local linear recovery guarantee at $\bm{\theta}^{\prime}$. On
the other hand, for
$n\geqslant\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$, we
claim that there exist $\bm{X}=(\bm{x}_{1},...,\bm{x}_{n})$ with
$\textnormal{rank}\left(\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})\right)=\textnormal{rank}_{f_{\bm{\theta}}}(\cdot;\bm{\theta}^{\prime})$.
Suppose this is not true. Let

$M^{\prime}=\max_{\bm{X}\in\mathbb{R}^{d\times
n}}\textnormal{rank}\left(\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{\prime})\right)$

and let $\bm{x}_{1},...,\bm{x}_{M^{\prime}}$ be such that

$\textnormal{rank}\left[\nabla_{\bm{\theta}}f((\bm{x}_{1},...,\bm{x}_{M^{\prime}});\bm{\theta}^{\prime})\right]=M^{\prime}.$

So in particular
$M^{\prime}<\textnormal{rank}_{f_{\bm{\theta}}}(\cdot;\bm{\theta}^{\prime})\leqslant
M$. Given $a\in\mathbb{R}^{M}$ such that
$\nabla_{\bm{\theta}}f(\bm{x}_{i};\bm{\theta})=0$ for all $1\leq i\leq
M^{\prime}$, we must have
$a\in\ker\nabla_{\bm{\theta}}f(\bm{\theta}^{\prime};\cdot)$. Therefore,

$\ker\nabla_{\bm{\theta}}f(\bm{\theta}^{\prime};\cdot)\subseteq\ker\nabla_{\bm{\theta}}f((\bm{x}_{1},...,\bm{x}_{M^{\prime}});\bm{\theta}^{\prime})\subseteq\ker\nabla_{\bm{\theta}}f(\bm{\theta}^{\prime};\cdot).$

This means

$\dim\ker\nabla_{\bm{\theta}}f(\bm{\theta}^{\prime};\cdot)=\dim\ker\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{\prime})=M-M^{\prime}$

and thus
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})=M^{\prime}$, a
contradiction. So there must exist $\bm{X}=(\bm{x}_{1},...,\bm{x}_{n})$ with
$\textnormal{rank}\left(\nabla_{\bm{\theta}}f(\bm{X};\bm{\theta}^{*})\right)=\textnormal{rank}_{f_{\bm{\theta}}}(\cdot;\bm{\theta}^{\prime})$.
By Lemma 7, $f^{*}$ has $n$-sample guarantee.

∎

We address above the LLR-guarantee at a target point. In the following, we
further address the LLR-guarantee for recovering a target function.

######  Definition 8 (model rank for function).

The model rank for any function $f^{*}\in\mathcal{F}$ is defined as

$\textnormal{rank}_{f_{\bm{\theta}}}(f^{*}):=\min_{\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}}\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime}).$
(4)

######  Theorem 1 (optimistic sample size estimate).

Suppose we have a differentiable model $f_{\bm{\theta}}$. For any function
$f^{*}\in\mathcal{F}$, we have

$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*}).$

###### Proof.

When the sample size $n<\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})$, for any
$\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$,
$n<\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$. By Corollary 1,
$f^{*}$ has no LLR-guarantee at $\bm{\theta}^{\prime}$. Therefore, $f^{*}$ has
no $n$-sample LLR-guarantee. When the sample size
$n\geqslant\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})$, there exists
$\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$, such that
$n\geqslant\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$.
By Corollary 1, $f^{*}$ has $n$-sample LLR-guarantee. By Definition 4, we have

$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*}).$

∎

The subsequent two corollaries provide a rigorous formulation of two intuitive
assertions about the best-possible cases of regression problem (1): (i) $M$
samples are sufficient for recovery; (ii) linear models generally cannot be
recovered at overparameterization.

######  Corollary 2 (generic upper bound for optimistic sample size).

Suppose we have a differentiable model $f_{\bm{\theta}}$. For any function
$f^{*}\in\mathcal{F}$, we have

$O_{f_{\bm{\theta}}}(f^{*})\leqslant M.$

###### Proof.

Because $\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta})\leqslant M$ for any
$\bm{\theta}\in\mathbb{R}^{M}$,
$\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})\leqslant M$ for any
$f^{*}\in\mathcal{F}$. Therefore, by Theorem 1,
$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})\leqslant
M$. ∎

######  Corollary 3 (no LLR-guarantee for linear models at
overparameterization).

For a linear model
$f_{\bm{\theta}}(\bm{x})=\sum_{i=1}^{M}\theta_{i}\phi_{i}(\bm{x})$ with
$\bm{\theta}=[\theta_{1},\cdots,\theta_{M}]^{\text{T}}$, if its basis
functions are linearly independent, i.e.,
$\textnormal{dim}(\textnormal{span}\\{\phi_{i}(\cdot)\\}_{i=1}^{M})=M$, then

$O_{f_{\bm{\theta}}}(f^{*})\equiv M,$

i.e., none of the functions in the model function space $\mathcal{F}$ has LLR-
guarantee at overparameterization.

###### Proof.

For any $\bm{\theta}^{*}\in\mathbb{R}^{M}$, we have

$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})=\textnormal{dim}\left(\textnormal{span}\left\\{\partial_{\theta_{i}}f(\cdot;\bm{\theta}^{*})\right\\}_{i=1}^{M}\right)=\textnormal{dim}\left(\textnormal{span}\left\\{\phi_{i}(\bm{x})\right\\}_{i=1}^{M}\right)=M.$

Therefore,
$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})=M$ for
any $f^{*}\in\mathcal{F}$. ∎

###  3.3 LLR-guarantee for analytic models

In this subsection, we exploit the characteristics of analytic functions to
enhance the LLR guarantee, extending it to an almost everywhere (a.e.)
guarantee for analytic models.

######  Lemma 9.

Given $m$ linearly independent analytic functions
$\phi_{1}(\bm{x}),\cdots,\phi_{m}(\bm{x})$ with
$\phi_{i}:\mathbb{R}^{d}\to\mathbb{R}$ for all $i\in[m]$,
$\textnormal{rank}(\bm{\Phi}(\bm{X}))=m$ almost everywhere (a.e.) with respect
to $\mathcal{L}^{d\times m}$ Lebesgue measure, where

$\bm{\Phi}(\bm{X}):=\left[\begin{matrix}\phi_{1}(\bm{x}_{1})&...&\phi_{m}(\bm{x}_{1})\\\
\vdots&\ddots&\vdots\\\
\phi_{1}(\bm{x}_{m})&...&\phi_{m}(\bm{x}_{m})\end{matrix}\right].$

###### Proof.

Clearly, $\det(\bm{\Phi}(\cdot)):\mathbb{R}^{d\times m}\to\mathbb{R}$ is an
analytic function over $\mathbb{R}^{d\times m}$. In addition, because
$\\{\phi_{i}\\}_{i=1}^{m}$ are linearly independent, there exists
$\bm{X}\in\mathbb{R}^{d\times m}$ such that $\det(\bm{\Phi}(\cdot))\neq 0$,
i.e., $\det(\bm{\Phi}(\cdot))$ is not constant zero. By the property of real
analytic function (Mityagin, 2020), $\textnormal{rank}(\bm{\Phi}(\bm{X}))=m$
a.e. with respect to $\mathcal{L}^{d\times m}$ Lebesgue measure. ∎

######  Corollary 4.

Given $m$ analytic functions $\phi_{1}(\bm{x}),\cdots,\phi_{m}(\bm{x})$ with
$\phi_{i}:\mathbb{R}^{d}\to\mathbb{R}$ for all $i\in[m]$ and
$\textnormal{dim}(\textnormal{span}(\\{\phi_{i}(\cdot)\\}_{i=1}^{m}))=r$,
$\textnormal{rank}(\bm{\Phi}(\bm{X}))=\min\\{n,r\\}$ a.e. with respect to
$\mathcal{L}^{d\times n}$ Lebesgue measure.

###### Proof.

It is obvious that
$\textnormal{rank}(\bm{\Phi}(\bm{X}))\leqslant\min\\{n,r\\}$. For $n\leqslant
r$, we can always pick $n$ independent functions from
$\\{\phi_{i}(\cdot)\\}_{i=1}^{m}$. By Lemma 9, $\bm{\Phi}(\bm{X})$ has a
rank-$n$ submatrix of $\bm{\Phi}(\bm{X})$ a.e. with respect to Lebesgue
measure. For $n>r$, we have that the submatrix of the first $r$ rows of
$\bm{\Phi}(\bm{X})$ has rank $r$ a.e. by Lemma 9. Therefore,
$\textnormal{rank}(\bm{\Phi}(\bm{X}))=\min\\{n,r\\}$ a.e. with respect to
$\mathcal{L}^{d\times n}$ Lebesgue measure. ∎

######  Theorem 2 (LLR-guarantee a.e. for analytic models).

Given any analytic model $f_{\bm{\theta}}$ (w.r.t. both inputs and
parameters), if target function $f^{*}\in\mathcal{F}$ has $n$-sample LLR-
guarantee, then $f^{*}$ has $n$-sample LLR-guarantee a.e.

###### Proof.

If target function $f^{*}\in\mathcal{F}$ has $n$-sample LLR-guarantee, by
Definition 4, $n\geqslant O_{f_{\bm{\theta}}}(f^{*})$. In addition, there
exists $\bm{\theta}^{*}\in\mathcal{M}_{f^{*}}$ such that
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})=O_{f_{\bm{\theta}}}(f^{*})$.
Then by Corollary 4, for $\bm{X}=[\bm{x}_{1},\cdots,\bm{x}_{n}]$ a.e. with
respect to $\mathcal{L}^{d\times n}$ Lebesgue measure with dataset
$S=\\{(\bm{x}_{i},f^{*}(\bm{x}_{i}))\\}_{i=1}^{n}$,
$\textnormal{rank}_{S}(\bm{\theta}^{*})=\min\\{\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*}),n\\}=\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})$.
By the LLR condition Lemma 7, $f^{*}$ has $n$-sample LLR-guarantee a.e. ∎

##  4 Upper bounds of optimistic sample sizes for DNNs

Building on the LLR theory, the task of estimating optimistic sample sizes for
target functions necessitates the elucidation of the model rank across the
space of functions. This task is notably challenging, particularly for DNNs
with three or more layers, due to the complexity inherent in disentangling the
linear dependencies among the compositional tangent functions. Fortunately, we
observe that the critical embedding operators introduced in Refs. (Zhang et
al., 2021b, 2022) can preserve the tangent function space and the model rank
when transitioning from a parameter point in a narrower DNN to one in a wider
DNN. This observation allows us to constrain the model rank of a target
function within a wide DNN by referencing the smallest DNN capable of
representing it regardless of the depth. The formal mathematical exposition of
these results is provided below.

###  4.1 DNNs and the Embedding Principle

In this subsection, we briefly recapitulate the key elements of Embedding
Principle in Refs. (Zhang et al., 2021b, 2022). Consider $L$-layer ($L\geq 2$)
fully-connected DNNs with a general differentiable activation function. We
regard the input as the $0$-th layer and the output as the $L$-th layer. Let
$m_{l}$ be the number of neurons in the $l$-th layer. In particular, $m_{0}=d$
and $m_{L}=d^{\prime}$. For any $i,k\in\mathbb{N}$ and $i<k$, we denote
$[i:k]=\\{i,i+1,\ldots,k\\}$. In particular, we denote
$[k]:=\\{1,2,\ldots,k\\}$. Given weights $W^{[l]}\in\mathbb{R}^{m_{l}\times
m_{l-1}}$ and bias $b^{[l]}\in\mathbb{R}^{m_{l}}$ for $l\in[L]$, we define the
collection of parameters $\bm{\theta}$ as a $2L$-tuple (an ordered list of
$2L$ elements) whose elements are matrices or vectors

$\bm{\theta}=\Big{(}\bm{\theta}|_{1},\cdots,\bm{\theta}|_{L}\Big{)}=\Big{(}\bm{W}^{[1]},\bm{b}^{[1]},\ldots,\bm{W}^{[L]},\bm{b}^{[L]}\Big{)}.$
(5)

where the $l$-th layer parameters of $\bm{\theta}$ is the ordered pair
$\bm{\theta}|_{l}=\Big{(}\bm{W}^{[l]},\bm{b}^{[l]}\Big{)},\quad l\in[L]$. We
may misuse the notation and identify $\bm{\theta}$ with its vectorization
$\mathrm{vec}(\bm{\theta})\in\mathbb{R}^{M}$ with
$M=\sum_{l=0}^{L-1}(m_{l}+1)m_{l+1}$.

Given $\bm{\theta}\in\mathbb{R}^{M}$, the neural network function
$\bm{f}_{\bm{\theta}}(\cdot)$ is defined recursively. First, we write
$\bm{f}^{[0]}_{\bm{\theta}}(\bm{x})=\bm{x}$ for all $\bm{x}\in\mathbb{R}^{d}$.
Then for $l\in[L-1]$, $\bm{f}^{[l]}_{\bm{\theta}}$ is defined recursively as
$\bm{f}^{[l]}_{\bm{\theta}}(\bm{x})=\sigma(\bm{W}^{[l]}\bm{f}^{[l-1]}_{\bm{\theta}}(\bm{x})+\bm{b}^{[l]})$.
Finally, we denote

$\bm{f}_{\bm{\theta}}(\bm{x})=\bm{f}(\bm{x},\bm{\theta})=\bm{f}^{[L]}_{\bm{\theta}}(\bm{x})=\bm{W}^{[L]}\bm{f}^{[L-1]}_{\bm{\theta}}(\bm{x})+\bm{b}^{[L]}.$
(6)

For notational simplicity, we may drop the subscript $\bm{\theta}$ in
$\bm{f}^{[l]}_{\bm{\theta}}$, $l\in[0:L]$.

We formally define the notion of wider/narrower as follows.

######  Definition 10 (Wider/narrower DNN).

We write $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ for a fully-connected neural
network with width $(m_{0},\ldots,m_{L})$. Given two $L$-layer ($L\geq 2$)
fully-connected neural networks $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}^{\prime}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$, if
$m^{\prime}_{0}=m_{0}$, $m^{\prime}_{L}=m_{L}$, and for any $l\in[L-1]$,
$m^{\prime}_{l}\geq m_{l}$ and $K=\sum_{l=1}^{L-1}(m^{\prime}_{l}-m_{l})>0$,
then we say that $\mathrm{NN}^{\prime}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$ is
wider or $K$-neuron wider than $\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ and
$\mathrm{NN}(\\{m_{l}\\}_{l=0}^{L})$ is narrower or $K$-neuron narrower than
$\mathrm{NN}^{\prime}(\\{m^{\prime}_{l}\\}_{l=0}^{L})$.

######  Theorem 3 (Embedding Principle, Theorem 4.2 in Ref. (Zhang et al.,
2022)).

Given any NN and any $K$-neuron wider NN, there exists a $K$-step composition
embedding $\mathcal{P}$ satisfying that: For any given data $S$, loss function
$\ell(\cdot,\cdot)$, activation function $\sigma(\cdot)$, given any critical
point $\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}$ of the narrower NN,
$\bm{\theta}^{\textnormal{c}}_{\textnormal{wide}}:=\mathcal{P}(\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}})$
is still a critical point of the $K$-neuron wider NN with the same output
function, i.e.,
$\bm{f}_{\bm{\theta}^{\textnormal{c}}_{\textnormal{narr}}}=\bm{f}_{\bm{\theta}^{\textnormal{c}}_{\textnormal{wide}}}$.

Figure 1: (Figure 2 in Zhang et al. (2021b)) Illustration of one-step
splitting embedding. The black neuron in the left network is split into the
blue and purple neurons in the right network. The red (green) output weight of
the black neuron in the left net is splitted into two red (green) weights in
the right net with ratio $\alpha$ and $(1-\alpha)$, respectively.

The cornerstone of the Embedding Principle’s proof lies in constructing a
series of critical embeddings that map any given DNN to a wider one. Figure 1
illustrates a typical type of critical embedding, specifically the ’splitting’
embedding. This process involves dividing a single neuron into two, while
simultaneously preserving both the neural network’s output function and its
criticality. It is readily apparent that this splitting embedding can be
seamlessly adapted to Convolutional Neural Networks (CNNs) and Residual
Networks (ResNets), suggesting that the Embedding Principle is applicable to
these architectures as well. Consequently, it is reasonable to infer that all
subsequent results that depend on the presence of critical embeddings for
fully-connected neural networks can be extended to CNNs and ResNets.
Additionally, Zhang et al. (2022) describes other varieties of critical
embeddings, such as the null embedding and the general compatible embedding.

###  4.2 Upper bounding optimistic sample size via critical mappings

In this subsection, we first provide a general definition of critical
mappings, by which the previously proposed critical embeddings (see Zhang et
al. (2022) Definition 4.2 for details) are special cases. Then, we prove Lemma
12, showing that uncovering critical mappings is an important means for
obtaining an upper bound estimate of the optimistic sample size. This general
result combined with the embedding principle of DNNs directly provides an
upper bound estimate of optimistic sample sizes for general DNNs in Theorem 4.
We also illustrate the upper bounds for a general depth-$L$ DNN without bias
terms in Table. 1.

######  Definition 11 (critical mapping).

Given differentiable model A $f_{\bm{\theta}_{A}}=f(\cdot;\bm{\theta}_{A})$
with $\bm{\theta}_{A}\in\mathbb{R}^{M_{A}}$ and differentiable model B
$g_{\bm{\theta}_{B}}=g(\cdot;\bm{\theta}_{B})$ with
$\bm{\theta}_{B}\in\mathbb{R}^{M_{B}}$,
$\mathcal{P}:\mathbb{R}^{M_{A}}\to\mathbb{R}^{M_{B}}$ is a critical mapping
from model $A$ to $B$ if given any $\bm{\theta}\in\mathbb{R}^{M_{A}}$, we have
(i) output preserving: $f_{\bm{\theta}}=g_{\mathcal{P}(\bm{\theta})}$;
(ii) criticality preserving: for any data
$S=\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{n}$ with mean-squared error (MSE) empirical
risk function $R_{S}(h)=\frac{1}{2}\sum_{i=1}^{n}(h(\bm{x}_{i})-y_{i})^{2}$,
if $\nabla_{\bm{\theta}}R_{S}(f_{\bm{\theta}})=\bm{0}$, then
$\nabla_{\bm{\theta}}R_{S}(g_{\mathcal{P}(\bm{\theta})})=\bm{0}$.

######  Lemma 12 (upper bound of optimistic sample size).

Given two models $f_{\bm{\theta}_{A}}=f(\cdot;\bm{\theta}_{A})$ with
$\bm{\theta}_{A}\in\mathbb{R}^{M_{A}}$ and
$g_{\bm{\theta}_{B}}=g(\cdot;\bm{\theta}_{B})$ with
$\bm{\theta}_{B}\in\mathbb{R}^{M_{B}}$, if there exists a critical mapping
$\mathcal{P}$ from model $A$ to $B$, then the optimistic sample size
$O_{g}(f^{*})\leqslant O_{f}(f^{*})\leqslant M_{A}$ for any
$f^{*}\in\mathcal{F}_{A}$.

######  Remark 1.

If $M_{B}\gg M_{A}$, this upper bound estimate is highly informative,
indicating target recovery capability at heavy overparameterization for model
$B$. Importantly, this lemma establishes the relation between our rank
stratification and previous studies about the critical embedding for the DNN
loss landscape analysis. As a result, the critical embedding intrinsic to the
DNN architecture not only benefits optimization as studied in previous works,
but also profoundly benefits the recovery/generalization performance.

###### Proof.

By Definition 8, for any $f^{*}\in\mathcal{F}_{f}$, there exists
$\bm{\theta}^{*}\in\mathbb{R}^{M_{A}}$ such that
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})$.
Then, $g_{\mathcal{P}(\bm{\theta}^{*})}=f_{\bm{\theta}^{*}}=f^{*}$. Because
$R_{S}(\bm{\theta})=\frac{1}{2}\sum_{i=1}^{n}(f_{\bm{\theta}}(\bm{x}_{i})-y_{i})^{2}$,
we have

$\nabla_{\bm{\theta}}R_{S}(f_{\bm{\theta}^{*}})=\sum_{i=1}^{n}(y_{i}-f^{*}(\bm{x}_{i}))\nabla_{\bm{\theta}^{*}}f_{\bm{\theta}^{*}}(\bm{x}_{i})$

and
$\nabla_{\mathcal{P}(\bm{\theta})}R_{S}(g_{\mathcal{P}(\bm{\theta}^{*})})=\sum_{i=1}^{n}(y_{i}-f^{*}(\bm{x}_{i}))\nabla_{\mathcal{P}(\bm{\theta})}g_{\mathcal{P}(\bm{\theta}^{*})}(\bm{x}_{i})$.
Because $\mathcal{P}$ is criticality preserving for arbitrary data $S$, we
have
$\ker(\nabla_{\bm{\theta}}f_{\bm{\theta}^{*}}(\bm{X}))\subseteq\ker(\nabla_{\mathcal{P}(\bm{\theta})}g_{\mathcal{P}(\bm{\theta}^{*})}(\bm{X}))$
for any $\bm{X}:=[\bm{x}_{1},\cdots,\bm{x}_{n}]$. Here,
$\nabla_{\bm{\theta}}f_{\bm{\theta}^{*}}(\bm{X})=[\nabla_{\bm{\theta}}f_{\bm{\theta}^{*}}(\bm{x}_{1}),\cdots,\nabla_{\bm{\theta}}f_{\bm{\theta}^{*}}(\bm{x}_{n})]$.
Because
$\textnormal{rank}_{S}(\mathcal{P}(\bm{\theta}^{*}))+\textnormal{dim}(\ker(\nabla_{\mathcal{P}(\bm{\theta})}g_{\mathcal{P}(\bm{\theta}^{*})}(\bm{X})))=\textnormal{rank}_{S}(\bm{\theta}^{*})+\textnormal{dim}(\ker(\nabla_{\bm{\theta}}f_{\bm{\theta}^{*}}))=n$,
we have
$\textnormal{rank}_{S}(\mathcal{P}(\bm{\theta}^{*}))\leqslant\textnormal{rank}_{S}(\bm{\theta}^{*})$
for any data $S$ (See Definition 6 for $\textnormal{rank}_{S}(\cdot)$). Taking
the infinite data limit, we obtain
$\textnormal{rank}_{g}(\mathcal{P}(\bm{\theta}^{*}))\leqslant\textnormal{rank}_{f}(\bm{\theta}^{*})\leqslant
M_{A}$. Therefore,
$\textnormal{rank}_{g}(f^{*})\leqslant\textnormal{rank}_{f}(f^{*})\leqslant
M_{A}$ for any $f^{*}\in\mathcal{F}_{f}$. By Theorem 1, $O_{g}(f^{*})\leqslant
O_{f}(f^{*})\leqslant M_{A}$. ∎

As a direct consequence of Lemma 12 and Theorem 3, we obtain the following
theorem.

######  Theorem 4 (upper bound of optimistic sample size for DNNs).

Given any NN with $M_{\textnormal{wide}}$ parameters, for any function in the
function space of a narrower NN with $M_{\textnormal{narr}}$ parameters and
for any $f^{*}\in\mathcal{F}_{\textnormal{narr}}$, we have
$O_{f_{\bm{\theta}_{\textnormal{wide}}}}(f^{*})\leqslant
O_{f_{\bm{\theta}_{\textnormal{narr}}}}(f^{*})\leqslant
M_{\textnormal{narr}}$.

###### Proof.

By Theorem 3, there exists a critical mapping
$\mathcal{P}:\mathbb{R}^{M_{\textnormal{narr}}}\to\mathbb{R}^{M_{\textnormal{wide}}}$
from the narrower NN to the given NN. Then, by Lemma 12,
$O_{f_{\bm{\theta}_{\textnormal{wide}}}}(f^{*})\leqslant
O_{f_{\bm{\theta}_{\textnormal{narr}}}}(f^{*})\leqslant
M_{\textnormal{narr}}$. ∎

It should be noted that while Theorem 4 is proven here for fully-connected
DNNs, the results are readily extendable to CNNs and ResNets by employing
their respective critical embeddings, such as the splitting embedding. Theorem
4 provides a significantly more precise upper bound for optimistic sample
sizes than the generic upper bound presented in Corollary 2, as demonstrated
for an $L$-layer DNN in Table 1. Furthermore, from this theorem, we can infer
two corollaries that tackle two fundamental issues in the theory of deep
learning: (i) the guarantee of LLR at overparameterization for DNNs; and (ii)
the benefits derived from the layer-wise architectural design of DNN models.

model:
$f_{\bm{\theta}}(\bm{x})=\bm{W}^{[L]}\sigma(\cdots\sigma(\bm{W}^{[1]}\bm{x})\cdots)$,
$\bm{W}^{[l]}=\mathbb{R}^{m_{l}\times m_{l-1}}$,$m_{L}=1$, $m_{0}=d$
---
$f^{*}$ | generic bound (Cor. 2) | our bound (Thm. 4)
$\mathcal{F}_{\\{1,1,\cdots,1\\}}$ | $M$ | $d+L-1$
$\vdots$ | ⋮ | $\vdots$
$\mathcal{F}_{\\{m_{i}^{\prime}\\}_{i=1}^{L-1}},1\leq m_{i}^{\prime}\leq m_{i}$ | $M$ | $dm_{1}^{\prime}+m_{1}^{\prime}m_{2}^{\prime}+\cdots+m_{L-2}^{\prime}m_{L-1}^{\prime}+m_{L-1}^{\prime}$
$\vdots$ | ⋮ | $\vdots$
$\mathcal{F}_{\\{m_{i}\\}_{i=1}^{L-1}}$ | $M$ | $M$
Table 1: Upper bound of optimistic sample size for a general $L$-layer fully-
connected DNN with width-${\\{m_{i}\\}_{i=1}^{L-1}}$. For the simplicity of
presentation, we consider the DNN without bias terms. Its total number of
parameters $M=dm_{1}+m_{1}m_{2}+\cdots+m_{L-2}m_{L-1}+m_{L-1}$.
$\mathcal{F}_{\\{m_{i}\\}_{i=1}^{L-1}}$ denotes the function space of the
$L$-layer DNN with width-$\\{m_{i}\\}_{i=1}^{L-1}$ for hidden layers.

######  Corollary 5 (LLR-guarantee at overparameterization for DNNs).

For a DNN model, all functions expressible by any narrower DNNs have LLR-
guarantee at overparameterization.

###### Proof.

We denote $f_{\bm{\theta}_{\textnormal{wide}}}$ as the DNN model and
$M_{\textnormal{wide}}$ as its total parameter size. For any narrower DNN
$f_{\bm{\theta}_{\textnormal{narr}}}$ (see Definition 10), its parameter size
$M_{\textnormal{narr}}<M_{\textnormal{wide}}$. For any
$f^{*}\in\mathcal{F}_{\textnormal{narr}}$, by Theorem 4, the optimistic sample
size $O_{f_{\bm{\theta}_{\textnormal{wide}}}}(f^{*})\leqslant
O_{f_{\bm{\theta}_{\textnormal{narr}}}}(f^{*})\leqslant
M_{\textnormal{narr}}<M_{\textnormal{wide}}$. By the Definition 4 of the
optimistic sample size and Definition 2 of the LLR-guarantee, $f^{*}$ has LLR-
guarantee at overparameterization. ∎

As far as we know, this is the first recovery guarantee at overparametrization
for general DNNs. Though LLR-guarantee is a relatively weak form of recovery
guarantee, it sets a solid ground for further improving the guarantee to
stronger types of recovery, e.g., local or even global recovery. In
particular, we reasonably conjecture that having LLR-guarantee at
overparameterization is a necessary condition for having any stronger type of
recovery guarantee.

######  Corollary 6 (free expressiveness in width).

The optimistic sample size of a target function expressible by any DNN never
increases as the DNN gets wider.

###### Proof.

For any DNN $f_{\bm{\theta}_{\textnormal{narr}}}$, any wider DNN
$f_{\bm{\theta}_{\textnormal{wide}}}$ and a target function
$f^{*}\in\mathcal{F}_{\textnormal{narr}}$, by Theorem 4, the optimistic sample
size $O_{f_{\bm{\theta}_{\textnormal{wide}}}}(f^{*})\leqslant
O_{f_{\bm{\theta}_{\textnormal{narr}}}}(f^{*})$. ∎

Corollary 6 ensures that the potential for recovery in the sense of LLR is not
compromised when employing wider neural networks. This provides theoretical
justification for the application of large DNNs in modeling even simple target
functions.

##  5 Optimistic sample sizes for two-layer tanh NNs

Theorem 4 prompts the investigation of two pertinent questions: (i) the
tightness of the established upper bound, and (ii) the methodology for
determining the precise value of the optimistic sample size. In the subsequent
analysis, we specifically address these issues for two-layer NNs with tanh
activation functions. We provide exact estimates of the optimistic sample
sizes that reach the upper limits as delineated by Theorem 4, with the results
detailed in Table 2. Furthermore, we extend our estimation to the optimistic
sample sizes for two-layer tanh-CNNs, both with and without the implementation
of weight-sharing. A comparative analysis of the optimistic sample sizes for
fully-connected NNs versus CNNs reveals that superfluous connections among
neurons lead to an increase in the optimistic sample size, which in turn
adversely affects the fitting performance in terms of LLR.

model:
$f_{\bm{\theta}}(\bm{x})=\sum_{i=1}^{m}a_{i}\tanh(\bm{w}_{i}^{\text{T}}\bm{x}),\bm{x}\in\mathbb{R}^{d},\bm{\theta}=(a_{i},\bm{w}_{i})_{i=1}^{m}$
---
$f^{*}$ | generic bound (Cor. 2) | upper bound (Thm. 4) |  $O_{f_{\bm{\theta}}}(f^{*})$ (Thm. 5)
$\\{0(\cdot)\\}$ | $0$ | $0$ | $0$
$\mathcal{F}^{\mathrm{NN}}_{1}\backslash\\{0(\cdot)\\}$ | $m(d+1)$ | $d+1$ | $d+1$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
$\mathcal{F}^{\mathrm{NN}}_{k}\backslash\mathcal{F}^{\mathrm{NN}}_{k-1}$ | $m(d+1)$ | $k(d+1)$ | $k(d+1)$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
$\mathcal{F}^{\mathrm{NN}}_{m}\backslash\mathcal{F}^{\mathrm{NN}}_{m-1}$ | $m(d+1)$ | $m(d+1)$ | $m(d+1)$
Table 2: Results of the optimistic sample sizes for two-layer width-$m$ tanh-
NN. Here
$\mathcal{F}^{\mathrm{NN}}_{k}:=\\{\sum_{i=1}^{k}a^{*}_{i}\sigma(\bm{w}_{i}^{*\text{T}}\bm{x})|a_{i}\in\mathbb{R},\bm{w}_{i}\in\mathbb{R}^{d}\\}$
denotes the function space of the width-$k$ tanh-NN.

###  5.1 Theoretical preparation

The exact estimation of model rank hinges on unraveling the linear
dependencies among tangent functions. The subsequent results concerning linear
independence form the bedrock for estimating the model rank in two-layer
neural networks.

######  Proposition 2 (linear independence of neurons).

Let $\sigma:\mathbb{R}\to\mathbb{R}$ be any analytic function such that
$\sigma^{(n_{j})}(0)\neq 0$ for an infinite sequence of distinct indices
$\\{n_{j}\\}_{j=1}^{\infty}$. Given $d\in\mathbb{N}$ and $m$ distinct weights
$\bm{w}_{1},...,\bm{w}_{m}\in\mathbb{R}^{d}\backslash\\{\bm{0}\\}$, such that
$\bm{w}_{k}\neq\pm\bm{w}_{j}$ for all $1\leqslant k<j\leqslant m$. Then
$\\{\sigma(\bm{w}_{i}^{\text{T}}\bm{x}),\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{d}\\}_{i=1}^{m}$
is a linearly independent function set.

###### Proof.

For $x$ sufficiently close to $0\in\mathbb{R}$, we can write
$\sigma(x)=\sum_{j=0}^{\infty}c_{j}x^{j}$, where $c_{j}=\sigma^{(j)}(0)/(j!)$.
Then, $\sigma^{\prime}(x)=\sum_{j=1}^{\infty}jc_{j}x^{j-1}$ . Suppose that the
set is not linearly independent. Choose not-all-zero constants
$\\{\alpha_{i}\\}_{i=1}^{m}$ and $\\{\beta_{i1},...,\beta_{id}\\}_{i=1}^{m}$
such that

$\bm{x}\mapsto\sum_{i=1}^{m}\left(\alpha_{i}\sigma(\bm{w}_{i}^{\text{T}}\bm{x})+\sum_{t=1}^{d}\beta_{it}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{t}\right)$

is a zero map on $\mathbb{R}^{d}$, where $x_{t}$ denotes the $t$-th component
of input. For $k,j,i\in[d]$, define the sets

$\displaystyle A_{k,j}$
$\displaystyle:=\\{\bm{x}\in\mathbb{R}^{d}|\left<\bm{x},\bm{w}_{k}\pm\bm{w}_{j}\right>=0\\}$
$\displaystyle B_{i}$
$\displaystyle:=\\{\bm{x}\in\mathbb{R}^{d}|\left<\bm{x},\bm{w}_{i}\right>=0\\}.$

Clearly, each $A_{k,j}$ is the union of two linear subspaces of dimension
$(d-1)$, while each $B_{i}$ is a possibly empty affine subspace of dimension
$(d-1)$. Thus,

$E:=\left(\cup_{1\leqslant k,j\leqslant
m}A_{k,j}\right)\cup\left(\cup_{i=1}^{d}B_{i}\right)$

has $\mathcal{L}^{d}$ Lebesgue measure zero. Let
$\bm{e}\in\mathbb{R}^{d}\backslash E$. Denote
$p_{i}:=\left<\bm{w}_{i},\bm{e}\right>$ for each $i\in[m]$. Since $p_{i}\neq
p_{j}$ and $p_{i}+p_{j}\neq 0$ whenever $i\neq j$, we can, without loss of
generality, assume that $|p_{1}|>|p_{2}|>...>|p_{m}|>0$. For any sufficiently
small $\varepsilon$ and any $i,t$ we have

$\displaystyle\sigma(\bm{w}_{i}^{\text{T}}(\varepsilon\bm{e}))$
$\displaystyle=\sum_{j=0}^{\infty}(c_{j}p_{i}^{j})\varepsilon^{j},$
$\displaystyle\sigma^{\prime}(\bm{w}_{i}^{\text{T}}(\varepsilon\bm{e}))(\varepsilon\bm{e})_{t}$
$\displaystyle=e_{t}\sum_{j=1}^{\infty}(jc_{j}p_{i}^{j-1})\varepsilon^{j}.$

Thus, for sufficiently small $\varepsilon$,

$\displaystyle\sum_{i=1}^{m}\left(\alpha_{i}\sigma(\bm{w}_{i}^{\text{T}}(\varepsilon\bm{e}))+\sum_{t=1}^{d}\beta_{it}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}(\varepsilon\bm{e}))(\varepsilon\bm{e})_{t}\right)$
$\displaystyle=\left(\sum_{i=1}^{m}\alpha_{i}\right)c_{0}+\sum_{j=1}^{\infty}c_{j}\sum_{i=1}^{m}\left(\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}j\beta_{it}e_{t}\right)p_{i}^{j}\varepsilon^{j}$
(7) $\displaystyle=0.$

We have
$c_{j}\sum_{i=1}^{m}\left(\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}j\beta_{it}e_{t}\right)p_{i}^{j}=0$
for all $j\in\mathbb{N}$. In particular, for any $j\geq 2$, since $n_{j}\geq
1$ and $c_{n_{j}}\neq 0$, we have
$\sum_{i=1}^{m}\left(\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}n_{j}\beta_{it}e_{t}\right)p_{i}^{n_{j}}=0$,
which yields

$\alpha_{1}+\frac{1}{p_{1}}\sum_{t=1}^{d}n_{j}\beta_{1t}e_{t}=-\sum_{i=2}^{m}\left(\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}n_{j}\beta_{it}e_{t}\right)\frac{p_{i}^{n_{j}}}{p_{1}^{n_{j}}}.$

If $m=1$, by taking limits $j\to\infty$, we have
$\alpha_{1}=\sum_{t=1}^{d}\beta_{1t}e_{t}=0$.

Otherwise, since $|p_{1}|>|p_{i}|$ for any $2\leqslant i\leqslant m$, it
follows that, by taking limits $j\to\infty$,

$\lim_{j\rightarrow\infty}\left(\alpha_{1}+\frac{1}{p_{1}}\sum_{t=1}^{d}n_{j}\beta_{1t}e_{t}\right)=\lim_{j\rightarrow\infty}-\sum_{i=2}^{m}\left(\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}n_{j}\beta_{it}e_{t}\right)\frac{p_{i}^{n_{j}}}{p_{1}^{n_{j}}}=0.$

Thus, we also have $\alpha_{1}=\sum_{t=1}^{d}\beta_{1t}e_{t}=0$. For $m>2$, we
may rewrite Eq. (7) as

$\alpha_{2}+\frac{1}{p_{2}}\sum_{t=1}^{d}n_{j}\beta_{2t}e_{t}=-\sum_{i=3}^{m}\left(\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}n_{j}\beta_{it}e_{t}\right)\frac{p_{i}^{n_{j}}}{p_{2}^{n_{j}}}$

for each $j\geq 2$, and take limits as we do above to deduce that
$\alpha_{2}+\frac{1}{p_{2}}\sum_{t=1}^{d}n_{j}\beta_{2t}e_{t}=0$. By repeating
this procedure for at most $m$ times, we conclude that
$\alpha_{i}+\frac{1}{p_{i}}\sum_{t=1}^{d}n_{j}\beta_{it}e_{t}=0$ for all
$i\in[m]$. Then, $\alpha_{i}=\sum_{t=1}^{d}\beta_{it}e_{t}=0$ for any
$i\in[m]$. For each $i$, $\sum_{t=1}^{d}\beta_{it}e_{t}^{\prime}$ is a linear
function of $\bm{e}^{\prime}$ on the open set $\mathbb{R}^{d}\backslash E$
which vanishes on a neighborhood of $\bm{e}$, we must have
$\alpha_{i}=\beta_{it}=0$ for any $i\in[m],t\in[d]$. Therefore,
$\\{\sigma(\bm{w}_{i}^{\text{T}}\bm{x}),\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{d}\\}_{i=1}^{m}$
must be a linearly independent set. ∎

######  Corollary 7 (model rank estimate for two-layer NNs).

Let $\sigma=\tanh$. Given $d\in\mathbb{N}$, weights
$\bm{w}_{1},...,\bm{w}_{m}\in\mathbb{R}^{d}$, $a_{1},...,a_{m}\in\mathbb{R}$,
we have

$\textnormal{dim}(\textnormal{span}\\{\sigma(\bm{w}_{i}^{\text{T}}\bm{x}),a_{i}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{1},...,a_{i}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{d}\\}_{i=1}^{m})=m_{\bm{w}}+m_{a}d,$

where
$m_{\bm{w}}=\frac{1}{2}|\\{\bm{w}_{i},-\bm{w}_{i}|\bm{w}_{i}\neq\bm{0},i\in[m]\\}|$
indicating the number of independent neurons,
$m_{a}=\frac{1}{2}|\\{\bm{w}_{i},-\bm{w}_{i}|\bm{w}_{i}\neq\bm{0},a_{i}\neq
0,i\in[m]\\}|+|\\{\bm{w}_{i}|\bm{w}_{i}=\bm{0},a_{i}\neq 0,i\in[m]\\}|$
indicating the number of independent effective neurons. Here, $|\cdot|$ is the
cardinality of a set, i.e., number of different elements in a set.

###### Proof.

Note that $\sigma=\tanh$ is analytic and $\sigma^{(2n+1)}(0)\neq 0$ for all
$n$. Because $\tanh$ is an odd function, we have $\tanh(x)=-\tanh(-x)$ and
$\tanh(0)=0$. Therefore, given $\bm{w}_{i},\bm{w}_{j}\neq\bm{0}$ with
$\bm{w}_{i}=\pm\bm{w}_{j}$,
$\textnormal{span}\\{\sigma(\bm{w}_{i}^{\text{T}}x)\\}=\textnormal{span}\\{\sigma(\bm{w}_{j}^{\text{T}}x)\\}$
and
$\textnormal{span}\\{\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{d}\\}=\textnormal{span}\\{\sigma^{\prime}(\bm{w}_{j}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{j}^{\text{T}}x)x_{d}\\}$.
Since there are $m_{\bm{w}}$ different non-zero weights, by Proposition 2 we
have

$\dim\left(\textnormal{span}\\{\sigma(\bm{w}_{i}^{\text{T}}x)\\}_{i=1}^{m}\right)=m_{\bm{w}}.$

Furthermore, note that

$\textnormal{span}\\{a_{i}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{1},...,a_{i}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{d}\\}_{i=1}^{m}=\textnormal{span}\\{\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{d}:a_{i}\neq
0,i\in[m]\\}.$

Thus, by Proposition 2,

$\displaystyle\,\,\,\,\,\,\,\dim\left(\textnormal{span}\\{\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{d}:\bm{w}_{i}\neq\bm{0},a_{i}\neq
0,i\in[m]\\}\right)$
$\displaystyle=\frac{1}{2}|\\{\bm{w}_{i},-\bm{w}_{i}|\bm{w}_{i}\neq\bm{0},a_{i}\neq
0,i\in[m]\\}|\cdot d.$

Now suppose that $\bm{w}_{j}=\bm{0}\in\mathbb{R}^{d}$ for some $j\in[m]$.
Since $\sigma^{\prime}(\bm{w}^{\text{T}}x)=\sigma^{\prime}(0)\neq 0$ for all
$x\in\mathbb{R}^{d}$,

$\textnormal{span}\\{\sigma^{\prime}(\bm{w}_{j}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{j}^{\text{T}}x)x_{d}\\}=\textnormal{span}\\{x_{1},...,x_{d}\\}$

which consists only of linear functions. By the nonlinearity of $\tanh$, we
conclude that

$\dim\left(\textnormal{span}\\{\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{d}\\}\right)=m_{a}d$

and thus
$\dim\left(\textnormal{span}\\{\sigma(\bm{w}_{i}^{\text{T}}x),\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{1},...,\sigma^{\prime}(\bm{w}_{i}^{\text{T}}x)x_{d}\\}\right)=m_{\bm{w}}+m_{a}d$
as desired. ∎

The above corollary directly gives rise to the following result.

######  Corollary 8.

Let $\sigma=\tanh$. Given distinct weights
$\bm{w}_{1},...,\bm{w}_{m}\in\mathbb{R}^{d}\backslash\\{\bm{0}\\}$ satisfying
$\bm{w}_{k}\neq\pm\bm{w}_{j}$ for $k\neq j$ , and
$a_{1},...,a_{m}\in\mathbb{R}\backslash\\{0\\}$, we have

$\textnormal{dim}(\textnormal{span}\\{\sigma(\bm{w}_{i}^{\text{T}}\bm{x}),a_{i}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{1},...,a_{i}\sigma^{\prime}(\bm{w}_{i}^{\text{T}}\bm{x})x_{d}\\}_{i=1}^{m})=m(d+1).$

Next we consider the estimate of the model rank for CNNs which are widely used
in practice. Here we consider the case where the input has two-dimensional
indices, which is the most general case for the image input. The following two
propositions can be directly generalized to the model rank estimate of CNNs
with an input of one index dimension.

######  Definition 13 (ineffective neurons/kernels).

For two-layer tanh NNs, we say a neuron/kernel is output-ineffective if its
output weight array is zero but input weight array is nonzero. We say a
neuron/kernel is input-ineffective if its input weight array is zero but
output weight array is nonzero. We say a neuron/kernel is null if both input
and out weight arrays are zero. All these neurons/kernels are ineffective.
Neurons/kernels that are not ineffective are effective.

######  Remark 14.

Estimating the model rank at parameter points with input-ineffective neurons
is complicated for CNNs. Luckily, we notice that model rank of a target
function $f^{*}\in\mathcal{F}$ can be obtained by considering only
$\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$ with no input-ineffective
neurons. This is because any $\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$ with
input-ineffective neurons associates to a
$\bm{\theta}^{\prime\prime}\in\mathcal{M}_{f^{*}}$ such that (i) input-
ineffective neurons at $\bm{\theta}^{\prime}$ are replaced by null neurons
(ii)
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime\prime})\leqslant\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$.
Therefore, we only estimate the model rank for CNNs at the parameter points
with no input-ineffective neurons in the following propositions.

######  Proposition 3 (model rank estimate for CNNs (with weight sharing)).

Given $m\in\mathbb{N}$, $d\in\mathbb{N}$ and $s\in[d]$. For any $l\in[m]$, let
$\bm{K}_{l}$ be a $(s\times s)$ matrix. Consider CNNs with stride = 1. For a
tanh-CNN $f_{\bm{\theta}}$ with weight sharing,

$f_{\bm{\theta}}(\bm{I})=\sum_{l=1}^{m}\sum_{i,j=1}^{d+1-s}a_{lij}\tanh\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K_{l;\alpha,\beta}\right),\bm{I}\in\mathbb{R}^{d\times
d},$

its model rank at $\bm{\theta}=(a_{lij},\bm{K}_{l})_{l,i,j}$ with no input-
ineffective neurons is given by

$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta})=m_{a}s^{2}+m_{K}(d+1-s)^{2},$

where
$m_{K}=\frac{1}{2}|\\{\bm{K}_{l},-\bm{K}_{l}|l\in[m],\bm{K}_{l}\neq\bm{0}\\}|$
indicating the number of independent kernels,
$m_{a}=\frac{1}{2}\sum_{\bm{K}\in\mathcal{K}}\operatorname{dim}(\textnormal{span}\\{a_{l,:,:}\\}_{l\in
h(\bm{K})})$ indicating the number of independent effective neurons. Here
$\mathcal{K}=\\{\bm{K}_{l},-\bm{K}_{l}|l\in[m],\bm{K}_{l}\neq\bm{0}\\}$, $h$
is a function over $\mathcal{K}$ s.t. for each
$\bm{K}\in\mathcal{K},h(\bm{K})=\\{l|l\in[m],\bm{K}_{l}=\pm\bm{K}\\}$.
$|\cdot|$ is the cardinality of a set, i.e., number of different elements in a
set, and $a_{l,:,:}$ denotes the $(d+1-s)\times(d+1-s)$ matrix whose entries
are $a_{lij}$’s.

###### Proof.

Let $\sigma=\tanh$. We first consider the case in which there is no
ineffective neuron (i.e., $a_{lij}\neq 0$ for all $l,i,j$) and
$\bm{K}_{l}\pm\bm{K}_{l^{\prime}}\neq\bm{0}$ for any distinct
$l,l^{\prime}\in[m]$. In this case the model rank is the dimension of the
following function space (with respect to variable
$\bm{I}\in\mathbb{R}^{d\times d}$)

$\displaystyle\,\,\,\,\,\,\,\textnormal{span}\left\\{\frac{\partial
f_{\bm{\theta}}}{\partial a_{lij}},\frac{\partial f_{\bm{\theta}}}{\partial
K_{l;\alpha,\beta}}\right\\}$
$\displaystyle=\textnormal{span}\left\\{\sigma\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right),\right.$
$\displaystyle\,\,\,\,\,\,\,\left.\sum_{i^{\prime},j^{\prime}=1}^{d+1-s}a_{li^{\prime}j^{\prime}}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i^{\prime}+s-\alpha^{\prime},j^{\prime}+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i^{\prime}+s-\alpha,j^{\prime}+s-\beta}\right\\}_{l,i,j,\alpha,\beta},$

where $l\in[m]$ and $\alpha,\beta\in[s]$. Next, we prove by contradiction that
the set of functions

$\left\\{\sum_{i,j=1}^{d+1-s}a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}\right\\}_{l\in[m],\alpha,\beta\in[s]}$

are linearly independent. If they are not linearly independent, there exist
not all zero constants $\zeta_{l11},...,\zeta_{lss}$ for $l\in[m]$, such that

$\sum_{l=1}^{m}\sum_{\alpha,\beta=1}^{s}\zeta_{l\alpha\beta}\sum_{i,j=1}^{d+1-s}a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0,$

which implies that the set of functions

$\left\\{a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}\right\\}_{l,i,j,\alpha,\beta}$

are linearly dependent, contradicting Proposition 2.

In presence of null neurons and output-ineffective neurons, if $a_{lij}=0$ for
certain $l\in[m]$ and all $i,j\in\\{1,...,d+1-s\\}$,

$\sum_{i,j=1}^{d+1-s}a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0$

for all $\alpha,\beta\in[s]$. If $\bm{K}_{l}=\bm{0}$ for certain $l\in[m]$,
then by Definition 13 $a_{lij}=0$ must hold for all $i,j$. Thus, we have

$\sigma\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0,$
$\sum_{i,j=1}^{d+1-s}a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{l;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0.$

Moreover, notice that two kernels with $\bm{K}_{l}=\pm\bm{K}_{l^{\prime}}$ can
be reduced to one while maintaining model rank if and only if the
corresponding output weights $a_{l,:,:}$ and $a_{l^{\prime},:,:}$ are linearly
dependent. Then, similar to Corollary 2, we conclude that the model rank is
$m_{a}s^{2}+m_{K}(d+1-s)^{2}$. ∎

######  Proposition 4 (model rank estimate for CNNs without weight sharing).

Given $m\in\mathbb{N}$, $d\in\mathbb{N}$ and $s\in[d]$. For any $l\in[m]$ and
$i,j\in[d+1-s]$, let $\bm{K}_{lij}$ be a $(s\times s)$ matrices. Consider CNNs
with stride = 1. For a $\tanh$ CNN $f_{\bm{\theta}}$ without weight sharing,

$f_{\bm{\theta}}(\bm{I})=\sum_{l=1}^{m}\sum_{i,j=1}^{d+1-s}a_{lij}\tanh\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K_{lij;\alpha,\beta}\right),\bm{I}\in\mathbb{R}^{d\times
d},$

its model rank at $\bm{\theta}=(a_{lij},\bm{K}_{lij})_{l,i,j}$ with no input-
ineffective neuron is given by

$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta})=m_{a}s^{2}+m_{K},$

where
$m_{K}=\frac{1}{2}|\\{p(\bm{K}_{lij}),-p(\bm{K}_{lij})|l\in[m],i,j\in[d+1-s],\bm{K}_{lij}\neq\bm{0}\\}|$
indicating the number of independent kernels,
$m_{a}=\frac{1}{2}|\\{p(\bm{K}_{lij}),-p(\bm{K}_{lij})|l\in[m],i,j\in[d+1-s],a_{lij}\neq
0\\}|$ indicating the number of independent effective neurons. Here $p$ is the
padding function over kernels, i.e., for each ($s\times s$) kernel
$\bm{K}_{lij}$, $p(\bm{K}_{lij})\in\mathbb{R}^{d\times d}$ s.t.
$p(\bm{K}_{lij})[i:i+s-1,j:j+s-1]=\bm{K}_{lij}$ and the other elements of
$p(\bm{K}_{lij})$ are zero. $|\cdot|$ is the cardinality of a set, i.e.,
number of different elements in a set.

###### Proof.

Let $\sigma=\tanh$. The model rank is the dimension of the following function
space

$\displaystyle\,\,\,\,\,\,\,\textnormal{span}\left\\{\frac{\partial
f_{\bm{\theta}}}{\partial a_{lij}},\frac{\partial f_{\bm{\theta}}}{\partial
K_{lij;\alpha,\beta}}\right\\}_{l,i,j,\alpha,\beta}$
$\displaystyle=\textnormal{span}\left\\{\sigma\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{lij;\alpha^{\prime},\beta^{\prime}}\right),\right.$
$\displaystyle\quad\left.a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{lij;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}\right\\}_{l,i,j,\alpha,\beta},$

where $l\in[m]$, $1\leqslant i,j\leqslant d+1-s$, and $\alpha,\beta\in[s]$.
Also note that if $a_{lij}=0$ for some $l\in[m]$ and
$i,j\in\\{1,...,d+1-s\\}$, then

$a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{lij;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0$

for all $\alpha,\beta\in[s]$. If $\bm{K}_{lij}=\bm{0}$ for some $l\in[m]$ and
$i,j\in\\{1,...,d+1-s\\}$, because there is no input-ineffective neurons, we
must have $a_{lij}=0$. Then

$\sigma\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{lij;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0,$
$a_{lij}\sigma^{\prime}\left(\sum_{\alpha^{\prime},\beta^{\prime}}I_{i+s-\alpha^{\prime},j+s-\beta^{\prime}}K_{lij;\alpha^{\prime},\beta^{\prime}}\right)I_{i+s-\alpha,j+s-\beta}=0.$

It follows from Proposition 2 that this space has dimension
$m_{a}s^{2}+m_{K}$. ∎

###  5.2 Optimistic sample size estimates

######  Theorem 5 (optimistic sample sizes for two-layer tanh-NN).

Given a two-layer NN
$f_{\bm{\theta}}(\bm{x})=\sum_{i=1}^{m}a_{i}\tanh(\bm{w}_{i}^{\text{T}}\bm{x}),\bm{x}\in\mathbb{R}^{d},\bm{\theta}=(a_{i},\bm{w}_{i})_{i=1}^{m},$
for any target function
$f^{*}\in\mathcal{F}_{k}^{\mathrm{NN}}\backslash\mathcal{F}_{k-1}^{\mathrm{NN}}$
with $0\leqslant k\leqslant m$, the optimistic sample size

$O_{f_{\bm{\theta}}}(f^{*})=k(d+1).$

Here
$\mathcal{F}^{\mathrm{NN}}_{k}:=\\{\sum_{i=1}^{k}a^{*}_{i}\sigma(\bm{w}_{i}^{*\text{T}}\bm{x})|a_{i}\in\mathbb{R},\bm{w}_{i}\in\mathbb{R}^{d}\\}$
for $k\in\mathbb{N}^{+}$, $\mathcal{F}^{\mathrm{NN}}_{0}:=\\{0(\cdot)\\}$ and
$\mathcal{F}^{\mathrm{NN}}_{-1}:=\emptyset$.

###### Proof.

Given any target function
$f^{*}\in\mathcal{F}_{k}^{\mathrm{NN}}\backslash\mathcal{F}_{k-1}^{\mathrm{NN}}$,
for $k=0$, $f^{*}=0(\cdot)$ and
$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})=0=k(d+1)$.
For $0<k\leqslant m$, we have

$\mathcal{F}_{k}^{\mathrm{NN}}\backslash\mathcal{F}_{k-1}^{\mathrm{NN}}=\\{\sum_{i=1}^{k}a_{i}\tanh(\bm{w}_{i}^{\text{T}}\bm{x}),a_{i}\neq
0,\bm{w}_{i}\neq\bm{0},\bm{w}_{i}\neq\pm\bm{w}_{j}\\}.$

Therefore, there exists $\bm{\theta}^{*}=(a_{i}^{*},\bm{w}_{i}^{*})_{i=1}^{k}$
with $a_{i}^{*}\neq 0$, $\bm{w}^{*}_{i}\neq\bm{0}$, and
$\bm{w}^{*}_{i}\neq\pm\bm{w}^{*}_{j}$ for $i\neq j$, such that
$f^{*}=f_{\bm{\theta}^{*}}:=\sum_{i=1}^{k}a^{*}_{i}\tanh(\bm{w}_{i}^{*\text{T}}\bm{x})$.
By the upper bound estimate Theorem 4, $O_{f_{\bm{\theta}}}(f^{*})\leqslant
k(d+1)$.

By definition, the model rank of $f^{*}$ is the minimal model rank among all
parameters recovering $f^{*}$ in the target set $\mathcal{M}_{f^{*}}$. For any
$\bm{\theta}^{\prime}=(a_{i}^{\prime},\bm{w}_{i}^{\prime})_{i=1}^{m}\in\mathcal{M}_{f^{*}}$,
by Corollary 7,
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})=m_{\bm{w}}^{\prime}+m_{a}^{\prime}d,$
where
$m_{\bm{w}}^{\prime}=\frac{1}{2}|\\{\bm{w}_{i}^{\prime},-\bm{w}_{i}^{\prime}|\bm{w}_{i}^{\prime}\neq\bm{0},i\in[m]\\}|$,
$m_{a}=\frac{1}{2}|\\{\bm{w}_{i}^{\prime},-\bm{w}_{i}^{\prime}|\bm{w}_{i}^{\prime}\neq\bm{0},a_{i}^{\prime}\neq
0,i\in[m]\\}|+|\\{\bm{w}_{i}^{\prime}|\bm{w}_{i}^{\prime}=\bm{0},a_{i}^{\prime}\neq
0,i\in[m]\\}|$. Because

$\sum_{i=1}^{m}a_{i}^{\prime}\tanh({\bm{w}_{i}^{\prime}}^{\text{T}}\bm{x})=\sum_{i=1}^{k}a_{i}^{*}\tanh(\bm{w}_{i}^{*\text{T}}\bm{x})=f^{*}(\bm{x}),$

by the linear independence of neurons Proposition 2,
$m_{\bm{w}}^{\prime}\geqslant k$ and $m_{a}^{\prime}\geqslant k$. Then
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})\geqslant k(d+1)$,
which yields
$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})\geqslant
k(d+1)$. Therefore $O_{f_{\bm{\theta}}}(f^{*})=k(d+1)$.

∎

######  Theorem 6 (optimistic sample sizes for two-layer tanh-CNN).

Given a $m$-kernel two-layer CNN with weight sharing with $2$-d input
$I\in\mathbb{R}^{d\times d}$, $s\times s$ kernel and stride $1$

$\displaystyle
f_{\bm{\theta}}(\bm{I})=\sum_{l=1}^{m}\sum_{i,j=1}^{d+1-s}a_{lij}\tanh\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K_{l;\alpha,\beta}\right),\quad\bm{I}\in\mathbb{R}^{d\times
d},$

for any target function
$f^{*}\in\mathcal{F}_{k}^{\mathrm{CNN}}\backslash\mathcal{F}_{k-1}^{\mathrm{CNN}}$
with $0\leqslant k\leqslant m$, the optimistic sample size

$O_{f_{\bm{\theta}}}(f^{*})=k(s^{2}+(d+1-s)^{2}).$

Here $\mathcal{F}^{\mathrm{CNN}}_{k}$ indicates the function space of
$k$-kernel CNN for $k\in\mathbb{N}^{+}$,
$\mathcal{F}^{\mathrm{CNN}}_{0}:=\\{0(\cdot)\\}$ and
$\mathcal{F}^{\mathrm{CNN}}_{-1}:=\emptyset$.

###### Proof.

Let $\sigma=\tanh$. The above theorem obviously holds for $k=0$. For any
target function
$f^{*}\in\mathcal{F}_{k}^{\mathrm{CNN}}\backslash\mathcal{F}_{k-1}^{\mathrm{CNN}}$
with $0<k\leqslant m$, there exists
$\bm{\theta}^{*}=(a^{*}_{lij},\bm{K}^{*}_{l})_{l\in[k],i,j\in[d+1-s]}$
satisfying (i) $\bm{K}^{*}_{l}\neq\pm\bm{K}^{*}_{l^{\prime}}$ for any $l\neq
l^{\prime}$ and (ii) $\forall l\in[k],\exists a^{*}_{lij}\neq 0$, such that

$f^{*}(\bm{I})=f_{\bm{\theta}^{*}}(\bm{I})=\sum_{l=1}^{k}\sum_{i,j=1}^{d+1-s}a^{*}_{lij}\sigma\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K^{*}_{l;\alpha,\beta}\right).$

By the upper bound estimate Theorem 4, $O_{f_{\bm{\theta}}}(f^{*})\leqslant
k(s^{2}+(d+1-s)^{2})$ ***Although Theorem 4 surely holds for CNNs, we do not
prove it in our work because it requires proving the Embedding Principle for
CNNs out of the focus of the current work. For the rigor of our proof, Theorem
4 can be walk around as follows. Considering
$\bm{\theta}^{\prime}=(a_{lij}^{\prime},\bm{K}_{l}^{\prime})_{l\in[m],i,j\in[d+1-s]}$
with $a_{lij}^{\prime}=a^{*}_{lij},\bm{K}_{l}^{\prime}=\bm{K}^{*}_{l}$ for
$l\in[k]$ and $a_{lij}^{\prime}=0,\bm{K}_{l}^{\prime}=\bm{0}$ for $l>k$, then
$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})\leqslant\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})=k(s^{2}+(d+1-s)^{2})$..

Next we prove that $k(s^{2}+(d+1-s)^{2})$ is also a lower bound of
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})$ for
$\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$. Note that, we only need to
consider the parameter points with no input-ineffective neuron. For any
$\bm{\theta}^{\prime}=(a_{lij}^{\prime},\bm{K}_{l}^{\prime})_{l\in[m],i,j\in[d+1-s]}\in\mathcal{M}_{f^{*}}$
with no input-ineffective neuron, by Proposition 4,

$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})=m_{a}^{\prime}s^{2}+m_{K}^{\prime}(d+1-s)^{2},$

where $m_{K}^{\prime}=\frac{1}{2}|\mathcal{K}|$,
$m_{a}^{\prime}=\frac{1}{2}\sum_{\bm{K}\in\mathcal{K}}\operatorname{dim}(\textnormal{span}\\{a_{l,:,:}\\}_{l\in
h(\bm{K})})$ with
$\mathcal{K}=\\{\bm{K}_{l}^{\prime},-\bm{K}_{l}^{\prime}|l\in[m],\bm{K}_{l}^{\prime}\neq\bm{0}\\}$.
Here $h$ is a function over $\mathcal{K}$ such that for each
$\bm{K}\in\mathcal{K},h(\bm{K})=\\{l|l\in[m],\bm{K}_{l}^{\prime}=\pm\bm{K}\\}$.
Because

$\sum_{l=1}^{k}\sum_{i,j=1}^{d+1-s}a^{*}_{lij}\sigma\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K^{*}_{l;\alpha,\beta}\right)=\sum_{l=1}^{m}\sum_{i,j=1}^{d+1-s}a^{\prime}_{lij}\sigma\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K^{\prime}_{l;\alpha,\beta}\right),$

by the linear independence of neurons Proposition 2, $m_{K}\geqslant k$ and
$m_{a}\geqslant k$. Therefore
$\textnormal{rank}_{f_{\bm{\theta}}}(\bm{\theta}^{\prime})\geqslant
k(s^{2}+(d+1-s)^{2})$ for $\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$, which
yields
$O_{f_{\bm{\theta}}}(f^{*})=\textnormal{rank}_{f_{\bm{\theta}}}(f^{*})\geqslant
k(s^{2}+(d+1-s)^{2})$. Then we obtain
$O_{f_{\bm{\theta}}}(f^{*})=k(s^{2}+(d+1-s)^{2})$. ∎

######  Theorem 7 (optimistic sample sizes of CNN functions in two-layer CNN
without weight sharing).

We consider a $m$-kernel two-layer CNN without weight sharing with $2$-d input
$I\in\mathbb{R}^{d\times d}$, $s\times s$ kernel and stride $1$

$\displaystyle
f_{\bm{\theta}}(\bm{I})=\sum_{l=1}^{m}\sum_{i,j=1}^{d+1-s}a_{lij}\tanh\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K_{lij;\alpha,\beta}\right),\quad\bm{I}\in\mathbb{R}^{d\times
d}.$

For any target function expressible by a CNN (with sharing)
$f^{*}\in\mathcal{F}_{k}^{\mathrm{CNN}}\backslash\mathcal{F}_{k-1}^{\mathrm{CNN}}\subset\mathcal{F}_{k}^{\mathrm{CNN-
NS}}$ with $0\leqslant k\leqslant m$, then the optimistic sample size

$O_{f_{\bm{\theta}}}(f^{*})=(s^{2}+1)(k(d+1-s)^{2}-m_{\mathrm{null}}),$

where $m_{\mathrm{null}}=|\\{(l,i,j)|a_{lij}^{*}=0\\}|$ counts the number of
neurons with zero output weight.

###### Proof.

Let $\sigma=\tanh$. The above theorem obviously holds for $k=0$. For any
target function
$f^{*}\in\mathcal{F}_{k}^{\mathrm{CNN}}\backslash\mathcal{F}_{k-1}^{\mathrm{CNN}}$
with $0<k\leqslant m$, there is a point $\bm{\theta}^{*}$ of CNN (with
sharing) such that

$f^{*}(\bm{I})=f_{\bm{\theta}^{*}}(\bm{I})=\sum_{l=1}^{k}\sum_{i,j=1}^{d+1-s}a^{*}_{lij}\sigma\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}H^{*}_{l;\alpha,\beta}\right),$

where $\bm{H}^{*}_{l}\neq\pm\bm{H}^{*}_{l^{\prime}}$ for any $l\neq
l^{\prime}$ and $\forall l\in[k],\exists a^{*}_{lij}\neq 0$. Then

$f^{*}(\bm{I})=f_{\bm{\theta}^{*}_{\mathrm{NS}}}(\bm{I})=\sum_{l=1}^{k}\sum_{i,j=1}^{d+1-s}a^{*}_{lij}\sigma\left(\sum_{\alpha,\beta}I_{i+s-\alpha,j+s-\beta}K^{*}_{lij;\alpha,\beta}\right),$

where $\bm{K}^{*}_{lij}=\bm{H}^{*}_{l}$ for all
$(l,i,j)\in\\{(l,i,j)|a_{lij}^{*}\neq 0\\}$, $\bm{K}^{*}_{lij}=\bm{0}$ for
$(l,i,j)\in\\{(l,i,j)|a_{lij}^{*}=0\\}$ and
$\bm{\theta}^{*}_{\mathrm{NS}}=(a^{*}_{lij},\bm{K}^{*}_{lij})_{l\in[k],i,j\in[d+1-s]}$.
By Proposition 3, the model rank at $\bm{\theta}^{*}_{\mathrm{NS}}$ for the
$k$-kernel no-sharing CNN becomes

$\textnormal{rank}_{\mathrm{CNN^{\mathrm{NS}}_{k}}}(\bm{\theta}^{*}_{\mathrm{NS}})=m_{a}^{*}s^{2}+m_{K}^{*},$

where

$m_{K}^{*}=\frac{1}{2}|\\{p(\bm{K}_{lij}^{*}),-p(\bm{K}_{lij}^{*})|\bm{K}_{lij}^{*}\neq\bm{0},l\in[k],i,j\in[d+1-s]\\}|=k(d+1-s)^{2}-m_{\mathrm{null}}$

and

$m_{a}^{*}=\frac{1}{2}|\\{p(\bm{K}_{lij}^{*}),-p(\bm{K}_{lij}^{*})|l\in[k],i,j\in[d+1-s],a_{lij}\neq
0\\}|=k(d+1-s)^{2}-m_{\mathrm{null}},$

and $p$ is the padding function over kernels, i.e., for each ($s\times s$)
kernel $\bm{K}_{lij}$, $p(\bm{K}_{lij})\in\mathbb{R}^{d\times d}$ s.t.
$p(\bm{K}_{lij})[i:i+s-1,j:j+s-1]=\bm{K}_{lij}$ and the other elements of
$p(\bm{K}_{lij})$ are zero. Similar to the proof of Theorem 6, by the upper
bound estimate Theorem 4,

$O_{\mathrm{CNN^{\mathrm{NS}}_{m}}}(f^{*})\leqslant
O_{\mathrm{CNN^{\mathrm{NS}}_{k}}}(f^{*})\leqslant\textnormal{rank}_{\mathrm{CNN^{\mathrm{NS}}_{k}}}(\bm{\theta}^{*}_{\mathrm{NS}})=(s^{2}+1)(k(d+1-s)^{2}-m_{\mathrm{null}}).$

Also similar to the proof of Theorem 6, for any
$\bm{\theta}^{\prime}_{\mathrm{NS}}=(a_{lij}^{\prime},\bm{K}_{lij}^{\prime})_{l\in[m],i,j\in[d+1-s]}\in\mathcal{M}_{f^{*}}$
with no input-ineffective neuron, by the linear independence of neurons
Proposition 2, we have

$m_{K}^{\prime}=\frac{1}{2}|\\{p(\bm{K}_{lij}^{\prime}),-p(\bm{K}_{lij}^{\prime})|l\in[m],i,j\in[d+1-s],\bm{K}_{lij}^{\prime}\neq\bm{0}\\}|\geqslant
k(d+1-s)^{2}-m_{\mathrm{null}},$
$m_{a}^{\prime}=\frac{1}{2}|\\{p(\bm{K}_{lij}^{\prime}),-p(\bm{K}_{lij}^{\prime})|l\in[m],i,j\in[d+1-s],a_{lij}^{\prime}\neq
0\\}|\geqslant k(d+1-s)^{2}-m_{\mathrm{null}}.$

Therefore
$\textnormal{rank}_{\mathrm{CNN^{\mathrm{NS}}_{m}}}(\bm{\theta}^{\prime})\geqslant(s^{2}+1)(k(d+1-s)^{2}-m_{\mathrm{null}})$
for $\bm{\theta}^{\prime}\in\mathcal{M}_{f^{*}}$, which yields
$O_{\mathrm{CNN^{\mathrm{NS}}_{m}}}(f^{*})=\textnormal{rank}_{\mathrm{CNN^{\mathrm{NS}}_{m}}}(f^{*})\geqslant(s^{2}+1)(k(d+1-s)^{2}-m_{\mathrm{null}})$.
Then we obtain
$O_{\mathrm{CNN^{\mathrm{NS}}_{m}}}(f^{*})=(s^{2}+1)(k(d+1-s)^{2}-m_{\mathrm{null}})$.
∎

Costly expressiveness in connection for two-layer NNs. Drawing from the
aforementioned findings, we present a comparative analysis of optimistic
sample sizes across various architectures, including CNNs with and without
weight sharing, as well as fully-connected NNs, as depicted in Fig. 2. It is
important to note that, to ensure an equitable comparison, the total number of
hidden neurons is held constant $m(d+1-s)^{2}$ across the different
architectures. As demonstrated in Table 3, for a typical image data with
dimension $d=28$, if the target function is recoverable by a CNN with width
$m$, then the model rank for different NN architectures exhibits significant
variation, ranging from $685m$ for a CNN with weight sharing, to $6760m$ for a
CNN without weight sharing, and up to $530660m$ for a fully-connected NN. This
stark contrast underscores the vast disparities in their target recovery
performance especially when the training data is limited.

Figure 2: Illustration of architectures from fully-connected NN to CNN for comparison.  Table 3: The optimistic sample size for two-layer tanh-CNN with $m$-kernels of size $s\times s$ and stride $1$. The input $\bm{x}\in\mathbb{R}^{d\times d}$. For functions in each CNN function set, we also present their model rank in the corresponding CNN without weight sharing and the corresponding fully-connected NN. Here $m_{\mathrm{n}}=m_{\mathrm{null}}=|\\{(l,i,j)|a_{lij}^{*}=0\\}|$ counts the number of zero output weights in the target function.  $f^{*}$ | CNN | CNN (no sharing) | Fully-connected NN
---|---|---|---
$\\{0\\}$ | $0$ | $0$ | $0$
$\mathcal{F}_{1}^{\mathrm{CNN}}\backslash\\{0\\}$ | $s^{2}+(d+1-s)^{2}$ | $(s^{2}+1)\left((d+1-s)^{2}-m_{\mathrm{n}}\right)$ | $(d^{2}+1)\left((d+1-s)^{2}-m_{\mathrm{n}}\right)$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
$\mathcal{F}_{k}^{\mathrm{CNN}}\backslash\mathcal{F}_{k-1}^{\mathrm{CNN}}$ | $k(s^{2}+(d+1-s)^{2})$ | $(s^{2}+1)\left(k(d+1-s)^{2}-m_{\mathrm{n}}\right)$ | $(d^{2}+1)\left(k(d+1-s)^{2}-m_{\mathrm{n}}\right)$
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$
$\mathcal{F}_{m}^{\mathrm{CNN}}\backslash\mathcal{F}_{m-1}^{\mathrm{CNN}}$ | $m(s^{2}+(d+1-s)^{2})$ | $(s^{2}+1)\left(m(d+1-s)^{2}-m_{\mathrm{n}}\right)$ | $(d^{2}+1)\left(m(d+1-s)^{2}-m_{\mathrm{n}}\right)$

##  6 Experimental results

In Fig. 3, we conduct experiments to assess the practical significance of the
previously estimated optimistic sample sizes in relation to the actual fitting
performance of two-layer tanh neural networks (NNs) with varying
architectures. Our experiments are centered around the target function defined
as:

$f^{*}(\bm{x})=\bm{W}^{*[2]}\tanh(\bm{W}^{*[1]}\bm{x}),$ (8)

where $\bm{W}^{*[2]}=[1,1,1]$ and

$\bm{W}^{*[1]}=\left[\begin{array}[]{cccccc}0.6&0.8&1&0&0\\\ 0&0.6&0.8&1&0\\\
0&0&0.6&0.8&1\\\ \end{array}\right].$

We generate both training and test datasets by sampling input data from a
standard normal distribution and computing the output using the target
function. We employ two-layer tanh-NNs, each with a bias term for the hidden
neurons, in a variety of architectures and with different kernels/widths, to
fit training datasets of sizes ranging from $1$ to $63$.

It is noteworthy that for a single-kernel CNN, with or without weight sharing,
or a fully-connected NN with width $3$ (denoted as $1\textnormal{x}$ in Fig.
3(b-d)), the model rank coincides with the number of model parameters. Under
these conditions, as depicted in Fig. 3(a), the CNN demonstrates a notably
earlier transition to almost-$0$ test error compared to other architectures.
However, this finding is somewhat expected since recoveries occur within the
traditional over-determined/underparameterized regime.

In Fig. 3(b-d), we scale up the kernels/widths of the NNs by a factor of $N$,
indicated by $N\textnormal{x}$ for each architecture. For $N=100$, the
parameter counts for the models are $700$, $1500$, and $2100$, respectively.
According to Table 3, the model rank for the target remains at $7$, $15$, and
$21$ (marked by yellow dashed lines), irrespective of the value of $N$. In
Fig. 3(b-d), we observe a postponement in the transition to accurate target
recovery for $N>1$, meaning that the test error decreases to nearly zero at a
sample size larger than the model rank. Notably, the transition to almost-$0$
test error is much closer to the model rank than to the parameter count,
particularly for large $N$ values. We acknowledge that various factors, such
as suboptimal hyperparameter tuning, could contribute to the observed delay in
recovery. Identifying an optimal training strategy and hyperparameters that
enable recovery of a target function as close to its model rank as possible
remains a significant challenge in the field.

(a) different network types (b) DNN

(c) CNN without weight sharing (d) CNN with weight sharing

Figure 3: Average test error (color) for NNs of different architectures
(ordinate) and sample sizes (abscissa) in fitting the target function Eq. (8).
The yellow dashed line for each row indicates the model rank of the target in
the corresponding NN. (a) Two-layer $1$-kernel tanh-CNN vs. two-layer
$1$-kernel tanh-CNN without weight sharing vs. two-layer width-$3$ fully-
connected tanh-NN. Note that these NNs are referred to as $1\textnormal{x}$
for each architecture in (b-d). (b) Two-layer $N$-kernel tanh-CNN, (c) two-
layer $N$-kernel tanh-CNN without weight sharing, and (d) two-layer width-$3N$
fully-connected tanh-NN labeled by $N\textnormal{x}$ for $N=1,3,10,34,100$.
For all experiments, network parameters are initialized by a normal
distribution with mean $0$ and variance $10^{-20}$, and trained by full-batch
gradient descent with a fine-tuned learning rate. For the training dataset and
the test dataset, we construct the input data through the standard normal
distribution and obtain the output values from the target function. The size
of the training dataset varies whereas the size of the test dataset is fixed
to $1000$. The learning rate for the experiments in each setup is fine-tuned
from $0.05$ to $0.5$ for a better generalization performance.

##  7 Conclusion

Figure 4: Schematic overview of our theoretical results and interconnections.

In this study, we have established a local linear recovery (LLR) guarantee for
deep neural networks (DNNs), demonstrating that all functions expressible by
narrower DNNs possess an LLR-guarantee at overparameterization. Fig. 4
presents a schematic overview of our theoretical results and their
interconnections. Our work lays a solid groundwork for advancing the recovery
theory of DNNs. Suggested by our results for two-layer NNs (Section 5), the
linear independence of neurons as in Proposition 2 plays a key role in the
exact calculation of model rank. For future research, three significant
challenges remain open: (i) determining how to recover a target function with
a sample size that approaches the optimistic estimate; (ii) investigating
whether DNNs can offer stronger forms of recovery guarantees at
overparameterization. (iii) exploring neuron independence in deeper networks
to exactly estimate their model ranks.

More recently, progress has been made on these fronts. Zhang and Xu (2024)
presents empirical evidence suggesting that dropout techniques may enable the
recovery of a target function with a sample size that aligns with its
optimistic one. Furthermore, Zhang et al. (2023a) introduces a stronger form
of recovery guarantee, namely the local recovery guarantee, for two-layer NNs
at overparameterization. As we progress, we anticipate a significant deepening
of our theoretical grasp of target recovery in DNNs.

## Acknowledgement

This work is sponsored by the National Key R&D Program of China Grant No.
2022YFA1008200, the National Natural Science Foundation of China Grant No.
12101402, the Lingang Laboratory Grant No.LG-QS-202202-08, Shanghai Municipal
of Science and Technology Major Project No. 2021SHZDZX0102. We are grateful
for the insightful comments provided by Zhi-Qin John Xu and Tao Luo.

## References

  * Arora et al. (2019) Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _ICML_ , 2019.
  * Bai et al. (2022) Zhiwei Bai, Tao Luo, Zhi-Qin John Xu, and Yaoyu Zhang.  Embedding principle in depth for the loss landscape analysis of deep neural networks.  _arXiv preprint arXiv:2205.13283_ , 2022.
  * Chizat et al. (2019) Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In _NeurIPS_ , pages 2937–2947, 2019.
  * Cooper (2021) Yaim Cooper.  Global minima of overparameterized neural networks.  _SIAM Journal on Mathematics of Data Science_ , 3(2):676–691, 2021.
  * Fukumizu et al. (2019) Kenji Fukumizu, Shoichiro Yamaguchi, Yoh-ichi Mototake, and Mirai Tanaka.  Semi-flat minima and saddle points by embedding neural networks to overparameterization.  _NeurIPS_ , 32:13868–13876, 2019.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: convergence and generalization in neural networks.  In _NeurIPS_ , 2018.
  * Luo et al. (2021) Tao Luo, Zhi-Qin John Xu, Zheng Ma, and Yaoyu Zhang.  Phase diagram for two-layer relu neural networks at infinite-width limit.  _Journal of Machine Learning Research_ , 22:71–1, 2021.
  * Mityagin (2020) B. S. Mityagin.  The zero set of a real analytic function.  _Mathematical Notes_ , 107(3):529–530, Mar 2020.  ISSN 1573-8876.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Shannon (1984) Claude E Shannon.  Communication in the presence of noise.  _Proceedings of the IEEE_ , 72(9):1192–1201, 1984.
  * Simsek et al. (2021) Berfin Simsek, François Ged, Arthur Jacot, Francesco Spadaro, Clement Hongler, Wulfram Gerstner, and Johanni Brea.  Geometry of the loss landscape in overparameterized neural networks: Symmetries and invariances.  In _ICML_ , pages 9722–9732. PMLR, 2021.
  * Sun et al. (2020) Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant.  The global landscape of neural networks: An overview.  _IEEE Signal Processing Magazine_ , 37(5):95–108, 2020.
  * Zhang et al. (2017) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In _ICLR_ , 2017.
  * Zhang et al. (2021a) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Communications of the ACM_ , 64(3):107–115, 2021a.
  * Zhang et al. (2023a) Leyang Zhang, Yaoyu Zhang, and Tao Luo.  Structure and gradient dynamics near global minima of two-layer neural networks.  _arXiv preprint arXiv:2309.00508_ , 2023a.
  * Zhang et al. (2021b) Yaoyu Zhang, Zhongwang Zhang, Tao Luo, and Zhi-Qin John Xu.  Embedding principle of loss landscape of deep neural networks.  _NeurIPS_ , 2021b.
  * Zhang et al. (2022) Yaoyu Zhang, Yuqing Li, Zhongwang Zhang, Tao Luo, and Zhi-Qin John Xu.  Embedding principle: a hierarchical structure of loss landscape of deep neural networks.  _Journal of Machine Learning_ , 1:1–45, 2022.
  * Zhang et al. (2023b) Yaoyu Zhang, Zhongwang Zhang, Leyang Zhang, Zhiwei Bai, Tao Luo, and Zhi-Qin John Xu.  Optimistic estimate uncovers the potential of nonlinear models.  _arXiv preprint arXiv:2307.08921_ , 2023b.
  * Zhang and Xu (2024) Zhongwang Zhang and Zhi-Qin John Xu.  Implicit regularization of dropout.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pages 1–13, 2024.
  * Zhou et al. (2022) Hanxu Zhou, Qixuan Zhou, Zhenyuan Jin, Tao Luo, Yaoyu Zhang, and Zhi-Qin John Xu.  Empirical phase diagram for three-layer neural networks with infinite width.  _NeurIPS_ , 2022.