Effective Distributed Learning with Random Features: Improved Bounds and Algorithms
Authors: Yong Liu
Jiankun Liu
Shuqiang Wang
Venue: ICLR 2021 Poster (2021)
Keywords: Risk bound
statistical learning theory
kernel methods

Abstract: In this paper, we study the statistical properties of distributed kernel ridge regression together with random features (DKRR-RF), and obtain optimal generalization bounds under the basic setting, which can substantially relax the restriction on the number of local machines in the existing state-of-art bounds. Specifically, we first show that the simple combination of divide-and-conquer technique and random features can achieve the same statistical accuracy as the exact KRR in expectation requiring only $\mathcal{O}(|\mathcal{D}|)$ memory and $\mathcal{O}(|\mathcal{D}|^{1.5})$ time. Then, beyond the generalization bounds in expectation that demonstrate the average information for multiple trails, we derive generalization bounds in probability to capture the learning performance for a single trail. Finally, we propose an effective communication strategy to further improve the performance of DKRR-RF, and validate the theoretical bounds via numerical experiments.

Published as a conference paper at ICLR 2021
EFFECTIVE DISTRIBUTED LEARNING WITH RANDOM FEATURES: IMPROVED BOUNDS AND ALGORIHTMM
Yong 1, Jiankun Liu "aum"r,huuinnn Wang'
!Gaoling School of Artificial Intelligence, Renmin University of China BBiijng Key Laboratory of Big Data Management and Analysis Methods iInstitute of Information Engineering, Chinese Academy of Sciences "Shenzhen Institutes of Advanced Technology. Chinese Academy of Sciences liuyonggsai @ruc. edu.cedu.cn liujiankun @iie. acc,,, sq. wang siat.ac.en
ABSTRACT
In this paper, we study the statistical properties of distributed kernel ridge regres- sion together with random features (DKRR-RFF -FF), and obtain optimal generalization bounds under the basic setting, which can substantially relax the restriction on the number of local machines in the existing state-of-art bounds. Specifically, we first show that the simple combination of divide-and-conquer technique and random features can achieve the same statistical accuracy as the exact KRR in expectation requiring only O([D)) memory and ((D))15) time. Then, beyond the generalization bounds in expectation that demonstrate the average information for multiple trails, we derive generalization bounds in probability to capture the learning performance for single trail. Finally, we propose an effective communi- cation strategy to further improve the performance of DKRR-RF, and validate the theoretical bounds via numerical experiments.
INTRODUCTION
Kernel ridge regression (KRR) is one of the most popular nonparametric learning methods (Vapnik
2000).
Despite the excellent theoretical guarantees, KRR does not scale well in large scale settings
because of high time and memory complexities (Liu et al., 2013 2014 4 (017] 2018 8 2020b Liu &
Liao
2015 Li al.) 2018 2019c). Distributed learning (Zhang et al. [201 Hsich et al. 2014 Chang
ct al. 2017b:
Li et al. [2019b]]] Lin et al. (2020), random features (Rahimi & Recht 2007 Sutherland
Schneider 2015 Rudi & Rosasco 2017; Rudi al. 2018 Liu et al. 2000al Avron et al.) 7a
Yu et al. 2016 Jacot et al. (2020). and Nyström methods (Drinass & Mahoney 2005 Ding & Liao
2012. Yang | [ Camoriano et al.) [016 (Si et al.) | Musco & Musco 2017] Kriukova
al. 2017) are the most widely used large scale techniques to address the scalability issues. Recent statistical learning works on KRR together with large scale approaches demonstrate that these large scale approaches
not only obtain great computational gains but also can guarantee the optimal theoretical properties. such as KRR with divide-an -atel----n---uuuuerree (Zhang et al. 20013 2015 Chang et al.,
2017b a. Guo et al. 2017 Lin et al. 2017 Li al. 2019h d) Lin al. (020). with random features (Rudi & Rosasco 2017 Li et al. 2019e
2019e|CCrrratee Carratino et al. 2018 Yang et al. 2012)) and with Nyström
methods (Bach 2013] Alaoui & Mahoney 2015 Rudi al. 2015 2017 Ding et al. (020)).
The combinations of distributed learning and other large scale approaches are very intuitive but effective strategies to further improve the effectiveness, such as distributed learning with gradient
descent algorithms (Lin & Zhou 2018 Richards et al.] 2020)) with multi-pass SGD (Lin & Rosasco 2017 Lin & Cevher 2018: 20000 with random features (Li al.) 2019b), and with Nyström methods (Yin et al. 2020). The optimal generalization performance of these combining approaches has been studied, however, the main theoretical problem is that there is a strict restriction on the number of local machines. For sample, in (Lin & Zhou| 2018: Li et al.) 2019b] Yin et al.) 2020), to guarantee the optimal generalization performance in the basic setting, the upper bounds of the local machines are restricted to be a constant, which is difficult to be satisfied in real applications.
Bott authors contributed equally to this work
1 "ooresponniig author

---

Published as a conference paper at ICLR 2021
In this paper, we aim at enlarging the number of local machines by considering communications among different local machines. This paper makes the following three main contributions. Firstly, we improve the existing state-of-art results of the divide-and divide-and-conquer technique together with random features. We prove that the optimal generalization performance can be guaranteed even the partitions reach O ((V)D)) which are limited to a constant (11)) for the existing bounds in the basic setting, [D] the size of the data sets. Secondly, essentially reflect the generalization performance, beyond the minimax optimal rates in expectation, we derive optimal learning rates in probability, which can capture the learning performance for single trail. Finally, we develop a communication strategy to further improve the performance of our proposed method, and validate the effectiveness of the proposed communications via both theoretical assessments and numerical experiments.
Related Work The most related work includes the statistical analysis of distributed learning and random features.
Distributed learning. Optimal learning rates for divide-and and-oo-uu KRR in expectation were established in the seminal work (Zhang et al. 2013] 2015). An improved bound was derived in (Lin) et al. 2017) based on a novel tool of integral operator. Based on the proof techniques proposed in
(Zhang et al. 2013 2015 Lin et al. 2017). optimal learning rates were established for distributed
spectral algorithms Guo et al. [0117] Blanchard & Mücke [2018] 8 Lin & Cevher 2020), distributed
gradient descent algorithms (Lin & Zhou 2018: Richards et al.] (020), distributed semi-supervised
learning (Chang al. 2017b), distributed local average regression (Chang et al.
2017a Lin & Cevher
2020), localized SVM (Meister & Steinwart 2016), etc. Some other communication strategies for
distributed learning have been provided, see e-g. (Fan et al. 2019; Li et al. 2019a Lin & Cevher 2020 Li et al. 2020),, and references therein. The theoretical analysis mentioned above shows that the divide-and-cove and-conquer learning can achieve the same statistical accuracy as the exact KRR, however, there is strict restriction on the number of local machines. The optimal learning rates with a less strict condition on the number of local machines for distributed stochastic gradient methods and spectral algorithms were established in (Lin & Cevher 2020). In (Lin et al. 2020), they considered the communications among different local machines to enlarge the number of local machines. However, the communication strategy proposed in (Lin et al. 2020) based on operator representation, which requires communicating the input data between each local machine. Thus, it is difficult to protect the data privacy of each local machine. Furthermore, for each iteration, the communication complexity of each local machine is O(DD)d) [d),, where d denotes the dimension, which is infeasible in practice for large scale data sets.
The generalization bound of random features was first proposed in (Rahimi & Recht, 2008), which shows that ((D)) random features are needed for 0(1/ /ID) learning
Random Features.
rate. Some works further studied its theoretical performance (Cortes et al.) 2010 Yang al. 2012
SStherland & Schneider 2015), (Sriperumbudur & Szabó) 2015 Bach 2017 Avron et al. 201 70).). b). By
applying the standard integral operator framework (Smale Zhou| 2007 Caponnetto Vito 2007
the optimal generalization bounds of KRR with random features were established in (Rudi & Rosasco
2017), which requires only O( D(V[D) [D] log( random features. To decrease the size of random features, an improved approach was proposed based on novel leverage score sampling strategy (Rudi et al. 2018). Sun et al. (2018) extended the result of (Rudi & Rosasco, 2017) to SVM. In (Li ct al. 2019e), they further devised a simple framework for the unified analysis of random Fourier features, which can be applied to KRR, as well as SVM and logistic regression. To further improve the effectiveness, recently, Li et al. (2019b) considered the simple combination of divide-and-conquer and random features. However, to guarantee the optimal generalization performance, the number of local machines should be restricted to a constant, degenerating it into a single random features-based large scale KRR.
2 BACKGROUND
In a standard framework of supervised learning, there is a probability space X x y with an unknown
distribution p. where X' is the input and )' is the output space. The sample set D = {xx, }=)};, of size n is drawn i.i.d from X' x y with respect to p. Let K : X x X + IR be a Mercer kernel, and Hx be its reproducing kernel Hilbert space (RKHS) (Steinwart & Christmann 2008 Vapnik 2000). and assume that K (xx, x') < K, Vx, x' E X. Throughout, we will denote the inner product in 7x by (s ) K, and corresponding norm by ||. -||x.
2

---

Published as a conference paper at ICLR 2021
Kernel Ridge Regression (KRR)
KRR is one of the most popular nonparametric learning methods (Shawe- Taylor & Cristianini 2000
Vapnik 2000), which can be stated
JD.
arg min JEHK
E (f(x.)
yo)² + fll
D
where À > O is the regularization parameter,
[D] is the size of D. Using the representation
theorem Shawe-Taylor & Cristianini 2000; Vapnik 2000), SD. can be written as LD.A (x)
Ee o; (x;,,;; x) with (KD - -1)- where KD Doj [Ko(x;, x;)) is the D x D
[P]
kernel matrix and yD = To (yr,,..,,pp)))"
Despite the excellent theoretical guarantees (Blanchard & Krämer 2010 Caponnetto & Vito 2007 KRR requires ((2 memory to store Kp. and O(D))) time to solve inverse K + AI, which
is infeasible for large scale settings.
KRR with Random Features (KRR-RF)
Assuming the spectral measure has density function e(-). the corresponding shift-invariant k- ernel can be written as K (xx, x') = fg ( w/ ( ((w))) where / X' x - R is continuous and bounded function with respect to w and x. The main idea behind random Fourier features is to approximate the kernel function K (xxx')) by its Monte-Carlo estimation RRahimi & Recht 2007 (x,xxx)) = M. En e0 wxx wi wi) = (& (x), (xr()))), where ΦM (x)
1
VM (x,,),1),... (x, The solution of KRR with random features can be
written as
fM.D,)(X) = w WM (x) with WM.DA = - S.MD T T
MDD + XI) + M.DND,
where MMD 1 ( ( and YD ( DIDD)
ViDi
KRR-RF requires (M) to store M.D. ((M)) and (M time to solve the inverse of ( MM TT M,D + XI) and the matrix multiplication M, M,D. respectively. Thus, the total space and time complexity of KRR-RF are (MM)D)) and O(M2 (D)), M < (D), respectively.
Distributed KRR with Random Features (DKRR-RF)
Let (Dj pe be m disjoint subsets with = Uن=12 Dj. The distributed KRR with random features (DKRR-RT RF) is defined as
'Dj D
M,D Σ
fM.D,,A:
(3)
where JAM,D,.(x)) WH.D, .A A (x) with W. = + M.D, M.D. - M,,,,, The space complexity, time complexity and communication complexity of DKRR-RF for each local machine are (MM(D))), O(M M2ID,)) and O(M), respectively.
T
3 DKRR-RF WITH COMMUNICATIONS (DRKK-RF-CM)
In this section, we will present an effective communication strategy to enlarge the number of local machines. We first give the motivation of our communication strategy, and then propose communication based method, called ORKK-RF-CCL The proposed communication strategy are adaptations from (Lin al. 2020) to avoid communicating local data among partition nodes.
Motivation. Let IM.DA. R + R be gM.D.>(W) := | TT.
MDD + AI $M.DND. One
can see that 2gM.D. (w)) is the gradient of the empirical risk of (D) Σ E(x.NJDD (wT TT (x;) - v1)2-
A| ?/2 on w. From Eq 2 we know that for any w, the following equation holds:
$ P T M.D + AI]
[ AI LM.DND
WM.DA
(4)
[ M.D + XI]
9M.D..(W).
3

---

Complexity analysis. Space complexity: each local machine only needs store + M.D,, and the local gradient 9Mr,D,A.. thus the space complexity of each local machine is (D + M) = (M))) Time complexity: for each local machine, we only need to compute the matrix multiplication M, $ M,D, and the inverse of M, $.1 P M, + AI once. For each iteration, we need to compute the local gradient 9M.D, , and Bj for each local machine. Therefore, the total time complexity of each local machine is O(M3 + M2|D, + pM(D,1), where is the number of communication; Communication complexity: for each iteration, we only communicate the local gradient JM,D,.A and G, to the global machine, and receive the gradient JM and w!-1 M,D.A from the global machine, so Published as a conference paper at ICLR 2021
Algorithm Distributed KRR with Random Features and Communications (DKRR-RF-CM)
Initialize: w M.D =
for ( to p do
Local machine: compute the local gradient 9M.D,, (W M.D.A,, and communicate back to GM.
Global machine: get the global gradient 9M,D.A ( M.D.A) Σラ= 12 9M.D
( M.D.D.) and
communicate each local machine.
Local machine: compute 3)- cate back to the global machine.
1 M.D.D 2
Al
D...D.WWM,,.... and communi-
M,D,
Global machine: compute w WMrDDA local machine.
wh1 W.DDA
P TD Σラ BJ- and communicate to each
end for
Output: w M.D.A and M.D... (w (.M.D..) (M(+))
Define w M,D,A
W M,D, it easy to verify that
D
D2J
w M,D.A
+ M.D,
T AI]
M.D
9M.D),A(W).
(5)
D
Comparing 4 and and noting that the global gradient 9M.D.> (w) can be achieved via the commu- nications of each local gradient 9M,D,,a Le., 9M.D,A(W) Σÿ= [Pyl (Di IM.D), (w), thus,
consider the following Newton Raphson iteration-based communication strategy:
w WM.DD
wt-1 M.D.A
Σ f=1
D2j D
M,D T PM.,, M.D, + AI]
(6)
We propose iterative procedure implement the communication strategy Eq 6 which can be broken down into 4 steps. first, each local machine computes the local gradient and communicates back to the global machine. Then the global machine computes the global gradient based on the local gradient, and communicates it to each local machine. the third step, each local machine computes 3/-1. and communicates back to the global machine. Finally, the global machine obtains the solution w W. More details can be seen Algorithm
the total communication complexity is O(pM).
see that the number of the communication p satisfying S M or S (Dz). then the time and space complexity of DKRR-RF-CO are the same DKRR-RF. Only the communication complexity is slightly increased from ((M) O(pM).
Remark 1. From the complexity analysis above,
THEORETICAL ANALYSIS
In this section, we analyze the generalization performances of DKRR-RF and DKRR-RF-CM. The performance of the algorithm is usually measured by the expected risk E() (xx)(f(x) dp)x y). The optimal hypothesis fHx in Hx is denoted by fHx = arg E(f), and we assume SHx exists in the paper.
4

---

Published as a conference paper at ICLR 2021
4.1 OPTIMAL LEARNING RATE FOR DKRR IN EXPECTATION
Theorem 1. Suppose that (xx(x, w)l S. T almost surely, T E [1, oo) and ly S. 1 2([ 3).
[Pal ... I..1Dmb the number of partitions and the number of random features M respectively correspond m S VTDi and M 2 VIDI, then, for every 6 (0, 11, with probability least 1 we have ([ 8(Hxx) O (IDI- - log (1/5))
log()))))
From Theorem 1 one can see that if m S VID and M 2 VPD, the learning rate of the general-
ization bound can reach (1/ / (DI), which is optimal in minmax sense (Rudi & Rosasco 2017 Caponnetto & Vitol 2007). It means that, in this basic setting, as long as the number of partitions and random features are in order D ((D)), the corresponding ridge regression estimator has optimal generalization properties. The assumption of ly] can be related to the Bernstein condition or moment assumption (Blanchard & Krämer 2016). but for simplicity, in this paper, we only consider that y is bounded.
Optimal learning rates for divide-and-conquer KRR in expectation have been established in (Zhang ct al. 2013 2013; Lin et al. 2017), etc. However, there is strict restriction on the number of local machines m. Specifically, in (Lin et al. (017)) to reach the optimal rate, m should to restrict to constant m (1). In (Li et al. (011b), the authors have studied the generalization performance of the combination of divide-and-conquer technique and random features. Using the same setting as Theorem
(that is r = 1/2 and y = Theorem of Li et al. (019b)), they prove that, M 2 [ and m S S2(1), then EjE(JRr,,,)) - E(HH)) O(I log (1/5)). It means that to guarantee the optimal generalization properties, the number of partitions should be restricted to constant, but for our result is O /D). In (Li et al. 2019b), they also considered using the unlabeled data to enlarge the number of partitions. They have proved that (see Corollary 12 of Li et al. (019b)
for detail), if M Z vIDI and m S |D'1/|P), then ( - ) = O( log (1/8)).
E(Hxx
where D* is the dataset includes both labeled and unlabeled data. Thus, if we want the number of
partitions m to reach !! (D)) as the same as our Theorem | the size of [D*| should be 2 / )D)
times of [D]. In this case, the data size of each local machine is [D] |2/ / //D). so the time and space complexity are the same as KRR with a single random feature technique.
4.2 OPTIMAL LEARNING RATES FOR DKRR IN PROBABILITY
Note that E[E M. M.D..)) -((xx) B - fMx 1221 Caponnetto & Vito 2007). thus Theorem proposes the optimal learning rate in expectation, which demonstrates the average information for multiple trails, but may fail to capture the learning performance for a single trail. To essentially reflect the generalization performance for single trail, we derive the optimal learning rate in probability:
Theorem 2. Under the same assumptions as Theorem I
If 2((P)- |Di] ... I.
m $ I and M 2 |D]$, then, for every E (0, 1}, with probability at least - ó, we have
M.D. fuN l| o [DI- logoo (1/8)-
To guarantee the optimal generalization properties in probability, the number of partitions should be restricted to ((DD) which stricter than (([ (/2) in Theorem [ This because the generalization error in expectation can be decomposed into approximation error, sample error and distributed error (more details can be seen Proposition I Appendix), but the error decomposition in probability is not easy to separate distributed error in probability to control the number of local machines. The derive the optimal learning rate, we provide a novel decomposition, please see details in Proposition
9 in Appendix.
The following result demonstrates that the proposed communication strategy can enlarge the number of partitions in probability.
Theorem 3. Under the same assumptions as Theorem I If > 2(D |D,) = ... |.ml.
2 and M 2 |D| then, for every 8 E (0, 1), with probability least 8, we have
m
5

---

Published as a conference paper at ICLR 2021
Table 1: Computational complexity required by different algorithms for the optimal learning rate (L))V(D) in the basic setting. Logarithmic terms are showed.
Methods
Partitions
Rundorn M
Types
Space
Time
Communication
KRR
Capocnetio
Vito
2007
Ia probubility
[D]
KRR-XF
Rodi
Dj0.6 D
probability
[D]
KRR-
KRR-Vyumm Rodi of
2014
In prolubility
13 1.5
[D]
DKRK
2015
expectation
(2)
[D
| 0..
DKRR
Tinetal Moz1
In prolubility
[D
1.5
(P] 2:25
[
Pe1
Stxr 3)
DKRR-CM
Ilin
2020
[D] S(P+2y
In probubility In expectation
[P] PT2
(D] 2[P+2]
pdl
DKRR-BI RF
al.
20196
2(1)
D
[P]
[D]
|D 0.5
DKRR.RF
Ilbeorem
D
expectation
(>)
[D
| 0.5
DKRR- RF (Ibeurem
(D)0.25
DD
In probubility
1.25
1:70
|D 0.3
2
3p17
DKRR-FR OKRR-RF-CM (Theorem
[D] 31p
1D
In probubility
[>
(D)
P/D|0.3
PL.... SMK p-th iterations.
O (1/6)) where M.D.D.. is returned by Algorithm 1
under
Compared Theorem 3 with Theorem 2 clear that the proposed communication strategy can relax the restriction from f (1D) 171) to Ω (TD((+))((((+22111 Note that is monotonically increasing with the number of communications which can demonstrate the power of the proposed communications. When p + oo, the partitions can reach (VvDi), which is the same as the generalization bound expectation.
In the main text of this paper, we only give the optimal rates of DKRR-RF in the basic setting. The fast learning rates can be achieved under favorable conditions, see in Appendix.
Remark 2.
Remark (The Significance of Distributed Learning for RF). At first glance, it seems that the bottleneck in learning with random Fourier features featuress is not the size of the dataset but the number of features. However, from (Rudi & Rosasco 2017), one can see that we only requiring O( ( random features to guarantee the optimal performance, so the total computational complexity O(M + D2 = ((D( Thus, the computational bottleneck in learning is not only the size of random features, but also the size of dataset. If we don't It consider reducing the size of the computational complexity is [D] in the busic setting, which is not suitable for large scale problems. Distributed learning is one of the most popular methods to reduce the size of dataset. The distributed learning bring the distributed error, but decrease the variance of the model modelZhang 2.15). Thus, how to choose an appropriate number of partitions to trade off the distributed error and the variance guarantee the optimal performance is very interesting and significant direction.
al. (2013
4.3 COMPARED WITH THE RELATED WORK
Comparisons of the Time and Space Complexities
Table T reports the statistical and computational properties of the related approaches and our the- oretical findings under the basic setting. We see that our DKRR-RF can guarantee the optimal generalization performance in expectation only requiring [D] memory and |D] 2.5 time, which is more effective than other methods. For DKRR-RF-CH. generalization performance in probability requiring less complexity than the communication based method of DKRR-CM (Lin et al. 2020).
also that it guarantee optimal
Remark 4. (Rudi et al. (017), the authors considered combining the Nyström method and preconditioned conjugate gradient (PCG) (Cutajar et al. (016) to scale up KRR. As far as we know, is the only existing work that can guarantee optimal statistical accuracy, only requiring (D) memory and (D) 1.5 time for KRR. In this paper, we consider combining distributed learning and random features, a completely different path from (Rudi et al.) (017). Note that in our proposed method. we need to compute the inverse of 4 M.D. & M,D + XL, which requires [D]L5 time. Inspired by (Rudi also adopt PCG to avoid the inverse calculation, which can further speed up
et al. 2017), our proposed DKRR- RF-CM. The combination of DKRR-RE RF-CM and PCG may open a path to reach the linear time complexity for optimal learning rate.

---

Published as a conference paper at ICLR 2021
Novelty and Proof Techniques
The most related works of our paper are (Li et al. 2019b). (Lin et al. 2020) and (Rudi & Rosasco 2017h. We discuss the novel techniques adopted to derive the improved results compared with them.
Compared with (Li et al. 2019b). (a) To derive the learning bounds, 2M,D == ll(OM
X1)-1/2(CM - (Crr + 1/)-1/211 is required to be estimated, where Cm and CM.DD are self-adjoint and positive operators defined in Definition (see in Appendix). In (Li al. 2019b), they
used a classical approach from (Chang et al.] 2017b] Guo et al. (017) to estimate MM (see Lemmas
21 and 22 in (Li et al. 2019b), and obtain that QM.D S VA ICCM (M, + XT) 1/2
(L/A|D] + (A)////))) where (A)) is the effective dimension defined in Assumption (see in Appendix). However, in our paper, we directly estimate QM.D based on the concentration in- equality for self-adjoint operators (Rudi& & Rosasco 2017, Lin & Cevher 2020 2018 Caponnetto &
Yao 2006) and prove that QM.D ((1((ID)) + (I/(A (see in Proposition (6) Thus, our estimation of QMID is v (A( tighter than that in (Li et al. 2019b). This is the one of the key reasons why can substantially relax the restriction on the number of local machines compared 2019b): (b) We not only present the bounds in expectation, but also in probability. To derive the tight bound in probability, we provide new decompositions of D. L.I, and || M.D.A - w warl please see Proposition 9 in detail. As far as we know, these decompositions are novel; (c) We also consider the Newton Raphson itcration- based communication strategy. To derive the improved
with (Li et al.
bounds with communication, we introduce novel decomposition of Il/M... - D., p.ll lp (see in Proposition 10
Compared with (Lin et al., 2020). (a) In (Lin al. 2020), they also considered communication strategy to enlarge the number of local machines. At first it seems that it only need to communicate the gradient information, but it should be noted that the gradient information is based on an operator representation (see (7) in (Lin et al., (020)), which is usually infcasible in practice. The authors present a realization for the proposed strategy by communicating the data among each local machine, see in Appendix B (page 34 in (Lin et al., (020), step 1). Thus, the data privacy of each local machine is difficult to be protected. Furthermore, since it requires communicating data Dj. J = 1...., m, among each local machine, for each iteration, the communication complexity of each local machine is O(DD)d) /d), which is too high for large scale data sets. However, the communication strategy proposed in this paper only requires communicating the gradient JM.D,. (w (wi-1 (,) and proposed strategy do better
the model parameters gy rather than the data, therefore privacy protection. Moreover, the communication complexity is only ((M) for each local machine, M < (D), which is suitable for large scale data sets; (b) At first it seems that the proof techniques of (Lin et al. 2020) can be easily extended to our paper, but it is not true. If we use the same proof technical of (Lin et al. 2020), we can only obtain that [ SMAlle = [[LLM - AT)- - (fp fM)l))l (((I/(VX/D))+ + (V(A)/ fas. leallll /A), where fL SMrA and fp are defined in Definition 12] Combing with Proposition one can only obtain that [l.fM.D.A - fM.llee = ((1/A(D) + (A)A/D) I|p fM.illa). However, in our paper, we introduce new decompositions of [, - fM.Allo and [M - fMr ll (see Propositions ? and 3 in detail), and further obtain that [| - fl,ill ((1/(V(I)) + (I
SAs.Allp) (see in Proposition 4. which is ((1/VA) tighter than the directly use of the techniques of LLn et al. 2020 The novel decompositions Il,f,r - fMLlll and [|. - MM.DD,lle are the
key reasons why we can guarantee the optimal performance even under m (D)(D)) We only
give an example here, but the novel decompositions have also been embedded in Propositions 5
10 etc.
Compared with (Rudi & Rosasco 2017). (a) We study the statistical properties of the combination of distributed learning and random features, but in (Rudi & Rosasco 2017). they only consider random features. As mentioned above, to estimate the tight bound of the distributed error, we introduce a novel decomposition of IIMM - fM.D.>ll to derive the tight bound in expectation, and novel decompositions of [ (b) The combination not only brings distributed error, but also brings some other problems. If you compare the proofs of (Rudi & Rosasco| (017)) with these of our paper in detail, you can find that the decompositions of (Rudi& & Rosasco 2017 and ours are very different.
D. and [ - JM, to derive tight bounds in probability;
7

---

Published as a conference paper at ICLR 2021
DR7R 93
DERA 11 CH
0408-60-04 OX
CRRA- CH
3.203
30005
58011
52
53 60 10
10
20
52
90
simulated data, 9 =
(b) simulated data, q 2,
Figure 1:
The mean square emror rate the test set with different partitions KRR. DKRR-RF and our DKRR-RF-CM. # represents the number communications.
Overall, we improve the existing state-of-art bounds in expectation, and provide novel communication- based distributed bounds with RF in probability. Moreover, we introduce some novel techniques and decompositions to substantially relax the restriction on the number of local machines, which are non-trivial extensions (Li et al. 2019b Lin et al. 2020 Rudi Rosasco, 2017).
5 EXPERIMENTS
In this section, validate theoretical findings by performing experiments both simulated and real datasets.
Numerical Experiments. Inspired by numerical experiments in (Rudi & Rosasco 2017 Li al. 2019e), we consider spline kernel of order q: (x, x') = 1+
D =+ the marginal distribution of X' is uniform [0.1], then K2, (x, x') = fo e'(x w w))(xx w )(w )dw, where (x, w) = Kg (x, w) and g(w) is also uniform on [0,1]. The random features of the spline kernel are Φ (x) = (1,(x, wi).... .... (,,,,,(xx WM)) /T/M/ According Theorem
cos 1os(2mk(x x x')) (124 If
and we set the size of the random features to be = VDD, and fine tune À around 1D/2 using 5-fold cross validation the tuned set is (2-5, 12-5,2-3 ..... 1 We let the target function f. be a Gaussian random variable with mean f (, 0) and variance x² 0.01.
We generate 10000 samples for training and 10000 samples for testing. We use the exact KRR as a baseline, which trains all samples in batch. We compare our proposed DKRR-RF-CM (p 2, 4, 8) with KRR and DKRR-RF. We repeat the training 5 times and estimate the averaged error on testing data. The mean square error on the test set with different partitions is given in Figure Ta. b), which can be summarized as follows: 1) When m is not too large, the distributed methods (DRKK-RF and BORKK-FF-CM are always comparable to original KRR. There exists an upper bound of m, when larger than it, the eтror increases dramatically and is far from the original KRR. This verifies the theoretical statement in Theorem [ and 2) The upper bound m of DKRR-RF-CO RF-CM is much larger than DKRR-RE RF. This result is aligned with Theorem 3 which demonstrates that the proposed communication strategy can enlarge the upper bound m:; 3) The upper bound m of DKRR-RF-CM monotonically increases with the number of communications, which verifies Theorem B
Real Data. In this experiment, we consider the performance on real data. We use publicly available datasets from LIBSVM Date The empirical evaluations with Gaussian kemnel, exp 1app--1xx -x|| are given in Figure 2 where the optimal a and À are selected by 5-fold cross-validation. a E (2',
and the number of random features is 2 2 100 - -8...... 10). {2 (2-5, 2-3 .....25): 2,,......22 |
Becauus of the selection of the optimal À using the 5-fold cross validation, the computational complexity should enlarged. However, should noted that even plain methods, tuning the optimal is also required, which will enlarge the computational complexity as well. hhtp://www.esic.mm wdw.t////ciiii/iiiss...
8

---

Published as a conference paper at ICLR 2021
38a
0,2243
IK38-F-0X
D6-4-AFCM-
0,2205
SX38-FF-0 v3
3,174
0.0201
2.172
0.0305
0.2303
0.1385
N Bldsa
N Mocks
36a
spaco.co ca
5.174
DORA RF
3.520
3.530
2.45
3.536
2142
5.836
D.33 R7
Sloces
abalone
5.4
60-
5.2
DKAR-FF EKAR-BF-CK
60-
DKAR-BF-CK
4.6
44-
4.2
40
Figure 2: The mean square error or error rate on the test set with different partitions DKRR-RF and our DKRR-RF-CH minist, a8a, a6a, space-ca, cpusmall and abalone. # represents the number of communications.
From Figure 2, one can find that: 1) our DKRR-RF-CM are better than the original DKRR-RF on all data-sets; 2) the larger the iterations of the communication, the better the performance. The above results demonstrate that our communication-buse DKRR-RF is effective.
CONCLUSION
In this paper, we study the generalization properties of the combination of distributed learning and random features for ridge regression. We first improve the existing results of divide-and-conquee KRR with random features in expectation. Then, beyond the expectation, we derive generalization error bound in probability. Finally, we propose novel effective communication strategy further improve the learning performance of the combination method, and demonstrate the power of communications via both theoretical assessments and numerical experiments. Our results may open several venues for both theoretical and empirical work: (a) combine the approach with gradient algorithms such as preconditioned conjugate gradient Avron et al. (2017a) and multi-pase cilti--pass SGD (Carratino et al. 2018 Lin & Cevher, 2018 2020); (b) replace synchronous distributed methods with asynchronous ones
Suresh et al. 2017): (c) consider the loss functions other than quadratic loss (Li et al. 2019e).
Acknowledgment
This work was supported in part by the National Natural Science Foundation of China NO. 62076234 and the Beijing Outstanding Young Scientist Program NO. BJJWZYJH01 100020009..

---

Published as a conference paper at ICLR 2021
REFERENCES
Ahmed Alaoui and Michael Mahoney, Fast randomized kernel ridge regression with statistical guarantees. Advances Neural Information Processing Systems (NeurIPS), pp. 775-783, 2015.
Miguel Arcones. A Bemssten-type inequality for U-statistics and U-processes. Statistics & probability letters, 22(3)239-247, 1995.
Haim Avron, Kenneth Clarkson, and David Woodruff. Faster kernel ridge regression using sketching and preconditioning. SIAM Journal on Matrix Analysis and Applications, (8(4):1116-11 (138,, 2017 7a.
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp- 253-262, 2017b.
Francis Bach. Sharp analysis of low-rank kernel matrix approximations. In Proceedings of the 26th Annual Conference on Learning Theory Conference on Learning Theory (COLT), pp. 185-209, 2013.
Francis Bach. On the equivalence between kernel quadrature rules and random fekernel expansions. Journal of Machine Learning Research, 21:1-38, 2017.
Gilles Blanchard and Nicole Krämer. Optimal learning rates for kernel conjugate gradient regression. In Advances in Neural Information Processing Systems (NeurIPS), pp. 226-234, 2010.
Gilles Blanchard and Nicole Krämer. Convergence rates of kernel conjugate gradient for random design regression. Analysis and Applications, 14(6):763-794, 2016.
Gilles Blanchard and Nicole Mücke. Parallelizing spectrally regularized kernel algorithms. Journal of Machine Learning Research, 19(30):1-29 2018.
Raffaello Camoriano, Tomás Angles, Alessandro Rudi, and Lorenzo Rosasco. Nytro: When sub- sampling meets early stopping. In Proceedings of the 19th International Conference Artificial Intelligence and Statisties (AISTATS), pp. 1403-1411, 2016.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Andrea Caponnetto and Yuan Yao. Adaptation for regularization operators in learning theory. Technical report, Technical Report CBCL Paper# 265/AI Technical Report, 2006.
Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with SGD and random features. In Advances in Neural Information Processing Systems (NeurIPS), pp. 10192-10203, 2018.
Xiangyu Chang, Shao-Bo Lin, and Yao Wang. Divide and conquer local average regression. Electronic Journal of Statistics, 1 11()):326-1333 2017a
Xiangyu Chang, Shao-Bo Lin, and Ding-Xuan Xuan Zhou. Distributed suni-supervised learning with kernel ridge regression. The Journal of Machine Learning Research, 18(1):1493-151) 2017b.
Corinna Cortes, Mehryar Mohri, and Ameet Talwalkar. On the impact of kernel approximation on learning accuracy. Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1 113-120, 2010.
Kurt Cutajar, Michael Osborne, John Cunningham, and Maurizio Filippone. Preconditioning kernel matrices. In Proceedings of the 33rd International Conference Muchine Learning (ICML), pp. 2529-2538, 2016.
Lizhong Ding and Shizhong Liao. Nyström approximate model selection for LSSVM. In Advances in Knowledge Discovery and Data Mining 16th Pacific-Asia Conference (PAKDD), pp. 282-293, 2012.
10

---

Published as a conference paper at ICLR 2021
Lizhong Ding, Shizhong Liao, Yong Liu, Li Liu, Fan Zhu, Yazhou Yao, Ling Shao, and Xin Gao. Approximate kernel selection via matrix approximation. IEEE Transactions on Neural Networks and Learning Systems, pp. Online, DOI: 10. N0.1109/NNNLS
2020.
Petros Drineas and Michael W Mahoney. On the Nyström method for approximating Gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6:2153-2175, 2005. 2005.
Jianqing Fan, Yongyi Guo, and Kaizheng Wang. Communication-efficceenn accurate statistical estimation. arXiv preprint arXiv:1906.0448: 2019.
Zheng-Chu Guo, Shao-Bo Lin, and Duan Zhou. Learning theory of distributed spectral algorithms. Inverse Problems, 33(7):074009, 2017.
Cho-Jui Hsieh, Si Si, and Inderjit Dhillon. A divide-and-conquer solver for kernel support vector machines, In Proceedings of the 31st International Conference on Machine Learning (ICML), pp. 566-574, 2014.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression, In Conference on learning theory, pp. 2012
2012.
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Galyna Kriukova, Sergiy Pereverzyev, and Pavlo Tkachenko. Nyström type subsampling analyzed as regularized projection. Inverse Problems, 33(7):074001, 2017.
Boyue Li, Shicong Cen, Yuxin Chen, and Yuejie Chi. Communicationn-fffcccinn distributed optimiza- tion in networks with gradient tracking. arXiv preprint
2019a.
Boyue Li, Shicong Cen, Yuxin Chen, and Yuejie Chi. Communication-efficienn distributed optimiza- tion in networks with gradient tracking and variance reduction. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1662-1672, 2020.
Jian Li, Yong Liu, Rong Yin. Hua Zhang, Li zhong Ding, and Weiping Wang. Multi-Class learning: From theory to algorithm. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1693-1602, 2018.
Jian Li, Yong Liu, and Weiping Wang. Distributed learning with random features. arXiv preprint arXiv: /906.000333 155,, 2019b.
Jian Li, Yong Liu, Rong Yin, and Weiping Wang. Multi-class learning using unlabeled samples: Theory and algorithm. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (LJCAI), pp. 2880-2886, 2019c.
Jian Li, Yong Liu, Rong Yin, and Weiping Wang. Approximate manifold regularization: scalable algorithm and generalization analysis. In Proceedings of the 28th International Joint Conference Artificial Intelligence (ICCAI), pp. 2887-2893, 2019d.
Zhu Li, Jean-Franois Ton, Dino Oglic, and Dino Sejdinovic. Towards a unified analysis of random fourier features. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 3900539144 2019c.
Junhong Lin and Volkan Cevher. Optimal distributed learning with multi stochastic gradient methods. In Proceedings of the 35th International Conference on Machine Learning (ICML., number 3092-3101, 2018.
Junhong Lin and Volkan Cevher. Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms. Journal of Machine Learning Research, 21(147):1-63, 2020.
Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. The Journal of Machine Learning Research, (8(1)3335--421, 2017.
11

---

Published as a conference paper at ICLR 2021
Shao-Bo Lin and Ding- Xuan Zhou. Distributed kernel-based gradient descent algorithms. Construc- tive Approximation, 47(2):249-22) 276, 2018.
Shao-Bo Lin, Xin Guo, and Ding-Xuan Zhou. Distributed learning with regularized least squares. The Journal of Machine Learning Research, (8(1):3302-3233) 2017.
Shao-Bo Lin, Di Wang, and Xuan Zhou. Distributed kernel ridge regression with communica- tions. Xrviv preprint arXiv:2003.12210, 2020.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey in algorithms, theory, and beyond. arXiv preprint arXlv:2004.11154 2020a.
Yong Liu and Shizhong Liao. Eigenvalues ratio for kernel selection of kernel methods. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), pp. 2820, 2015.
Yong Liu, Shali Jiang, and Shizhong Liao. Eigenvalues perturbation of integral operator for kernel se- lection. Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM), pp. 2189 2198, 2013.
Yong Liu, Shali Jiang, and Shizhong Liao. Efficient approximation of cross- Validation for kernel methods using Bouligand influence function. In Proceedings of the 31st International Conference on Machine Learning (ICML), pp. 324-332, 2014.
Yong Liu, Shizhong Liao, Hailun Lin, Yinliang Yue, and Weiping Wang. Infinite kernel learning: Generalization bounds and algorithms. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 2280-22002222 2286, 2017.
Yong Liu, Hailun Lin, Li-Zhong Ding, Weiping Wan, and Shizhong Liao. Fast cross- cross-Validatie Validation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp- 2497-2503, 2018
Yong Liu, Shizhong Liao, Shali Jiang, Lizhong Ding, Hailun Lin, and Weiping Wang. Fast cross- Validation for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1265):1083-1066 2020b.
Mona Meister and Ingo Steinwart. Optimal learning rates for localized syms. The Journal of Machine Learning Research, 17(1)6722-6765, 2016.
Cameron Musco and Christopher Musco. Recursive sampling for the Nyström method. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3833-3845, 2017.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1177-1184 184, 2007.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1313-1320, 2008
Dominic Richards, Patrick Rebeschini, and Lorenzo Rosasco. Decentralised learning with random features and distributed gradient descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11 11:9059934, 2010.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3215-3225, 2017.
Alessandro Rudi, Guillermo Canas, and Lorenzo Rosasco. On the sample complexity of subspace learning. In Advances in Neural Information Processing Systems, pp. 2067-2075,
Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco. Less is more: Nyström computational regularization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1648-1656, 2015.
12

---

Published as a conference paper at ICLR 2021
Alessandro Rudi, Luigi Carratino, and Lorenzo Rosasco. Falkon: An optimal large scale kernel method. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3888- 3898, 2017.
Alessandro Rudi, Daniele Calandriello, Luigi Carratino, and Lorenzo Rosasco, On fast leverage score sampling and optimal learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 5672-5682, 2018.
John Shawe-Taylon and Nello Cristianini. An Introduction to Support Vector Machines and other Kernel-based Learning Methods. Cambridge University Press, 2000. ISBN 0521780195.
Si Si, Cho-Jui Hsich, and Inderjit Dhillon. Computationally efficient nyström approximation using fast transforms. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 2655-2663 2016.
Steve Smale and Ding- Ding-Xuan Zhou. Shannon sampling ii: connections to learning theory. Applied and Computational Harmonic Analysis, 19(3)28853302, 2005.
Steve Smale and Ding-Xuan Zhou Learning theory estimates via integral operators and their approximations. Constructive Approximation, 26(2):153-172, 2007.
Bharath Sriperumbudur and Zoltán Szabó. Optimal rates for random fourier features. In Advances in Neural Information Processing Systems, pp. 1144-1152 2015.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer Verlag, New York, 2008.
Yitong Sun, Anna Gilbert, and Ambuj Tewari. But how does it work in theory? linear SVM with random features. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3379-3388, 2018
Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference Machine Learning (ICML), pp. 3329-3337, 2017.
Dougal J. Sutherland and Jeff Schneider. On the error of random fourier features. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). pp. 862871, 2015.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 2000.
Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou Nyström method vs random Fourier features: A theoretical and empirical comparison. In Advances in Neural Information Processing Systems (NeurIPS), pp. 476 484, 2012.
Rong Yin, Yong Liu, Lijing Lu, Weiping Wang, and Dan Meng. Divide-and-conquer learning with Nyström: optimal rate and algorithm. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 6696-6703, 6703, 2020.
Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann-Rice, and Sanjiv Kumar. Orthogonal random features. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1975-1983, 2016.
Yuchen Zhang, John Duchi, and Martin Wainwright, Divide and conquer kernel ridge regression. In Proceedings of the 26th Annual Conference on Learning Theory (COLT), pp. 592-617, 2013.
Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates, The Journal of Machine Learning Research, 16 (1):3299-3340, 2015.
13

---

Published as a conference paper at ICLR 2021
A APPENDIX: FAST LEARNING RATES
In the section, we will show that the fast learning rates can be achieved under favorable conditions. Let
px fs
IR (xx)dxxx s }0)
be the square integrable space, || I13 be its norm. Denote the integral operator (Smale & Zhou 2007 Lg by
Lxf = J K(x, (fxx)xx Vf E Lpx
Assumption 1. For x > 0, (X) is the effective dimension of the integral operator Lx defined as ((A) = =Tr ((LK 11) - LK), where Tr is the trace. Assuming there exists constant 2 1, such that
N(A) S cA c ,, E 10.
The effective dimension is a common assumption within the framework of learning theory (Caponnetto
& Vito 2007 (Smale & Zhou 2005 Rudi & Rosasco 2017). which is used measure the complexity of the hypothesis space. It is always satisfied for y and e = k. Equation 7 can control the variance of the estimator and is equivalent to the classic entropy and covering number conditions.
In particular, it holds if the eigenvalues of integral operator LK decay i i-1/7, which is satisfied by the popular Gaussian and polynomial kernel functions. More details can be seen in (Steinwart & Christmann 2008 Caponnetto & Vito 2007 Rudi & Rosasco 2017).
Assumption 2. Let fa(x) = Jy ydp(y/x) be the regression function, ply]x) be the conditional distribution induced by p. For 1 S r S 1, assume there exists g E L such that
fx(x) Lig(x),
where Lg is the rth power of Lg.
Regression function fo is the best function in L which is the primary objective in regression problem. Assumption [ used to measure the complexity of the regression function fpr which is commonly used in approximation theory (Caponnetto & Vitol 2007). Equation can be used to control the bias of the estimator, requires the expansion of the regression function So having coefficients that decay faster than the eigenvalues of integral operator Lk. The larger the value of the faster the coefficients decay. The case r = 1/2 means that fo E Hk. More detail can be seen in (Rudi & Rosasco 2017; Smale & Zhou 2007).
Theorem 4. Suppose v is continuous, such that (x, (x, w)l S T almost surely, T E (0) and |y| S Ç.
Under Assumptions
2 with [1/2,1], 7 [0, 1]. if X (2(1D) .,:), ), [Dal ... (Dml.
m $ |D] . and M 2 |D] 1+
then, for every 8 (0, 1), with probability at least 1 6, we have
E [[FMM..
fell]] O [D] |D|
log"
The bound above is the same as the original KRR estimator and is optimal in a minimax sense (Caponnetto & Vito 2007 Lin al. 2017 7 Chang et al. 2017b). In the best case, when r = 1 and
Y 0, the rate O(1/ (D) can be achieved by Q (DD) random features and N /ID)) partitions. In the worst case, that is r = 1/2 and y = 1. which has been covered in Theorem
Theorem 5. Suppose va is continuous, such that | x, w) I T almost surely, [1, and |yl Ç.
Under Assumptions 2 with r E [1/2, 7 E [0, 1], if X = 2(D 2Att) ), |Dil = ... Ppml.
1+
m S |
and M 2 [D] 2017
(10)
then, for every 8 E (0, 11, with probability at least 1 - 8, we have
II Soll O (ID) 2r, log²
14

---

Published as a conference paper at ICLR 2021
One can see that the upper bound of is (D] 4:-25 which stricter than that of Theorem In the best case, when r = 1 and 7 = O, the rate (11(DD) can be achieved considering S2( v /DD random
features and (2( partitions. For the basic setting, that is r = 1/2 and = 1, which has been
given in Theorem 2
Theorem 6. Suppose vb is continuous, such that [x)(x, x, w)] S T almost surely, E [1, oo) and |y| S Ç.
Under Assumptions with [1/2, 7 [0, 11. if X ((( 2-イ5 ) [Pi] = ... [mml.
(2r4 D(p+1) [D]
and M Z [D] 1 1
log
(11)
8
then, for any E (0, 11, with probability at least 1 - d,
PM.DD -fl1 = O (D) कम.न 1og 1
8
One can see that the communication can relax the restriction on the number of partitions. As p oc. the partitions can reach SX[
2 " ), which is the same as Theorem
Remark& 5. In this paper, we focus on enlarging the number of local machines. In (Rudi Rosasco 2017 Rudi ef al.) 2018), they have proved that when generating random features in a data-dependen manner, fewer random features are required to obtain optimal learning. Thus, if we adopt the data- denendennnd manner to generate random features, further improve the performance of DKRR-RF- EERR--FFCMM fewer random features.
B APPENDIX: NOTATION AND PRELIMINARY
In this paper we denote the operator norm by || ||. and the square integrable norm by -1- Definition 1.
SM RRMM + pxx (SMw) (w,
&n (x)),
SM: 1 + RRM, GSM9
&M (xx(x((x)))xxx()
SM.D 12 RRM ,SMDD D
ΦM (x))
XjEDx
CM : RRMM + RRM, BRM.C / (x) (x) dxx
CM.D: : RM + RM CMMD
1
Σ (x,
[
xxEDx
Lemma 1. Oas and CM,D are self-adjoint and positive operators, with spectrum is [0, 72) Moreover
we have C' = SM and CM.D = 1 2M Mr = SM.
Proof. OM and OM.D are self-adjoint and positive operators, with spectrum is [0, 73, and
CM = SM CM.D = MM + T
M.D
can be directly obtained from Caponnetto & Vito (0077) Smale & Zhou 2005 2007
Rosasco et al.
(2010); Rudi & Rosasco (2017): Lin al. (2020).
In the following, we prove that CM.D SM.D From the definitions of Sas, S p and CM in Definition I have
V (SM3))( = (G, (m())) = sa (.)
and thus we can obtain that,
SMD D
Σ
(M(x))ou(x)) CM.DB.
x
So, the Equation CM SM holds.
15

---

Published as a conference paper at ICLR 2021
Definition 2.
fMDDA w WM.DAOM)) WM.DA arg min wERM
(w Φxs(x)) -vi)² + 21|w|| }
D
&ED
SMDD = -w
M.D.A.M (), = arg min WERN
Σ IEED
( T (x)((x)) - fo(xx)) + A|lw|/?
[
SMA w (MAAM(()) WM. = arg min WERM
w ΦML(x) [x(x)) dxxx(x) + (
fo(x)) (1 (f(x)) -f(x)) dpx(xx + Allflie
fx arg min JEHK
(12)
Remark (From Caponnetto & Vito (207); Smale & Zhou (2077 Li et al. (2220).
(2019b);
Lin al.
fM.D.. S..M.DA. WMDA = (CMr,D + A1) 2 M,DDD:
fM = S..W W WMDDA = (OMDD + M1) SM.ppfp
(13)
fMA= SSMWA. WMR (OM 1
Definition 3. The maximum random feature dimension is denoted as
(A) = sup [[(L + WES
w) 0.
Remark 7 (From Rudi & Rosasco 2017
Noc (A) S 33 is always satisfied for every À >>> 0.
C APPENDIX: PROOF OF THEOREM
4
C.I APPENDIX: ERROR DECOMPOSITION FOR DKRR- IN EXPECTATION
Proposition Let BaN, and fa,,,, fM. fx be defined by and respectively. Then, we
have
E [IIMM.DA - foll < [llfMA - fAll + [llf2 - fpll
m
D2,
m
+ 3
[IIMM.D, - fMLAl??]
[IM - faaal? ffaAl
D
D
Proof.
Let J. and f D...D.- SM.X be defined by 3 and 12 respectively. According to the
Proposition 5 of (Chang al. 2017b) Lemma 20 of Li al. 2019b), we have
E [M
1
D
(14)
[I|M..J.- - SMAl +
[1
SMAl33]
D
D
/=1
1=1
Note that (a + b + c)² 3a² 362 + +32 Ya, b, 2 Thus, have
E [ - foll E [1]fM,DD> FML FMM fx + fA - fo
< 3E [11 fl. +3 [I - fall +3 [Ilfx - foll81
Combining the above inequality and Eq. 14 we can prove this proposition.
Proposition 2. The follows hold:
V W. JM.D(RM. + KM.D)
and
||M - SMr S T2. (RM,D + KM.D).
where RMD = |l(CM + -TI (12 ( Sprfp) JMLD 11 + AI/-1/2(CM +
2/) KM.D == |l(CM + - Sh,DD
16

---

Published as a conference paper at ICLR 2021
Proof. From 13
know that WM,DDA (OM, A1) 1 M,DYD and WM.DA (CM.D
SM so have
W,DDAA WMrDD, - (CMDD + (MM.DD -
=CMMD A1) (CM AI) + XTM
+ ( SM,Dla).
(15)
Note (CM,D- - X12-1/2 is self-adjoint and positive operator, so ||(CMr, + +1) 1/21 S 1/V2.
thus, we can obtain that
WMDDA WM.DAll S VX
MM (CC + ( - SM.Dfe)l
JMDDllCM 11 M.DDD + Sup -Mppfo
Sirpfp)
(16)
VA
JM.D + VA
Note that fM.DA- fAr,D, = =uN(WMDA - W M.D.)). by 15 we have
fM.DA fh.,, = SM - W..D
-MM(CM A1) (1) (CM) 11)11/((CM.D + 112 A1) (17)
(OM+ + A1) 1/2 ( (DMDDD - SM.Dfo + - SM.Dfo)
Note that
[S + 11) 1/ =I(CMM S) + 112-1/211/2
= =I(CMM + (I + 2T) 1/2 1
So, by Eq 17 we have
MMMDA IM., S JhAD (RMD + KMrD))
Proposition 3. The follows hold:
VAllW3A.DA - WM.Al S lIfMA - follo + -JM.DIlfas. - folle
and
|MMDA fM.Ale & (JM.D + TM.p))lfM.-
where JM.D == 11(CMMD + A1) 1/101/2(CM + A1)
Proof. By Remark 6 we have
WM.DAA W W.A = (CM.D + AT) - (CMs + -
-CCMD + XI (Str, Si. [(MM. + A1- (CM + 11)-
Note that for any self-adjoint and positive operators A and B,
A- B A- A)B A B B 1 (B-))A
(18)
so we have
w 0 M.D.A - W.A
=(CMD + -S - fy 1 + (OM.D + -I - -CM,D)WM.
From Lemma we know that C'M = SM and CM.D LM.D M.D SM. thus we can
obtain that
WM.DA WASA
=COMD + AI) (S SMffl (CM, (S SM.DSMWMM.N
=(CMD + AI) -S Sh.DSMWM.N + + A1) 1| Shffol (19)
=(CMD + "S - -M.DDMNN
+ -
-(CM, + -1 - -MMAl + (OM.D + -T) -fpl-
17

---

Published as a conference paper at ICLR 2021
Thus, have
[ - w.ral & (I(CM. 10) I(C
Il - follo- (20)
Note that
|lCCMD M
+ -
and
[l(OM.D + 11)-1/25 =l( + A + (T) + AT)-1/2551
SJM.Dl(CM + 11)-1/25 S JM.D:
since II(CM + X1)
(C + A1)-1/"Car(CM + 21)-2/2111/2 2 1. Substituting the
above two inequalities into Eq. 20
we have
1 (1 JMDD)IIMA~ - Splles S
w M. WM.l
which prove the first result of Proposition
In the following, we will prove the second result. By Eq.
19 we have
fM.DA faa (w M.D.A. WaGA)
=SM(OM.D AT) - SMMN +
+ + Sol - fMAN
=SM(CM + 11)-1/2(CM +
+ +SM(CMM + A1)- + (AI) + +1) + +11)-1/2(C, + 21)2/2
(CM+ N1)+21)-1/2000 [fM - fpl
Note that [[MM(CM + A1) 1/2 =I(OM + CCM + XI)-1/211/2 < 1. llCCM
XI) - Mpll 11(OM,D + A1)-1PCM,(CM..D XT)-1/211/2
and [C
A St = |l(M + CM + 1121-11211117 v 1, so we have
MMM - fM.llo S (JMMD + JM.D))lfMA - follo-
(21)
Proposition 4. The follows hold:
VAlWWDAA- ww.ll S J...
KM,)) JM.D)lfMA K (1 folles
and
IIfM.D, fMAllp I JM. KM.D) + (JM,D + JMDD)llMM. -JuDDDhppllAAA---a fflle.
where RMD = |l(CMr + ( Sirfo))l JMID 11(CM,D + -I2-112((Mr
11 KM.D- == Il(CM + + -SirpDo)11
Proof. Note that
WWM.A WMAll < WWMDA Wi 1w wMall
and
||/M SMAlle S IM.M, SMp 11 SMalle
Combining Propositions 2 and we can prove this result.
18

---

Published as a conference paper at ICLR 2021
C.2 PROOF OF THEOREM 4
Lemma 2 (Lemma 23 in ò E (0, 1] and À > when
Li et al. 2019b), can be also seen in (Rudi & Rosasco 2017)). For
(A(A)) 2r-1
(Noo(A) ))²²²
2-22
M29 Ω
v (A) log 2d
Then, with probability at least
8, we have
IlfMA fAlls S cdar,
where c a constant.
Lemma (Theorem in (Smale Zhou 2005 ) Under Assumption 2 for r [1/2, 1), we have
Ilfx - fpllp S cA²",
where e is a constant.
Lemma 4 (Lemma 6 in (Rudi & Rosasco 2017 ). For 8 (0, 1). with probability least 1 5, have
RM.:: = [CCrr + 1// (MMDDD
Stafo)l=o(
(as( [D]
1
+
log
where Na1 = Tr ((TM + A1)-1 Lm is the integral operator associated with the approxi- mate kernel function KM, (()) Sxx KM (x, x') xf) ddxx(x)).
Lemma (Proposition 10 in Rudi & Rosasco 2017). For any å (0, M 22 log #t)
then with probability at least
6.
- - operators A and B, if there exists rj such that the following inequality holds
LA55((A),
(22)
where (A) == Tr ((LM + Lad.
Lemma (Lemma F.2, (Blanchard Krämer 2010)). For any self-adjoint and positive semidefinite
II(A + AT) (/2()BBBB(BBB// ())--A)(A-0) -1/21/11 1 $1
then
1 ViI
[[
Proposition 5. For d E (0, 1], with probability at least we have
2T log
Nar(A)
KM..- = 1IC + 1/2 SM.DDo)l S
+201
3/DIv
[D]
where (A) = Tr (LLM + -
The proof closely follows the proof of Lemma (Rudi & Rosasco 2017).
Proof. Define μ4; = (OM + X1) - (C'M + 1/) M (x:).f Note that
1
(CM + X1) Shspff)
P..
D
Since Mi.....,pp. Midi independent and identically distributed random vector, and Et4 / (CM
(CMr + X1) x2) (xxx) 0
19

---

One can that Published as a conference paper at ICLR 2021
To apply the Bernstein inequality (Arcones) 1995 Rudi & Rosasco 2017) for random vectors, need to bound their moments. Note that
lI(CMs + (MX))((00) T
VX
and
/2/ Eyς 2 / 110M (/O
$2²² / 11CMM (x 2ç
Thus, using the Bernstein inequality (Arcones) 1 - 6, we have
1995
Rudi & Rosasco 2017 for any 8 (0. 1]. with
27 loglog? llCM + 1/2 - Supfooll 5
(a
+ +2G
3/D VX
D
Lemma 7 (Lemma 2 in (Smale & Zhou variable on 2, P.P with values H. Assume ( be independent random drawers of p. For any 0 < 8 < L, with confidence 1 8,
2007
Let H be Hilbert space and be random
E S M < 2o almost surely. Denote a = B(g²). Let
m M 72
2M log(20)
2 ( log
B(E)
n
n
Proposition 6. For any 8 0, with probability least
6, we have
QM.D == [1OM + X1)-1/2((Ms - CCM.D) + +2)-1/21
2 2log" (2, (A) +1)
(lo (A) +
DD)
[D)
and
LMDD = 11CMM + 21M- -CMD))l
2log (2/0 (A) +1) +
2log(2/8)(Noo (A) + 1)
[D]
where Noc (A) supwen [l(Lk 1/) 1/2 IlB ci and C2 two constants.
To prove Proposition 6 we first prove the following lemma (a similar technique can be found in Hsu
al. 2012 Rudi al.
2013 Caponnetto & Yao 2006 Rudi & Rosasco 2017)).
The similar result for the matrix case was first proved in Hssu et al. 2012 and later was extended to the operator case in (Rudi al. 20133, Rudi & Rosasco 2017).
Lemma 8. Let St...., Sn with n 2 1, be i.i.d random vectors on separable Hilbert spaces H such that H = EC 8 Ç is trace class, and for any À there exists Nxo()) < oc such that
(S, (H + -1) <
(A).)). Denote Hn as Eh Si G. Then for any 2 with probability
at least - 26, the following holds
2 2lgg((2 (A) +
22ogg(200) +1)
(H + 1/2 Ha) + 11-1/2
1/2
n
7
Proof. Let H1 H + XI, 17 11 1/2
HH 1/2 1 - 1/2 @ 1 1/2
EG: = Note that
1/2 I H
1/2// & H
1/2 s
||l||
(Gs, H 1/25,) < (1)
20

---

Published as a conference paper at ICLR 2021
and
|| -
| |B (si, H 1/ () 8 1 1/2 11
- (2) E|H 1/2 @ H 1/2 Sil
+ || H2
s No (A) 1/2 H|| s Nan +
| H2 H2|
Thus, substituting the above two inequalities to Lemma 7 (Lemma 2 in (Smale & Zhou 2007 ) which finishes the proof.
Proof of Proposition 0
Since Cм is self-adjoint operator, we have
aI(C's + (CM CM.D)|l || = ll(CM + AT) CM.D)(CMr + AT)-
According to Lemma with v; Φa (x:), we can obtain this result.
Proposition? 7. If (D] 2 32 (llog(//))1 (A)), for any 5 > O. with probability at least we have
JM ll(CM,D AT) (C + AT) S 22.
No (A)), then Proof. From Proposition 6 know that if [D] 32log No
II(Car + A CM 1/31 5 Combining the above inequality and Lemma we can prove this result.
1 2
Proposition 8. f (0, 1], and (D] 2 52 (A)), then with we have
1 IMMDD SMall. = O TM.DA log z + +LMA - Sallo + 11ʃ2 - -Slllo -
where T..DA. VA/DI
N(A) e
Proof.
From Proposition
we have
[|M....A - SM,lle S (RM, + KM.D) + (JMDD + RMDD))lMMM... Sollo-
Thus, from Lemmas and Propositions we know that if [D] 2 S2NNoc (A)), can prove this result.
Proof of Theorem
According to Proposition we have
E [IM.
< [llfMA fAll + [llfa - fpl
D
D D
+ 3
[IIMM, SM.A + 3
Σ
2
Substituting Lemmas
23 Proposition
into the above inequality,
that if
((PR-112))
Na)2 (a)) 2
M M 2
and [D,l (ANoo
12r-11
with confidence 5, we have
D
D 2r D
E M.PPA
so1l O
2 +
T
TMND,, log? 8)
Σ f=1
(23)
2
21

---

Published as a conference paper at ICLR 2021
where M.DD,A=
VAIDA] +
N(A) D2
If setting [Di] -.. |lmm A Q((D) 2,ो ), we have
TM.DA =0 (V
(M((1) [Dyl
1
=0 -V 2-. m - -r422r
4nt22-1
(24)
[DIIAA
Note that if m s 0 (ID)
2-ta-1 2:
and [Di] = =... (Dml. and A = S2(12) 2Pt)), we have
D
(ID = (A)).
D
2
m
Thus, substituting 24 into 23 one can see that if S 9 (D))
2nto-1
and
M 2 Ω ((NR 12--1
28 v v.Nc(A)) (1)2222--2
2 (ID) + -
with probability at least - 8, we have
E 1 Soll
-0 -0(D 1
log" 2
1
+ |D]
logg
|D| शनन
8
1
0
[D]
log² 2
D APPENDIX: PROOF OF THEOREM 5
D.1 APPENDIX: ERROR DECOMPOSITION FOR DKRR-RF IN PROBABILITY
Proposition 9. The follows hold:
m
Dy
|w W.M.A. WMLDAA S
Th (h + (.D.)..WM.DAA' W...ll and
D
j=1
D
- -M.PA-MMPAA <
J2r (QM.D + @M.,))
D
3=1
[IfM.DDA fMalet + VĀ VAIWM., wMAll),
where JM.D [[C AT)-1/2(CM 2T/ and QM 11(C AT)-1/2(CM
CMM + x)
22

---

Published as a conference paper at ICLR 2021
Proof. Note that W.MDDA (CM.D + 1 M,DDD, thus we have
W M,D.A - W.DDA
Dj
(OM.D, + A
+
D
Dy
((OM.D - (CM, | $M.D,,
D
Pal
(CM.D + + (CM.D -CM,D- (CM,D, + DM.D,
D
DJ
11) (CM.D +1) (CM.D WMDD,,
D
DyJ
(CM.D + A (CM, (OM.D-CMM) CM)
DD]
[Dy]
(25)
(CM.D (CM (OM--)))) WMDDAA
[D]
Dyl
(OM.D (CA - -MMA)
D
Dyl
- + ( -CMM,DD-CMMWAA
D
Djl
(CM,,DAITT (CM- -M.D, WMDD,
[
Dj
(OM.D + + (CM.D-CMMMMM.... CMM. (AAD WMA)
D
D2
(CM,D + A (CM- -OMDD) (WM.DJ,A w.M.).
D
Note that
Djl + (CG -WMA)
D
m
Dyl (M
(CM.D - (CCp::IIJJ(N-N-OCA----CCGaaaI-a (CN -
[D]
j=1
1Dyl
and
(CM,D + XT) (Ca - CMDD, (WM.DAA-WMA.
D
1=1
Dyl + + AD)(OM + X (CM - CM.D,) (WM.D,.A - -MM.).
D
Substituting the above equations into Eq. 25
we have
DDyl
IMMA W.L.D.I <
The (LM + (.p.,.lWM.D.... wasall
D
23

---

Published as a conference paper at ICLR 2021
where LM.D II(CM + so we have
CM,D))l From Proposition 6 we know that LM.D Q.M.D.
m
Dil
M.D.A. - W.R.D.l S
Σ
IMD(QUDD + @.D.)IlWM.DJAA-WW.. D
j=1
which prove the first result of this proposition.
In the following, will prove the second result of this proposition. Note that Sas (w D,
WM.DD.) = PM.DA - SMM According 25 we have
Pyl D
30 M.D. - SM.D. =
SM + + (CM. (WM.JJA- wM..)
DJ
SM + A1) - CMMD, (WM.D,,A - War (26)
D
Dj
(n) + 13).
D
Note that
hi (MM(CM + 11)- +
+ A1)1122
(OM + A1) (CM.DCCMMM.... - -Ca) (CM +CM+
(27)
(OM + AT) - + >T)(W..D,.A Wasa),
thus we have
1b/lle J..DD.M.IP.. QM.DIISM (CM + A A1)-1/3(Css + AI)(WM,D,, wM,.)l
$ Qu. + -11--1/((CM, + - - W...ll
(28)
Since ||SM (CM + 11)-1/311 C + -1) + 1/2 < 1. So, we have
|1tt|le S Q... -1) M)..M.,, WM.A)l
-M.. + - + (T).W..
WM.))l
S - (WW..,, - WMA))l
+
-MMx)l
$ 1 fM.DAle
< VWJ...QM.DIIIMM..... -MMJl
IMPAALI V.llWM.D,.. waral),
the last inequality uses the fact that
1/2 1/2 = (C + AI) 1/2 SM +1) < [l(CM AT) 1/2
Similar as the above process, we can also obtain that | ll s MM (IfM..,,A - fM.DAAI VAIlWMDAAA- - -wl.ll.
Thus, using 26 we can prove this result.
D.2 APPENDIX: PROOF OF THEOREM 5
Proof of Theorem 5
Combining Proposition 9 and Proposition 4 we have
ma
D
I -M.DAA <
Thip (QMDD - 2M.,,)
D
1=1
(29)
(JM.D, JMHD, (RM,D, + KMMD, + (2JM.,, + JMr + 1)]lfMax solle).
24

---

Published as a conference paper at ICLR 2021
From Propositions and & one see that if [Dyl 2 S2VVo (A)), and A S [ ll, then for any > O, with probability at least - 6,
IlM fM.DDale
D
(MMDD + @MDD)) (TM.D,, log g + IlfM - fulle + l1fx - Follo)
D
where M.D.A
+
N(A) [
Note that QM.D I QM.D, and by Lemmas and so we
VilD.
have
m D2J
II - IMpalle= -
QM.D, T..D,, log 8 + X X'OMD,
(30)
D
Note that
P - follo IIfM.DA SM.DA+ fM.DA - SMA fal. - fa fx folle
(31)
M.D. - fM.D.ilee + [IM - fMall + lIfMA - fulle + llfx - fllp.
Combining E.q
30
Lemmas
2
Proposition g and E.q 31 one can see that if M 2
22 (2)
(1)2 2r V (oo( with probability 1 8, we have
23
D D
1 2M.D, M.D log TM.DA log 5 + *2.MMD +X'
1
[LM.AAA Solle =0
Solle
(32)
If [Dil :.. 1...=|mml. A Q([D) ス ) we have
TM.DA = O (ID) गांन ID]
0
(D) शंनन
T M.D = O (VmlD
क + ml DD)
4r
12
(33)
QM,, = 0 ml| [D] 2 + vmlD
2----1
Thus, when S 2 ( [D)
2rth-1 41125
we have
TM.DAA = =0 |D) (1()-
QM.DA 0 [D] शमक D
24-144 Br+ty
=0 =0(1D) (ID) -
D
1rtッ+1 4r-27
2 Q (I)arit)) (A))
[D,l > Ω
Thus, we have [I foll = (ID)
log 2 } which prove this result.
E APPENDIX: PROOF OF THEOREM 6
E.1 APPENDIX: ERROR DECOMPOSITION FOR DKRR- RF-CM IN PROBABILITY
Proposition 10.
[| - AM.D.lll
(2FM.D QM.D 2hh,p 2MD.)) ) (IIREDA- SM.DA.le (IPA.PA--M.PAle VAIWW... -WMDA-WMDD)).
D D
where JMDD = 1(CM,p 112 + XI)1/21 and QMD 11(CM + XI)-11²(CM
(M, + -1122
25

---

Published as a conference paper at ICLR 2021
Proof. Note that
WM,D,A w - -OMMD + AT) [CAMD + AT) M.D.A $M.DND.
W
W (-1
[Dj]
(CM.D, + -1)-1 ( + A1)
2M.D8D
M,D.
M.D.A
Thus, we have
WM,DA WM.DDA
M,D.A (CM,D + + [CM.D + .MDDND]
M.D.A
f-1
+
Σ
Djl
D
(CM.D, + -1) [CM. (CM.D AD) - LM.DND
j=l
D21
(CM,D [CM.D, + -C +CM NDW DM.DDD
Dyl
(CaM.D; + +1) [CM,D CM,D, (CM,D A1) [CMDD + AT)W .MMDDD
D
m
DJ
(CM.D, + -1) -CM,D - CM,D, WMDA -MMDA.
D
W
D
CCM.- - -MM - WM.DAA -WM.Al (CM,D, + (
[Dg
(CM.D, + + 1 - CM.D,,] W...D WM.DA.
D
D
NY +
D
(34)
Note that
SMNY = SM(CM + (1)-1 (CM.) + +
(CM.D, (AI
111 [CM, Car) (CM 211-1/2 (35)
(CM A1)+/A1-1/2(CH.. + +1) (W -WMDA).
Note that ||SM (CM + 1 |1(CMr XT)-1/2 (CM + AT)- < 1, so, we have
||S S Pú 2M.D [CAr A1) A1) 11/ + xI)
WM.DDA WWw.bb---
wM.D))) (WLLA--M.DA]1
(36)
Note that Cm = S SM, so
Om w 1-1 M.D.A W..D.A) SM (w
M.D.A wM.D.) = -S (JM.D.. SM.D..)
Substituting the above inequality into Eq. 36 we have
|Sanilll & JM.D, QMD (CM + A1) 11/59 - ||
ARIDD, @MD [CAr + 112-1/2 WMM.D. (WM.AN)
< JM.D, QMD (1 fMMPD,llo VAllWADA W..D.l).
26

---

Published as a conference paper at ICLR 2021
the last inequality the fact that Il(CM + X1)-1/2S;,11 Il(CM + A1M XT) 1//1//1///2 I Using the same process, obtain that
12 I JMP,, QM.D, (IRMAD-- fM.DAlle + VAllWM... w..DAa))
Thus, we have
D D
II - -aaulll-)S((WM.... W...Alll S
|S + 11S
D2l
(J 2M.D RM.D 2M.D,)
(37)
D
[lMbb SuppAll + Vill M,D W..DAal)
According to 34
we know that
D
WM.DA W
M.D.A
(N = N³)
D
DJ
(CM.D, + +1 [CarDD Carl (. - WM.D..
D
12j
(CM,D, +1 [CM CM.D,) WMM.A W.,DA
[D]
DJ
(OM.D, + +1) +CM++MMM AD) + +X) I - -CM.D- M.D.A WM.D..
D
P
(Cm.D, + + AD)(CM + 1CM - CarD, M.D. -M.D..
[D]
Thus, one can obtain that
WMM.A. WAr.D S Σ
Jir (LM, + LM.,,)llWM,, W..D.All
j=1
where LM.D = IICMM + (CM |C From Proposition we know that LM.D = -M.
Thus, have
WM,DA. W...A.ll < Σ Jh. (QM,D (M W.RDD.l-
(38)
Combining
and
we have
IlfMM.D.
Ft M.p.lll + VAllWM.A - W.M...ll
m
D
- SM.DAAlo + VAllw - wM.D.ll) TaI QM. + Júpp, (MD,) (IIAAAAA-MMAAA
D
1=1
Dyl
+
JRr.D, (QM.D + 2MD,) V W.R.Al
D
(2JRr. QM.D, + +2R2r, Q..D,) (1 fMaDAAle + VAllw wM.
Th M. Cmp + F2r QMD,.) ) (IRRIDAA -IPADA--MMOAlt SMoAlle VWWW - WMDDAl).
D
Ø=1
which prove the result.
27

---

Published as a conference paper at ICLR 2021
E.2 APPENDIX: PROOF OF THEOREM 6
Proof of Theorem 6 Substituting Propositions 5
and Lemma into Proposition 9
we have
If
S...DAlle Vxllw W...D.ll
m
Dj
Σ
(OM,D QM.D,) (RM,D KM,D l1MM Sollo)
D
=0
(QMDD + QM.D,) (TM.D, + follo)
D
Combining the above inequality and Proposition 10 and note that QM.D S QM.Ds, we can obtain
that
M
SM..A.lP
QMDD, +IfMA fxll + llfa - falle) ))
Dj Σ
Dj
oo
QM.D
Σ
D
D
Note that
I1 follo 11
fMA fML f folle
(39)
-lIMAAA-MMAAl IIfM.D + fAllo Ilfx flle.
Thus, by Lemmas
2
one that if
M Ω ((
((NPT-1N)) (1) 2 (ool(A)) ((ll)
we have
1IMMDDA- folle
=0
Σ
D
QM.DD
Σ
m
Dj D
QM., (IuD, ) + T...A log +\-
D
From 33 by setting [Di] :...= 1Dml : A S2( - ,,. ), we know that
Tar,Dy,A O ( (/ml D शंं + m (DI
1r
QM.D O (m|D) 2rtn-1
2-tz-1
+ v m D
T..DA = O (ID) मेन + |D]
4r-2y-1 art2y
Thus, when Ω (ID) the result.
(004-11(+1)) (2++))(+2)
). have IIM Spllp = - which proves
F APPENDIX: PROOF OF THEOREMS 1 2 3
Proof. From (Smale & Zhou 2007
Caponnetto & Vito 2007). if r = 1/2, then f, E Hg. Thus, in
this case, fHx exists and [(HKk] and -²_ So, using Theorems can be proved.
Elp). Note that Assumption is always satisfied for 7
and with 1/2, 7 1 and 7², Theorem and
28


Reviews:
[{"review_id": "zHufcqzJz-i", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nDuring 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.\n\nNot 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kPwjg8-oFKg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper 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).\n\n##### clarity\nThe 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.\n\n##### quality & significance\nI 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_se17mXPDK", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nSome few comments:\n- It looks to me that the idea of distributed learning with communication has already appeared in [ arXiv:1906.04870] if not earlier. \n-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]\n-Page 2. Optimal learning rates were also established for distributed\nspectral algorithms in [JMLR 2018, 19(1): 1069-1097] ( or [arXiv:1610.07487]). \n-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.\n-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). \nAlso, 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]\n-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.] \n-Numerical results on different data-sets could be given to further exemplify the performance of the algorithm. \n-How do you choose the regularization parameter $\\lambda$ in the distributed learning? Will this enlarge the computational complexity?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)