Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.  
main_review: 
 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

Comments: 

1. It would be useful to provide some practical/theoretical motivations on why the model 
assumption given by (3) is reasonable.  
2.	On page 5, could you provide a clear and explicit explanation based on the results of Theorem 3.1 for the stated observation there: 
“the weight matrix $\Lambda_{[p]}^{-\beta}$ only matters in the over parametrized regime while …”
3.	Would 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). 
4.	It would be more helpful if there are some explanations about the technical difference/novelty from the previous work. 

summary_of_the_review: 
 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

1. Is it possible to consider higher dimensional input space (instead of 1) and random sampling points?

2. 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? 

3. In the overparameterization regime, is it possible to observe the double descent phenomenon?

summary_of_the_review: Overall, the paper is well written and technically sound. The results should be of interest to the community.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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).
main_review: Pros:

This 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.

Cons:

One significant issue I concerned is the one-dimensional data setting, i.e., x_j = 2\pi j/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.

Regarding 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.

Another 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.

Besides, it would be best to compare Theorem 5.1 with the following refs that focuses on RFF under noisy data in the interpolation regime.

Li, Zhu, Zhi-Hua Zhou, and Arthur Gretton. "Towards an Understanding of Benign Overfitting in Neural Networks." arXiv preprint arXiv:2106.03212 (2021).

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

Some 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_review: Strong technical part, perhaps somewhat off topic for ICLR22 but nevertheless still a very good paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: strengths: solid analysis

my concerns:
1. 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.
2. 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?
3. For the sake of application, are there any guidelines on selecting the weight sequence?
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.
review_title: null

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)