On the Universality of the Double Descent Peak in Ridgeless Regression
Authors: David Holzmüller
Venue: ICLR 2021 Poster (2021)
Keywords: Double Descent
Interpolation Peak
Linear Regression
Random Features
Random Weights Neural Networks

Abstract: We prove a non-asymptotic distribution-independent lower bound for the expected mean squared generalization error caused by label noise in ridgeless linear regression. Our lower bound generalizes a similar known result to the overparameterized (interpolating) regime. In contrast to most previous works, our analysis applies to a broad class of input distributions with almost surely full-rank feature matrices, which allows us to cover various types of deterministic or random feature maps. Our lower bound is asymptotically sharp and implies that in the presence of label noise, ridgeless linear regression does not perform well around the interpolation threshold for any of these feature maps. We analyze the imposed assumptions in detail and provide a theory for analytic (random) feature maps. Using this theory, we can show that our assumptions are satisfied for input distributions with a (Lebesgue) density and feature maps given by random deep neural networks with analytic activation functions like sigmoid, tanh, softplus or GELU. As further examples, we show that feature maps from random Fourier features and polynomial kernels also satisfy our assumptions. We complement our theory with further experimental and analytic results.

Published as a conference paper at ICLR 2021
ON THE UNIVERSALITY OF THE DOUBLE DESCENT PEAK IN RIDGELESS REGRESSION
David Holzmüller
University of Stuttgart
Faculty of Mathematics and Physies
Institute for Stochastics and Applications
david. hel zellmmelll momuelllrr eerlller@maaa wtw.eeeateemmt....nnsttttteeeeee
ABSTRACT
We prove non-asymptotic distribution-indeeendee lower bound for the expected squared generalization caused label noise in ridgeless linear regres- sion. Our lower bound generalizes a similar known result to the overparameterized (interpolating) regime. contrast to most previous works, our analysis applies a broad class of input distributions with almost surely full-rank feature matrices, which allows us to cover various types of deterministic or random feature maps. Our lower bound is asymptotically sharp and implies that in the presence of label noise, ridgeless linear regression does not perform well around the interpolation threshold for any of these feature maps. We analyze the imposed assumptions in detail and provide a theory for analytic (random) feature maps. Using this the- ory, show that assumptions (Lebesgue) density and feature maps given by random deep neural networks with analytic activation functions like sigmoid, tanh, softplus GELU. As further amples, we show that feature maps from random Fourier features and polynomial kernels also satisfy our assumptions. We complement our theory with further ex- perimental and analytic results.
satisfied for input distributions with
INTRODUCTION
Seeking for a better understanding of the successes of deep learning, /Zhang et al. (2016) pointed out that deep neural networks can achieve very good performance despite being able to fit random noise, which sparked the interest of many researchers in studying the performance of interpolating learning methods. [Belkin et al. (2018) made a similar observation for kernel methods and showed that clas- sical generalization bounds are unable explain this phenomenon. Belkin et al. (2019a) observed "double descent" phenomenon in various learning models, where the test error first decreases with increasing model complexity, then increases towards the "interpolation threshold" where the model first able to fit the training data perfectly, and then decreases again in the "overparameterized" regime where the model capacity is larger than the training set. This phenomenon has also been dis- covered in several other works (Bös & Opper 1997 Advani & Saxe 2017] Neal et al. 2018 (ppigerr al. 2019). Nakkiran al. (209) performed large empirical study on deep neural networks and found that double descent can not only occur function of model capacity, but also as a function of the number of training epochs or as a function of the number of training samples.
Theoretical investigations of the double descent phenomenon have mostly focused on specific un- regularized ("ridgeless") or weakly regularized linear regression models. These linear models can be described via i.i.d. samples (11,31). 91........... (In, Bn) E Rd, where the covariates are mapped to feature representations z; = ((x:) ) E I via (potentially random) feature map Φ, and (ridgeless) linear regression is then performed
the transformed samples (z;, y:). While linear regression with random features can understood as a simplified model of fully trained neural networks, is also interesting in its own right: For example, random Fourier features (Rahimi & Recht 2008) and random neural network features (see e.g. Cao et al. 2018 Scardapane & Wang 2017) have gained notable amount of attention.

---

Published as a conference paper at ICLR 2021
Unfortunately, existing theoretical investigations of double descent are usually limited in one or more of the following ways:
(1) They assume that the 2, (or a linear transformation thereof) have (centered) i..d. compo- nents. This assumption is made by Hastie et al. (2019), while Advani & Saxe (0117) and [Blkin et al. (2019b) even assume that the 2; follow Gaussian distribution. While the assumption of i.i.d. components facilitates the application of some random matrix theory results, it excludes most feature maps: For feature maps with d < p, the z; will usually be concentrated on a d-dimensional submanifold of IP, and will therefore usually not have i..d. components.
(2) They assume a (shallow) random feature model with fixed distribution of the T;. e.g. an isotropic Gaussian distribution or uniform distribution on sphere. Examples for this are the single-layer random neural network feature models by Hastie et al. (2019) in the un- regularized case and by Mei & Montanari (2019); d''Asooli et al. (2020a) in the regularized case. A simple Fourier model with d = has been studied by Belkin et al. (2019)). While these analyses provide insights for some practically relevant random feature models, the assumptions the input distribution prevent them from applying real-world data.
(3) Their analysis only applies a nigh-dimensional limit where n. p + oc and n/p + % where y E (0, oo) the model by Belkin et al. (2019b) where the z, follow a standard Gaussian distribution.
constant. This applies to all works mentioned in (1) and (2) except
In this paper, we provide an analysis under significantly weaker assumptions. We introduce the basic setting of our paper in Section 2 and Section 3 Our main contributions are:
show non-asymptotic distribution-inddeeedde lower bound for the ex- pected excess risk of ridgeless linear regression with (random) features. While the un- derparameterized bound is adapted from a minimax lower bound in MMourtada (2019), the overparameterized bound is new and perfectly complements the underparameterized ver- sion. The obtained general lower bound relies on significantly weaker assumptions than most previous works and shows that there is only limited potential to reduce the sensitivity of unregularized linear models label noise via engineering better feature maps.
In Section 4.
In infSection 5] we show that our lower bound applies a large class of input distributions and feature maps including random deep neural networks, random Fourier features and polyno- mial kernels. This analysis is also relevant for related work where similar assumptions not investigated (e.g. Mourtada 2019 Muthukumar et al.) 2020). For random deep neural networks, our result requires weaker assumptions than related result by Nguyen & Hein (2017).
In Seccionn aadd Appendix C. we compare our lower bound to new theoretical and experi- mental results for specific examples, including random neural network feature maps as well as finite-width Neural Tangent Kernels (Jacot al. 2018). We also show that our lower bound is asymptotically sharp in the limit n., DC.
Similar to this paper, Muthukumar al., (2020) study the "fundamental price of interpolation" in the overparameterized regime, providing a probabilistic lower bound for the generalization error under the assumption of subgaussian features or (suitably) bounded features. We explain the difference to our lower bound in detail in [Appeddix I. showing that our overparameterized lower bound for the expected generalization error requires significantly weaker assumptions, that it is uniform across feature maps and that it yields more extreme interpolation peak.
Our lower bound also applies to a large class of kernels they can be represented using a feature map with finite-dimensional feature space, i.e. p 0o. For ridgeless regression with certain classes of kernels, lower or upper bounds have been derived (Liang & Rakhlin 2020: Rakhlin & Zhai 2019, Liang et al. 2019). . However, explained in more detail in Appendix K these analyses impose
restrictions on the kernels that allow them to ignore "double descent" type phenomena in the feature space dimension p.
Beyond Double Descent, a series of papers have studied "Multiple Descent" phenomena theoret- ically and empirically, both with respect to the number of parameters p and the input dimension d. Adlam & Pennington| (2020) and d' Ascoli et al. (2020b) theoretically investigate Triple Descent phenomena. Nakkiran et al. (2020) argue that Double Descent can be mitigated by optimal regular- ization. They also empirically observe a form of Triple Descent in an unregularized model, Liang
2

---

Published as a conference paper at ICLR 2021
et al. (2019) prove upper bound exhibiting infinitely many peaks and empirically observe Mul- tiple Descent. Chen et al. (2020) show that in ridgeless linear regression, the feature distributions can be designed to control the locations of ascents and descents in the double descent curve for a "dimension-normalize" mental limit to this "designability"" of the generalization curve for methods that can interpolate with probability one in the overparameterized regime.
noise-induced generalization error. Our lower bound provides a funda-
Proofs for our statements can be found in the appendix. We provide code to reproduce all of our experimental results at
ht.pss///tttbb.commm com https://4ttttaa..oommmmm/m//emep
and we will provide the computed data at att.pps//aal..orr/001114////////
2 BASIC SETTING AND NOTATION
Following Györfi et al.
2002
we consider the scenario where the samples (æ,, 3/) of data set D = R)" are sampled independently from a probability distribution P
((x1, 91) 91), ..... nn In
[R d
on R x RR i.. D ~ pm
We define
2/
X
E Rad
y
E 1"
Un
We also consider random variables (x,z) P that independent of D and denote the distribution of x by Px. The (least squares) population risk of a function f Rd - defined as
Rp(S) = En,y f()))2
We assume Ry² < co. Then, Rp is minimized by the target function fb given by
f>(x) B(y x))
have Rp(ff) oo, and the excess risk (a.k.a. generalization error) of function f Rp(f) Rp(fp)())))))) E. (f(x) ff(x))²
Notation For two symmetric matrices, write A B A- B is positive semidefinite and A > B A- is positive definite. For a symmetric matrix S E Rax= we let (S) 2... (S) be its eigenvalues in descending order. We denote the trace of A by ir( and the Moore-Penrose pseudoinverse of A by A+. For Φ Rd TR and X Raxd with @ applied to each of the rows of X individually. For a set A, we denote its indicator function by 1, For random variable æ, we say that æ has Lebesgue density if Px can be represented by probability density function (w.r.t. the Lebesgue measure). We say that æ is nonatomic if for all possible values H. P(x 3)
let ((X) E RRxp be the matrix
We denote the uniform distribution on A, e.g. the unit sphere S C RP, by ((A). We denote the normal (Gaussian) distribution with mean şe and covariance by N(, Σ). For N, we define [n] = (1..
We review relevant matrix facts, e.g. concerning the Moore-Penross pseudoinverse, in Appendix
3 LINEAR REGRESSION WITH (RANDOM) FEATURES
The most general setting that will consider in this paper is ridgeless linear regression in random features: Given a random variable that is independent from the data set and an associated random feature map 60 Rd + IR, define the estimator
fx,zo( = (x d0 (x)
Although many of our theorems apply to general domains æ; E X' and not just X = Red we set X = lgd for notational simplicity. We require X Rd whenever assume that the distribution of the has Lehesgue density work with analytic feature maps.
3

---

Published as a conference paper at ICLR 2021
which simply performs unregularized linear regression with random features. As special case, the feature map dg may be deterministic, in which case we drop the index 9. An even more specialized case is ordinary linear regression, where d = p and Φo id. yielding fx = x X y.
As described in Hastie et al. (2019), the ridgeless linear regression parameter = th ( y
has minimal Euclidean norm among all parameters 33 minimizing | X [ y1
is the limit of gradient descent with sufficiently small step size on ((3) = (00 (X ) y
with initialization ( : O, and
is the limit of ridge regression with regularization
for À Y
β lim (x) [@o( ( x + xTa)
(1)
For a fixed feature map o, the kernel trick provides correspondence between ridgeless linear re-
gression with and ridgeless kernel regression with the kernel k(x; #)) == ((x)) ( via
fx,v(z) = 6(z) T ((x)= = x(xx) ((X)
(o( X 0
y k(x, X x) X) (2)
where
((2,,11)
(k(11,21) 21)
k xnn)
k(x, x)= =
xXX =
(((xxxn)
k([x,, ((In,
A LOWER BOUND
In this section, we prove our main theorem. which provides non-asymptotic distribution- independent lower bound on the expected excess risk.
RF(ff) can be decomposed into several different contributions (see e.g. d' Ascoli et al. 2020a). In the following, we will focus on the contribution of label noise to the expected excess risk for the estimators fx.y.0 considered in Section 3 Using vias-variance decomposition with respect to y. it is not hard to show that the label-noise-induced error provides a lower bound for the expected excess risk:
The expected excess risk Ex (f
Noose 0. (fx Ey x
< Ex,0xx Eyix (fx.,,((x) (x)x (Bxx(xxolle)
Ex (()x()
= ex (Rp(pxxxxp) Rp(S)))
For linear models considered here, it is not hard to see that ENoise does not depend on fp and is equal to the expected excess risk the special case fp =
In the following, first consider the setting where the feature map ø is deterministic. We will con- sider linear regression on x = o(x) and == ((X) and formulate our assumptions directly w.rt. the distribution Pz of hiding the dependence x is usually fixed and determined by the problem. the distribution Pz can be actively influenced by choosing suitable feature map db We will analyze in /Scciin 5) how the assumptions Pz be translated back to assumptions on Px and assumptions on Φ.
the feature map ø. While the distribution Px of
For typical feature maps, we have p d, Pz concentrated on a d-dimensional sub- manifold of IR" and the components of z are not independent. A simple example (cf. PProposiiion 8) a polynomial feature map Ø IR. + R x + (1, x, p.).). The imposed assumptions on Pz should hence allow for such distributions on submanifolds and not require independent compo- nents.
Remark 1.
Definition 2. Assuming that E 1
Do, i.c. (MOM) in Theorem holds, can define the (positive semidefinite) second moment matrix
: E=
[zz]] _ E IRxPP
If Ez 0. Σ is also the covariance matrix of 2. If Σ is invertible, i.e. (COV) in Theorem 3 holds, the rows un; 1/12 mn of the "whitened" data matrix W - 1/2 satisfy Eur,w p-
4

---

Published as a conference paper at ICLR 2021
With these preparations, we state main theorem. Its assumptions and the obtained lower bound will be discussed in Section 5 and (acction 6, respectively.
Theorem (Main result). Let n, 1. Assume that P and satisfy:
(INT) Ey < 0o and hence Rr(s7) < co, (NOI) Var x) 2 o² almost surely over z, (MOM) E x < oc, i.e. E exists and is finite,
(COV) E invertible,
(FRK) Z E RRxp almost surely has full rank, ie. rank Z = min [n. p).
Then, for the ridgeless linear regression estimator [z),((z) = Z y, the following holds:
(I) ENoise 2 20 tr(((r(())
(II OeEz tr (WW
(IV)
P n,
ΣZ+)
0²
p
1
P S n,
ENoise 2 oZ tr( Ex+)
Ez tr( w)-
p
Here, the matrix inverses exist almost surely in the considered cases. Moreover, have:
(fOI) holds with equality, then (T) holds with equality.
If or Σ XI for some X > O, then (IT) holds with equality.
For discussion on how Σ influences ENoise. we refer to Remark G.] We can extend Theorem 3 to random features if it holds for almost all of the random feature maps:
Corollary 4 (Random features). Let O ~ Pe be a random variable such that do Rdd - Rp is a random feature map. Consider the random features regression estimator fx.0 (x) = x Z
with ze = óe (x) and Ze == (x If for Pe-almos all 0, the assumptions of Theorem are satisfied for 2i and Z Zg (with the corresponding matrix Σ Eg). then
f02 p+1-n
ipp 2 n 02 n+1-p ip S
ENolse 2
The main novelty in Theorem is the explicit uniform lower bound (IV) for p 2 n: The lower bound (V) for p S n. follows by adapting Corollary 1 in Mourtada (2019). Statements similar to (I), (TI) and (III) have also been proven, see e.g. |Hastie et al. (2019 and Theorem in Muthuku-- mar et al. 2020). However, as discussed in [Section Hastie et al. (2019) make sificiantly stronger assumptions for computing the expectation. In|Appendix L we explain in more detail that the proba- bilistic overparameterized lower bound Muthukumar et al. (2000) is not iestributionnindpeedeeee and only applies to a smaller class distributions than our lower bound. For a discussion on how Theorem 3 applies to kernels with mmite-dimensiona feature space, refer to Appendix KI
5 WHEN ARE THE ASSUMPTIONS SATISFIED?
In this section, we want to discuss the assumptions of Theorem 3 and provide different results helping to verify these assumptions for various input distributions and feature maps. The theory will be particularly nice for analytic feature maps, which define now:
Definition 5 (Analytic function). A function f Rdd + R is called (real) analytic for all z E Tdd the Taylor series of around converges to in neighborhood of z. A function f Rd is called (real) analytic if f1,... So are analytic.
R", z
Sums, products and compositions of analytic functions are analytic, ef. e.g. Section 2.2 in Krantz & Parks (2002). We will discuss examples of analytic functions later in this section.
Proposition 6 (Characterization (COV) and (FRK)). Consider the setting of Theorem and let FRK(m) be the statement that (FRK) holds for n. Then,
(i) Let n 2 1. Then, FRK(n) iff P(z E U) = ffror all linear subspaces U C RR of dimension min mni, p} 1.
(ii) Let (MOM) hold. Then, (COV) holds iff P( E U) < 1.for all linear subspaces U C RR of dimension p
5

---

Published as a conference paper at ICLR 2021
Assuming that (MOM) holds such that (COV) is well-defined, consider the following statements:
(a) FRK(p) holds.
(b) FRK(n) holds for all 2 1.
(c) (COV) holds.
(d) There exists a fixed deterministic matrix X E RRxx such that (et( +
We have (a) (b) -b)=00 (c) then (a) (d) are equivalent.
(d). Furthermore, if Rdd has Lebesgue density and is analytic,
With this in mind, we can characterize the assumptions now:
The assumption (INT) is standard (see e.g. Section 1.6 in Györfi et al. 2002 and guarantees Rp(ft) < D0, such that the excess risk is well-defined.
The assumption (NOI) is required to ensure the existence of sufficient label noise. Impor- tantly, Lemma H.1 shows that (NOI), i.e. Var(y/z) 2 a² almost surely over z, holds if Var(y/ œ) 2 x² almost surely over a. All Double Descent papers from Section make the
stronger assumption that the distribution of y E(ylz)) ) is independent of x: or even fixed Gaussian.
The assumption (MOM) can be reformulated as E3] =||=|| For example, & or equivalently & are bounded, or if á is continuous and || | is bounded, then (MOM) is satisfied. Such assumptions
Bl Ek(x,x) x)) <
frequently imposed (see e.g. Chapters 6, 7, 8, 10 in Györfi et al. 2002). In this sense, (MOM) a standard assumption.
The assumptions (COV) and (RK
implied by FRK(p) and are equivalent to FRK(p) in the underparameterized case p S. n. In the following, we will therefore focus on proving FRK(p) for various & and Px. In the case p n. FRK(p) ensures that fx.y almost surely interpolates the data, or equivalently that the kernel matrix xXX, X)) almost surely has full rank. Importantly, assuming FRK(p) is weaker than assuming strictly positive definite kernel, since strictly positive definite kernels require oc. Example D.1 shows that the assumption (FRK) in Theorem 3Jcanoot be removed.
For the analytic function Ø id with d p. Proposition yjiills simple sufficient criterion: If has Lebesgue density, then (FRK) holds for all ni. This assumption is already more realistic than assuming i..d. components. However, Proposition 6) is also very useful for other analytic feature maps, as we will see in the remainder of this section.
Remark 7. Suppose that # 0 is analytic, æ has a Lebesgue density and (INT), (MOM) and (NOI) are satisfied. If (d) (d) in Proposition 6 does not hold, there exists < p such that the lower bound from Theorem holds with p replaced by p: Let U = Span(ó(x=)
æ E IRd). Since & $ 0, p dim 0 Moreover, (d) holds iff dim = p. Take any isometric isomorphism dé U R
and define the feature map ő IRd R2, x + v(((x)). Then, á is analytic since &b is linear, and satisfies (d), hence Theorem 3 can applied ø. However, Φ and @ lead to the same kernel since v is isometric, hence to the same estimator fx.y by Eq. (2) and hence to the same ENoise-
Proposition 8 (Polynomial kernel). Let d 1 and c O. For x, x E Rdd define the polynomial kernel ke x) = (x: ToTa: T + c)m Then, there exists a feature map á Rdd - R., p (m+d), such that:
(a) k(x, .t) ((x)) ((()) (z) for all x, & E Rd, and
(b) if E Rd has Lebesgue density and we use z ((x), then (FRK) is satisfied for all n.
Proposition 8 says that the lower bound from Theorem 3 holds for ridgeless kernel regression with the polynomial kernel with p = (mi+d) if æ has a Lebesgue density and = 2 Ek(x, æ) E[[|=||| + c)Th < co. The proof of Proposiiiio can be extended to the case c = 0, where one needs to choose (m+d-1). In general, we discuss in Appendix K that Theorem 3 can often be applied to ridgeless kernel regression, where p needs to be chosen as the minimal feature space dimension for which A can still be represented.
We can also extend our theory to analytic random feature maps:
Proposition (Random feature maps). Consider feature maps do Rdd - RP with (random)
parameter 0 RR9 Suppose the map (0, x) +> Φo is analytic and that O and are independent

---

Published as a conference paper at ICLR 2021
and have Lebesgue densities. If there exist fixed 0 R X RPxd with det(og(X)) # 0, then almost surely over 0, (FRK) holds for all n for x = (0(x).
In Appendix C we demonstrate that Proposition 9 can be used to computationally verify (FRK) for analytic random feature maps.
Up until now, we have assumed that x has a Lebesgue density. It is desirable to weaken this as- sumption, such that æ can, for example, be concentrated
submanifold of R It is necessary for (R with p 2 2 that æ is nonatomic, such that the 2; are distinct with probability one. In general, this is not sufficient: For example, if Φ id and lives on a proper linear subspace of Rd, (R)(p) is not satisfied. Perhaps surprisingly, we will show next that for random neural network feature maps, is indeed sufficient that is nonatomic Especially, Exppcialie our lower bound in(Corollary thus applies to large class of feedforward neural networks where only the last layer is trained (and initialized to zero, such that gradient descent converges to the Monre-Penrose pseudoinverse).
Theorem 10 (Random neural networks). Let d,p, I. 2 1, let a + R. be analytic and let the layer sizes be do = d, di,...,dr, d,.,, 2 and dr. = P. Let W()) Rdd4ixds for I E {o..... ......,, L 13 be random variables and consider the two cases where
(a) a is not a polynomial with less than p nonzero coefficients, =0= (W w(L-1)) and the random feature map 6o Rd IR? is recursively defined by
)(x:1)) = x011) a(+t)) = =o(((),))))
(b) a is not polynomial of degree < p 1, 1 == (W ..... (l (
b 6 (
with random variables bt9) E RRd++1 for 1 E (0...... I 1}, and the random feature map
óg : IRd + RP is recursively defined by
==
((+11) = o(W(0) (0)) + +bO)..
In both cases, 0 has Lebesgue density and is nonatomic, then (FRK) holds for all and almost surely over 0.
The assumptions of Thheorem 10 on are satisfied by the classical initialization methods He et al. (2015) Glorot & Bengio (2010). Possible choices of are presented in Table 1 A statement similar to Theorem 10 has been proven in Lemma 4.4 in Nguyen & Hein (2017). However, their statement only applies to networks with bias and a more restricted class of activation functions: For example, the activation functions RBF, GELU, SiLU/Swish, Mish, sin and cos are not covered by their assumptions. In [Appendix we explain that the proofs of many other theorems in the literature similar to Theorem 10) for single-layer networks are incorrect.
Some examples of analytic activation functions that are not polynomials. The CDF of N 1) is denoted by 4. Other non-polynomial analytic activation functions are sin, cos or erf. Equation
Table 1:
Activation function
Sigmoid
sigmoid( 1/(1 +e e=)
Hyperbolic Tangent
tanh(z) = (6* e ")/(c" te
Softplus
softplus(2 x -log[ +
RBF
RBF(x) = exp( -Bx²)
GELU (Hendrycks & Gimpel| 2016)
GELU = x
SiLU (Elfwing et al., 2018))
SiLU x. sigmoid
Swish (Ramachandran et al. (217))
Swish(x) (3r
Mish [iisr|[2019
Mish(æ) = x tanh (sof(tpuu)))
TThis appears to he convenient consequence of randomizing the feature map: For each fixed feature map &e. there may be an exceptional set F.g of nonatomic input distributions Px for which FRK(p) is not satisfied. However, Theorem 10 shows that for each nonatomic input distribution Px, the set (0 Px Eg) is a Lebesgue null set. For (deterministic) feature maps where it is not possible to prove FRK(p) for all nonatomic Px. there is a trick that works in certain cases: If æ lives on a submanifold (e.g. sphere), we might be able to write x = (v)) where has Lebesgue density and şi is analytic (e.g. the stereographic projection for the sphere). Then, we can apply our theory to the analytic feature map do o 9/.
7

---

Published as a conference paper at ICLR 2021
Under the assumptions of Theorem 10 if ||||| is bounded, (MOM) holds for all 9. This follows since any analytic function & is also continuous, and continuous functions preserve boundedness. However, the activation functions from Table I evvn satisfy (a(a)) a|æ1 + for some a, 2 0 and all x E R.. In this case, is not hard to see that (MOM) already holds for all 0 if E 13 < 00.
Theorem 10 does not hold for ReLU, ELU (Clevert al. 2015), SELU (Klambauer al. 2017) or other activation functions with perfectly linear part. To see this, observe that with nonzero probability, all weights and inputs are positive. In this case, the feature map acts linear map from R to RP, and if d < p n, the output matrix ((X) cannot be invertible.
In Appendix show that (FRK) is satisfied for random Fourier features if x: is nonatomic and the frequency distribution (i.c. the Fourier transform of the shift-invariant kernel) has a Lebesgue density.
QUALITY OF THE LOWER BOUND
In this section, discuss how sharp the lower bound from Theorem 3 is. To this end, we assume that Var(y|=) z) = o² almost surely over z.
In their Lemma 3, Hastie al. (2019) consider the where has i..d. entries with zero mean, unit variance and finite fourth moment. They then use the Marchenko- Pastur law to show in the limit In this limit, our lower bound shows
p, + 20, p/n y 1 that ENosse
0² 7-I-
ENoise
p p+1-1 o² p/n + 1/n 0² 7-1
n
hence, in this sense, our overparameterized bound is asymptotically sharp. An analogous argument shows that the underparameterized bound is also asymptotically sharp. In order to better understand to which extent our lower bound is non-asymptotically sharp in the over- and underparameterized regimes, we explicitly compute ENoise BZ ir((Z+) E= (cf. Theorem 3 for some distribu- tions Pz:
Theorem 11. Let Pz u(s--1). Then, Pz satisfies the assumptions (MOM), (COV) and (FRK)
for all n with E = I Moreover, for n 2 p 1 or n 2 1, we can compute
if pp=,, ifp2n=1,
Ez tr((Zt) T>*+
=
8
s n+ s2
P-2 P
p-1-n
The formulas in the next theorem have already been computed by Breiman Freedman (1983) for p S 2 and by Belkin et al. (2019b) for general p. Our alternative proof circumvents technical problem in their proof for p E (n n, n + 1}, cf. (pppendxx J
Theorem 12. Let Pz = (0, Ip). Then, Pz satisfies the assumptions (MOM), (COV) and (FRK) for all n with Σ = Ip Moreover, for n,p 2
ifp2 n
P- 1--n
Ez (r( TZ+
X
i {n I,n,n+ 11, n-
For Pz -N,0 Ip) and the lower bound from Theorem 3
the formulas for the under- and over- parameterized cases can be obtained from each other by switching the roles of n and p. Numerical data strongly suggests that this symmetry does not hold exactly for Pz (Sp-1)..
For p 2 n + 2, we can relate our lower bound Theorem 3), the result for the sphere Theorem II) and the result for the Gaussian distribution (Theorem 12) as follows:
n1
n1
(p + 1 111-) p-1
n2
2-2
7
p p-1-1
p+1-
These values are also shown in Figure together with empirical values NN feature maps specif- ically optimized minmmize ENoise- Since E affects ENoise only for p > (cf. Remark G.T) it is
8

---

Published as a conference paper at ICLR 2021
1.1
Enoise relative to (SP 1) (empirical)
1.0
(0, (analytic)
0.9
Optimized for n 15
Optimized for n 60
U(SP-1) (empirical)
0.8
u($5-1), 1), S p (analytic)
Lower bound
0.7
100
104
102
Number of points
Figure 1:
Various estimates and bounds for ENoise relative ENoise for Pz USPS-)), using
Var(y/z) = and 30. The optimized curves correspond to multi-layer NN feature maps whose parameters were trained to minimize ENgiae for n 15 or 60. More experiments and details on the setup can be found in (Appenddix C We do not plot estimates for n E have high estimation variances.
since they
not surprising that the feature map optimized for n = 60 > 30 = performs badly in the over- parameterized regime. The results in FFiure support the hypothesis that among all Pz satisfying (MOM), (COV) and (FRK), Pz this hypothesis further discussed in Remark G.3 We can prove the hypothesis for 1 p
U(S
minimizes EE tr(( Z Ez*).. The plausibility of
since in this case, the results from Theorem 11 are equal to the lower bound from Theorem 3
When using continuous feature map Rd I2 with d p 2, it seems be unclear first whether the low Eoosse of Pz u((S-1) can even be achieved. We show in Proposition J.2 that this is possible using space-fillle filliniiiing curve feature maps.
The results in this section and in Appenddix Cssow that while our lower bound presumably does not fully capture the height of the interpolation peak at p = n, is quite sharp in the practically relevant regimes p >> n and p & irrespective of d.
ACKNOWLEDGMENTS
The author would like to thank Ingo Steinwart for proof-reading most of this paper and for pro- viding helpful comments. Funded by Deutsche Forschungsgemeinschatff (DFG, German Research Foundation) under Germany's 's Excellence Strategy EXC 2075 390740016, The author thanks the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for support.
REFERENCES
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In International Conference on Machine Learning, pp- 74-84. PMLR, 2020.
Madhu S. Advani and Andrew M. Saxe. High-dimensional dynamics generalization error in neural networks. arXiv:1710.03667, 2017.
Herbert Amann and Joachim Escher. Analysis. Springer, 2005.

---

Published as a conference paper at ICLR 2021
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. arXiv: 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical biai-variance trade-off. Proceedings of the National Academy 2019a.
of Sciences, 16663)):1849--1588
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv:1903.07577, 2019b.
Rajendra Bhatia. Matrix Analysis, volume 169. Springer Science & Business Media, 2013.
Vladimir I. Bogachev. Measure Theory, Volume 2, volume 1. Springer Science & Business Media, 2007.
Charles Bordenave and Djalil Chafai. Around the circular law. Probability surveys, 9:1-89, 2012.
Stephen Boyd and Lieven Vandenberghe. Corvex optimization. Cambridge university press, 2004.
Leo Breiman and David Freedman. How many variables should be entered in regression equation? Journal of the American Statistical Association, 781381) 1983.
Siegfried Bös and Manfred Opper. Dynamics of training. Advances Neural Information Pro- cessing Systems, pp. 141-147, 1997.
Weipeng Cao, Xizhao Wang, Zhong Ming, and Jinzhu Gao. A review neural networks with random weights. Neurocomputing, 275:278-287, 2018.
Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. arXiv:2008. 01036, 2020.
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). |r 2015.
Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance (s) in the lazy regime. wwXiv:2003.0105: 2020a.
Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where why do they appear? arXiv:2006.033: 035009 2020b.
Rick Durrett. Probability: theory and examples, 5th edition, volume 49. Cambridge university press, 2019.
Stefan Elfwing, Eiji Uchibe, and Kenji Doya. function approximation in reinforcement learning. Neural Networks, 107:3-11, 2018.
linear units for neural network
Herbert Federer. Geometric Measure Theory. Springer, 1969.
Catherine Forbes, Merran Evans, Nicholas Hastings, and Brian Peacock. Statistical Distributions. John Wiley & Sons, 2011.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Gene H. Golub and Charles F. Van Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, USA, 1989.
Ping Guo. A vest of the pseudoinverse learning algorithm. arXiv: 2018.
Lászłó Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A Distribution-Free Theory of Nonparametric Regression. Springer Science & Business Media, 2002.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv: 190.008000 2019.
10

---

Published as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015. 2015.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). orXiv:1606.08411. 2016.
Pablo A. Henriquez and Gonzalo A. Ruz. An empirical study of the hidden matrix rank for neu- ral networks with random weights. 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 883-888. IEEE, 2017.
Gao Huang, Guang-Bin Huang, Shiji Song, and Keyou You. Trends extreme learning machines:
A review. Neural Networks, 61:32-48, 2015.
Guang-Bin Huang. Learning capability and storage capacity wwwhhhidddaaeee feedforward net- works. IEEE Transactions Neural Networks, 14(2):274-281, 2003.
Guang-Bi Bing Huang, Qin-Yu Yu Zhu, and Chee-Kheong Siew. Extreme learning machine: theory and applications. Neurocomputingg 70(1-3):489-500 2006.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and
generalization in neural networks. In Advances in neural information processing systems, pp- 8571-8580 2018
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. Advances in neural information processing systems, pp. 971-980, 2017.
Steven G. Krantz and Harold R. Parks. A Primer of Real Analytic Functions. Springer Science & Business Media, 2002.
Peter Kuchment. An overview of periodic elliptic operators. arXiv:1510.00977) 2015.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression gener- alize. Annals of Statistics, (8(3):1329-13444 2020.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-norm interpolants and restricted lower isometry kernels. arXiv: 10292, 2019.
K. V. Mardia, J. T. Kent, and M. Bibby. Multivariate analysis. Probability and mathematical statistics. Academic Press Inc., 1979.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv:1908.05355 2019.
Diganta Misra. Mish: A self regularized non-monotonic neural activation function.
arXiv: 08681, 2019.
Boris Mityagin. The zero set of real analytic function. arXiv: 2015.
Jaouad Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covari- ance matrices. arXiv:1912.10754 2019.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless inter- polation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 2020.
Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv:1912.07242. 2019.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. arXiv=191..22292 2019.
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. 2xXiv:2003.01897 2020.

---

Published as a conference paper at ICLR 2021
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. arXiv:1810.0859) 2018.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Interna- tional Conference on Machine Learning, pp. 2603-2612, 2017.
Viet Dang Nguyen. Complex powers of analytic functions and meromorphic renormalization in QFT. (rXiv:/503.009:5 2015.
James Press. Applied Multivariate Analysis: Using Bayesian and Frequentist Methods of Infer- ence. Courier Corporation, 2005.
Robert James Purser, Manuel de Pondeca, and Sei- Park. Construction of Hilbert curve the sphere with an isometric parameterization of area. Office Note, 2009.
Ali Rahimi and Benjamin Recht. Random features for scage-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008.
Alexander Rakhlin and Xiyu Zhai. Consistency interpolation with laplace kernels high- dimensional phenomenon. In Conference Learning Theory, pp. 2595-26233 2019.
Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for activation functions.
arXiv:1710.05941, 2017.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the Convergence of Adam and Beyond. In International Conference on Learning Representations, 2018.
Hans Sagan. Space-filling curves. Springer Science & Business Media, 2012.
Michael A. Sartori and Panos Antsaklis. A simple method to derive bounds on the size and to train multilayer neural networks. IEEE transactions on neural networks, (44):4674711 1991.
Simone Scardapane and Dianhui Wang. Randomness in neural networks: An overview. Wiley
Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 7(2), 2017.
Wouter F. Schmidt, Martin A. Kraaijveld, and Robert PW Duin. Feed forward neural networks with random weights. In International Conference on Pattern Recognition, pp. 1-1. IEEE COM-
PUTER SOCIETY PRESS, 1992.
Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to over wer-paramettriztioon affects generalization in deep learning. Journal of Physics A: Mathematical and Theoretical, 52(47):474001, 2019.
Shin'ichi Tamura and Masahiko Tateishi. Capabilities of a four-layered feedforward neural network:
four layers versus three. IEEE Transactions on Neural Networks, 6(2):251-255 1997.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices.
1rX1v: 2010.
Dietrich von Rosen. Moments for the inverted Wishart distribution. Scandinavian Journal of Statis- fics, pp. 97-109, 1988.
Guorong Wang, Yimin Wei, Sanzheng Qiao, Peng Lin, and Yuzhuo Chen. Generalized Inverses: Theory and Computations, volume 53. Springer, 2018
Bernard Widrow, Aaron Greenblatt, Youngsik Kim, and Dookun Park. The No-Prop algorithm: A new learning algorithm for multilayer neural networks. Neural Networks, 37:182-188, 2013.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXh::1611.035.0 2016.
12

---

Published as a conference paper at ICLR 2021
A OVERVIEW
The appendix is structured as follows: In Appendix B, we provide an overview over some ma- trix identities used throughout the paper. We provide additional numerical experiments for various (random) feature maps in AAppendix C The counterexample given in [Appendix D shows that the assumption (FRK) cannot be omitted from [Thorem 3 In AApenddx E provide an overview over full-rank theorems for random neural networks in the literature and explain why their proofs are incorrect. We then prove our main results in [Appendix F before discussing consequences in Appendix G] In Appendix H we give proofs for the theorems and propositions from [Section 5) As an addition, we prove (HRK) for random Fourier features Appendix Finally, proofs for the statements from Rectiontion 6 are given in Appendix J
Whenever we prove theorems or propositions from the main paper (like) Theorem 3 in the Appendix, repeat their statement before the proof for convenience. In contrast, new theorems propositions are numbered according to the section they are stated in, e.g. Proposition
B MATRIX ALGEBRA
In the following, we will present some facts about matrices that are relevant this paper. For general reference, we refer to textbooks the subject (e.g. Golub & Van Loan 1989 Bhatia 2013).
Let n, 2 and let k == (n, p}. The singular value decomposition (SVD) of a matrix A E Raxp is decomposition A UDV into orthogonal matrices U Raxk V R with U V I& and diagonal matrix D R with non-negative diagonal elements 2 s (A) called singular values.
81 (1 2 2..
For given symmetric square matrix A Baxn with eigenvalues {1 ...)..2..... the trace satisfies
(r(A)
A
The trace is linear and invariant under eyclical permutations. We use this multiple times in arguments of the following type: If v E TRP and A E IRxx are stochastically independent (e.g. because A is constant), we can write
E Av E. tr(u Av) E. tr trvvvv] tr tr(AE.vu
Moreover, A > 0, then for all i E [n]. \ (A) > O and we have
1
A (A (A(A)
For positive definite matrix Σ RPxp, the SVD and the eigendecomposition coincide Σ U diag(Ai (E), ... (E))U and we can define the inverse square root
Σ 1/2 U diag Ar (E) 1/2 Ap (E) 1/2)1 U > 0,
which is the unique s.p.d. matrix satisfying (Σ 1 Σ-1 By the
Weyl theorem, two symmetric matrices A, B E Raxn with A 3 B satisfy
(A) =
max min NEV ||]|===
T ATAu S
max VCR subquace dim V=i [
min NEV
v Bu = (B)
VCR" suhspace dim V=i
Let A Raxp, The Moore- pseudoinverse * of A satisfies the following relations (see e.g. Section 1.1.1 in Wang et al. 2018):
Suppose has the SVD A UDVT, where diag(Si,.... Sk), ) = min(n, p)-
Using the convention 1/0 = 0. we can write * = VD*UT where D* diag(1/s1.... 1/51,..;11/1)
13

---

Published as a conference paper at ICLR 2021
A = = A) = (AA yt. If A is invertible, then _ A
A (A"A = (A A)+.
We will also use basic fact the Schur complement that, for example, is outlined in Appendix A.5.5 in Boyd & Vandenberghe 2004):
A11
A12
0
A21
A22
then 22 > 0 and An1 (A A12Az2 A21)
A12 A21 > and the top-left m, x my block A 11 is given by
C EXPERIMENTS
the following, we experimentally investigate &Noise for different (random) feature maps. will first give overview over the plots and then explain the details of how they were generated and some implications. More details can be found in the provided code. All empirical curves show one estimated standard deviation of the mean estimator this standard deviation is sometimes too small to be visible. We assume Var(y|z) = almost surely over such that (T) in Theorem holds with equality with o² 1.
shaded area around the estimated mean, but
104
103
sigmoid NN
Enoise (noisc- (noisc-induced induccd crror)
tanh NN
102
GELU NN
softplus NN
ReLU NN
10
SELU NN
NN
10
U(SP-1)
Lower bound
10
100
10
10
Number of points
Figure C.I: Estimated Eeiss for random neural network feature maps (cf. Theorem 10 with differ- activation functions and dn from Pz = U(S-11) as comparison, ef. Section
10.d; d, d2 256, d3 p 30. We include the results
Figure C. shows Exoise for random three-layer neural network feature maps with 30, differ- ent activation functions and varying n. Note that all neural networks produce higher Eooise than Pz U((S=1)). The effect of non-isotropic covariance matrices in the overparameterized regime can be clearly seen when comparing Figure C.T to Figure C.2 where features have been whitened separately for each set of random parameters 0, cf. Remark G.T Figure C.3 then shows ENois for 30 and varying p.
Note that double descent is usually plotted as function of the "model complexity" p as in Belkin et al. 2019a),, but varying p is only possible when we have a (random) feature map o(()) Rdd + R for each value of p. For the following NTK and polynomial kernels, there is canonical way
14

---

Published as a conference paper at ICLR 2021
10
10a
sigmoid NN
Enoiso (noise moise-induced crror)
tanh NN
10a
GELU NN
softplus NN
ReLU NN
10
SELU NN
ELU
100
U(SP-1)
Lower bound
10
100
10
102
Number of points
Figure C.2: As in Figure C.I but with whitened features, i.e. using (tr((WWt]] in the overpa-
rameterized case S p, cf. hhooem and Remark G.1
104
103
Euoise (noisc-induced crror)
sigmoid NN
tanh NN
10
GELU NN
softplus NN
10
ReLU NN
SELU NN
10
ELU NN
Lower bound
10
10"
10
102
Number of parameters
Figure C.3: As Figure C.I but with 30 fixed and varying ds p.
define such sequence of feature maps. For this reason, we will plot their results only with varying Double descent as function of the number of samples has for example been pointed out by Nakkiran et al. (2019) and Nakkiran (2019).
Figure C.4 shows ENoise for various random finite-width Neural Tangent Kernels (NTKs), cf. Jacot et al. (2018). These results mostly exhibit larger Exoise than the random NN feature maps from Figure C.1 perhaps because of correlations parameter gradients in different layers. However, this
15

---

Published as a conference paper at ICLR 2021
comparison is not really fair since the NTK feature map much smaller underlying neural network and the input dimension is smaller.
10
103
sigmoid NTK
Euoiso (noisc- induceduudddd crror)
tanh NTK
10a
GELU NTK
softplus NTK
ReLU NTK
10
SELU NTK
ELU NTK
10a
U($*-1)
Lower bound
10-1
100
10 Number points n
102
Figure C.4: Estimated Noise for Neural Tangent Kernel (NTK) feature maps given by various random neural networks (cf. Theorem I0 with do = d 4, d1 p 6. = 30. We include the empirical results from Pz (S as comparison, cf. Section 6
6. d3 1, resulting in
Figure C.5 and Figure C.6 show ENoise for two variants random Fourier features for two different scalings of the random parameters. Figure C.6 shows that for random Gaussian parameters with large variance (corresponding to an approximated narrow Gaussian kernel,, the values of ENoise for random Fourier features are very close to the values for Pz u($P-1). We decided to plot these values relative to each other as in Figure since the curves would overlap normal plot like FFigure C.5 Note that the the version of random Fourier features with sin and cos features automatically yields constant ||=||2 like for Pz = 1(P-1)).
Finally, Figure C.7 shows that linear regression with the polynomial kemel is quite sensitive to label noise. We use p = 35 for the polynomial kernel since there are no particularly interesting polynomial kernels with p 30.
Neural Network feature maps For Figures
and we use random neural network feature maps without biases in Theorem 10 with do 10, d2 256 and dN p. As the input distribution Px, we use (O0 Ta). We initialize the NN weights independently as
w ~ (0,1 where
do d, Var Varn-w(o..((((u)
= ifl 2 1.
Vi
Here, Var,, (u)) ) is approximated once by using with 10 samples for u. This initialization is similar (and for the ReLU activation essentially equivalent) to the initialization method by He et al. (2015). The initialization variances are chosen such that for fixed input æ with ||l||| z 1, the pre-activations in each layer approximately (0, 1)-distributed.
NTK feature maps For Figure C.4, we use a NTK parameterization similar to the original one proposed by [aacot et al. (2018), but again with activation-dependennt scaling. Our neural network is
16

---

Published as a conference paper at ICLR 2021
10
10
Envine (noise-ine (noise-induced induced errof)
10
RFF (cos with bias)
RFF (sin and cos)
10
(SP
Lower bound
10
10
100
10a
10a
Number of points
Figure C.5:
Estimated ENoise for the two versions of random Fourier features described in Ap
pendix I We use =1, Px = NO0 Ia), p = 30 and the weight vector distribution Px.
NO, Ta) a) (ef. Appendix l..
p
1.1
Enoise relative to ( 1) (empirical)
1.0
(O. (analytic)
0.9
US (empirical)
U(PP~1), n p (analytic)
0.8
RFF (cos with bias)
RFF (sin and cos)
Lower bound
0.7
100
104
102
Number of points
Figure C.6: Estimated ENoise for the two versions of random Fourier features described in Ap-
pendix I relative to Pz = 2(23()) ((P-(()))))) )) We use d = 10, Px = No0, Ia), 30 and the weight vector
distribution Ps- (0, Ia) (cf. Appendix 1}.
given by
(11 w( VV
5o Rdd R
w
'For random NN feature maps Theorem one can interpret the linear regression being an layer on top the neural network, and therefore the last layer of the feature map should contain an activation function. For NTK feature maps, one can instead interpret the linear regression as performing a "linearized" training of the whole NN, and the whole NN usually does not contain an activation function in the last layer.
17

---

Published as a conference paper at ICLR 2021
10
Polynomial kernel
Lower bound
10a
Enoise (noise- induucdducdddd error)
10
10
10"
10-1
10
10
102
Number of points n
Figure C.7: Estimated ENoise for the polynomial kernel (cf. Proposition 8 with d = 3, m 4,
== 1, Px = NO0,, La), resulting in p (m++d)
35.
with do = d = 4. 6, d2 = 1 and W (OO, 1) ii.d. Our input distribution is again Px = NO,, Ia). The NTK feature map then defined as
6 R - 00 (x)
where p = 6 1 30 is the number parameters in Note that moving the variances Vi outside of the ( does not affect the forward pass but only the backward pass (i.e. the derivatives).
While we have theoretically established the properties (FRK) and (COV) for such feature maps, we can do this experimentally for analytic activation functions like sigmoid, tanh, softplus and GELU: Since the random NTK feature map derivative of the analytic random NN feature map, also analytic. By Proposition 9 if (FRK) does not hold, then for every fixed 0, the range of &3 must be contained in proper linear subspace of RP, and therefore Z = (x(X) never has full rank for n 2 p. this case, the singular value (2) would be zero, and even accounting for
numerical errors, the "inverse condition number" 5x(2) Z)
(z) should most be of the order of 64-bit float
machine precision, i.e. around 10-16 16 However, among 10a samples of Z for := 90 2 30 p. the maximum observed "inverse condition number" was greater than 10-3 for all of the activation functions sigmoid, tanh, softplus and GELU Hence, by Proposition and PProposition 9 we can confidently conclude that (COV) and (FRK) hold for all almost surely over for this network size and these activation functions.
Estimation of ENoise In order to estimate ENoise. we proceed follows: Recall from Section that ridgeless regression is the limit of ridge regression for Y O. We use small regularization of 10 in order improve numerical stability. Also for numerical stability. use singular value decomposition (SVD) Z U diag(s1,.. V with k min(n, n, p} as in Appendix B
The regularized approximation Z is then
Z ~ (Z' Z - V diag
UT
$
"We p since this usually improves the "inverse condition number" of Z.
18

---

Published as a conference paper at ICLR 2021
We can then estimate
of (s} + A)2
tr((Z*)' (((())"="") (Z*) Re tr VVdiag
V Σ
(4)
(5) +
x)2
We can then obtain m 10 (non-ReLU NNs. polynomial kernel, high-variance random Fourier features) or m = 10 (all other empirical results) sampled estimates for tr((Z*) Σ in order to obtain a Monte-Carlo estimate tr((2*) TEE+) by repeating the following procedure m times:
Sample random parameter 0.
(2) Sample random matrices X E Rnxd and X R'xd I = 10 with i.d. Px-distributed rows.
(3) Compute Z ~ () and Z (x( ()
(4) Compute the estimate Σ = | Z Z.
(5) Compute regularized estimate of tr tr((Z* ΣZ*) using the SVD of and Eq. (4)
For performance reasons, we make the following modification of step (2) and (5): Since we perform the computation for all E [256]. we sample
256xxd and then, for all E [256], perform
the computation for using the first rows of Z. Hence, the estimates for different n are not independent. In Figure C.3 we perform an analogous optimization for p by taking the first p E [256] of the d3 = 256 output features in Z.
Curious ReLU results The curves for the ReLU NNs and ReLU NTKs in the underparameterrized regime p 2 n may seem odd. The locally almost constant "platcaus" are presumably an artefact of the non-independent estimates for different Seccion 5] networks with ReLU, ELU or SELU activations do not satisfy (FRK). It seems plausi- ble that, since both "halves" of the ReLU function higher chance than SELU or ELU networks to be initialized with "bad" parameters that are likely generate "degenerate" feature matrices Z that do not have full rank full rank for some >> p. When inspecting the data underlying the plots, the estimate of ENoise for ReLU networks in the underparameterizeed regime seems to dominated by few outliers. It seems that the distribution of tr(( (2+) ΣZ+) for ReI.U networks is often so heavy-tailed that computing more Monte Carlo samples does not significantly reduce the estimation uncertainty.
explained in the last paragraph. As discussed in
linear, ReLU networks have a significantly
= p and only become
in the overparameterized case in Figure C.2. we regularize both matrix inversions on the right-hand side as above: For symmetric matrix A E Im we use symmetric eigendecomposstion A = U diag(s1..... 8m 8m)) and approximate
Whitening For computing B((WW = =
A ~ U diag
$1
Sm s
U
$ +
+
Optimization For our optimized feature maps in Figure with p 30, we use neural network feature map with do d = 30, d1 d2 = 256, d3 use NTK parameterization and zero-initialized biases, leading to
30 and tanh activation function. We
(x (b) V222 1/2 w (b V.
1/2 W (b
V.
W (())))
with independent initialization w:(h) AO 1), 60 = 0. As the input distribution, we use Px (O0,,) For given O, let Eg = depending on O. We then optimize the loss function
-.c. define the second moment matrix Σ as
L(e) = Ex (x(( Eooo(X)))
2018) with learning rate that linearly decays from 10-3 to 0 over 1000 iterations. In order to approximate L(0) in each iteration, we approximate Eg using 1000 Monte Carlo points and we draw 1024 different realizations of X (this can be considered as using batch size 1024). We also use a regularized version as in Eq. (3). but we omit the SVD for reasons of differentiability.
using AMSGrad (Reddi et al.
19

---

Published as a conference paper at ICLR 2021
D A COUNTEREXAMPLE
Example D.1. Let p 2 Consider the uniform distribution Pz on an orthonormal basis { ep} C RP. Then, Σ p. Σ e;e; I1 and hence (COV) is satisfied. However, from Proposition 6 is easy to see that for any n 2 2. (FRK) is not satisfied. Indeed, if the vector e; occurs m, times among the samples 21, J., then Z Z = diag(m),... mp). Assuming Var(y|z) = 0² 1 for all
then obtain from Theorem 3 with the convention = 0:
- Ex ur( 1r -Ez tr((2' 2)*)
ENoise = Ez lr( E2*
1 m1;
1
IE
P
m1
where my follows a binomial distribution with parameters n and Using m] - E1 1, easy to see that the lower bound violated for some values of n. For example, Figure D.I shows that for = 30, the lower bound is violated in large region, especially in the overparameterized regime The underlying reason that the function + is convex on (0, oo). but not on [0, oo).
p'
If Z has singular values 8,, the pseudo-inverse Z has singular values - If 8; = 0 is possible, we cannot use a convexity-basee argument anymore.
Lower bound
Enoss moise-inducedd error)
10
Counterexample
10
10
100
10 Number of points n
10a
Figure D.1: The counterexample given in Example D.I for 30 often has lower Exoise than the lower bound from Theorem 3, but violates its assumption (FRK). For the counterexample, ENoise was approximated as explained in |Example D. using 106 Monte Carlo samples for each n. We assume Var(y|z) = almost surely over z.
Remark D.2 (Histogram regression). The distribution Pz in Example D.1 may seem contrived at
first, but such distribution arise in histogram regression (cf e.g. Chapter 4 in Györf et al.) (002). For example, suppose that Px is supported on a domain D C Rd and this domain is partitioned into disjoint AI,..., Ap. Then, performing histogram regression performing ridgeless linear regression with the feature map Φ Rd RR with ((x) e, if E A, If all partitions are equally likely, i.c. (x.))) = 1/p for all (1,..., then Pz is the uniform distribution on {Ei,...,e,, ep} as Example D.
this partition equivalent
E FULL-RANK RESULTS FOR RANDOM WEIGHT NEURAL NETWORKS
In the literature on neural networks with random weights (Schmidt et al. 1992) and the later virtually identical Extreme Learning Machine (ELM) (Huang et al. 2006), properties similar to (FRK) have
For (FRK) holds and it easy see that the lower bound holds exactly in this case.
20

---

Published as a conference paper at ICLR 2021
been investigated for random neural network feature maps. In the following, review the relevant approaches known to us and explain why most of them are flawed.
First, Sartori& & Antsaklis (1991) state result where the assumptions not clearly specified, but which could look as follows:
Claim (aaroori & Antsaklis (1991), informally discussed after Lemma 1). For n. p. consider single-layer random neural network with weights ( E (n-11)xd and signum activation that
appends a to its output:
6
(a W (0) x),
!f at,..... ,i,
nn E TRd are distinct, then for almost all W (0) so 6 (X) is invertible.
This claim is evidently false for n > 2. For example, the following argument works for n. 2 3: For T E {-1,0, 0, 1)", let 21 = {w E R2 o(w [(wT=z))))) = Ty for all j}. Then, (1,(-1,0.1)" U,- = Ik" and since (-1,0, 11th is finite, there exists T" such that Uy is not Lebesgue null set. Hence the (n(=1)xxx
set W = { (W(())
least two rows of ( are in Uy- is not Lebesgue null set. But for all (0)) E W, the matrix (x = (o (o(X((()) 1nx1) has two columns equal to T* and is therefore not invertible, contradicting Claim
Second, Tamura Tateishi
(997) state a result where the assumptions are not clearly formulated,
but which could look as follows:
Claim Tamura & Tateishi (1997)). For n = pp consider a Lingle-laee random neural network
with weights W E [R(n-1)x44 1ixd biases (0) E R=-1 and sigmoid activation that appends a 1 to its output:
Φ Ro:R-
(o(W x + ),)), 1).
aaa..... ..... Fn RRd. distinct, then for almost all W and all a < b, there exists b E [a, b)m- such that Φo X) is invertible.
Tamura & Tateishi (997) attempt prove this claim via showing that the curve G : (a, b] is not contained in any (n --ddimensionnl subspace of (o(ww, (0) Tar, + +b)) SE[n]
R", b.
IR,, which would allow them to pick a suitable bias b, for each curve c such that the (6.)) and (1,...,1) 1)" are linearly independent. Although this is part is formulated confusingly, it should work out. The major problem is that under the counterassumption that & lies in an (n 1)-dimensional subspace. they construct an infinite (overdetermined) system of equations involving derivatives of the sigmoid function which they claim has no solution. However, in general, overdetermined systems can have solutions and they do prove why this would not be the case in their situation. Indeed, the only properties of the sigmoid function they use is that it is C and not polynomial, and it not hard see that the exponential function has these properties as well and leads to a solvable overdetermined system since its derivatives are all identical.
This leads us to the next claim:
Claim 3 (Huang (2003). Theorem 2.1). Consider the setting of Claim 2 but with W Raad instead of appending
all feature vectors. If "f,,..,, E RR. are distinct and 0 has a Lebesgue density, then Φe X) is invertible almost surely over 0.
Huang (0033 uses the "proof" by [Tamura& & Tateishi (1997) to show that from any nontrivial inter- vals one can choose (0)), (0) such that Φ (X) is invertible, setting all rows of (0) to be equal. He then concludes without further reasoning that do (X must then be invertible almost surely over
0. This major unexplained step cannot be fixed by a continuity- argument since all b(0) were chosen from the same interval and similarly, all rows of (0) were chosen from the same interval. Since the sigmoid function is analytic, would however be possible to prove this step using the multivariate identity theorem for analytic functions, Theorem H.3] in fashion similar the proof of (d) + (a) in |Propssition 6) The approach pursued in Huang (2003) thus introduces an additional problem top of the problem of Tamura & Tateishi (1997) although this additional problem is in principle fixable.
A similar strategy is reused in the next claim issued in particularly popular paper:
21

---

Published as a conference paper at ICLR 2021
Claim 4 (Huang al. (2006), Theorem 2.1). Clain hoodd for all C activation functtios
Not only does the "proof" Huang al. (2006) inherit the problems from the previous "proofs", but now the result is obviously false as well: For = 0, the matrix de (X( can never be invertible, and for a id, also easy to find counterexamples. Moreover, not sufficient to exclude (low- order) polynomials V.3 in Amann & Escher
For example, the well-known construction (e.g. Remark 3.4 (d) in Chapter 2005)
0 (x) = 11///
2 S x
yields C function that is (-o0, 0] but not polynomial. For this function, it is not hard to see that do (X) would be singular with nonzero probability since there chance that ( x + (0) contains only negative components.
Despite these evident problems and the paper's popularity, Claim restated years later as Theorem I in survey paper by the same author (Huang et al., 2015). 5.. In his Theorem 1, Guo (2018) attempts to disprove Claim However, this "disproof" is also invalid: functions like tanh, Guo (2018) lets 0 to a singular matrix. The problem with this approach singular, the matrices for finite & do not need to be singular. However, this limiting behavior might at least explain the empirical results of Henriquez & Ruz (2017). which find in certain setting with sigmoid activation that numerically, oo(X) usually not full-rank matrix. In contrast, Widrow et al. 2013) numerically reach the opposite conclusion. This is not a contradiction, considering that very small eigenvalues of (x(()) (X) may be numerically rounded zero, and the probability of having such small eigenvalues depends on the chosen distributions of æ and 0.
certain saturating activation in certain fashion, which causes de (X) to converge that just because the limiting matrix is
The only previously published correct result known to the following one:
Lemma E.5 (Lemma 4,4 in Nguyen & Hein (2017)). Lel R - IR be analytic, strictly increasing and let one of the following two conditions be satsified:
(a) a is bounded, or
(b) there exist positive constants P1, P2. P3, P1 such that (a())] S pietst fort and (a(t) s pst + Pa for O.
Let 6e be random NN feature map with biases as in Theorem 10 (b) and let æ1...., Fn Rd be distinct. If p 2 1, then the (p + 1) feature matrix
de (x)) )
(
has rank n for (Lebesgue-) almost all 0.
(without the appended ones in the feature matrix) to a substantially larger class of analytic activation functions As argued above, is not possible to replace the assumption that ar is analytic with o E Co00 and as shown in Remark H.17 our exclusion of certain polynomials for general necessary.
In Theorem H.9
we generalize Lemma E.5
PROOFS FOR SECTION 4
In this section, prove main theorem and corollary from Section 4 Recall from Definiton 2 that if E||==|/ < oo, we can define the second moment matrix
Σ = B=EEZ- [zz]] E RRXx,
and if Σ invertible, we can also define the "whitened" data matrix W == ZΣ 1/2 - whose rows We 1/2 satisfy ww Ip-
'It principle possible to extend our results to the case with appended ones in the feature matrix by choosing the activation function for one of the output neurons to be = 1. As discussed in Rn/emarr H.16 our arguments have no problem handling different activation functions. In this case, would only need to adapt the corresponding Taylor series coefficients in Lemma H.8
22

---

(1) Published as a conference paper at ICLR 2021
Theorem (Main result). Let n 1. Assume that P and satisfy:
(INT) Ey < oo and hence Rp(ff) < oo, (NOI) Var (y x) 2 o² almost surely (MOM) E x 2 < 0c, i.e. E exists and is finite,
(COV) E invertible,
(FRK) E Raxp almost surely has full rank, iee rank = min(n. p).
Then, for the ridgeless linear regression estimator [z, = z y. the following holds:
If 2 n,
(1) ENoise oo tr(((t)))))))))
ΣZ O' )
(TV)
2 0
n1
1
ENoise 2 B² tr (z() E d' tr((") w) (V)
p
P S n,
n 1 p
Here, the matrix inverses exist almost surely in the considered cases. Moreover have:
IJOO)) holds with equality, then (I) holds with equality.
. 1f p or Σ p for some X > O, then (II) holds with equality.
Proof. By (FRK), we only consider the case where Z has full rank. For further details on some matrix computations, refer Appenddix B
Step I: Preparation. Since the pairs (=1, (1,,,........ (Zn, Un) are independent, we have the condi- tional covariance matrix
(ar((11211)
(1)
Cov(yl
= IIIn
Var(yn zxn)
with equality in (1) if (NOI) holds with equality. Therefore,
ENoise
def
Ez (fz. - By 1 1,1z522,.00z) Ez,y, (= 2 y -Eyyzz z y)
B22.Byy12 Z (y F 2
FR 24) ( TZ=)==
=R2,22 T z Cov(g) (Z+) (1)
2 0²Ez,=² "TEzz=TZ''22 Tz=((=*
dZ tr((2 tr((2*)] 2z z²)
o²Ez ur(( "
Step 2.1: Reformulation, underparamettrrzed case. In the case I n, we have z ( Z) z thanks to (FRK) and thus
tr((2* TZ = tr (x (2 121 tr(2 122 1 tr((W W)-1).
Step 2.2: Reformulation, overparameterized case. In the case > n. we have z Z (ZZ )-1 thanks (FRK). For AIp, we can show tr((Z)) "/==z* tr(( W ) similar to Step 2.1. For general Σ, we can obtain lower bound by "removing projection": First, let
S (Z
Ez (2z")
(ZZ
A = 11/2
Now, since Z and Σ have full rank, can compute
S-1 zz T (ZΣZ
zz WAWAAAA A
Since A(A A)-1A -'AAA is the orthogonal projection onto the column space of A, we have S-1 = WW and hence (s(S-1) < (WW by the Courant-Fischer-eee Weyl theorem. This yields
tz(( Ez TZ = tr(S) = Σ
A (S) Σ
i=1
i=l
23

---

Published as a conference paper at ICLR 2021
An+1- - tr((WW))-)
X (WW
For p. A(A A)-1 A projects onto p-dimensional space and is therefore the identity matrix, yielding equality.
Step 3.0: Random matrix bound, p or 1. If n p w; we is scalar and we have
1
1
1
Etr((WT -) W
E
W
Ei=1 w Ei=1 w
Ei= to tr(Rw;nc,))
n
12 + by Jensen's inequality. Similarly, for p 2 n 1, we obtain
Etr (r((WWT)e
n
wi w1
Ewj w1 tr(Eer()))
p
p +
Step 3.1:
Random matrix bound, overparameterized case. We first consider the overparameter- ized case p 2 n 2 2 and block-decompose
w w W 2
w W
W
w W
(R(++(11))x
WWT
W2W,
Since Z has full rank, W has full rank. Because of n S it follows that WW > 0. Therefore,
(wwW))-)) =[w) w1 wi W ( (2w1) [w] (I, P2)w1)
where
P2: (W2W?) W2 R2x
the orthogonal projection onto the column space of W Thus, P2 has the eigenvalues 1 with multiplicity 1 and 0 with multiplicity p- (n 1), which yields tr (2) = 1. Since the z; are stochastically independent, wy and W₂ 2 are also stochastically independent and we obtain
_wi (I, P2]w: = Etr((Ip (2,, w ( Etr(I, P2) = p- 1 - n2
Using Jensen's 's inequality with the convex function (0, 00) - (0, o0), x + 1/x, we thus find that
E (wwW))+)) E [w) (I, P2)w1)
1
Ew (I, P2)W1
p p+1-n n
Since tr(( W
( (WW i and all diagonal entries can be treated in the same fashion (e.g. via permutation of the w.), it follows that
(ur((WWT))t) p
Random matrix bound, underparameterizeed case. In the case n 2 p 2 1, we follow the proof of Corollary 1 in Mourtada (2019), which can be applied in our setting as follows: Introduce a new random variable Wn+1 such that wI...., un+1 are i.i.d. Then,
Step 3.2:
E (t W) = Ew tr((W W) W w w w I+1)
Ew W T W) wwtt
Now, Lemma in Mourtada 2019 uses the
formula to show that
i l En41
T ( W) (
wat1 = I
with the so-called leverage score
iut w T ( W wn+1 tw - -wa+1 10,
24

---

Published as a conference paper at ICLR 2021
Since W W wn+1w 2+1
EE= : and since wi,.... Wn+1 are Li.d., obtain
Blatt
Etr
w,w!
Wn+ 1 w
n+1
-1 n+1
E
w; w,
+
p
1 tr (pp
++1
+
Finally, the function (0, - (0, 00), ++
I-x
I-x
is convex, and Jensen's inequality yields
fnt1
Elat1
Eur((W -) IF-
P -+1-p
1
1 Ela+1
Note that is not possible to analyze Step 3.2 like Step 3.1 since the corresponding matrix blocks not stochastically independent.
Corollary 4 (Random features). Let 0 ~ Pe be a random variable such that do Rd - R is a random feature map. Consider the random features regression estimator fx. v.0 x 2 Z
with za == do (x) and Zo == (x( If for Pe-almost all O, the assumptions of Theorem are satisfied for 26 and Z Zō (with the corresponding matrix E Ezg. then
00
p+1-- ifp n
n
Eoosse
isp s
a+1-p
Proof. First, let S n. Since 0 is independent from X, y.
ENoise (Ex.y,0 (z) Z y Eylx 2 y)
= Eo Ex.y (z 3 y
Eg, x )
hearem
Eg0²
p
=
0²
+ 1 1-p
p
The case 2 n can be treated analogously.
G DISCUSSION OF THE MAIN THEOREM
Remark G.1 (Dependence on E). Hastie et al. (2019) discuss that only influences the expected excess risk in the overparameteriize regime. In the following, will illustrate that Theorem even implies that in the overparameterized case, Σ = A yields the lowest ENoise This fact is also discussed in Muthukumar al. (2020) in slightly different setting. Note that since Px is unknown in general, Σ is also unknown in general.
Assume that (NOI) holds with equality such that have ENoise =o2 tr((2t)TTT ( TEZ+) by Theorem 3 Suppose that perform linear regression on the whitened data 2 E --1/22 Then,
Ž 1/2 W Σ = 2g T Σ 1/2
1/2 [Ezz T Σ Σ-1/2 1p:
W = 2 - 1/2 = W
In the underparameterized case p S n, we then obtain
E (r((2))T22) = ir( (r(( W)-1) Ez (rr(((WWW) ( W)-1) = Ez (r(((t) ((=)
Therefore, whitening the data does not make a difference p S n. contrast, for p > n, we only know
E2 tr((2
ΣΣ
Ez tr (WWTTWW-
Ez tr( (r(WWWT--)
< Ez tr(( TE
25

---

Published as a conference paper at ICLR 2021
since (II) holds with equality for whitened features. From Step 2.1 in the proof of Theorem 3 is obvious that (II) in general does not hold with equality. Hence, in the overparameterized case p n, whitening the features often reduces and never increases Noise. Since &Noise is just lower bound for the expected excess risk, whitening does not necessarily reduce the expected excess risk.
This phenomenon also has different kernel-based interpretation: Under the assumptions (MOM) and (COV), we can choose an ONB ui...., U, of eigenvectors of E with corresponding eigenvalues Aiy.... Ap > O. If z = ((x) and k( x') = ((x)) "((x),
we can write
k(z, x') = x(x))
Σ u.u 6(x') Σ (x)(()))s))))
(5)
where the functions th : I2d + R. x
vx, ue Φ(x) form an orthonormal system in L2(Px):
U 1 V.J,,
X uu, uj d:j- (6)
Eg thy (z))))))))
(L
u Euj VA.
Therefore, Eq. (5) is a Mercer representation of k and the eigenvalues A of E are also the eigenval- ues of the integral operator T3 (2(xx) - L2 (Px) associated with k:
Σ "
(Tf)(x)= =
We can define a kernel i with flattened eigenspectrum via
M( xt) Σ (ar()))))()
Its feature map x -> (1)(())) by Eq. 66 satisfies Σ p. By the above discussion, Nosse (k) < (Noise(k), However, this needs to be taken with caution: Assume for simplicity that for independent x, ã. the feature map @ yields d(x), o()) N p pp). Then, k(æ, k(z,x) x) = but Ek(x, z) = 0
and Var klr, ()) = + Em= Bu. = $. In this sense, for p - oc, converges to the Dirac kernel k: x)) = 5 2 which satisfies Exoise = O but provides bad interpolation performance ff # O.
The next lemma and its proof are an adaptation of Lemma 4.14 in Bordenave & Chafai 2012).
Lemma G.2. For E [n], let W-; == Span (1 1 E [n] \ (i)). Then, under the assumptions of Theorem in the overparameterized case p 2
tr( ) = Σ (w;; W-
(7)
Proof. The case is trivial hence let n 2 2. In Step 3.1 in the proof of Theorem 3, since Pa is the orthogonal projection onto W-1, we have
i (I, P2) ww 12 P2 Pythugoras dist(wi, W-1)²,
where dist(w,, w1, W-1) is the Euclidean distance between wT and W-1-
Remark G.3 (Is (SP-11) optimal?). From (I) in Theorem it is clear that the best possible lower bound for Exoise under the assumptions of Theorem gliven nI, 2 1 is
ENoise
inf
Ez-ry tr((Z*) TZ*).
(8)
Distribution I22 on R." satisfying (MOM), (COV), (FRK)
Here, want to discuss the hypothesis that the infimum in Eq. 8 is achieved (for example) by Pz = (SP-1). Figure shoows that we were not able to obtain a lower Exoise by optimizing a neural want to discuss some theoretical
(Figure network feature map to minimize Exoise- In the following, evidence as to why this is plausible in the overparameterized case 2 n. Lemma G.2 shows that Step 3.1 of the proof of Theorem has a distance-based interpretation. In this interpretation, Step 3.1 then applies Jensen's inequality to the convex function (0, 20) + (0, oo), + 1/r using
E Ediis(wu,, W p + n
9
26

---

Published as a conference paper at ICLR 2021
We use this perspective gain insights how distributions Pz with small ENoise in the over- parameterized case p 2 n look like. First of all, Remark G.I suggests that for minimizing ENois in the overparameterized case, Σ should be a multiple of p. which is clearly satisfied for (SP-1) by Theorem IT] Since the lower bound obtained from (9) is independent of the distribution of W, minimizing E (ar((WWW))) (WW")->> amounts to minimizing the error made by Jensen's 's inequality, which essentially amounts reducing the variance of the random variables dist dist(w;, WL+). We can decom- pose (ws W- ||wx:|2 (list(w:/1) //:l///:/2222222 W-i). where dist (w:/ ///////,//22 W-:) only depends on the angular components w,/ll /|, ll2 for j E [m]. This suggests that for "good" distribution Pw,
the radial component |ee/|2 should have low variance, and the distribution of the angular component w should not contain "clusters", since clusters would increase the probability of dist(w;, W-+) being very small.
Clearly, both points are perfectly achieved for Pz (SS-1).
H PROOFS FOR SECTION 5
In this section, we prove all theorems and propositions from Section 5 as well as some additional results.
H.1 MISCELLANROUS
First, we prove statement about conditional variances.
Lemma H.1. the setting of [Thoormm 3 we have
Var(ul=) IE [(Var(y)=))]=)+ + Var(B(y|z)]2z)
Hence, if Var(ylæ) 2 o² almost surely over æ. then Var(ylz) 2 o² almost surely over z. The converse holds, for example, if is injective.
Proof. For properties of conditional expectations, we refer to the literature, e.g. Chapter 4.1 in Durrett (2019). Since <(x) is function of æ; we have E[-|2] E[E(11=)] 22]. Thus,
Var (w/=) E [(v |(() =]
E ((v [By (=) + (E(y]æ)) - E(E(v|x) 2))
E E ((v [[yl)))²
E E ((y [(yl=)) E(E [z) xx) |>|
+ E E ((B(y)=) ((E()) x)) =]
For the first term, we have E ( (y E(y [()) Var(v/#) by definition. The second term is zero:
Since E(y| - ((E(g)=)(z) is already function of æ, we have
E ((v [(yl=)))(((((()])) E(E(vl=)==))er = E ((v (z)l=)) (E(yl=) EEE(v/ x)) ==)=)) (E(y)<z) (B(y))) (((())=)))) 0.
Finally, the third term is by definition equal to Var(E(y xx) 12). Therefore,
Var(ul=) = [[Var(y]=)\=>) + Var(B(g|==))z)
If & is injective, then æ is also function of z and we obtain Var(yl=) Var(ylz).
Our main ingredient for analyzing analytic activation functions will be the univariate and multivari- ate identity theorems.
Theorem H.2 (Identity theorem for univariate real analytic functions). Let f : : + R be analytic. If f is not the zero function, the set N(f) = {2 E f(z) = 0} has no accumulation point. In particular, Nf) is countable.
27

---

Published as a conference paper at ICLR 2021
Proof. See e.g. Corollary 1.2.7 in Krantz & Parks (2002) for the first statement. If [f((() is uncount- able, there exists & E 2 such that + ( is also uncountable, hence it contains a strictly increasing and bounded sequence of points, and the limit of this sequence is an accumulation point Nf).
IT
Theorem H.3 (Multivariate version of the identity theorem). Let f: Rd - R be analytic. If f is not the zero function, then NJ) = { E R f(x) = 0} is a Lebesgue null set.
Proof. Although less well-known than the univariate version, this multivariate version has been proven several times in the literature. For example, different proofs are given in Section 3.1.24 in Federer (1969), Lemma 1.2 in Nguyen (2015) and Proposition 0 in Mityagin (001)). More proof strategies have been hinted at in Lemma 5.22 Kuchment (2013). Here, we provide an elementary proof following the proof strategy briefly mentioned at the beginning of Section 4.1 in Krantz &
Parks (2002).
Let A be the Lebesgue measure on R' and let X = X We prove the statement by induction on 1 For d = 1, if ((V(f)) > 0, then ((f) is uncountable and hence f = by (hhoorm H.2
Now, let the statement hold for d - 1 2 1 and assume xL((()) > 0. For R, define the functions fa Rd-1 R. fa() = f(a, x). Then,
< X(((F)) [ dx x0-1 x)
= -/6 (A(a))
follows that the set U = ta E R ( > - satisfies X(U) > 0. By induction, we can conclude that the function
for all U, we have fa = O. Then, for all x E fa : R + R. a + f(a, x) satisfies N((a) 2 U and therefore {(V(f)) 2 A(U) > 0. Using the case d again, it follows that fa and therefore f(a, x)) for all R and E Rd-1
The following lemma provides some intuition about null sets for readers less familiar with measure theory. Recall that a property Q holds almost surely with respect to measure on Idd if there exists a null set N, i.. a measurable set with P(N) = O, such that Q(x) holds for all x E IRd N. Lemma H.4. Let X be the Lebesgue measure on R and let P be a measure on Rd with a Lebesgue density function (i.e. probability density function) p. Then, null set with respect to X² is also null set with respect to P. The converse holds if p(x) + 0 for (almost) all æ.
Proof. A well-known fact from measure and integration theory states that if measure μ has density with respect to a measure v. then æ-null sets are also y--ull sets. Setting μ P and v = X yields the first fact. p(x) * for (almost) all æ, then μ X has density 1/p with respect to P. and hence the converse follows.
Proposition 6 (Characterization of (COV) and (FRK)), Consider the setting of Theorem 3 and let FRK(n) be the statement that (FRK) holds for n. Then,
(i) Letn Z 1. Then, FRK(n) iff P(z E U) for all linear subspaces U C RP of dimension min D} 1.
(ii) Let (MOM) hold. Then, (COV) holds P(z E U) < 1, for all linear subspaces U C IR of dimension p-
Assuming that (MOM) holds such that (COV) is well-defined, consider the following statements:
(a) FRK(p) holds.
(b) FRK(n) holds for all n 2 1.
(c) (COV) holds.
(d) There exists a fixed deterministic matrix X E RRpxd such that det(@ (X)) )) # O.
We have (a) < (b) = (c) = (d). Furthermore, if x E Rdd has a Lebesgue density and Φ is analytic, then (a) (d) are equivalent.
Proof. Step 1: Prove (i) and (ii).
28

---

Published as a conference paper at ICLR 2021
(i) Denote the n (stochastically independent) rows of Z by 21..... Zn- First, assume P(z U) > O for some subspace U of dimension min [2 1. Then,
P( rankk 2) S min pn -1) 2 P......... 2n E EU)
00.
For the converse, it suffices to consider the case S p since if > p and if an arbitrary p x submatrix of Z E RR'P almost surely has full rank, then Z also almost surely has full rank. We prove the statement for p by induction on For 1, the claim is trivial. Thus, let n > and let 21,..., 2n be the (stochastically independent) rows of Z. Assume 1. Then, also have P(= E U) = 0 for all linear subspaces U S Iº of dimension n 2 and by the induction hypothesis, we obtain that 21..... 2n-1 are almost surely linearly independent. Hence, almost surely, 2.....,
P( E U) 0 for all linear subspaces U TRP of dimension
. nn are linearly independent iff 2n & Un- = Span æ 2 2n-13 Then, since nn and - are stochastically independent,
P(Z Rx has full rank) P( ,(2,,,.,,) are linearly independent)
P(zn $ $nn-1)= = /f Lus
= =PPllzn Pz & Un-1) dP(Un-1) = 1 IdP(Un-1)=
For the case p S (i) is also proven after Definition in Mourtada (2019). (ii) If (COV) does not hold, there exists a vector 0 * v E Rp with v Ex 0. hence
0= v (Eez)) 1) v = E(v" [[uT=)] x)²
and therefore almost surely orthogonal to v. If U the orthogonal complement of Span(v) in IR,, then P(z E U) 1. For the converse, there exists a (p 1)-dimensional subspace U with P(z E U) 1, then
again take vector 0 * E Rº that is orthogonal to U, reverse the above computation and obtain v Ev = hence (COV) does not hold.
Step 2: (a) <> (b). The implication (b) (a) is trivial and the implication (a) + (b) follows immediately from (i).
Step 3: (b) (c). This also follows from (i) and (ii..
Step 4: (c) + (d). We will prove by induction on n that for all n E {0, {O.....P). there exist
EI,..., E d such that ((x1)..... o(x,) are linearly independent. For = 0, the statement is trivial. Now assume that the statement holds for TI..... In-1. where 0 S n 1a-11- 1 0(xn-1)) satisfies P(ò(x) E U) 1,
1. Since
(COV) holds, by (ii) the subspace U == Spanfo(z1), hence there is Fn such that x, & U and for this choice, ((x1), ((.)),...,d ((x,) are linearly independent.
Finally, the statement for p yields the existence of X Raadd such that ((X) has linearly independent rows, which implies ( + 0.
Step 5: Analytic feature map. Assume that ø is analytic, has Lebesgue density and (d) holds.
Let = p. For X Roxd, consider the analytic function f(X) == det(((()) (The determinant is analytic since it is polynomial in the matrix entries.) Since (d) holds, Theorem shows that
((X for (Lebesgue-) almost all X. Since has Lebesgue density and X has independent a-distributed rows, X has a Lebesgue density. Therefore, f(X) o almost surely over X, hence (a) holds.
Proposition 8 (Polynomial kernel), Let d 2 1 and c 0. For æ, x E Rdd define the polynomial kernel k(æ,, T) == (x: T + c) Then, there exists a feature map á Rd - RP, p (m++d) such that:
(a) k( (x d(x) ((z) for all x, Rd, and (b) if E Rd has a Lebesgue density and we use z = 5(x), then (FRK) is satisfied for all n.
Proof. Let M -(mp...,maat) E No+1
mi +
+ m4+1 = =m] and for m
(ma...., m4+1) E let
C(m) := m1
m
md+1
29

---

Published as a conference paper at ICLR 2021
be the corresponding multinomial coefficient. Then, [M] (mitee p. Define the feature map Φ IRd
Rº by
((x)) = ((C(()) ... 2 (Vo)murt
mEM
(a) We have
((x) 6(()) (xx)
Σ ((m)(1111) (z.()))))))))))) c
MEM
(21 +... 2gHd c) = k( Ø))
(b) Assume that æ has a Lebesgue density. Let U be an arbitrary (p 1) -i-imennionnal linear subspace of IP, Then, there exists * 12 such that U (S)an(v))) Since the monomials z7 ... and for m E MM are all distinct, the polynomial
v x(()== = Σ
MEM
is not the zero polynomial. By the identity theorem TThorem H.3 since a has Lebesgue density and since polynomials are analytic,
P()(œ) E U) P(u x(x) 0) 0.
Hence, Proposition 6/shows that (FRK) satisfied for p and hence for all n.
We want to remark at this point that the proof strategy of Proposittinn 8 where the identity theorem applied to the functions v. o(x) for all 0 a E IR,, does not work for random feature maps: The statements
For all 0 # E IR for almost all for almost all 0, v de x)) For almost all for all 0 + v E IR" for almost all æ, v Φ0 x # 0
not equivalent since in the first statement, the null set for 0 may depend on v, and the union of the null sets for all v an uncountable union. Perhaps the simplest counterexample is n 2, 0, which satisfies the first but not the second statement. For rescue,
0 (0, I2) and do (x) we can replace the uncountable analytic function family (æ + v 60 ) by the single analytic function (0, X) + det( (X)):
Proposition (Random feature maps). Consider feature maps 69 Rd Rp with (random)
parameter 0 R Suppose the map (0, x) + (0(x)) is analytic and that O and independent and have Lebesgue densities. If there exist fixed O RR, X RRxd with det( (X)) # then almost surely over 0, (FRK) holds for all n nor r (x))
Proof. Consider the analytic map (0, X) + det (bgg X)). Suppose there exist O E R and X Rexd with (ct())())) # Then, Theorem H.3 tells us that det(o(e, X)) + for almost all (0, X). This implies that for almost all 8, we have for almost all X that det()e(X)) # 0. Since by assumption, has density, this implies that almost surely over 0, there exists X such that deh X)) * 0. Since all de are analytic, the claim now follows using (d) + (b) from Proposition 6 (The proof (d) = (a) + (b) in Proposiitio does not require (MOM).)
H.2 RANDOM NETWORKS WITH BIASES
In order to prove (FRK) for random deep neural networks, we pursue slightly different approaches for networks with bias (this section) and without bias (Appendix H.3). In both approaches, consider a property related to the diversity of the æI...., Rd and proceed as follows:
Ensure that random projections of the æI...., 2n almost surely preserve the diversity property, such that is sufficient to consider the case d= =. (2) Propagation:
Projections:
Using the projection result from (1), prove that if the inputs layer have the diversity property, then the outputs also have the diversity property almost surely over the random parameters of the layer.
30

---

Published as a conference paper at ICLR 2021
(3) Independence: Prove that if the inputs to the last layer have the diversity property and 7t p. then the outputs of the last layer are almost surely linearly independent.
Our main tools will be the identity theorems for analytic functions (Thcorem H.2 Theorem H.3) expanding a into its power series around point and the Leibniz formula for the determinant matrix, which is based the permutation group S,, on [n].
We consider two diversity properties:
(a) The first property is that .1...., En distinct. This is the weakest possible diversity property. However, cannot always be used for networks without (random) biases: For example, if a is even function and -y for some + j, the propagation property is violated. As another example, (0) = 0 and a; = 0 for some i, the independence property is violated.
(b) The second property, which works for networks with and without bias, is the property that 31. In are independent nonatomic random variables.
Using the first property yields shorter proofs and slightly stronger theorem for networks with bias, Theorem H.9 If we only care about probability distributions Px on that almost surely generate distinct :1,....;.. Zn, these probability distributions are exactly the nonatomic distributions. Hence from the viewpoint of probability distributions Px on at, which we take in the main part of the paper, the first property (a) does not provide benefit over the second property (b) except for the shorter proofs.
The advantage of having biases is in being able to choose the point in which a is Taylor-expanded. The following lemma shows that this choice enables us make certain coefficients of the Taylor expansion nonzero:
Lemma H.5. Let 2 1. Let a: R + I. be analytic and not polynomial of degree less than Then, there exists E IR such that the Taylor expansion
(xx)
ax 6)R
k=
of a around b satisfies ou...., am +
Proof. Since a is not polynomial of degree less than m, neither of the derivatives o("),..,, (m))
the zero function. Since of these derivatives are analytic, the set
U
(b) =
A=
(by Theorem H.3) finite union of Lebesgue null sets and hence Lebesgue null set. Hence, there exists b E IR such that (b) * O.... ((m)(() * 0. This implies that the corresponding coefficients ag...., am in the Taylor expansion around are nonzero.
We now prove our three-step program (1) (3) from above for the distinetness property. Lemma H.6 (Projections of distinct variables). æf .i....,, Tn E Rd are distinct, there exists Rd such that u." æ1,..., u xa are also distinct.
Proof. We essentially follow the corresponding proof in Lemma 4.3 in Nguyen & Hein (017). By the identity theorem Theorem H.3 the functions
fiz Rd R. + u
x; TT; 2uu x;
for i.j E [n]. # j are nonzero almost everywhere, hence there exists E R such that T x ær.... u Fn are all distinct.
Lemma H.7 (Propagation of distinct variables). Let R R be analytic and non-constant. I En E Idd are distinct. then for (Lebesgue-) almost all (W, ,b) E Roxd R., the vectors (War wa; + b) (with applied element-wise) are also distinct.
31

---

Published as a conference paper at ICLR 2021
Proof. Step 1: Bias. By assumption, is not polynomial of degree less than 2. By Lemma H.5 there exist (az)k20. b and E > 0 such that ag. a1 * 0 and for all x E R with <
(xx)
Σ km 0
as(a b)*
Step 2: Weight. By Lemma H.6 we can choose u E Red such that u æ1.-... u 2n are distinct.
Now, consider i,j n. with * j. The function
fiz : R + R A +
a(Au' x. + +b o(Au 2j + b)
satisfies
(1)(A) Σ ana(u ax)* (u 2. (u)ary))))))))))))))) )
for sufficiently small |A|. Here, the coefficient ag as((u) xx)****** (u x; x²)}* ) is nonzero for k and hence fig is not the zero function. Using the identity theorem again (as in the proof Lemma H.6 we find that there exists À R with (A)(A) + for all i. E [n]] with + j.
Step 3: Generalization. Now, choose
Au
W
=
E Ipxd
b =
E R
Au
Then, by construction, the first components (o(Wx, + b)) for i E [ri] are distinct. Hence, the analytic function
W W) II ((o(Wa, + b)); (o(Wa, + b)))
(.E
the function. By the identity theorem Theorem H.3), for (Lebexgue-) almost all (W, b), the first components of the vectors a (W (Wa, +b) are distinct, and therefore also the vectors themselves distinct.
Lemma H.8 (Independence from distinct variables), Let 2 1. Let R + E be analytic but not a polynomial of degree less than p - 1. If I1...., Tp E Rd are distinct, then for (Lebesgue- almost all W Ixxd and b RP, the vectors oWWar a + b). x + b) are linearly independent.
Proof. Step 1: Preparation. By Lemma H.5
there exist (ax)u20, b E IR and > such that [ b <e
a0 ap-1 of and for all x I with
o(x) Σ (
By Lemma H.6 there exists E Rd such that x; u Ø; for i E [p] are all distinct. Using the fact that Vandermonde matrices of distinct z; are invertible and using the Leibniz formula for the determinant (with the permutation group Sp (p]). we obtain
D3 =
Σ (m iT
= det
F 0.
(10)
KES,
p
Step 2: Determinant expansion. Define the analytic function
(owix + b)
(wp21 +b)
f RD + R. w + det
(ww + b)
awppp + b)
32

---

Published as a conference paper at ICLR 2021
For small enough ||w||2,
use the Leibniz formula for the determinant to write
f(w) =
Σ
sgn
iT
II
an (W)Jx(s)) )
TES
1=
0=0
E
Ok w. x =T(()
i=1
Σ
II
ak;
Σ TESP
sgn
II
ke m(s)
my
kp.0.
1=1
For k; = find the coefficient of w
up
be
P
I
ok;
Σ
(gg(T))
(i)
D2 X0,
SESP
hence / not the zero function and there exists w such that f(w) + 0.
Step 3: Generalization. Consider the analytic function
a (W æ + b)
g W. b) = det
a (W Tp + b)
When setting W wu T E Rxx and b (b...., b)T E HR we obtain from Step that g(W b) f(w) * O, hence is not the zero function. But then, by the identity theorem Theo- rem H.3), 9 is nonzero for (Lebesgue-) almost all (W.b) b).
Theorem H.9. Let p, d 1, let IR IR be analytic but not polynomial of degree less than max(1,p 1) and let $1...., Dp E Rd be distinct. Let 2 and dy = d, -dd-....,dL- 2 1, = p. For Morle E (o..... 1..1-11 },, les w(l) (TRd44xxd xdi and (1) E TRd++1 be random variables such that = (w
(L--1) (0) ....,,(L- b(l-1)) has a Lebesgue density. Consider the random
feature map given by
60
x (L), where =++1):= (( + (1)
Then, almost surely over 0, (0)))), (xp))) are linearly independent.
Proof. By Lemma H.4 it suffices consider the case where 0 has standard normal distribution, since a standard normal distribution has a nonzero probability density everywhere. Especially, in this case, all weights and biases independent. Using Lemma H.7 and that is non-constant, it follows by induction on / ,O....,L- L 1} that क (1) Zp are distinct almost surely over 0. But (L-1) are distinct, then 2z(") ..... f linearly independent almost surely over by Lemma H.8. which is what we wanted to show.
if x (L-1)
H.3 RANDOM NETWORKS WITHOUT BIASES
As discussed at the beggining of Appendix H.2 we will now consider the property of having inde-
pendent nonatomic random variables æ1..... Fn. We will again consider projection and propagation lemmas first.
Lemma H.10 (Projections of nonatomic random variables). A random variable x E Rd is nonatomic iff for (Lebesgue-) almost all u Rdd, u T nonatomic.
Proof. Step 1: Decompose into subspace contributions. For h E (O....,d). let
Sa = (w V d V linear subspace of Rd dim V k)
33

---

Published as a conference paper at ICLR 2021
be the set of k-dimensional affine subspaces of R.. Let Au == (A Su Px(A) 0}. which cor- responds to the set atoms Px. We then recursively define "minimally contributing subspaces" for k [d]:
A = (AES, S (x(4) 0 and for all Á Sk-1 with Ā C A, Px(A)= 03
We can define corresponding sets of "annihilating" vectors as follows: For A = w + V E Sg. let A y+ {u [ for all E V. uu = 03. This is well-defined since is independent of the choice of wc Define
d
u = UUU++ A+
K=
N = {u E Rd is not nonatomic).
We want to show 21 N.
Step Show U N. Let A Let
V E As for some & {O...., d3 and let A Then, 0 PA() = P( E A) & P(u x (u (ur + v) v EV) P(u u ('ww)
which shows u E N.
Step 3: Show N U. Let u NN, i.c. there exists R such that P(u" x a) 0. Define A = (v E Rd u v = a}. Then, A is an affine subspace of R and we have Px(A) > by construction of A. Among all affine subspaces Á of A with Px(A > 0), there exists one with minimal dimension. This subspace then satisfies À E A Ā and it is not hard to show that A- C A+, hence u U.
Step 4: For all k E {O....,d) .d. A& is countable. To derive a contradiction, assume that A& is uncountable. Then, there exists > 0 such that
A {A E As Px(() 2
also uncountable. Pick an integer n > 1/2 and pick n distinct sets A An E Ac,e. We will show by induction on E [n] that À == A U...U A satisfies
(A Px (A1) +... Px(AI)
which will then yield the contradiction
12 (x(AA) = Px +... + Px(,)) 2 ne > 1.
Obviously, (x,) = (x Assuming that the statement holds for E [n 11, we first derive
Px = Px (A U A +
(x A(+1)
(A1) (A44))) -x( A
For * j. the intersection A, n Aj of two distinet k-dimensional affine subspaces is either empty or an affine subspace dimension less than k. hence the definition of Ag yields Px(A, 0 A,) 0. Therefore,
Px A++1) = Px O A444444 (4: (4:())4))
< (Ax(A A41) +... +....... Px(A A441) = .... +0=0,
which concludes the induction.
Step 5: Conclusion. Let A E Sg, then A is a (d k) -iimension linear subspace of gd, If is nonatomic, the set Ao empty, and hence
==U U R
AE
which means that A is not Lebesgue null set. Conversely, if nonatomic, the set Ag is empty, and therefore
N = = U A+
AEA:
(by Step 4) a countable union of proper affine subspaces of Rd, all of which are Lebesgue null sets. Therefore, / is a Lebesgue null set.
34

---

Published as a conference paper at ICLR 2021
Lemma H.11 (Propagation of nonatomic random variables). Let the random variable I be nonatomic.
(a) For all 2 1 and (Lebesgue-) almost all W Rexd We is nonatomic.
(b) For all E R a x-+ is nonatomic.
(c) If TR R is analytic and not constant, then (xx) E Rd is nonatomic, where is applied element-wise
Proof.
(a) By Lemma H.10 the set A == {u E Rd u is not nonatomic] is Lebesgue null set. If wi is the first row of W. then clearly,
{ E Rexd W x is not nonatomic) S { E Rexd w1 ENT.
where the right-hand side Lebesgue null set. This proves the claim.
(b) This is trivial.
(c) Let z E Rd, Since the function - R, (a:) - 2; is analytic and not the zero function by assumption, its zero set a ({2;)) is countable by the identity theorem, Theorem H.2 Therefore, the set
o ((z}) f E Rd o (
2) o ((=i)) x o- (fzal)
is also countable. Thus, since x is nonatomic, we obtain
((o(()) =) P( ((z)))
Σ
P(==
Σ
0.
EEO (1=))
(1=1)
For proving independence from nonatomic random variables, we need some preparation. In the proof of the independence result for the case with biases (Lemma H.8 Vandermonde matrix appeared. In the case of networks without bias, we will not be able to use Lemma H.5 control the power series coefficients of a, which requires treat Vandermonde matrices with more general exponents.
Lemma H.12 (Random Vandermonde-type matrices). For n 2 1, let I1y... In be independent nonatomic RR-valued random variables and let ki.... kin be distinct non-negative integers. Then, the random Vandermonde-Pye type matrix
ki (X1,... Fnn) =
invertible with probability one.
Proof. By swapping
of V. assume without loss of generality that 0 S kn K2
< kin We prove the statement by induction on n. For n = 1, V is invertible whenever 01 # 0, and this happens with probability one. Now assume that the statement holds for n 1 > 1. For i e [n),, define the submatrices
V V Ka..... (I),...,, 21th,
Since the statement holds for 1, V, is invertible with probability one. Now, fix any such II...., 2n-1 where V,, is invertible. Especially, == det( (, n)) is a non-zero constant. We will show that V is then invertible almost surely over v.. For this, compute the determinant of V using the Laplace expansion with respect to the last row of V as
f(zn) = det(V) Σ (1 pin det(V.) Cr 1-1 det (V.)
By the Leibniz formula, for E 1], det V.) is a polynomial in x, of degree S kn-1 < k. Hence, if is nonzero polynomial in I, of degree k. and has at most k, zeros. Since any finite set is a null set with respect to a nonatomic distribution, follows that det (V) * almost surely over F,,- Since the assumptions Fi:.... Fn-1 are also satisfied almost surely, the statement follows. n
35

---

Published as a conference paper at ICLR 2021
As in the case of networks with biases, we will prove the independence result by first reducing to the case = 1. Since we also want to perform this reduction for random Fourier features in Proposition I.1. state the reduction to the d case separate result. Lemma H.14 and case in the following definition.
define the
Definition H.13 (Non-degenerate). Let p. 2 1. We call a function f RR - I29 non-degenerate it is analytic and for arbitrary independent IR-valued nonatomic random variables 31,.... Tys there almost surely exists w W War.n E R2 with
f (wxr1)
det
#0.
f(wxp))
Lemma H.14. Let ʃ R29 IPP be non-degenerate, let W E Raxd be a random variable with Lebesgue density and let Ø1,- Up E IRd be independent nonatomic random variables. Then,
((Wx)))
det
$0
[(Wxxp)
almost surely over W and æ1
Zp.
Proof. By Lemma H.10 there exists u. E IRd such that for all [p]. == =uul uT æz E is nonatomic. Obviously, ......... Zn are independent. Fix I1,..., Zn such that Wa....... E R in Defini
tion H. exists, which true with probability one since f is non-degenerate. Then, for W wu
have
f(W x1)
(f(wx1)
W) = det
= det
*
f(Wxpp) xp)
f(wxp))
Since g is non-zero analytic function, Theorem H.3 shows that g is only zero Lebesgue null set, and this null set is also null set with respect to the distribution of W since W has Lebesgue density. Hence, g (W) almost surely over W.
The following lemma proves the d = version of the independence result, which can then be upgraded general case using Lemma H.14
Lemma H.15 (Independence from nonatomic random variables). Let 1. Leto:
be an-
alytic and not polynomial with less than nonzero coefficients. Then, the elementwise application function f IRP RP, . x + (a(x1), (zzp) non non-degeeeeate in the sense of Definition H.13
Proof. Let ........ Tp be independent scalar nonatomic random variables.
Step 1: Power series coefficients. Since is analytic, there exists > 0 and coefficients (ax) such that
((2)
ax2 2
k=0
for 2 E R with |a| < s. Let K (k 2 0 ag # 0}. Then, |K] 2 pt Assume that K| S p 1, then the polynomial
h:R R
Σ a=
KEK
equals E-E,e). Hence, the function g h is zero (-e,e). By Theorem H.2 g is the zero function and hence a = is a polynomial with less than nonzero coeffcients, which we assumed not be the case.
36

---

Published as a conference paper at ICLR 2021
Step 2: Condition the T₁. By Step 1, choose indices h
12 <..
kp with
ki,..., kp E K. Then, by Lemma H. 12 and the Leibniz formula for the determinant, we have
D3 = Σ
sgn(T)a* x(1)
by x x())
= det
#
(11)
x(1)
RESp
kp
kp
Pp
with probability one.
Step 3: Determinant power series. Now, fix realization of 21,... By such that 11 holds. For w E Iº with sufficiently small || we can write
f(wxx))
g(w) det
fwxzp)
o (w1r1))
(wpp))
= det
o(w)pp)
o (wptpp)
p I12
Σ sgn
as (i) )k
RES
im km0
Σ
Σ
sgm n
aks w. =1))
Σ
II
Σ sgn ④T RESp
7(1)
w
(12)
kg....k200 20
Now, consider the special values kn ...... kp chosen in Step 2. Since k; K, we have ax, # 0. The coefficient of the multivariate monomial
w
wp" kp
in Eq. [12
fI ok
Σ sgn FES,
④T)
II
Rs (8)
ak
akp
Dz #0.
was the zero function, all derivatives of would be zero and therefore coefficients of all monomials would be zero, which is not the case. Hence, there exists w IP with g(w) + 0. This shows that ff is non-degenerate.
H.4 RANDOM NETWORKS: CONCLUSION
In the following, will prove Theorem an discuss some possible extensions and limitations.
Theorem 10 (Random neural networks). Let d, P, let - IR be analytic and let the layer sizes be do d, di...., d1-1 and d, p. Let (!) Rdd11x44 for I (O..... be random variables and consider the two cases where
(a) is not polynomial with less than p nonzero coefficients, = (W w((-1)) and the random feature map Φo Rdd - TRP recursively defined by
o(x = (T)) ((+1) =
(b) a is not polynomial of degree < p - 0 = (W (0) W(L-1) (0)
LL- (1-1)
with random variables ( E Rd+++ for I E {O...., L 1}. and the random feature map
dg d + RP is recursively defined by
((x(()) = (L)) ((+1) = (0 + +b0).
In both cases. if has a Lebesgue density and x is nonatomic, then (FRK) holds for all n and almost surely over 0.
37

---

Published as a conference paper at ICLR 2021
Proof. By Lemma H.4 it suffices consider the case where 0 has standard normal distribution, since a standard normal distribution has a nonzero probability density everywhere. Especially, we assume that all parameters in 0 are independent. ByPrrpositiion 6 we only need to prove (FRK) for n = P. Let Φ1 ,....,pp Tp (0) Px be i.i.d. nonatomic random variables.
(a) If p 1, is allowed to be non-zero constant function. In this case, the feature map do is constant and non-zero with p = 1. which means that (FRK) holds. In the following, we thus assume that a is non-constant. Let (0 ~ Px. Since x is nonatomic and is non- constant, an inductive application of Lemma H.11 yields that almost surely over 0, x1-11) is also nonatomic. Hence, 2; ((6-1)
Up are independent and nonatomic almost surely over 0. But by [emma H.15, the elementwise application of is non-degenerate, and hence by Lemma H.14| we almost surely have
det
20,
(1-1))
IP yT
which implies that (FRK) holds for n = p almost surely over A.
(b) If p and is polynomial of degree p function. Like in case (a), this implies that de is constant and non-zero with p = 1. which thus assume again that is non-constant, i.e. not polynomial of degree less than max{1, 1- 1}. Since the distribution of the x; == x; is non-atomic, they are distinct almost surely. By Theorem H.9
0, this means that is a non-zero constant
means that (FRK) holds. In the following,
x.p are linearly independent almost surely over 0, which proves (FRK) for n p almost surely over 0. L
x; 21(2)
Remark H.16 (Generalizations). The proof technique used in Theorem 10jis quite robust and can be further generalized. For example, it is easy to incorporate different activation functions for different neurons, and in all layers but the last layer, the activation functions only need to be analytic and non-constant, as required by the corresponding propagation lemmas. It is also possible to treat fixed but nonzero biases using combination of Lemma H.I (b) and using shifted activation functions ā. (x) o(r + b.) in Lemma H.15 Also, the propagation lemmas, which are used for all layers except the last one, can be easily extended DenseNet-like structures where the input of layer is concatenated to the output.
Remark H.17 (Necessity of the assumptions). For analytic a, the assumptions on not being a too simple polynomial in Theorem 10 are necessary. For this, consider the case with L layer and d == 1.
(a) Assume that is polynomial with less than p nonzero coefficients, i.c. axx) EKEK ag for [K] I 1. For arbitrary weights w Ipex| and data points Fl, Fi...., Tp E R, we obtain the feature matrix dw (X) E RRxP with
Duo (x)ix o(wj,,
Σ kEK
awffat
which means that dw (X) is the sum of the |K| S p matrices (axw xf jaje which have at most rank 1. Hence, ow has at most rank p 1 and is therefore not invertible. (b) Assume that is polynomial of degree less than p 1. i.e. 2p ax. For arbitrary weights w E | biases E IR and data points 1 Tp E R. we obtain the feature matrix Pw (X) Rexp with
p-2
Dw, (X)s - o (wyas + by)
Σ
a (uezz + b,)*
k=0
p-2 k
ak
Σ
Σ ak
(1)
k
b3
x
1=
38

---

Published as a conference paper at ICLR 2021
2
100
(1) Ek= ax (1)
where uj
does not depend Hence, ( the sum of the
p matrices (u)) dd)a.ee)p) each of which has rank most 1. Hence, (w,b(X) (X) has most rank and is therefore not invertible.
I RANDOM FOURIER FEATURES
In a celebrated paper. Rahimi & Recht 2008 propose to approximate a shift-invariant positive definite kernel k(2,, x') k(x (((==xx) with potentially infinieeddimensional feature map by a random (up to scaling)
finite-dimensional feature map. yielding so-called random Fourier features. the Fourier transform of probability distribution Pk on R. two versions of random Fourier features are proposed:
(1) One version uses Φw (w))(=) = v2 cos cos + b), where the rows of W E R are independently sampled from Pj. and the entries of b RP are independently sampled from the uniform distribution on [0, 2n.. This feature map is covered by Theorem 10 and hence, if Pk. has Lebesgue density and æ is nonatomic, (FRK) is satisfied for all For example, if is Gaussian kernel, Ps is Gaussian distribution and therefore has a Lebesgue density.
The other version uses
sin W a:) cos w
Øw (x)
with the same distribution over W. is not covered by Theorem 10Jbecause of the different "activation functions" and the "weight sharing" between these activation functions. In the following proposition, we show that the proof of Theorem 10 can be adjusted to this setting and the conclusions still hold.
Proposition L.I. For Rdd W Raxd and p 2q. define
<w(x) = sin W x) coO(( W x)
E RP
If W has a Lebesgue density and x is nonatomic, then (FRK) holds for all almost surely over W.
Proof. Step 1: Reduction. According to Proposition 6 it suffices to consider the case n p. By
Lemma H.14 is then sufficient to prove that the function
R
R22 x (sin(æ:) cos(2))
non-degenerate in the sense of Definition H.13
Let T1, ,, be indepen- dent scalar nonatomic random variables. For i [q], choose k; 21 and kytt 2i 2. Then, ki,..., kp are distinct non-negan negativve integers, and by Lemma H.12 and the Leibniz formula for the determinant, we have
Step Condition on the r,, We will proceed similar to Lemma H.15
Do = Σ sgn(T)*** SES,
by x(x)
= det
# 0
kp
with probability one.
Step 3: Non-degeneracy. Now, suppose that we are indeed in the case where Dr + 0. Take the power series of sin and
sin(x)
Σe
20
(-1)
1)*
x
2k+1
Σ axax
(2k + 1)!
k=0
k=
39

---

Published as a conference paper at ICLR 2021
2
cos(2)
by
(2k)
k=0
Similar to the proof of Lemma H.15
compute
f(wz1))
g(w) = del
f(wxxp)
Σ
(gn((T)an
.... bR
bizu
W1
k1t Ro-
wg hzv x(1)
Aay x(2g)
1i 2
Σ
Ok
axe bkytt
bizo
Σ TES20
(1))
2
kec =(2))
wi
thots
wo (13)
2200
Define the set K = (kk c of the monomial wiws
k2g
2
for all i
[g). + katt 2i 13. Then, the coefficient can be written as
w
-1 in (13
(K1....R,))E
Cki K2g = Oks
ak, bkgtt
bkan
((1)
Jzz (24)
RES20
Now, consider (K1, ................................ k2g) K. Note that Ok * 0 iff & is odd and by + iff & is even. For the
choice k; := 2i 1, di 2i for E [g] from Step 2, we have (ki,..., k2,) E K and
Cb
ak1 ak. bRat1 bkzo De #0.
In the following, will show that Ck2 C2, 0 for all other (k1, .h...... k22) E K, which implies e ( and therefore yields that g is not the zero function, which what we want to show. k; = kj for some * j. we have
Σ SES2
12 x(2g)
del
0
T(1)
since the i-th and j-th rows of the matrix are equal, and hence Cli = 0. Now, suppose that (ki,..., k2n) E K with C22 * O. By induction, easy to show that (ki, kgtz}
(2i 1,2i 2} for all E [g]. But since
ak
Oki bkggt ... -bug + 0
and dg 0 for even h. we need to have h; = 2i - 1, kops 2i 2 for all i E [g]. This shows the claim.
J PROOFS FOR SECTION 6
In this section, first prove the analytic formulas from Section 6 before discussing the case of low input dimension d.
Theorem 11. Let Pz = U(S--1). Then, Pz satisfies the assumptions (MOM), (COV) and (FRK) for all n with Σ ! Moreover, for 2 p 1 or p > 2 can compute
Ez (r((Zt)TEZ)) Σズ =
8
p-2
p-1
P
40

---

Published as a conference paper at ICLR 2021
Proof. Step 1: Verify (MOM). Let 2; NN),,p)) for i E [n] be independent. Then, 2, 1 = E1 = (MOM) is satisfied and thus, E is well-defined.
21
U(B=11) Since 2/
2
Step 2: Compute E. We
rotational invariance follows: Let V E Rexp be arbitrary fixed orthogonal matrix. Then, Væ, ~ (V, = NoO, Ip) and hence Vz,
Va:
VoL U(SP-1)) Therefore. IV
Σ Ez,2 EV V VEVT.
(14)
If T E IP U
is an eigenvector of E with eigenvalue X, then Ve must by Eq. (14) also be an eigenvector of Σ with eigenvalue A. But since V is an arbitrary orthogonal matrix, this means that Vu is an arbitrary rotation of v. From this it is easy to conclude that Σ Alp. and from
pd tr E tz( Ez 2; E1
follows that = p. Hence, (COV) is satisfied and we vpz:-
Step 3: Verify (FRK) for all n. By Proposition 6 it is sufficient verify (FRK) for p. Therefore, let n = p. It is obvious from Proposition with Φ = id that (0, Ip) satisfies (FRK). Hence, X almost surely has full rank. But then, since a O almost surely.
diag
X
[
almost surely has full rank as well, which proves (FRK).
Step 4.1: Computation for 2 1. In the underparameterizee case 2 p compute
1, we can
Ex 1 1 71
Ez (xtr = = Ez tr ( (WTW)- W)-
Ez Σズ wp
n
Step 4.2: Computation for p 2 1. In the overparametterized case p 2
compute
Ez tr((2*) ΣZ = Ez tn (WW = Ez w W1
Ez
where we used that since Σ Ip- wi 11 = ww 112 = |l / 1 = =p.
Step 4.3: Computation for p 2 n 2 2. Now, let 2 2 2. Since E = 1 p. we have
Ez tr((2*) Σz Ez tr (
by Theorem Using that the w, are i.i.d., we obtain from Lemma G.2 that E( )-1) n. dist W1, W-1)=² where W-1 is the space spanned by W2...., w., Define the subspace Un = 2 E IRP Zn = Zn+1 = Zp = 0}. By (FRK), we almost surely have dim(WW.) = n 1.
Thus, there is an orthogonal matrix U depending only on W_ that rotates W_1 to Un:
Un U-1
Because wi stochastically independent from W-1 and U-1 and its distribution is rotationally symmetric, we have the distributional equivalence (using the z; and æ; from Step
dist(w), w-1)² dist(U (U00UU1110 -1W1, U W- distrib. (ist(w,,2un)" = p(2?,n +... +..+ 2
x +...
+ xP_
A
p
1 12112
A B P
where == 2f,n + wi,++1 +... ... has a x²+1-n distribution and xf,1 + ... + xf
has x distribution. Hence,
B((WWT)-1) W.distt -- n + A
p
41

---

Published as a conference paper at ICLR 2021
Since n 2, n and p + - are positive. Since A and B are independent, A/(p+1-1 follows Variance-Ratie F-distribution with parameters and + n, whose mean is known (see c.g. Chapter 20 in Forbes et al. 2011):
B/(n-1)
E B/(n - 1) p+l n A n)
n
x
if + 1- 2, 2.
(15)
A
p+l-n (p+1-n)-2 = p-1-n .
n-1 p+i-n
n-1
The infinite expectation for + 1- - n easy to obtain from the p.d.f. of the didistribution: The p.d.f. f(x) of the F(a. b)- distriibbuion for 2 is
< 2 is not explicitly specified in Forbes et al.
(2011). but it
x(a-2)/2
f(x) Co.b (1 (a/ (a/b)x)(atb)/2
O(x 6/2-1)
(xr + oc)
for some constant Ca.b (cf. Chapter 20 in Forbes et 2011 and the expected value is therefore
xf(x) dr = /0-0 O(x (o2--/2)) dr,
which is infinite for p+11+111 - S. 2. Forn (p.p-1}, 1}, we therefore obtain B (( (WWT)--1) = co.
For S p 2, compute
(1 p-1-w p P p- -----) n2 p-2
B(WW
In the following, we will prove Theorem 12 using the same proof idea as for Theorem 11 formulas in Theorem 12 have in principle already been computed by BBreiman & Freedman (983)
The
for p Σ n and by Belkin et al.] (2019h) for general p. However, our proof circumvents a technical problem in the proof Belkin al. (2019b): Consider for example the case p S Belkin al. (2019b) mention that (W W) has an inverse Wishart distribution, which for p S has expectation - p. and then use Etr((W] -))+)) tr(IE W W)-1). However, for 2 n 1, the latter expectation is not specified in common literature distribution (Mardia et al., 1979 Press] 2005) von Rosen] 1988), presumably because it is oo for diagonal elements but is not dell-defined for off-diagonal matrix elements.
7 on the inverse Wishart
Theorem 12. Let Py = (N, Ip). Then, Pz satisfies the assumptions (MOM), (COV) and (FRK) for all n with Σ Ip. Moreover, for n, 1,
fp2n+2 ifpe {n - 1, n, n + 1}, n
p-
Ez tr(((t TE
0
n-1-p
Proof. Step 1: Assumptions. Verifying (MOM), (COV) and Σ I, is trivial and (FRK) for all follows from Proposition 6) with æ = z and Φ = id.
Step 2: Overparameterizze case. For the expectation, we first follow Step 4.3 in the proof of Theorem I1 in the overparameterized case 2 n 2 1, the main difference being that instead of we now have w, 2g, which translates to the simpler equation w; /p |
dist(w:, W_1)² distrib.
with A ~ 2 X Let B ~ x be independent of A, then we can compute similar to Eq.
15
B
Eur((W nE nEdist(w, i W 1) = nE A (EB)
E
= n
A
A
B/1
p n A/(p (p + 11 n)
8
if p 1
p+iーn p+i-n (p+1-n)-2
if fp+1-n>2
p-1-2
Belkin al. 2019b) do not cite any source on the inverse Wishart distribution.
42

---

Published as a conference paper at ICLR 2021
This proves the wer-parameterize case.
Step 3: Underparameterized case. Since the rows w, of W E R are independent and follow a
(0, Ip) distribution, the rows of W gpxa are independent and follow a ( I.) distribution. Therefore, the underparameterized case S n. follows from the overparameterized case S by switching the roles of n and p.
Remark J.1. An alternative (and presumably similar) way to prove Theorem 12 is to use that the diagonal elements of a matrix with an inverse Wishart distribution follow an inverse Gamma distri- bution as specified in Example 5.2.2 in Press (2005).
The next proposition shows that small input dimension d does not necessarily provide limitation: Proposition J.2. pet d 2 L. Then, there exists probability distribution Px on E (with bounded support) and continuous feature map ó g + IRP such that for a Px, x(x)) ) U()
Proof. For p 1, the result is trivial we will therefore assume p 2 2. We will prove the result for any d by a reduction to the case d I, although substantially simpler constructions are possible for d 121 p 1. First, introduce the spaces
S {= SP 2p 2 03 C
BP-1 { E RP-1 || 1
X' = [0,3] x {0)p-1 I..
Step 1: Space-filling curve on the sphere. In this step, we show that there exists continuous surjective map Φ Sr-1 First of all, fi : [0. 1] [0, 1]m=1 be continuous and surjective, e.g. Hilbert or Peano curve (see e.g. Sagan 2012
We define the following maps:
if u
f2: [0, 1]p-1
B
1 1 la
u
if u + 0,
fa 1P-1 + St 2 +
1 1013
is not hard to verify that fa and fs are continuous and surjective as well. For example, f2 is continuous in 0 since |//|/> ||u||2 for all u E R=-1 Thus, the map = Sa f2 fi [0, - S is continuous and surjective. Define the map
R
(21,-.., 1 -zp)
By the previous considerations, not hard to verify that the map
f(x)
if or E [0,1]
[0,3] + SP-1
+0)+ + (1-)++11-11) - T((()) 7f133 -)))
if i E [1,2] if E [2,3]
continuous and surjective as well. We can therefore define the continuous and surjective map X + S0-1 + + g(21).
Step Existence of pull-back measure. We consider the Borel o-algebras B(X)) ((P-1)) on X and Sp-1 The uniform distribution Pz = (SS- on the sphere is defined with respect to B(S=-1) and is therefore Borel measure. Since á is continuous, it is Borel measurable. Moreover, since X' and S=-1 are complete separable metric spaces, they are also Souslin spaces, cf. Section 6.6 in Bogachev (2077). Since ø is surjective, Theorem 9.1.5 in Bogachev (2007) guarantces the existence of measure Px such that if x Px, then dxx: ~ USA F). Since Px(2)) = (2 (S 1, Px a probability measure.
Step 3: Continuation. We can arbitrarily extend the mapping X + S--1 to continuous mapping ò Bd + RP Moreover, the domain Px can extended to Rd via Px(A) = Px n 2'), the support of Px is still bounded, and we still have 6(x) ~ ((P-11) if x Px. n
43

---

Published as a conference paper at ICLR 2021
Remark J.3. The proof of Proposition could be slightly shorter if we required ((x) ~ (($""" instead of Φ(xx)
U(S* J). This would be of similar interest since the uniform distribution u($ on the "half-sphere" leads to the same Ez tr((Z E(Z )) as the uniform distribution 1) ) on the full sphere: 24 ~ U( 1 and E ~ u((-1, are stochastically independent, then 2; := = U( Therefore, Σ = Σ, Z diag(S1, En. Z, and if UDV T is SVD of Z. then (diag(E1,..... (n) DV is SVD of Z. Therefore, Z and Z have the same singular values, hence W and W have the same singular values, hence tr((WW ) = tr((W )
forp n and tr(( ")) =r((W tr((W
1) p Sn.
choose Px as a "nice" distribution, like a uniform distribution on a cube Gaussian distribution. The answer to this question is affirmative there exists an area-preserving space-filling curve di [0. voluum((SS-))) $5-1. For 3, such construction is informally described by Purser et al. (2009) and it seems
Remark J.4. One might ask whether it is possible in Proposition J.2
plausible that such a construction is possible for all p.
K RELATION TO RIDGELESS KERNEL REGRESSION
In this section, we want to discuss the relation between this paper and recent work on ridgeless kernel regression. To this end, we need to introduce some terminology on representations of kernels with dinee--ammnsional feature maps.
Definition K.1. Let l IRd x R2d - R be a kernel, let be an integer with 1 S < oc and let 6 Rdd + R2 be a (measurable) function. Then, (p, o) is called Px-representation of k if
k( = d(x) To()) almost surely for independent æ, ã ~ Px, and k(xx)) x) = (6x)) T <(x) almost surely for x ~ Px.
If k has Px-representation, then we define
Pk
min (p.6) is a Px Px-repcccnntation P,
i.c. pk is the smallest p for which Perrepresentation exists.
Usually, pa corresponds to the dimension of the RKHS associated with the restriction of k to the support of Px. but since the feature map & only needs represent the kernel Px Pl-almost surely, pk may be smaller for pathological kernels. The following lemma states that Theorem 3 if applicable,
should be applied to ridgeless kernel regression with p = Pk:
Lemma K.2. Let l be kernel on IRd with Px (k(æ, x) + 0) > O. Let (p, 0) be Px-representaatin of k.
(a) Then, (COV) in Theorem 3 is satisfied iff p Pt-
(b) The assumptions of Theorem 3 3are satisfied for a Px Px-representation (px. 6) of if and only if they are satisfied for all such representations.
(c) the assumptions Theorem Dare satisfied for any Px-representation of k, then the lower bound from Theorem 3 alsoo holds for ridgeless kernel regression with p Pk-
Proof. In the notation of Section 3| the definition of Px-representation implies that xXx.X) = ((X) (x( and k(x;, X) x(z) 6(X)" almost surely.
(a) If (COV) is not satisfied and 2 2, it is possible to construct a Px-representation with smaller p using the construction from Remark 7 hence p > Pk- If p = 1, (COV) is satisfied due to the assumption on k.
Conversely, assume p > pk and let (px, Φ) be another Px re-reeeesentttion of k. Set n = p. Then, we almost surely have
rank db ()) rank ( (X))(X)) rank(k(XX (mnn(())x)))) = rank (x))) S pk
p
hence x(X) has full rank with probability zero. Since the rows o(x,) of ((X) are i.i.d.
this means that there must be proper linear subspace U of R" such that Φ(x;) E with probability one. But then, according to Proppsiitin 6. (COV) is not satisfied.
44

---

Published as a conference paper at ICLR 2021
(b) Let (px. o) and (ps. ④) be two Px Px-representations of k such that = ((x) satisfies the
assumptions of Theorem 3 We need to show that Σ = z(xx) also satisfies the assumptions
First of all, (INT) and (NOI) hold since they are independent of the feature map. Moreover, (COV) holds by (a). We find that (MOM) holds due to
[hhorem 3/
|| Ex(x) ((x)= Ek x:) = Eş(x) ((x) B| < oc
and (FRK) holds since, almost surely,
rank (xx) rank( ( X @ )) = rank(k(X, X)) rank (X)
rank (X) - min
(c) Assume that there exists a Px-representation (p, Φ) of k: that satisfies the assumptions of [Theorem By (a), we have p Pk- By Eq. (2) in [Section 3| the ridgeless kernel regression estimator and the linear regression estimator with the feature map é are almost surely equivalent, hence they have the same Noisee
For kernels that cannot be represented with finiteddimensional feature space, Theorem cannot be applicd. In fact, any distribution- innpuiiiinnndeeeedeeettn lower bound for ridgeless kernel regression must be zero in this case: For example, the Kronecker delta kernel given by
{ k(x,, ②) - 0 otherwise
if = à
yields ENoise 0 for any nonatomic input distribution Px. Of course, this kernel is well-suited for learning since the learned functions are zero almost everywhere. However, there exist results for ridgeless kernel regression with specific classes of kernels. For example, [Rakhlin & Zhai (2019) show that in certain settings, ridgeless kernel regression with Laplace kernels is inconsistent because ENoise = (1) as + so. Note that Laplace kernels in general do not allow for minee-dimensional feature map representations.
example,[akklin
Liang & Rakhlin (202)) derive upper bounds for certain class of kernels and input distributions with (linearly transformed) i.i.d. components. Their analysis focuses on the high-dimensional limit d,n + oo with 0 < e S d/n S C < ao and ignores the "effective dimension" ys of the feature space. It appears that their analysis is not impacted by Double Descent w.r.t. pk since their assump- tions on the kernel imply either pk = oo or ps/n - oo as n, d + co: In particular, they consider kernels of the form
k(x,, ②) = (2(x,)) (
for suitable smooth function h that is independent of d. Due to the factor and the limit d - the kernel behaves essentially like a quadratic kernel
(( (
2
k(x, ②) ao + a1 (e. + a2
kquad (x, ã).
where the curvature 02 should be positive in order to obtain good upper bounds on ENose (the variance term). For d2, d1, ag > 0, it is possible to represent this quadratic kernel with feature map analogous to that of the polynomial kernel in PProposition 8) with feature space dimension p = 1 + d + d(d+1) An argument similar to the proof of Prooosstion 8 shows that this feature map (p) if æ has Lebesgue density, hence (COV) is satisfied. By Lemma K.2 (a), we have n, d -
satisfies (R&(p) (dP) = @(ni), ), which shows Phyuuaa /n
Pliqund
Liang et al. (019) consider similar setting with d ~ n E (0, 1), and find that Exose converges zero under suitable assumptions
n 0o. Again, appears that their assumptions on the kernel imply at least strongly overparameterized regime with ps 0o or Pk/n + oo for d, -> 20, where our lower bound is vacuous.
L NOVELTY OF THE OVERPARAMETERIZAR BOUND
In their Corollary 1, Muthukumar et al. (020)) provide lower bound in the case p 2 holding with high probability for & (WW)) ) e, where
NN Ip) is noise vector independent of
45

---

Published as a conference paper at ICLR 2021
W. Since Ee (WW Ez tr((Ww))) ) "EeEe") = Ez tr (r( W ))-),, their lower bound yields lower bound for E Er Btr((WW))-) However, the resulting lower bound is weaker than ours and requires stronger assumptions:
(I) Assuming that the subgaussian norm ||willlz == suP BuP T ( T w. 19)//)// (cf. Vershynin 2010) bounded by constant K < co, they obtain a lower bound of the form CgO P with constant сж > O that depends on K and is only explicitly specified for the of centered Gaussian Pz. They note that ||w:ll if the components Wiy of w; are independent and all satisfy w llyss I K. However, as discussed Remark such independence assumptions are not realistic. In contrast, our lower bound Is explicit, independent of constants like K and is larger: For example, at
K holds, for example,
n = p. our lower bound aan and theirs is g²ck.
(2) Assuming || ww 1 S almost surely, they obtain a lower bound of the form co² plog(n)) First of all, this lower bound converges to zero = p - Moreover, since we always have TB|] = E tr(w,,w,) )
E tr( = the assumption implies || = p almost surely. Although we can sometimes guarantee constant || e.g. for certain random Fourier features, we cannot guarantee the same for w. = 2-1/2g z; since E depends on the unknown input distribution Px.
By inspecting the proof behind (1), one finds that ск + 0 as K - cc. Hence, lower bound of Muthukumar al. (2020) might raise hope that it is possible achieve low ENoise by choosing features with a large (or even infinite) subgaussian norm. Our result shows that this is not possible: Essentially the only possibility to avoid large Noise for ridgeless linear regression around to violate the property (FRK) that guarantees the ability to interpolate the data in the overparameter- ized case, see Section 5 Otherwise, in order to achieve ENoise E022 8 < 1, is necessary to make the model either strongly underparameterized (p < En) or strongly overparameterized (p >> n/E).
p
46


Reviews:
[{"review_id": "kHYxLVmN-d-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work studies the double descent phenomenon in ridgeless regression with deterministic or random features. The work provides a lower bound on the generalization error that requires weaker assumptions than bounds given in previous work and applies to many interesting learning methods.\n\nStrengths:\n-- The generalization bound presented this work requires fewer assumptions than previous such bounds while also being stronger.\n-- The work is theoretically rigorous and helps to shed light on why various learning methods perform well.\n-- The authors thoroughly investigate the applicability of their bound with specific discussion of each of their assumptions.\n\nWeaknesses:\n-- While the analysis applies to a class of feedforward neural networks with analytic activation functions, some common activationswith a perfectly linear component like ReLU, however are not covered by the results in this work.\n\nThe second sentence in Remark 7 says, \"If (d) in Propositions 8 does not hold...\" but I don't think you mean to reference Prop. 8 here.", "extra_scores": {}, "extra_text": {}}, {"review_id": "XMMqP6uQBss", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Contributions\n\nThis work studies linear regression with feature maps (or kernel regression) without regularization in order to theoretically explore double descent phenomena seen empirically when training over-parametrized networks.\n\nThis paper provides lower bounds on the out of sample error or generalization error caused by the label noise. In the over-parametrized regime or beyond the interpolation threshold this is the primary source of error. \n\nWhile this setting has been studied before this work strictly generalizes previously provided bounds especially around the interpolation threshold. They also consider analytic feature maps including random ones and thus imply results for random deep neural networks. \n\nThe main text of the paper is well organized. However, it could benefit from some more clarity in presentation of the technicalities especially in section  5 when comparing with prior work and in section 6 when providing examples. \n\n# Concerns\n1. It seems that a big part of the assumptions is that the data is generated from a full dimensional distribution. Given that in the high dimensional settings where d ~ n a key problem is to characterize the behavior of estimators when true data has low intrinsic dimension can we say anything about this regime given the results in the paper? \n2. It seems that the main novelty over prior work especially Muthukumar et al. (2020) is around the interpolation threshold or slight weakening of the assumption on the noise. Since the over-parametrized regime is currently most relevant to the community is there a relevant example in this regime where the results provided in this work are strictly better (in terms of actual rates or in understand of this regime) than those from prior work? \n3. Or just as importantly are there examples of proof techniques that are used here that are substantially novel over those in the prior work that may be beneficial to the community in general in understanding these over-parametrized regimes? \n4. There is some recent work on ridgless kernel regression by [Liang et al. (2020)][1]. Since these two settings are fairly intertwined it would be nice to understand how results in current work compare to the results in this paper.\n\n[1]:https://arxiv.org/abs/1808.00387", "extra_scores": {}, "extra_text": {}}, {"review_id": "SDvSLJGlwB9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the phenomenon of double descent for ridgeless regression. They show that when the label noise in the regression problem is lower bounded, the test error for regression must peak at the interpolation threshold (n=p) before descending again in the over-parameterized regime and that this holds with very weak assumptions making it a universal phenomenon when we consider unregularized linear regression. \nThese results extend our understanding of double descent and point that under most general settings it is impossible to avoid for ridgeless linear regression. \n\nThe paper is well-written and the analysis and comparison to prior work provided appears thorough. I have not verified all the proofs in the appendix.\n\n-------\nThank you to the authors for their response and update. I have read the response and am keeping my current rating for the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BsZt3HrISIV", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper focuses on the theoretical understanding of the so-called double descent phenomenon, which may offer insights into the practical success of deep learning methods and has been observed in both overparametrized neural networks and kernel machines.  In particular, the authors derive a nonasymptotic distribution-independent lower bound on the excess generalization error of the ridgeless linear regression under mild conditions on the input distributions and feature maps. More specifically, their analysis applies to the cases where the input distribution has a Lebesgue density and the features are induced by random deep neural networks with analytic activation functions,  random Fourier features, polynomial kernels, and so on. The sharpness of the lower bound has been demonstrated by some numerical experiments. The results should be of interest to the community of theoretical deep learning. Overall, I vote for accepting.\n\n\nConcerns:\n\n1. Is it possible to derive a nonasymptotic upper bound which matches the lower bound in Theorem 3?\n2. In Theorem 3 and Corollary 4, which lower bound should be adopted when $p=n$, $\\sigma^2n$ or $\\sigma^2$?\n3. In the underparameterized regime ($\\gamma<1$), the derived lower bound seems to be not asymptotically sharp by looking at Theorem 2 of Hastie et al. (2019), any special reason for this?\n4. The authors may consider using subsections since sections 2 and 3 are very short compared to other sections.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows that the double descent phenomenon of ridgeless regression appears under considerably general settings of the input distributions by showing a lower bound of the excess risk. The analysis covers various types of input distributions including deterministic and random feature maps and its asymptotic sharpness is also shown.

One reviewer raised a concern about its novelty compared with existing work, but the authors properly clarified the novelty in the rebuttal and updated version of the manuscript. Although there were some other minor concerns, the reviewers all agree that this paper gives a valuable theoretical result supporting universality of double descent phenomenon. I also concur with this assessment. I think this paper is a solid theoretical paper giving an informative result as a piece of researches in double descent. Thus, I would recommend acceptance of this paper.
Decision: Accept (Poster)