Strong inductive biases provably prevent harmless interpolation
Authors: Michael Aerni
Marco Milanta
Konstantin Donhauser
Fanny Yang
Venue: ICLR 2023 poster (2023)
Keywords: high-dimensional statistics
non-parametric regression
deep learning theory
generalization bounds
benign overfitting

Abstract: Classical wisdom suggests that estimators should avoid fitting noise to achieve good generalization. In contrast, modern overparameterized models can yield small test error despite interpolating noise — a phenomenon often called "benign overfitting" or "harmless interpolation". This paper argues that the degree to which interpolation is harmless hinges upon the strength of an estimator's inductive bias, i.e., how heavily the estimator favors solutions with a certain structure: while strong inductive biases prevent harmless interpolation, weak inductive biases can even require fitting noise to generalize well. Our main theoretical result establishes tight non-asymptotic bounds for high-dimensional kernel regression that reflect this phenomenon for convolutional kernels, where the filter size regulates the strength of the inductive bias. We further provide empirical evidence of the same behavior for deep neural networks with varying filter sizes and rotational invariance.

Published as a conference paper at ICLR 2023
STRONG INDUCTIVE BIASES PROVABLY PREVENT HARMLESS INTERPOLATION
Michael Aerni"!, Marco Milanta" Konssantin Donhauser Fanny Yang' Department of Computer Science, ETH Zurich 2ETH Al Center
ABSTRACT
Classical wisdom suggests that estimators should avoid fitting noise to achieve good generalization. contrast, modern overparameterized models can yield small test error despite interpolating noise phenomenon often called "benign overfitting" or "harmless interpolation". This paper argues that the degree to which interpolation is harmless hinges upon the strength of an estimator's inductive bias, i.c., how heavily the estimator favors solutions with a certain structure: while strong inductive biases prevent harmless interpolation, weak inductive biases even require fitting noise to generalize well. Our main theoretical result establishes tight non-asymptotic bounds for high-dimensional kernel regression that reflect this phenomenon for convolutional kernels, where the filter size regulates the strength of the inductive bias. We further provide empirical evidence of the same behavior for deep neural networks with varying filter sizes and rotational invariance.
INTRODUCTION
According classical wisdom (see, e.g., Hastie et al. (2001)), an estimator that fits noise suffers from "overfitting" and cannot generalize well. A typical solution is to prevent interpolation, that is, stopping the estimator from achieving zero training error and thereby fitting less noise. For example, one can use ridge regularization or early stopping for iterative algorithms to obtain model that has training error close to the noise level. However, large overparameterized models such as neural networks seem to behave differently: even noisy data, they may achieve optimal test performance at convergence after interpolating the training data (Nakkiran et al., 2021; Belkin et al., 2019a) a phenomenon referred as harmless interpolation (Muthukumar et al., 2020) or benign overfitting (Bartlett et al., 2020) and often discussed in the context of double descent (Belkin et al., 2019a).
To date, lack general understanding of when interpolation is harmless for overparameterizeed models. In this paper, we argue that the strength of an inductive bias critically influences whether an estimator exhibits harmless interpolation. An estimator with strong inductive bias heavily favors "simple" solutions that structurally align with the ground truth (such as sparsity or rotational invariance). Based on well-established high-probability recovery results of sparse linear regression (Tibshirani, 1996; Candes, 2008; Donoho & Elad, 2006), we expect that models with a stronger inductive bias generalize better than ones with a weaker inductive bias, particularly from noiseless data. In contrast, the effects of inductive bias are much less studied for interpolators of noisy data.
Recently, Donhauser et al. (2022) provided first rigorous analysis of the effects of inductive bias strength on the generalization performance of linear max-fp- margi//miaaiii
interpolators. In particular, the authors prove that a stronger inductive bias (small p - 1) not solely enhances a model's 's ability to generalize on noiseless data, but also increases model's sensitivity to noise eventually harming generalization when interpolating noisy data. As a consequence, their result suggests that interpolation might not be harmless when the inductive bias is too strong.
In this paper, we confirm the hypothesis and show that strong inductive biases indeed prevent harmless interpolation, while also moving away from sparse linear models. As example, consider data where the true labels nonlinearly only depend on input features a local neighborhood, and vary the strength of the inductive bias via the filter size of convolutional kernels shallow convolutional neural networks - small filter sizes encourage functions that depend nonlinearly only on local
"Equal contribution; correspondence to researchêmi chael aerri..... ccm

---

Published as a conference paper at ICLR 2023
neighborhoods of the input features. As second example, we also investigate classification for rotationally invariant data, where we encourage different degrees of rotational invariance for neural networks. In particular,
prove a phase transition between harmless and harmful interpolation that occurs by varying the strength of the inductive bias via the filter size of convolutional kernels for kernel regression in the high-dimensional setting (Theorem 1).
we further show that, for weak inductive bias, not only is interpolation harmless but partially fitting the observation noise is in fact necessary (Theorem 2).
we show the same phase transition experimentally for neural networks with two common inductive biases: varying convolution filter size, and rotational invariance enforced via data augmentation (Section 4).
From a practical perspective, empirical evidence suggests that large neural networks not necessarily benefit from early stopping. Our results match those observations for typical networks with a weak inductive bias; however, we caution that strongly structured models must avoid interpolation, even if they are highly overparameterized.
2 RELATED WORK
We now discuss three groups of related work and explain how their theoretical results cannot reflect the phase transition between harmless and harmful interpolation for high-dimensions kernel learning.
Low-dimensional kernel learning: Many recent works (Bietti et al., 2021; Favero et al., 2021: Bietti, 2022; Cagnetta et al., 2022) prove statistical rates for kernel regression with convolutional kernels in low-dimensional settings, but crucially rely on ridge regularization. In general, one cannot expect harmless interpolation for such kernels in the low-dimensional regime (Rakhlin & Zhai, 2019; Mallinar et al., 2022; Buchholz, 2022); positive results exist only for very specific adaptive spiked kernels (Belkin et al., 2019b). Furthermore, techniques developed for low-dimensional settings (see, e.g., Schölkopf et al. (2018)) usually suffer from curse of dimensionality, that is, the bounds become vacuous in sigh-dimensional settings where the input dimension grows with the number of samples.
High-dimensional kernel learning: One line of research (Liang al., 2020; McRac et al., 2022; Liang & Rakhlin, 2020; Liu et al., 2021) tackles high-dimensional kernel learning and proves non aon-asymptotic bounds using advanced sigh-dimensional random matrix concentration tools from El Karoui (2010). However, those results heavily rely on bounded Hilbert norm assumption. This assumption is natural in the low-dimensional regime, but misleading in the high-dimensional regime, as pointed in Donhauser et al. (2021b). Another line of research (Ghorbani et al., 2021: 2020; Mei et al., 2021; Ghosh et al., 2022; Misiakiewicz & Mei, 2021; Mei et al., 2022) asymptotically characterizes the precise risk of kernel regression estimators in specific settings with access to a kernel's eigenfunctions and cigenvalues. However, these asymptotic results are insufficient to investigate how varying the filter size of convolutional kernel affects the risk of kernel regression estimator. In contrast to both lines of research, we prove tight asymottti matching upper and lower bounds for high-dimensiona kernel learning which precisely capture the phase transition described in Section 3.2.
Overfitting of structured interpolators: Several works question the generality of harmless interpolation for models that incorporate strong structural assumptions. Examples include structures enforced via data augmentation (Nishi et al., 2021), adversarial training (Rice et al., 2020; Kamath et al., 2021; Sanyal et al., 2021; Donhauser et al., 2021a), neural network architectures (Li et al., 2021), pruning-bui based sparsity (Chang et al., 2021), and sparse linear models (Wang et al., 2022; Muthukumar al., 2020; Chatterji & Long, 2022). In this paper, continue that line of research and offer new theoretical perspective to characterize when interpolation is expected to be harmless.
3 THEORETICAL RESULTS
For convolutional kernels, small filter size induces strong bias towards estimators that depend nonlinearly on the imput features only via small patches. This section analyzes the effect filter size (as example inductive bias) the degree of harmless interpolation for kernel ridge regression.
2

---

Published as a conference paper at ICLR 2023
For this purpose, derive and compare tight non-asymptotic bias and variance bounds function of filter size for min-norm interpolators and optimally ridge-regularized estimators (Theorem 1). Fur- thermore, prove for large filter sizes that not only does harmless interpolation occur (Theorem 1), but fitting some degree of noise is even necessary to achieve optimal test performance (Theorem 2).
3.1 SETTING
We study kernel regression with a (cyclic) convolutional kernel in high-dimensional setting where the number of training samples n scales with the dimension of the input data d as n E ((d)). We use the same setting as in previous works on high- -igh-immensooall kernel learning such as Misiakiewicz & Mei (2021): we assume that the training samples { Vs y-) are i..d. draws from the distributions T; ~ 1))) and yı = (z;) ) +e; with ground truth f* and noise ~ (0, o²). For simplicity of exposition, we further assume that (x) = 2 LI,,, with L specified in Theorem 1.
While the assumptions on the noise and ground truth can be easily extended by following the proof steps in Section 5, generalizing the feature distribution is challenging. Indeed, existing results that establish precise risk characterizations (see Section 2) crucially rely on hypercontractivitty of the feature distribution - an assumption so far only proven for few high-dimensional distributions, including the hypersphere (Beckner, 1992), and the discrete hypercube (Beckner, 1975) which we use in this paper. Hypercontractivity is essential to tightly control the empirical kernel matrix within Lemma 3 in Section 5. Generalizations beyond this assumption require the development of new tools in random matrix theory, which we consider important future work.
We consider (cyclic) convolutional kernels with filter size a E (1...., of the form
K(x,x') 1 Σ
((()))
K
9
where T(kkgg) == [Tmod(k.d) ... = and K: [-1, 1] + R is a nonlinear function that implies standard regularity assumptions (see Assumption 1 in Appendix B) that hold for instance for the exponential function. Decreasing the filter size q restricts kernel regression solutions to depend nonlinearly only on local neighborhoods instead of the entire input
We analyze the kernel ridge regression (KRR) estimator, which is the minimizer of the following convex optimization problem:
fa = arg min SEH
(f(x)) - 11
(2)
where H is the Reproducing Kernel Hilbert space (RKHS) over (-1, 1) generated by the convolu- tional kernel IC in Equation (1), |1- the corresponding norm, and X > 0 the ridge regularization
penalty.' In the interpolation limit (A + 0), we obtain the Sonn-RKHS--nmmm interpolator
fo arg min Il. s.t. Vi: f(x)) yi-
fEH
For simplicity, we refer to fo as the kernel ridge regression estimator with = 0. We evaluate all estimators with the expected population risk over the noise, defined as
Risk(fa) = Ez ((E.((()))))))))))
+ Ez,e ((((())-,((A ((A()))-LL((C)))) 27
Blas ((A))
: -Variance(fs)
3.2
MAIN RESULT
We now present tight upper and lower bounds for the prediction error of kernel regression estimators in the setting from Section 3.1. The resulting rates hold for the high-dimensional regime, that is, when both the ambient dimension d and filter size q scale with n.? We defer the proof to Section 5.
Note that previous works show how carly-stopped gradient methods the square loss hehave statistically similarly to kemee ridge regression (Raskutti et al., 2014; Wei et al., 2017).
We hide positive constants that depend most on l and / (defined in Theorem 1) using the standard Bachmann Landau notation O(-), (()), (()), as well S. Z, and use c, c1.... as generic positive constants.
3

---

Published as a conference paper at ICLR 2023
Theorem 1 (Non-asympiotic prediction error rates), Let 0, (0, (0, Eo R. Assume dataset and a kernel as described in Section 3.1, with the kerne satisfying Assumption 1. Assume further (dd)), the filter size ④ (dd),, and o² (dd= Lastly, define 8 = { - and
6= == /- 1 1 1 for any lx. Then, with probability at least - cd (6, uniformly
over all lx E 10 16-11 1), the KRR estimate fx in Equation (2) with max m 11 E @dd*)) satisfies
Variance O (n -ta-tx min mmm((411-))
Further, for ground truth (*(x) = 21 ... ILL" with L S (
with probability at least
1 -
we have
Bias Bias? E 2 ( (n- (------))-)-
Finally, by setting la 0, both rates also hold for the SintRRKHS-oomm interpolator So in Eq. (3).
Note how the theorem reflects the usual intuition for the effects of noise and ridge regularization strength on bias and variance via the parameter ex: With increasing ridge regularization εx (and thus increasing A), the bias increases and the variance decreases. Similarly, as noise increases (and thus t decreases), the variance increases.
Phase transition as a function of 3: In the following, we focus on the impact of the filter size q E θ (d²) on the risk (sum of bias and variance) via the growth rate 3.. Recalling that a small filter size (small () corresponds to a strong inductive bias, and vice versa, Figure I demonstrates how the strength of the inductive bias affects generalization. For illustration, we choose the ground truth [*(x) 22 so that the assumption on I,* is satisfied for all B3 Specifically, Figure 1a shows the interpolator fo and the optimally ridge-regularized estimator fxy.- where we choose App to minimize the expected population risk Risk (fxag) Furthermore, Figure 1b depicts the (statistical) bias and variance of the interpolator fo. At the threshold 3 (0. 1), implicitly defined as the 8 at which the rates of statistical bias and variance in Theorem match, we can observe the following phase transition:
rates for the min-RKHS-
For 3 < , that is, for a strong inductive bias, the rates in Figure Ia for the optimally ridge- regularized estimator Sxy, are strictly better than the ones for the corresponding interpolator fu. In other words, we are observing harmful interpolation.
For B > f", that is, for weak inductive bias, the rates in Figure 1a of the optimally ridge-regularized estimator fxy, and the nin-RKKS-norm interpolator fo match. Hence, we observe harmless interpolation.
In the following theorem, we additionally show that interpolation is not only harmless for 3 > 8 but the optimally ridge-reguland regularegulri estimator fxy. necessarily fits part of the noise and has a training error strictly below the noise level. In contrast, we show that when interpolation is harmful in Figure 1a, that is, when 3 < 3 the training error of the optimally ridge-regularized model approaches the noise level.
Theorem 2 (Training error (informal)). Let rop be such that the expected population risk Risk fxam) minimal, and let 3* be the unique threshold where the bias and variance bounds in Theorem I are of the same order for the interpolator So (setting lx = 0). Then, the expected training error converges in probability:
1 (ta u1)
3 < 3
lim n.d +00000
Ee
< C3
3 2 3
where cg < for any 3 > 8*.
We refer Appendix D.2 for the proof and general statement.
See Theorem for more general statement that does not rely on unique 8".
4

---

Published as a conference paper at ICLR 2023
interpolating
optimally regularized
variance
bias"
var. lower bound
rate exponent a
rate exponent J
-0.4
-0.51
-0.9
0.1
0.1
3
s.t. size q c (
3 s.t. filter size & c (()))
(a) Interpolating vs. regularized model
(b) Variance vs. bias interpolating model
Figure I: Illustration of the rates in Theorem I for high eigh-dimensional kernel ridge regression as function of
3 the rate of the filter size q E (.d)). (a) Rate exponent a of the Risk (n²") ) for the interpolator fo vs. the optimally ridge-regularized estimator fxqq- (b) Rate exponent of the variance and bias for the interpolator fo. For both illustrations, we choose fo with 2, la = 0.6, the ground truth f (x) = #1 Lastly, / denotes the threshold where the bias and variance terms in Theorem match, and where we observe phase transition between harmless and harmful interpolation. See Appendix D.I for technical details.
Bias-variance trade-off: bias and variance trade-off for the min-RKKS-nomm interpolator as a function of B, reflected in Theorem when setting l = 0 and illustrated in Figure lb. While the statistical bias monotonically decreases with decreasing (i.e., increasing strength of the inductive bias), the variance follows multiple descent curve with increasing minima as 5 decreases. Hence, analogous to the observations in Donhauser
We conclude by discussing how the phase transition arises from a (statistical)
(2022) for linear max-ep- maxx---margii/mmn--- -nomm interpolators, the interpolator achieves its optimal performance at 3 E (0, 1), and therefore at moderate inductive bias. Finally, we note that Liang et (2020) previously observed multiple descent curve for the variance, but as function of input dimension and without any connection to structural biases.
4 EXPERIMENTS
We now empirically study whether the phase transition phenomenon that we prove for kernel regression persists for deep neural networks with feature Icarning. More precisely, present controlled experiments to investigate how the strength a CNN's inductive bias influences interpolating noisy data is harmless. In practice, the inductive bias of a neural network varies by way of design choices such as the architecture (e.g., convolutional vs. fully-connected vs. graph networks) the training procedure (e.g., data augmentation, adversarial training). We focus on two examples: convolutional filter size that we vary via the architecture, and rotational invariance via data augmentation. To isolate the effects of inductive bias and provide conclusive results, we use datasets where we know priori that the ground truth exhibits a simple structure that matches the networks' inductive bias. See Appendix E for experimental details.
Analogous to ridge regularization for kernels, we use early stopping mechanism to prevent noise fitting. Our experiments compare optimally early- stoope CNNs their interpolating versions. This highlights trend that mirrors our theoretical results: the stronger the inductive bias of neural network grows, the more harmful interpolation becomes. These results suggest exciting future work: proving this trend for models with feature learning.
4.1 FILTER SIZE OF CNNS ON SYNTHETIC IMAGES
In first experiment, we study the impact filter size on the generalization of interpolating CNNs. As reminder, small filter sizes yield functions that depend nonlinearly only on local neighborhoods of the input features. clearly isolate the effects of filter size, we choose a special architecture on a synthetic classification problem such that the true label function is indeed CNN with small filter size. Concretely, we generate images of size 32 x 32 containing scattered circles (negative class) and crosses (positive class) with size at most x 5. Thus, decreasing filter size down to x 5 corresponds to stronger inductive bias. Motivated by our theory, we hypothesize that interpolating noisy data is harmful with small filter size, but harmless when using large filter size.
5

---

Published as a conference paper at ICLR 2023
interpolating:
0% noise
20% noise
opt. early-stopped:
0% noise
20% noise
noisy subset
clean subset
45%
subset train error
(opt. early stopping)
100%
test error
10%
0%
0%
Tr11TTTT
5
13
22
31
5
13
22
31
filter size
filter size
(a) Test emror
(b) Training emror of optimally early-stopped models
Figure 2: Convolutional neural network experiments with varying filter size on synthetic image data. (a) For noisy data, small filter sizes (strong inductive bias) induce a gap between the generalization performance of interpolating (bluc) optimally early-stopped models (ycllow). The gap vanishes the inductive bias decrcases (i.e., filter increases). For noiseless data (dashed), interpolation is always harmless. (b) Training error of the optimally early-stopped model (optimized for test error) on the noisy and clean subsets of a training set with 20% label noise. Under optimal early stopping, models with a strong inductive bias ignore all noisy samples (100% error on the noisy subset), while models with a weak inductive bias fit all noisy training samples (0% error the noisy subset). All lines show the mean over five random datasets, and shaded areas the standard error, see Section 4.1 for the experiment setup.
In the experiments, we use CNNs with a single convolutional layer, followed by global spatial max pooling and two dense layers. We train those CNNs with different filter sizes on 200 training samples (either noiseless or with 20% label flips) to minimize the logistic loss and achieve zero training error. We repeat all experiments over 5 random datasets with 15 optimizations per dataset and filter size, and report the average 0-1-error for 100k test samples per dataset. For a detailed discussion on the choice of hyperparameters and more experimental details, see Appendix E.
Training setup:
Results: First, the noiseless error curves (dashed) in Figure 2a confirm the common intuition that the strongest inductive bias (matching the ground truth) at size yields the lowest test error. More interestingly, for 20% training noise (solid), Figure 2a reveals a similar phase transition as Theorem 1 and confirms our hypothesis: Models with weak inductive biases (large filter sizes) exhibit harmless interpolation, indicated by the matching test error of interpolating (blue) and optimally early- stopped (yellow) models. In contrast, as filter size decreases, models with strong inductive bias (small filter sizes) suffer from increasing gap in test errors when interpolating versus using optimal early stopping. Furthermore, Figure 2b reflects the dual perspective of the phase transition as presented in Theorem 2 under optimal early stopping: models with small filter size entirely avoid fitting training noise, such that the training error on the noisy training subset equals 100%, while models with a large filter size interpolate the noise.
Difference to double descent: One might suspect that our empirical observations simply reflect another form of double descent (Belkin al., 2019a). As CNN's filter size increases (inductive bias becomes weaker), so does the number of parameters and degree of overparameterization. Thus, double descent predicts vanishing benefits of regularization due model size for weak inductive biases. Nevertheless, we argue that the phenomenon we observe here is distinct, and provide an extended discussion in Appendix E.3. In short, we choose sufficiently large networks and tune their hyperparameters to ensure that all models interpolate and yield small training loss, even for filter size 5 and 20% training noise. To justify this approach, we repeat a subset of the experiments while significantly increasing the convolutional layer width. As the number of parameters increases for a fixed filter size, double descent would predict that the benefits of optimal early stopping vanish. However, we observe that our phenomenon persists. In particular, for filter size 5 (strongest inductive bias), the test error gap between interpolating and optimally early-stopped models remains large.
4.2 ROTATIONAL INVARIANCE OF WIDE RESIDUAL NETWORKS ON SATELLITE IMAGES
In second experiment, investigate rotational invariance inductive bias for CNNs whenever true labels are independent of an image's 's rotation. Our experiments control inductive bias strength by fitting models multiple rotated versions of an original training dataset, effectively performing

---

Published as a conference paper at ICLR 2023
interpolating:
0% noise
20% noise
opt. early-stopped:
0% noise
20% noise
noisy subset
clean subset
17%
subset train error (opt. early stopping)
100%
test error
12%
8%
38%
3%
0%
0%
12
12
# rotations
# rotations
(a) Test error
(b) Training emror of optimally early-stopped models
Figure 3: Varying degrees rotational invariance when fitting Wide Residual Networks on satellite images. (a) For noisy data (solid), strong bias towards rotational invariance (via the number of augmented rotations) induces gap between the generalization performance of interpolating (bluc) vs. optimally early stooped models (yellow). The gap decreases as the inductive bias decreases (# rotations decreases).
(b) Training error of optimally early-stopped models (w.r.t. the test error) on the noisy and clean subsets a training set with 20% label noise: For maximum rotational invariance (12 rotations), optimally early-stopped models avoid fitting noisy data (close to 100% training error on noisy subset), yet no rotational invariance (1 rotation) requires fitting noise (less than 50% training error noisy subset) for optimal generalization. All lines show the mean over five optimization runs, and shaded areas the standard error, see Section 4.2 for the experiment setup.
varying degrees of data augmentation. As an example dataset with a rotationally invariant ground truth, we classify satellite images from the EuroSAT dataset (Helber et al., 2018) into 10 types of land usage. Because the true labels are independent of image orientation, we expect rotational invariance to be particularly fitting inductive bias for this task.
Truining and test setup: For computational reasons, we subsample the original EuroS training set to 7680 raw training and 10k raw test samples. In the noisy case, replace 20% of the raw training labels with a wrong label chosen uniformly at random. We then vary the strength of the inductive bias towards rotational invariance by augmenting the dataset with increasing number of k rotated versions of itself. For each sample, we use & equal-spaced angles spanning 360", plus a random offset. Note that training noise applies before rotations, that all rotated versions of the same image share the same label. We then center-crop all rotated images such that they only contain valid pixels. In all experiments, we fit Wide Residual Networks (Zagoruyko & Komodakis, 2016) on the augmented training set for 5 different network initializations. We evaluate the 0-1-error on the randomly rotated test samples to avoid distribution shift effects from image interpolation. All random rotations are the same for all experiments and stay fixed throughout training. See Appendix E.2 for more experimental details. Lastly, we perform additional experiments with larger models to differentiate from double descent; see Appendix E.3 for the results and further discussions.
Results: Similar to the previous subsection, Figure 3a corroborates our hypothesis under rotational invariance: stronger inductive biases result in lower test errors noiseless data, but increased gap between the test errors of interpolating and optimally early-stopped models. In contrast to filter size, the phase transition is more abrupt; invariance to 180 rotations already prevents harmless interpolation. Figure 3b confirms this from a dual perspective, since all models with some rotational invariance cannot fit noisy samples for optimal generalization.
5 PROOF OF THE MAIN RESULT
The proof of the main result, Theorem 1, proceeds in two steps: First, Section 5.1 presents a fixed- design result that yields matching upper and lower bounds for the prediction error of general kernels under additional conditions. Second, in Section 5.2, we show that the setting of Theorem satisfies those conditions with high probability over dataset draws.
*Daaa augmentation techniques efficiently enforce rotational invariance; see, e.g., Yang et al. (2019).
7

---

Published as a conference paper at ICLR 2023
Notation Assuming that imputs draws from data distribution (i.e., I, x, v), can decompose and divide any continuous, positive semi-defiite kernel function as
2(x, = Σ (=
Ausha (z)
(4)
R=m++1
1 K (21,21)
where (0a is an orthonormal basis of the RKHS induced by (f.g)v = Egnu [f)))(()] and the eigenvalues d are sorted in descending order. In the following, we write [ike refer to the entry in row i and column j of matrix. Then, we define the empirical kernel matrix for I. K E R=xn with K] = K(x; Zy), and analogously the truncated versions Km and Kym for Kem and Kym- respectively. Next, we utilize the matrices L zm E R= with Wmmli. == (,,), and Dmm diag(A biag(A)...... Am). We further use the squared kernel S(x, x²) Egay [a,,, (z(,za) }} its truncated versions Sam and Sym: as well as the corresponding empirical kernel matrices S, <m: Sym E R=x=. Next, for a symmetric positive-definite matrix, we write Mmin (+) and Mmax (-) (or II-II) to indicate the min and max cigenvalue, respectively, and v₂(+) for the i-th eigenvalue in decreasing order. Finally, we use (. for the Euclidean inner product in Rd
5.1 GENERALIZATION BOUND FOR FIXED-DESIGN
First, Theorem 3 provides tight fixed-design bounds for the prediction error.
Theorem (Generalization bound for fixed-design). Let K. be kernel that under a distribution decomposes as K(x, x²) = Ex A (x') with (E (x))
ōg, v. and {(T;,, v:)) Vi=1 be a dataset with y4 = f + for zero-mean o² o²-variance i.i.d. noise E, and ground truth f*.
Define Ti == min max
nAm
T2 = max
ndm+1 max
}}.
= Pmin mK+m)+X
max 12
[| +|+
max(x.1]
Then, for any E N such that 1 0 and
v Sm v Wm//n
1m
(5)
2
the KRR estimate fx in Equation for any X 2 0 has a variance upper and lower bounded by
Ei-mta (s(S>)) [a 132
Variance (rriance(fa)//F2
17
Tr (S
2r
Ti n
Ti max (X, 1]2
Furthermore, for any ground truth that can be expressed as f*(x) Σ k= and th as defined Equation (4), the bias upper and lower bounded by
axva (z) with a RT
P? (1.5 r1)) max 1)2
[D |
< Bias" fias((ff)))))) < (1 1.5
To max A, 1)2
D a Sm
n²
n
See Appendix A. for the proof. Note that this result holds for any fixed-design dataset. We derive the main ideas from the proofs in Bartlett al. (2020); Tsigler & Bartlett (2020), where the authors establish tight bounds for the min-e2-norm interpolator on independent sub-Gause GabbGaussian features.
Remark 1 (Comparison with McRae et al. (2022)). The upper bound for the bias in Theorem 1 from 11/2
McRae al. (2022) depends on the suboptimal term [D 2m all/n, but also applies more general ground truths. We improve that upper bound in Theorem 3 and present a matching lower bound.
5.2 PROOF OF THEOREM
Throughout the remainder of the proof, all statements hold for the setting in Section 3.1 and under the assumptions of Theorem 1, especially Assumption
KC, E O(d') and max 1) (
Furthermore, as in Theorem 1, we use 5, > 0 with 0 = -
and ليي - -
We show that there exists a particular m for which the conditions in Theorem 3 hold and we can control the terms in the bias and variance bounds.
8

---

Published as a conference paper at ICLR 2023
Step 1: Conditions for the bounds in Theorem 3 that the conditions on V sm and f in Theorem hold with high probability. The following standard concentration result shows that all < satisfy Equation (5) with high probability.
We first derive sufficient conditions such
Lemma (Corollary Theorem 5.44 in Vershynin (2012)). For d large enough, with probability at least 1 - cd-$8 68 all m E On q ") satisfy Equation (5).
See Appendix C.1 for the proof. Simultaneously, to ensure that f* is contained in the span of the first m eigenfunctions, m must be sufficiently large. We formalize this the following lemma.
Lemma 2 (Bias bound condition). Consider kernel as in Theorem I satisfying Assumption 1, and
ground truth f (x) I1 3y with 1 S L S 1- 1 Then, for any m with Am E c dg dg
and d sufficiently large, f* is in the span of the first m eigenfunctions and | E e θ (dq"
See Appendix B.3 for the proof. Note that L' > 1 follows from lx < <6- - 1 in Theorem 1, and allows us to focus on non-trivial ground truth functions.
Step 2: Concentration
the (squared) kernel matrix In a second step, we show that there exists set of m that satisfy the sufficient conditions, and for which the spectra of the kernel matrix K and squared kernel matrix Sym concentrate.
Lemma 3 (Tight bound conditions). With probability at least 1 cd (m, uniformly over all Ex [0, 1), for d sufficiently large and any X R, m E N with max E O(dxx),
nmm E (max (A, 1}), and E O
ng
we have
max
11, E ((),, Tr(S E 0 ddag (1-1))
Σ (=++1
(s(Smm) 3
We refer to Appendix C.3 for the proof, which heavily relies on the feature distribution. Note that the results for in Lemma also imply 7I, 72 O(1).
Step 3: Completing the proof Finally, we complete the proof by showing the existence of particular m that simultaneously satisfies all conditions of Lemmas to 3.
Lemma 4 (Bigendecay). There exists an m such that
n'm (max (onaxx2,11 1})
and
m E
nqq
C On..gg
max max
Furthermore, ussuming I <
[-/g_1] we have Am E dight
We refer to Appendix B.4 for the proof. As a result, we can use Lemmas 1 to 4 to instantiate Theorem for the setting in Theorem I, resulting in the following tight high-probability bounds for variance and bias:
Ex + l2 (1-8) S Variance (ar) Sa + d ggg (1 (1-8)
d 2 11-81-1--BLL--0 x Bias? (fx) & -1---------- -1))
Reformulating the bounds in terms then concludes the proof of Theorem 1.
SUMMARY AND OUTLOOK
In this paper, we highlight how the strength of an inductive bias impacts generalization. Concretely, we study when the gap in test error between interpolating models and their optimally ridge-regulatized or carly-stopped counterparts is zero, that is, when interpolation is harmless, In particular, we prove phase transition for kernel regression using convolutional kernels with different filter sizes: a weak inductive bias (large filter size) yields harmless interpolation, and even requires fitting noise for optimal test performance, whereas a strong inductive bias (small filter size) suffers from suboptimal generalization when interpolating noise. Intuitively, this phenomenon arises from bias- trade-off, captured by our main result in Theorem 1: with increasing inductive bias, the risk on noiseless training samples (bias) decreases, while the sensitivity noise in the training data (variance) increases. Our empirical results on neural networks suggest that this phenomenon extends to models with feature learning, which opens up avenue for exciting future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
K.D. is supported by the ETH AI Center and the ETH Foundations of Data Science. We would further like to thank Afonso Bandeira for insightful discussions.
REFERENCES
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117:30033-300700 2020.
William Beckner. Inequalities in Fourier Analysis. Annals of Mathematics, 102:159-182, 1975.
William Beckner. Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn. Proceedings of the National Academy of Sciences, 89:4816-4815 1992.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- Beachine practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116:15849-5554, 2019a.
Mikhail Belkin, Alexander Rakhlin, and Alexandre Tsybakov. Does data interpolation contradict statistical optimality? In Proceedings of the Conference on Learning Theory (COLT), 2019b.
Alberto Bietti. Approximation and Learning with Deep Convolutional Models: Kemel Perspective. In Proceedings of the International Conference on Learning Representations (ICLR), 2022.
Alberto Bietti, Luca Venturi, and Joan Bruna. On the Sample Complexity of Learning under Geometric Stability. In Advances in Neural Information Processing Systems (NeurIPS). 2021.
Simon Buchholz. Kernel interpolation in Sobolev spaces is not consistent in low dimensions. In Proceedings of the Conference on Learning Theory (COLT), 2022.
Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart. What can be learnt with wide convolu- tional networkds? arXiv preprint arXiv:2208.. 01003, 2022.
Emmanuel J. Candes. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathématique, 346:589-592, 2008.
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterizationn in model compression: From double descent to pruning neural networks. In Proceedings of the Conference Artificial Intelligence (AAAI), 2021.
Niladri S. Chatterji and Philip M. Long. Foolish Crowds Support Benign Overfitting. Journal of Machine Learning Research (JMLR), 23:1-12, 2022.
Konstantin Donhauser, Alexandru Tifrea, Michael Aerni, Reinhard Heckel, and Fanny Yang. In- terpolation can hurt robust generalization even when there is no noise. In Advances in Neural Information Processing Systems (NeurIPS), 2021a.
Konstantin Donhauser, Mingqi Wu, and Fanny Yang. How rotational invariance of common kernlls prevents generalization in high dimensions. Proceedings of the International Conference on Machine Learning (ICML), 2021b.
Konstantin Donhauser, Nicolò Ruggeri, Stefan Stojanovic, and Fanny Yang. Fast rates for noisy interpolation require rethinking the effect of inductive bias. In Proceedings of the International Conference on Machine Learning (ICML), 2022.
David L.. Donoho and Michael Elad. On the stability of the basis pursuit in the presence of noise. Signal Processing, 86:511-5322 2006.
Noureddine El Karoui. The spectrum of kernel random matrices. Annals of Statistics, 38:1-50, 2010.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimen- sionality convolutional teacher-student scenarios. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
10

---

Published as a conference paper at ICLR 2023
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. Annals of Statistics, 49: 49:1029-1054, 2021.
Nikhil Ghosh, Song Mei, and Bin Yu. The Three Stages of Learning Dynamics in High-dimensional Kernel Methods. In Proceedings of the International Conference on Learning Representations (ICLR), 2022.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer New York, 2001.
Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Introducing EuroSAT: A Novel Dataset and Deep Learning Benchmark for Land Use and Land Cover Classification. In Proceedings of the IEEE International Symposium on Geoscience and Remote Sensing (IGARSS), 2018.
Sandesh Kamath, Amit Deshpande, Subrahmanyam Kambhampati Venkata, and Vineeth N Balasub- ramanian. Can We Have It AlI? On the Trade-off between Spatial and Adversarial Robustness of Neural Networks. In Advances Neural Information Processing Systems (NeurIPS), 2021.
Jingling Li, Mozhi Zhang, Keyulu Xu, John Dickerson, and Jimmy Ba. How Does a Neural Network's Architecture Impact Its Robustness to Noisy Labels? In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. Annals of Statistics, 48: 18:9 1347, 2020.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum norm interpolants and restricted lower isometry of kernels. In Proceedings of the Conference Learning Theory (COLT), pp. 2683-2711, 2020.
Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting. arXiv preprint arXiv:2207.065: 06566, 2022.
Andrew D. McRac, Santhosh Karnik, Mark Davenport, and Vidya K. Muthukumar. Harmless interpolation in regression and classification with structured features. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Proceedings of the Conference on Learning Theory (COLT), 2021.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontracciiitty and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022.
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint arXiv:2111.08308, 2021.
Vidya K. Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas Information Theory, 1:67-83, 2020.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and llya Sutskever. Deep double descent: where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 12403,, 2021.
11

---

Published as a conference paper at ICLR 2023
Kento Nishi, Yi Ding, Alex Rich, and Tobias Hollerer. Augmentation Strategies for Learning With Noisy Labels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with Laplace kernels is high- dimensional phenomenon. In Proceedings of the Conference on Learning Theory (COLT), 2019.
Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Early stopping and con-paramttric regression: an optimal data-dependent stopping rule. Journal of Machine Learning Research (JMLR), 15: 335-366, 2014.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Amartya Sanyal, Puneet K. Dokania, Varun Kanade, and Philip Torr. How Benign is Benign Overfitting? In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Bernhard Schölkopf, Alexander J. Smola, and Francis Bach. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2018.
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society, 58:267-288, 1996.
Alexander Tsigler and Peter L. Bartlett. Benign overfitting in ridge regression. arXiv preprint 2422:20009.12266, 2020.
Roman Vershynin. Compressed Sensing: Theory and Applications, chapter Introduction to the non-asymptotic analysis of random matrices, pp. 210-268. Cambridge University Press, 2012.
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum & norm interpolation of noisy data. In Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS), 2022.
Yuting Wei, Fanny Yang, and Martin J. Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Fanny Yang, Zuowen Wang, and Christina Heinze-Deml. Invariance-induccngg regularization using worst-case transformations suffices to boost accuracy and spatial robustness. Advances Neural Information Processing Systems (NeurIPS), 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide Residual Networks. In Proceedings of the British Machine Vision Conference (BMVC), 2016.
12

---

Published as a conference paper at ICLR 2023
A GENERALIZATION BOUND FOR FIXED-DESIGN
We prove Theorem by deriving a closed-form expression for the bias and variance, and bounding them individually. Hence, the proof does not rely on any matrix concentration results.
A.1 PROOF OF THROREM 3
is well-known that the KRR problem defined in Equation (2) yields the estimator (xxx) -
y(o) k(z), where I, v. ff ( f + +.,
[(z) [K(11, z).... x)),,
and H = K Mr, For this estimator, both bias and variance exhibit closed-form expression:
Bias² (fa) Egau (f [. + TH
Egael (f((z) f (K=))
Egwn [m(x)²] 2FTH Eeww (/" F E ((o
a -2 H T Sm D Sm a a a H SH
L sma.
(6)
1
Variance (
Brnu Ee Ee( + TH R [ +) k(z)))
BxneBi EH
Σ Eleg) H HT (a)
Tr (H-
Step (i) uses the definition of the squared kernel S, that (x) Σx= (x) as f is in the span of the first eigenfunctions, and the following consequences of the eigenfunctions' orthonormality:
m
m
E Exwa [5(()]]
u.aw-rr (1) =
Ogax-dR = =|aa|B
A
k
ExpD [[)((((()
ak Aur [ahn (xxe)
k= ===1
m
(x = [ mm Smmal
We now bound the closed-fone form expressions of bias and variance individually.
Bias
Lemma 5 below yields S =
V 5m
+ SSm Hence, the bias decomposes into
mm
Bias 2 (ff) = aTa - 2a LT
5m
Smma + a TT
Sm
Sm
T
Sm
a
a T T
H S
H
<ma
In
m
VT
H
1
Sm
a v
H
H
1
mma
B1
B
First, we rewrite Bi as
B Im
Dam
Zm
H
Sm
a
i
-1
Km
mm
T Sm
T V
D
cm
T
Sm
H. Hym
mmml
D
mm
D
Zm
D
VT
V
Sm
D
mm
a
(
13

---

Published as a conference paper at ICLR 2023
where (i) uses the decomposition H Kgm + Hom with Hom the Woodbury matrix identity.
Kym AIns and (it) applies
Second, can upper-bound B2 follows:
B2 S
|5ym
L Sm
H
Sma
|S
(D
D
Smm
Sm
T
Sm
H-2
Sm
Dsm (D a)
[ >m
la
D
D
TTT
St
Hol v
Sm
mm
T
H
D
mm
D +
D Sm
Sm
pm
Sm)
S S mml
Sm
H
m
sm
(
Sm
+
Sm
sm
Sm a
Bi
where (1) uses Lemma Thus, the bias can be bounded by B1 + C2) with C1 2 0.
We proceed by upper bounding C₁:
V Sm
Sm
1+ C+ 1hi1+nl 1+|n 2ml
Amia (H )
(
ndm++ll [
ndm+1 ( Sml + A)
$
1+ 1.5
S 11+1 1.5
(Nuin (k>m) + +2²
(pmin (Kym) 2)²
51+ 1.5 ndm+1
max (1, 1}2
K +
max (), 13 (Amin (K mm) + A)2
max 1}
S1+ 1.5 12 ndm+1
ri 11
(4)
ndm+1
1 + 1.5 7
max
ri
max
1 + 1.5
1.5
T2:
(9)
where (i) uses Equation (5) to bound
| Sm L (mmm/m) /nl and Lemma to bound ||S>m||| and (it)
follows from or + 1 S (c + 1) max (2,, 1} for e 2 0.
Hence, to conclude the bias bound, we need to bound B, in Equation (8) from above and below. Upper bound:
B1
<
D
2m
Np Cm
m
V
<m
|D 1 all
11
n²
H 112
DD_1 mm
D
al2
TT.
Sm 1 5m
2
n
Mmin
(4)
1 ||
a
< 4 (m
+ 2)2
mm
n²
D sm
a
= 4r max (A, 1
(10)
n²
where (i) follows from Equation (5).
Combining Equation (9) in (i) and Equation (10) in (ii) yields the desired upper bound on the bias:
2 < SB+B & (1 B (0) & (1+15
22 !
(t)
1 1 1.5 1270 max (2, 1)2
| 1
mm all
B
n²
14

---

Published as a conference paper at ICLR 2023
Lower bound:
2
D
ypT Stn
H 5m
[
11
all
2 Punin
Sm
Sm
Sin
n
n1
n2
[ Sm a al?
2m 4 mm
n²
71
Amin (ym)
ndmm max 11
D
amal?
CAI
max(A, 1]2
Sm
1.5
max [.1]
+
n²
Pmin 33m max(A.1]
(9)
71
min
72
max A, 1}²
D sm
all
1.5 + r
max ( 1
n²
2
D
all
F1
max X, 1]² Sm
1.5 +r
n²
where (i) follows from Equation (5), and (di) from the fact that
cx+1 2 1tc min(x, 1) for 2,
Since 2 > B1. this concludes the lower bound for the bias.
Variance As for the bias bound, we first apply Lemma to write Dm VT and decompose the variance in Equation (7) into
Sm + Sym
Sm
Variance (a) Tr (H-
v
D2
H
Tr
(H-'S, 2m H
(1I)
Sm
Sm
Sm
Next, we rewrite V1 as follows:
V
Tr
H
DT
H
Tr
D
cm
TT Sm
H 2
sm
D
Sm
(
Tr
(D
Sm
V
Sm
H
Sm
-1
y
Sm
H.
mm
Sm
D Sm
+
T
Sm
H
Sm
Tr
D-1
Sm
Sm
m
1 <m
Vp
Sm 5m
H
cm
D-11
Sm
2m 5m
Sm
n
n
n
where (i) follows from Lemma
To bound V1 and V2, bounded from above and below by the size of the matrix times the largest and smallest eigenvalue, respectively. This yields the following bounds for Vi:
the fact that the trace is the of all eigenvalues. Therefore, the trace
D
V
V
W
V Sm
D-1 1 Km
D
WT
V
V <
m
cm
Sm
Sm.
71
n
n
11
m
4 max (A, 1
T
Sm
Sm/
n
(6)
6
m 2
max A, 132 (Jmmin (Kym) + 2)
Pmin (Hym)
6
F1
15

---

Published as a conference paper at ICLR 2023
and
Vi
Mmnn
D==
sm
VpT 5m
H
Sm
4 mm
2m
D
mm
y Sm
H
n
n
n
(18) m
71
Ti max X, 11²
Mmin
T Sm
v "mm/n)
1.5 + rl
K X)²
(iv) 1 m
r1
max {A, 1}²
2 m
r1
71.
2 n
1.5 +
[| mm + A)
T2 + +r1)
For (i) and (iti), we bound the terms analogously the upper and lower bound of Bi, and use
Equation (5) in (ti) and (iv).
Next, the upper bound V2 follows from special case of Hölder's inequality follows:
1/2 = Tr (H H < Tr (S
(8)m)
H 21
Tr (S mm) Pmin (Ken Sm Hym) Mmnn (H
Tr (S mm)
Tr (S>m)
ri max (X, 132¹
For the lower bound, we need more accurate analysis. First, apply the identity
H = (Hym + (mm)= H H 5m K cm (Hym + Kmm)
(12)
which is valid since H and Hom are full rank.
Next, note that the rank of A is bounded by the rank of Ksm. which can be written as T Sm Dmm V Sm and therefore has itself rank at most m. Furthermore, Equation (5) implies that I L Sm has full rank, and hence S
Let now (V1,-.., Prank(A) be orthonormal basis of col (),, and let (Urank(A)+1;->> vn) be an orthonormal basis of col col(A) Hence, (ui...., Un an orthonormal basis of R", and similarity invariance of the trace yields
1/2 Tr (H H 1)
D H I S
-
o T Sym H
i=rank(A)+1
(HE 5m
-ASS (H
A)e
T=rank A1
H S H H
iStan A)+1
U. 3SSmmu U/:
m
(=rank(A) +1
Tr (PTS P)
where P is the projection matrix of R onto col( (o) and (i) follows from Equation (12). Step (ii) uses that, for all > rank(A A), n is orthogonal to the column space of A, and hence
H - A)S H mm
A)U
= H pm S-m H 11
A
Sy m
H Sm
H >m
A + uu. AS mm Av
>m
16

---

Published as a conference paper at ICLR 2023
Finally, let (a(()) be the i-th eigenvalue of its argument with respect decreasing order. Then, the Cauchy interlacing theorem yields (ran S (PTSsmm P) for all i = 1..... rank(A). This implies
n n-rann(A)
n-rank(A) A)
Tr TTTS pm
P)
Σ
(PTS
(rank(A)+i(S2n)
1G m)
Σ
(s(S)
iml+rank(A)
i=1+m
where (i) uses that the rank A is bounded by m. This concludes the lower bound on 2/2 as follows:
> m+1 (5
2 mm m
(4((gmm)
1/2 Tr (H'S S (SSHH H)
12
r2 max (A,1) 1)2
A.2 TECHNICAL LEMMAS
Lemma 5 (Squared kernel decomposition). Let K. a kernel function that under a distribution can be decomposed K(x,x') Eg ( (x))))())) where Exwoltr(z))t the (x)] ōk, Then, the squared kernel S(x,x') = Eznu (x(, 2)(((r 2)] can be written as
S(x, x²) Σ (((x(t))ee(()),
k
for any m > 0, the corresponding kernel matrix can be written as Sm Sm Sm + +Smm
D3 Vi
Proof. The statement simply follows from
S(x, x')= = Σ
(edenthe Egna [wh (3)())/) (2x)
Σ
62,00
k
Lemma 6 (Corollary of Lemma 20 in Bartlett et al. (2020)).
D Dzm
L
H
D mm
D + VT H
Lm
1
H
L mm
5m
Sm
D Sm
+
cm
Sm
5m
Proof.
D Dem
T
H 2
sm D.D Sm =D D1/22 Sm
1/2
Sm T H -
D.DD D/22 5m
Sm
Sm
Sm
Sm
(
1/2
Im + D Sm
1/2
T H
D 1/2
-1
D
1/2 Sm
TTT
H
sm
1/2
1/2 Sm
Sm
Sm
mm
Sm
Sm
Sm
Im D 1/2
T
T
1/2
D 1/2
5m
-(D=
D -1 5m
+
VT
5m
VTT
H
T
Sm
D-1 Sm
TT
H Sm
V
Sm
where (i) applies Lemma 20 from Bartlett al. (2020).
Lemma 7 (Squared kernel tail). For m let Szm be the kernel matrix of the truncated squared kernel Szm = Σ Eksm bpom (o and let K Xm be the kernel matrix of the truncated original Then,
kernel K = Eksm
S 3lml S Am+1 Amtt||Kzmll
17

---

Published as a conference paper at ICLR 2023
Proof. We show that for any vector v, uT I Am+1tTK, >mm, which implies the claim. To do SO, we define K E Rn*n with Lkke = 2h (2,)))))(z)) for all k > m. Then we can write
K = Exsm A & and Sym Exsm X R Since the eigenvalues are in decreasing order, we have d S Am+1 for any k > m, and thus
r y
Σ Σ12e N Uuo S Am+1
Σ k2T
Y Am+12 KK Kym
k2m
B CONVOLUTIONAL KERNELS ON THE HYPERCUBE
First, Appendix B.1 provides way to decompose general functions for features distributed uniformly on the hypercube. Next, Appendix B.2 uses those results to characterize the eigenfunctions and eigen- values cyclic convolutional kernels. Finally, Appendices B.3 and B.4 apply this characterization to prove Lemmas 2 and 4, respectively.
B.1 GENERAL FUNCTIONS ON THE HYPERCUBE
This subsection focuses on the main setting in our paper: the hypercube domain {-1, together with the uniform probability distribution, previously studied in Misiakiewicz & Mei (2021). For any S C [1, {l.....d} d}, we define the polynomial
Vs(
II b jES
(13)
of degree (S), where [zlg is the j-th entry of æ (-1, It is easy to see that sc.... is set of orthonormal functions with respect the inner product (J Those functions play a key role the remainder of our proof; as it turns out, they are the eigenfunc- tions of the kernel in Section 3.1. Towards formal statement, define the polynomials
P2-u(--1,1 (z))
(x. (m, = B(I,d) Vd
)s(2))s(sz',
(14)
|S|=]
where B(I, = KSS S (1, d) |1 = = (1)
(
(15)
Note that gi(d)) only depends on the (Euclidean) inner product and x'. Furthermore, (g( M is a set of orthonormal polynomials with respect to the distribution of (at, xx,x")/v The following lemma shows how such polynomials form an eigenbasis for functions that only depend the inner product between points in the unit hypercube.
Lemma 8 (Local kernel decomposition). Let k: R , R be any function and E N Then, for any x, x E 1,1, 13d we can decompose K² k((xxx²") 2dd
(I,x")
Σ )s(c))s((').. 15
(16)
B(I, d)
Proof. Note that the decomposition only needs to hold at the evaluation of к in the values that x') /d can take, that is, computed {-1, -11-111 2/d, ... 2 1, 1}. Since that set has cardinality d ++ 1, we can write a linear combination of d uncorrelated functions. In particular, (g(()) dd Ji=n is a of such functions with respect the distribution of (a,x''/vVd and hence
R (x.2"))
(
vd
for some (unknown) coefficients et. Finally, the proof follows by expanding the definition of g in Equation (14) and choosing c(d) Ct.
18

---

Published as a conference paper at ICLR 2023
B.2 CONVOLUTIONAL KERNELS ON THE HYPERCUBE
While the previous subsection considers general functions on the hypercube, we now focus on convolutional kernels and their eigenvalues. This yields the tools prove Lemmas 2 and 4. In order to characterize cigenvalues, we first follow existing literature such as Misiakiewicz & Mei (2021) and introduce useful quantities.
Let S S {I....,d]] d}. The diameter of S is
r(S) = max min (mod (j - i, + 1, mod (i j. + 1} AJES
for S + and (0) Furthermore, we define
c(l.q.d) ((S S (L..... d) S|| (,7 S ggوl.
(17)
Intuitively, the diameter of S is the smallest number of contiguous feature indices that fully contain S. The following lemma yields an explicit formula for C(I, q, d), that is, the number of sets size I with diameter at most q. Lemma 9 (Number of overlapping sets), Let 1, q, d N with S q < d/2. Then,
d( (()) 1> 0,
1= 0.
Proof. Since the result holds trivially for I = 0 and = 1, we henceforth focus on 1 2 2. Let Č(1, 7, .) be the number of subsets S C {l,..., d} of cardinality |S| = / with diameter exactly 7(S) y. First, consider C(2, 7, d). For each set, we can choose the first element from d different values, and the second as mod ((i - 1) + (7 - 1), d) + 1. In this way, since q < d/2, we count each set exactly twice. Thus,
C(2,7, d) = 2.2 2
d.
Next, consider / 2. We can build all the possible sets by starting with one of the C(2, 7, d) sets, and adding the remaining - 2 elements from 2 possible indices. Hence, every fixed set of size 2 and diameter 7 yields (?-2) different sets of size L. Furthermore, by construction, every set of size and diameter results from exactly one set of size and diameter 7y. Therefore,
7(1,7 71 = d (--
The result for 1 2 2 then follows from summing Č(1,7; d) all diameters 7 $ gF
(1_2)
2
@ d q (
d( d
where (i) follows from the hockey-stick identity.
Now, we focus on cyclic convolutional kernels IC as Equation (1). First, we restate Proposition from Misiakiewicz & Mei (2021). This proposition establishes that Y's for S C {1...., d} are indeed the eigenfunctions of IC, and yields closed-fone eigenvalues Às up to factors elg) S|5) that depend on the inner nonlinearity k. Next, Lemma 10 uses additional regularity assumptions on k to eliminate the
c(a) dependency S[8] This characterization of the eigenvalues then enables the proof Lemmas and 4.
Proposition (Proposition I from Misiakiewicz Mei (2021)). Let be a cyclic convolutional kernel over the unit hypercube as defined in Equation (1). Then,
(Fikk)) (8.)))
K(x, 21)
Σ
Σ (sDss())D's(''),
(3)
19

---

Published as a conference paper at ICLR 2023
with
c()) 4 + 7()) Sisi d)(
As
where 5/8) are the coefficients of the k-decomposition (Equation (16) over (-1, Alternatvely,
K(x,x') (
where we order all Sy S [L....,d} with (Sk) S q succh that As A524. In particular, Ase Ak-
We refer to Proposition 1 from Misiakiewicz & Mei (2021) for formal proof. Intuitively, the result follows from applying Lemma for each subset _ (I.....d possible because crucially, any subset of q features is again distributed uniformly
...,.,,,, d} of contiguous elements. This is
the g-dimensional unit hypercube. Lastly, the factor q + 1 7()) stems from the fact that each eigenfunction Vss appears many times there are contiguous index sets of size (S) supported in a fixed contiguous index set of size q. In other words, the term is the number shifted instances of S supported in contiguous subset of features.
As mentioned before, Proposition characterizes the eigenvalues of cyclic convolutional kernels IC clq) up to factors Sis) that depend on the inner nonlinearity K. To avoid the additional factors, we require the following regularity assumptions:
Assumption (Regularity). Let T =
[ 4+ 3 A cyclic convolutional kernel K(x,,
2 K (#uua) (.o))) from the setting of Section 3.1 with inner function satisfies the regular-
ity assumption if there exist constants 2 T, d,,e" e" and series of constants {cr > 0] such that, for any q 2 c, the decomposition
( q +1 11-7(5)
K(x,x')=
Σ
)'s (x)))s
S dB((S),9)
(S) |8|=1
from Proposition / over inputs x, x' E (-1,, 1]a satisfies
<(0) 2 4 11 E (0.....T)
(18)
(1) 2 0 <> T
(19)
d'
(00) < qT I+1
1I E T)....,T).
(20)
Σ (1) c 120
(21)
For sufficiently high-dimensional inputs v, x', Equations (18) and (19) ensure that the convolutional kernel [(x,, x') in Equation (1) is a valid kernel, and that it can learn polynomials of degree up to T. Indeed, if <) (9) = 0 for some 1, then there are polynomials of degree among the eigenfunctions of KC. Furthermore, Equations (18), (20) and (21) guarantee that the eigenvalue tail is sufficiently bounded. This allows to bound KK>m and Mmin (K>m) in Appendix C.
Our assumption resembles Assumption by Misiakiewicz & Mei (2021); For one, Equations (20) and (21) are equivalent Equations 43 and 44 in Misiakiewicz & Mei (2021). Furthermore, Equation (18) above a slightly stronger version of Equation 42, where strengthening is necessary due to the aonmttyypt nature of our results.
We still argue that many standard k, for example, the Gaussian kernel, satisfy Assumption with our convolution kernel K. Because such satisfy Assumption I in Misiakiewicz. & Mei (2021), we only need to check that they additionally satisfy our Equation (18). K is a smooth function, we have <(()) (* (0) o(1) for all I < T, where f² is the I-th derivative of In particular, all derivatives of the exponential function at 0 are strictly positive, implying Equation (18) for the Gaussian kernel if d is large enough.
20

---

Published as a conference paper at ICLR 2023
The final lemma of this section is corollary that characterizes the eigenvalues solely in terms of [S), and further shows that, for d large enough, the eigenvalues decay as |S| grows.
Lemma 10 (Corollary of Proposition 1), Consider cyclic convolutional kernel in Proposition I that satisfies Assumption I with E ((d²) for some 3 E (0. 1). Then, for any S _ ........... d} such that (SS) S q and [S| < T, the eigenvalue As corresponding to the eigenfunction (2( satisfies
As E Ω
and As O
(22)
dl
d d-
Furthermore,
max As E dd.qT-I) 18 r())
(23)
Proof. Without loss of generality, assume d is large enough such that > g/2 2 c/2, where is constant from Assumption 1.
Let S C {l....,d} d) with 7(S) S be arbitrary and define |S| and r = q + 7(S). Since I I ((5) 9, have
1 1 I
Furthermore, since B((,g) (9), we use the following classical bound on the binomial coefficient throughout the proof:
(i) o' s B(l, q) - (7) d'
For the first part of the lemma, assume |S| < T. Then, using Assumption 1, we have
(4) 1 d'r
As dB(1,qg
S c11 dy
S or,1 d
g d
1 cr
1
d'e!
d
a22 dg'
CT dq
for some positive constants C1,1 that depend on I, CT.1 maxie (0....T--1) Ct,, and CT22
min Cr2 Step (i) follows from the upper bound in Equation (21) with non-negativity in
Equations (18) and (19), and (ii) follows from the lower bound in Equation (18). Since CT,1 and cr,2 do not depend on this concludes the first part of the proof.
For the second part of the proof, we consider two cases depending on whether |S| E [T,9 T] or [S] q T. Hence, first assume T 1S1 S q- T. Then,
(8) As 1sl
4+1 7(S) (1i)
9 1-1-8 9+1-7(S) 7SS)
(iH)
S d" 9
CTT dq
(24)
((3))
d(7)
d (2))
where (i) follows from Proposition 1. step (ii), we use that (13) is minimized when |S] has the largest difference to q/2. Lastly, step (itl) applies the upper bound from Equation (21) together with non-negativity of Eist in Assumption 1, and the classical bound on the binomial coefficient.
Now assume S > q T. Then,
9 0+1 1 - (S))
q
As Eisl
< Eg-(9-191)
d(2))
9 d
d(
(g- SS)
(8)
q
Eg (g-1S1)
d
9-15)
(18)
(q - 1
5 En (g-(1181)
dga
(ie)
(g | 0 18
(0) TT
(25)
dq"
T 151) 1 |s|
dg"
21

---

Published as a conference paper at ICLR 2023
where (i) follows from Proposition 1, (ii) from the fact that (,**) (2) (tid) from the classical
bound for the binomial coefficient, (fo) from Equation (20) in Assumption 1, and (t) from the fact
that |S| < T in the current case.
Combining Equations (24) and (25) from the two cases finally yields
max 1812T (S)
Às S max
max
As
max As
T TS S9--s-- 7(8)59
18129-T TT 7(8)59
CTTTT CTT
S max
E
dg"-I1' dgd"
dq
which concludes the second part of the proof.
B.3 PROOF OF LEMMA
First, note that f Vs- for S = fl..... L"}. Since | > L", Proposition yields ( (4)
1
Ag- E1 dB(L',9)
E
w(Am):
dq
where (i) uses Equations (18) and (21) in Assumption 1 for I T and d large enough to get (4)) SL- (1), and (ti) uses Am o - Hence, for d sufficiently large, Às- > Am- Since the cigenvalues are in decreasing order, this implies that f is in the span of the first m eigenfunctions. This further yields
D sm all As- θ (dgt
since the entry of corresponding V/s- is while all others are O.
B.4 PROOF OF LEMMA 4
Before proving Lemma 4, we introduce the following quantity:
lx
(26)
Intuitively, L corresponds to the degree of the largest polynomial that cyclic convolutional kernel as
defined in Equation (1) can learn. This quantity plays key role throughout the proof Lemma 4, and Lemma later. Finally, note that defined in Theorem can be written {-6,-1 L.
Proof of Lemma 4. First, we use Proposition write the cyclic convolutional kernel as
K(x, x') Σ Σ AsDs(c)ss(t')= = Σ As. (x))ss,
1=0
{S)
[S
where the As are ordered such that ASE.
AsE
For the first part of the proof, we need to pick an m E N such that ndm E θ (max 1}) and
m E (xx1 We will equivalently choose m E O(dg²) with Am E θ digh+s) since
E (dd) and max (A, 1} E ((dx), we have
max ( X, 13
d
de
1
θ
= 0
n
de
(++e++((+8))
d gb+s
d''q
8
d1 +1 (1+txx+,((1.t00) = =
ng
max
θ
dea
=
dea
The remainder of the proof proceeds in five steps: first construct a candidate Sm {1, . d) with ((Sm) ) & q, show that the rate of the eigenvalue corresponding to Vs... satisfies As.. = Am
(ggtt>)) show that the rate of m E O(dg*), ). establish θ ag max(A.1] S O(n q 3). and finally
show that Am E o ( for appropriate L*.
22

---

Published as a conference paper at ICLR 2023
Construction of m
We consider two different S.m depending on 6:
Sm [1, ..... L, 1
8 (0, 8= 0.
(27)
(1.....,44 L, [g/2[}
For d and hence q ((d)) large enough, Sm is well-defined, |Sml L + 1, and the diameter is
(( { 19
[g/22] (
8 8 (0,
5=
For the rest of the proof, assume that is sufficiently large.
Rate of As Using Proposition I and |Sml L + 1, we can write
(4) q + (Sm.. Et+ 1
Asn
First, we show that the numerator is + (6-- for both definitions of Sm- In the case where E (0, 1), we have
+ 1-1-1 1+1-19+1-10 --1------------111--- [ o (q'-)),
where (i) follows from and sufficiently large. the case where = 0, we have g + [g/2] S q e
+ 1 [g/2] 2 g/2 (gg).
Thus, since 8 in this case, the numerator is in (g)) O(g²-5).
As the denominator does not depend on 8, we use the same technique for both and å E (0, (). The classical bound on BL + 1, g) = (. yields
J+1 5
q
- [+11 selt1 (
4+1
Sigh1
L+1
1++1
Therefore, dB(L + 1, θ (dq
Finally, since + < T [4 + 48/37. we have SL+1 @(1) by Equations (18) and (21) in Assumption for d sufficiently large. Combining all results then yields the desired rate of As,, as follows:
(g)
g/- dgitt) (
Asm e
(d.gtts)
(28)
Rate of m To establish m E O(dg"), we bound m individually from above and below.
Upper bound: Since the eigenvalues in decreasing order, bound from above by counting
how many eigenvalues are larger than Am- To do so, we use |Sm = L + 1, and show that for d sufficiently large, all S₁. with |S&| L. correspond eigenvalues As, < Asm We first decompose
max k: 11
Asa max
max k:
Ase
max Ase k: 2T rSe)5n
7($))5
25
M:
For Mj. let le with L 1< SA/ < T' be arbitrary. Then,
( As
1 )
0 dgg.t1 )
(4)
0
c o
C o(Asm))
dgi Sul-1
23

---

Published as a conference paper at ICLR 2023
where we apply Equation (22) from Lemma 10 in (1), and use Equation (28) with 8 1 in (ii). This implies M1 E oAAs..)
For M2. directly get
(6)
( C
( o
dgl+1 (
1
(1it)
M2 max AsE
(gllt
S o(Asm)
A: Se 27 (S
dy
where we apply Equation (23) from Lemma 10 in (i), (ii) follows from L + 2 S T, and step (iii uses Equation (28) with < 1.
Combined, we have ciently large and |Sx > L + 1, we have As, < As... For this reason, m is at most the number of eigenfunctions with degree larger than L+11
(SS))) Às max [M,, M2} o(As..). Thus, for d suffi-
L-1 m q().
(1)
E O(dg"),
where (i) uses Lemma 9 for d large enough with (7) E O(d))
Lower bound: By construction of Sm in Equation (27), we have ((Sm) 2 Lg/2]. This, combined with Proposition implies that the indices of all polynomials with degree L +1 1 but diameter at most [q/2] - are smaller than m. Hence, for large enough d, Lemma yields the following lower bound:
M 1,, - 1, (000==111-1
[g/2] [1//2-22 -2 L (L//2 )=)= 2
(L0/21-2) L
E ((dg"))
L
The upper and lower bound together then imply E ((dq"). This concludes the existence of an m E N such that Am and m exhibit the desired rates.
Rate of with respect to We can write
E O(d') 2 (d d
e (dgl (ar1*1+
θ (dg1=1++0)
Combining this with L < we directly get O(dq")) S Old =1) = O(ng -
Rate of Am for appropriate L*
Since ndm, @(max(X, 11),
we have
max max(X,
de
1
Am e
d deggtts 4
dgL+5
where (i) uses the identity 1=1+ Ex + 3(L + 8). Assume now L v need to consider two cases depending 6. 5 > 0, then I < L + 1, and we have
For the remainder,
9 dgb--1
Am E O
So
If 8 then L S L, and we have
9 dg
dgا- )
Am
Co
Co
dgb
In both cases, Am E o )
concluding the proof.
C MATRIX CONCENTRATION
This section considers the random matrix theory part of our main result. First, Appendix C.1 focuses on the large cigenvalues of our kernel, and proves Lemma 1. Next, Appendices C.2 and C.3 focus on the tail of the eigenvalues, culminating in the proof of Lemma 3. Lastly, Appendices C.4 and C.5 establishes some technical tools that throughout the proofs.
24

---

Published as a conference paper at ICLR 2023
C.I PROOF OF LEMMA
In this proof, we show that the matrix Vp V /w//n concentrates around the identity matrix for all Sm
m E O(nd-85), thereby establishing Equation (5). Let in be the largest m E Ong The proof consists of applying Theorem 5.44 from Vershynin (2012) to the matrix V sg. and extending the result to all suitable choices m simultaneously.
More precisely, let ē be the implicit constant of the )nnqt")-notation, and define mn to be the largest W E N with m < č ng- Note that rn exists, because is large enough and fixed.
Bound for m To apply Theorem 5.44 from Vershynin (2012), we need verify the theorem's conditions on the rows of v <n In particular, we show that the rows are independent, have common second moment matrix, and that their norm is bounded. Let [ gill, indicate the i-th row of v <m paxi We may write each row entry-wise as
L Msm,a = (i;) (2()4) ... (x:))"
First, the rows of v si are independent, since each row depends different wi, and we assume the data to be i.i.d..
Second, since the eigenfunctions are orthonormal w.r.t. the data distribution, the second moment of the rows is E [ s.,,,, sm][ = La for all rows i E (1..
Third, show that each row has a bounded norm, we use the fact that the eigenfunctions Vk in Equation (13) over {-1, 13d satisfy {x(x;)² = for all k. Thus, the norm of each row is
| smlulle
(x;)²
E Vn.
k=1
We can now apply Theorem 5.44 from Vershynin (2012). For any 2 O, this yields the following inequality with probability i
where e is an absolute constant:
sm
m VV
Ln
S max
where A
n
The choice 1 / a yields max ||, 1/2, and the following error probability for
large enough d:
(4)
exp {
-dd ng
1 S d d'exp--dg $
m exp
-c
S ng
4mn
where (i) follows from i E O(nq
Bound for any < m Note that TT L <m is a submatrix of D L smh Thus,
V
sm
Sm
I
is also a submatrix of
I
Therefore,
VTT Sm
V Sm
V
I.
<
m
I
S 1/2
with probability at least
cd-35
uniformly over all S m.
C.2 FURTHER DECOMPOSITION OF THE TERMS AFTER m
In this section, focus the concentration of the smallest and largest eigenvalue of the kernel matrix K mm to prove Lemma 3. However, this proof is involved, and requires additional tools. In particular, we further decompose Kym into kernels Kr, and K2.
25

---

Published as a conference paper at ICLR 2023
In the following, we consider the setting of Theorem I with convolutional kernel K. that satisfies Assumption 1. We define the additional notation
and L
B
Intuitively, L is the maximum polynomial degree that K. can learn with regularization, and is the analogue without regularization. Finally, note that 6 and defined in Theorem can be written as 8 f L and 8 1 L. respectively.
We now introduce the additional kernels, and then show in Lemma 11 that Ksm Ki + K2. First, applying Proposition to IC yields
K(xxx0) = Σ (ss, (z'),
(29)
where {Sk] is a sequence of all subsets Sk E (1...., d) with 7(s)) S q. ordered such that As As Next, let E N be such that nds... E Omax 1]), and define the index sets
I (k E k > m and S S T. + 1}.
I2 (k EN| S 2 2..
Those sets induce the following kernels:
(1(2,x))== = Σ As (x))sss
(1(x,x') = Σ V's. (x))'s,
kEZ1
kEZ1
(2(2) =
Σ
As \s.
S2(2,2')
Σ
X Vs. (z))',,
kEIa
kEIa
where S and S. are the squared kernels corresponding to K₁ and K2, respectively. The empirical kernel matrices K,, K2, S1, S2 E R=x= are
[Ki]i, = (1i,, xz), [Kajs = K2 xz),
[iijk =
and
[Saka = S2(1,, (3))
Furthermore, as in the original kernel decomposition, we define the matrices
V E R
| Wikk = Vss, (II), D = diag( Ask,
D ERAINAI
ASHIZi
where (ky /al sequence of all indices in I, ordered such that Ase. 2 As Intuitively, I Dj are the analogue to v Sm. Dem in the original decomposition K. = Kgm K=m.
Lastly, we define m as the largest eigenvalue corresponding an eigenfunction V's of degree [S] 2 L + 2, that is,
m min Iz.
Using the previous definitions, the following lemma establishes that K,, and Ic, indeed constitute decomposition of X- Lemma (1-2 decomposition). For sufficiently large, we have
Kym(x,x') (1(x,x')+ K2(axx') and Sym(x, =1)= S1
Proof. For the decomposition of K Kmmm we have to show that exactly the eigenfunctions with index larger than m appear in either K₁ or K2, that is, I U = {k > m). and that no eigenfunction write Sym (z, x')
appears in both Kr or K2, that is, In II D. Furthermore. since Σkzm X2, V's. Vs) (x') by Lemma 5, the same argument implies the 1-2 decomposition of S
First, from the definition of I₁ and Iz, it follows directly that I₃ n nI = 0. that I₁ UI, 2 {k > m)
and that I₁ C {k > m). Hence, to conclude the proof, we only need to show that Ig S (k m). Since the eigenvalues are sorted in decreasing order, we equivalently show that, for d sufficiently large, all eigenvalues Äs, with à Ia are smaller than As Omax (A, 1)/n).
26

---

Published as a conference paper at ICLR 2023
More precisely, show that maxkez, nλs, o(nism.) o(maxfA, 1)). Using T from Assump- tion 1, we have
max nss, = max
max keIz|SAk<1 <T
nAs
max
nds.
kEZz
k 1
=:M1
-:M²
For M1, we bound a generic k I2 with |Sk| ' as follows:
nAs=
(
5o dg(l+z))11 =0
(dLt(+t(LL0)
d-
dqlsul- -
d1+B(L+6)
(16)
= (max (2, 1 1)dd(L-L)) 1-10 2(1-6)) C o(ndm),
where (i) applies Equation (22) from Lemma 10, and (ii) uses L 2 and ō 1. In particular, this
implies M1 o(ndm).
For M2 we have
n
max nds. = max As keZg:|8. 127
E
O
18.12T
dq
(0)
(d d-1(1-6)
C 0
=0
dg (Q((++2)-
(1(+3(+0))
(14))
(maxx (, ( ((10)) C o(ndm))
where (i) applies Equation (23) from Lemma 10, (ii) uses that L+ < T, and (iti) follows from 2 L and
Combining the bounds Mj and M2, we have maxkez, nλs, o(n)s.,)) = o(max (A, 1)). Hence, for d sufficiently large, all E In yield As, < Asm. and consequently >> m.
[
Using the 1-2 decomposition, we now prove Lemma We defer the auxiliary Lemmas 12 to to Appendix C.4, and concentration-resulls Appendix C.5.
C.3 PROOF OF LEMMA 3
Throughout the proof, we assume d to be large enough such that all quantities are well-defined and all necessary lemmas apply. In particular, assume the conditions of Lemma 11 to be satisfied, and that e < [9/2] < < d/2 for in Assumption 1. Hence, 4+2 2 < L < T < [g/2], and we can apply Lemmas 9 to 15, the setting of Appendix C.2, well as Assumption throughout the proof. We will mention additional implicit lower bounds on d as they arise.
The proof proceeds in three steps: we first bound r1 and r2, then bound Tr(S>m). and finally E (S.mm) We do not establish the required matrix concentration results directly, but apply various auxiliary lemmas. All corresponding statements hold with either probability at least - ag- or at least - ōy (1-8) for context-dependent constants We hence implicitly choose a c > such that collecting all enror probabilities yields the statement of Lemma 3 with probability at least 1 cd min (8,1
To start, m E N as in the statement of Lemma 3, and instantiate Appendix C.2 with that m. In particular, Lemma 11 yields the 1-2 decomposition K=m K₁ K2 and S>m S Sg, which we will henceforth use. Finally, we define
oltaa) (x,z')
Σ
a+1 1+1 (
dB(l. y (s(2)))s(1))
(30)
7S)S |5|-1
with the corresponding kernel matrix (d.4)) E R
27

---

Published as a conference paper at ICLR 2023
Bound on 71 and
Remember the definition of rı and rg:
11 Mmin (Km +
| +
72 max X, 1]
max max(X.1 {X,1}
To bound those quantities, we have to bound Mmin ||>lllll II. use the triangle inequality >Kmm individually.
(K (K>m) and K >ylll-- For the upper bound on K2ll- and then bound [ and [[2]
K
Note that we can write K D I by definition. Hence,
(i) S 1.5m |Dll I 1.5nmm E
(it)
K = V. L = n D2
O (max (A, 11),
where (i) follows from Lemma 12 with probability at least 1 Ō2 (ii) uses that all eigenvalues of 1 are at most Am by definition, and (iii) follows from n.m. E O (mmx ( X, 1}).
Next, Lemma 13 directly yields with probability at least 1 č24 (1-8) that ||2| O(1) and Mmin (K2) E (1)). Hence, with probability least - (ō14 á + E2q (1-8)) we have
cq (5,1
Ki ll. K2ll E (max (A, 1}),
Punn (K2) E (())..
This implies
K y + E Ki|| + |2| + ( { X, 1)),
Pmin (K>m)= + X 2 M'in (K2) + À Mmmax 1}),
and subsequently
|| || +
r2 max ( 1}
E EO(1),
T1 Pmin (K>m) +
E 2(1).
maxxX, 1}
Finally, since 1ı S T2, this yields 71. E (().
Bound on Tr We need to show that
Tr(S>m) S ddag d
(31)
with high probability, where the two terms correspond
the 1-2 decomposition Tr(S>m.
Tr(Si) + Tr(S2). We differentiate between i. T. and T. T.> L.. Intuitively, the case - T. corre- sponds to interpolation or weak regularization, because the maximum degree of Icarnalle polynomials with regularization equals the one without regularization. Conversely, L > L corresponds to strong regularization.
Case L = L (interpolation or weak regularization): In this setting,
L l-
{ 2-1-L-4
4
(32)
3
3
3
First, Lemma 14 yields Tr(S2) E E (0 (1-5) with probability at least 1 - 2z3 223-- (1-5), Therefore,
Tr(S2) (1-51) (0) O(g (1 = -d(d'r0-10
where (i) follows from Equation (32).
We now consider Tr(S,):
T V
V L
Tr(S,) nTr
D
<
Tr(Di) S 1.5m
23.
kEI
28

---

Published as a conference paper at ICLR 2023
where (1) follows from Lemma 12 with probability at least 1 .-q-
The bound continues as
Tr(Si) S
n [1|
REI,
(1)
max ( X 112 |Z1l
E
O
(181) des
dyt
= -det (40)
C O
d
where (i) uses 0 S Am for all E Ii by definition, (it) uses ndm E *(max (d, 13), and (iv)
follows from Equation (32). Furthermore, (fii) uses the following bound of [Za]:
2 Σ c(I.q, d) _
L+1
Σ
L+1
9 (1=)) (1))
S Σ
(+E)))
L+1
1-1 ((0) Old- qt),
where q(1,g,d) d) is defined in Equation (17), (i) follows from Lemma 9, (ii) is classical bound
on the binomial coefficient, and (iit) follows from the fact that the term corresponding to L + 1 dominates the polynomial.
Finally, collecting the upper bounds on Tr(S1) and Tr(S2) yields
Tr(S2m) = Tr(Si) + Tr(S2) E O dd + dd
with probability at least (c39 (1-8) ē,9 $)
cq min(8,1-3)
Case L > L (strong regularization):: this setting, the dominating rate will arise from Tr(S;). We start by linking ō and in analogy Equation (32):
lx L -
lx -
lx L -
+ L.
(33)
B
3
B
3
Next, as in the previous case, Lemma 14 yields Tr(S2) E 1 ōeq (1-6), and therefore
with probability at least
Tr(S2) E Oly (1 -- + ( (d (1t)
5
where (1) follows from Equation (33), and (di) from L >>> L.
To bound Tr(Si), we start as in the previous case:
V
V
(1) Tr(D;)
Tr(Si) = nTr
D?
< n
S 1.5n
Σ
KEI,
where (1) follows from Lemma 12 with probability at least over all squared eigenvalues with index in Iı
-à1q
8. We then decompose the sum
72
X
= n
Σ
X5 +n n
Σ
X
+n
Σ
KET
RET
KET
RET
S
|S+|=L+2
2
E
E
Eg
and bound the three terms individually.
First, we upper- Ej as follows:
(1)
22 S
E = n Σ
Σ 1
AS
n
KEI,
KEZ,
18
n X2
L+1
(1) E 0
mmaxfA X, 1
m
C(I.g.)) d)
da
n
1=0
dha
0
d d' g.: d't 2
=0 (d"ag-o)
29

---

Published as a conference paper at ICLR 2023
where (i) follows from X I Am for all k > m due to the decreasing order of eigenvalues. Step (it) applies n'm E (maa(A,, 1)), as well as E/=o C(I, q(I,q,d) O(d q²), which follows as in the other case from Lemma 9 and the classical bound on the binomial coefficient.
Second, the upper bound of Eg arises as follows:
q 9+1- 2
E2 = n
Σ
Σ
Sk
dB(T. +,
KET
REZI
|
L+2
|SL 1+1
(86)
9
n
Σ
q 9+ 1 - ((S)
SL+2
dB +
dB(L +2
|S|=L+2
(163
n.g
9 -+1 -+1-7(S)
d g
dB(L 2,9)
|8|=1.22
(te)
n- (d.4g) L+2 (xr x)
d 22
(w) E O
d d'agltb
0 (
d-
where (i) follows from Proposition 1, and (it) uses q + 1 - (Sk) S q. Next, (tii) uses that Equations (18) and (21) in Assumption 1 imply S142 ((1), and applies the bound B(L + 2,4) (2422 & (eq/(L + 2)2++2 Step (iv) uses {s(x))(s(z) = 1 for all and x E {_1, together with the definition of (/4 Lastly, (v) applies Lemma 15 and n E O(d') = Od d
Third, we upper-bound Ez:
Es = n
Σ
2 Sn
max
As
As Sn n
max (Asc).
1EI,
(5I1,151|2244 L+3
RET
KET 15,/24+3
L++
The last step follows from
T+1 Σ
Asa
S
Σ As
KEII
I= (S)
18,22++3
|||=]
L+1
(a) 9 + 1- (S)
dB(1.g)
1= 75)
|8|=1
18
L+1
Σ
(4)
Σ
9+1 7(S)
Vs
dB(1,g) 4)
1=L+3
وو
L+1
(tv)
(188)
(a)
1,
I=L+3
where (i) follows from Proposition 1, (ti) uses Vs(x) = 1 for all S and x {-1, (Mi) applies the definition of O (d4))) and Lemma 15, and (iv) follows from Equations (18) and (21) in Assumption since T, T.
For 1186, (As,). ), we bound each element individually:
As,
( E
(
0
1
C c
1
dgl
dg(1++3)-1)
30

---

Published as a conference paper at ICLR 2023
where (i) uses Equation (22) in Lemma 10 since & S L + 1 T definition of I1. Hence, obtain the following bound on Eg:
=0 =0 -0 (d.diigh+0)
Es S nh
max
(As.) E
dgltt
n
dglht
00 00 (0(
Finally, we can bound Tr(S))
Tr(S1) _ 1.5n
E1 + E2 + E3 E dddag--1--))
KET
which yields
Tr(S2m) Tr(Si) Tr(S2) E O (d 00 - (2-)-
as desired with probability at least 1 - (ट34 (1-8) + E2q 6) 2 1- cq min (8, 6,1-8).
Bound on Ei=1+m (S As before, we differentiate between no/weak and strong regulariza- tion, that is, between L and L> L:
Case L = L (interpolation weak regularization): In this case, we start by directly bounding
n Σ
Σ
(m)))
[s(S] + S2)
Σ (S2)
i=1+m
i=1+m
m Σ (s(22) Σ (i((2) Tr(S2) - -mmmmmmmp S2|
n1
(34)
i=1
(8)
(1-8)
m
11
Lg
Ω
d
(1 8)
m
dgL+11
where (1) bounds each of the first m eigenvalues of S2 with the largest one, (ii) follows from
Lemma 14 with probability at least - čअq č3g (1-5)_ and (iii) from Equation (32) since L = L.
m To conclude the lower bound, it suffices to show that dg E o(d -1(1-))):
(
nd
q ddgg
(1t)
(20) S o (1--6))
L+1
m (dgg+t1
de> de*dgh+1
and (ii) from Equation (32). For (iii), note that ő for sufficiently large yields vacuous result. We hence assume without loss of generality that 5 > 0, which justifies the step. This concludes the proof for the current case with probability at least 1 1-2ag- (1-8) 2 1 - oq 18).
where (i) follows from m E
12g max
Case L > L (strong regularization): In this case, define the additional index set
Is = (k E Ii |S = L 2}
with S3, L, D3 analogously to S.. V D2 in Appendix C.2, but using Ig instead of In Since I3 C IT it follows that & V. is submatrix of V and thus
L
V T
V
I Izal
is a submatrix of
I 1z
This particularly implies
V
V
V v
(4) [|z,1
Iz,
<
S
1/2,
(35)
where (i) follows from Lemma 12 with probability at least -5
31

---

Published as a conference paper at ICLR 2023
We now move focus back to the lower bound of
D (m())
(
(8)
(111)
Σ (s(S)m) 1=++m
Σ
(s((S)
Σ (Sa)
Tr(Ss) - m Sslls
(36)
= 1=1+m
1=++
where (i) follows from the 1-2 decomposition Syn S + S2 (ii) from the fact that I3 S I1
and (iit) analogously to Equation (34). Similar to the previous case, we conclude the proof by first showing that Tr(Ss) Q (d"*q- (d"*q-(1-a)) (1=1)). and then m||SB] E o(Tr(S))).
For the lower bound of Tr(Ss), we start with
Tr(S3) nTr
1 3
2 nTr (D²) Mmin
(2)
0.5n
X
kEIs
q (+11-(5)) dBIL +
(4)
n(C2+2)
1S|=L+2 (S)
where (i) follows with high probability from Equation (35). Step (ii) applies Proposition 1, and the fact that I3 = {k E N
| = L 2 and 7(S) S 4) for d sufficiently large. To show this, we use
c
dea
Am E θ
-
ddd'gghtt
dgg+88
Since the eigenvalues are in decreasing order and L + < L + 1 in the current case, we only need to show that Äs Am for all S fl......d
d} with |S| = L + 2 and 7(5) S q:
(1) As E O dg
ddgh+ (
o()m),
where (t) applies Equation (22) in Lemma since L+2 < T. Thus, As < Am for all S C (1,...,d) d}
with |S| = L + 2 and 7S) if d is sufficiently large, which additionally assume from now on.
The lower bound of Tr(Sa) continues as follows:
9+1-7(() 2
Tr(Ss) 2 n(((())
Σ
dB(L 2,9)
L+
SS)
(q+ 1+11-((5) 2
n(Elo)
n(5L+2) )
Σ
(B(L+2,0)
18|=L-2
755)
(m)
n1 9/2
14/2| + +1- (SS)
(5L+2)
dB + 2,9)
dB(L + 2,9)
1S|=L+2
(SS)((1/2
(iw)
n n-9/2
Lg/2| + -1
Σ 1 7(8)_1//3]
(SL+2) dB(L + 2,9)
dB 2, 1//21
where (iii follows from [g/2] and 1- 9/2. Step (iv) follows from the fact that B(L + 2.9) g) and B(L + 2, Lg/2 /2) are of the same order; this follows from a classical bound on the binomial coefficient:
[T. 2,4) S
eq
L+2
$
Lg/2l
4+2
S B(L + Lg/2])-
L
++2 2
L+2
32

---

Published as a conference paper at ICLR 2023
We conclude the lower bound on Tr(Ss) follows:
n 9/2
[g/2] + +1-1(())
Tr(Ss) Z (L++2)
(E(
(B(++2,0)
dB(L + 2, [g/21)
1S|=L+2
(4)
9/2 dB L + 2.9)
(d.19/21) (1,
(LL+2)
L+2
9/2
(1)
2
dB(L + 2.
(vit) E
Ω
dB(L 2,9)
(witt)
( d d
L+5 q ) = 10
(37)
qq
where (v) uses (zs()))s(z))= for all S and x {-1,1]á with the definition of (d.1g/21) in Equation (30), (vi) applies Lemma 15 with [g/2] as filter size, (vii) follows from Equation (18) in Assumption I, and (witt) uses the classical bound on the binomial coefficient.
L++2
Finally, for the upper bound on ml S3/l we have
L
(
m S||l
ml
M DI
S mm D3ll
1.5mm
D3ll
mn max X kE
(#)
mn max kEIa
(9) 9 9+1
SL+2 dB + 22
m
(5 L+2
)2
dB + 2,
12
(188)
O
m
dd g 1. 9
2
(tv)
0
8 8
Es
(digq-(1- 2
dy 1:42
(vi) S o(Tr(S)))
O (q-ba-11-- (ding- (0-01100) (1-6))
S o (d (1-6)
where (i) follows with high probability from Equation (35), and (ii) from Proposition 1. Step (Md
uses that Equations (18) and (21) in Assumption yicld e(g) E O(),, and B + 2, q) (1422 t2)) Furthermore, (iv) follows from m E O
ny (A.1] ) (v) from -- (1-6) E o(1), and
(vi) from the lower bound on Tr(Ss) in Equation (37).
Finally, combining this result with Equations (36) and (37), we have
12
(4(52m) 2 Tr(S:) m m||SB]l ((Tr(S))) C a ( (a-)) -1-6)
1-9900
with probability at least - ônq 2 1 cq min
C.4 TECHNICAL LEMMAS
We use the following technical lemmas in the proof of Lemma 3. All results assume the setting of Appendix C.2, particularly kernel as Theorem that satisfies Assumption
Lemma 12 (Bound on K,). In the setting of Appendix C.2. for d/2 q 2 L + 1. we have
V
1/2
with probability at least cq uniformly over all choices of m and X.
Proof. The proof follows a very similar argument to Lemma with minor modifications. First, define
i = (k N |Sa < T.+1) 13.
33

---

Published as a conference paper at ICLR 2023
Note that In does not depend or X, and I1 S In for any m. Furthermore,
121-
L+1 - -1--Ecu cl1.
L-
Σ d
(
(1) 1 Σ
L+1
c(q 1)
(ai)
O(d-9")
1-1
1=0
where (i) follows from Lemma (ii) classical bound on the binomial coefficient, and (iii) follows from the fact that the largest degree monomial dominates the others.
Next, define L 12x with 11,, Ss,,, (24) where ky is the j-th element in 2, Using the arguments as in the proof of Lemma 1, it follows that the rows of T independent, that their norm is bounded by [Z and that they have an expected outer product equal 1
Hence, in the proof of Lemma can apply Theorem 5.44 from Vershynin (2012). Choosing
t 2
yields
2,
$
1/2
71
with probability at least 1 - -g- for some absolute constant c.
Finally, since In C Σ for all choices of and m,
1
4
I 7x
S
I [11
$ 1/2
with probability at least - cq uniformly over all À and m.
Lemma 13 (Bound on K2). In the setting of Appendix C.2, if < Lg/2] < < for c as in
Assumption 1, we have
Ca S Mmin (K2) K2 02
for some positive constants 61,02 with probability at least čg (1-3),
Proof. First, the condition on d implies > T and ensures that we can apply Lemmas 16 and 17, and Assumption Furthermore, note that
+
Proposition I and the definition of K2 yield the following decomposition:
q 9+1 -+1- )s(())'((+'== = Σ o (x,x²), (e,)))
(2(xxx²)= = Σ I=
dB((,
SS) S|=!
t=L+2
where Q(d.0) (x. x²) is defined in Equation (30). Then, using the triangle inequality with non-negativity of the ( from Equations (18) and (19) in Assumption 1, have
T-1
K2
Σ
Q
(d.q)
Σ
Q
(d.g)
5
Q
(d.q)
1=
1=
T-1
(
(d.4)
Σ
99)
d.g)
+
I=L-2
1=T
T-1
(8) 5
1.5
Σ
+
03
C2
-aa- with probability 2 1 - -a--tt (1--)
I=L+2
Q (d-9) is the kernel matrix corresponding to e (d.)) (z. I²), (i) uses Lemmas 16 and 17, and (ii) uses non-negativity and additionally Equation (21) in Assumption 1.
34

---

Published as a conference paper at ICLR 2023
The lower bound follows similarly from
Muuin (2₂)
Punin (Q/air)
cl0) 22+2
2 21122 c1
1 clg) (18)
L
where (i) follows from Lemma 16 with probability at least 1 oq (1-6), and (ii) from Equation (18) Assumption
Since Lemma 16 yields both the upper and lower bound for all uniformly with probability 1 cg eg- (1-6), this concludes the proof.
L
Lemma 14 (Bound on Tr(S2)). In the setting of Appendix C.2, if < |g/2| <9 < d/2 c as in
Assumption 1, we have with probability at least 1 -ēg (1-8) that
Tr(Sa) (11-(11))) and ||S E E ( dgght> (
where S2 defined in Appendix C.2.
Proof. Throughout the proof, the conditions on d and hence E O(d ensure that we can apply Assumption and Lemma 16, as well as < < Lg/2].
First, Lemma 13 yields |2l| E ((1) with probability at least 1 - p' (1-5), which we will use throughout the proof. Next, we bound ||S||| in two steps. For this, remember that An is the largest eigenvalue corresponding to an eigenfunction Y/ of degree |S] 2 +
Proof that || < Am K2ll Define L E Ruxa with p = Vs. (a.))sss for all i e (L.... n). k I2, and be any vector in R Then,
|2ul|| (
X
max Av
Σ
kEIz
KEIa
(ii)
Am
Σ d
KEIZ
Am
K20/l.
where (i) follows from the definition of S2 and (ii) from the definition of m.
Proof that Am E e
We show that A E O dg for all is E Iz, and that there exists
d
mn E In with Ay E Ω
Since Am maxteI, Àse. those two facts imply Am E θ dob
Let Ta be arbitrary. Lemma 10 yields
Sel < T S&l 2
dg
d
A E
dg
C
0
dg
where (i) follows from [Sa] 2 L and > L
Now we show that there exists in with Am 5 dy
We choose in with S... (1,2, .., .,,...,,2,)
Note that L 2 = y(Sm)) 1 q and thus m E Iz. Next, Proposition yields
Asa = T dB + 2,
(44 (q + - (S
E θ
1
ce
1
dgh+22
dgg+t1
35

---

Published as a conference paper at ICLR 2023
where (i) follows from Equations (18) and (21) in Assumption 1.
Finally, combining the previous two results and |gg] || E @ we have
| S Am K2|l O (Am) O dgg+1
1
Upper bound of Tr(S2)
The upper bound also follows directly from the last two results:
( n Tr(S2) S n| S2ll E e
(dghtt) (अ O
dg
00g-01100
dg
Lower bound of Tr(S2)
The lower bound requires a more refined argument.
S2(x,x')=
Σ
Σ (=)ss()))s(²²)
kEIz
SS) 1S|=L+2
{+)ss)))s((t')
|8| 1.42
0 (5( )2
Σ
(1 (1+1- (=(())ss(t)
1.42
2,
7
1
(1)
L+2
Σ
(q 1 - ((5)) 9+1 7(5)
dB(L+ + 2, Y's (z(x)))s(a))
dB( L + 2,0)
([5)
|
/2/22 (2/2)))9/12 L+2
(8)
Lq/2] 1+ ((())))ss)(
Σ
dB(L + 2
dB L + 2.9)
7(S)_19/21 LS|=L+2
where (i) follows from Proposition 1. In (ii). we use that, as long as 7(5) S 19/2], we have q (1) 2 2 and q 2 1g/2]. Continuing the bound, we have
(5 92//2
(4)
14/2|+1-~(5 ys (x(2)(/(zz)
Sx(I,x') 2 dB L + 2,9)
dB(L+2,9))
7/5)51//21 1S|=L+2
(51+2)
[g/2] + - 1(5)
d7 dB L 22
Σ
)s (s(z)))s(())
dB(L + 2, [9/2])
7(8)5 g/2l
|s|=L+2
(5(9) (5 24/2 (d.14) (2)
(in)
dB 2,
L+2
In (Zi1), we use the classical bound on the binomial coefficient (f,42)= = =BLL + 2, follows:
(
q/2 (
L+2
Lg/2] L+2
B(L 22.9) S (22)
S {(2)Lt+2g
= + 22, =c,
T
where cz is constant that depends only on L. Finally, (iv) follows from the definition of Q (d.1g/2 in Equation (30).
L
The bound on S2 x') implies
(5(0) (57.t2) 99/2
Jmin (Sz) 2 c/
Panin (Q(4. (d.19/21)
dB L + 2, ②)
f.42
36

---

Published as a conference paper at ICLR 2023
and allows to ultimately lower-bound Tr(S2) as follows:
(g) L+22 ( 9//2
Tr(S2) 2 Milmmin (S2) 2 e
dB T. + 2, 1)
Mmin
L+2
(6)
15..t2 2 9
(9)
2 c dB(L (L 22
(8)
2 d 9 dg L+
dgLti = q (2-6)
dq
where (i) follows from the lower bound on Mmin (o (2221))))) in Lemma 16 with probability at
least - c" Lg/2] (1-3) 2 d"q (1-8), and (ii) follows from Equation (18) in Assumption
and the classical lower bound on the binomial coefficient. This yields the desired lower bound Tr(S2) E (0gg-(111))
Finally, collecting all error probabilities concludes the proof.
Lemma 15 (Diagonal elements of Q(d.a)). Let 1 q. E N with 0 < d/2 and (-1,1] Then,
o (d.g)) (I, =1
Proof. First,
q 9+1 9+1 (SS)
(I,x)=
Σ
Vs(())²
dB(1,q)
SS) s|
(
Σ
q 9+1-
dB(L.) 9)
7())
|8|=1
Σ
(q (9+1-1) 7)
Σ
dB(1,g) g)
7-1
1()=
|
where (1) follows from the fact that (>(2)) = 1.
Note that Σ 25) s
matches the definition of Č(I, 7, d) in the proof of Lemma 9. Next, the
following recurrence:
4 Σ 7=1
(u+1-7)0(1 7,
(c()),)++(0 ((-1)+++++))))+))+())))))
9-1
C(l, 1. d) +0+ Σ
- 1) (1--1)+1-))((+
7m1
where the last step uses the fact that C(1, g, d) = ES C(1, 7, d) by definition, and that the term corresponding to q in the second sum is zero. Recursively applying this formula / times yields
Σ 7(1 c,,
7=!
Using this identity, we finally get
(d.a) (id (z,z) dB(L,g) Σ C(L.
q
(40)
d
1.
dB(L 9)
dB(L. q)
7=1
where (i) follows from Lemma 9, (it) from the hockey-stick identity, and (iti) from the definition of
B(1, q) in Equation (15).
37

---

Published as a conference paper at ICLR 2023
C.5 RANDOM MATRIX THEORY LEMMAS
We use the following lemmas related to random matrix theory in the proof of Lemma 3. The first two results bound the kernel's intermediate and late eigenvalues.
Lemma 16 (Bound on the kernel's intermediate tail), In the setting of Appendix C.2, for T 1 q < d/2, with probability at least - oq (1-8), all I N with L + 2 < < T satisfy
|
(d.9) I, - 2'
where T is defined in Assumption 1 and Q in Equation (30).
This lemma particularly implies |Q] (4.4)) || S 1.5 and Mmin
(Q((e))) 2 1/2 for all L+2
with high probability.
Lemma 17 (Bound the kernel's ' late tail), In the setting of Appendix C.2, ife S Lg/2 - -l< d/2, for e and as Assumption we have
4
(d.g)
21
with probability at least 1 od-1
Proof of Lemma 16. First, Lemma 15 yields that the diagonal elements of Q,d.0) are just 1. Hence,
we define wr(d.)) == Q (d.a) I,, and want to show that, with high probability, ||w["d) (d.1) || S 1/2 for all L 2 < l < T at the same time.
The proof makes use of Lemma 18. Therefore, we need to find an appropriate ((1aa) for each considered I, and show that the conditions of the lemma hold.
The first condition follows directly from the construction of w(dd.) and diag
(Q, (d.)) = I,,-
To establish the second condition, have for all + j. #
Bx, [w/de)) ko [.[ (d.2) 15.8
Σ
Σ
(dB(l,
=|
|/
(q+1 (
(dB(L.g))
rS)) |8|=1
(9+1-7(8)))4 (0+1->()))s::))))(((
dB(1, a) dB(l.g)
SS) -
-(BBll.9 dB 9)
w
-1 dBB(I 9)
[w(dwe)
1.
lq
where (i) follows from orthogonality of the cigenfunctions. Hence,
((aa) -dB(l, 9)14
satisfies the second condition in Lemma 18 for all T.+2 < T.
38

---

Published as a conference paper at ICLR 2023
The extra factor is necessary for the third condition to hold. As in Lemma 18, let Then, for all i + j,
N.p 2 2.
E |
d.)) 1i (r)
I (p
(p-1) V B
E
| [w/dd))p
[in
pl
(0+1~1(5))
(dB(1.9))
7(S) |S|=1
(186) Vo (dB(1.)) ())...)) c(1 (U..0)))
lg dB g)
qC(L, q. d. IdB(L. q)
(in)
d
pl
M
where (i) follows from hypercontractivity in Lemma 19, (ii) from orthogonality of the cigenfunctions,
and (iti) from the definition of C(I, q, d) as well as 1 S (S) S q. Step (iv) follows from Lemma 9,
the definition of B(1, q) in Equation (15), (1=1) (9). and the definition of M0..)
Since all conditions are satisfied, Lemma 18 yields for all p E E, 2
Pr [I (1 1/2) Gippon
M
P + t.22 (ll.))
2
++++ where 01,,, 012 are positive constants that depend on 1. In particular, if 2+ + 1-8
then we get
Pr [ (d.)) > 1/2) S 4q 2(1-))
where e is positive constant that depends on L. To avoid this dependence, can take the union bound over all I = L + 2......... T
Pr (I (L+ .., T 13: ||
(w/d0)) (d.a)
1/2) S -(1-5) 8)
Σ a 6 2(1-b),
I=L+2
where of only depends on L and T, which are fixed in our setting. Finally, additionally note that neither L nor T depend on lx-
Proof of Lemma 17. First, Lemma 15 yields that the diagonal elements of Q (d.9) (,40)) are just for all
I E Hence, we define w(l.g) = Qf (d.9) In. and decompose the kernel matrix
(d.))
1=T
We can hence apply the triangle inequality to bound the norm as follows:
g
q
9
Q
(d.9)
(dg))
+
(d.a)
n
g
(4)
W
12
itj
(182)
n22
max
(d.))
d
1=1
(60)
+ d 11 with probability 2 1 - cd-1
where (i) uses non non-negativity of the 5 from Equations (18) and (19) in Assumption 1, (ti) bounds the operator norm with the Frobenius norm, and (iii) additionally bounds the sum of the g(9) using
39

---

Published as a conference paper at ICLR 2023
Equation (21) in Assumption 1. Step (iv) use bound that we show in the remainder of the proof: with probability at least cd we have wi S d//q uniformly over all E {T.... 9).
We first bound wi for fixed T s S q as follows:
Pr(wi > 1/9) Pr
())0)
n²
max
(
1 (dd)) > 1/9)
143
Pr
max
if]
W/ w
Rig
n2(g(())22
1
Pr
3i # j: [W,
j:
1s
n² n²(((5)) )20p))
1
(1)
S nnnn- Pr
[ [w
P2.2
n² (=(
(1)
[wo[despp.
n²(4))))222
(00)
(a 1 - - 1 1-111---000 (D) (11)))))))
(dB(1,9))²
(S)))()))
85.5"
|51,151
n²(5(0))
11 xSS)²²
(dB(L, q))²
|s|=t
(wv)
(q 1)) (5/ (c()))2g
(g+1 7(S)) )2(211)²
dB(1,q)
dB(1,q)
Sq |8|=1
n=(5( gf (11, dB(1.q)
(v) n 3 (5) (1))
d B((,9))
where (i) follows from the union bound and the distribution of the off-diagonal entries in (d.g)) and (ii) from the Markov inequality. In step (iii), we use orthogonality of the eigenfunctions, as well as the fact that w/(d.)) and Q (d.a) coincide on off-diagonal entries by construction. Step (iv) follows from (x))
for all S and x E {-1, 13d, Finally, step (v) applies Lemma 15.
Next, we use the union bound over all x of interest:
Pr E (T...... g): का > 1/9) S Σ
Pr > 1/4)
1-7
(1)
q
B(l,g)
1=T
1//2|
((())) 2
g
(G) 0)
n qa
Σ
Σ
Σ
d
1= / +1
1=--4++ T +1
14/21
[4/2]
(5(0) j2
T-1
(5 )2
d
(1)x)
[a/2] ( y2 + (5(9) )
T- (e(a) )2
(84)
n
-1-)
E2
where (i) substitutes 1' = 9 1, and (il) uses q - [q/2] 1 S [q/2] as well as the fact that
9,) (g). We bound both Fg and Fg using Assumption 1.
40

---

Published as a conference paper at ICLR 2023
For Ej in particular, Equations (18), (19) and (21) imply that all g/0)
X 1. Hence,
1q/2] (2 (6,2))
Tq/21
(
[q/2]
[//2]
(4)
T
1
E = 7- (
q"
q²-1
1=T
where (i) exploits that 7' is the value in (T...., [q/2]] the furthest away from q/2, and thus
(
9 )
min LE 1E(T....19/21)
and (ii) follows from the classical lower bound on the binomial coefficient.
For Eg, we have
M
(
(1)) Σ
9p-1441
2 +248 ST T 1
E2
g²
gT
q
qT-1'
K=0
P=0
where (1) uses the classical bound on the binomial coefficient, and (ii) Equation (20) in Assumption 1.
Combining the bounds on Ej and Eg finally yields
n'q² Pr 1090>119)//
Pr (31 E (T. .T.....0. a: a > 1/9) S
(E + E2)
d
dg dg S d
n1
(8) x d'
where (i) follows from the definition of T = [4 in Assumption 1.
The next statement non-asymptotic version of Proposition from Ghorbani al. (2021).
Lemma 18 (Graph argument). Let W E Rax* be random matrix that satisfies the following conditions:
1. [W], 0, Vi mn..
2. There exists M > 0 such that, for all i, {I,...,n) with + j and j + k, we have
1
[,,,,,
- M
3. There exists E M such that, for all p E N, p 2 2 and all i,j E [l.....,. nJ. i # j. we have
pl
E B[[ b. 1/ S
V.M* M
Then, for all p N.p
Pr ( > 1/2) s 2
11 (n)²+ + +g n
{
(
(
where ej and 02 are positive constants that depend on
Proof. Repeating the steps in the proof of Proposition 3 from Ghorbani et al. (2021), get
n++
+ cdd (.²)²
Pr E Tr(W?*)] < (cp)
MP
Note that the proof in Ghorbani al. (2021) assumes M to be in the order of d' We get rid of this assumption and keep M explicit. Furthermore, Ghorbani et al. (2021) use their Lemma 4 during their proof, but our Lemma 19 instead.
Ultimately, we apply the Markov inequality to get a high-probability bound: Pr
Pr[ W|| 1/2)
21) 2t
E
3
p
nP+1
)
n M
21
(1/2)3
MP
+
(1/2)2
Renaming the constants concludes the proof.
41

---

Published as a conference paper at ICLR 2023
Lemma 19 (Hypercontractivvtty) For all 1, E N and 2 2, we have
Ba,a'=e((-111) [10/4.00 (z, (x, PP 1/p S 10-1)12 ( (B. (x,,,)))
where Q( (sr, is defined in Equation (30).
Proof. Let x, x' u1}-1,1) and let 2 be the entry-wise product of x and Then, for all S S (1, d), (ss()))s(()) depends only on 2:
{s(x))'s(r)>
[ [ VES
II iEE
[1/),)
-
H ÉES
iE
Hence, Q,4-)) (1r, x') also only depends on æ and x' via z. Furthermore, note that 2 ~ U([-1, 1) 13d). Therefore, we can use hypercontractivity (Beckner, 1975) as for instance in Lemma 4 from Misi- akiewicz & Mei (2021) to conclude the proof.
D OPTIMAL REGULARIZATION AND TRAINING ERROR
D.1 OPTIMAL REGULARIZATION
In the main text we often refer the optimal regularization Aopt. defined as the minimizer of the risk Risk(fa). (fx) While we cannot calculate Appt directly, we only need the rate Exp such that max Aope 1} E θ (d" Furthermore, it is not priori clear that such Exp minimizes the rate exponent of the risk Theorem 1. The current subsection establishes that this is indeed the case, and provides a way to determine Ex
We introduce some shorthand notation for the rate exponents Theorem
(, -la lx
8
minf6, 8),
1
2
(o,xs T,,, ,8) == -2 =-2 Mexxe,t,, L", ,B) = max (n (exi l, la. 3), mo B),
{ (La 1 B(I," 1)),
We highlight that n7 and 1) depend on lx also through 8 6-4-1 of Theorem 1, we have with high probability that
e-
Hence, in the setting
B
Variance (Î^) 0(1tu((stPPo)))))
Bias (fA) E O(nm((atth1 10))
Risk (fx) O(n .8))
In the following, we view those quantities as functions of Ex, with all other parameters fixed. Next, we additionally define
Appi =
arg min
Risk(f
X (2.1)
E == arg min
e
Tmin
min TT(li e, lo Li, ,3, (.
i - 1- 3 1).
First, remark that mx... the set of regularization rates that minimize the risk rate might have cardinality larger than one. However, it cannot be empty: [0, ? a closed set, and Lemma 21 below shows that y) continuous function.
42

---

Published as a conference paper at ICLR 2023
Second, defines the scope of the minimization domain, guaranteeing that the constraint on L in Theorem holds for all candidate Lx-
Rate of optimal regularization Xxe vs. optimal rate Exa.s Let Exye be the rate of the optimal regu- larization strength such that max (Aope: 1] (dd is a priori not clear that Êxy, minimizes v). However, Lemma 20 bridges the two quantities, and guarantees with high probability that the rate of Aspt minimizes the rate of the risk.
Lemma 20 (Optimal regularization and optimal rate). In the setting of Theorem 1, assume > O, (0,1), 1), la -l, L [1,1 O Then, for d sufficiently large, with probability at least
1 - ed-0 min(8,11 there exists E Exm such that
max Doprs 1} @
Hence, we only need to obtain minimum rate I E Exais instead of Exp In order to propose method for this, we first establish properties of 1), Vb. The in the following lemma.
Lemma 21 (Properties of 1)). Assume & > O, 8 (0, 2- (1 NN.
1. Over [0, G. no no is continuous and non-increasing, and no l, B) is continuous and strictly increasing.
2. \ == arg c. m(xx C, lo, ,B, is closed interval.
3. there exists i E [0, f with no (T; lo, mo(0; I.",,"","", 33,, then Muii = nn[ L² 18) Otherwise, Quiin = n0 E, lu 33.
4. Every I E [0, with 1 2 ffrr all l Exw satisfies
El, L' L2, -,,0;;,,,,,
5. Let 1, 80 with 1 S 1 for all I. E Exm-- unllee, T,"BB) 7/min where > 0 is constant and depends only on f, Lo, L', 3,, then
2 TLL: E, la I,,,8) = Mmnin + (min (Exma)) - [)-
Finding an optimal rate: Lemma 21 suggests a simple strategy to find a E Exmi numerically: search the intersection of The and 7h in [0, E]: if found, then the intersection point is optimal, otherwise / is optimal. Note that, if the intersection point exists, it is unique and easy to numerically approximate, since T) is non-increasing, and т/ is strictly increasing.
Calculating numerical solutions: However, Lemma 21 also shows that ax... is an interval and thus might contain multiple values. In that case, the proposed strategy might not necessarily retrieve the rate of Appi but a different / E Exm.. Yet, Theorem guarantees that both the optimally regularized estimator and any estimator regularized with max (A, 1} E d' for any E & have a risk vanishing with the same rate Touia with high probability. In particular, this allows us exhibit the rate of the optimally regularized estimator in Figure la. Finally, because of the multiple descent phenomenon (see, for example, Figure 1), we do not expect either (xy, or 3 attain easily readable closed-form expression. Nevertheless, simple optimization procedures allow to calculate accurate numerical approximations.
Finally, we prove Lemmas 20 and 21.
Proof of Lemma 20. Let Exy, be such that
max Mopt 1) O (dthm))
'e omit explicit definition of here for brevity and refer the proof instead.
43

---

Published as a conference paper at ICLR 2023
Combining the bounds on bias and variance from Theorem we have
Risk (fa) = Bias (fx) + Variance
E θ 2- -- + -fa-fs- min(6.1-6))
E + (n
with probability 2 - od min(8.1-8)
(38)
uniformly for all lx [0. with max (A, 1] ((d"A).
Throughout the remainder this proof, we drop the dependencies on &, fo L", 3 the notation of 7 and simply write n((x). We further omit repeating that each step true with probability at least 1 od -d min but imply it throughout.
The goal of the proof is to show that there exists E txm. sufficiently close to eayx formally, we need show that
Y - (1).
(39)
If this is the case, then the definition of Exm yields the conclusion as follows:
max Mapss 1} E E (d = - (ddddww
( + (d).
where (i) uses Equation (39).
Towards an auxiliary result, we first apply Equation (38) to Exp and Exaia with max (,,1) 1} (dd")
Risk (fx) s ogn"(0) Rmia,
Risk 2 (FSmn) 2 (Ane))
where C1. C2 > 0 the constants hidden by the --notation in Equation (38). Next, the optimality of Aopt yields C1 < and
Cin Cy (eera S Risk2 (Jam)) S Risk (fi) S 62n Piiin
This implies
m(Exnr)) Muii log(c2/c1)
n (1 J Jmin
(40)
log
where the second implication uses that 7) v)((,.g)) Mmmn O. since Mmmi is the minimum rate.
With this result, we finally focus on establishing Equation (39) which yields the claim of this lemma.
Lemma 21 shows that Exm is interval; hence, we distinguish three cases:
Case Ex E Exaai Picking Expe = E Expa directly yields A -h = do E O(1)
Case exme < min (exmn): Let L min(exm. Equation (40) yields (T(()))) Quin S c for any e >> 0 d is large enough. Hence, for fixed but sufficiently large, Lemma 21 yields
(((aa))) Mmmin p
(L Exaa)
Applying Equation (40), we get
L (n (m(()ep)) Mmin) v elog(c2/c1)
Exue
2
2log
Now, since Exp I L. d' - E O(1). Furthermore.
dh < d
4 (lox(eg/s1) 2log
loxica/o) 2lnud
Ve2/c1 E EO)),
where (1) follows from n E (dd)). Since both dl-Baue Exy and wltmm = =d are in O()),
Annn EE((),
44

---

Published as a conference paper at ICLR 2023
which establishes Equation (39) for 7 E Exai and thereby concludes this case.
Case Expe > max (Exmn) Let 7 == max (. Then, Lemma 21 yields
2
n((rgg)) = -2 -2
(~bup - - B(L'" - -1))
2
-2
(-hhes -1+1 1+1-- -B(LL -1))
2 (-1 -1--1- - 11-BLL 1)) / (
2
-2
Mmin + ? (Caum -1), 1):
where (i) uses that 7 E lx Exma- Applying Equation (40), we get
Dup - -- l
elog(c2/c))
2 (m(())))) - 7min) 1
2 2log n
Analogously to the previous case, this implies d' -1 E O(),, and the fact that Ex. 7 implies de E Q(1). Together, this yields
(1),
which establishes Equation (39) for E Exm.. and thereby concludes this case.
Proof of Lemma 21. Throughout this proof, we drop the dependencies e, L", in the notation of q) ll. Th and simply write v7)), (1), (I).
Continuity and monotonicity (Item We first show that (1) and (1) are continuous functions. (7) is an affine function of 1, hence continuous. ne (T), however, additionally depends on / via 8, which is not linear. Hence, to show that n/ (1) is continuous, we need show that min 5) is continuous. Consider the triangle wave function
(t) = min(t [t], (t [+})},
which is well-known to be continuous. Because min - 8) = w ( and 1-1-1 1 is linear function of 1, we get that 7/ (I) is also continuous.
For monotonicity, we consider the derivatives of (I) and (o))). For (1), have
Oem (1) =
Since 77 is an affine function, and? > 0, this also implies that 77 is strictly increasing, For ye. we need distinguish two cases:
0
18-1-28
8 < 8
(m) =
1
to
8 8>
0 8 < 1 - 8,
2 8 > 1-6. 5.
Since Th is a continuous function with non posiiivie derivatives, this implies that 7) is non-increasing.
decomposition (Item 3) First assume that there exists E [0. with n.) = (i). Since n, is non-increasing and тp strictly increasing,
- (l) 1<
(!) == (n)
(mp()
(1) otherwise.
In particular, 77() > ( for all / >> i as nh is strictly increasing, and ni()) n()) for all I < since No non-increasing. Combined, this yields Mmnin E,, 1*
45

---

Published as a conference paper at ICLR 2023
Next, assume 2 does not exist, that is, m))() # (l) for all E [0. Then, due continuity, either (1)()) >> (1) for all I E [0, f). or (t) > (1) for all E [0, However, a closer analysis shows
that the latter is not possible: the rates the boundary i are
(e(()) = -2 8 (- 1- - -1) -1 3 - 1)) = 0, (1)
no lo + (e - 11)
8 { min 8) S 0,
where (i) follows from the assumption e, 2 - and the fact that min -3 2 0. Hence, if i does not exist, (1) < (1), 4I E [0, E. In particular, Mmin is the minimum of the strictly increasing function (T)) over [[0, f), and therefore attained only at O.
Lastly, combining both cases of yields the following convenient expression:
(1) exists and I (1())) otherwise.
(1)
(41)
Closed interval of solutions (Item 2) We again differentiate whether as in the previous step exists or not. If 7 does not exist, then the previous step already yields Exnin = {0], which is closed interval. Next, assume I exists. Then, all E Exm. satisfy I S I, since I Exmm and 17u is strictly increasing. Since further ?/v continuous and non-increasing over [o. 2 Exm.. Exan is an interval. Finally, n]({ = m (1), (1) the maximum of continuous functions, hence itself also continuous. Therefore, the minimizers Exm. of are a closed set. This concludes that Ex is closed interval.
Proof of Items 4 and 5 Item 4 follows straightforwardly from Equation (41): If does not exist, then n7(1) =l)(() for all I e E.. Similarly, if exists, r7(1) (l) for all / 2 [, in particular for 1 12 E
Item 5 requires additional considerations. the case where does not exist, we have bxm. = {0). and the result follows directly. Otherwise, using Equation (41), we have ry(1) = ()) for any 1 $ L. I. As shown in the proof of Item 1, (I) alternates between derivatives and -2/C. We claim that there exists a left neighborhood of min (fxm.) where the derivative is -2. Assume towards a contradiction that no such left neighborhood exists. Then, there must be left neighborhood of min (fxm.) where the derivative is O, since 77 (1) alternates between only two derivatives. However, in that left neighborhood, (2) constant with all values equal to Mmmin- Hence, there exists < min (Exm.) with (1) = (1) = Manin and thus 1 E tx... which is a contradiction.
as < (min(
Thus, there exists left neighborhood of min (6xm.) with diameter E O throughout which the derivative is - Then, for all E [min (fxmm)) - -, min (Exmn)).
2 - min (Exmn)).
no (1) Mmin
Finally, since (I) non-increasing, as long as no (!) S 7min + Ge we have ! min (Exaa) C. Hence, choosing = e yields the statement Item
D.2 PROOF OF THEOREM 2
The informal Theorem 2 in the main text relies on S*, defined as the intersection of the variance and bias rates from Theorem for the interpolator fo (setting la = 0). Whenever 3 is unique, the fact that Bias² (ff) in Theorem strictly increases as a function of 3 induces a phase transition: for 3 8", the bias dominates the rate of the risk in Theorem while for 3 < S*, the variance dominates. In particular, Lemmas 20 and 21 imply that interpolation is harmless whenever the bias dominates, and harmful if the variance dominates.
Intuitively, Theorem considers optimally regularized estimators, and varies the inductive bias strength via B. The formal Theorem below presents different perspective: it considers 33 fixed,
46

---

Published as a conference paper at ICLR 2023
and instead differentiates whether the optimal risk rate in Theorem 1 results from éx (harmful interpolation) or x (harmless interpolation).
Whenever 3 is well-defined and unique, for example in the setting of Figure 1, the two perspectives coincide. However, one can construct pathological edge cases where variance and bias rates intersect on an interval of /3 values, the dominating quantity of the risk rate in Theorem as a function of alternates between the variance and bias. While Theorem 2 fails to capture such settings, Theorem more general result.
still applies. We hence present Theorem
Theorem 4 (Formal version of Theorem 2). In the setting of Theorem I using the notation from Appendix D.I, let > 0, E (0, 1), Eo 2 -t, and L' E [1.
3 N.N Let further Aopt
arg min x20/max (A,1) (isk(fx). Then, the expected training envor behaves as follows:
1. Ifall I E arg ming v(1; l, E,, ,B) satisfy n(1; la, 1,) < n(0; (100;,,0 la, L3,)), then
E
(zi) - vi) -02 E Old 'Risk (frmn)) ( Σ
wip. 2 1-ed B (8.11
2. Ifall E (0, satisfy n](:; l, Lo, L', L2, 110; lo 1), then
Eg E (op)))))) - y1)² s 202 + o (Risk" (frp)) w.p. 2 1 -dd-cciin 10-
for some constant č < 1.
Intuitively, the two cases in Theorem 4 correspond to harmful and harmless interpolation, where the optimal rate in Theorem is for Ex > 0 and lx = O, respectively. Then, Lemma 20 yields with high probability that also Exp. remark that Theorem 4 lacks an edge case: if both some fx > 0 and ε 0 minimize the risk rate in Theorem simultaneously, Lemma 20 fails to differentiate whether εX zero or positive. However, that edge case corresponds to either interpolation or very weak regularization. Hence, we conjecture the corresponding model's 's training error behave similar the second case Theorem 4.
and Ex 0 in the first and second case, respectively. Finally,
Proof of Theorem 4. First, Lemma 20 yields with probability at least 1 - cd min( that max m 1} (dd',, where is a minimizer 17(1; e, L", 3). The condition in Item guarantees that all optimal are positive, while the condition in Item 2 ensures that the optimal I = 0.
Harmful interpolation setting (Item 1) In this case, 1 > 0, and thus Aopt E ((d') for d sufficiently large. We start by applying Theorem with lx = in this setting.
Within the proof of Theorem I in Section 5.2, we pick a E N such that for d sufficiently large, with probability at least 1 ed (8,18, m satisfies the conditions of Lemmas I to 4 and Theorem 3. For the remainder of this proof, let m the same as in the proof of Theorem for lx = L. This m satisfies the conditions of Lemma 23, which hence yields
2 Tr (H (H-2)- < E.
02
D all Sm
n (An (Z,) y1)2
Tr (H- + 612 r
n
upt
n
where H = K + AIn. Then, using that < b s + d implies 1b - cl S la cl + d. we further get
Ex
(nsn - 21)2
و² < 0
2
opt
Tr (H 2) -1
61 1
D all
(42)
opt
n2
=
47

---

Published as a conference paper at ICLR 2023
We first bound T2 follows:
D
al
d
r2
T2 612 opt
D
Sm
2
n
d
(0)
d
d q
2(1-11) -1)
2(
d
d
d (11-
d'd (2(1-111)
2 d 2
(8is) E 0 Bias (fxmm)) _
Risk (fxmp)
(43)
where (i) uses E O(d') and Aup E (dd),
(ii) applies Lemma 2 for the rate of |
Sm all and
Lemma 3 for r ri E (1), and (iii) matches the expression the rate of the bias Theorem 1.
For Tı, will bound Tr (H-2) from above and below using Lemma 22. We hence introduce the following notation:
K = K Kmn + K1, H2 = K2 + Aope-
so that H = H2 + K and where K₁ and K2 are defined in Appendix C.2. Furthermore, the rank of K_ is at most IN T2| = K E N [S&l < L + 2}}, that is, the number of eigenfunctions that contribute K 2. The rate of [N Ia is
④ Σ
L+1
L-1
9 (
(at) E O(d d'),
N
2
cl1, g.
where (i) uses the definition of C(1, q, d) in Equation (17), (ii) applies Lemma with sufficiently I-1
large, and (tii) uses the classical bound (0-) I e
well as the fact that the largest
monomial dominates the sum. Finally, since n E O(d g L+]), we have
rank(K_.) 2) S IN Iz E O(n 9) S o(n).
(44)
Therefore, for d and hence E (d')) sufficiently large, rank -2) n, and Lemma 13 yields
C1 S Pmin (H2) S |Hا|| S C2 for some constants C1. C2 with probability least 1 1- c'g (1--)
We can thus instantiate Lemma 22 with M = H. M, = K. M2 H2. This implies that:
n rank K
rank(K
Tr (H-2)² >
H2|
(C2 + )opa)2
The upper bound on Tr (H (H-2) simply follows from
Tr H 2) < H 211
n
Umin (Kem + K₁ + K2 + In
umin (K₂ )
(45)
(ci )apr)
where (1) uses the previous lower bound on Mmin (K2) from Lemma 13.
48

---

Published as a conference paper at ICLR 2023
Combining the upper and lower bounds on Tr (H 2) yields
rank(K 2)
( (H-
n
(02 + )app)
(c) + )opp)
nt rank(K
Aog
App
opt Tr (H
(C2 + )aps)
n
(c1 + Aap1)
rank((K2) 2)
Neu
Nop
+
upl
-1
Tr (H (H-2)-
- 2)
1
(02 + Appe)
(02 + )ops)
(ci + )opi)
rank (K 22)
App 202 c3
upt
201 Nape + of
Tr (H 2)
71
(02 + )²pi)
(c2 + )aaa)
n
(ci + )op1
Taking absolute values, a simple case distinction and 01 < C2 yields the following bound:
2 Tr 3H- -
202 + Aopt
Pank(K_2) 2)
2
(02 )oa))
(02 + Aop )
( d'
nq d2
d + - O(d
dal
d
n
where (i) uses the rate of rank(K-2) from Equation (44) and Appt θ (d') Combining this bound on Ti with the bound on T2 in Equation (43) and collecting all error probabilities concludes the current case.
Harmless interpolation setting (Item 2) In this setting, the only minimizer of the risk rate is = 0, and hence
Appe I max (Popt 1} E O(d)) = 0(1)
As for the previous case, let m be the same as in the proof of Theorem I for lx = O. With probability least 1 - ed B (i, 12--)) 8) this m again satisfies the conditions of Lemma 23, which yields
D Dihaal
E
Tr (H
61
opt 7
n
Furthermore, apply the same steps with 1 = 0 in the previous case (Equation (43)) to bound T2:
To E O Risk (Risk((fx.))) (fxm))
For T3. we use the same bound on Tr (H-2) in Equation (45) with the same probability as follows:
ope 0²
op 02
T3
Tr H 2) z
n
n
n
(c1 + Auga) 2
upi
(c + dope)
(
(d')2
(cr + c')
where (i) follows for d sufficiently large from App E O()) with c" > 0. Since (
> 0, we have (er terra < 1. Hence, combining the bounds on Tg and T3. as well as collecting all probabilities, we
get the desired result for this case.
D.3 TECHNICAL LEMMAS
Lemma 22 (Trace of the inverse). Let M, M1, M2 E R be symmetric positive semi-definite matrices with M M, + M2. Furthermore, assume that Puii (M2) > O and rank(M,) < Then,
Tr(M 2) n - --rank(M))
M
49

---

Published as a conference paper at ICLR 2023
Proof. First, apply the identity M = (M2 + M,)- = M -M2 MM -M2' + M.)
which holds since M2, and thus M, are full rank. Next, A is a product of matrices including M1; hence, the rank of A is bounded by rank(M1) < n. Let now {Vi,... Prank(A) be an orthonormal basis of col(A), and let (*rank(A) -1 Un. be orthonormal basis of col(A)". Thus, (ui,..., Un) is an orthonormal basis of R", and similarity invariance of the trace yields
rank(A)
Tr(M 3)
Σ
M
Σ
0 M +
E
RM- 02
1=1
irrak (A)+)(A))1
n
1 (M₂ 1-11-11 -A) Uz
(=rank(A)+1
rM 3/4 A -- M
Au
+o
(rank(A)--
=0
Σ
1. M2 -25
(=rank(A)+)
(8)
(n rran(()))))))) (ank(A)))mai (M2-) 3) (n rank(A)) 1
|Ma
(16) r
|2
where (1) uses that, for all > rank(A), v, is orthogonal to the column space of A, and is
symmetric. Furthermore, (it) uses that all v; have norm 1, and (iit) that rank(A) I rank(M1). 0
Lemma 23 (Fixed-design training error). In the setting of Theorem 3, let m E N such that >> 0, Equation (5) holds, and the ground truth satisfies f*)x) -Et (x(x(x)) Then,
X²02
1 ñ Σ (fa(x)) - vi)2 S Tr (T- + 6Λ
X²02
D all 2
Tr H
S E
n
n
ri
n
where H: = K + AIn-
Proof. The kernel ridge regression estimator is
fx(x") = y k(x"),
where y = [M....,, Vn. T with y, (xz) + es and k(x*) =
...., ((),,,"") Thus,
the estimator evaluated at Z1...., is KH y, which yields the following training error:
1 Σ (fa())) y1)² 1 -KH yl (0) X²
H 'yl?
where (1) follows from
I, KH-1-1. I, K(K + AI,)) I, (K + AI, AL,)(K + AIa) X(K + AL
Next, by the assumptions on the ground truth, we can write y c ama. Thus, the expected training error with respect to the noise is
1 Σ
2 Er [(E + v (
E,
(fa(zz)
2 v smma)
0z Tr (H
V H v
Sm
Sma
:
T2
50

---

Published as a conference paper at ICLR 2023
First, T3 O since H is positive semi-definite. Therefore, Ti already yields the desired lower bound on the expected training error. For the upper bound, we bound T2 as follows:
X²
T2
D Sm
a)
TD
Sm
T St
Sm
D Dmm
(D
Smaa
x
m
Smu)T a)T
D-11
Sm
+
T
Sm
m
mm
-1
VeT
Sm
H.
2m
V
Sm
D mm
+
Sm
H
Sm
mmma
H V Sm
D D
cm
+ T
H
1 Sm
D
Sm
1
H
L Sm
(D-1 Sm
T H
D-1
D Sm
n
Sm
20
Sm
1,5X
(mmin (Kum) 2)2 B1.
(646)
12 max 132
[ mm all
6\2²2 D | all
6x2
6x
(pmin (K (K3m) A)2
n²
11
n²
where Hym = K pm + Mhn Step (i) follows from Lemma 6, step (ii) uses Equation (5) and matches the term B1 from the proof of Theorem 3, and step (tit) applies the bound on BN achieved in Theorem This upper-bound bounds the expected training error and thereby concludes the proof. C
E EXPERIMENTAL DETAILS
This section describes our experimental setup and includes additional details. We provide the code to replicate all experiments and plots in
E. SETUP FOR FILTER SIZE EXPERIMENTS
The following describes the main filter size experiments presented in Section 4.1.
Network architecture We use special CNN architecture that amplifies the role of filter size as an inductive bias. Each model of the main filter size experiments in Figure 2 has the following architecture:
Convolutional layer with 128 filters of varying size and no padding
2. Global max pooling over the spatial feature dimensions
3. ReLU activation
4. Linear layer with 256 output features
5. ReLU activation
6. Linear layer with 1 output feature
All convolutional and linear layers use bias term. Since employ a single convolutional layer before global max pooling, the convolutional filter size directly determines the maximum size of an input patch that can influence the CNN's output. Note that this architecture reduces an MLP if the filter size equals the input image size.
Optimization procedure We use the same training procedure for all settings in Figure 2. Optimiza- tion minimizes the logistic loss for 300 epochs of mini-batch SGD with momentum 0.9 and batch size 100. We linearly increase the learning rate from 10-6 to peak value of 0.2 during the first 50
51

---

Published as a conference paper at ICLR 2023
32
00
32
32
32
o
0
8
32
32
0
32
0
32
(a) Negative samples
(b) Positive samples
Figure 4: Example synthetic images used in the filter size experiments.
epochs, and then reduce the learning rate according to an inverse square-root decay every 20 epochs. For peak learning rate No. a decay rate L, the inverse square-root decay schedule at epoch f 0 is
7
(46)
VI
[t/L]
Learning rate warm-up helps to capture the early-stopped test error more precisely. Whenever possible, deterministic training algorithms, so that our results are reproducible possible. We selected all hyperparameters to minimize the training loss of the strongest inductive bias (filter size noisy training data, with the constraint that all other settings still converge and interpolate. Note that we do not use data augmentation, dropout, or weight decay.
Evaluation We observed that all models achieved their minimum test error either at the beginning or very end of training. Hence, our experiments evaluate the test error every 2 epochs during the first 150 epochs, and every 10 epochs afterwards to save computation time. We use an oracle, that is, the true test error, to determine the optimal early stopping epoch in retrospective. The optimal early stopping training error always over the entire training set (including potential noise) for fixed model, not average optimization procedure, we average over multiple dataset and training seeds. More precisely, we sample 5 different pairs of training and test datasets. For each dataset, fit 15 randomly initialized models per filter size on the same dataset, and calculate average metrics. The plots then display the mean and standard error over the datasets.
mini- bati-b. To mitigate randomness in both the training data and
Dataset All filter size experiments synthetic images. For a fixed seed, the experiments generate 200 training and 100k test images, both having an equal amount of positive and negative classes. Given class, the sampling procedure iteratively scatters 10 shapes a black 32 x 32 image. A single shape is either a circle (negative class) or a cross (positive class), has a uniformly random size in [3, 5). and uniformly random center such that all shapes end up completely inside the target image. We use conceptual line width of 0.5 pixels, but discretize the shapes into a grid. See Figure for examples. A single dataset seed fully determines the training data, data, and all scattered shapes.
Noise model replacement, and flip their label. The noise is deterministic per dataset seed and does not change between different optimization runs. Note that we never apply noise to the test data.
the noisy case, we select 20% of all training samples uniformly at random without
E.2 SETUP FOR ROTATIONAL INVARIANCE EXPERIMENTS
The following describes the rotational invariance experiments presented in Section 4.2.
Dataset We the EuroSAT (Helber al., 2018) training split and subsample it into 7680 raw training and 10k raw test samples in stratified way. For fixed number of rotations k, we generate a training dataset follows:
52

---

Published as a conference paper at ICLR 2023
1. In the noisy case, select random 20% subset of all training samples without replacement; for each, change the label to one of the other 9 classes uniformly at random.
2. For the i-th training sample
fI....,6880)
(a) Determine random offset angle a:..
(b) Rotate the original image by each angle in {ar + j. (360%/k) |j = -0.=0..... O,..., 1}.
(c) Crop each of the k rotated 64 x 64 images 44 x 44 so that no network sees black borders from image interpolation.
3. Concatenate all & x 7680 samples into single training dataset.
4. Shuffle this final dataset (at the beginning of training and every epoch).
To generate the actual test dataset, apply random rotation to each raw test sample independently, and crop the rotated images to the same size as the training samples. This procedure rotates every image exactly once, and uses random angle offsets to avoid distribution shift effects from image interpolation. Note that all random rotations are independent training rotations. Hence, all experiments share the same test dataset. Furthermore, since we apply label noise before rotating images, all rotations of an image consistently share the same label.
the label noise and the number of
Network architecture All experiments use Wide Residual Network (Zagoruyko & Komodakis, 2016) with 16 layers, widen factor 6, and default PyTorch weight initialization. We chose the width and depth such that all networks are sufficiently overparameterized while still being manageable in terms of computational cost.
Optimization procedure We use the same training procedure for all settings in Figure 3. Optimiza- tion minimizes the softmax cross-entropy loss using mini-bater SGD with momentum 0.9 and batch size 128. Since the training set size grows in the number of rotations, all experiments fix the number of gradient updates to 144k. This corresponds to 200 epochs over dataset with 12 rotations. Similar to the filter size experiments, we linearly increase the learning rate from zero to a peak value of 0.15 during the first 4800 steps, and then reduce the learning rate according to inverse square-root decay (Equation (46)) every 960 steps. Whenever possible, we use deterministic training algorithms, so that our results are as reproducible as possible. We selected all hyperparameters to minimize the training loss of the strongest inductive bias (12 rotations) on noisy training data, with the constraint that all other settings still converge and interpolate. As for all experiments in this paper, we do not use additional data augmentation, dropout, or weight decay.
Evaluation Similar to the filter size experiments, we evaluate the test error more frequently during early training iterations: every 480 steps for the first 9600 steps, every 1920 steps afterwards. The experiments again use the actual test error to determine the best step for carly-stopping, and calculate the corresponding training error over the entire training dataset, including all rotations and potential noise. Due to the larger training set size and increased computational costs, we only sample a single training and test dataset, and report the mean and standard error of all metrics over five training seeds.
E.3 DIFFERENCE TO DOUBLE DESCENT
As mentioned in Section 4.1, our empirical observations resemble the double descent phenomenon. This subsection expands on the discussion and provides additional details about how this paper's phenomenon differs from double descent.
While all models all experiments interpolate the training data, we observe that both noisy labels and stronger inductive biases increase the final training loss of an interpolating model: Smaller filter size results in a decreasing number of model parameters. Enforcing invariance to more rotations requires model to interpolate more (correlated) training samples. Thus, in both cases, increasing inductive bias strength decreases a model's overparameterization in relation to the number of training samples- tisssssshiiiie shifting the setting closer to the interpolation threshold.
We argue that our choice of architecture and hyperparameter tuning ensures that no model in any experiment is close to the corresponding interpolation threshold. If that is the case, then double descent predicts that increasing the number of model parameters has a negligible effect on whether regularization benefits generalization, and does therefore not explain observations.
53

---

Published as a conference paper at ICLR 2023
0% noise, width:
128
256
512
0% noise:
WRN16-6
WRN16-12
> 1024
2048
20% naise, width:
128
256
- 512
20% noise:
WRN16-6
WRN16-12
O 1024
X 2048
x10
x x10
2.4
training loss
training loss
1.5
9.9
6.5
0.0
0.0
13
23
12
filter size
# rotations
(a) Filter size
(b) Rolational invariance
Figure 5: Training losses of the models in this paper's experiments as function of (a) filter size and (b) the number of training rotations. Models with stronger inductive bias generally exhibit larger losses. However, in all instances, the numerical difference small. Lines show the mean loss over 5 training set samples in (a) and 5 different optimization runs (b), shaded areas the corresponding standard error.
In the following, we first describe how our hyperparameter and model selection procedure ensures that all models all experiments are sufficiently overparameterized, so that double descent predicts negligible effects from increasing the number of parameters. Then, we provide additional experimen- tal evidence that supports our argument: We repeat a subset of the experiments in Section while upscaling the number of parameters in all models. For fixed model scale and varying inductive bias, we observe that all phenomena in Section persist. For a fixed inductive bias strength, we further that the test eтror of interpolating models saturates at value that matches hypothesis. In particular, for strong inductive biases, the gap in test error between interpolating models and their optimally early-stopped version harmful interpolation persists.
Hy Hyperparameter tuning We mitigate differences in model complexity for different inductive bias strengths by tuning all hyperparameters on worst-case settings, that is, maximum inductive bias with noisy training samples. To avoid optimizing on test data, we tune on dataset seeds and network initializations that differ from the ones used in actual experiments. Figure 5 displays the final training loss for all empirical settings in this paper. While models with stronger inductive bias exhibit larger training losses, all values are close to zero, and the numerical difference small. Finally, we want to stress again that this discussion is only about the training loss; all models in all experiments have zero training error and perfectly fit the corresponding training data.
Increasing model complexity for varying filter size As additional evidence, we repeat the main filter size experiments from Figure in Section 4.1 using the same setup as before (see Appendix E. I), but increase the convolutional layer width to 256, 512, 1024, and 2048, For computational reasons, we evaluate a reduced number of filter sizes for widths 256 and 512, and only the smallest filter size 5 for widths 1024 and 2048. Since we found the original learning rate 0.2 be unstable for the larger model sizes, we use decreased peak learning rate 0.13 for widths 256 and 512, and 0.1 for widths 1024 and 2048.
Figures 6a and 6b show the test eιrоrs for 20% and 0% training noise, respectively. With noisy training data (Figure 6a), larger interpolating models yield a slightly smaller test error, but the overall trends remain: the gap in test error between converged and optimally early-stopped models increases with inductive bias strength, and the phase transition between harmless and harmful interpolation persists. In particular, Figure 6a shows strong evidence that the number of model parameters does not influence our phenomenon: for example, models with filter size (strong inductive bias) and width 512 (red) have more parameters than models with filter size 27 (weak inductive bias) and width 128 (blue). Nevertheless, models with filter size benefit significantly from early stopping, while interpolation for models with filter size 27 is harmless. In the noiseless case (Figure 6b),
54

---

Published as a conference paper at ICLR 2023
interpolating, width:
128
256
512
noisy:
128
256
512
1024
X 2048
1024
2048
optimally early-stopped, width:
128
256
-- 512
clean:
128
256
512
1024
x 2048
C 1024
x 2048
25%
25%
100%
(optima eall SSppinng
subset train arron
test error
10%
6%
6%
0%
0%
0%
13
23
5
23
27
5
13
23
27
filter size
filter size
filter size
(a) Test error (20% noise)
(b) error (0% noise)
(c) Opt. early stopping (20% noise)
Figure 6: An increase in convolutional layer width by factors 2 to 16 does not significantly alter the behavior of (a) the test error when training on 20% label noise, (b) the test when training 0% label noise, and (c) the training error when using optimal early stopping 20% lahel noise. Despite significantly larger model size, the phase transition between harmless and harmful interpolation persists. Lines show the mean over five random datasets, shaded areas the standard error.
increasing model complexity does neither harm nor improve generalization, and all models achieve their optimal performance after interpolating the entire training dataset. Similarly, Figure 6c reveals that the fraction of training noise that optimally early-stopped models fit stays the same for larger models. Finally, for a fixed inductive bias strength, the test errors saturate as model size increases, making a different trend for models with more than 2048 filters unlikely. increase legibility, we present the numerical results for the largest two filter sizes in Table 1.
Table 1:
Test errors for filter size 5 (strongest inductive bias) and very large width under 20% training noise.
width 1024
width 2048
early-stopped test error
0.0062%
0.0049%
interpolating test error # parameters
3.6251%
3.3664%
289281
578049
Increasing model capacity for varying rotational invariance For completeness, we also repeat the rotation invariance experiments from Figure 3 in Section 4.2 with twice as wide Wide Residual Networks reduced number of rotations. More precisely, we increase the network widen-factor from to 12, and otherwise use the same setting as the main experiments (see Appendix E.2). Note that this corresponds to parameter increase from around million to around 24 million parameters.
The results in Figure provide additional evidence that our phenomenon distinct from double descent: both the test error (Figures 7a and 7b) and fraction of fitted noise under optimal early stopping (Figure 7c) exhibit the same trend, despite significant difference number of parameters.
55

---

Published as a conference paper at ICLR 2023
noisy subset: WRN16-6
WRN16-12
interpolating: optimally early-stopped:
WRN16-6
WRN16-12
clean subset:
WRN16-6
WRN16-12
WRN16-6
WRN16-12
17%
17%
subset train error (
100%
[optimal early deopaan
12%
12%
test error
8%
8%
38%
3%
3%
0%
0%
0%
12
12
rotations
# rotations
# rotations
(a) Test error (20% noise)
(b) Test error (0% noise)
(c) Opt. early stopping (20% noise)
Figure 7: Doubling Wide Residual Network width does not significantly alter the behavior of (a) the test training on 20% label noise. (b) the test error when training on 0% label noise, and (c) training error when using optimal early stopping on 20% label noise. Despite significantly larger model size, the phase transition between harmless and harmful interpolation persists. Lines show the mean over five random network initializations, shaded areas the standard error.
56


Reviews:
[{"review_id": "WYDeyBoTrD", "reviewer": "Reviewer_NQJb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "This paper studies the harmless interpolation in the setting of high-dimensional kernel regression with convolutional kernels. Here, harmless interpolation means that the performance (measured by test error) gap between the interpolated models and optimal-regularized model is small. The authors gave the non-asymptotic bounds of test error (in terms of bias-variance decomposition) for both regularized and interpolated models. The authors further showed the impact of filter size of convolutional kernels: harmless interpolation will not happen for small filter size (strong inductive bias), but will occur for large filter size. Also, it is shown that for large filter size, the optimal-regularized models have to fit part of the noise, i.e., training error smaller than noise level. Experiments are provided to justify the theoretical results.", "summary_of_the_review": "In summary, the paper studied the generalization error of optimal-regularized and interpolated models in high-dimensional kernel regression setting. The results showed impact of filter size to the test error, which appears to be new and interesting. Therefore, I’m leaning towards accept.", "strength_and_weaknesses": "Strength:\n- The paper is overall clearly written and easy-to-follow.\n- Understanding the generalization properties of interpolated models is an important and interesting direction of the theoretical machine learning, and this paper gives interesting results towards this direction.\n- The results are interesting and novel to my knowledge, which show the relation between filter size and the performance of optimal-regularized and interpolated models.\n- The results are clearly stated with assumptions. Proof sketch is provided in the main text with full proof in the appendix.  \n\nWeaknesses:\n- The proof techniques may not be easy to generalize to other settings beyond kernel and linear settings.\n- It would be great if authors could provide a formula (or the order) of some quantities in the main text or appendix, such as $\\beta^*$ and $\\lambda_{opt}$.\n\nMinor:\n- line 208: missing a space between descent and predicts\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "T7UgnU77oAy", "reviewer": "Reviewer_fKcA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "This paper studies how the strength of inductive biases affect harmless interpolation or benign overfitting, where models can generalize well despite interpolating a (possibly noisy) test set. To study this question, the authors adjust the filter size in convolutional kernels. Smaller filter sizes encode for functions that depend nonlinearly only on local neighborhoods of the input features, whereas this bias is weakened for larger filter sizes. The paper shows theoretically that for high-dimensional kernel regression with convolutional kernels, there is a phase transition between harmless and harmful interpolation in filter size (Theorem 1). The authors show that interpolation is harmless for weak inductive biases, and that for strong inductive biases, they show interpolation can be harmful. Further, they show fitting noise is necessary for strong inductive biases to achieve optimal performance. These theoretical results are supported by experiments in neural networks, where the same phenomenology is observed.", "summary_of_the_review": "The paper makes a nice contribution and is of interest to the ICLR community. It is clearly written with nice figures. From my read of the paper's main text, the theorems seem correct.", "strength_and_weaknesses": "**Strengths**\n- The paper studies an important problem of benign overfitting and finds a new condition (strength of inductive bias) that it is predicated on.\n- The paper is easy to follow and well written. It states the main claims clearly and provides evidence for them.\n\n**Weaknesses**\n- The difference between the strength of inductive biases and parameter count is not fully resolved in the neural network experiments. Is it possible to just control the number of parameters by adjusting the width to compensate for change in filter size?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1RyVkWOh6I", "reviewer": "Reviewer_KVHo", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper studies the impact of the strength of inductive bias on the generalization performance of the trained model. First, the authors prove that in kernel learning with convolutional kernels, a phase transition occurs in the noisy data setting. Specifically, when the level of inductive bias exceeds a particular threshold, interpolation is harmful. But, it is harmless when the inductive bias is sufficiently weak. For the noiseless data setting, no similar transition occurs and interpolation is provably harmless. In addition, the authors prove that in the noisy data setting, the model with the weak inductive bias fits some of the noise (variance on the training sample is below the data variance). However, the latter statement does not really prove that interpolating noise is necessary since nothing is mentioned about the optimal inductive bias. Finally, the authors present two experiments, which suggest that such conclusions seem to hold in deep neural networks as well. \n", "summary_of_the_review": "This is a nice, insightful paper that is well-executed. However, I haven't verified the correctness of the proofs.", "strength_and_weaknesses": "This is a well-polished paper that studies the important topic of generalization in modern neural networks. The authors present an interesting insight in terms of inductive bias that is quite novel and is supported both theoretically and experimentally. The experiments are also well-executed. \n\nThe primary weakness is that the settings studied theoretically and experimentally are contrived but I don’t think this is a major issue given the insight this paper provides. It would have been valuable to figure out how to quantify inductive bias in typical training settings, e.g. in standard benchmark image datasets with convolutional neural networks, but this is quite challenging given the lack of knowledge about the ground truth. \n\nAnother weakness is already acknowledged by the authors. The main theoretical results make strong assumptions about the distribution of the data that cannot be easily relaxed. \n\nFinally, while the authors prove that models with weak inductive bias interpolate some of the noise, this does not mean that interpolating noise is necessary since it is not clear whether the optimal bias is below or above the threshold $\\beta^\\star$. Please correct me if I have miss-interpreted this part.\n\nI have two minor suggestions:\n\n- Please clarify the meaning of the $\\Theta$ notation for quantities that are bounded from below by zero and go to zero such as writing $\\sigma^2 = \\Theta(d^{-\\ell_\\sigma})$. I personally read this as $O$ notation but if there is more than that, please clarify in the paper. \n- The statement of the theorems should be self-contained. Currently, there are hidden assumptions on the ground truth and eigenfunctions in the proof that are not stated in the main theorems. Please mention them explicitly. \n\nTwo typos:\n\n- Line 32: “interpolators interpolators”\n- Line 208: “double descentpredicts”\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster