On Optimal Interpolation in Linear Regression
Authors: Eduard Oravkin
Patrick Rebeschini
Venue: NeurIPS 2021 Poster (2021)
Keywords: interpolation
optimality
generalization
linear regression
statistical learning theory

Abstract: Understanding when and why interpolating methods generalize well has recently been a topic of interest in statistical learning theory. However, systematically connecting interpolating methods to achievable notions of optimality has only received partial attention. In this paper, we ask the question of what is the optimal way to interpolate in linear regression using functions that are linear in the response variable (as the case for the Bayes optimal estimator in ridge regression) and depend on the data, the population covariance of the data, the signal-to-noise ratio and the covariance of the prior for the signal, but do not depend on the value of the signal itself nor the noise vector in the training data. We provide a closed-form expression for the interpolator that achieves this notion of optimality and show that it can be derived as the limit of preconditioned gradient descent with a specific initialization. We identify a regime where the minimum-norm interpolator provably generalizes arbitrarily worse than the optimal response-linear achievable interpolator that we introduce, and validate with numerical experiments that the notion of optimality we consider can be achieved by interpolating methods that only use the training data as input in the case of an isotropic prior. Finally, we extend the notion of optimal response-linear interpolation to random features regression under a linear data-generating model.


On Optimal Interpolation in Linear Regression
Eduard Oravkin Department of Statistics
Patrick Rebeschini Department Statisties University of Oxford
University of Oxford
eduard. -chaardoraaviinnsttaee ox.ac.
wetttetttttt....o ox
Abstract
Understanding when and why interpolating methods generalize well has recently been a topic of interest in statistical learning theory. However, systematically connecting interpolating methods to achievable notions optimality has only received partial attention. In this paper, investigate the question of what is the optimal way to interpolate in linear regression using functions that are linear in the response variable (as the case for the Bayes optimal estimator in ridge regression) and depend on the data, the population covariance of the data, the signal-to-noise ratio and the covariance of the prior for the signal, but do not depend on the value of the signal itself nor the noise vector in the training data. We provide a closed- form expression for the interpolator that achieves this notion of optimality and show that it can be derived as the limit of preconditioned gradient descent with a specific initialization. We identify regime where the minimum-norm interpolator provably generalizes arbitrarily worse than the optimal response- interpolator that we introduce, and validate with numerical experiments that the notion of optimality we consider can be achieved by interpolating methods that only use the training data as input in the case of isotropic prior. Finally, we extend the notion of optimal response-linent interpolation to random features regression under linear data gentratinn model that has been previously studied in the literature.
-eppea linear achievable
Introduction
Establishing mathematical understanding for the good generalization properties of interpolating methods, i.e. methods that fit the training data perfectly, has attracted significant interest in recent years. Motivated by the quest to explain the generalization performance of neural networks which have zero training error, for example even on randomly corrupted data (Zhang et al. al,(2017), this area of research has established results for variety of models. For instance, in kernel regression, Liang and Rakhlin (2020) provide data-dependent upper bound on the generalization performance of the minimum-nore interpolator. By analyzing the upper bound, they show that small generalization emoor of the minimum-norm interpolator occurs a regime with favourable curvature of the kernel, particular decay of the eigenvalues of the kernel and data population covariance matrices and, importantly, in an overparametrized setting. In random features regression, Mei and Montanari (2019) showed that for large signal-to-noise ratio and in the limit of large overparametrization the optimal regularization is zero, i.e. the optimal ridge regressor is an interpolator. Liang and Sur (2020) characterized the precise high-dimensional asymptotic generalization of interpolating minimum- & fn-nomm classifiers and boosting algorithms which maximize the l margin. Bartlett et al. (2020) isolated a setting of benign overfitting in linear regression, dependent on notions of effective rank of the population covariance matrix, in which the minimum-nomm interpolator has small generalization error. Similarly, this regime of benign overfitting occurs with large overparametrization.
Linear models, in particular, provide a fundamental playground to understand interpolators. On the one hand, in overparametrized regimes, interpolators in linear models are to reproduce
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

stylized phenomena observed in more general models. For example, the double descent phenomenon. which was first empirically observed in neural networks (Belkin et al., 2019), has also featured in linear regression (Hastie et al.) 2019). On the other hand, neural networks are known to be well-approximated by linear models some regimes. For example, with specific initialization and sufficient overparametrizationn two-layer neural networks trained with gradient descent methods are well-approximated by a first-order Taylor expansion around their initialization (Chizat et al. 2019). This linear approximation can be split into a random features component and neural-tangent component. The random features model, a two-layer neural network with randomly initialized first layer which is fixed during training, shares similar generalization behavior with the full neural network (Bartlett et al. 2021). and as such, the random features model provides a natural stepping stone towards tackling theoretical understanding of neural networks.
major focus of the interpolation literature has so far been to theoretically study if and when interpolating methods based on classical techniques such as ridge regression and gradient descent can have optimal or near-optimal generalization (Bartlett et al.) 2021]. However the question of understanding which interpolators are best, and designing data-dependent schemes to implement them, seems to have received only partial attention. Work investigating which interpolators are optimal in linear regression includes Muthukumar et al. (2019), where the authors constructed the best-possible interpolator, i.e. a theoretical device which uses knowledge of the true parameter and training noise vector to establish fundamental limit on how well any interpolator in linear regression can generalize. When the whitened features are aub-Gaussian, this fundamental limit is lower bounded by term proportional to n/d d, up to an additive constant and with high probability, which is small only in the regime of large overparametrization. Here, n and d are the size and the dimension of the data. While this interpolator provides the hest-possible generalization error, the interpolator is not implementable in general, as one would need access to the realization of the true data-generating parameter w* and the realization of the noise in the training data. Rangamani et al. (220)) studied generalization of interpolators in linear regression and showed that the minimum-norm interpolator minimizes an upper bound on the generalization error related to stability. In (Mourtada 2020), it was shown that the minimum-nooe norm interpolator is minimax optimal over any choice of the true parameter w" E Id distributions of the noise with mean 0 and bounded variance, and for a fixed nondegenerate distribution of the features. Amari et al. (202I) computed the asymptotic risk of interpolating preconditioned gradient descent linear regression and investigated the role of its implicit bias on generalization. In particular, they identified the preconditioning which leads to optimal asymptotic (as d/n + 7 > 1 with n, d -> 0o) bias and variance, separately, among interpolators of the form w Px (XPX")) for some matrix P, where X E Rexd is the data matrix, y E R" is the response vector. They showed that, within this class of interpolators, using the inverse of the population covariance matrix of the data as preconditioning achieves optimal asymptotic variance. However, the interpolator with optimal risk is not given.
In this paper, we study the question of what is the optimal way to interpolate in overparametrized linear regression by procedures that do not use the realization of the true parameter generating the data, nor the realization of the training noise. The motivation for studying this question is twofold. First, in designing new ways to interpolate that are directly related to notions of optimality in linear models, we hope to provide a stepping stone designing new ways to interpolate in more complex models, such as neural networks. Second, our results illustrate that there can be arbitrarily large differences in the generalization performance of interpolators, in particular considering the minimum- -orm interpolator as a benchmark. This is phenomenon that does not seem to have received close attention in the literature and may spark new interest in designing interpolators connected to optimality.
We consider the family of interpolators that can be achieved as an arbitrary function f of the data, population covariance, signal-to-noiss ratio and the prior covariance such that f is linear in the response variable y (as the case for the Bayes optimal estimator in ridge regression). We call such interpolators response-linear achievable (see Definition 3). We also introduce a natural notion of optimality that assumes that the realization of true data-generating parameter and the realization of the noise in the training data are unknown. Within this class of interpolators and under this notion of optimality, we theoretically compute the optimal interpolator and show that this interpolator is achieved as the implicit bias of preconditioned gradient descent with proper initialization. We refer to this interpolator as the optimal pippons--linear achievable interpolator.
Could it be that the commonly used minimum-nowe interpolator is good enough so that the benefit of finding a better interpolator is negligible? We illustrate that the answer to this question is, in general,
2

---

no. In particular, we construct an example in linear regression where the minimum- normmumm--ommmmmm norm interpolator has arbitrarily worse generalization than the optimal response- achievable interpolator. Here, the variance (hence also generalization error) of the minimum-norm interpolator diverges to infinity as function of the eigenvalues of the population covariance matrix, while the generalization error of the optimal response-linear achievable interpolator stays bounded, close to the optimal interpolator, ie. the theoretical device of Muthukumar et al. (2019) which uses the value of the signal and noise.
The optimal response-lineal achievable interpolator uses knowledge of the population covariance matrix of the data (similarly as in Amari et al. (202T). ) the Signal-to-noiss ratio, and the covariance of the true parameter (on which we place a prior distribution). Is it the case that the better performance of our interpolator simply a consequence of this population knowledge? We provide numerical evidence that shows that the answer to this question is, in general. no. In particular, we construct an algorithm to approximate the optimal response-linear achievable interpolator which does not require any prior knowledge of the population covariance or the signal-to-noise ratio and uses only the training data X and y, and we empirically observe that this new interpolator generalizes in a nearly identical way to the optimal response-linear achievable interpolator.
Finally, we show that the concept of optimal response- linear achievable interpolation can be extended to more complex models by providing analogous results for a random features model under the same linear data- gentratnng regime as also considered in (Mei and Montanari 2019), for instance.
2 Problem setup
In this paper we investigate overparametrized linear regression. We assume there exists w e Rd (unknown) so that yi (w" 2z) + for i {I,...,ny nn., with i..d. noise & E R (unknown) such that B(G)) = 0, B(E))= = o² and i.i.d. features x; E R that follow a distribution Pa with mean E(x;) = 0 and covariance matrix B(z,z,) Σ. We store the features in random matrix X E Raxd with rows 2, E Rd, the response variable in random vector E R" with entries y; E R. and the noise in random vector & 1² with entries & R. Throughout the paper we assume that d 2 n. We consider the whitened data matrix Z XE E In whose rows satisfy E(z,2?) Ia. where la E Raxd is the identity matrix. We place a prior on the true parameter in the form w² Pw such that E(w*)= = 0 and B(w*w**) = =a Φ. Here, & is a positive definite matrix and r² is the signal. We sometimes abuse terminology and refer to & as the covariance of the prior even though r @ is the covariance matrix. Our results will be proved in general, but for the sake of exposition a
it can be assumed that H; (O, o0,,02,, and w ~N 2² @). We also define the signal-to-noise ratio 8 /0² and consider the squared error loss & : (x., y) R² + (x - y)²
Througout the paper, we assume the following two technical conditions hold.
Assumption 1. (a E = 0 for any linear subspace V of Rd with dimension smaller than d.
Assumption 2. For all Lebesgue measurable sets C R2,, ((A) > 0 implies Pwr (w- E A) > where v is the standard Lebesgue measure on Rdd
Assumption is needed only so that rank () n with probability (for proof see A.4b. A
sufficient condition is that Pz has a density on dRd A sufficient condition for Assumption 2 is that Pw. has a positive density on IRd. Now, our goal is to minimize the population risk
r(w) = F ((w .) -))²,
or, equivalently, the excess risk r(w) - r(w)). Here, (H. {) is random variable which follows the distribution of (I1, 3/1 E.)...., (zn, yn. En) and is independent from them. Throughout the paper we
write (z 2) to denote the conditional expectation E[g(2, 2)), for two random variables and and for a function g. The population risk satisfies
r( r(w) (w wn o E(w w²) + +o = wwww w w + r(w"),
(1)
where ||0l|3 = T Ew. We define the bias and variance of w E Rdd by the decomposition
E E r(w)= = B(w) + V(w),
(2)
3

---

where
(ww) = Bg B [[[[w X) - w0 ((w) = B 1|00 B(wll w., X
(3)
One of the main paradigms to minimize the (unknown) population risk is based on minimizing
the empirical risk R(w)) = - ( y1)² zi=1 f(w vi, yt) (Vapnik] 1995) In
setting, minimizing the empirical risk equivalent to finding w E R such that Xw
Interpolators
An interpolator is any minimizer of the empirical risk. Let be the set of interpolators, which in linear regression can be written as
- Rd Xw Xw=xwwp y)
As rank(XX) n with probability 1, we have G o 0 with probability 1. In linear regression, the implicit bias of gradient descent initialized at 0 the minimum-norm interpolator (Gunasekar et al., 2018). We define the minimum-norm interpolator by
WF2
arg min WER Xw=y
1 Xty,
where Xt E Rand is the Moore-Penrose pseudoinverse (Penrose 1955). As rank(X) n, we
can also write Xt X" x"xXx")= The second interpolator of interest is purely theoretical device, previously used in (Muthukumar et al. (2019) to specify a fundamental limit to how well any interpolator in linear regression can generalize.
Definition 1. The best possible interpolator defined as
W₁ arg minr(w) weg
We write
W arg min
| (w w²) >|
wER": Xw=y
and after a linear transformation and an application of result on approximate solutions to linear equations (Penrose 1956), obtain
W3 = -- = #)tE.
(4)
We notice that the best possible interpolator fits the signal perfectly by having access to the true parameter u" and fits the noise through the term Σ (XE 1ytg by having access to the noise vector & in the training data. In general, this interpolator cannot be implemented as it requires access to the unknown quantities w² and &. We are interested in interpolators which can be achieved by some algorithm using the data X and y.
Definition 2. We define an estimator w E Rdd be achievable if there exists a function f such that = [(X, (X,,,, 8).
In our definition of achievability, we allow for knowledge of the population data covariance, the signal-to-noise ratio, and the prior covariance to define fundamental limit what generalization performance can be achieved also without access to these quantities, and we later empirically show that we can successfully approach this limit using only the knowledge of the training data X and y. in considered examples (see Section 5.1 Moreover, our theory is also useful in situations when one has access to some prior information about the regression problem which they can incorporate into an estimate of Σ, 8, & (for example, one may know the components of diagonal) and hence it is relevant to consider broader class than w = f(X,y).
independent and hence
Definition 3. We define the set of response-linear achievable estimators by
L = { w E Rd 3f such that f(X, E, 2, where y E R f(X, Σ, D. 8) is linear }.

---

Linearity of y E R" + J. E, any function which has image Rdxx. The notion of optimality that we introduce is that of the optimal response-linear achievable interpolator, which is the interpolator that minimizes the expected risk in the class L.
is equivalent to = 9, 8,8,, where
Definition 4. We define the optimal response-lineat achievable interpolator by
wo arg min B w. r(w) rr(w(w wEgnL
(5)
4 Main results
By definition, the interpolator wo has the smallest expected risk among all response- linear achievable interpolators. Our first contribution the calculation of its exact form.
Proposition 1. The optimal response-linear achievable interpolator satisfies
nn = x (xx- (T, 8 -1 ( y-
(6)
For an isotropic prior Ld, wo depends only on the population covariance E and the signal-to- noise ratio ó so that wo can be approximated using estimators of these quantities, which is what we do in Sections 5 and A.8] Even if + * Ta. one might have some information about the prior covariance, which can be incorporated into an estimate @ and used instead of + However, even no such estimate is available, in Section A.9 we empirically show that, in our examples, using क = Ta when & * Ta has small effect on generalization.
Secondly, using results of Gunasekar et al. (2018) on the implicit bias of converging mirror descent, we show that the optimal response-linear interpolator is the limit of gradient descent preconditioned by the inverse the population covariance, provided that it converges and is suitably initialized.
Proposition 2. The optimal response-linest achievable interpolator is the limit of preconditioned gradient descent
Wt-1 wt E "VE''))(w)), provided that the algorithm converges, initialized
5 xxxT (T+ 6 -1 Wo d
xxxxx
y.
(8)
The interpolator wo does not have the smallest bias the smallest variance in the variance decomposition Eg..- r(w) B(w)= + V(w), but rather achieves a balance. This is related to the results of (Amari et al. 202I). Their setting looks interpolators achieved the limit of preconditioned gradient descent in linear regression (preconditioned with some matrix P) and For these interpolators, they compute the risk of w, separate the risk into a variance and a bias term and using random matrix theory they find what the variance and bias terms converge to when d - oo, such that d/n + 7 >> 1. For these calculations to hold, they assume that the spectral distribution of (Eg)des converges weakly obtaining the limiting variance and bias, they prove which matrices P minimize these limits separately (not their sum, which is the overall asymptotic risk).
initialized at 0. Such interpolators can be written w PX (
in way
distribution supported on (c, CJ for some c, C > Then, after
We approach the problem from the other direction. That is, we do not a priori consider interpolators that can be achieved as limits of specific algorithms, but directly look at which interpolator minimizes the risk as a whole (not bias and variance separately). Only after computing the optimal response-lines -inear interpolator, preconditioned gradient descent, however with a specific initialization. Our results hold for every finite d 2 n and we do not put assumptions on the eigenvalues or the spectral distribution of Σ.
show in Proposition 2 that the interpolator is in fact the limit of
In particular, we can recover the results of (Amari et al., (02T) as a special case of Proposition | obtain the matrix P
we take the signal-to-noise ratio d + 0 (by taking nd + 0) in Proposition
5

---

which achieves optimal variance and if we take ò + oc (by taking o² - 0), we obtain the matrix P which achieves optimal bias. Moreover, we provide further extension Proposition
We show that the preconditioned gradient descent W++1 = W/ 7/p - R(w)) achieves optimal variance among all interpolators when initialized at any deterministic wo and for any finite d, n E N.
Proposition 3. The limit of preconditioned gradient descent W w. T - (V((s) initialized at a deterministic wi E Rdd, provided that it converges, satisfies
lim we arg min V(w).
WEg
We note that the optimal variance is achieved among all interpolators, not only among response-lines achievable interpolators.
natural question ask is whether the optimal response-lineat achievable interpolator wo provides a significant benefit compared to other interpolators. A second question is whether we can successfully approximate the optimal response- -inear achievable interpolator without knowledge of the population covariance Σ and the signal-to-nois ratio ó. In the following section, we illustrate that both the interpolator with optimal variance and the interpolator with optimal bias can generalize arbitrarily badly in comparison to as function of the eigenvalues of the population covariance. In the same regimes where this happens, we present numerical evidence that we can successfully approximate wo by an empirical interpolator woe without any prior knowledge of Σ or ó by using the Graphical Lasso estimator (Friedman et al. 2007) of the covariance matrix Σ and choosing the empirical estimate of by crossvalidation subset of the data.
5 Comparison of interpolators
First, we present example where the minimum- norm interpolator Wy, generalizes arbitrarily worse than the best response-linear achievable interpolator wo. Second, we give an example where an interpolator with optimal variance generalizes arbitrarily worse than wo- This shows that arbitrarily large differences in test error are possible within the class of estimators with zero training error.
In the examples, we consider a setting where I; ~ _N, and wn ~ NNO, =) Therefore, throughout Section we assume Pa = (0, M) and P = No D). Before presenting these examples, we discuss approximating wo by an interpolator, woe. which uses only the data X and y.
5.1 Empirical approximation
The interpolator wo is the limit of the algorithm
W = w. T3. V H((w).
(10)
The population covariance Σ is required to run this algorithm. However, the matrix Σ is usually unknown in practice. One may want estimate Σ. However, if one replaces E by Σ X//++AAL (with À 2 0), then the limit of (10) is the same as the limit of gradient descent (provided that both algorithms converge). This is because, using the singular value decomposition of X, one show
- b) =
The preconditioned gradient update Wt+1 wi
R(w:) has to not belong to Im(X") ) in order to not converge to the minimum-norm interpolator: Hence, using p = Σ XTX/n Xa (for example, also the Ledoit Wolf shrinkage approximation (Ledoit and Wolf 2004)) in preconditioned gradient descent removes the benefit of preconditioning in terms of generalization of the limit.
We use the Graphical Lasso approximation (Friedman al. 2007). We empirically observe that in the examples considered in this paper (Figures 1
5 6 using the Graphical Lasso covariance
Σg instead of Σ has nearly no effect on generalization. Under specific assumptions, Ravikumar et al.) (2011) provide some convergence guarantees of the Graphical Lasso.
In regards to approximating the signal-to-noise ratio we choose 6, that minimizes the crossvalidated error on random subsets of the data. In this way, we arrive at the interpolator
6 XT Iz (xXx-)))
5e In+
Wo
XXX) V. d
(11)

---

which approximates wo and is function of only X and We note that the interpolator woe uses Ia place of the prior covariance matrix.
In the experiments (Figures 2 4 60 we used the Graphical I Lasso implementation of scikit- 0.25 (a: also be crossvalidated for even better performance) and in estimating ö, for each de in {0.1, 0.2,.... ,,...,,,, 1,.,,,,,2 2,2,... 10), we computed the validation error on a random, unseen tenth of the data and averaged over 10 times. The de with smallest crossvalidated error was chosen.
learn (Pedregosa et al., 2011) with parameter
5.2 Random matrix theory concepts
For presenting the discussed examples need to review concepts from random matrix theory.
Definition 5. For a symmetric matrix E Raxd with eigenvalues 2 A2 2 Aa 2
we
define its spectral distribution by F2(x) = E 1 (z).
The following assumptions will be occasionally considered for the covariance matrix E.
Assumption 3. There exists kmax > 0 such that Amax (E) S kimax uniformly for E N. Assumption 4. There exists Kmin such that kmin I Amin (X)) uniformly for E N. Assumption 5. The spectral distribution Fy: of the covariance matrix E converges weakly distribution H supported on [0, oc).
Marčenko and Pastur 1967) showed that there exists distribution F,, such that F ZTZ
F y,
weakly, with probability as n + 0o, d + oo with d/n - 7. our discussion, T, = Σ 2i where >0,N(0, Ia) independently. Then, under Assumption 5 can be shown that the spectral distribution of E X/n ف z 2 /'n converges weakly, with probability 1 distribution supported on [0, 2o), which we denote by F,, see e.g. (Silverstein and Choi 1995). Similar arguments also show that the spectral distribution of XX4 /n E lgax converges weakly, with probability 1.
Definition 6. For a distribution F supported on [0, oo), we define the Stieltjes transform of F, for any z C IR+ by
1 ( _F(().
m==()==]
A-
The weak convergence of the spectral distribution of E to F, is equivalent to mg(=) m(2) and mxx7/n (=) + v(2) almost surely for all C R+, where m and are the Stieltjes transforms of F, and the limiting spectral distribution of XXT /n, respectively (see e.g. Proposition 2.2 of (Hachem et al. 2007)). We call the companion Stieltjes transform of Fy.
5.3 Diverging variance of interpolator with optimal bias
Using we 0 in Proposition 3 WV = 2
choose the interpolator with optimal variance be (see A.3)
(12)
When + la. the interpolator with best bias among response-lineal achievable interpolators the minimum-norm interpolator (see Section A.5). We identify an example where the minimum-nowe interpolator we, generalizes arbitrarily worse than the best response-linear achievable interpolator wo. For this, exploit results of Hastie al. (2019) computing the asymptotic risk of the minimum-noo interpolator. They show that if Ta under Assumptions
and if 7
with n + xc, + oo then with probability 1.
2
d'())
w. r(we)) - r(w") (0) + +
v002 -1)
(13)
where e is the companion Stieltjes transform introduced in Section 5.2 comparison, similarly as in (Amari et al. 202I), the asymptotic risk of the best variance estimator wy satisfies that under
7

---

Assumption
and 5 if n, d + do with d - 7 > then with probability 1 we have that
lim Eew r(wv) - r(ww)) ,22 d
/ s dHH(s)
o²
(14)
7
An alternative way to write - d lima-aco Tr(E). This result follows by an application of Theorem I of (Rubio and Mestre 2011 which is in the supplementary material for completeness.
Now we find a regime of covariance matrices Σ. for which the variance term of the minimum- norm solution, Vi2- = o² " - 1), diverges to infinity, while the risk of wo stays bounded and close to optimal. For this, we consider generalization of the spike model of covariance matrices (Baik and Silverstein 2006 Johnstone 2001), which fundamental model in statistics. Here E diag(Pi..... PI P2: ..... (2) E _ax where the number of P1s is d 1/1 with d [0, 1]. This model was also considered in (Richards et al. 2021) where it is called the strong weak features model. In this regime, it is possible to explicitly calculate the companion Stieltjes transform v(0) and v v0))) of 13
the case that 7 = 2/ = 1/2 we have
(0) Vi, = 000) -1 1)
a²
PI
P2
+2
(15)
2
we fix #1 = 1 and take 02 + O, then the variance term Vr, diverges to infinity. This also means that the asymptotic risk of the minimum -orm interpolator diverges to infinity, Moreover, the asymptotic risk wy in [14 evaluates to
lim (..wr((v)) - r(w"((==)) ) 4//p1 + -b1))22 (1 -1- d000
o²
(16)
In addition, by construction of wo, we know that (g..)((wo) I Es (ww) ) and therefore the asymptotic limit of rwwo) - r(w"), as d/n + > 1, stays bounded by (16) p2 + 0. The expected generalization error in the setting described above is illustrated Figure
Comparison interpolators
Comparison interpolators
My
MD
No
Risk
Rick
20
80
100
20
40
60
100
Pulps
01/Oz
Figure 1: Plot of (g((w) (points) for w E Figure 2: Plot of Eg((w) (points) for w E {wez, WV, wo, Wos, Wb} along with predictions (crosses) from (14) and (13) in the strong weak
{wez wy, wo, WDe, w/) along with predictions (crosses) from (14) and (13) in the strong weak
features model with 2 1 1,7 2, 1/1
features model with x2 I, =, 1,7 1/1
1/2, = 3000 and P1 = 1, P2 +.
1/2, 3000 and P2 = 1, P1 20.
We note that the empirical estimator whe (yellow points), which is a function only the training data X and y and does not the population covariance Σ the signal-to-noise ratio 8, performs almost identically to the optimal response-lings linear achievable interpolator wh (cyan points).
In this example, we chose for arbitrary choice of y and wh. However, for any 7 such that 74/1 = 1, the phenomenon of Figure hholds (see A.7 of the supplementary material).
2 and 1i 1/2 deliberately. One does not achieve diverging variance

---

5.4 Diverging bias of interpolator with optimal variance
Now, we illustrate a regime where the best variance interpolator wy generalizes arbitrarily worse than wo. In the same strong and weak features covariance model described above in Section 5.3 when y and 1 1/2, if we instead have P1 - oo and P2 1, then the asymptotic risk (16) diverges to infinity linearly. However, the variance of the minimum-norm interpolator in (15) diverges only like /p1- Moreover, the bias term satisfies
x2
Ba
? VPIP2,
y0(0)
which also diverges like /pi. Now, because ((w-))(wo) S ((.e)) we have that
,² lim (gw)) S + 2
a²
>\P22VVr (v++V+++)) +3).
(
P1
P2
31
d+000
P2
so that the asymptotic risk wo diverges to infinity as /PI. We illustrate this Figure
We notice that the empirical approximation woe again performs in a nearly identical way to the optimal response- linear achievable interpolator wo. Moreover, importantly, we note that wy and Σ V R(ww), only with different initialization.
wo are limits of the same algorithm, W(+1 = Hence, this shows that different initialization of the same optimization algorithm can have an arbitrarily large influence generalization through implicit bias.
6 Random features regression
The concept of optimal interpolation a function which linear in the response variable, is general and can be extended beyond linear models. We present an extension of Proposition to the setting of random features regression. Random features models were introduced kernel methods (Rahimi and Recht 2008) and can be viewed as a two-layer neural network with first layer randomly initialized and fixed as far training is concerned. They can be shown approximate neural networks in certain regimes of training and initialization and hence are often considered in the literature as first step to address neural networks (e.g. (Jacot al. 2018)) p). We consider data generated in the same way as before, network fa TR 3 x + a" a(Ox/ dd), where the first layer @ E TR- Nd is randomly initialized. This setting, along with z; and rows of O belonging to the sphere gd-1 ( /d) with radius vdd in Rd is often considered in the literature on interpolation of random features models (Mei and Montanari] [019)] Ghorbani al. 202T). If analogously define the optimal response- -ineer achievable interpolator in random features regression by
random approximation to
(z,, w²) + E, and the model to be a two-layer neural
a0 = arg min (g. - r(w"), eEGNL
(17)
where here G {a N Za = y} is the set of interpolators, oXX6" /Va) and L is the same as in Definition 3
then the following analogue of Proposition [ holds.
Proposition 4. The optimal response-linear achievable interpolator satisfies
17 in random features regression
- -1 d ( +XXX In - E. Ex.) 7 (" 10= TXT +
( (o y,
and E. = (o (08V/V))) are covariance and cross- covariance matrices, respectively. This interpolator be again obtained as the implicit bias of preconditioned gradient descent using results of Gunasekar et al. (2018).
Here Σg = Ea
Proposition 5. The optimal response- linear achievable interpolator (17 in random features regression is the limit of preconditioned gradient descent on the last layer.
Wi+11 W/ E, V VV(Ww)
provided that the algorithm converges, initialized at
ao = - Den xxT ">'
J + xxxx) y.

---

In Section A.12 we illustrate the test error of fa, with a = do in comparison to the test eтror for the minimum-nom interpolator ag, Z' on a standard example.
7 Conclusion
In this paper, we investigated how to design interpolators in linear regression which have optimal gen- eralization performance. We designed interpolator which has optimal risk among interpolators that are a function of the training data, population covariance, signal-to-noise ratio and prior covariance, but does not depend on the true parameter or the noise, where this function is linear in the response variable, We showed that this interpolator is the implicit bias of a covariance-based preconditioned gradient descent algorithm. We identified regimes where other interpolators of interest are arbitrarily worse using computations of their asymptotic risk as d ? 1 with d, +
In particular, we found regime where the variance term of the minimum- norm interpolator is arbitrarily large compared to our interpolator. This confirms the phenomenon that implicit bias has an important influence on generalization through the choice optimization algorithm.
We identified a second regime where the interpolator that has best variance is arbitrarily worse than interpolator. In this second example, both interpolators are the implicit bias of the same algorithm, but with different initialization. This contributes to illustrating that initialization has an important influence on generalization.
We also considered an empirical approximation of the optimal response- achievable interpolator, which uses only the training data X and y and does not assume knowledge of the population covariance matrix, the signal-to-noise ratio or the prior covariance and empirically observe that generalizes in nearly identical way to the optimal response- lineer achievable interpolator in the examples that we consider.
A limitation of this work includes a precise guarantee on the approximation error of the Graphical Lasso for a general covariance matrix E. Some guarantees are (Ravikumar et al. 2011). however establishing guarantees for general covariance matrix would be contribution on its
natural question for future research, which also motivated our work, is how systematically design new ways of interpolation, which are adapted to the distribution of the data and related to notions of optimality, for more complex overparametrized machine learning models such as neural networks.
8 Acknowledgements
The authors would like to thank Dominic Richards, Edgar Dobriban and the anonymous reviewers for valuable insights which contributed to the technical quality of the paper. Eduard Oravkin was part-time employed at the Department of Statistics during a part of this project. Patrick Rebeschini was supported in part by the Alan Turing Institute under the EPSRC grant EP/N510129/1.
References
S. Amari, J. Ba, R. B. Grosse, X. Li, A. Nitanda, T. Suzuki, D. Wu, and Xu. When does precon- ditioning help or hurt generalization? International Conference on Learning Representations, 2021.
Z. Bai and Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer Series in Statisties. Springer New York, 01 2010.
Z. D. Bai and Y. Q. Yin. Limit of the smallest eigenvalue of a large dimensional sample covariance matrix. The Annals of Probability, 21(3): 1294, 07 1993.
J. Baik and J. W. Silverstein. Eigenvalues of large sample covariance matrices of spiked population models. Journal of Multivariate Analysis, 97(6): 1408, 2006.
Bartlett, P. Long, G. Lugosi, and A. Tsigler. Benign overfitting linear regression. Proceedings of the National Academy of Sciences. 117333):0003--0007, 2020.
10

---

P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: statistical viewpoint, 2021. arXiv preprint arXiv:2103.0917.
M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15854, 2019.
L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
E. Dobriban and S. Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-215 2799, 07 2015.
Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432 441, 12 2007.
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2): 1054, 2021.
S. Gunasekar, J. Lee, D. Soudry, and N. Srebro. Characterizing implicit bias in terms of optimization geometry. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 1832-1841, 2018.
W. Hachem, P. Loubaton, and J. Najim. Deterministic equivalents for certain functionals of large random matrices. Ann. Appl. Probab., 17(3):875-933) 06 2007.
T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation, 2019. arXiv preprint
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
I. M. Johnstone. On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist., 29(2):295-327, 04 2001.
O. Ledoit and M. Wolf. well-conditioned estimator for large-dimensional covariance matrices. Journal of Multivariate Analysis, 88(2):365-411, 2004.
Liang and A. Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. Ann. Statist.,
4299):1329-1347, 06 2020.
T. Liang and P. Sur. A precise high-dimensional asymptotic theory for boosting and minimum-61- norm interpolated classifiers, 2020. arXiv preprint arXiv:2002.01586.
V. Marčenko and L. Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik, 1:457-483, 01 1967.
Mei and A. Montanari. The generalization emror of random features regression: Precise asymptotics and double descent curve, 2019, arXiv preprint
J. Mourtada. Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices, 2020, arXiv preprint
V. Muthukumar, K. Vodrahalli, and A. Sahai. Harmless interpolation of noisy data in regression. 2019 IEEE International Symposium on Information Theory, pages 2299-2303, 2019.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
R. Penrose.
generalized inverse for matrices. Mathematical Proceedings of the Cambridge Philosophical Society, 51(3):406-413 1955.

---

R. Penrose. On best upproximate solutions of linear matrix equations. Mathematical Proceedings of the Cambridge Philosophical Society, 52(1):17-19, 1956.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems. Curran Associates, Inc., 2008.
A. Rangamani, L. Rosasco, and T. Poggio. For interpolating kernel machines, minimizing the norm of the erm solution minimizes stability, 2020. arXiv preprint arXiv:2006. 15522.
Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation by minimizing & -e-enaliieed log-determinant divergence. Electronic Journal of Statistics, 5:935 980, 2011.
D. Richards. J. Mourtada, and L. Rosasco. Asymptotics of ridge(less) regression under general source condition. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 3889-3897, 13-15 Apr 2021.
F. Rubio and X. Mestre. Spectral convergence for general class of random matrices. Statistics & Probability Letters, 81(5):592 602, 2011.
Silverstein. Strong convergence of the empirical distribution of eigenvalues of large dimensional
random matrices. Journal of Multivariate Analysis, 55(2):331-33) 1995.
Silverstein and S. Choi. Analysis of the limiting spectral distribution of large dimensional random matrices. Journal of Multivariate Analysis, 54(2):295 - 309, 1995.
N. Vapnik. The Nature of Statistical Learning Theory. Peringer-Verlang Berlin, 1995.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, 2017.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] These are in the conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] They are in the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] The code is in the supplementary material. The data generating process described in Section The parameters used in Figures I and 2 are in the captions and the definitions of the interpolators used in the figures are the text. The method of obtaining the empirically approximated interpolator is in [..]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] The parameters used in Figures [nd details of the datasplit and crossvalidation scheme the method of obtaining the empirically approximated interpolator is in the last paragraph 5.
Zare are in the captions. The and 2
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used? [Yes] We used the compute-optimized c2-standard-8 with 8 CPUs and 32GB RAM Google Cloud to obtain the figures.
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "OLCgEmfSiAw", "reviewer": "Reviewer_raJt", "summary": "This paper considers the problem of optimal interpolation in linear regression. It defines the class of response-linear achievable interpolators, and provides a closed-form expression for the optimal interpolator in this class. The paper is about an important topic in machine learning and statistics. However, it is unclear to me whether the \"achievable\" interpolators are really achievable, and as a result if the investigation is meaningful.", "questions": "", "limitations": "", "rating": 4, "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": "Major comments and questions:\n1. The paper claims that the realization of true data-generating parameter and the realization of the noise in the training data are unknown. However, it assumes that the population covariance, the signal-to-noise ratio, and the covariance of the prior for the signal are known. The latter seems to be more unrealistic. For high dimensional data, the covariance matrix contains much more number of parameters than the regression coefficient so it is a much harder problem to estimate the covariance matrix. In a Bayesian setting, the primary goal is to find the distribution of the parameter. If the distribution of the parameter is assumed to be known, then there is no estimation problem.\n\n2. For $\\Phi$, do you mean it is the correlation matrix? Otherwise calling $r^2$ the signal is not appropriate. \n   \n3. The population risk between lines 125 and 126 is not clear.It is written as the conditional expectation given $X, \\xi, w^*$, but this does not make sense. A risk should not be random.\n\n4. I think the $y$ in line 131 should be $y_i$, but what is the $y$ in line 132? The $y$ in line 117 should be $y_i$? How about the $y$ in lines 120 and 124? Each of these may be typos or poor notations, but when there are too many this type of problems and makes it hard to following the paper it becomes a major issue. \n   \n5. Line 142, I believe you need $\\gamma\\ge1$.\n\n6. Line 156 says \"rank(X) = n with probability 1\" while this becomes a condition in line 160.\n\n7. Definition 4, do you mean there exists a known function? Otherwise, the function $f$ may depends further on other unknowns.\n\n8. As in my first point, the $w_O$ is not realistic. The updating formula in (7) requires the inverse of $\\Sigma$ which is almost impossible for high dimensional data. \n\n9. I don't think Hastie et al. (2019) considered the case of $\\Phi=I_d$. It is probably a typo here.\n   \n\nMinor issues and typos:\n\nLine 53, \"are best\" to \"are the best\".\n\nIn (5), use paratheses to make the definition clear.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "about four hours"}, "extra_text": {}}, {"review_id": "G8naOY1q-61", "reviewer": "Reviewer_JMam", "summary": "This paper studies the generalization error of a class of interpolator in linear regression and identifies conditions for optimality. They consider a setting where there is a true linear model generating the data, whose parameters are drawn from a Gaussian distribution with zero-mean and covariance Phi. In this setting they consider a natural class of estimators that are a function of the data, the population covariance matrix, the prior covariance matrix Phi and the signal to noise ratio. Among this class of estimators they calculate a closed-form expression for the optimal interpolator, with respect to the expected excess risk and show that there are certain settings where the expected excess risk of this estimator can be much lower than the risk of the OLS solution. They also provide an extension of their results to the random features model.", "questions": "", "limitations": "", "rating": 7, "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": "The authors study an interesting problem on a topic of much recent interest---benign overfitting of linear models. While the assumptions made on the problem are pretty stringent, the authors provide a clean exposition of their results which I appreciated as a reader. \n\nHere are some questions/comments about the paper:\n\n1. The authors mention the results by Amari et al. (2021), who they mentioned studied estimators whose asymptotic bias or variance is optimal. How do the techniques and setting used in this paper differ from theirs? Can the techniques used there also be used here but instead to balance the bias and the variance optimally? A discussion regarding this would be helpful to the reader. \n\n2. On ln 91 the authors say an interesting question that they study here is if minimum norm interpolant is always close to optimal, and show that this is not the case. But I think this question has already partially been answered given past work of Bartlett et al. (2020). Given their results, it is easy to construct cases, for example, when population covariance matrix is isotropic, where the minimum norm interpolant is not consistent but the ridge regression solution is. So, I would urge the authors to provide some more nuanced context and discussion here.\n\n3. Regarding the assumptions both the noise xi and the true parameter w* are assumed to be drawn from a Gaussian distribution. Can this be relaxed? Further, can the results of this paper (Proposition 1 in particular) be extended to hold in the case where w* is not mean zero?\n\n4. In the experiments described in Section 4.1, where w_O is approximated by w_{O_e}, what is the structure of the population covariance matrix? Is it isotropic or close to it? Or does it have a heavy tailed structure similar to one that was shown to be necessary by Bartlett et al. for the minimum norm solution to be consistent? Further, empirically, was the estimate Sigma_e close to Sigma? A plot to verify this would be nice.\n\n\n=================== Post rebuttal comments =================== \n\nFirstly, I would like to thank the authors for their very carefully response to the questions raised by all of the reviewers. I continue to support acceptance of this paper post the rebuttal period. In my view, I think it would be nice if the authors incorporate the many helpful suggestions raised in all of the reviews in a subsequent version.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do a good job of describing the potential negative impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "AtUlOFZn4ul", "reviewer": "Reviewer_472b", "summary": "This paper is concerned with inducing a certain type of best possible interpolator in linear regression. It is based on the notion of best possible interpolator, defined in Muthukumar et al., 2019., which is the best estimator (i.e., with minimum risk) among the class of interpolators. Based on that, the authors define a new theoretical estimator, the best estimator among interpolators that are also linear in the response variable.  They manage to induce a closed form of this estimator and prove that it is the limit of preconditional gradient descent under a specific initialization. In addition, using approximations for quantities that are usually unknown in practice (e.g.  population covariance matrix, signal to noise ratio), they turn this theoretical estimator into a fully empirical one and compare its performance to other frequently used estimators, showing that this estimator performs arbitrarily better in certain cases. Finally, they extend this notion of best possible theoretical estimator to the random features setting, where they again induce a closed form for this estimator and prove that it is the limit of preconditioned gradient descent under a specific initialization.\n", "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": "The paper is interesting to read. It belongs to the long list of papers that are concerned with the overparametrized estimation, but instead of trying to explain why this type of estimation generalizes so well, it aims to find the best linear interpolator in the linear regression setting. By restricting the class of possible estimators in the definition by Muthukumar et al., 2019, they manage to turn a theoretical device into a fully observable estimator. They also define a similar notion of optimal estimator for a more complex model and induce a closed form of this estimator, something that may suggests that we could try to induce this type of optimal estimators for even more complex model like neural networks. There is also an interesting example, where we can see that a frequently used interpolator, the minimum-norm interpolator, has arbitrarily bad generalization. Finally, these examples combined with the results related to preconditional gradient descent highlight nicely the importance of initialization.\n\nThe paper could be of greater significance if\na) the construction of the fully-empirical estimator would not be restricted to the isotropic regime\nb) (as they note) it included a precise guarantee on the approximation error of the estimation of the covariance matrix Σ\nc) instead of performing an empirical analysis for special cases, they could manage to prove a theoretical result that bounds the generalization error of the fully-empirical estimator w.r.t. the generalization error of the theoretical optimal response-linear achievable interpolator.\n\nIn addition, I think that some points in the beginning of the proof of Proposition 1 could be written with more clarity.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In line:\n-64  I don't think that Mourtada deals with interpolators in this paper.\n-129 A comment regarding the subscript in the expectation may add some more clarity, as some times this means expected value given this quantity, or expected value given everything else other than this quantity\n- 132 \"In linear regression (when d>n), minimizing the...\"\n-480  Maybe you could start with a general W that belongs in this class instead of Wo, as equation (17) seems a bit strange.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "36Or6mpDu3L", "reviewer": "Reviewer_hWGm", "summary": "The paper under reviews studies the problem of optimal linear interpolation. More precisely the authors derive an explicit formula for the *best* linear interpolator that can be written as a linear function of the outputs and as a function of desired quantities. From this, they show how to recover theoretically this estimator from a optimization algorithm. Finally they expose cases where the designed estimator show some good generalization properties while the miminum norm interpolator does not.  The link with kernel methods is also made.", "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": "**Overall comments and impression**\n\nFirst, I would like to say that I am not an expert in statistical learning theory, so that I may have missed some insights in the results.\n\nTo begin, I would like to say that the paper is perfectly well written: the story is very clear and the mathematical writing is precise and fluid. This made the reading very pleasant and I would like to thank the authors for that.\n\nThe aim of the author is clear: provide an (under certain constraints) optimal linear predictor that may perform better than the minimum norm one naturally considered in the literature (naturally coming from GD or SGD on the empirical risk). The authors do so quite effortlessly ad give, to my opinion a nice result for those asking whether minimum norm solutions are always good estimators. **Yet**, I would have liked a lot more comments on the shape of this estimator: what intuition should the reader build when reading the paper ? A clear weakness is that the authors never really take the time of analysing why makes the estimator optimal (beyond technical considerations). In the very same manner, Proposition 2 gives that the optimal linear response is in fact the solution recovered by GD with a certain initialization: could the authors comment a bit on this ? \n\nThe result on the divergence of the minimum norm linear interpolator (whereas the optimal one does not) is nice: however I would really need to understand further *why* and *when* we should expect this to happen. And in general cases *how close* should I expect the minimum norm interpolator to be close to the optimal one ? \n\n\n**Minor comments:**\n\n- I guess that the part on the random matrix concepts arrive too early. As far as I understood, there is absolutely no need to put this part at the beginning, and this could be postpone in section 4.2 or even in the Appendix. \n\n- The part on random features model gives nothing new to the results: they are not commented (at all) and are absolutely expected once the linear model is covered. If these results are not further commented, then I recommend to put it in the Appendix as they do not give any additional insight on the paper. A nice introduction on why linear model are trendy is enough in my opinion (NTK, random features...)\n\n- In Section 4.2, is this possible to derive a close form for the asymptotic risk of the optimal interpolator ? If not, why is this complicated ?\n\n- Give more motivation and justification for the form of the *optimal linear interpolating estimator* you build. Why are you okay with the dependance on \\Sigma, \\phi, \\delta. How could relax these ? I understand that these parameter will be estimated on the fly later: but once again, the comments on this are not deep precise enough to convince me. In particular there are only a few comments on the Graphiical Lasso approximation and why this is a good idea to approximate the population covariance.\n\n- Plots commenting Proposition 2 would rely complement the result! If not, it seems not so important: a comparison with GD without preconditionning would be welcomed.\n\n\n**Conclusion**\n\nEven if I really enjoyed reading the paper, my opinion is that, under this form, the results lack from commentaries, intuition, insights and a bit of further developments.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a good paper and I recommend to accept it. There are plenty of points in the reviews that suggest ways to improve the paper and I recommend that the authors follow up on these.
Decision: Accept (Poster)