For interpolating kernel machines, minimizing the norm of the ERM solution minimizes stability
Authors: Akshay Rangamani
Lorenzo Rosasco
Tomaso Poggio
Venue:  (2021)
Keywords: Stability
Linear Regression
Kernel Regression
Cross Validation Leave One Out Stability
Minimum norm solutions
Interpolation
Double Descent

Abstract: We study the average CV Leave One Out stability of kernel ridge-less regression and derive corresponding risk bounds. We show that the interpolating solution with minimum norm minimizes a bound on CV Leave One Out stability, which in turn is controlled by the condition number of the empirical kernel matrix. The latter can be characterized in the asymptotic regime where both the dimension and cardinality of the data go to infinity. Under the assumption of random kernel matrices, the corresponding test error should be expected to follow a double descent curve.

Under review as a conference paper at ICLR 2021
FOR INTERPOLATING KERNEL MACHINES, MINIMIZING THE NORM OF THE ERM SOLUTION MINIMIZES STABILITY
Anonymous authors Paper under double-blind review
ABSTRACT
We study the average CV stability of kernel ridge-less regression and derive corresponding risk bounds. We show that the interpolating solution with minimum norm minimizes bound on CVioo stability, which in turn is controlled by the condition number of the empirical kernel matrix. The latter can be characterized the asymptotic regime where both the dimension and cardinality of the data go infinity. Under the assumption of random kernel matrices, the corresponding test error should be expected to follow double descent curve.
INTRODUCTION
Statistical learning theory studies the learning properties of machine learning algorithms, and more fundamentally, the conditions under which learning from finite data is possible. In this context, classical learning theory focuses on the size of the hypothesis space in terms of different complexity measures, such as combinatorial dimensions, covering numbers and Rademacher/Gaussian complexities (Shalev-Shwarzz & Ben-David 2014 [oucheron et al. 2005). Another more recent approach based on defining suitable notions of stability with respect perturbation of the data (Bousquet & Elisseeff] [000]] Kutin & Niyogi (002). In this view, the continuity of the process that maps data to estimators crucial, rather than the complexity of the hypothesis space. Different notions of stability can be considered, depending on the data perturbation and metric considered (Kutin & Niyogi 2002). Interestingly, the stability and complexity approaches to characterizing the learnability of problems are not at odds with each other, and can be shown to be equivalent as shown in Poggio et al. (2004) and Shalev- -hwir-----ttzzz et al. 2010).
In modern machine learning overparameterized models, with larger number of parameters than the size of the training data, have become common. The ability of these models to generalize is well explained by classical statistical learning theory long as some form of regularization is used in the training process (Bühlmann & Van De Geer [001 Steinwart & Christmann, 2008). However, it recently shown first for deep networks (Zhang al. (017), and more recently for kernel methods (Belkin et al., 2019) that learning is possible in the absence of regularization, i.c., when perfectly fitting/intrrpolatin the data. Much recent work in statistical learning theory has tried to find theoretical ground for this empirical finding. Since learning using models that interpolate is not exclusive to deep neural networks, we study generalization in the presence of interpolation in the case of kernel methods. We study both linear and kernel least squares problems in this paper.
Our Contributions:
We characterize the generalization properties of interpolating solutions for linear and kernel least squares problems using stability approach. While the (uniform) stability properties regularized kernel methods are well known (Bousquet & Elisseeff] 2001). we study interpolating solutions of the unregularized ("ridgeless") regression problems.
We obtain an upper bound on the stability of interpolating solutions, and show that this upper bound is minimized by the minimum norm interpolating solution. This also means that among all interpolating solutions, the minimum norm solution has the best test emror. In

---

associated feature Under review as a conference paper at ICLR 2021
particular, the same conclusion is also true for gradient descent, since it converges to the minimum norm solution in the setting we consider, see e.g. Rosasco & Villa (2015).
Our stability bounds show that the average stability of the minimum norm solution is controlled by the condition number of the empirical kernel matrix. It is well known that the numerical stability of the least squares solution governed by the condition number of the associated kernel matrix (see the discussion of why overparametrriztion is "good" in Poggio ct al. (2019). Our results show that the condition number also controls stability (and hence, test etror) statistical sense.
Organization: In section 2 we introduce basic ideas in statistical learning and empirical risk minimization, as well as the notation used in the rest of the paper. In section [] we briefly recall some definitions of stability. In section we study the stability of interpolating solutions to kernel least squares and show that the minimum norm solutions minimize an upper bound on the stability. In section 5 we discuss our results in the context of recent work on high dimensional regression. We conclude in section
STATISTICAL LEARNING AND EMPIRICAL RISK MINIMIZATION
We begin by recalling the basic ideas statistical learning theory. In this setting, X is the space of features, Y is the space of targets or labels, and there is an unknown probability distribution μ on the product space 7 = X x Y. In the following, we consider X = R and Y = RR. The distribution j fixed but unknown, and we are given a training set consisting of n samples (thus |S| = n) drawn i..dd from the probability distribution on Z S = (z))
(x,, y4 w))== Intuitively, the goal of supervised learning is to use the training set S to "learn" " function fs that evaluated at a new value Nnew should predict the associated value of Vnew, i.e. Vnew Re fs(Xnew).
The loss is a function V x Z - oo), where to Y. that measures how well function performs the space of measurable functions from X data point. We define hypothesis space H. C FF where algorithms search for solutions. With the above notation, the expected risk of f is defined T[]] W V[f =) which is the expected loss new sample drawn according to the data distribution In this setting, statistical learning can be seen as the problem of finding an approximate minimizer of the expected risk given training set S. A classical approach derive an approximate solution is empirical risk minimization (ERM) where we minimize the empirical risk Islf] - 2f)
A natural error measure for our ERM solution fs is the expected excess risk - 1 [[]]] Another common error measure is the expected generalization error/gap given by Es[[[fs] - Is [fs]]. These two етrог measures are closely related since, the expected excess risk is easily bounded by the expected generalization error (see Lemma
2.1 KERNEL LEAST SQUARES AND MINIMUM NORM SOLUTION
The focus in this paper is on the kernel least squares problem. We assume the loss function V is the square loss, that is, V(f,z) x) (y f( The hypothesis space is assumed to be a reproducing kernel Hilbert space, defined by a positive definite kernel K X x X R map T X + H. such that K(x,x') = (0)x). (xx)) for all x, x' E X, where (5))) is the inner product in H. In this setting, functions are linearly parameterized, that is there exists E H such that fx) = (w, (xx)) for all & E X.
The ERM problem typically has multiple solutions, one of which is the minimum norm solution:
S = arg min || FEM
M = arg min
()(())) -.)
FEH n 1=1
Here || is the norm on H induced by the inner product. The minimum norm solution can be shown be unique and satisfy representer theorem, that is for all X:
f(x)= Σ X(xxxx)csl
cs = k
(2)
2

---

Under review as a conference paper at ICLR 2021
where cs = [cs[_].....,.
y (..) R", K is the n by n matrix with entries K,y K ((x,, xy). i,j I...., n. and Kt is the Peooree pscudoinverse of K. If assume d and that we have n linearly independent data features, that the rank of X is n, then it is possible to show that for many kernels can replace Kt by K- (see Remark 2 Note that invertibility is
necessary and sufficient for interpolation. That is, if K is invertible, f3 (x:) - ya for all = 1..... n, in which case the training error in is zero.
Remark 1 (Pseudoinverse for underdeterminet linear systems) A simple yet relevant example linear functions f(x) w x, that correspond H = R and & the identity map. If the rank of X E R is n, then any interpolating solution ws satisfies x; yi for all i 1,... Th, and the minimum norm solution, also called
solution, is given by (wls) = =y TTX X where the pseudoinverse X! takes the form X X )
Remark 2 (Invertibility of translation invariant kernels) Translation invariant kernels are family of kernel functions given by K (x1,xx)) = k(xi X2) where k. is an even function on Rd Translation invariant kernels are Mercer kernels (positive semidefinite) if the Fourier transform of k(-) is non-negative. For Radial Basis Function kernels (K (x)Xx))
k[[[x] x2ll)) we have the additional property due to Theorem 2.3 of Micchelli (986)) that for distinct points
X1. X E R the kernel matrix K is non non-singular and thus invertible.
The above discussion is directly related to regularization approaches.
Remark 3 (Stability and Tikhonov regularization) Tikhonov regularization is used to prevent potential unstable behaviors. In the above setting, it corresponds to replacing Problem (1) by minseH 1 (i=(((x)) - y:) + 11 where the corresponding unique solution is given by c
n
(x) = Ei x(((l, c (K (K+ XIx) In contrast to ERM solutions, the above approach prevents interpolation. The properties of the corresponding estimator are well known. In this paper, complement these results focusing the case X + O.
Finally, we end by recalling the connection between minimum norm and the gradient descent.
Remark 4 (Minimum norm and gradient descent) In our setting. it well known that both batch and stochastic gradient iterations converge exactly to the minimum norm solution when multiple solutions exist, see e-g. Rosasco & Villa (2015). Thus, a study of the properties of the minimum norm solution explains the properties of the solution to which gradient descent converges. In particular, when ERM has multiple interpolating solutions, gradient descent converges solution that minimizes a bound on stability, as we show in this paper.
3 ERROR BOUNDS VIA STABILITY
In this section, we recall basic results relating the learning and stability properties of Empirical Risk Minimization (ERM). Throughout the paper, assume that ERM achieves minimum, albeit the extension to almost minimizer is possible (Mukherjee et al. 2006) and important for exponential-type loss functions (Poggio 2020). We do not assume the expected risk to achieve minimum. Since we will be considering leave-one-out stability in this section, we look at solutions to ERM over the complete training set S (=1, 22, 2n} and the leave one training set S (21, 22,...,
Ait1y-..,
The excess risk of ERM can be easily related its stability properties. Here, we follow the definition laid out in Mukherjee et al. (2006) and say that an algorithm is Cross- Validatin leave-one-out too) stable in expectation, if there exists 3ev such that for all i I,...,7, n,
Es|V(Js, 2) V(fs, & Bcv.
This definition is justified by the following result that bounds the excess risk of a learning algorithm by its average CVi.o stability
et al. 2010 Mukherjee et al. 2006).
Lemma 5 (Excess Risk & CV too Stability) For all i I,...,m inf Ti]]] s Es(V([s,, - v(ss.z)).
Es [[fs.)
(4)
SEK
3

---

Under review as a conference paper at ICLR 2021
Remark 6 (Connection to uniform stability and other notions of stability) Uniform stability, introduced by Bousquet & Elisseeff (200T), corresponds in our notation to the assumption that there L...., sup=ez 2) ( 2) S Bu. Clearty this is strong notion implying most other definitions stability. We note that there are number of different notions of stability. We refer the interested reader to Kutin & Niyogi (2002). Mukherjee al. (0066)
exists 3n > 0 such that for all
V(fs,
We recall the proof of Lemma 5 in Appendix A.2 due to lack of space. In Appendix A, we also discuss other definitions of stability and their connections to concepts in statistical learning theory like generalization and learnability.
4 Co STABILITY OF KERNEL LEAST SQUARES
In this section we analyze the expected CVico stability of interpolating solutions to the kernel least squares problem, and obtain upper bound their stability. We show that this upper bound on the expected CV too stability is smallest for the minimum norm interpolating solution when compared other interpolating solutions to the kernel least squares problem.
We have a dataset S = {(x;, yi )== and we want to find a mapping S E H. that minimizes the empirical least squares risk. Here H is reproducing kernel hilbert space (RKHS) defined by positive definite kernel
> R. All interpolating solutions are of the form fs(.) E K (x,,,) where èş = K + (I K KiK)v. Similarly, all interpolating solutions on the leave one out dataset S; can be written as (.) = Lj- ()) "), where čs. K Yi + Ks, )v, Here K, Ks, are the empirical kernel matrices on the original and leave one out datasets respectively. We note that when 0 and v; O, we obtain the minimum norm interpolating solutions on the datasets S and S..
X
Theorem (Main Theorem) Consider the kernel least squares problem with a bounded kernel and bounded outputs y, that is there exist K, M >> such that
x(x,x) k2,
1 M,
(5)
almost surely. Then for any interpolating solutions fs., Ss.
Es(V(fs. V (fs. =i)l S y,v,v,
(6)
This bound Bev is minimized when v minimum norm interpolating solutions fs.Js:
= v; = O, which corresponds to the
et
For the minimum norm solutions we have
3cv -CB C282. where 31 Es | l x cond(K) x ||y|]] and, B2
Es ||K&|10, 1 (cond(KK)²² x 11x112] and C1, C2 are absolute constants that do not depend on either or n.
In the above theorem ||op refers to the operator norm of the kernel matrix K, ||y|| refers to the standard f2 norm for y E R", and cond(K) is the condition number of the matrix K.
We can combine the above result with Lemma 5 to obtain the following bound on excess risk for minimum norm interpolating solutions to the kernel least squares problem:
Corollary 8 The excess risk of the minimum norm interpolating kernel least squares solution can be bounded as:
[ inf JEN
Es
< C1,88 + C2B2
where 32, 32 are as defined previously.
Remark 9 (Underdetermined Linear Regression) In the case of underdetermined linear regression, ie, linear regression where the dimensionality is larger than the mumber of samples
in the training set, we can prove a version of Theorem with 3 = Es ||
| and
32 Es [||]|]] 1?. Due to space constraints, we present the proof of the results in the linear regression case in Appendix B
4

---

Under review as a conference paper at ICLR 2021
4.1 KEY LEMMAS
In order to prove Theorem 7 we make use of the following lemmas to bound the CVtow stability using the norms and the difference of the solutions.
Lemma 10 Under assumption
55. for foralli allaiill....... it holds that
Es[V 24) - 2:) S Es (2M (1(ss] + +1[is,]1 (w)) x k Iliss fs. [m]
Proof We begin, recalling that the square loss is locally Lipschitz, that is for all y, a, a' E R, with
(ly - a)² - (y - d')²1 - (2]y) + |a| + la la'Daaa d').
we apply this result to f. f' in RKHS H.
Ily f(x))² (y f (x)) & x(2M + K. (Ilfllx + (1)))) - f'
using the basic properties a RKHS that for all f E H
|x() 1 |1/ - supxlf(x
sup (J, Kx)xl S K 111
(7)
In particular, we can plug fs. and fs into the above inequality, and the almost positivity of ERM (Mukherjee et al. 2006) will allow to drop the absolute value the left hand side. Finally the desired result follows by taking the expectation over S.
Now that we have bounded the Co stability using the norms and the difference of the solutions, we can find bound on the difference between the solutions to the kernel least squares problem. This our main stability estimate.
Lemma 11 Let fs. be any interpolating kernel least squares solutions on the full and leave one out datasets (as defined at the top of this section), then ffs - fs.l1 S (cv y, v, v:), and Bcy is minimized when v =, O, which corresponds to the minimun norm interpolating solutions fs.
Also some absolute constant C,
|1 - 13. < C
Kt
Kt
co) x ||y||
(8)
op
Since the minimum norm interpolating solutions minimize both |
+ [fs. and fs
fs.
(from lemmas 10 [1), we can put them together to prove theorem In the following section we provide the proof of Lemma II
Remark 12 (Zero training loss) In Lemma 10 we the locally Lipschitz property of the squared loss function to bound the leave one out stability in terms of the difference between the norms of the solutions. Under interpolating conditions, if we set the term V = 0, the leave one out stability reduces to Eg
21) = (x. - 9:) = Ess,s,,)) fs(,, (xx(xx))) (-)) IEs [llfs - fs. li x n²) We can plug in the bound from Lemma to obtain similar qualitative and quantitative (up constant factors)
V(fs, 24) (ffs. = Es [((s..
Es((fs,(x))
results as in Theorem 7
Simulation: In order illustrate that the minimum norm interpolating solution is the best performing interpolating solution we ran simple experiment on a linear regression problem. We synthetically generated data from a linear model y w X, where X E IR was i.i.d i.i.d. 1). 1000 and there were n = 200 samples in the training dataset. A
The dimension of the data was held out dataset of 50 samples was used to compute the test mean squared error (MSE). Interpolating solutions were computed as w = y Txt +v (I-XX xXX and the norm of v was varied to obtain the that the training loss is 0 for all interpolants, but test MSE increases as || increases, with (wT) = y T xi having the best performance. The figure reports results averaged over 100 trials.
plot. The results shown in Figure [ where
5

---

Under review as a conference paper at ICLR 2021
MSE of interpolating solutions
80000
test MSE
60000
20000
2
10
|| w
Figure 1: Plot of train and test mean squared error (MSE) distance between interpolating solution w and the minimum norm interpolant w' of a linear regression problem. Data was synthetically generated as y = w X, where X E Rdxa with i.i ((0, 1) entries and = 1000, n = 200. Other interpolating solutions
computed as w y xt +v to obtain the plot. Train MSE is 0 for all interpolants, but test MSE increases as ||v| increases, with w! having the best performance. This plot represents results averaged over 100 trials.
XXt) and the norm of
varied
4.2 PROOF OF LEMMA
We can write any interpolating solution to the kernel regression problem fs(x) Σ k where èş K'y + (I K'Kjv, and K E gax= is the kernel matrix K on S and v is any vector in R" i.. K, K(x, xy), and y R" is the vector ly.... yn!
Similarly, the coefficient vector for the corresponding interpolating solution to the problem over the leave one out dataset S, is čs. (Ks,) + (I (Ks,)KK (K,, V4. Where y; ......., O,... yn and Ks, is the kernel matrix K with the 7th row and column set to zero, which is the kernel matrix for the leave
out training set.
We define a = | ((1 x4),..., - K(x, x;) E IR" and b E IR" as a one-hot column vector with all zeros apart from the 9th component which is 1. Let a,
K K(x,, x,)b. Then, have:
K, = + ba?
Ks. = K, + ab
That is, we can write Ks, as a rank-2 update to K. This can verified by simple algebra, and using the fact that K is symmetric kernel. Now we are interested in bounding Ilʃs fs, llx. For m function h(-) DI= (x.,)) H. we have ||l|| vp Kp || pll. So we have:
llfs fs.11 = (Cs ēs.)ll
||K' (Kly (I K'K)v (Ks;) (I--KK (K-ss - Ks,
||K (Kty (Ks,)ty + tk,,Ks))
(I KtK)(v- vv)) + (KtK- (Ks;) ( Ks:)v:)
= || - -(Ks)) + (I (L-KKK)(---- v.) - (K' (Ks,) ) K vvill
(10)
Here make of the fact that (Ks, bb 0. If K has full rank (as in Remark that lies in the column space K and a. lies in the column space of KT. Furthermore, 3,
1 1 +a. Ktb 1 + Kib (x;,,,)b kib (x(KK)a o 0. Using equation 2.2 of Baksalary

---

Under review as a conference paper at ICLR 2021
al. 2003 obtain:
K Kt
Kt Kt ((a((K)))-kkig T K - - -bbbT kt
(11)
Kt + (aa((K))))K"" - ((KK))))) -K
Here we make use of the fact that a Kl = -b. Also, using the corresponding formula from List of Baksalary et al. (200)), we have K.K, = K.
Next, we see that since K, has the same rank as K, a lies in the column space of K., and lies in the column space of K. Furthermore 9 = + K,a = O. This means we can use Theorem Meyer (973) (equivalent to formula 2.1 in Baksalary et al. (003)) to obtain the expression for (Ks,), with KŞa and b K..
(Ks,) = K kkkk -K (k'
(Ks:) K; = -Kk - kktk K[hhh
(12)
I1(Ks;)))))) kopp S <3|K!!lop
Above, we use the fact that the operator of rank matrix is given by |uv llop
||u||
||vl|-
Also, using the corresponding formula from List 2 of Baksalary et al. (2003), we have:
(Ks)) Ks. K,K, kk
(13)
KIK sKs;) Ks, -kk
Putting the two parts together we obtain the bound on (Ks;)) K l'
|K (Kss)*
||K
K + K (Ks;)*lle
< 3 K lop + |K - K Killop
(14)
S 3 K
lop + 4(K,; (K) (K()) -K bKkklllpp 1lap
Kt
lop 8 | |l
K lop)
The last step follows from (Kx)~
<
K
op and ((K)):)) $ |
|||ppp
Plugging in these calculations into equation 10 get:
[lss - fs.12 = | [[kt (Ks,) + (I KtK)(v - v.) (KÝK -Ks, (Ks
< K dlop (II(K) (Ks, |y ||[I ((V[I-KKKVV----O lkkk/v
< K (Bo + |I - K K - 1|vill)
(15)
We see that the right hand side minimized when v v; 0. We have also computed Bg = C' x ||K||lop cond(K) x ||yl|, which concludes the proof of Lemma 11
5 REMARK AND RELATED WORK
In the previous section we obtained bounds on the CV stability of interpolating solutions to the kernel least squares problem. Our kernel least squares results can be compared with stability bounds for regularized ERM (see Remark 3 Regularized ERM has strong stability guarantee in terms of uniform stability bound which turns out to be inversely proportional to the regularization parameter À and the sample size (Bousquet& & Elisseeff 2001). However, this estimate becomes vacuous as + In this paper, we establish bound on average stability, and show that this bound is minimized when the minimum norm ERM solution is chosen. We study average stability since can expect
7

---

Under review as a conference paper at ICLR 2021
3000
Condition number
2500
2000
1500
dio
500
Figure 2: Typical double descent of the condition number (y axis) of radial basis function kernel K(x, x²) = exp |<=2''12 built from a random data matrix distributed as (0, 1): as in the linear 20
case, the condition number is worse when d, better if d (on the right of d) and also better if n < d (on the left of n = d). The parameter was chosen to be 5. From Poggio et al. (2019)
worst case scenarios where the minimum norm is arbitrarily large (when n R d). One of our key findings is the relationship between minimizing the norm the ERM solution and minimizing bound on stability.
This leads second observation, namely, that we can consider the limit of our risk bounds both the sample size (11) and the dimensionality of the data (d) go infinity, but the ratio & + 7 > 1 as n, d > D0 This is classical setting in statistics which allows us to use results from random matrix theory (Marchenko & Pastur 1967). In particular, for linear kernels the behavior of the smallest eigenvalue of the kernel matrix (which appears our bounds) can be characterized in this asymptotic limit. In fact, under appropriate distributional assumptions,
bound for linear regression can be computed as (I|x*I x I|y|))* R Td-VE - Here the dimension of the data coincides with the number of parameters in the model. Interestingly. analogous results hold for more general kerelss (inner product and RBF kernels) (El Karoui 2010) where the asymptotics are taken with respect to the number and dimensionality of the data. These results predict double descent curve for the condition number as found in practice, see Figure While it may seem that our bounds in Theorem) 7 covered by theorem, since when
diverge if d is held constant and n 20, this case we no longer have interpolating solutions.
Recently, there has been surge of interest in studying linear and kernel least squares models, since classical results focus on situations where constraints or penalties that prevent interpolation are added to the empirical risk. For example, high dimensional linear regression is considered in MMi & Montanari] (2019); Hastie et al. (2019); Bartlett et al. (2019), and "ridgeless" kernel least squares is studied in Liang et al. (2019): Rakhlin & Zhai (2018) and Liang al. (2020). While these papers study upper and lower bounds on the risk of interpolating solutions to the linear and kernel least
squares problem, ours are the first to derived using stability arguments. While might be possible to obtain tighter excess risk bounds through careful analysis of the minimum norm interpolant, simple approach helps us establish link between stability in statistical and numerical sense.
Finally, we can compare our results with observations made in Poggio et al. (2019) on the condition number of random kernel matrices. The condition number of the empirical kernel matrix is known to control the numerical stability of the solution
kernel least squares problem. Our results show that the statistical stability is also controlled by the condition number of the kernel matrix, providing a natural link between numerical and statistical stability.
8

---

Under review as a conference paper at ICLR 2021
CONCLUSIONS
In summary, minimizing a bound on cross validation stability minimizes the expected error in both the classical and the modern regime of ERM. In the classical regime (d < n)) CV stability implies generalization and consistency for + In the modern regime (d >> n.) deseribed in this paper, Lo stability can account for the double descent curve kernel interpolants (Belkin et al. 2019) under appropriate distributional assumptions. The main contribution of this paper is characterizing stability of interpolating solutions, in particular deriving excess risk bounds via stability argument. In the process, we show that among all the interpolating solutions, the one with minimum norm also minimizes a bound on stability. Since the excess risk bounds of the minimum norm interpolant depend on the pseudoinverse of the kernel matrix, we establish here an elegant link between numerical and staristical stability. This also holds for solutions computed by gradient descent, since gradient descent converges to minimum norm solutions in the case of "linear" kernel methods. Our approach is simple and combines basic stability results with matrix inequalities.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jerzy K Baksalary, Oskar Maria Baksalary, and Götz Trenkler. A revisitation of formulae for the moore-penrose inverse of modified matrices. Linear Algebra and Its Applications, 372:207-224, 2003.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. CoRR, (oss/190.11 1300, 2019.
11300
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical varinner trade-off. Proceedings of the National Academy of 2019. ISSN 0027-8424. doi: 10.1073/pnas. 19030701 16. URL
Sciences, 158632)
https: www pwws. wwtp://gtttooooneneeeeeeee /20111//22155/ 32/11/ 3584999
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
O. Bousquet and A. Elisseeff. Stability and generalization. Journal Machine Learning Research, 2001.
Peter Bühlmann and Sara Van De Geer. Statistics for high-dimensional data: methods, theory and applications. Springer Science Business Media, 2011
Noureddine El Karoui. The spectrum of kernel random matrices. arXiv e-prints, art. arXiv:1001.0492 Jan 2010.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High- Dimensional Ridgeless Least Squares Interpolation. arXiv e-prints, arXiv:1903.08560, Mar 2019.
S. Kutin and P. Niyogi. Almost-everywhere algorithmic stability and generalization error. Technical report TR- 2002000, University of Chicago, 2002.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels. arXiv e-prints, art. arXiv: M.Xi:1998..12999 10292, Aug 2019.
Tengyuan Liang. Alexander Rakhlin, et al. Just interpolate: Kernel "ridgeless" regression can generalize. Annals of Statistics,
2020.
V. A. Marchenko and L. A. Pastur. Distribution of eigenvalues for some sets of random matrices. Mat. Sb. (N.S.), 72 22114):44577-83 1967.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv e-prints, art. 908.05555, Aug 2019.
Carl Meyer. Generalized inversion of modified matrices. SIAM J. Applied Math, 24:315-323, 1973.
C. A. Micchelli. Interpolation of scattered data: distance matrices and conditionally positive definite functions. Constructive Approximation, 1-122, 1986.
Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25(1):161-193, 2006. ISSN 1572-9044. doi: 111100//111444000--666333 s 110444-004-6344
URL http://da doi www.:oooo.......0000/
T. Poggio, R. Rifkin, S. Mukherjee, and P. Niyogi. General conditions for predictivity in learning theory. Nature, 428:419-477 422, March 2004.
T. Poggio, G. Kur, and A. Banburski. Double descent in the condition number. Technical report, MIT Center for Brains Minds and Machines, 2019.
Tomaso Poggio. Stable foundations for learning. Center for Brains, Minds and Machines (CBMM) Memo No. 103, 2020.
10

---

Under review as a conference paper at ICLR 2021
Alexander Rakhlin and Xiyu Zhai. Consistency of Interpolation with Laplace Kernels is High- Dimensional Phenomenon. arXiv e-prints, art. arXiv:1812.11167 Dec 2018.
Lorenzo Rosasco and Silvia Villa. Learning with incremental iterative regularization.
In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 1630-1638.
Curran Associates, Inc.. 2015. URL http::/papers.. intrrrss.piis nips. cc/paper/
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. J. Mach. Learn. Res., 11:2635 2670, December 2010. ISSN 1532-4435.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science Business Media, 2008.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL http:://ppeeeevieeee/ net Sorumidd-SyyddBBB.

---

Under review as a conference paper at ICLR 2021
A EXCESS RISK, GENERALIZATION, AND STABILITY
We use the same notation introduced in Section 2 for the various quantities considered in this section. That is in the supervised learning setup [ 2) is the loss incurred by hypothesis f on the sample 2, and [[ B. (f, 2]] the expected error of hypothesis f. Since we are interested in different forms of stability, we will consider learning problems over the original training set {21, 22.... ) the leave one out training set S = (21,...; Fi , and the
replace one training set 2)) (=1...., 21-1, 21+1:-.., kn, 2]
A.1 REPLACE ONE AND LEAVE ONE OUT ALGORITIIMIC STABILITY
Similar to the definition of expected Co stability in equation 3 of the main paper, we say an algorithm is cross validation replace one stable (in expectation), denoted as CV there exists Bro 0 such that
Vs. ((((s.s)))) s 3ra-
We can strengthen the above stability definition by introducing the notion of replace one algorithmic stability (in expectation) Bousquet Elisseeff (200T). There exists aro > such that for all I,.
Es f(s).=) bel aro-
We make two observations: First, if the loss is Lipschitz, that there exists Cv > 0 such that for all f, f H
[V((f,) v(f,, Cv llf - f'll.
then replace one algorithmic stability implies CV stability with 3ro Cya Moreover, the same result holds if the loss is locally Lipschitz and there exists R 0, such that || I R almost surely. In this latter case the Lipschitz constant will depend on R. Later, we illustrate this situation for the square loss.
Second, we have for all i = 1...., ,, S and 2,
Es.e fs - f(s..)) [ s Es. - fs.ll +E,.all l.
This observation motivates the notion of leave algorithmic stability (in expectation) [Bouqquet & Elisseeff [2001)]
Es..lllfs - fs. Iloo] S Olooo
Clearly, leave one out algorithmic stability implies replace one algorithmic stability with Oro = 200 and it implies also CVro stability with 3ro 2Cy
A.2 EXCESS RISK AND Co CV,o STABILITY
We recall the statement of Lemma in section that bounds the excess risk using the CVi.o stability of solution.
Lemma 13 (Excess Risk & CVioo Stability) For all = I,...,n, n.
Es [[fs.]
inf Tis]] Es(V - v(ss,
(16)
JEH
In this section, two properties of ERM are useful, namely symmetry, and form unbiasedeness.
Symmetry. A key property of ERM is that it is symmetric with respect to the data set S, meaning that it does not depend on the order of the data in S.
second property relates the expected ERM with the minimum of expected risk.
12

---

Under review as a conference paper at ICLR 2021
ERM Bias. The following inequality holds.
[[[ssfsl]
min [[f] 0. FEN
(17)
To see this, note that
[s[fs] S [s]s
for all / E H. by definition of ERM, so that taking the expectation both sides
As([s[ss] x [s(Ts[[] [[]]
for all f E H. This implies
Es[Is|fll S min [[f]
FEN
and hence 17 holds.
Remark 14 Note that the same argument gives more generally that inf
E inf
[T[ff]]
[if] O.
(18)
JEH
FEH
Given the above premise, the proof of Lemma is simple.
Proof [of Lemma 5
Adding and subtracting E. [s]] from the expected excess risk we have that
[s[[]
min
SEH [[]]] Es 1s [f[s]] + Is[fs]
min / [[]]].
(19)
JEH
and since EE5 sin [[]]] is less or equal than zero, see (8). then
[s[[[[s.] - min 7 [[[]] < [Tss] Ts [s]]]]]
(20)
JEH
Moreover, for all 1 1,...,
Es [s[[[[s,]] Es V(fs, Es| (fss, z:]
and
1
Es [s|s]]
Es (Js, Es Es =]]
Plugging these last two expressions in 20 and in 19 leads to
We can prove similar result relating excess risk with CVro stability.
Lemma (Excess Risk & CVro Stability) Given the above definitions, the following inequality holds for all i I,....
Es[[[fs]-
inf FER
[[ll S Es[[[ss] [s[fs]] Es. [V... V(((s..))
(21)
Proof The first inequality is clear from adding and subtracting Is[fs] from the expected risk [[ss] we have that
[s[[[[s]
min T[]] Es[ [s[[s] + Ts[[s] min [[[]], feH
/EH
and recalling 18) The main step in the proof is showing that for all = 1,...,n. n,
E[As[/s]] ([(s,))
(22)
to be compared with the trivial equality, [[[s[[s] = EVV =:)]. To prove Equation for all 1,...,n,
22 we have
Es[[s[/]]] Es.. Σ ((s, 1 n Σ Es.: Bss..V (V(s..))) Es, [V.ss
12
2))
where we used the fact that by the symmetry of the algorithm Es, (V([S..)).
=)] is the same for all
i = 1,..., n.. The proof is concluded noting that [[s]]] = Es. (V..VV(ss (fs,
13

---

Under review as a conference paper at ICLR 2021
A.3
DISCUSSION ON STABILITY AND GENERALIZATION
Below we discuss some more aspects of stability and its connection to other quantities in statistical learning theory.
Remark 16 (CVioo stability in expectation and in probability) In Mukherjee et al. 2006), CV1 stability is defined in probability, that there exists BEv > 0. 66v I such that
Ps 2.) - V(fs. 2:)l 2 gev S gEv.
Note that the absolute value is not needed for ERM since almost positivity holds Mukherjee al. (2006), that is V (fs. 2,) V(fs, 2,) > O. Then CV1oo stability in probability and in expectation are clearly related and indeed equivalent for bounded loss functions. CVioo stability in expectation is what we study in the following sections.
Remark 17 (Connection uniform stability and other notions of stability) Uniform stability, introduced by Bousquei & Elisseeff (2007), corresponds in our notation to the assumption that there exists B. > such that for all i - sup=ez (V(fs..)) V(fs. S Ba. Clearly
this is strong notion implying most other definitions of stability. We note that there are number of Mukherjee
different notions of stability. We refer the interested reader to Kutin Niyogi 2002
el al. (2006).
Remark 18 (CV ioo Stability Learnability) A natural question is to which extent suitable notions of stability not only sufficient but also necessary for controlling the excess risk of ERM. Classically, the latter is characterized in terms of a uniform version of the law of large numbers, which itself can be characterized in terms of suitable complexity measures of the hypothesis class. Uniform stability is too strong to characterize consistency while CVioo stability turns out to provide a suitably weak definition as shown in Mukherjee et al. (2006). see also Kutin & Niyogi (2002), Mukherjee al. (2006). Indeed, a main result in Mukherjee et al. (2006) shows that CVtoo stability is equivalent to consistency of ERM:
Theorem 19 Mukherjee et al. (2006) For ERM and bounded loss functions, CVioo stability in probability with Bey converging to zero for - oo equivalent to consistency and generalization of ERM.
Remark 20 (CVioo stability & in-sample/outtof--ammpp error) Let (S, ........ Zns 2}. (z is a data point drawn according the same distribution) and the corresponding ERM solution f(s.:). then 44 can be equivalently written as,
Es[[[fs]
inf I & -V((sss))))((((()))))) JEF
2(((s.)),
Thus CV1.o stability measures how much the loss changes when we test on a point that is present in the training set and absent from it. In this view, it can be seen as an average measure of the difference between in-sample and out-of- sample error.
Remark 21 (CV too stability and generalization) A common error measure is the (expected) For non-ERM algorithms, CVion stability by itself not sufficient
generalizution gap Ess to control this term, and further conditions are needed Mukherjee el al. 20066, since
[s[[[ss] [s[s>]] [s[[[ss] Is[[s.]] [s(Ts[ss]] [[s]]
The second term becomes for all i = 1....,n
n Es Es
Es[Ts[fs.] Ts[
= 2) V(Js,
and hence is controlled by CV stability. The first term is called expected leave one out error in Mukherjee et al. (2006) and is controlled in ERM as Do, Theorem 79 above.
14

---

Under review as a conference paper at ICLR 2021
B Co STABILITY OF LINEAR REGRESSION
We have a dataset S = [(x,,; 0:)] and we want to find mapping w E R that minimizes the empirical least squares risk. All interpolating solutions are of the form Ws = v
Similarly, all interpolating solutions on the leave one out dataset S; can be written as Ws, y. (X,) + vI
(X,), )) Here X.X, X, E Rdxx are the data matrices for the original and leave one out datasets respectively. We note that when interpolating solutions on the datasets S and S..
0 and v; = O, we obtain the minimum norm
In this section we want to estimate the CVion stability of the minimum norm solution to the ERM problem the linear regression case. This the case outlined in Remark of the main paper. In order to prove Remark|9 we only need to combine Lemma I0 with the linear regression analogue of Lemma IT We state and prove that result in this section. This result predicts a double descent curve for the norm of the pseudoinverse as found in practice, Figure 3
Let Ws. Ws, be any interpolating least squares solutions on the full and leave one out datasets S, S,, then ||ws- ws,ll S Bev .y, V, V.). and Bev is minimized when V, which corresponds to the minimum norm interpolating solutions w W
Lemma 22
Also.
W's w's
5 3
x
x ||yl|
(23)
As mentioned before in section 2.1 of the main paper, linear regression can be viewed as case of the kernel regression problem where H = R and the feature map & is the identity map. The inner product and norms considered in this case are also the usual Euclidean inner product and 2-norm for vectors in Rd. The notation ||-|| denotes the Euclidean norm for vectors both in Rd and RR.. The usage of the norm should be clear from the context. Also, || is the left operator norm for matrix A Raxd that is | = suPyER" || Ily All-
We have n samples in the training set for a linear regression problem, (()) We collect all the samples into single matrix/vector X X xx] Rdxn, and y [V192... ... yv]] E RR.. Then any interpolating ERM solution wg satisfies the linear equation
w X y
(24)
Any interpolating solution can be written as:
(ws) = y xt (I-
(25)
If we consider the leave one out training set S; we can find the minimum norm ERM solution for
X; [x] .5....1 ...0..... x,,] and y: [y11 .v........ yn]] as
(ws)) = y. (X.)² (I-XXX(Xx)))
(26)
We can write X; as:
X; x + ab
(27)
where a E Rd is a column vector representing the additive change to the 7th column, i.e, a = - Xx. and b E R= is the i-th element of the canonical basis in RD (all the coefficients are zero but the i- which is one). Thus ab is d x n matrix composed of all zeros apart from the 7th column which is equal to a.
We also have y; y y.b. Now per Lemma T0 we are interested in bounding the quantity Iws. wsll = =[((ss) - (Ws) TI. This simplifies to:
Ws. wsll= = [lxT(X,)' y xx + v. - - - XXI - v XX,')I
xt
II(yT w/b -(,))((X,) - y
- +v Xxt xx,x(X
-(x,
" - -x)) + y (X,) +v. -vT +v xxt -XX,,XX (28)
= =IIyT(XX,) -x') + v. -VT +v Xx! -v, x
= =IlxT((X,)) - -x') (v. -v -, (xx xx(X))'II
15

---

Under review as a conference paper at ICLR 2021
|
oopp for d= 50
50
30
10
10 20
30
40
50
70
80
100
Figure Typical double descent of the pseudoinverse norm (y axis) of a random data matrix distributed (0, 1): the condition number is worse when d, better if > d (on the right of n d) and also better if n < (on the left = d).. From Poggio et al. (2099)
In the above equation make use of the fact that b T (X,)1 O. We use old formula (Meyer 1973 (Baksalary et al. 2003) to compute (X,)* from Xt. We use the development of pseudo-inverses of perturbed matrices in Meyer (1973). We see that a -x;
vector in the column space of X and b is in the range space of X (provided X has full column rank), with 8 = 1 1 b "tta 0. This means we can use Theorem in Meyer (973) (equivalent to formula 2.1 in
X X
b
Baksalary et al. ))03 to obtain the expression for (X,)
(X,) x xk'x x'hh + x kh
(29)
T where k = Xla, and h b x and ul aal for any non-zero vector
(X,) xt (k'th*)) kh kk Xthth
kh
=a (xi) Tx (xl)
la xT(xt)Txt(XX Txt |Tb
||(x,)* x
1lop v
2 llop
(30)
| b Xill
X 1opp
Xta [b Txt]
+ 2|
x 1lop
| b Xi||
3 X
1lop
The above set of inequalities follows from the fact that the operator norm of a rank matrix given
by |luv Tlop ||u|| x ||v||
Also, from List 2 of Baksalary et al. 2003) we have that X,(X;)+ = Xxt hhh.
Plugging in these calculations into equation 28 we get:
l|ws, wsll |yy ((x,)* - xt) (v. -v D)( Xxt) - (xxt- xx()))l
< By + I- x 11op1 |V vell + llvall x |lhth|lop
(31)
< Bo + 2 v.ll + ||vil|
We see that the right hand side minimized when v = V; = 0. We can also compute Bo = extllopllyly which concludes the proof of Lemma 22
16


Reviews:
[{"review_id": "vX0hAEBSwq0", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper establish the average leave-one-out stability bound for the interpolation solutions, and show the above bound depends on condition number and spectral norm of kernel matrices.  The authors establishes a nice connection between numerical and statistical stability. A nice property is that among all interpolation solutions, the upper bound on stability achieves the minimum at the solution with the minimal norm. The authors then comment that the interpolation solution with minimal norm may generalize better than other interpolation solutions. The paper is clearly and well written.\n\nComments:\n\n1. In Theorem 7, the authors show that the stability can be bounded by the spectral norm of $K,K^\\dag$, the condition number of $K$ and the norm of $y$. It seems that this upper bound would diverge as we increase the dimension or sample size. This means that the upper bound is vacuous and may not explain the true generalization behavior of the interpolation solutions. If the upper bound is loose, then even if the interpolation solution with the minimal norm achieves the minimal upper bound, this may not convincingly show that it outperforms other interpolation solutions.\n\n2. I have doubts on eq (10). I think the left-hand side and right-hand side of the third identity differ by the term $2K^\\dag Kv_i$. If $K^\\dag Kv_i\\neq 0$, then this identity would not hold. Since $v_i$ can be any vector, the deduction is not convincing. I would suggest the authors to take a close look at it.\n\n3. Lemma 5 is standard in the literature. I would suggest the authors to indicate its connection with existing results, e.g., Lemma 11 in \"Learnability, Stability and Uniform Convergence\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "uWYilxm14zS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, they provide the risk bounds of  kernel ridge-less regression (the regularization $\\lambda-\\rightarrow 0$) based on the CV_{loo} stability. They show  that the interpolating solution with minimum norm is the minimal bound of CV_{loo} stability, and can be controlled by the condition number of the empirical kernel matrix, which establishes an  elegant link between numerical and statistical stability. \n\nPros: \n-1:  The stability of Tikhonov regularization has been well studied, but the study for the unregularized regression probelms is lacking. This paper fills the gap for unregularized regression.\n\n-2:  They provide an upper bound on the stability of interpolating solutions, and show that among all interpolating solutions, the minimum norm solution has the best test error. They further provide emprical experiments to verify their theoretical findings.  \n\n-3: They show that CV_{loo} stability can be bounded by the condition number of the empirical kernel matrix, which establishes an  elegant link between numerical and statistical stability. \n\nCons:\nIn Theorem 7, the CV_{loo} stability of minimum norm solutions  can be bound by $C_1\\beta_1+C\\beta_2$.  Note that the kernel matrix $\\mathbf K$ converges to the integral operator $L_K:  L_K(f)(x)=\\int_{X}f(x)K(x,y)dy$ when $n\\rightarrow \\infty$, so $\\|{\\mathbf K}^{1/2}\\|$  and $\\|{\\mathbf K}^+\\|$  may converge to  two constants.  Note that the  condition number of the empirical kernel matrix $cond(\\mathbf K)\\geq 1$,  and $\\|y\\|$ grows with the increase of $n$, thus the $\\beta_1$ and $\\beta_2$ may grow  with the the increase of $n$. However, intuitively,  we think the CV_{loo} stability should decrease with the increase of $n$. So, we think the upper bound proposed in this paper may be too loose.\n\nIf you can answer my concern at this point, I will increase my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "UKEnrXcu-U", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "UPDATE:\nAs the authors were already aware of the zero loss case and analyzed this previously, I am confident that the authors can address this to the point in an updated version. With this I think this is a good paper that should be accepted.\n\n##########################\n\nSummary:\nThe papers addresses the setting of overparametrized models that interpolate the training data, and the related double descent observation in a kernel setting. The overparametrized case of interpolating models is not yet that well understood, but of importance as the success of neural networks is closely related to that setting. This paper shows that the minimum norm interpolating solution is optimal (among all interpolating solutions) with respect to a derived bound on the expected leave-one-out stability, and thus also optimal in the same sense with respect to the excess risk. \n\n##########################\n\n##########################\n\nPros:\nThe paper is well written, to the point, and technically (mostly! see cons) sound. \nTo the best of my knowledge this particular stability analysis is novel, and thus warrants a publication, in particular as the overparametrized case is not that well understood as of yet.\n\n##########################\n\n##########################\n\nCons:\nI actually don't have many cons, I enjoyed the paper. There is however one thing that the authors seemed to have missed:\nThe term V(hat(f_S),z_i) is zero, as hat(f_S) interpolates the training data and z_i is part of it. That doesn't mean that any of the theory is wrong, but that creates two problems in my opinion:\n1. The story about leave-one-out stability does not make sense anymore. In fact the expected leave-one-out stability is just the expected risk for interpolating solutions.\n2. I would imagine that most of the results can be simplified because of that. I could imagine that all the results hold with essentially all terms regarding hat(f_s) being removed. I think the qualitative conclusions would remain the same though.\n\nMy suggestion would be to leave the paper as is (the results as far as I see also hold for not interpolating solutions), and then discuss the interpolating solutions as an extra case.\n\n##########################\n\n##########################\n\nScoring: \nFor now I will have to vote for a rejection, as I am not sure if the problem that I mention can be addressed in one rebuttal phase. But I am happily convinced otherwise, or convinced that I am wrong in any other way.\n\n##########################\n\n##########################\n\nAdditional feedback:\n- When I first read the title I thought that you wanted to show minimal norm solutions are NOT stable, as it has 'minimal' stability. I understand now that minimal refers to the numerical value of the stability definition, but still the wording was somewhat confusing. (Just to consider, no need to change for me if you think it is correct like that)\n\n- Equation (2) and also bit later. You use a comma to separate an index \"S,i\", fairly unusual I would say.\n\n- Remark 4, rework first sentence.\n\n- Equation (7), in the very basic property of RKHS the kappa would depend on x, for you that seems to follow with one of your assumptions + cauchy-schwarz. I would not consider that a basic property.\n\n##########################", "extra_scores": {}, "extra_text": {}}, {"review_id": "EDt09JmYuKL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates kernel ridge-less regression from a stability viewpoint by deriving its risk bounds. Using stability arguments to derive risk bounds have been widely adopting in machine learning. However, related studies on kernel ridge-less regression are still sparse. The present study fills this gap, which, in my opinion, is also one of the main contributions of the present study. \n\nPros:\n1.  As mentioned above, this study presents some novel research into kernel ridge-less regression from a stability viewpoint.\n\n2. The study presented here brings some novel insights into the relationship between minimizing the norm of the ERM solution and minimizing a bound on stability and also reveals the role that the condition number of the kernel matrix plays in kernel ridge-less regression, see formula (6). \n\n3.  The paper is well presented and well polished. The analysis conducted in this paper seems to be sound.\n\nJust one minor concern: what would happen if the boundedness assumption on the output variable, which excludes the most common Gaussian noise, is not imposed? I understand that this condition is common in learning theory but are expecting more comments.    ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates the average stability of kernel minimal norm interpolating predictors. The main result 
establishes an upper bound on a particular notion of average stability for which it is well-known that it 
can be used to bound the generalization error. This upper bound holds for all interpolating predictors 
from the RKHS, but it is minimized by the minimal norm predictor. 

While at first glance this result looks highly interesting, a closer look reveals that the significance of the results 
crucially depends on the quality of the derived upper bound. Here two reviewers raised concerns, since it is 
by no means clear that even the optimized upper bound produces meaningful bounds on the generalization
performance. The authors tried to address these concerns in their response and promised to update their 
paper accordingly. As a result, they added a paragraph on page 8. Unfortunately, this paragraph remains extremely 
vague, in particular if it comes to the more interesting case of non-linear kernels. Here, the authors briefly refer to 
a paper by El Karoui but no details are given. However, looking at El Karoui's paper it is anything but obvious whether 
the results of that paper lead to reasonable upper bounds on the average stability for a sufficiently general class 
of distributions. 
As a result, I view the paper under review to be premature since it remains unclear if the observed optimality of the minimal norm solution is a real feature or just an artifact due to an upper bound that is simply too loose to make any conclusion.

  
Decision: Reject