Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper investigates an algorithm for distributed learning with random Fourier features. The main idea is to sample M random Fourier features and split the data into m chunks. Each chunk is processed on a separate machine that outputs a linear hypothesis using the sampled M random features. The hypotheses coming from different machines are then aggregated on the master machine via importance weighting. In particular, each hypothesis is assigned importance weight proportional to its data chunk size (see Eq. 3). The regularization parameter is fixed across different machines. The main contribution of the work is a consistency bound. In comparison to a previous bound on the divide & conquer algorithm (Li et al., arXiv 2019), this one does not require a constant number of machines (in my understanding of the related work section).

##### clarity
The paper is clear and easy to follow. I would say that the related work is fairly well covered and the contributions are appropriately placed in this regard.

##### quality & significance
I have a fundamental disagreement when it comes to the considered distributed setting. In particular, the bottleneck in learning with random Fourier features is not the size of the dataset but the number of features. The computational complexity is linear in the dataset size and cubic in the number of features. Moreover, there are examples of machine learning problems where it is required to use a huge number of features for satisfactory results (e.g., see Kernel Approximation Methods for Speech Recognition, May et al.). Thus, I do not see this direction as significant. After all, the algorithm improves over variable amounting to linear computational complexity. What would be interesting is to use different sets of random features on different machines and then aggregate on the master machine. In that way, one would be tackling the factor contributing to cubic computational complexity.
review_title: ICLR 2021 Conference Paper1362 AnonReviewer1

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the statistical properties of distributed kernel ridge regression together with random features (DKRR-RF), and obtain optimal generalization bounds under the basic setting in the attainable cases.  Numerical results are given for the studied new algorithms. The algorithms and the derived results are new and interesting to me. However, the presentations as well as the citations need some major revision before the publication. 

Some few comments:
- It looks to me that the idea of distributed learning with communication has already appeared in [ arXiv:1906.04870] if not earlier. 
-Page 1. The authors mention that distributed learning has been combined with multi-pass SGD, but they did not cite the related paper [Optimal Distributed Learning with Multi-pass Stochastic Gradient Methods, ICML 2018]
-Page 2. Optimal learning rates were also established for distributed
spectral algorithms in [JMLR 2018, 19(1): 1069-1097] ( or [arXiv:1610.07487]). 
-Page 2 and the other locations.  Optimal learning rates with a less strict condition on the number of local machines were first established in [JMLR 2020, 21(147): 1-63] (or [arXiv:1801.07226]) if not earlier.
-Bottom of Page 6, to my knowledge,  the first one using the concentration inequality for self-adjoint operators to relax the restriction on the number of local machines is [JMLR 2020, 21(147): 1-63] (or [arXiv:1801.07226], or [Optimal Distributed Learning with Multi-pass Stochastic Gradient Methods, ICML 2018]) (if not earlier). 
Also, the first part of Proposition 6 was first proved in [Random design analysis of ridge regression. 2012 COLT] for the matrix case, and later was extended to the operator case in [ On the sample complexity of subspace learning. NeurIPS 2013]
-Finite-sample theoretical analysis about the approximation quality of RFFs has been established in [On the error of random Fourier features. UAI 2015] and [Optimal Rates for Random Fourier Features, NeurIPS 2015.] 
-Numerical results on different data-sets could be given to further exemplify the performance of the algorithm. 
-How do you choose the regularization parameter $\lambda$ in the distributed learning? Will this enlarge the computational complexity?
review_title: This paper studies the statistical properties of distributed kernel ridge regression together with random features (DKRR-RF), and obtain optimal generalization bounds under the basic setting in the attainable cases.  Numerical results are given for the studied new algorithms. However, the presentations as well as the citations need some major revision before the publication. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper analyses generalization properties of distributed kernel ridge regression (DKRR) with random features and communications. It studies optimal learning rates of the generalization bounds both in expectation and in probability. In the case of DKRR with random features, the optimal learning rate in expectation is shown to achieve by relaxing the requirement on the number of partitions from $O(1)$ (Li et al., 2019a) to $O(|D|^{0.5})$ (Theorem 1). Within the same setup of random features, the number of partitions is relaxed to $O(|D|^{0.25})$ guaranteeing optimal generalization performance in probability (Theorem 2). The latter bound $O(|D|^{0.25})$ on partition count is much smaller then $O(|D|^{0.5})$. However, as proved in Theorem 3, allowing multiple communication rounds in DKRR-RF, up to $O(|D|^{0.5})$ partitions can be handled depending on the number of communication rounds. In other words, it can exploit more partitions at the cost of more communication rounds.

The idea of DKRR with random features and communications is a combination of DKRR with random features studied in (Li et al., 2019a) and DKRR with communications studied in (Lin et al., 2020). It seems that the communication strategy and Algorithm 1 presented in section 3 are adaptations from (Lin et al., 2020) handling random feature, which should be properly mentioned and credited.

During the comparison with (Lin et al., 2020), it is mentioned that the letter work required communicating local data $D_j$ among partition nodes. However, I failed to spot it in (Lin et al., 2020), and instead found similar steps of Algorithm 1 in section 2.3 of (Lin et al., 2020), where only gradient information is communicated. Please elaborate on this.

Not being an expert in this narrow field, I think the improvements are essential and would be helpful for the associated community. The paper is well written with fair amount of discussion comparing with the results and proof techniques of recent works.
review_title: Non-trivial improvements combining distributed iterative learning and random features for KRR

Meta-review: The focus of the submission is kernel ridge regression in the distributed setting. Particularly, the authors present optimal learning rates under this assumption both in expectation and in probability, while they relax previous restrictions on the number of partitions taken. The effectiveness of the approach is demonstrated in synthetic and real-world settings.

As summarized by the reviewers, the submission is well-organized and clearly written, the authors focus on an important problem, they present a fundamental theoretical contribution which also has clear practical impact. As such the submission could be of interest to the ICLR and ML community.
Decision: Accept (Poster)