A Generalized Weighted Optimization Method for Computational Learning and Inversion
Authors: Kui Ren
Yunan Yang
Björn Engquist
Venue: ICLR 2022 Poster (2022)
Keywords: weighted optimization
generalization error
feature regression
machine learning

Abstract: The generalization capacity of various machine learning models exhibits different phenomena in the under- and over-parameterized regimes. In this paper, we focus on regression models such as feature regression and kernel regression and analyze a generalized weighted least-squares optimization method for computational learning and inversion with noisy data. The highlight of the proposed framework is that we allow weighting in both the parameter space and the data space. The weighting scheme encodes both a priori knowledge on the object to be learned and a strategy to weight the contribution of different data points in the loss function. Here, we characterize the impact of the weighting scheme on the generalization error of the learning method, where we derive explicit generalization errors for the random Fourier feature model in both the under- and over-parameterized regimes. For more general feature maps, error bounds are provided based on the singular values of the feature matrix. We demonstrate that appropriate weighting from prior knowledge can improve the generalization capability of the learned model.

Published as a conference paper at ICLR 2022
A GENERALIZED WEIGHTED OPTIMIZATION METHOD FOR COMPUTATIONAL LEARNING AND INVERSION
Björn Engquist
Kui Ren
Yunan Yang
The University of Texas at Austin
Columbia University
ETH Zürich Zürich, Switzerland
Austin, TX 78712, USA
New York, NY 10027, USA
engquist@odens oden... utexas. edu
1o20020columbee .dd
yyn0 40000mmaamm i com
ABSTRACT
The generalization capacity of various machine learning models exhibits different phenomena in the under- and ever-parameterized regimes. In this paper, we focus on regression models such as feature regression and kernel regression and ana- lyze a generalized weighted least-squares optimization method for computational learning and inversion with noisy data. The highlight of the proposed framework is that we allow weighting in both the parameter space and the data space. The weighting scheme encodes both a priori knowledge on the object to be learned and strategy to weight the contribution of different data points in the loss function. Here, we characterize the impact of the weighting scheme on the generalization error of the learning method, where we derive explicit generalization errors for the random Fourier feature model in both the under- and over parameterized regimes. For more general feature maps, error bounds are provided based on the singular values of the feature matrix. We demonstrate that appropriate weighting from prior knowledge can improve the generalization capability of the learned model.
INTRODUCTION
Given data pairs (æy, M3 J 1-1 where F. E R. y, E -, N, we are interested in learning random Fourier feature (RFF) model (Rahimi & Recht 2008 Liao al. 2020 Xie et al. 2020
P-1
fe(x)=
Σ Oke
[0, 2x].
where P N is given positive integer and used the short-hand notation 0 = (0o. (p..)) with the superscript denoting the transpose operation.
This exact model well as its generalization more complicated setups have been extensively studied; see for instance Liao & Couillet (2018); (Shahrampour & Kolouri (2019): d' Ascoli et al. (2020): Li et al. 22020); Ozcelikkale (2020) Liu et al. (2020) (021) and references therein. While this model may seem to be overly simplified from a practical perspective for many real-world appli- cations, serves prototype for theoretical understandings of different phenomena in machine
learning models (Sriperumbudur & Szabo 2015 Belkin et al. 2020 Li et al. 2021a).
common way computationally solve this learning problem is reformulate it an optimization problem where we find 0 by minimizing the model and data mismatch for given dataset. In this paper, we assume that the training data are collected on a uniform grid of x over the domain [0, 2m). That is, (z, x -
Let wN = exp( 2xll where the imaginary unit. We introduce V E NxP to be the feature matrix with elements
(V) (w 0 S < N 1, 0
Based on the form of (x) in ( we can then write the 2-norm based data mismatch into the form Σn= [fo(r)) yı v y where the column data vector y (yo, y²-1) The learning problem is therefore recast least-squares optimization problem of the form
= arg min 1/ y1
(2)

---

Published as a conference paper at ICLR 2022
assuming that minimizer does exist, especially when we restrict @ to an appropriate space.
P-1 is then replaced with a dif- In a general feature regression problem, the Fourier feature {e T==U
ferent feature model (pp(2)) k= while the least-squares form remains unchanged except that the entries of the matrix 1/ is now Vzk= (xy))) We emphasize that this type of generalization will remark that this least-squares optimization formulation is a classical computational inversion tool in solving the general linear inverse problems of the form 0 y; see for instance Engl al. (1996): Tarantola (2055) and references therein.
be discussed in Section 5 Moreover,
Previous work on weighted optimization for feature and kernel learning, Xie et al. (2020) stud- ied the fitting problem for this model under the assumption that the coefficient vector 0 sampled from a distribution with the property that y is positive constant,
Eg 0 0, Eo[00'] - (p
where the superscript denotes the Hermitian transpose and the diagonal matrix App has diagonal elements (A(r))a t2 1 + k, A 2 0. That is,
APp diag(tu, t1, f22 .... th. tp-1h, t::= k.
(4)
The subscript [P] indicates that A(P] is diagonal submatrix of A that contains its element indexed in the set [P] := {0, 1, P 1). The normalization constant c 1/(E (1 + k) -2)) is only selected so that Ea[100] = 1. It does not play a significant role in the rest of the paper.
The main assumption in (3) says that statistically, the signal be recovered has algebraically decay-
ing Fourier coefficients. This is simply saying that the target function we are learning is relatively smooth, which certainly the case for many functions as physical models in practical applications.
It was shown in Xie et al. (2020) that, to learn model with p I P features, it is advantageous to use the following weighted least-squares formulation
0
A 3 A 0 W with w arg ming || [N
y 1
(5)
(p)
when the learning problem is overparamettrrize, i.e., p > N. Here, V Vi E C is the matrix containing the first columns of V, and 3 > 0 is some pre-selected exponent that can be different from the y in (3) To be more precise, we define the the generalization error of the learning problem
Ep(P,p,N) Eo [llfo(z) - fo, (x) (1) Eo [10 01
where the equality comes from the Parseval's identity, and 0, is understood the vector (0) 0,..,000000) so that 0 and O, are of the same length P. The subscript in Eg indicates that the expectation is taken with respect to the distribution of the random variable 0. It was shown in Xie et al. (020)) that the lowest generalization error achieved from the weighted least-squares approach (5) in the overparameterized regime (p > N) is strictly less than the lowest possible gen- eralization error in the underparameterized regime (p < N). This, together with the analysis and numerical evidence in previous studies such as those in Belkin al. (2019 (020). leads the under- standing that smoother approximations (i.e., solutions that are dominated by lower Fourier modes) give better generalization in learning with the RFF model (T.
Main contributions of this work. In this work, we analyze generalized version of (5) for gen- eral feature regression from noisy data. Following the same notations as before, we introduce the following weighted least-squares formulation for feature regression:
0
A W, with w = arg min ||A ||A
-a ( AI yo)
12
where the superscript on y and O, denotes the fact that the training data contain random noise of level d (which will be specified later). The exponent a is pre-selected and can be different from 3. While sharing similar roles with the weight matrix Aim. the weight matrix A -a [N] provides us the additional ability to deal with noise in the training data. Moreover, as we will see later, the weight matrix A [N does not have to be either diagonal or in the same form as the matrix A A-8. the
2

---

Published as a conference paper at ICLR 2022
current form is to simplify the calculations for the RFF model. It can be chosen based on the priori information we have on the operator V as well as the noise distribution of the training data.
The highlight and also of the main contributions of our work is that introduce a new weight matrix A [ that emphasizes the data mismatch in terms of its various modes, in addition to A [p] the weight matrix imposed on the unknown feature coefficient vector 0. This type of generalization has appeared in different forms in many computational approaches for solving inverse and learning problems where the standard 2-norm (or e in the unfiite-dimensiona setting) is replaced with a weighted norm that is either weaker or stronger than the unweighted 2-norm.
-
In this paper, we characterize the impact the new weighted optimization framework 7 on the generalization capability of various feature regression and kemel regression models. The new con- tributions of this work are threefold. First, we discuss in detail the generalized weighted least- squares framework (7) in Section 2 and summarize the main results for training with noise-free data in Section 3 for the RFF model in both the overparameterized and the underparameterizeed regimes. This is the setup considered in Xie et al. (2020), but our analysis is based on the proposed weighted model 7 instead of (5) as in their work. Second, we provide the generalization error in both two regimes for the case of training with noisy data; see Section This setup was not considered in Xie et al. (2020), but we demonstrate here that it is a significant advantage of the weighted optimization when data contains noise since the weighting could effectively minimize the influence of the noise and thus improve the stability of feature regression. Third, we extend the same type of results to more general models in feature regression and kernel regression that are beyond the RFF model, given that the operator V/ satisfies certain properties. In the general setup presented in Section [5] we derive error bounds in the asymptotic limit when P, .N, and all become very large. Our analy- sis provides some guidelines on selecting weighting schemes through either the parameter domain weighting or the data domain weighting, or both, to emphasize the features of the unknowns to be learned based priori knowledge.
2 GENERALIZED WEIGHTED LEAST-SQUARES FORMULATION
There are four essential elements in the least-squares formulation of the learning problem: (i) the parameter be leamed (0), (ii) the dataset used in the training process (y), (iii) the feature matrix (I)), and (iv) the metric chosen to measure the data mismatch between v/ and y.
Element (i) of the problem is determined not only by the data but also by a priori information we have. The information encoded in (3) reveals that the size (i.e., the variance) of the Fourier modes in the RFF model decays as fast as (1 + k)- Therefore, the low-frequency modes in (I) dominate high-frequeng
modes, which implies that in the learning process, we should search for the solution vectors that have more low- frequenqucc components than the high-frequency components. The motivation behind introducing the weight matrix A,) in (5) is exactly to force the optimization algorithm to focus on admissible solutions that are consistent with the priori knowledge given in (3, which is to seek whose components |0 statistically decay like (1 + k)-29
When the problem is formally determined (i.c., p = N). the operator V is invertible, and the training data are noise-free free, similar to the weight matrix A, A the weight matrix [Nj does not change the solution of the learning problem. However, the solutions in various ways under the practical setups that we are interested in, for instance, when the problem is werr-parameterized when the training data contain random noise.
will see later, these two weight matrices do impact
The weight matrix A [M] is introduced to handle elements (ii)-(iv) of the learning problem. First, since A is directly applied to the data y", it allows us to suppress (when a > 0) or promote (when a < 0) high-frequency components the data during the training process. In partieular, when transformed back to the physical space, the weight matrix A with a >> 0 corresponds to smoothing convolutional operator whose kernel has Fourier coefficients decaying at the rate k-a This operator suppresses high-frequency information in the data. Second, A is also directly applied to VO. This allows us to precondition the learning problem by making A AN y a better- conditioned operator (in an appropriate sense) than V, for some applications where the feature matrix V has certain undesired properties. Finally, since [N] is applied to the residual vo y, we can
[N]
3

---

Published as a conference paper at ICLR 2022
regard the new weighted optimization formulation as the generalization of the classic least- squares formulation with a new loss function (a weighted norm) measuring the data mismatch.
Weighting optimization schemes such as have been studied, implicitly explicitly, in different settings (Needell et al., 2014 Byrd & Lipton 2019; Engquist et al.] 2020 Li 2021 Yang et al. 2021). For instance, if take 0, then have case where rescale the classical least- squares loss function with the weight [N]. If we take a = 1, then this least-squares functional equivalent the loss function based on the H norm, instead of the usual L norm, of the mismatch between the target function fe (z) and the learned model (z). Based on the asymptotic equivalence between the quadratic Wasserstein metric and the 7 semi momim (on an appropriate functional space), this training problem is asymptotically equivalent to the same training problem based on a quadratic Wasserstein loss function; see for instance Engguist et al. (2020) for more detailed illustration on the connection. In the classical statistical inversion setting. A 20 plays the role of the covariance matrix of the additive Gaussian random noise in the data (Kaipio Somersalo, 2005). When the noise is sampled from mean-zero Gaussian distribution with covariance matrix 20 a standard maximum likelihood estimator (MLE) is often constructed as the minimizer of ( y)" A N (vO y) AAj o 1)
2n
The exact solution to 7 with X denoting the Moore-Penrost inverse of operator X, is given by
5 = AT A Ax A AN.y" p
(8) In the rest of this paper, analyze this training result and highlight the impact of the weight matrices A -a and A [N] in different regimes of the learning problem. We reproduce the classical [N]
birs-variance trade-off analysis in the weighted optimization framework. For that purpose, we utilize
the linearity of the problem to decompose 0 as
0p- A (A [N] (xp)) A N + A [N] (N
[p] A yy, (y
(9)
where the first part is simply o,. the result of learning with noise-free data, while the second part is the contribution from the additive noise. We define the generalization error in this case as
(P,.(P,).N) Eø.5 [11o(=) fx(()))l:=
Eo.5
100 0p O2 0
(10)
where the expectation is taken over the joint distribution of and the random noise 8. By the stan- dard triangle inequality, this generalization error is bounded by sum of the generalization error from training with noise-free data and the error caused by the noise. We will use this simple observation to bound the generalization errors when no exact formulas can be derived. We also look at the variance of the generalization error with respect to the random noise, which is
Var (Fax(Folll [| 0 01 == E& [Fo
Eg.al100 -1
(11)
In the rest of the work, consider two parameter regimes of learning: (i) In the overparaneterized regime, we have the following setup of the parameters:
N P<PSP, and, P= P=pM ,N, p vN for some μ. E N s.t. 42
(12)
(ii) In the underparameterized regime, have the following scaling relations:
p N < The formally-determineed case of = N < P is included in both the overparameterized and the underparameterized regimes. We make the following assumptions throughout the work:
and, P μNN for some μ E N.
(13)
(A-I) The random noise ò in the training data is additive in the sense that yd y + 6.
(A-II) The random vectors ô and 0 are independent.
(A-III) The random noise d (O, o [pj) for some constant a O.
While assumptions (A-I) and (A-II) essential, assumption (A-III) is only needed to simplify the calculations. Most of the results we obtain in this paper can be reproduced straightforwardly for the random noise 5 with any well-defined covariance matrix.
4

---

Published as a conference paper at ICLR 2022
3 GENERALIZATION ERROR FOR TRAINING WITH NOISE- DATA
We start with the problem of training with noise-free data. In this case, we utilize tools developed in Belkin et al. (2020) and Xie et al. (2020) derive exact generalization errors. Our main objective compare the difference and similarity of the roles of the weight matrices [Ni and
[p
We have the following results on the generalization error. The proof is in Appendix A.1 and A.2
Theorem 3.1 (Training with noise-free data). Let 5 0, and f be sampled with the properties in Then the generalization error in the overparameterized regime
is:
00 = 1122
N-1
Σ
23 En
K+NN
24
Cr
N-1
Σ
2
Eij= N-N
k+ No
1 kKNN))
23
(14)
k=0
KKNN
k=
and the generalization error in the underparameterized regime
13 is:
P-1
N
N p-11 (N)
E (P.D =
Σ
27
27 K4Nn
27 N4
+N
1 j
Σ ΣE
j=N
k=
1=
y=1
+J=0
(15)
where {tz}5a0 P-1 and cy are those introduced in
and while
A/N) = -k== (2 UsuUn
(N) Ejj = - + Xp+w V ViN,, 0
with UEV* being the singular value decomposition of A ((v) L (NNMN and {xm li- defined
Xm = E kk= | (
(N N Ey= Wo w))m 0 O
WN
We want to emphasize that the generalization errors we obtained in Theorem 3.1 are for the weighted optimization formulation 7 where we have additional weight matrix A ANj compared to the for-
mulation in Xie et al. (2020) even though our results look similar to the previous results of Belkin al. 2020) and Xie al. (020). Moreover, we kept the weight matrix A the underparame- terized regime, which is different from the setup in Xie et al.) (2020) where the same weight matrix was removed in this regime. The reason for keeping A [p] the underparameterized regime will become more obvious in the case of training with noisy data, as we will see in the next section.
[p]
Here are some key observations from the above results, which, we emphasize again, are obtained in the setting where the optimization problems are solved exactly, and the data involved contain no random noise. The conclusion will differ when data contain random noise or when optimization problems cannot be solved exactly.
-8 -a First, the the weight matrix A only matters in the overparameterized regime while ATr] only
matters in the underparameterizee regime. In the overparameterizee regime, the weight A Tpl forces the inversion procedure focus solutions that biased toward the low-frequency modes. In the underparameterizzed regime, the matrix A -a re-weights the frequency content of the "residual" [v]
(data mismatch) before it is backprojected into the learned parameter θ. Using the scaling P = μNN and p vN in the overparameterized regime, and the definition of Cy, we can verify that when 3 = 0, the generalization error reduces to
E0 (P.p(P.) -
N
2N
C P-
N
2N ey
21
(16)
P
p P
This is given in Xie et al. (0000
Theorem 1).
Second, when the learning problem is formally determined, i.e., when p N, neither weight matri- ces play role when the training data are generated from the true model with no additional random noise and the minimizer can be found exactly. The generalization error simplifies to
Ea (P,p(PPp, N) 2c, Ep1
(17)
5

---

Published as a conference paper at ICLR 2022
10
00
10
10
0.5
107
10
Singular value Index
10'
10
10
(a) singular values of [N) [N]Va]
(b) double-descent curves with different &
N y [N](P)] for a system with N = 1024 and p = 512. Shown are singular values for a = 0, a = 0.4, a = 0.6, a = 0.8, and a = 1.0; Right: double-descent curves
Figure I: Left: singular values of
for the generalization error a, for the cases of N 64, 7 0.3, 3 0.3, and 0, 0.3, 0.8.
This is not surprising as, in this case, V is invertible (because it is a unitary matrix scaled by the constant N). The true solution v/0- y simply 0 v- The weight matrices in the optimization problem are invertible and therefore do not change the true solution of the problem. The generalization error, in this case, is therefore only due the Fourier modes that are not learned from the training data, i.e., modes to P 1
While it obvious from the formulas for the generalization error that the weight matrix A [N] indeed plays a role in the underparameterizee regime, we show in Figure [a] the numerical calculation of the singular value decomposition of the matrix [ V/ [M]]p] for the case of (N, p) = (1024, 512). The impact of can be seen by comparing the singular values to their correspondence in the = 0 case (where all the singular values are the same and equal to VN). When the system size is large (in this case N 1024), even a small a (e.g., a = 0.4) can significantly impact the result. In Figure 1b we plot the theoretical prediction of Eg.9 in Theorem 3.1 to demonstrate the double- descent phenomenon observed in the literature on the RFF model. We emphasize again that in this particular noise-free setup with perfectly solved minimization problem by the pseudoinverse, A [M] only plays a role in the underparameterized regime as can be seen from the double-descent curves.
Selecting to minimize generalization error. It is clear (and also expected) from (16 and (17) that, in the cases of p = N or a B y= = O, the generalization error decreases monotonically with respect to the number of modes learned in the training process. One should then learn as many Fourier coefficients as possible. When p * N or or, B & O, e p, N), for fixed and N, does change monotonically with respect to p anymore. such a situation, we can choose the p values that minimize the generalization error and perform learning with these values.
ERROR BOUNDS FOR TRAINING WITH NOISY DATA
In this section, we study the more realistic setting of training with noisy data. The common practice that when we solve the minimization problem in such case, should avoid overfitting the model to the data by stopping the optimization algorithm early at an appropriate level of values depending on the noise level in the data, but see Bartlett et al. (220 direction of "benign overfitting". When training with noisy data, the impact of the weight matrices A aa and A, -8 on the generalization error becomes more obvious. In fact, both weight matrices play [p]
et (2021b) for some analysis in the
[N] neg-lggli roles in the overparameterized and the underparameterized regimes, respectively.
We start with the circumstance where we still match the data perfectly for each realization of the noise in the data. The result is summarized as follows.

---

Published as a conference paper at ICLR 2022
Lemma 4.1 (Training with noisy data: exact error). Under the assumptions (A-I)-A-III,, the gen- eralization error e p. N) is given as
+ Enoise (P.P. N);
where E (P.,(P is the generalization error from training with noise-free data given Theo- rem 3.1 and Encise (P.P p. N) is the ervor due to noise. The error due to noise and the variance of the generalization error with respect to noise are respectively
Enoiso (P,p, =
N-1
Σ 1==0
2
K+NN
48
Vars
Eoll
-0
20 N-1
rg
40
Noy
k+Nu
2
=
N
k=0
> ==
28 A N+
(18)
in the overparameterized regime 12p and
N N-p-1
(N)
Enoiso (.P.NN = 0²
2p (222p-
N
+
Σ
ij
p> N/2,
N
|=
(19)
p-1
(N)
20 2p
N
Vars EBoll0* -
ij
N2
1
11
in the underpurameterizzn regime 13
The proof of this lemma is documented in Appendix A.3 Note that due to the assumption that the noise ô and the coefficient O are independent, the noise-averaged generalization errors are split exactly into two separate parts: the part due to 0 and the part due to ô. The coupling between them disappears. This also leads to the fact that the variance of the generalization error with respect to noise only depends on the noise distribution (instead of both the noise variance and the 0 variance).
8 is only For the impact of noise on the generalization eтror, we see again that the impact of [
seen in the overparameterized regime while that of A -a [N] is only seen in the underparameterized regime. This happens because we assume that we can solve the optimization problem exactly for each realization of the noisy data. In the overparameterized regime, when 3 = O, we have that Enoise No²2 /p as expected. In such a case, the variance reduces to Varş (Eellee 2No* /p2. In the underparameterrzed regime, when a 0, we have that Enoise pa? /NN The corresponding variance reduces to Vars (Eoll 0 3) 2po
@1
In the limit when p + N, that is, in the formally determined regime, the mean generalization error due to random noise (resp. the variance of the generalization error with respect to noise) converges to the same value Enoise p, N) o² (resp. (EE [| 0112)) 2 /N) from both the overparameterized and the underparameterized regimes. This is the classical result in statistical learning theory (Kaipio & Somersalo 2005).
The explicit error characterization above is based on the assumption that we solve the optimization exactly by minimizing the mismatch to 0 in the learning process. In practical applications, is often the case that we stop the minimization process when the value of the loss function reaches level that is comparable to the size of the noise in the data (normalized by the size of the target function, for instance). We now present the generalization error bounds for such a case.
Theorem 4.2 (Training with noisy data: error bounds). In the same setup as Lemma 4.1 for fixed N. we have the following general bound on the generalization error when is sufficiently large:
(P.. Z 20 E
61,
1--1+ +p -=2 20-228 El 1.
- [N]
where ā = + 1/2 (resp ā a) in the overparameterized (resp. underparameterized) regime. When à 2 O, the error decreases monotonically with respect to p. When < O, the bound is minimized by selecting
p
Es
2.A
2.A
(20)
in which case have
E (P.P.N)
$ Eoll01
2 23
25
Es
11 2
213
28
(21)
2.A
2.A [M
7

---

Published as a conference paper at ICLR 2022
Note that the calculations in (20) and (11) only to the leading order. We neglected the contribu- tion from the term involving Y Also, the quantities in expectations can be simplified. We avoided doing so make these quantities easily recognizable as they are the main quantities of interests.
In the underparameterizee regime, that is, the regime of reconstruction, classical statistical inversion theory shows that is statistically beneficial introduce the weight matrix A [M] that is related the
covariance matrix of the noise in the data (Kaipio & Somersalo 2005) (see also Bal Ren (2009) for an adaptive way of adjusting the weight matrix for some specific applications). Our result here consistent with the classical result as we could see that if we take A be the inverse of the covariance matrix for the noise distribution, the size the noise contribution in the generalization error is minimized.
Theorem 4.2 shows that, in the case of training with noisy data, the a parameter can be tuned to reduce the generalization error of the learning process just the 3 parameter in the weight matrix [P]- Moreover, this result serve be pursued in the training process to minimize the generalization error, depending on the level of random noise in the training data as well as the regime of the problem.
guidance the selection of the number of features to
5 EXTENSION TO GENERAL FEATURE REGRESSION
The results in the previous sections, even though are obtained for the specific form of Fourier feature regression, also hold in more general settings. Let fo general random feature model of the form
fo(x) = E (2px(T), x E X, constructed from a family of orthonormal features {pk] in (X).. Let be the feature matrix constructed from the dataset {I,, My -
(22)
v jR (x5)), 0
We can then apply the same weighted optimization framework 7 to this general model. As in the case of RFF model, the data in the learning process allows decomposition
y
L [N] [p) 0 [r] + V ([T)(( θ (P])))) + 5
The learning process only aims to learn the first modes, i.c., 0pp indicating that the effective noise that we backpropagate into |ii in the learning process is V ([NIx((PMM))) 0 PPNNp + 6. The frequency contents of this effective noise can come from the true noise 8, the part of Fourier modes that we are homogeneously VN. For learning with many other features in practical applications,
not learning (i.e., 0 (P))(r)) ) or even the feature matrix L [NN]x For the RFF model, the feature matrix 1 [N is unitary after being normalized by 1/VN. Therefore, all its singular values are could have feature matrices V []]] with fast-decaying singular values. This, on one hand, means that [I]]x (a (r])pp) will decay even faster than 0 (P]) making its impact on the learning process smaller. On the other hand, [N]][[]] having fast-decaying singular values will make learning yr) harder (since it less stable).
The impact of the weighting scheme on the generalization error as an expectation over O and (defined in Lemma I. summarized in Theorem [.T] Its proof is in Appendix(A.4 Note that here we do not assume any specific structure on the distributions of 0 and 8 except there independence.
Theorem 5.1. Let = UΣV* be the singular value decomposition V. V. Under the assumplions (A-I)-A-IIII,, assume further that Lise ~ t/ for some Ç > 0. Then the generalization error of training, using the weighted optimization scheme with A [N] replaced with replaced with V Ap satisfies
A -o U and A (P) [N]
E (P.P.N) 2(5 Es
20 [ +
2. 2
in the asymptotic limit ~ N ~ P co. The bound is minimized, as a functio of p. when
p (E
"E 2.A a
pectà-o3, -
(23)
2.4
8

---

Published as a conference paper at ICLR 2022
in which case have that
(P 2.A pm
Es Es
(c+3-0)
(24)
2.
On the philosophical level, the result says that when the learning model is smoothing, that is, when the singular values of V decays fast, we can select the appropriate weight matrix to compensate the smoothing effect so that the generalization emrr is optimized. The assumption that we have access to the exact form of the singular value decomposition of the feature matrix is only made to trivialize the calculations, and is by no means essential. When the optimization algorithm is stopped before perfect matching can be achieve, the fitting from the weighted optimization scheme generated a smoother approximation (with a smaller p, according to (2 than what we would obtain with regular least-squares minimization).
Feature matrices with fast-decaying singular values are ubiquitous in applications. In Appendix B we provide some discussions on the applicability of this result in understanding general kernel learn- ing (Amari & Wu 1999. Kamnitsas et al. 2018 Jean et al. 2018 Owhadi & Yoo 2019 Bordelon et al.
2020) Canatar et al. 2021) and learning with simplified neural networks.
CONCLUDING REMARKS
In this work, we analyzed the impact of weighted optimization on the generalization capability of feature regression with noisy data for the RFF model and generalized the result to the case of fea- ture regression and kernel regression. For the RFF model, we show that the proposed weighting scheme (7) allows us to minimize the impact of noise in the training data while emphasizing the cor- responding features according to the a priori knowledge we have on the distribution of the features. In general, emphasizing fwyffreuenccy features (i.e., searching for smoother functions) provide bet- ter generalization ability.
While what analyze in this paper is mainly motivated by the machine learning literature. the problem of fitting models such as the RFF model (T) to the observed data is a standard inverse problem that has been extensively studied (Engl al., 1996; Tarantola 2005). The main focus of classical inversion theory is on the case when V ([Nxp) is at least rank p so that there is a unique least- squares solution the equation VO y for any given dataset y. This corresponds to the learning problem we described above in the underparameterizet regime.
In general, weighting the least-squares allows to have an optimization algorithm that prioritize the modes that we are interested in during the iteration process. This can be seen as preconditioning strategy from the computational optimization perspective.
It would be of great interest to derive a rigorous theory for the weighted optimization 7 for general non-convex problems (note that while the RFF model itself is nonlinear from input x output fz)),, the regression problem is linear). Take general nonlinear model of the form
F(x; 0) y,
where F is nonlinear with respect to For instance, could a deep neural network with representing the parameters of the network (for instance, the weight matrices and bias vectors at different layers). We formulate the learning problem with a weighted least-squares as
0 A W, with w arg min
[vj [F App w) 1
w
where the weight matrices are used to control the smoothness of the gradient of the optimization procedure. The linearized problem for the learning of w gives problem of the form v/ ý with
V =((iix) (xx; A (p) "A) ) (F") A (A ý ) A w) )) (A [N]))'
(FF)
For many practical applications in computational learning and inversion, F' (with respect to 0) has the properties we need for Theorem 5.1 to hold. Therefore, a local theory could be obtained. The question is, can we show that the accumulation of the results through iterative optimization procedure (e.g., a stochastic gradient descent algorithm) does not destroy the local theory so that have in this work would hold globally? We believe thorough analysis along
the conclusions the lines of the recent work of Ma & Ying (20T)) is possible with reasonable assumptions on the convergence properties of the iterative process.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is partially supported by the National Science Foundation through grants DMS-1620396, DMS-1620473, DMS-1913129, and DMS-1913309, Y. Yang acknowledges supports from Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. This work was done in part while Y. Yang was visiting the Simons Institute for the Theory of Computing in Fall 2021. The authors would like to thank Yuege Xie for comments that helped us correct a mistake in an earlier version of the paper.
SUPPLEMENTARY MATERIAL
Supplementary material for the paper "A Generalized Weighted Optimization Method for Compu- tational Learning and Inversion" is organized as follows.
A PROOF OF MAIN RESULTS
We provide here the proofs for all the results that we summarized the main part of the paper. To simplify the presentation, we introduce the following notations. For the feature matrix v E CNXP. we denote by
Vr E CX and Mr E (x((pp))
the submatrices of v corresponding to the first p columns and the last P p columns respectively. In the underparamettrrized regime
13 we will also use the following submatrices
V
[M] E NNN and L (NNTT E CNN(W-P),
corresponding to the first N columns of v and the last N columns of VIN respectively. We will use V denote the Hermitian transpose of V. For a P x diagonal matrix A, Ag Ap) and Ag- denote respectively the diagonal matrices of sizes p x p and (P-p) p) (P - p) that contain the first p and the last P diagonal elements of A. Matrix A[v] is of size N x N and used to denote the first N diagonal elements of A. For any column vector 0 E CPx1 Or and OT. denote respectively the column vectors that contain the first p elements and the last P - p elements of
To study the impact of the weight matrices A and A -8 [N]
we introduce the re-scaled version of the bo]
feature matrix v, denoted by 4, as
A [P]
(25)
In terms of the notations above, we have that
T A A and Pro ==
A [N]
(26)
For given column vector 0 E Cd and real- square-matrix E IRdxd we denote by
| l = |X0|22 (X
the X-weighted 2-norm O. We will not differentiate between finite- and infinite-dimensionn vectors. In the dinnnt--dmmeniooall case, simply understand the 2-norm as the usual e f-norm.
We first derive a general form for the generalization error for training with 0 sampled from a distri- bution with given diagonal covariance matrix. It is the starting point for most of the calculations in this paper. The calculation procedure is similar to that of Lemma of Xie et al. (2020). However, our result for the case with the additional weight matrix A [ [N]
A.1 PROOFS OF LEMMA A.I LEEMA A.3
p, N)), Let K E CPXP be a diagonal matrix, and be drawn from a distribution such that
Lemma A.1 (General form of E (P
Eg ( 0,
Ep(00') K.
(27)
10

---

Published as a conference paper at ICLR 2022
Then the generalization ervor for training with weighted optimization 7
be written
0 (P... tr(K) + Pa,s + Qa.3,
(28)
where
Pa. = tr ( 2
LT AT
2tr KT DT)
and
2 tt TT. A KT= A BG.), 2a.5 = tr (1)
with p7 and PT given in 26
Proof. We introduce the variables
w A p and z A [N] y-
We then write the solution the weighted least-square problem 7
WT क z,
and Win 0,
where & is the noise, write
inverse of Φr. Using the fact that the data y contain no random
y TT
3 WT Pr WT., and ANjy PTwr + Pr Wr..
Therefore, we have, following simple linear algebra, that
|@
01l || 8 (w: w: 112 + AA (WT w--)
= ||T o (PTWT + 4T- WT-)
AT wT 11 + || WT 12
|A Φ 4T
WT- WT- " 4 2T) wr/p) 9 wr
(29)
Next, we make the following expansions:
||A_ $ $ t Th WT=
T TT)
w
||A_ t TT WT + IA *(1
$7 TT)
w
Ti
3
Φ (T) WT
||L wT
WT 12 + " + WT -12
with Ti and Ta given respectively
Ti = 29
(A, क6 pT WT:) ) "A AI + (T)
and
To
23R
w
AT o Prwr)
We therefore conclude from these expansions and 29 over 0, that
using the linearity property of the expectation
Eg || 0
01
ww + Ee A WT=
+ E. A क tr || + A 9 t
Eo[Ti]
Eg [T2].
(30)
We first observe that the first two terms in the error simply tr [ that is,
Ee AT wT 11 + Ee
T WT tr (K).
(31)
By the assumption 27 we also have that IEg (0 X01 0 for any matrix X such that the product is well-defined. Using the relation between 0 and we conclude that
Eg [T] = 0.
(32)
We then verify, using simple trace tricks, that
Eg [T2] = 2Ea 32 (IrWWAAT AT t wnwr)]]] = 23 (I(( 21r(K- (33)
11

---

Published as a conference paper at ICLR 2022
where we have also used the fact that KTAT" " KT since both matrices diagonal, and the last step comes from the fact that O Dr is Hermitian.
Next, we observe, using standard trace tricks and the fact that o Dr is Hermitian, that
EfllAAF f P.wrlal
Eg (ojtr((w
D AT o P.wr))
tr tr(# PTAT 29 t Pr /ww
Kr
(34)
and
Eoll| AT B7 PT- wr
t7. = 07. (0
AT x Dr WTr
tr(#f. (0) t E WT Wiee
= tr(0i. (07) " AT To A K Ag.)
tr((
29 2 P K T. T7
(35)
The proof is complete when put 31
34 and
35 into
30
Next we derive the general formula for the generalization error for training with noisy data. Lemma A.2 (General form of ed.s(P.p. N)). Let 0 be given as in Lemma A./ Then, under the assumptions (A-I)-(AIII, the generalization error for training with weighted optimization 7 from noisy data y can be written as
E. (P.p(P =
(P.,, E + Enoise (P.p,N)
(36)
where E2, (P,,,, N) is given as in 28 and Enoise (P, p, N) is given
Enniso (P, (P.p, N) ir + t AT 29 Es(6")
[N]
The variance of the generalization error with respect to the random noise is
Vars [Eollle 011) Es [trtt A (
28 Φ
55
29 o A [N]
(Enoise (P.p, ()), (37)
Proof. We start with the following standard error decomposition
10 0 o -
0
01 = 1|0
011 +
-
-
23h (0 6 - 0))
Using the fact that
8 σ-. 0T: = =0
the error can be simplified to
1
0 |
0112 + 110
0r113
Ts:
(38)
where
Tg = 29 (0 - 0-) @o - 0T)
Taking expectation with respect to and then the noise we have that
Ea.ell 0| E 0 E
0r121 -
(39)
The first term on the right-hand side is simply E (P. p. N) and does not depend on ö. To evaluate the second term which does not depend on 6, we use the fact that
5 0 θr A- 1200 2)
A - + A y)
AT 2 [N]
12

---

Published as a conference paper at ICLR 2022
This leads to
Es [|| 6
0r13]
AF $ 81
Es(tr 6" A |N] ( AT 23 ọ A O
= tr(A + ) AT x A Es 66
The last step realize that
E.g [Ta) = 23 [E..0 (AT 8 $ (x (0T 0r)
due to the assumption that 8 and 0 are independent.
Utilizing the formulas in (38) and (39). and the fact that Ee [sl = 0, we can write down the variance of the generalization error with respect to random noise as
Vara [Eo [||0 01 E. || 0Til
[B 0T113)
Es(tr(("AA A [N] (
23
-a [N]
A
[ (TT) AT 2. क A [N] (Enoise P.. N))
The proof is complete.
We also need the following properties on the the feature matrix of the random Fourier model.
Lemma A.3, (i) For any C 2 we define, in the overparameterized regime 12 the matrices II E NNN and Il2 C. respectively as
II = WTA- VV and II, V ATe A V.
Then II and Il, admit the decomposition II VIN ( and II, Au ('m) re- spectively with Anss and A1la.5 diagonal matrices whose m-th diagonal elements are respectively
(m))
Σ
Σ
- ) m. 0 S -
11.55
k=0
y=0
and
(m) Ills
(N) mm 0 m S N 1,
k+NN
k=
(N) where 6 m, is defined as, denoting WN = c x
N-1
(N) m,k
= N
km-
0,
1,
k: = m k: 4
0sm,k S N <
j=0
(ii) For 2 O, define, in the underparameterized regime 13 with p < N, the matrix
E CPx(NN (N-p) -p) as
= (BAA
20
NNTTT V [N]
[N]
Then E' 3 has the following representation:
E'E = N(
V [M
(MJTT) IN 4a [N]
[N]
20 IN (NN I[N-n)
Proof. Part (i) is simply Lemma 2 of Xie et al. both circulant matrices whose eigendecompositions
2020 was proved by verifying that II, and II, standard results in linear algebra.
To prove part (ii), let us introduce the matrices P, Q, R through the relation
1 [N] A- 20 V
VG
[M]
LT
A A [N) (NNTTT
INI
L INNT
P
R Q
[N]
(N
-2
Wr
-2
20
=
13

---

Published as a conference paper at ICLR 2022
Then by standard linear algebra, have that
P + P R R R
RTP-1
-P-IR(Q - R
(
(Mi A [NI
20 (MM)
Q RRP-R R
(Q R'P R)
since P LiA
-2 ur is invertible.
Meanwhile, since
1 VN
W [[]] is unitary, we have that
V (
A
MJ
2a [M])
N
V
IN
V
[N
2a
LT
UT IN WART
2a
P R
N2
[NKKT
[N]
V
2a [N) VINIV
R
Q
Comparing the two inverse matrices lead us to the following identity
P P P RR =
This gives us that Therefore, we have
P- R = P- -Ra--pp-RRRR R
R'P-'p-RR R- (1 - R*R) '''''PR N- R-R)-
Utilizing the fact that
1
R
N2 iN
L
[N] MT A (N) P INNTT
1
V
iMRTA 20 [N]
[NT[M] VINKT AMT
20 [NNTT I[N-p) QQ,
N2
we can now have the following identity
R (
Using the formulas for P and R. as well as VT
NI [N]
V VINIVT V
[NJYT we have
CPPRR
N MNRT IN
V
V
N
Wr
Wr
VT U
INTT
Q
INNTTA NY
INNK
QΩΩQ.
N
This finally gives us
R'P-PP-'R-
Q "V
[N] NNVT
IpN-p]
N
The proof is complete when we insert the definion of Q into the result.
A.2 PROOF OF THEOREM 3.1
We provide the proof of Theorem
3.1 here. We split the proof into the overparameterized and the
underparameterizee regimes.
Proof of Theorem 3.7 OOvrrpaameetrrized Regime). In the overparameterized regime 12
we have
that the Moore-Penrose inverse o verify that
( Φb )1 Using the definitions of क. in 26 we can
T A
" V ", - 29
A a tT = A-
28 ( 1+ -
and
$ A
28 Φx fT AT AT VVi(VAA
-2 (
48 ( -
14

---

Published as a conference paper at ICLR 2022
We therefore have
( A
tr((
29 U
AT
4. V
Meanwhile, trace trick leads to tr tr(K=0f0r
Ir Ir(K
TT) = Lr ( - K
tr (AA 2/ U
-(x) [Nj
A A V AT KTAT (iA
-8 v17) tr (V 2. wT) ATAT KTAT
(40)
Therefore, based on Lemma A.I we have finally that
28 TT Pa.3 ( 28 v AT 43 V (VTA
1/ TT
21r A 28 vT
- " Vz)
(41)
In similar manner, we can check that
28 ea.3 = tr(( A
T TT A. K T. A $
1r((Pr0i)~ TT 2
TT fir K A3.
= tr((V-AT 28 (T)
~ 1
A )G7) Kr. Vg.)
(42)
The above calculations give
(e = tr(K) - 2tr (er((11) (T 23 ~
Kーク 28 w リ リーイ Vi ( ~ -VK"".
+ (v
(43)
We are now ready to evaluate the terms in the generalization error. First, we have that since K Cy A [p] we have, using the definition of Cy. that
tr (K) G Σ
t 27 2
=
(44)
j=0
Second, using the results in part (i) of Lemma A.3 and the fact that I v W[n] is unitary, we have
VN
tr(( 28 TT)
1
A
KIAT 8 V+)
V
[N
[Nn]
A11 (iN))
N2
1
c,ta(
11
N
IT,
A
23 An. 20+2,
(N]) G. tr 21,,
=
N-1
2k
N-1
22 2nno
-20-21
m
(N)
(N)
=
N-1
Σ
2n k+Ny
Dnjo k+NN9
-28
27
(45)
m=0
k=
mm,k
k=
The results in Lemma A.3 also give that tr((VAA= 28
V
(VT 29 VT) -VKV")
= tr( N2 [
V
A
L iM D
INJ A AH [NI N2 L (N
A
10 |N (A1, + Al1.227) 1 (iNi)
I. 28
tr(A 28 An. 40 24
(AII, 27 + Ann.2))
We can plug in the formula of A.3 to get
tr ( A T
ATA 1 U
AT
29 Φ
(KK"
1-1 43
(N)
N-1
1--1 27
(N)
2 k+ Nu
m,
k==
Σ
Σ E
Σx=o
No
-28
Cmii]
[N)
N-1
1 13
Σ μ-1 = k+No
-=
k+Ng)
(46)
23 2 k
15

---

Published as a conference paper at ICLR 2022
We can now put
444
45 and (46) together into the general error formula 433 to get the result (4)
in Theorem 3.1 The proof is complete.
Proof of Theorem 3.7 have that the (Underpuramettrrzed Regime). the underparameterizze regime
13 we
inverse o (1) This leads to
$ ọT = IT and (Φ7)
AT
2- - o = Φ (+) AT ( Φ-)
Therefore, using notations in Lemma A.1
we have that Pa, is simplified to
Pa. -tr(Kr).
while 2a,3 is simplified to
Qa.8 tr (r(or(#141)
AT
28 (D
- 24
Uo T AI.A [N]
tr ( [
20
LT
V
2n UT)
(ViA
20 (T) -
20x
UT KTo W.).
(47)
(N)
In this regime, p S. N S P. We therefore have T (LNIVT) U [N] ([N) = (PMND Using the fact that K is diagonal, we obtain
KT Vi. "IMjTTKNN [NNNE" + Ii [Mj= v [N]e
Following the result of Lemma A.3] the second part of decomposition is simply the matrix II with 1. To avoid confusion, we denote it by II, and the result of Lemma A.3 to get
V [N V An V [[N]
where the diagonal elements of A1 are
N-1
N-1
24
(17)
Σ
K+Ng)
N
1
Σ
WN
(m--))))
0 m N
(48)
k=
j=0
Next perform the decomposition
Au, VNn V AT Vi + A ViNNTT
and define the diagonal matrices
K Ang.27T and K2 = KINNE + ATS.RTINNV
We can then have
VT.Ko. K 13 + MI
Plugging this into the expression for Qa,0, we have
2o.8 tr tr(A
20 V (
(
2a UT)
(V 2x VT)
20
v K w²
[N]]
+ tt
2a L
V MT)
(VIA
20 UT)
2a
[Nj IN (wyT)) (49)
Ni
IM
The first term simplifies tr [2₃) The second term vanishes in the case of a and in the case when the problem is formally determined; that is, when N, but is in general nonzero when p < N. Using the result part (ii) Lemma A.3 we have that
tr (A - 2a V (V. UT)
INI
20 (V.AA 22 UGANNA [N]
[NNV
K K2 (NNN))
tr ( T [N
20 UT)
20 (T)
u IN
2a 201 (PTTTK2)
Ntr(X V M
4a M
K2) tr (K²).
X = v L (N]YT.
2a
Using this result and the singular value decomposition
fNy VINJTT Udiag((Eo.. (000:==))=X----N)N---=-))
16

---

Published as a conference paper at ICLR 2022
introduced in Theorem 3.1 have
Ca. tr [K K2) + Ntr (tr
US V
N N-p-
---p-11
NNN
ir(An1s,2T - N AUN + N Σ
yj ji
/=0
where
N-1 Σ k=0
N-p-1
((N) 43
& =
(e + ((tt')
V ik VjN,
N
The proof is complete when we insert the expressions of Pa,s and Qa, back to the general for- mula
28
and use the form X (m)
48).
11..2
When the problem is formally determined, i.c. in the case of N (equivalent to 1), A 20 Vy This allows us to find that
L Vi -2
[N] Tr
2a.8 = tr( w A ViN N2
L Am, ['M "Nn A 20 "NN
N2 v
4IN An (N))
-4a Exjo k+Nn
EE p- --2
k+NN
-tr(Aji tr( 40 Ao An,,27))
vリ-1 2-20 T== *+NN
which degenerates to its form (46) in the overparameterized regime with v 1. The result is then independent of a since the terms that involve cancel each other. Similarly, the simplification of Qa,8 in (46) with v/ = 1 (N = p) also leads to the fact that 3 disappears from the formula.
A.3 PROOFS OF LEMMA AND THEOREM
By Lemma A.2 the main task is to estimate the size the generalization error caused the random noise in the two regimes. The error is, according to (36).
Proof of Lemma 4.1
Enoiee (P.p, N) tr ( 23 + T [o
In the overparameterized regime, we have that
229 -a
A (TT
[
(VTA
28
- U
48 u
28 - (TA
Therefore we have, using the results in part (i) of Lemma A.3
Enoise (P.p. o²trl [N In 28 iim v
An (iN
v22 MIN (in)
o²
N-1
= K+NN
w-1
-88
N tr 2g An 48 A
=
N
23 12
k=
2 k+N
17

---

Published as a conference paper at ICLR 2022
To get the variance of the generalization enror with respect to noise, we first compute
AM 2 Txj6)]
= o [M] +
+20 22 (A (
[N]
01
43 A1
A
11 V (w))
N4
20a
tr
( 11, An,
(N]
A1, An, -1 23 (N))
N+
=
N2
tr
28 11,
(A I1,
An,, An,
17, 28)
Ai 28 An, 48 i1.28)
20
tr (ATii An,
An, 134
23
TT.
43 A 23))
N2
m= k+ Nn
マリー 1-8
2
20
N-1
リール 1 19 2n= K+Nn
N2
2/
N2
29
m Nn
my 0 N+
This, together with the general form of the variance in gives the result in In the underparameterizee regime, we have that
18
A 1-20 20 W (V [N] [N] Therefore we have, using the fact that V- + VINRY ViNYY= NI [N). that
[ (
AT 2/ o [N]
TT) (V 2a VT)
1 [N]
[N]
(
a 28 क [N]
(50)
[N]
Vr + L INN
V (NTNT A (T) 'AA x A -0
V + WINNTTWNNNT
N2
VT
N2 P
N2
1
L UNNNT
IN
( 1
N2
T NNNT (NIVT
M 20 V
[N] V
(
20 TT
VTA -20 T INJYT "NITT
Na
This leads to, using the fact that V/
NI [p] and properties of traces,
Enoise N)
d2 detr o²
[N]
(+)
AT
28 [vj)
0² N
p
N tr V
[N]
2a
V [N]
20 U
(N)
-2 - -2a (M]TT)
A [N]
Using the result in part (ii) of Lemma
A.3
we have that the second term simplifies to
tr V VNNITAA -2 V V 2a V
2a L -r) ATA 2c ((N]TT) [N]
Ntr X
[v]
(N (N - p), x ViNIN 20 [MJ.T
Using this result and the singular value decomposition
iyy v INJTT Udiag(
-(N----1(N---11)V
introduced in Theorem we have
N-p-1 (N)
Emoise (P,p, N)
P po2__ N
N --P P to
1 = 0² 2p -
+ Σ
N
N
Σ
1=
18

---

Published as a conference paper at ICLR 2022
Following the same procedure as in the overparamettrrized regime,, the variance of the generalization error with respect to noise in this case is
Es Es(tr(6" A [M]
68 A
= o (A
-, A き
(M 2 [N]
+20
4 + M
The first term on the right hand side is simply (Ennisel P. N)) To evaluate the second term, we use the formula 50 is straightforward to obtain, after some algehra, that
Ir ir(A
28 A [NT]
=
N3
tr
(T
N2
[N
20 UT) ( [N]
A L (INTVT)
tr
iN
(V (N)
(T)
[N]] VINNTT]
N2
p
2
Ntr
X (N -V-1) -p))
N2
N2
X
ViNiN (MV) -
N
2Ntr
X
(INN-11)))
2p -
+ tr
N2
2p- tr
PNTVT
N2
This leads
Es[1r((" (N]
AT
28 Φ A [M]
00
IN
2p N
(P.,,e((P.p,))) + 20
tr
U
20
UNE U UT)
U
N2
N-p-IN
2p N
20
=
N2
j=0
Inserting this into the general form of the variance, i.c. terized regime. The proof is complete.
37
will lead to
19) for the underparame-
Proof of Theorem
4.2
By standard decomposition, we have that
10
0
= 100
0 01
V ( (0
0 V
(PPP)XX)) (x -y)+ (ImM +((m(
((p-))xP) )0
w v
2 51 +
[I[p)
0 (
(51)
From the calculations the previous sections and the normalization of V we used, is straightfor- ward to verify that, for any fixed N.
VUND =p=
p N P<N N
| 122
P aaa
and
1
1z1
0
-22
where [X]
-2 denotes the norm of as an operator from the A -a
[N] weighted CN to CP.
19

---

Published as a conference paper at ICLR 2022
This allows to conclude, after taking expectation with respect to @ and then 8, that
Eg,0ll = +
2. Ball A [N] (y
-y)
+ ([1 -
w 2 2- Eo 1 =l S pp
+ 1--p00 2a Eg | 2
+
23 Ee
2. 1nj
2M
where p min(1, N/p). For any fixed N, when a in the suder-parameterizen regime), the error decrease monotonically with respect to When < 112 in the ver-paraaeterized regime (resp. < 0 in the under parameterized regime), the first term increase with while the second term descreases with p. To minimize the right-hand side, take
11/2 in the over-parameterized regime (resp.
ES ||
1
200-0)
(52)
where â == a + in the over parameterizee regime and â in the under pardamtrtattt regime. This leads
Ea 01
EollO 2.1 2.1
2 25--5
(53)
The proof is now complete.
A.4 PROOF OF THEOREM 5.1
Proof of Theorem 5.7 Without loss of generality, we assume that V is diagonal with diagonal ele-
ments VE S- If not, we can rescale the weight matrix A -8 by V and weight matrix A [N]] by [p]
U given in the theorem.
Let th the pseudoinverse of that consists of the first p features such that
{.. q 9 p
(w+) 9g (,
g>p
where ( is the exponent in the SVD v assumed in Theorem
We can then check that the operators 1- + v norms respectively
l2 a [pj
+ lz and +t+ ;22 62_ [n]
+ l² have the following
12 Ax -p-a and
[[ 4 v
-2
~p-
By the error decomposition then d, that
51 we then conclude, after taking expectation with respect to 0 and
Eg. 0 01
S
|
|
Es
EallA
|
2,4
IN
+ -
+
Eo
0113
2.
=
S 222 2(c-a) E. Es11811 |,10011 A
11p-2900 Eo|[0
+
29
12
2.4
We can now select
p (Es
11
2,1 Eo 11
(54)
2.A
(p)
to minimize the error. This leads
Eso1 01
Eoll
1
Eg
| 2.A
(55)
2.A
[p
The proof is now complete.
B ON THE APPLICABILITY OF THEOREM 5.1
In order for the result of Theorem 5. to hold, we need the model to be learned to have the smooth- ing property. In the case of feature regression, this requires that the feature matrices (or sampling matrices) correspond kernels whose singular values decay algebraically. This turns out to be true for many kernel regression models in practical applications. In the case of solving inverse prob- lems, this is extremely common as most inverse problems based physical models have smoothing operators; see, for instance, [sakov (2006); Kirsch (201T) for a more in-depth discussion on this issue.
20

---

Published as a conference paper at ICLR 2022
General kernel regression. Let H. be reproducing kernel Hilbert space (RKHS) over X, and IC H. x H. + R be the corresponding (symmetric and positive semidefinite) reproducing kernel. We interested in learning function f from given data {zz, 8f 1 1==1- The learning process can be formulated as
N
Σ ((())) B11SI SEH
min
(56)
Let {2p the eigenfunctions of the kernel K. such that
/ ((I,,))a(())(ū)d (xpx(x),
(57)
where ya is the probability measure that generates the data. Following Mercer's Theorem (Rasmussen & Williams 2006), we have that K. admits representation in terms of its kernel eigenfunctions; that is, K(x, ū) = Exzo Mxpx(x))p (ō). Moreover, the solution to the learning problem as well as the target function can be approximated respectively as
P-1
Σ (x)x(z), and (z) - (x)) k=0
fz)))
(58)
k=
where to be consistent with the setup in the previous sections, we have used and p to denote the numbers of modes the target function and the learning solution respectively. We can now define I to be the feature matrix (with components (V)as = (x(x;)) )) so that the kernel regression problem can be recast as the optimization problem
= arg min || V0,- - y 2 + 0110
(59)
For given training data set consisting of N data points, the generalization error for this learning problem can then be written in the same form as (6); that is,
cô (P,p,N) = Eg.5 (x) - fa, (x) (Bx((]] Eg.5 |10p 012
(60)
using the generalized Parseval's identity (also Mercer's Theorem) in the corresponding reproducing kernel Hilbert space.
Popular kernels (Rasmussen Williams, 2006 Chapter 4) applications include the polynomial kernel
K Polymomiaa .) = (afa, .) 1)
(61)
where d is the degree of the polynomial, and the Gaussian RBF (Radial Basis Function) kernel
21 -
Kuusssio (I, exp
(62)
20t
where is the standard deviation. For appropriate datasets, such as those normalized ones that live on the unit sphere sd-1, there is theoretical as well as numerical evidence to show that the feature matrix v has eigenvalues decay fast (for instance, algebraically). This means that for such problems, we also have that the low-frequency modes dominate the high-frequency modes in the target function. This means that the weighted optimization framework analyzed in the previous sections should also apply here. We refer interested readers to Rasmussen & Williams (2006) and references therein for more technical details and summarize the main theoretical results here.
Neural tangent kernel. It turns out that a similar technique can be used to understand some as- pects of learning with neural networks. It is particularly related the frequency bias of neural networks that has been extensively studied (Ronen et al.) 2019)) Wang et al. 2020). It is also closely related to the regularization properties neural networks (Martin & Mahoney 2018). To make the connection, we consider the training of simple two-layer neural network following the work of Yang & Salman 2019) and Ronen et al. (2019). We refer interested readers to Daniely et al. (016) where kernel formulation of the initialization of deep neural nets first introduced. In their setting, the neural network is concentration of a computation skeleton, and the initialization of the neural network is done by sampling Gaussian random variable.
21

---

Published as a conference paper at ICLR 2022
We denote by f two-layer neural network that takes imput vector E R to output scalar value. We assume that the hidden layer has J neurons. We can then write the network, with activation function a, as
M
f(x: = VM
Σ m=1
amd (0+x)
(63)
where θ = [01. ar E RdxM and a = [ai,... " E R are respectively the weights of the hidden layer and the output layer of the network. We omit bias in the model only for simplicity.
In the analysis of Ronen et al. 2019); Yang & Salman (2119). it is assumed that the weight of the output layer a is known and one therefore only interested in fitting the data to get θ This training process is done by minimizing the L loss over the data set {x,, Uj 1=:
N
(
1
Σ
1(x
yj
2
When the activation function is taken as the ReLU function o(z) = max(ar, 0), we can define the matrix, which depends on O
X1X11
02X12X; X22222X2
aMXIMXI
x1
OM X2M
(()) VM
01XNIXN
02XN2XN
AMXNMXN
where Xjm 1if0 2 0 and Xim if 0 x < O. The least-squares training loss can then be written 3 ([ -yl2- A linearization of the least-squares problem around O can then be formulated as
AO arg min (0,)) Ayyle.
(64)
Ae
where Ay := (, is the perturbed data.
Under the assumption that the input data are normalized such that ||x|| and the weight og 1) (1 < k < .), it was shown in Ronen et al. (2019) that the singular values of the matrix (9)) decays algebraically. In fact, starting from initialization Om (O, I²),, this result holds during the whole training process under some mild assumptions
We summarize the main result on the Gaussian kernel and the linear kernel the following theorem. Theorem B.1 (Theorem 2 and Theorem 3 of Minh et al. (2066).. Let X Sm-1, E N and > 2. Let μ be the uniform probability distribution on S ga-1 Then eigenvalues and eigenfunctions for the Gaussian kernel 62) respectively
2 (2) )2) (
b 22/0² --2 1--1//422211111
(65)
for all 2 O, where I denotes the modified Bessel function of the first kind. Each A occurs with multiplicity N (n,, k) with the corresponding eigenfanctions being spherical harmonics of order k on 8d-1 The d 's are decreasing if 2 22/n for the Gaussian kernel (Rasmussen & Williams 2006 Furthermore, d forms a descreasing sequence and
2e
k
A
2e 03
k
A2
Ae
(2k + 2)k+
m-1
(2k: + n
2)*+
The nonzero eigenvalues are
A 2dtn-2 d!
T(d+ I
(66)
(d- v
for the polynommial kernel 61 with S k S d Each d occurs with multiplicity N N(n, k), with the correpsonding eigenfunctions being spherical harmonics of order k on g--1, Furthermore, x forms descreasing sequence and
B1
B2
(A: d + 2
(k d 2
22

---

Published as a conference paper at ICLR 2022
43
01 40
100
130
140
70 100
1.0
200
250
300
Figure 2: Decay of singular values of sampling matrices for the polynomial and Gaussian kernels respectively for the (normalized) MNIST data set. The z-axis represents the singular value index.
The results have been proved in different settings. When the samples are not on S but in the cube [-1, 1 the unit ball R", or the underlying distrubion of the data is not uniform, there are similar results. We refer interested readers to Minh et al. (2006): Rasmussen & Williams (2006) and references therein for more details. In Figure we plot the singular values of the sampling matrix for the polynomial kernel and the Gaussian RBF kernel for the MINST data set.
For the theorem to work for learning with neural networks as we discussed in Section 5 has been shown that the neural tangent kernel also satisfies the required property in different settings. The main argument is that neural tangent kernel is equivalent to kernel regression with the Laplace kernel proved in Chen & Xu (2020). We cite the following result for the two-layer neural network model.
Theorem B.2 (Proposition 5 of Bietti & Mairal (2019)). For any मे E Sn-1, the eigenvalues of the neural tangent kernel KC are neg-tegative satisfying po: M1 > 0, pa = if = 2j + 1 with j 2 1, and otherwise μæ C(n)k-* as k + with C(n) constant depending only on The eigenfunction corresponding to μlg is the spherical harmonic polynomials of degree k.
The proof of this result can be found in Bietti & Mairal (2019). The similarity between neural tangent kernel and the Laplace kernel was first documented in Geifiaan et al. (2020), and rigorous theory was developed Chen Xu (2020).
REFERENCES
S. Amari and S. Wu. Improving support vector machine classifiers by modifying kernel functions. Neural Networks, 12:783-789, 1999.
G. Bal and K. Ren. Physics-based models for measurement correlations. application to an inverse Sturm-Liouville problem. Inverse Problems, 25, 2009. 055006.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063-300770 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the bias-variance trade-off. Proceedings of the National Academy of Sciences, 116: 15849-15854, 2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 114):1167-1188 1800 2020.
A. Bietti and J. Mairal. On the inductive bias of neural tangent kemelss. Advances in Neural Infor- mation Processing Systems, pp. 12893-12904, 2019.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
23

---

Published as a conference paper at ICLR 2022
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning. International Conference on Machine Learning, pp. 872-88888888 881, 2019.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communi- cations, 12(1):1-12, 2021.
Lin Chen and Sheng Xu. Deep neural tangent kernel and Lsaplace kernel have the same rkhs. arXiv preprint arXiv:2009. 100,63,00..088,, 2020.
A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. Neural Information Processing Systems (NIPS), pp. 2253-2252222 2016.
Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprini arXiv:2006.03509, 2020.
H. W. Engl, M. Hanke, and A. Neubauer. Regularization of Inverse Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.
B. Engquist, Ren, and Yang. The quadratic Wasserstein metric for inverse data matching. Inverse Problems, 36:055001, 2020. arXiv:1911 1.iv:1911.06911
A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and R. Basri. On the similarity between the Laplace and neural tangent kernels. arXiv:2007.01580 2020.
V. Isakov. Inverse Problems for Partial Differential Equations. Soringer-Verlage New York, second edition, 2006.
N. Jean, S. M. Xie, and S. Ermon. Semi-supervised deep kernel learning: Regression with unlabeled data by minimizing predictive variance. NIPS, 2018.
J. Kaipio and F. Somersalo. Statistical and Computational Inverse Problems. Applied Mathematical Sciences. Springer, New York, 2005.
Konstantinos Kamnitsas, Daniel Castro, Loic Le Folgoc, Ian Walker, Ryutaro Tanno, Daniel Rueck- ert, Ben Glocker, Antonio Criminisi, and Aditya Nori. Semi-supervised learning via compact la- tent space clustering. In International Conference on Machine Learning, pp. 2459-2468. PMLR, 2018.
A. Kirsch. An Introduction to the Mathematical Theory of Inverse Problems. Springer-Verkee New York, second edition, 2011.
Weilin Li. Generalization error minimum weighted norm and kernel interpolation. SIAM Journal Mathematics of Data Science, 3(1):414-443) 2021.
Zhu Li, lean-Francon Ton, Dino Oglic, and Dino Sejdinovic. Towards a unified analysis of random Fourier features. Journal of Machine Learning Research, 22:1-51, 202
Zhu Li, Zhi-Hua Zhou, and Arthur Gretton. Towards an understanding of benign overfitting in neural networks. arXiv preprini arXiv:2 2021b.
Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, An- drew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differential equations. arXiv preprint arXiv:2010.08895, 2020.
Zhenyu Liao and Romain Couillet, On the spectrum of random features maps of high dimensional data. Proceedingy of the 35th International Conference on Machine Learning, 80:3063-3071, 2018.
Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kemel,, a precise phase transition, and the corresponding double descent. arXiv preprint arxiv:2006.50033 2020.
24

---

Published as a conference paper at ICLR 2022
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A. K. Suykens. Random features for kernel approximation: survey on algorithms, theory, and beyond. arXi::2004.1115, 2020.
Fanghui Liu, Zhenyu Liao, and Johan Suykens.
Kernll regression in high dimensions: Refined analysis beyond double descent. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (PMLR), 130:649-657, 2021.
Chao Ma and Lexing Ying. arXiv:2 1346vvl, 2021.
The Sobolev regularization effect of stochastic gradient descent.
Charles H. Martin and Michael W. Mahoney. Implicit self-regularization deep neural networks: Evidence from random matrix theory and implications for learning. arXi:: 0rX1n:1/10001175vvv 2018.
H. Q Minh, P. Niyogi, and Y. Yao. Mercer's theorem, feature maps, and smoothing. In G. Lugosi and H. U. Simon (eds.), Learning Theory, Lecture Notes in Computer Science, Berlin, Heidelberg, 2006. Springer.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling. and the randomized Kaczmarz algorithm. Advances in neural information processing systems, 27:1017-1025, 2014.
Houman Owhadi and Gene Ryan Yoo. Kernel flows: From learning kernels from data into the abyss.
Journal of Computational Physics, 389:22 47, 2019.
A. Özcelikkale. Sparse recovery with non-linear Fourier features. 2020 IEEE International Confer- ence on Acoustics, Speech and Signal Processing (ICASSP), 2020:5715-5719, 2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pp. 1177-1184, 2008.
C. E. Rasmussen and C. K. Williams. Gaussian Processes for Machine Learning. MIT Press, Cambridge, MA, 2006.
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural net- works for Icarned functions of different frequencies. Advances in Neural Information Processing Systems, 12:4761-4771, 2019.
Shahin Shahrampour and Soheil Kolouri. On sampling random features from empirical leverage scores: Implementation and theoretical guarantees. arXiv: 1XXiv:990300322) 2019.
Bharath Sriperumbudur and Zoltan Szabo. Optimal rates for random Fourier features. Proceedings of the 28th International Conference on Neural Information Processing Systems, 1:1144-1152 2015.
A. Tarantola. Inverse Problem Theory and Methods for Model Parameter Estimation. SIAM, Philadelphia, 2005.
Haohan Wang, Xindi Wu, Zeyi Huang, and Eric P. Xing. High-frequency component helps explain the generalization of convolutional neural networks. CVPR, 2020.
Yuege Xie, Hung-Hae Hsu Chou, Holger Rauhut, and Rachel Ward. Overparameterization and general- ization error: weighted trigonometric interpolation. arXiv preprint htt.:2000060845553 2020.
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks. a1X1v:1907.1059994, 2019.
Yunan Yang, Jingwei Hu, and Yifei Lou. Implicit regularization effects of the Sobolev norms in image processing. 1rXiv:2109.06255 2021.
25


Reviews:
[{"review_id": "sJVB3xC-eX1", "reviewer": "Reviewer_WRNZ", "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": "strengths: solid analysis\n\nmy concerns:\n1. I feel difficult to imagine how the introduction of weight to least squares loss helps to \"deal with noise in the training data\" or introduce a priori information. I hope that the author(s) could provide some motivating application scenarios.\n2. It seems to me (for example, if one studies Theorem 3.1 carefully) that in this paper, the weights for both parameter vector and data points are the same (except that they are raised to different powers, -alpha and -beta, respectively). Prior information in these two spaces could be different. Is there some reason why we use the same sequence of weights?\n3. For the sake of application, are there any guidelines on selecting the weight sequence?", "summary_of_the_paper": "This paper starts from the random Fourier model, generalizes the recent results on weighting the coefficients to adopt weighted least squares loss. Under different settings of noise levels and over-/under- parameterized regimes, error analysis has been provided.", "summary_of_the_review": "Better if the author(s) could provide more motivations and guidelines on how the weight could be selected, and why the same sequence of weights is used for both the sample space and the parameter space.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "s9uR77CEi7y", "reviewer": "Reviewer_vfX6", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n\nThis paper is well-written and easy to follow. The findings of this paper mainly focus on the relationship between generalization and noise under various weighted matrices. For least squares model, the weighted matrices play different roles in under-/over-parameterized regimes. For random features model, the weighted setting is able to minimize the impact of noise.\n\nCons:\n\nOne significant issue I concerned is the one-dimensional data setting, i.e., x_j = 2\\pi j/N,\n which could significantly decrease the value of this work and restrict its findings/observations for a general real-world case. The considered data distribution is quite simple and specific.\n\nRegarding to Eq. (3), this is actually an assumption. It requires that the second-order moment (matrix) of the parameter theta is diagonal and decay fast. Normally, it’s fair to assume the data admitting this, e.g., E(xx’)=\\Sigma for isotopic/covariate data. I do not find any justification for the diagonality assumption on the parameter. Besides, it also requires this matrix decays fast with \\gamma > 0, I understand this setting as the generalization error requires this decay, as given in Eq. (28). Nevertheless, the problem setting is quite specific on a toy model.\n\nAnother issue is that, in Theorem 5.1 for random features model, the generalization error (LHS) is a random variable as it does not take the expectation on the random features (implicitly included in Eq. (22)) ? The RHS is deterministic? This error bound appears a little strange if my understanding was right. If both LHS and RHS are random, a probability error bound is needed.\n\nBesides, it would be best to compare Theorem 5.1 with the following refs that focuses on RFF under noisy data in the interpolation regime.\n\nLi, Zhu, Zhi-Hua Zhou, and Arthur Gretton. \"Towards an Understanding of Benign Overfitting in Neural Networks.\" arXiv preprint arXiv:2106.03212 (2021).\n", "summary_of_the_paper": "This paper studies the weighted least squares, random features model under noise one-dimensional data setting in under-/over-parameterized regime. The derived error bounds demonstrate the impact of noise on the generalization error. Besides, the extension to kernel regression shows that, the selected weighted matrix is helpful to generalization when the RKHS is small (i.e., singular values of \\Psi decay fast).", "summary_of_the_review": "In sum, the problem setting is quite simple, specific, and appears far away from practice settings. The derived results bring in new message and findings but could be not enough to overlook the drawback of problem setting. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nRiS6_Kcnd8", "reviewer": "Reviewer_muho", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The technical contribution is solid and generally of interest to the machine learning community. However, there is only a loose match with the topics of interest according to the CfP of ICLR22, so it may be very different (topically) compared to the bulk of submissions. Not sure how the PC sees that. \n\nSome parts could be underpinned with more information, e.g., I am wondering what implication follows from the statement that \"in the case of α = 0, when β ̸= 0, our result in (14) is slightly different from its equivalence in Xie et al. (2020)\"? ", "summary_of_the_paper": "The authors study generalization errors in Fourier regression scenarios with over and under parameterized models. They also present generalizations to vanilla feature regression. ", "summary_of_the_review": "Strong technical part, perhaps somewhat off topic for ICLR22 but nevertheless still a very good paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KSBkfY5G2hR", "reviewer": "Reviewer_XgS8", "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": "\n The paper is a solid work that provides some substantial extension of the work (Xie et al. (2020)) for a more general weighted scheme and the noise case study.   The main results are given in Theorem 3.1\n\nComments: \n\n1. It would be useful to provide some practical/theoretical motivations on why the model \nassumption given by (3) is reasonable.  \n2.\tOn page 5, could you provide a clear and explicit explanation based on the results of Theorem 3.1 for the stated observation there: \n“the weight matrix $\\Lambda_{[p]}^{-\\beta}$ only matters in the over parametrized regime while …”\n3.\tWould it be possible to provide a figure to describe the double-descent curve or the effect of different weight matrices which is similar to Figure 1 in Xie et al. (2020). \n4.\tIt would be more helpful if there are some explanations about the technical difference/novelty from the previous work. \n", "summary_of_the_paper": " The paper follows and extends the work by Belkin, Hsu, and Xu (2020) and  Liang and Rakhlin (2018) which studies the bias-variance trade-off of the regression/interpolation problem in the under/over-parametrization regions.  In particular, this paper follows the random Fourier model setting in Xie et al. (2020) and analyzed a generalized weighted least-square optimization method that allows the weighting in both the parametrization and data space. The authors derived the generalization error of such weighted least-square framework for the over parametrized and under parameterized regimes and compare them in these two cases.  The general conclusion is that emphasizing low-frequency features provide better generalization ability.  The paper also studies both noise-free and noise cases.  ", "summary_of_the_review": "\n This solid theoretical work is a substantial extension of Xie et al. (2020) by considering weighting in both parameter space and data space. The main contribution compared to the related work is well illustrated.  The paper is also well written. I have no time to read the proofs step by step, but it would be helpful if the authors can highlight the novelty of the proof techniques.   I support its acceptance of this solid theoretical work after the authors can address some of my comments mentioned above. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5pd-LuAp1my", "reviewer": "Reviewer_Koia", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presented weighted least-squares formulation is of interest. Theorem 3.1 gives the generalization error bounds for random Fourier feature model in both under- and over-parameterized regrimes for noise-free setting. Theses results are extended to the noisy setting in Theorem 4.2 and general feature regression in Theorem 5.1. I have some concerns as follows.\n\n1. Is it possible to consider higher dimensional input space (instead of 1) and random sampling points?\n\n2. The weight matrix $\\Lambda_{[N]}^{-\\alpha}$ only matters in the underparameterized regime. Does this mean we should not use it in the overparameterization regime, which should be of more interest? \n\n3. In the overparameterization regime, is it possible to observe the double descent phenomenon?\n", "summary_of_the_paper": "The paper considers a novel generalized weighted least-squares optimization method for the random Fourier feature model and conducts its generalization error analysis in both under- and over-parameterized regimes. The impact of the proposed weight matrices are also discussed.", "summary_of_the_review": "Overall, the paper is well written and technically sound. The results should be of interest to the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers a generalized weighted least-squares optimization method for the random Fourier feature model. Generalization error analysis is carried out under both the over-parametrized and under-parametrized schemes, and under both noise-free and noisy scenarios.

Reviewers generally agree that this is a solid theoretical work that considerably extends previous work (Belkin et al. (2020), Xie et al. (2020)) in the literature and that the paper is ready for publication.

While some reviewers express reservation about the relevance of the work to ICLR, I believe this is a nice work that would be of interest to the machine learning community at large.
Decision: Accept (Poster)