Distributed Kernel Ridge Regression with Communications
Shao-Bo Lin Di Wang Ding-Xuan Zhou
cs.LG stat.ML















Distributed Kernel Ridge Regression with Communications
    Shao-Bo Lin sblin1983@gmail.com 

       Center of Intelligent Decision-Making
        and Machine Learning

        School of Management

       Xi'an Jiaotong University

       Xi'an, China
       Di WangCorresponding author wangdi@wzu.edu.cn 

       Center of Intelligent Decision-Making
        and Machine Learning

        School of Management

       Xi'an Jiaotong University

       Xi'an, China
       Ding-Xuan Zhou mazhou@cityu.edu.hk 

       School of Data Science and Department of Mathematics

        City University of Hong Kong

        Kowloon, Hong Kong, China
    
===========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




This paper focuses on generalization performance analysis for distributed algorithms in the
framework of learning theory.  Taking distributed kernel ridge regression (DKRR) for example,
we succeed in deriving its optimal learning rates in expectation and providing  theoretically
optimal ranges of the number of local processors. Due to the gap between theory and experiments,
we also deduce optimal   learning rates for DKRR in probability to essentially reflect the
generalization performance and limitations of DKRR. Furthermore, we propose a communication
strategy to improve  the learning performance of DKRR and demonstrate the power of communications
in DKRR via both theoretical assessments and numerical experiments.



learning theory, distributed learning, kernel ridge regression, communication



§ INTRODUCTION


Commonly in this era, data of huge size are stored in numerous machines and cannot be shared for protecting data privacy. Typical examples include the clinical data in  medicine where  medical data are collected in different hospitals  and  financial data in business where commercial  data are generated in different companies. These distributively stored data bring a new challenge for machine learning in the sense that every one would like to use the other's data but is unwilling to share his  own data. Nonparametric distributed  learning (NDL) <cit.> presents   a preferable approach to conquer this challenge by means of combining  the prediction results from many local processors without sharing individual  data each other.


There are three ingredients of
NDL: local processing, communication, and synthesization. The local processing issue refers to applying a particular learning algorithm such as the kernel ridgel regression <cit.>, local average regression <cit.>, multi-penalty regularization <cit.>,   coefficient-based regularization <cit.>, and spectral algorithms <cit.> to tackle the data subset  in a local  machine  and produce a local estimator. The communication issue focuses on  exchanging  exclusive information  such as the data <cit.>, gradients <cit.> and local estimator <cit.> between different local machines. The synthesization issue devotes to producing a global estimator by combining   local estimators  and communicated information on the global machine, typical strategies of which are the majority voting <cit.>, weighted average <cit.> and gradient-based algorithms <cit.>.

One of the most popular NDL approaches is    the divide-and-conquer learning, in which the communication  is not required and the weighted average is utilized in the synthesization issue.  Figure  <ref> presents the training and testing flows of  the divide-and-conquer learning.
As shown in  Figure <ref>, to give a prediction of a query point x_t, only a real number f_D_j,λ(x_t)  is communicated to the global machine, which succeeds in protecting the data privacy of each local machine.
Generalization performances of  the divide-and-conquer learning   have been  proved to be similar to running the corresponding algorithm processing the whole data on   a single but large enough machine <cit.>. The theoretical problem is, however, that there is a strict restriction on   the number of local machines to guarantee the optimal generalization performance, which is difficult to be satisfied in real applications.

In this paper, taking the distributed kernel ridge regression (DKRR) to be the specific algorithm,  we aim at enlarging the number of  local machines by considering  communications among different local machines. There are three purposes in our study. At first, we improve the
existing results for DKRR in expectation in the sense of removing
the eigen-function assumption in <cit.> and relaxing the
regularity assumption  in <cit.>.




Our main tool to achieve this goal is a tight operator product estimate  based on a recently
developed concentration inequality for self-adjoint operators
<cit.>. These estimates improve the results in
<cit.>, where the second order decomposition of
operator differences and a classical concentration inequality in
<cit.> are used.

Since generalization error estimates in probability quantify the generalization performance of DKRR in a single trial while estimates in expectation describe   the average error, it is highly desired to deduce optimal learning rates for DKRR in probability. However,
almost all existing
results for DKRR are established in expectation <cit.>.
The main reason is
that the power of averaging in DKRR can be directly reflected by expectation, provided the samples are assumed to be drawn independently and identically according to some distribution. Our second purpose is to derive optimal learning rates for DKRR in probability, by means of a novel
error decomposition  technique motivated by <cit.>.
  Since the advantage of  averaging cannot be directly
utilized, the restriction on the number of local machines is a bit strict. Our estimates in probability support numerical observations that cannot be seen from the estimates in expectation.

Our last purpose is to
develop a communication strategy  to improve the performance of DKRR.  Combining the recently developed integral approach <cit.> with a Newton-Raphson iteration, we design a communication strategy to enlarge the number of local machines to guarantee optimal learning rates for DKRR. Our basic idea is to communicate  gradients of each local machine and utilize the Newton-Raphson iteration in the global machine to synthesize the global machine. Both theoretical analysis and numerical results are conducted to verify the power of   communications. Theoretically, we prove that, in the sense of probability, DKRR with communications can reach the optimal learning rates, while the restriction to the number of local machines is the same as that in expectation. Numerically, we exhibit that communications   enlarge the number of local machines of DKRR and thus essentially improve its learning performance.

The rest of the paper is organized as follows. In the next section, we present the communication  strategy as well as its motivation. In Section <ref>, theoretical results including optimal learning rates for DKRR in expectation, optimal learning rates for DKRR in probability and optimal learning rates for DKRR with communications in probability are given.   Section <ref> makes some comparisons between our results and related work. In Section <ref>, we provide the main tool in our analysis, where a novel concentration inequality is used to bound the difference between integral operators and their empirical counterparts and some novel error decomposition strategies are adopted to quantify the generalization error. In Section <ref>, we prove our theoretical results presented in Section <ref>. In the last section, we conduct a series of numerical studies to verify the outperformance of DKRR with communications.



§ DKRR WITH COMMUNICATIONS

In this section, we propose a novel communication strategy for DKRR to improve the learning performance.



 §.§ Limitations of DKRR without communications

Let m be the number of local machines,
D_j={(x_i,j,y_i,j)}_i=1^|D_j| be the data subset stored
in the j-th local machine  with 1≤ j≤ m and
D=⋃_j=1^mD_j be the disjoint union of {D_j}_j=1^m,
where |D_j| denotes the cardinality of D_j. Write
D_j(x):={x:(x,y)∈ D_j}. Let (ℋ_K, ·_K) be
the reproduced kernel Hilbert space (RKHS) induced by a Mercer
kernel K on a compact metric (input)  space 𝒳.  DKRR
  is  defined <cit.> with a
regularization parameter λ>0 by

    f^0_D,λ= ∑_j=1^m |D_j|/|D| f_D_j,
           λ,

where

    f_D,λ =min_f∈ℋ_K{1/|D|∑_(x, y)∈
        D(f(x)-y)^2+λf^2_K}.




The limitations of DKRR were studied in <cit.> and <cit.> by presenting a sharp upper bound of m to guarantee the comparable  performances  for DKRR and KRR. Their core idea is that the weighted average in (<ref>) cannot improve the approximation ability of KRR in  each local machine.
The representer theorem shows

    f_D_j,λ∈ℋ_K,D_j:={∑_x∈ D_j(x)a_x K_x: a_x∈ℝ},

where K_x:=K(x,·). Since ℋ_K,D_j is a |D_j|-dimensional linear space, its approximation ability becomes worse   when m increases,  just as the trend  of green line in   Figure <ref> shows. Therefore, it is impossible to derive comparable generalization errors of DKRR (blue line in Figure <ref>) and KRR with whole data (black line in Figure <ref>) when m is larger than m_1.  An ideal range of m   to guarantee the optimal generalization performance of DKRR is [1,m_1]. However, as shown in Figure <ref>, the practical range [1,m_2]  is much narrower than [1,m_1]. This phenomenon says that the main bottleneck for DKRR is not due to the approximation ability  but the fact that the weighted averaging is not good enough to compensate the loss of samples. Thus, efficient communication strategies and synthesization methods are required to enlarge the range of m to guarantee the best  generalization performance of distributed learning.




 §.§ Motivations from operator representations


Before presenting our communication strategy, we give the motivation first.  Let S_D:ℋ_K→ℝ^|D| be the sampling
operator <cit.> defined by

    S_Df:=(f(x))_(x,y)∈ D.

 Its scaled adjoint S_D^T:ℝ^|D|→ℋ_K  is
given by

    S_D^T c:=1/|D|∑_i=1^|D|c_iK_x_i,    
           c:=(c_1,c_2,…,c_|D|)^T
           ∈ℝ^|D|.

Define

    L_K,Df:=S_D^TS_Df=1/|D|∑_(x,y)∈
             Df(x)K_x.

Then, it can be  found in    <cit.> and <cit.> respectively that

    f_D,λ=(L_K,D+λ
        I)^-1S_D^Ty_D

and

    f^0_D,λ=∑_j=1^m|D_j|/|D|(L_K,D_j+λ
        I)^-1S_D_j^Ty_D_j,

where y_D:=(y_1,…,y_|D|)^T.
For an arbitrary f∈ℋ_K, we have

    f_D,λ= f -(L_K,D+λ
        I)^-1[(L_K,D+λ
        I)f-S_D^Ty_D],

and

    f^0_D,λ= f -∑_j=1^m|D_j|/|D|(L_K,D_j+λ
        I)^-1[(L_K,D_j+λ
        I)f-S_D_j^Ty_D_j].

Since the (half) gradient of the empirical risk in (<ref>) over ℋ_K on f is

    G_D,λ,f= 1/|D|∑_(x, y)∈
        D(f(x)-y)K_x+λ f=(L_K,D+λ
            I)f-S_D^Ty_D

and the Hessian is

    H_D,λ=1/|D|∑_(x, y)∈
        D⟨·,K_x⟩_KK_x+λ I=L_K,D+λ I,

(<ref>) and (<ref>) can be regarded as the well known Newton-Raphson iteration.  Comparing (<ref>) with (<ref>) and noting that the global  gradients can be achieved via communications, i.e.,
G_D,λ,f=∑_j=1^m|D_j|/|D|G_D_j,λ,f,
 we aim at designing a communication strategy
  via the Newton-Raphson iteration formed as

    f^ℓ_D,λ= f^ℓ-1_D,λ -∑_j=1^m|D_j|/|D|(L_K,D_j+λ
        I)^-1[(L_K,D+λ
        I)f^ℓ-1_D,λ -S_D^Ty_D],    ℓ∈ℕ.






 §.§ DKRR with communications


In order to derive an estimator with the operator representation (<ref>), we propose a communication strategy for DKRR(ℓ)  by iterating the following procedure for ℓ=1,…,L.

Step 1. Communicate the global estimator f^ℓ-1_D,λ  to
local machines and get the local gradient function
G_D_j,λ,ℓ:=G_D_j,λ,f^ℓ-1_D,λ.

Step 2. Communicate back {G_D_j,λ,ℓ:j=1,…,m}
 to the global machine and synthesize the global
gradient by
G_D,λ,ℓ:=∑_j=1^m|D_j|/|D|G_D_j,λ,ℓ.


Step 3. Communicate the gradient function G_D,λ,ℓ to each local machine and generate the gradient data G_j,ℓ={(x,G_D,λ,ℓ(x)):x∈ D_j(x)}. Then
  run  KRR on the data G_j,ℓ to obtain a function

    g_D_j,λ,ℓ:=min_f∈ℋ_K{1/|D_j|∑_(x, y)∈
        G_j,ℓ(f(x)-y)^2+λf^2_K},      j=1, …, m.


Step 4. Communicate back g_D_j,λ,ℓ to the global machine
and get

    f^ℓ_D,λ=
        f^ℓ-1_D,λ-
        1/λ[G_D,λ,ℓ-∑_j=1^m|D_j|/|D|
        g_D_j,λ,ℓ].


Due to (<ref>) and (<ref>), we have

    g_D_j,λ,ℓ=   (L_K,D_j+λ I)^-1L_K,D_jG_D,λ,ℓ.

This together with  the identity

    1/λ[I-(L_K,D_j+λ I)^-1L_K,D_j]G_D,λ,ℓ
       =(L_K,D_j+λ I)^-1G_D,λ,ℓ

and (<ref>) yields (<ref>). The training and testing flows of  DKRR(ℓ) are exhibited in Figure <ref>. Comparing Figure <ref> with Figure <ref>, communications are required in both  training and testing stages of DKRR(ℓ). Noticing that communicating functions are infeasible in practice, Appendix B presents a simple realization for DKRR(ℓ) by communicating input data. We believe that there are other efficient implementations of DKRR(ℓ) and leave it as   future studies.





§ MAIN RESULTS


In this section, we analyze the generalization performances of the proposed algorithm as well as DKRR in a standard regression setting
<cit.>.  Let  a sample D={(x_i,y_i)}_i=1^N be
independently drawn according to ρ,  a Borel probability
measure  on 𝒵 :=𝒳×𝒴 with  𝒴=ℝ . The
primary objective is the regression function defined by

    f_ρ(x)=∫_𝒴 y dρ(y|x),      x∈𝒳,

where ρ(y|x) denotes the conditional distribution at x
induced by ρ.
Throughout the paper, we assume that K is a Mercer kernel and
𝒳 is compact, which implies
κ:=√(sup_x∈𝒳K(x,x))<∞.






 §.§ Optimal learning rates for DKRR in expectation


  To derive   optimal learning rates for
DKRR, we need   some assumptions on the decay of the outputs,
regularity of the regression function and capacity of ℋ_K.



 We
assume
  ∫_𝒴
 y^2dρ<∞ and

    ∫_𝒴(e^|y-f_ρ(x)|/M-|y-f_ρ(x)|/M-1)dρ(y|x)≤γ^2/2M^2,     ∀ x∈𝒳,

where M and γ are positive constants.


   Condition (<ref>) is
 satisfied  if the noise is uniformly bounded,
Gaussian or sub-Gaussian <cit.>. Let ρ_X be the marginal distribution of ρ and
L^2_ρ__X be the Hilbert space of ρ_X square integrable
functions on 𝒳, with norm denoted by ·_ρ.
The Mercer kernel K: 𝒳×𝒳→ℛ defines an integral operator L_K on
ℋ_K (or L_ρ_X^2) by

    L_Kf =∫_𝒳 K_x f(x)dρ_X,      f∈ℋ_K    ( f∈ L_ρ_X^2).

Our second assumption is the capacity assumption measured by the
effective dimension <cit.>,

    𝒩(λ)= Tr((λ I+L_K)^-1L_K),      λ>0.



 There exists some s∈(0,1] such that

    𝒩(λ)≤ C_0λ^-s,

where C_0≥ 1 is  a constant independent of λ.

  Condition (<ref>) with s=1 is always satisfied by taking the constant
C_0=(L_K)≤κ^2. For 0<s<1,   it was shown in
<cit.> that (<ref>) is slightly
more general than the eigenvalue decaying assumption in the
literature <cit.> and has been employed in
<cit.> to
derive optimal learning rates for kernel-based algorithms.


For r>0, assume

    f_ρ=L_K^r h_ρ,   for some  h_ρ∈ L_ρ_X^2,

where L_K^r denotes the r-th power of L_K: L_ρ_X^2 →
L_ρ_X^2 as a compact and positive operator.


The regularity condition (<ref>) describes the
regularity of f_ρ and has been adopted in a large literature to
quantify  learning rates for some algorithms
<cit.>. Based
on the above three assumptions, we can derive the following optimal
learning rates for DKRR in expectation.



  Under Assumptions 1-3 with  1/2≤ r≤ 1 and
 0<s≤ 1, if λ=|D|^-1/2r+s, |D_1|=…=|D_m| and

    m≤ C_1|D|^2r+s-1/2r+s(log|D|)^-3,

 then

    E[ f^0_D,λ-f_ρ_ρ^2]≤ C_2
         |D|^-2r/2r+s,

where  C_1,C_2 are constants independent of |D| or m, whose
 values will be given explicitly  in the proof.



Theorem <ref> exhibits optimal
learning rates for DKRR in expectation under the restriction
(<ref>). In previous studies
<cit.>, optimal learning rates for
DKRR are built upon the restriction

    m≤ |D|^2r-1/2r+s.

A direct consequence is that if r=1/2, then   DKRR with m=|D|^θ for an arbitrarily small θ>0 may not achieve the optimal learning, according to the existing work. In particular, it was shown in <cit.> that a parameter value for λ larger than |D|^-1/(2r+s) is required under this circumstance, which leads to a sub-optimal learning rate. Comparing (<ref>) with (<ref>), we
relax the restriction on m so that optimal learning rates for
DKRR also hold  for r=1/2.
 The restriction (<ref>) with r=1/2 is similar   to that in <cit.>.
However, we remove  the eigenfunction assumption in <cit.>
and derive optimal learning rates for DKRR under Assumption
<ref> with 1/2≤ r≤ 1.   It should be mentioned that removing the eigenfunction assumption in <cit.> was already made in a series of previous papers <cit.>. However, an additional level of regularity, r>1/2 is imposed due to (<ref>), excluding r=1/2 for <cit.>.  Our study in Theorem <ref> successfully fills this gap.















 §.§ Optimal learning rates for DKRR in probability

Theorem <ref> presented optimal learning rates   for DKRR in expectation. However, the expectation describes the average information for multiple trails and fails to capture the learning performance of DKRR for a single trail.  This explains  the inconsistency between the theoretical result in Theorem <ref> and numerical observation in Figure <ref>, where m_2 is much smaller than m_1.
In the following theorem, we deduce   learning rates for DKRR in
probability.



Let 0<δ<1. Under Assumptions  1-3  with
  1/2≤ r≤ 1 and
0<s≤ 1, if λ=|D|^-1/2r+s,
|D_1|=…=|D_m|,

    m≤|D|^2r+s-1/4r+2s/C_3log^3|D|,

and

    16|D|^2r+s-1/4r+2sexp{- C_4|D|^2r+s-1/8r+4slog|D|}≤δ,

 then with confidence at least
1-δ, there holds

    f^0_D,λ-f_ρ_ρ≤ C_5
         |D|^-r/2r+slog^28/δ,

where C_3,C_4,C_5 are constants independent of |D|, m or
δ, whose values will be given explicitly in the proof.


It has been a difficult task to derive optimal learning rates for DKRR in probability as shown in  (<ref>).  Compared with the  classical error decomposition in expectation <cit.>, where the generalization error is decomposed into approximation error, sample error and distributed error, the error decomposition in probability  is totally different. In particular, it is   not easy to separate a distributed error in probability to control the number of local machines. As a consequence,  the upper bound of  (<ref>) is  tighter than that of (<ref>), showing a stricter restriction on m to guarantee the optimal learning rate in probability. Neglecting the logarithmic fact, we have |D|^2r+s-1/4r+2s=√(|D|^2r+s-1/2r+s). Noting that m_2∼√(m_1) in Figure <ref>, the error estimate in probability coincides with the numerical results, showing the power of estimate in probability.  Based on the confidence-based error estimate in Theorem <ref>, we can   derive   almost sure
convergence of DKRR.



Under Assumption <ref>, Assumption
<ref> with 1/2≤ r≤ 1 and
Assumption <ref>   with 0<s≤ 1,
if λ=|D|^-1/2r+s, |D_1|=…=|D_m| and
(<ref>) holds,
 then for any ε>0, there holds

    lim_|D|→∞|D|^r/2r+s(1-ε)f_D,λ^0-f_ρ_ρ=0.






 §.§ Optimal learning rates for DKRR with communications



In the previous  subsection, we presented  theoretical limitations of DKRR in terms of a small range of m to guarantee the optimal learning rate in probability. In the following  theorem, we show that our proposed communication strategy can improve the performance of DKRR.



Let 0<δ<1.  Under Assumptions 1-3
  with 1/2≤ r≤ 1 and
  0<s≤ 1, if
λ=|D|^-1/2r+s, |D_1|=…=|D_m|,

    m≤|D|^(2r+s-1)(ℓ+1)/(2r+s)(ℓ+2)/C_6log^3|D|,

and

    |D|^(2r+s-1)(ℓ+1)/(2r+s)(ℓ+2)/C_7log^3|D|exp{-|D|^2r+s-1/2(2r+s)(ℓ+2)log|D|}≤δ<1,

 then with confidence at least
1-δ, there holds

    f^ℓ_D,λ-f_ρ_ρ≤
         C_8
         |D|^-r/2r+slog^ℓ+24/δ,

where C_6,C_7,C_8 are constants independent of m, δ or
|D|, whose value will be given  explicitly in the proof.


Comparing (<ref>) with (<ref>), the proposed communication strategy  relaxes
the restriction on m from order |D|^2r+s-1/4r+2s  to |D|^(2r+s-1)(ℓ+1)/(2r+s)(ℓ+2). Furthermore, the upper bound of m is monotonically increasing with the number of communications,   showing the   power  of   communications in DKRR. As ℓ→∞,  up to a logarithmic factor, the restriction tends to  the best one in (<ref>).    At the first glance, the restriction  (<ref>) is always worse than (<ref>), contradicting our assertions on the outperformance of communications.   However, it should be highlighted that (<ref>) only guarantees the error bound in expectation. This means that if m satisfies (<ref>), we cannot conduct feasibility analysis of DKRR via a single (or  finite many) trial.  Figure 2 numerically shows the drawback of analysis in expectation.  Theorem <ref> conducts the error analysis in probability, a totally different theoretical framework from Theorem <ref>. In this framework, Theorem <ref> shows that communications improve the performance of DKRR since (<ref>) is better than (<ref>). It will be shown in Proposition <ref> below that under (<ref>), the error of DKRR(ℓ) converges exponentially fast with respect to the number of communications, meaning that only a small ℓ in DKRR(ℓ) is required to get a satisfactory error bound in probability.
Based on Theorem <ref>,   we  present   almost sure
convergence of DKRR with communications.


Under Assumptions <ref>-
<ref> with  1/2≤ r≤ 1   and 0<s≤ 1,
if λ=|D|^-1/2r+s, |D_1|=…=|D_m| and
(<ref>) holds,
 then for
any ε>0, there holds

    lim_|D|→∞|D|^r/2r+s(1-ε)f_D,λ^ℓ-f_ρ_ρ=0.






§ RELATED WORK AND DISCUSSIONS

Kernel ridge regression (KRR) is a classical learning algorithm for regression and has been extensively studied in statistics and learning theory. Optimal learning rates for KRR were   established in <cit.>.
For DKRR,   optimal learning rates were deduced in <cit.> under Assumption  1, Assumption 3  with r=1/2,  some eigenvalue decaying assumption that is similar to Assumption 2, and an additional boundedness assumption for the eigenfunctions. In our   paper <cit.>, we removed the eigenfunction  assumption by introducing a novel integral operator approach as well as a second-order decomposition for operator difference <cit.>. However,   optimal learning rates for DKRR <cit.> were derived under Assumption 3 with 1/2<r≤ 1, excluding the most popular case r=1/2, i.e. f_ρ∈ℋ_K.  Although several recent work <cit.> focused on conquering this theoretical drawback, there is  no essential improvement in presenting a good bound for  the number of local machines according to the theory of <cit.>. In this paper, we succeed in deriving a tight bound for the number of local machines as (<ref>) by applying the  concentration inequality established in <cit.> to describe the similarity   of different operators (see the next section for detailed descriptions). Different from <cit.>,  Theorem <ref> in this paper removes the eigenfunction assumption of <cit.> without presenting additional regularity assumption.


Previous optimal learning rates for DKRR <cit.> were built in  expectation. Technically, the generalization error in expectation can be divided into the   approximation
error, sample error and distributed error <cit.> by using the unbiasedness property E[y|x]=f_ρ(x).
 The approximation error,
independent of the sample, describes the approximation capability of the hypothesis space.
 The sample error connects the synthesized estimator
(<ref>) with the estimator (<ref>) by showing an additional
|D_j|/|D| in the sample error for local estimators.
The distributed error   measures  the  limitation of the distributed
learning algorithm (<ref>) and presents the upper bound of m to guarantee optimal learning rates for DKRR.   Our error estimate in expectation also follows from this classical error decomposition (see  Lemma <ref> below). However,  this widely used   error decomposition is  not applicable to   DKRR in probability  since there lacks an expectation operator to realize the  unbiasedness E[y|x]=f_ρ(x).
Thus, it requires novel approaches to deduce  optimal  learning rates for DKRR in probability. According to an explicit operator representation for the kernel-based gradient descent algorithm, optimal learning rates as well as a novel error decomposition based on its operator representation for distributed gradient descent algorithms were established in probability in <cit.>. Using the similar error decomposition as <cit.>, a   minimum error entropy algorithm with   distributed gradient descents was proposed in <cit.> and a tight learning rate was derived.  However, DKRR requires the computation  of the inverse matrix (or operator),   the error decomposition of gradient descent algorithm in <cit.>  is not suitable for DKRR. In this paper, as shown in Proposition <ref> below, we succeed in deriving a novel error decomposition for DKRR by introducing some measurements to quantify the difference between integral operators and their empirical counterparts. Then, applying the recently developed concentration inequalities for positive operators <cit.>, we derive optimal learning rates for DKRR in probability under much looser restriction on m than <cit.>.

Numerous communication strategies <cit.> were proposed to improve the learning performance of distributed learning algorithms in the framework of parametric regression (linear regression). To the best of our knowledge, our proposed communication strategy  is the first work focusing on improving the performance of learning algorithms in nonparametric regression.  As shown in Figure <ref>, nonparametric regression transmits function values and protects the privacy of local machines,  while parametric regression <cit.> transmits coefficients that disclose the detailed information for local estimators. The most related work is <cit.>, where a communication strategy based on Newton-Raphson iterations is proposed to equip ridge regression in linear regression. Our work differs from <cit.> in the following three aspects. Firstly, our analysis is carried out in nonparametric regression rather than linear regression. Secondly, the communication strategy is based on the operator representation, which is exclusive for kernel approaches. Thirdly, our theory focuses on enlarging the range of number of local machines rather than improving the learning rate  of distributed learning algorithms, since DKRR without communications is already optimal for not so large m based on previous studies <cit.>.
It would be interesting to extend our communication strategy to other distributed learning schemes such as distributed learning with convolutional neural networks in deep learning <cit.>.



§ OPERATOR SIMILARITIES AND ERROR DECOMPOSITION

We analyze the learning performance of DKRR(ℓ) by using the
integral operator approach presented in
 <cit.>. Our novelty in analysis
is   tight bounds on quantifying the similarity between different
operator. These bounds together with the exclusive error
decomposition yield   optimal learning rates for DKRR and show the
advantage of communications in distributed learning.






 §.§ Similarities of operators



The similarity between f^ℓ_D,λ and
f_D,λ depends heavily on  that between the
operator L_K and L_K,D.
The classical method for analyzing similarity between L_K and
L_K,D is to bound the norm of operator difference L_K-L_K,D.
By using a concentration inequality in Hilbert spaces  from
<cit.>, it can be found in   <cit.> that for any
δ∈(0,1), with confidence at least 1-δ, there holds

    𝒮_D,λ:=(L_K+λ I)^-1/2(L_K-L_K,D)≤
             2κ(κ+1)𝒜_D,λlog2/δ,

where

    𝒜_D,λ:=1/√(|D|)(1/√(|D|λ)
               +√(𝒩(λ))).


 The bound in (<ref>) is tight. However, in estimating
the difference between f_D,λ and
f^ℓ_D,λ, one also needs to estimate

    ℛ_D,λ:=(L_K+λ I)^-1/2(L_K-L_K,D)(L_K+λ I)^-1/2.

 A
classical approach <cit.> is to use
ℛ_D,λ≤1/√(λ)𝒮_D,λ and get that

    ℛ_D,λ≤
         2κ(κ+1)λ^-1/2𝒜_D,λlog2/δ

holds with confidence 1-δ. The leading term in (<ref>) is √(𝒩(λ))/√(|D|λ) for
λ≥ |D|^-1. In the following lemma, which will be proved
in Appendix A, we  reduce the leading
term for bounding ℛ_D,λ  from
√(𝒩(λ))/√(|D|λ) to
√(log𝒩(λ))/√(|D|λ) by using a new concentration inequality for
self-adjoint operators <cit.>.



Let 0<δ≤ 1. If 0<λ≤1 and 𝒩(λ)≥ 1, then
  with confidence 1-δ, there
holds

    ℛ_D,λ≤ C_1^*ℬ_D,λlog4/δ,

where C_1^*:=max{(κ^2+1)/3,2√(κ^2+1)} and

    ℬ_D,λ:=
               1+log𝒩(λ)/λ|D|+ √(1+log𝒩(λ)/λ|D|).




Besides the differences between ℛ_D,λ and 𝒮_D,λ, another quantity to measure the similarity between
L_K,D and L_K is the operator product (L_K+λ
I)^1/2(L_K,D+λ I)^-1/2. A recently developed second
order decomposition for positive operators <cit.>
  asserts that  if A and B are
invertible operators on a Banach space, then

    A^-1-B^-1
              =
              B^-1(B-A)B^-1(B-A)A^-1+B^-1(B-A)B^-1.

This implies the following decomposition of the operator product

    BA^-1
       =(B-A)B^-1(B-A)A^-1+(B-A)B^-1+I.

Inserting A=L_K,D+λ I and B=L_K+λ I to
(<ref>) and noting
(<ref>), it is easy to derive the following upper bound for
(L_K+λ I)(L_K,D+λ I)^-1 (e.g., <cit.>):
  for any 0<δ<1, with confidence at least
1-δ, there holds

    (L_K+λ I)(L_K,D+λ I)^-1≤
              2[(2κ/√(|D|λ)(κ/√(|D|λ)
               +√(𝒩(λ)))log2/δ)^2  +1].

Hence, according to the   Cordes inequality <cit.> 

    A^τ B^τ≤AB^τ,      0<τ≤ 1,

  we have

    𝒬_D,λ   :=   (L_K+λ I)^1/2(L_K,D+λ I)^-1/2
       ≤   √(2[(2κ/√(|D|λ)(κ/√(|D|λ)
               +√(𝒩(λ)))log2/δ)^2  +1]).

The leading term of the  right-hand side of (<ref>) is
√(𝒩(λ))/√(|D|λ).  In the
following lemma, whose proof is postponed to Appendix A,  we improve
(<ref>) by using Lemma <ref>.




Assume   0<λ≤ 1 and 𝒩(λ)≥ 1.
 For δ≥ 4exp{-1/(2C_1^*ℬ_D,λ)} , with
confidence 1-δ, there holds

    𝒬_D,λ≤√(2).





In (<ref>), to guarantee the boundedness of 𝒬_D,λ, it requires √(𝒩(λ))/√(|D|λ)log2/δ≤ C_2^* for
some C_2^*>0 depending only on κ. However, in Lemma
<ref>, recalling (<ref>), it is
sufficient that
  log(𝒩(λ))/√(|D|λ)log2/δ≤ C_3^* for
some C_3^*>0 depending only on κ.




 §.§ Error decomposition for DKRR in expectation


We use the error decomposition for DKRR in <cit.>, where
the data-free limit and noise-free
  version  of f_D_j,λ,

    f_λ =min_f∈ℋ_K{∫_𝒳(f(x)-f_ρ(x))^2dρ_X+λf^2_K}
        =(L_K+λ I)^-1L_Kf_ρ.

and

    f^♢_D_j,λ:=E[f_D_j,λ|D_j(x)]=(L_K,D_j+λ
      I)^-1L_K,D_jf_ρ

  are utilized.
The following lemma can be found in <cit.>.


 Let f^0_D,λ be defined by (<ref>).
 We have
 
    1/2E[f_D,λ^0-f_ρ_ρ^2]
            ≤f_λ-f_ρ_ρ^2+
             ∑_j=1^m|D_j|^2/|D|^2E[f_D_j,λ
             -f_λ_ρ^2]
            +∑_j=1^m|D_j|/|D|
            E[f^♢_D_j,λ-f_λ_ρ^2].



The three  terms on the  right-hand side of (<ref>)  are respectively the approximation error, sample error and distributed
error. Based on Lemma <ref>, we can
derive the following error decomposition for DKRR in expectation.


Let f_D,λ^0 be defined by (<ref>). If
f_ρ∈ℋ_K, then

    1/2E[f_D,λ^0-f_ρ_ρ^2]
               ≤   f_λ-f_ρ_ρ^2+
             ∑_j=1^m|D_j|^2/|D|^2E[ 𝒬_D_j,λ^4(𝒫_D_j,λ+𝒮_D_j,λf_λ_K) ^2  ]  
       +   ∑_j=1^m|D_j|/|D|
            E[𝒬_D_j,λ^4ℛ^2_D_j,λ(L_K+λ
        I)^1/2(f_λ-f_ρ)_K^2],

where

    𝒫_D,λ:=
             (L_K+λ
              I)^-1/2(L_Kf_ρ-S^T_Dy_D)_K.



Proof.  We  first bound the sample error. It
follows from (<ref>) and (<ref>) that

    f_D,λ-f_λ
       =
       (L_K,D+λ I)^-1S_D^Ty_D
       -
       (L_K+λ I)^-1L_Kf_ρ
       =   
       (L_K,D+λ I)^-1(S^T_Dy_D-L_Kf_ρ)+[(L_K,D+λ I)^-1
       -
       (L_K+λ I)^-1]L_Kf_ρ
       =   
       (L_K,D+λ I)^-1/2(L_K,D+λ I)^-1/2(L_K+λ I)^1/2(L_K+λ
       I)^-1/2(S^T_Dy_D-L_Kf_ρ)
       +   
       (L_K,D+λ I)^-1/2(L_K,D+λ I)^-1/2(L_K+λ
       I)^1/2
       (L_K+λ
       I)^-1/2(L_K-L_K,D)f_λ.

So

    (L_K+λ I)^1/2(f_D_j,λ-f_λ)_K
            ≤𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K).

Then, we bound the distributed error. Due to
(<ref>) and (<ref>), we get

    f^♢_D,λ-f_λ
      =
       (L_K,D+λ I)^-1L_K,Df_ρ-(L_K+λ
       I)^-1L_Kf_ρ
       =   
       (L_K,D+λ I)^-1(L_K,D-L_K)f_ρ
      +[(L_K,D+λ I)^-1-(L_K+λ I)^-1]L_Kf_ρ
       =   
      (L_K,D+λ I)^-1(L_K,D-L_K)f_ρ+(L_K,D+λ I)^-1(L_K-L_K,D)
      f_λ
       =   
      (L_K,D+λ I)^-1(L_K,D-L_K)(f_ρ-f_λ)
       =   
       (L_K,D+λ I)^-1(L_K+λ I)^1/2 (L_K+λ I)^-1/2(L_K,D-L_K)(L_K+λ I)^-1/2
          (L_K+λ I)^1/2(f_ρ-f_λ).

Combining this with f_ρ∈ℋ_K yields

    (L_K+λ I)^1/2(f^♢_D_j,λ-f_λ)_K
        ≤𝒬_D_j,λ^2ℛ_D_j,λ(L_K+λ
        I)^1/2(f_λ-f_ρ)_K.

Plugging (<ref>) and (<ref>) into (<ref>), we have

    1/2E[f_D,λ^0-f_ρ_ρ^2]
               ≤   f_λ-f_ρ_ρ^2+
             ∑_j=1^m|D_j|^2/|D|^2E[ 𝒬_D_j,λ^4(𝒫_D_j,λ+𝒮_D_j,λf_λ_K) ^2  ]
       +   ∑_j=1^m|D_j|/|D|
            E[𝒬_D_j,λ^4ℛ^2_D_j,λ(L_K+λ
        I)^1/2(f_λ-f_ρ)_K^2].

This completes the proof of Proposition <ref>. 




 §.§ Error decomposition for DKRR in probability

 To deduce learning rates for
DKRR in probability, we need the following error decomposition. It holds for
f_D,λ^0-f_D,λ_ρ, which is
totally different from Proposition <ref> focusing  on the expectation.



Let f_D,λ^0 be defined by (<ref>). Then

    f_D,λ^0-f_D,λ_ρ≤(L_K+λ I)^1/2
       (f_D,λ^0-f_D,λ)_K
       ≤   𝒬_D,λ^2∑_j=1^m|D_j|/|D|(ℛ_D_j,λ+ℛ_D,λ) 𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K).



Proof.
 From the definition of f_D,λ^0, we see

    f_D,λ^0-f_D,λ
          =
          ∑_j=1^m|D_j|/|D|(L_K,D_j+λ
          I)^-1S_D_j^Ty_D_j -(L_K,D+λ I)^-1S_D^Ty_D
       =   ∑_j=1^m|D_j|/|D|[(L_K,D_j+λ
          I)^-1-(L_K,D+λ
          I)^-1]S_D_j^Ty_D_j
       =   ∑_j=1^m|D_j|/|D|(L_K,D+λ
          I)^-1(L_K,D-L_K,D_j)f_D_j,λ
       =   ∑_j=1^m|D_j|/|D|(L_K,D+λ
          I)^-1(L_K,D-L_K)(f_D_j,λ-f_λ)
       +   ∑_j=1^m|D_j|/|D|(L_K,D+λ
          I)^-1(L_K-L_K,D_j)(f_D_j,λ-f_λ)
       =   (L_K,D+λ
          I)^-1(L_K+λ I)^1/2(L_K+λ
          I)^-1/2(L_K,D-L_K)(L_K+λ
          I)^-1/2
          ∑_j=1^m|D_j|/|D|(L_K+λ
          I)^1/2(f_D_j,λ-f_λ)
       +   
         (L_K,D+λ
          I)^-1(L_K+λ I)^1/2
          ∑_j=1^m|D_j|/|D|(L_K+λ
          I)^-1/2(L_K,D-L_K)(L_K+λ I)^-1/2(L_K+λ
          I)^1/2(f_D_j,λ-f_λ).

Then,

    (L_K+λ I)^1/2
       (f_D,λ^0-f_D,λ)_K
      ≤𝒬_D,λ^2ℛ_D,λ∑_j=1^m|D_j|/|D|(L_K+λ
      I)^1/2(f_D_j,λ-f_λ)_K
       +   𝒬_D,λ^2
        ∑_j=1^m|D_j|/|D|ℛ_D_j,λ(L_K+λ
      I)^1/2(f_D_j,λ-f_λ)_K.

This together with (<ref>) gives

    f_D,λ^0-f_D,λ_ρ   ≤   𝒬_D,λ^2ℛ_D,λ∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K)
       +   𝒬_D,λ^2∑_j=1^m|D_j|/|D|ℛ_D_j,λ𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K).

This completes the proof of Proposition <ref>. 



 §.§ Error decomposition for DKRR(ℓ)

In this subsection, we derive an error decomposition for
DKRR(ℓ). At first, we   show  in the following proposition the
power of communications.


Let ℓ≥0. We have

    (L_K+λ I)^1/2 (f_D,λ^ℓ-
        f_D,λ)_K    
       ≤   (∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2
        (ℛ_D_j,λ+
        ℛ_D,λ))^ℓ(L_K+λ
        I)^1/2(f_D,λ^0- f_D,λ)_K.



Proof. Since

    f_D,λ=f_D,λ^ℓ-1-(L_K,D+λ I)^-1[(L_K,D+λ
          I)f_D,λ^ℓ-1-S_D^Ty_D],

we have

    f_D,λ-f_D,λ^ℓ
         =f^ℓ-1_D,λ
        -
        ∑_j=1^m|D_j|/|D|(L_K,D_j+λ I)^-1[(L_K,D+λ
            I)f^ℓ-1_D,λ-S_D^Ty_D]
       -   f_D,λ^ℓ-1+(L_K,D+λ I)^-1[(L_K,D+λ
          I)f_D,λ^ℓ-1-S_D^Ty_D]
       =   ∑_j=1^m|D_j|/|D|[(L_K,D_j+λ I)^-1
          -(L_K,D+λ I)^-1][(L_K,D+λ
            I)f^ℓ-1_D,λ-S_D^Ty_D]
       =   ∑_j=1^m|D_j|/|D| (L_K,D_j+λ
            I)^-1(L_K,D-L_K,D_j)
           (L_K,D+λ I)^-1[(L_K,D+λ
            I)f^ℓ-1_D,λ-S_D^Ty_D]
       =   ∑_j=1^m|D_j|/|D| (L_K,D_j+λ
            I)^-1(L_K,D-L_K,D_j)
            ( f^ℓ-1_D,λ-f_D,λ)
       =   ∑_j=1^m|D_j|/|D| (L_K,D_j+λ
            I)^-1(L_K,D-L_K)
            ( f^ℓ-1_D,λ-f_D,λ)
       +   ∑_j=1^m|D_j|/|D| (L_K,D_j+λ
            I)^-1(L_K-L_K,D_j)
            ( f^ℓ-1_D,λ-f_D,λ)
       =:   𝒰_D,λ,1+𝒰_D,λ,2.

Since

    (L_K+λ I)^1/2𝒰_D,λ,1
       =   ∑_j=1^m|D_j|/|D|(L_K+λ I)^1/2 (L_K,D_j+λ
            I)^-1(L_K+λ I)^1/2 (L_K+λ
            I)^-1/2(L_K,D-L_K)
       ×   
            (L_K+λ I)^-1/2(L_K+λ I)^1/2( f^ℓ-1_D,λ-f_D,λ),

we have

    (L_K+λ I)^1/2𝒰_D,λ,1_K
        ≤∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2 ℛ_D,λ(L_K+λ
        I)^1/2(f_D,λ^ℓ-1- f_D,λ)_K.

Similarly, we find

    (L_K+λ I)^1/2𝒰_D,λ,2_K
        ≤∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2 ℛ_D_j,λ(L_K+λ
        I)^1/2(f_D,λ^ℓ-1- f_D,λ)_K.

Then,

    (L_K+λ I)^1/2 (f_D,λ^ℓ-
        f_D,λ)_K
       ≤   (∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2
        ℛ_D_j,λ+ ∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2
        ℛ_D,λ)(L_K+λ
        I)^1/2(f_D,λ^ℓ-1- f_D,λ)_K
       ≤   (∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2
       ℛ_D_j,λ+ ∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2
       ℛ_D,λ)^ℓ(L_K+λ
        I)^1/2(f_D,λ^0- f_D,λ)_K.

This completes the proof of Proposition <ref>. 


Combining Proposition <ref> with
Proposition <ref>, we can
derive the following error decomposition for DKRR(ℓ).



Let ℓ≥0. We have

    (L_K+λ I)^1/2 (f_D,λ^ℓ-
        f_D,λ)_K
         ≤(∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2
        (ℛ_D_j,λ+ℛ_D,λ)
        )^ℓ
       ×   𝒬_D,λ^2∑_j=1^m|D_j|/|D|(ℛ_D,λ+ℛ_D_j,λ) 𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K).








§ PROOFS

In this section, we present proofs of our main results.



 §.§ Optimal learning rates for DKRR in expectation


In this subsection, we prove optimal learning rates for DKRR in
expectation. We need the following general theorem based
on Assumption <ref> and Assumption
<ref>

Under Assumption <ref> with 1/2≤ r≤
1 and Assumption <ref>, if
0<λ≤1 and 𝒩(λ)≥ 1, then

    E[f_D,λ^0-f_ρ_ρ^2]
               ≤   
             2λ^2r+
             24∑_j=1^m|D_j|^2/|D|^2(exp{-1/(2C_1^*ℬ_D_j,λ)}
       +
        C̃_1^2𝒜^2_D_j,λ)
               
       +   ∑_j=1^m|D_j|/|D|(16exp{-1/(2C_1^*ℬ_D_j,λ)}
       +
       32C̃_2^2ℬ^2_D_j,λλ^2r).

where C̃_1:=2(2(κ
        M+γ)(κ+1)+2κ^2r(2κ+1)h_ρ_ρ) and
        C̃_̃2̃:=4κ(κ+1)h_ρ_ρ.


Proof. Due to  Assumption <ref> with
r≥ 1/2, we obtain

    f_λ_K=(L_K+λ
           I)^-1L_KL_K^rh_ρ≤κ^2r-1L_K^1/2h_ρ_K
           =κ^2r-1h_ρ_ρ.

Moreover  (<ref>) implies
<cit.> that with confidence at least
1-δ, there holds

    𝒫_D_j,λ≤   2(κ M+γ)(κ+1)𝒜_D_j,λlog2/δ.

Thus, for δ≥ 12exp{-1/(2C_1^*ℬ_D_j,λ)}, it follows from Lemma <ref>, (<ref>), (<ref>) and (<ref>) that with confidence 1-δ, there holds

    𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K)
            ≤C̃_1𝒜_D_j,λlog6/δ,    ∀        j=1,…,m.

 Using the probability to expectation formula

    E[ξ] =∫_0^∞ P[ξ > t] d t

  to the positive random variable ξ_1,j =
 𝒬^4_D_j,λ(𝒫_D_j,λ+ 𝒮_D_j,λf_λ_K)^2 for any
         j=1,…,m,
we have

    E[ξ_1,j]=∫_0^∞ P[ξ_1,j > t] d t
       =   ∫_0^12exp{-1/(2C_1^*ℬ_D_j,λ)} P[ξ_1,j > t] d t
      +
      ∫_12exp{-1/(2C_1^*ℬ_D_j,λ)}^∞ P[ξ_1,j > t] d
       t
       ≤   
       12exp{-1/(2C_1^*ℬ_D_j,λ)}
       +
        ∫_12exp{-1/(2C_1^*ℬ_D_j,λ)}^∞
        P[ ξ_1,j>t]dt.

When t≥ 12exp{-1/(2C_1^*ℬ_D_j,λ)}, it
follows from (<ref>) that

    P[ ξ_1,j>t]
             ≤
             6exp{-C̃_1^-1𝒜_D_j,λ^-1t^1/2},    ∀ j=1,…,m,

and

    ∫_12exp{-1/(2C_1^*ℬ_D_j,λ)}^∞
       P[ξ_1,j>t]dt
            ≤
        6∫_0^∞exp{-C̃_1^-1𝒜_D_j,λ^-1t^1/2}dt
       ≤   
        12C̃_1^2𝒜^2_D_j,λ∫_0^∞ ue^-udu=12C̃_1^2𝒜^2_D_j,λ.

Thus,

    E[ 𝒬_D_j,λ^4(𝒫_D_j,λ+𝒮_D_j,λf_λ_K) ^2  ]
            ≤
           12exp{-1/(2C_1^*ℬ_D_j,λ)}
       +
       12C̃_1^2𝒜^2_D_j,λ.

Due to   Assumption <ref> with r≥1/2, we
have

    (L_K+λ I)^1/2(f_λ-f_ρ)_K
          ≤λ(L_K+λ I)^-1/2L_K^r+1/2h_ρ_ρ≤λ^rh_ρ_ρ.

Then, Lemma <ref> and Lemma
<ref> with
δ≥8exp{-1/(2C_1^*ℬ_D_j,λ)} yield that
 with confidence
1-δ, there holds

    𝒬_D_j,λ^2 ℛ_D_j,λ(L_K+λ
        I)^1/2(f_λ-f_ρ)_K≤C̃_2ℬ_D_j,λλ^rlog8/δ,    ∀ j=1,…,m.

 Then, applying (<ref>) to ξ_2,j =𝒬_D_j,λ^4 ℛ^2_D_j,λ(L_K+λ
    I)^1/2(f_λ-f_ρ)_K^2 and using the same approach as
    above,
we can derive for any j=1,…,m,

    E[𝒬_D_j,λ^4
       ℛ^2_D_j,λ(L_K+λ
        I)^1/2(f_λ-f_ρ)_K^2] ≤
       8exp{-1/(2C_1^*ℬ_D_j,λ)}
       +
       16C̃_2^2ℬ^2_D_j,λλ^2r.

Plugging (<ref>), (<ref>) and
(<ref>) into (<ref>), we get (<ref>) directly.
This completes the proof of Theorem <ref>. 

Based on Theorem <ref>, we can
prove Theorem <ref> as follows.


Proof of Theorem <ref>.
For
C_1:=min{2r+s/2s,(2r+s)^3/2rsmax{(κ^2+1)/3,2√(κ^2+1)}},
due to (<ref>), |D_1|=…=|D_m|,
λ=|D|^-1/2r+s and (<ref>), we
have for any j=1,…,m,

    ℬ_D_j,λ   ≤   2s/2r+sm|D|^-2r+s-1/2r+slog|D|
        +
        √(2s/2r+sm|D|^-2r+s-1/2r+slog|D|).

Noting C_1^*=max{(κ^2+1)/3,2√(κ^2+1)}, we see that
(<ref>) implies

    ℬ_D_j,λ≤2r+s/4rC_1^*log|D|

and

    exp{-1/(2C_1^*ℬ_D_j,λ)}≤
        |D|^-2r/2r+s,    ∀ j=1,…,m.

According to (<ref>), |D_1|=…=|D_m|,
λ=|D|^-1/2r+s and (<ref>), we
also get

    𝒜_D_j,λ≤
        m|D|^-4r+2s-1/4r+2s+√(m)|D|^-r/2r+s,    ∀ j=1,…,m.

Inserting (<ref>), (<ref>) and (<ref>) into (<ref>) and noting
λ=|D|^-1/2r+s and (<ref>), we have

    E[f_D,λ^0-f_ρ_ρ^2]
           ≤
           C_1|D|^-2r/2r+s,

where
C_2:=42+48C̃_1^2+32C̃_2^2(2r+s/4rC_1^*)^2.
This completes the proof of Theorem <ref>. 






 §.§ Optimal learning rates for DKRR in probability



In this subsection, we prove Theorem <ref>. To this end, we need the following theorem for
DKRR in probability.


  Under Assumption <ref>   and  Assumption <ref> with
1/2≤ r≤ 1, if 0<λ≤1, 𝒩(λ)≥
1, and

    16mexp{-1/(2C_1^*ℬ_D_j,λ)}<1,    ∀
      j=1,…,m,

  then for

    16mexp{-1/(2C_1^*ℬ_D_j,λ)}≤δ<1,     ∀
      j=1,…,m,

 with confidence 1-δ there holds

    f_D,λ^0-f_D,λ_ρ≤C̃_̃3̃log^2(4m)∑_j=1^m|D_j|/|D|𝒜_D_j,λℬ_D_j,λlog^24/δ,

  where C̃_3=16C_1^*C̃_1.





Proof. Let j∈{1,…,m} be fixed. It follows from Lemma
<ref> and ℬ_D,λ≤ℬ_D_j,λ that with confidence 1-δ/4,
there holds

    ℛ_D,λ+ℛ_D_j,λ≤
          2C_1^*ℬ_D_j,λlog16/δ.

Since δ≥ 16exp{-1/(2C_1^*ℬ_D_j,λ)},
Lemma <ref> together with (<ref>) shows that
   with confidence 1-3δ/4, there holds

    𝒬_D,λ^2𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K)
            ≤
             2C̃_1𝒜_D_j,λlog16/δ.

Plugging (<ref>) and (<ref>) into (<ref>), for fixed j∈{1,…,m},
we see with confidence 1-δ, there holds

    𝒬_D,λ^2 (ℛ_D_j,λ+ℛ_D,λ) 𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K)
            ≤C̃_̃3̃log^216/δ𝒜_D_j,λℬ_D_j,λ.

Thus, for δ≥ 16exp{-1/(2C_1^*ℬ_D_j,λ)}, the above estimate  implies that   with
confidence at least 1-mδ, there holds

    max_1≤ j≤ m𝒬_D,λ^2 (ℛ_D_j,λ+ℛ_D,λ) 𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K)
            ≤C̃_̃3̃log^216/δ𝒜_D_j,λℬ_D_j,λ.

Scaling mδ to δ, for δ≥
16mexp{-1/(2C_1^*ℬ_D_j,λ)}, with confidence
1-δ, there holds

    f_D,λ^0-f_D,λ_ρ≤
        4C_1^*C̃_1log^216m/δ∑_j=1^m|D_j|/|D|𝒜_D_j,λℬ_D_j,λ.

Note that

    log16m/δ=log4/δ+log(4m)≤
       (log(4m)+1)log4/δ≤2log(4m)log4/δ,

which follows from (<ref>).  Then
  the proof of Theorem <ref> is complete.



Proof of Theorem <ref>.
Due to the triangle inequality, we have

    f_D,λ^0-f_ρ_ρ≤f_D,λ-f_D,λ^0_ρ+f_D,λ-f_ρ_ρ.

To bound f_D,λ-f_ρ_ρ, under
(<ref>) with 1/2≤ r≤ 1, we obtain
from (<ref>) and (<ref>) that

    f_D,λ-f_ρ_ρ≤λ^r+𝒬_D,λ^2(𝒫_D,λ+𝒮_D,λf_λ_K).

Then, (<ref>) with
C_3:=max{4C_1^*(4log2+1),16log^22} and (<ref>) with C_4:=4C_1^* imply δ≥exp{2C_1^*ℬ_D,λ}, and then (<ref>)
with D_j  replaced by D shows that with confidence
1-δ/2, we know that there holds

    f_D,λ-f_ρ_ρ≤λ^r+C̃_1𝒜_D,λlog16/δ.

Noting (<ref>) and
(<ref>) imply (<ref>) and (<ref>), and plugging
(<ref>) and (<ref>) into
(<ref>), with confidence 1-δ, there holds

    f_D,λ^0-f_ρ_ρ≤λ^r+C̃_1𝒜_D,λlog16/δ
            + C̃_̃3̃log^2(4m)log^28/δ∑_j=1^m|D_j|/|D|𝒜_D_j,λℬ_D_j,λ.

Since |D_1|=…=|D_m|, λ=|D|^-1/2r+s and
2s/(2r+s)≤ 1, we have from (<ref>) and (<ref>) that

    𝒜_D_j,λℬ_D_j,λ≤(m|D|^-4r+2s-1/4r+2s+√(m)|D|^-r/2r+s) 
       ×   (m|D|^-2r+s-1/2r+slog|D|
        +
        √(m|D|^-2r+s-1/2r+slog|D|)).

This together with (<ref>) shows

    log^2(4m) 𝒜_D_j,λℬ_D_j,λ≤ 4|D|^-r/2r+s.

Inserting the above inequality into (<ref>) and
noting

    𝒜_D,λ≤
        |D|^-4r+2s-1/4r+2s+|D|^-r/2r+s≤ 2|D|^-r/2r+s,

we see with confidence 1-δ, there holds

    f_D,λ^0-f_ρ_ρ≤
       C_5|D|^-r/2r+slog^28/δ,

where we use log16/δ≤log^28/δ and

    C_5=1+2C̃_1+4C̃_3.

This completes the proof of Theorem <ref>. 




To prove Corollary <ref>, we
need the following  Borel-Cantelli Lemma  <cit.>. The Borel-Cantelli Lemma asserts  for a sequence
{η_n}_n of events that if the sum of the probabilities is
finite, i.e., ∑_n=1^∞ P[η_n]<∞, then the probability
that infinitely many of them occur is 0.


Let {η_n} be a sequence of events in some probability space
and {ε_n} be a sequence of positive numbers satisfying
lim_n→∞ε_n=0. If

    ∑_n=1^∞[|η_n-η|>ε_n]<∞,

then η_n converges to η almost surely.


Proof of Corollary <ref>. Let N:=|D|, it is easy to check that
δ=δ_N=C̃_4 N^-2  satisfies (<ref>) for some C̃_4>0 independent of N.
 Set
Ψ_N=N^-r/2r+s. By Theorem <ref>, if λ=|D|^-1/2r+s,
|D_1|=…=|D_m| and
 (<ref>) holds, then
 for any N and ε>0,

    P[Ψ_N^-1+εf^0_D,λ-f_ρ_ρ
          >
          C_5Ψ_N^ε(log8/δ_N)^2]
          ≤δ_N.

 Denote
μ_N=C_5Ψ_N^ε(log8/δ_N)^2.
Obviously,

    ∑_N=2^∞ P[Ψ_N^-1+εf_t,D-f_ρ_ρ>μ_N]
               ≤∑_N=2^∞δ_N<∞

and μ_N→0 when N→0. Then our conclusion
follows from Lemma <ref>. This completes the
proof of Corollary <ref>.
  




 §.§ Optimal learning rates for DKRR(ℓ)


In this subsection, we present the proof of Theorem
<ref>. To this end, we  prove the following
theorem.


  Under Assumption <ref>   and  Assumption <ref> with
1/2≤ r≤ 1, if 0<λ≤1, 𝒩(λ)≥
1, and (<ref>) holds,
  then for δ satisfying (<ref>),
 with confidence 1-δ
  there holds

    f_D,λ^ℓ-
        f_D,λ_ρ≤
        2C̃_3 (4C_1^*)^ℓ(log(4m)log4/δ)^ℓ+2(∑_j=1^m
         |D_j|/|D|ℬ_D_j,λ)^ℓ∑_j=1^m
         |D_j|/|D|𝒜_D_j,λℬ_D_j,λ.




Proof. Under (<ref>) and
(<ref>), we obtain from Lemma
<ref>, (<ref>) and (<ref>) that
with confidence 1-mδ, there holds

    max_1≤ j≤ m𝒬_D_j,λ^2
        (ℛ_D_j,λ+ℛ_D,λ)
        ≤
        4C_1^*ℬ_D_j,λlog16/δ,

and

    max_1≤ j≤ m𝒬_D,λ^2(ℛ_D,λ+ℛ_D_j,λ) 𝒬_D_j,λ^2(𝒫_D_j,λ+𝒮_D_j,λf_λ_K)
             ≤C̃_̃3̃log^216/δ𝒜_D_j,λℬ_D_j,λ.

Scaling mδ to  δ, we obtain from (<ref>) that

    f_D,λ^ℓ-
        f_D,λ_ρ≤(L_K+λ I)^1/2 (f_D,λ^ℓ-
        f_D,λ)_K
       ≤   (4C_1^*log16m/δ)^ℓ(∑_j=1^m
         |D_j|/|D|ℬ_D_j,λ)^ℓC̃_̃3̃log^216m/δ∑_j=1^m
         |D_j|/|D|𝒜_D_j,λℬ_D_j,λ.

 Noting further log16/δ≤ 2log 4m,  we have with
 confidence 1-δ,

    f_D,λ^ℓ-
        f_D,λ_ρ≤
        2C̃_3 (4C_1^*)^ℓlog^ℓ+2(4m)log^ℓ+24/δ(∑_j=1^m
         |D_j|/|D|ℬ_D_j,λ)^ℓ∑_j=1^m
         |D_j|/|D|𝒜_D_j,λℬ_D_j,λ.

This completes the proof of Theorem <ref>. 


Proof of Theorem <ref>.    Since
|D_1|=…=|D_m| and λ=|D|^-1/2r+s, it  follows
from (<ref>) and 2s/(2r+s)≤ 1 that

    (∑_j=1^m|D_j|/|D|ℬ_D_j,λ)^ℓ≤(m|D|^-2r+s-1/2r+slog|D|)
        +
        √(mlog|D|)|D|^-2r+s-1/4r+2s)^ℓ.

This together with (<ref>) shows that with confidence
1-δ, there holds

    (∑_j=1^m|D_j|/|D|ℬ_D_j,λ)^ℓ∑_j=1^m|D_j|/|D|ℬ_D_j,λ𝒜_D_j,λ
       ≤   (m|D|^-2r+s-1/2r+slog|D|
        +
        √(mlog|D|)|D|^-2r+s-1/4r+2s)^ℓ+1(m|D|^-4r+2s-1/4r+2s+√(m)|D|^-r/2r+s).

Since (<ref>) with C_6:=(4C_1^*(2+4log
2))^2 and (<ref>) with C_7=C_6/4, we
obtain (<ref>) and (<ref>). Then, it follows from
 Theorem
<ref> that with confidence 1-δ, there
holds

    f_D,λ^ℓ-
        f_D,λ_ρ≤  2C̃_3
         |D|^-r/2r+slog^ℓ+24/δ.

Hence, we obtain from (<ref>) and (<ref>) that with confidence 1-δ, there holds

    f_D,λ^ℓ-
        f_ρ_ρ≤f_D,λ^ℓ-
        f_D,λ_ρ+f_D,λ-f_ρ_ρ
       ≤   
         C_8|D|^-r/2r+slog^ℓ+24/δ,

where C_8=1+C̃_1+2C̃_3, which completes the proof of
Theorem <ref>. 

Proof of Corollary <ref>. The proof of   Corollary <ref> is the same as that of  Corollary <ref> with (<ref>)  replaced by (<ref>).  




§ EXPERIMENTS

In this section, we report numerical results to verify our theoretical statements. We employ  three criteria for
comparisons. The first criterion is the global mean squared error (GMSE) which is the mean square error (MSE)
of a testing set with training all samples in a batch mode. GMSE provides a baseline to assess the  performances of DKRR and DKRR(ℓ).
The second criterion is the average error (AE) which is the MSE of DKRR. The third criterion is the average
error with communications (AEC), which is the MSE of  DKRR (ℓ). Regularization parameters in all experiments are selected by grid search.

We carry out three simulations to verify our theoretical statements. The first simulation is devoted to
illustrating the power of communications in DKRR. The second simulation is performed to
demonstrate the relation between the generalization ability of DKRR(ℓ) and the number of training samples for
fixed numbers of local machines and communications.
The third simulation focuses on  comparisons on the training complexities of DKRR and DKRR(ℓ).

Before carrying out simulations, we describe how the synthetic data is generated.
The inputs {x_i}_i=1^N of training samples are independently
drawn according to the uniform distribution on the (hyper-)cube [0,1]^d with d=1 or d=3. The corresponding outputs
{y_i}_i=1^N are generated from the regression models y_i=g_j(x_i)+ε_i for i=1,2,⋯,N and j=1,2, where
ε_i is the independent Gaussian noise 𝒩(0,0.2),

    g_1(x)={[            x    0<x≤ 0.5,;          1-x 0.5 < 0 ≤ 1, ].

for 1-dimensional data, and

    g_2(x)={[ (1-x_2)^6(35x_2^2+18x_2+3)                  0<x_2≤ 1,;                          0                    x_2> 1, ].

for 3-dimensional data. The inputs {x_i'}_i=1^N' of testing samples are also drawn independently according to
the uniform distribution on the (hyper-)cube [0,1]^d but the corresponding outputs {y_i'}_i=1^N' are generated  by
y_i'=g_j(x_i'). It can be found in <cit.> that g_1∈ W_1^1 and g_2∈ W_3^4, where W_d^α represents
the α-order Sobolev space on [0,1]^d. If we define K_1(x,x')=1+min(x,x') and K_2(x,x')=h(x-x'_2)
with

    h(r)={[ (1-r)^4(4r+1)      0<r ≤ 1,;             0         r> 1, ].

then we know <cit.> that K_1 and K_2 are reproducing kernels for W_1^1 and W_3^2, respectively. Obviously,
g_1∈ℋ_K_1 and g_2∈ℋ_K_2. In the training process of DKRR and DKRR(ℓ), we uniformly distribute N training samples
to m local machines.







Simulation 1: We generate 10000 samples for training and 1000 samples for testing. The number m of local machines
varies from  {20,40,60,⋯,480} for 1-dimensional data, and varies from {2,4,6,⋯,60} for 3-dimensional
data. The testing results are shown in Figure <ref> and Figure <ref>.
Figure <ref> shows the relation between MSE and the number of local machines by different numbers of communications.
From Figure <ref>, we can conclude the following four assertions: 1) When m is not too large, AEs are always comparable to GMSEs.
There exists an upper bound of m, denoted by m_ (e.g., m_≈ 40 for d=1 and m_≈ 6 for d=3), larger than which AE curves
increase dramatically and far from the GMSE curves. This verifies the theoretical statement in Theorem <ref>. 2) AECs also have the upper bound, such as m_≈ 200 for d=1 and ℓ=2,
which is much larger than that of AEs. This result confirms  Theorem <ref> by showing the power of communications in the sense that communications in DKRR can help to relax
the restriction on m.
3) The upper bound m_ of AECs increases with the number of communication increasing, which implies the necessity of communications and verifies Theorem <ref> by showing that  the upper bound in (<ref>) is monotonically increasing with respect to the number of communications.
4) Different from DKRR which cannot sufficiently embody the best approximation ability of local estimator, DKRR(ℓ) succeeds in presenting an upper bound of m which is  close to  m_1 in Figure <ref>.







The relation between MSE and the number of communications by different  numbers of local machines is illustrated in Figure <ref>.
We can see that there exists an upper bound of m (e.g., about 280 for 1-dimensional data and 30 for 3-dimensional data), less than which AECs are
guaranteed to converge to GMSEs with a fast rate, and larger than which AECs diverge dramatically.
This verifies Proposition <ref> by comparing
∑_j=1^m|D_j|/|D|𝒬_D_j,λ^2 (ℛ_D_j,λ+ℛ_D,λ) with 1.

Simulation 2: This simulation investigates the generalization performance of DKRR and DKRR(ℓ) with
varying the number of training samples N∈{3000,3500,4000, ⋯,20000}
and fixing the number of testing samples N'=1000. The regression results are shown
in Figure <ref> and Figure <ref>, from which it can be drawn the following conclusions:
1) For a fixed number of local machines and a fixed number  of communications, AE curves are getting closer and closer
to GMSE curves, and AEC curves are converging to GMSE curves with the number of training samples increasing.
This verifies our theoretical assertions of Theorem <ref> and Theorem <ref>.
2) For each fixed number of local machines, there exists a lower bound for the number of training
samples, denoted by N_ (e.g., N_≈ 6000 for d=1 and m=180, and N_≈ 13500 for
d=3 and m=40), larger than which, the generalization
performance of DKRR(ℓ) is significantly superior than that of DKRR, and AECs converge to
GMSEs with the number of communications increasing. Obviously, the bound N_ increases
as the number of local machines increases. This also confirms the conclusion
in Theorem <ref>.




Simulation 3: In this simulation, we compare the training complexities of DKRR and DKRR(ℓ).
The computational complexity analysis for the training flow in Appendix B is given in Table <ref>, in which the computational
complexity of Step 1, Step 4 and Step 6 refers to the complexity of each local machine, provided that parallelization is
implemented. It should be noted that the time of data transmission in DKRR(ℓ) is not considered, and the computational complexity
of Step 1 is also that of DKRR. Thus, the training complexity of DKRR and DKRR(ℓ) are O(N^2τ/m+N^3/m^3)
and O(N^2τ/m+N^3/m^3+N^2ℓ/m+mNℓ), respectively. We define

    Ω_ = N^2τ/m+N^3/m^3,  Ω_(ℓ) = N^2τ/m+N^3/m^3+N^2ℓ/m+mNℓ .

It can be seen that Ω_ monotonously decreases with m increasing; Ω_(ℓ)
first decreases and then increases with m increasing, and the number m with minimum of Ω_(ℓ)
is given by

    m^⋆ = √(√((τ+ℓ)^2+12ℓ)+(τ+ℓ)/2ℓ)√(N) .

Once data and the kernel function are given, the complexity τ of calculating a kernel value can be considered as a constant.
Provided ℓ is large enough, we have m^⋆≈√(N), from which a rough conclusion can be drawn as follows: the training complexity of DKRR(ℓ) mainly focuses on the local process (i.e., Step 1 of the training flow in Appendix B) when m<√(N), while it mainly focuses on the communications (i.e., from Step 4 to Step 7 of the training flow in Appendix B)
when m>√(N). In the following, some numerical results are reported to verify the above analysis of training complexity.




 We start by introducing some notations that are used below.
_N,m represents the MSE of DKRR with m local machines for N training samples.

_N,m,ℓ represents the MSE of DKRR(ℓ) with m local machines and ℓ communications for N training samples.
_N represents the MSE of the model with training N samples in a batch mode. The relative errors for DKRR and DKRR(ℓ)
are defined by
_N,m=|_N,m-_N|/_N
and
_N,m,ℓ=|_N,m,ℓ-_N|/_N, respectively. In DKRR with N training samples, we denote the maximum number m of local machines that satisfies _N,m<ε as m̅_^N, i.e.,
m̅_^N = max{m| _N,m<ε}.
In DKRR(ℓ) with N training samples and ℓ communications, we denote the maximum number m of
local machines that satisfies _N,m,ℓ<ε as m̂_^N,ℓ, i.e.,
m̂_^N,ℓ = max{m| _N,m,ℓ<ε}.
In the experiments, ε is set as 0.05. The computing capability of each local machine is assumed to be the same
for simplicity.

 We first generate 20000 training samples and 1000 testing samples. The number m varies from {20,40,60,⋯,600} for the 1-dimensional data, and varies from {2,4,6,⋯,60} for the 3-dimensional data. The training time of DKRR with the number m changing from the minimum number (20 for 1-dimensional data and 2 for 3-dimensional data) to m̅_^N
and the training time of DKRR(ℓ) with the number m changing from the minimum number to m̂_^N,ℓ by different numbers
ℓ∈{4,8,12,16,20} are shown in Figure <ref>.
The following observations can be made from these results. 1) Because there are
no calculations for communication steps, DKRR naturally consumes the least time when m<m̅_^N. 2) For the two simulation datasets, we have m̅_^N ≪m̂_^N,ℓ, resulting that DKRR(ℓ) can further reduce the least training time of DKRR with the maximum number m̅_^N as the number m approaches to m̂_^N,ℓ. However, the improvement is very limited for the 1-dimensional data, because the number m̅_^N of DKRR is sufficiently large (m̅_^N = 120), and thus the marginal utility for the reduction of training time is very small when DKRR(ℓ) further enlarges the maximum number of local machines. 3) With the number m increasing, the training time curves of DKRR(ℓ) (ℓ=4,8,16,32) first decrease quickly and then increase slowly for the 1-dimensional data, and monotonously decrease for the 3-dimensional data. This phenomenon coincides with the
aforementioned theoretical analysis of training complexity, because m̂_^N,ℓ≈ 450 > √(N) for the 1-dimensional
data, and m̂_^N,ℓ≈ 50 < √(N) for the 3-dimensional data. In practical applications, we estimate the optimal number of local machines by the formula

    m̂^⋆_N,ℓ = {[         m^⋆, m̂_^N,ℓ>m^⋆,;     m̂_^N,ℓ,              ].

to expect it to have the lowest time consumption. The estimated m^⋆ and the corresponding training time for DKRR(ℓ) with ℓ=2,4,8,16,32 on the 1-dimensional data are marked by red pentagrams in the left figure of Figure <ref>. It can be seen that the training time with the estimated number m^⋆ is very close to the minimum of training time, which validates the correctness and reliability of equation (<ref>).







 We also record the results with varying the number of training samples N∈{3000,3500, 4000,⋯,20000} and fixing the
number of testing samples N'=1000. Figure <ref> shows the maximum numbers m̅_^N of DKRR and
the maximum numbers m̂_^N,ℓ of DKRR(ℓ) with varying the numbers of training samples and communications, and Figure <ref>
shows the training time of DKRR with m̅_^N local machines and the training time of DKRR(ℓ) with m̂^⋆_N,ℓ local machines.
From these results, we have the following observations. 1) The maximum number of local machines increases as the number of training samples increases
for both DKRR and DKRR(ℓ), but the growth of DKRR(ℓ) is faster than that of DKRR.
2) The maximum number m̂_^N,ℓ of DKRR(ℓ) is robust to the number ℓ of communications when ℓ>4. This verifies the fast convergence as shown in Figure <ref>, and also implies that DKRR(ℓ) can achieve a satisfactory generalization
performance in a small number of communications. 3) For the 1-dimensional data, DKRR(ℓ) does not have much advantage in the training time, and is even worse than DKRR when the number of training samples N≥ 10000 and the number of communications ℓ≥4. Furthermore, the training time increases significantly as the number of communications increases. The main reason has two folds. On one hand, the marginal utility of enlarging the number of local machines diminishes when m̅_^N of DKRR is large enough to efficiently deal with large-scale data. On the other hand, the training complexity of DKRR(ℓ) mainly focuses on the communications when the number m is sufficiently large.
4) For the 3-dimensional data, the number m̅_^N of DKRR is relatively small (e.g., m̅_^N=12 for N=20000 training samples). DKRR(ℓ) shows the significantly superior performance on training time when compared to DKRR, even for the large number ℓ=32. This is the main focus of this paper, on an enlargement of the maximum number of local machines guaranteeing optimal learning rates when DKRR has a small number m̅_^N of local machines.

All these simulations verify our theoretical statements  and show the power
of  communications in distributed  learning.



§ APPENDIX A: PROOFS OF LEMMAS IN SECTION <REF>


We use a new concentration inequality for positive operators
<cit.>, which was a refined estimate for the well known
Bernstein inequality for matrix <cit.>. This lemma has
been adopted in <cit.> and <cit.> to derive
optimal learning rates for kernel-based spectral algorithms and
coefficient-regularization algorithms.


Let R>0 be a positive real constant and consider a finite sequence
of self-adjoint Hilbert-Schmidt operators {ξ_i}_i=1^n
satisfying E[ξ_i]=0 and ξ_i≤ R almost surely. Suppose
there are constants V,W>0 such that
E[(∑_i=1^nξ_i)^2]≤ V and
(E[(∑_i=1^nξ_i)^2])≤ VW. For all t≥ V^1/2
+R/3,

    P(∑_i=1^nξ_i≥ t)≤
          4Wexp(-t^2/2(V+Rt/3)).





Proof of Lemma <ref>. Define the
random variable

    η(x)=(L_K+λ I)^-1/2K_x⊗ K_x(L_K+λ
           I)^-1/2,      x∈𝒳.

It is easy to see that η(x) is a self-adjoint operator for
 x∈𝒳. Furthermore,

    E[η]=(L_K+λ I)^-1/2L_K(L_K+λ I)^-1/2,

and

    1/|D|∑_(x,y)∈ Dη(x)=(L_K+λ I)^-1/2L_K,D(L_K+λ
         I)^-1/2.

Set

    ξ(x)=η(x)- E[η],     x∈𝒳.

Then, we have E[ξ]=0.  If
{σ_ℓ,ψ_ℓ}_ℓ≥1 are  normalized
eigenparis of the integral operator L_K on L_ρ_X^2, then
√(σ_ℓ)ψ_ℓ_K=1 when σ_ℓ>0. Thus,
{√(σ_ℓ)ψ_ℓ:σ_ℓ>0} forms an orthonormal
basis of ℋ_K. This implies that

    η(x)^2
            =   sup_f_K=1η(x)f_K^2
         ≤∑_ℓ(L_K+λ I)^-1/2K_x⊗ K_x(L_K+λ
           I)^-1/2√(σ_ℓ)ψ_ℓ_K^2
       =   ∑_ℓσ_ℓψ_ℓ^2(x)/λ+σ_ℓ(L_K+λ
           I)^-1/2K_x_K^2=[∑_ℓσ_ℓψ_ℓ^2(x)
           /λ+σ_ℓ]^2.

Then,

    ξ(x)= η(x)- E[η]≤max_x∈𝒳η(x)+1≤max_x∈𝒳∑_ℓσ_ℓψ_ℓ^2(x)
           /λ+σ_ℓ+1≤  (κ^2+1)λ^-1,

where we use
E[η]=(L_K+λ I)^-1L_K≤ 1 and 0<λ≤ 1.
 For an arbitrary f∈ℋ_K, it follows from [η(x)]^2f=η(x)[η(x)f] that

    [η(x)]^2=⟨ K_x,(L_K+λ I)^-1K_x⟩_Kη(x)
        =∑_ℓσ_ℓψ_ℓ^2(x)/λ+σ_ℓη(x).

Then, we get from
ξ(x)=η(x)- E[η]
that

    E[(∑_(x,y)∈
       Dξ(x))^2]≤
       |D|(E[(η)^2]+(E[η])^2)    
       ≤   
       |D|(κ^2λ^-1E[η]+E[η]^2)
       ≤
        |D|λ^-1(κ^2+1).

Moreover,

    (E[(∑_(x,y)∈
       Dξ(x))^2])≤
       |D|Tr(E[(η)^2]-(E[η])^2  )   
       ≤   
       |D|(κ^2λ^-1(E[η])+(E[η])^2)
       ≤
        |D|λ^-1𝒩(λ)(κ^2+1).

Plugging R=λ^-1(κ^2+1),
V=|D|λ^-1(κ^2+1) and W=𝒩(λ), we have
that for all t≥√((κ^2+1))/√(λ|D|)+κ^2+1/3λ|D|,
there holds

    P[ℛ_D,λ≥ t]
         =
         P[∑_(x,y)∈ Dξ(x)≥ |D|t]
         ≤ 4𝒩(λ)exp(-λ|D|t^2/2(κ^2+1)+(κ^2+1)t/3).

 Set
4𝒩(λ)exp{-λ|D|ε^2/(κ^2+1)(2+ε/3)}=δ.
 With confidence 1-δ,

    ε≤(κ^2+1)log4𝒩(λ)/δ/3λ|D|+ √(2(κ^2+1)log4𝒩(λ)/δ/λ|D|).

Setting

    t=(κ^2+1) log4𝒩(λ)/δ/3λ|D|+ √(2(κ^2+1)log4𝒩(λ)/δ/λ|D|)≥√((κ^2+1))/√(λ|D|)+κ^2+1/3λ|D|,

 we then get that    (<ref>) holds with confidence 1-δ. This
completes the proof of Lemma <ref>. 

We then prove Lemma <ref> by using Lemma
<ref>.

Proof of Lemma <ref>.  Since
δ≥ 4exp{2C_1^*ℬ_D,λ}, it follows from
Lemma <ref> that ℛ_D,λ<1/2 holds with confidence 1-δ. Then,

    (L_K+λ I)^1/2(L_K,D+λ
             I)^-1(L_K+λ I)^1/2
       =   
             (L_K+λ I)^1/2[(L_K,D+λ
             I)^-1-(L_K+λ
             I)^-1]   (L_K+λ I)^1/2+I
              = I
       +   
             (L_K+λ I)^-1/2(L_K-L_K,D)(L_K+λ I)^-1/2(L_K+λ I)^1/2(L_K,D+λ
             I)^-1(L_K+λ I)^1/2.

Thus,

    (L_K+λ I)^1/2(L_K,D+λ
             I)^-1(L_K+λ I)^1/2
       ≤   
             1+ 1/2(L_K+λ I)^1/2(L_K,D+λ
             I)^-1(L_K+λ I)^1/2.

This implies

    (L_K+λ I)^1/2(L_K,D+λ
             I)^-1(L_K+λ I)^1/2≤ 2.

Since t^1/2 is operator monotone <cit.>, we
have

    𝒬_D,λ≤[(L_K+λ I)^1/2(L_K,D+λ
             I)^-1(L_K+λ I)^1/2]^1/2≤√(2).

  This completes the proof of Lemma
<ref>. 








§ APPENDIX B:   TRAINING AND TESTING FLOWS FOR DKRR(ℓ) 


Generally speaking, it is difficult to communicate functions in practice. Thus, the implementation of DKRR(ℓ) requires communications of additional information. In this part, we numerically realize  DKRR(ℓ) by communicating the inputs of data for the sake of simplicity,  though there are numerous state-of-the-art approaches to approximate the gradient matrix via much less of communication loss.


Training Flow:



Step 1 (local process). Run KRR (<ref>) on the j-th local
machine with data D_j and communicate D_j(x)={x:(x,y)∈ D} to the
k-th local machine for k=1,…,m. Store m matrices of size
|D_j|×|D_k|, 𝕂_D_k,D_j:={K(x,x')}_x∈
D_k(x),x'∈ D_j(x) with k=1,…,m, the matrix
M_D_j,λ=(𝕂_D_j,D_j+λ |D_j| 𝕀_D_j)^-1, and the
 vector
α⃗__D_j=M_D_j,λy_D_j, where 𝕀
is the unit matrix of size |D_j|×|D_j|.



Step 2 (synthesization) On the j-th local machine, communicate m
vectors of size |D_k|, K_D_k,D_jα⃗__D_j for
k=1,…,m to the global machine. Synthesize m   global
    vectors
f⃗_D,λ,D_k^0=∑_j=1^m|D_j|/|D|𝕂_D_k,D_jα⃗__D_j for k=1,…,m.



Step 3 (distributing) For  ℓ=1,2,…, distribute
f⃗_D,λ,D_j^ℓ-1 to the j-th local machine.




Step 4 (local gradients) On the j-th local machine, compute m
gradient vectors G⃗_D_j,λ,k,ℓ=𝕂_D_k,D_j/|D_j|(f_D,λ,D_j^ℓ-1-y_D_j)+λf⃗_D,λ,D_k^ℓ-1
for k=1,…,m and communicate these m vectors to the global
machine.



Step 5 (synthesizing gradients)  Synthesize m global gradient
vectors,G⃗_D,λ,k,ℓ:=∑_j=1^m|D_j|/|D| G⃗_D_j,λ,k,ℓ
for k=1,…,m. Distribute m vectors
G⃗_D,λ,k,ℓ with k=1,…,m to each local
machine.



Step 6 (KRR on gradient data) On the j-th local machine,  compute
the vector
β⃗_j,ℓ=M_D_j,λG⃗_D,λ,j,ℓ and
 m vectors H⃗_D_j,λ,k,ℓ:=
G⃗_D,λ,k,ℓ
   -𝕂_D_k,D_jβ⃗_j,ℓ for k=1,…,m.
   Communicate m vectors   H⃗_D_j,λ,k,ℓ  with k=1,…,m to the
global machine.


Step 7 (final estimator)  Generate m vectors

    f⃗_D,λ,D_k^ℓ=f⃗_D,λ,D_k^ℓ-1
       -1/λ∑_j=1^m|D_j|/|D|H⃗_D_j,λ,k,ℓ,    
       k=1,…,m

and transmit f⃗_D,λ,D_j^ℓ to the j-th local
machine with j=1,…,m.

The above 7 steps provide a realization for DKRR(ℓ). However, it is difficult to get all  input  data in a local machine, due to the loss of communications.  In particular, input data of some local machines are unaccessible due to the data privacy. Under this circumstance, these local machines are only used to build f_D,λ^0 and are excluded in building f_D,λ^ℓ for ℓ≥ 1. This provides a numerical realization for the algorithm in Simulation 3 in Section <ref>.

Testing Flow: given vector D'(x):=(x_1',…,x_|D'|) which
consists  of |D'| query points.


Step 1 (local estimates) Transmit D'(x) to m local machines. On
the j-th local machine, store vectors of size |D'|,
K⃗_D',D_jα⃗__D_j.

Step 2 (global estimates) Compute test vector of size |D'|,

    f_D,λ^0(D'):=∑_j=1^m|D_j|/|D|K⃗_D',D_jα⃗__D_j .


Step 3 (local gradients) For ℓ=1,2,…, distribute
f_D,λ^ℓ-1(D') to m local machines, and
compute

    G_D_j,λ,ℓ(D'):=K⃗_D',D_j/|D_j|(f⃗_D,λ,D_j^ℓ-1-y_D_j)
          +λf_D,λ^ℓ-1(D'),

where f⃗_D,λ,D_j^ℓ-1 is obtained from the
training flow.

Step 4 (global gradients) Transmit G_D_j,λ,ℓ(D') with
j=1,…,m to the global machine and get the global gradient
vector

    G_D,λ,ℓ(D')=∑_j=1^m|D_j|/|D|G_D_j,λ,ℓ(D').


Step 5 (final estimator) Generate the vector of estimators

    f_D,λ^ℓ(D')
        =
         f_D,λ^ℓ-1(D')-1/λ∑_j=1^m|D_j|/|D|[G_D,λ,ℓ(D')-K⃗_D',D_jβ⃗_j,ℓ].


























































































































§ ACKNOWLEDGEMENT

The work of Shao-Bo Lin is supported
partially by the National Natural Science Foundation of China (Nos. 61876133, 11771021).
The work of Di Wang is supported partially by the National Natural Science Foundation of China (Grant No. 61772374)
and by Zhejiang Provincial Natural Science Foundation (Grants No. LY17F030004).
The work of Ding-Xuan Zhou is supported partially by the Research Grants Council
of Hong Kong [Project No. CityU 11306617] and by National Natural Science Foundation of China under Grant 11461161006.


31


urlstyle

 
[Bathis(1997)]Bathia1997
R. Bathis.
Matrix Analysis, Volume 169 of Graduate Texts in Mathematics.
Springer, Berlin, 1997.


[Bellet et al.(2015)Bellet, Liang, Garakani, Balcan, and Sha]Bellet2015
A. Bellet, Y. Liang, A. B. Garakani, M. F. Balcan, and F. Sha.
A distributed frank-wolfe algorithm for communication-efficient sparse learning.
In Proceedings of the fifteenth SIAM International Conference on Data Mining, Society for Industrial and
Applied Mathematics, 478-486, 2015.

 
[Blanchard and Krämer(2016)]Blanchard2016
G. Blanchard and N. Krämer.
Convergence rates of kernel conjugate gradient for random design regression.
Anal. Appl., 14:0 763-794, 2016.



 
[Caponnetto and DeVito(2007)]Caponnetto2007
A. Caponnetto and E. DeVito.
Optimal rates for the regularized least squares algorithm.
Found. Comput. Math., 7:0 331-368, 2007.


[Chang et al.(2017)Chang, Lin, and Zhou]Chang2017
X. Chang, S. B. Lin,  and D. X. Zhou.
Distributed semi-supervised learning with kernel ridge regression.
J. Mach. Learn. Res., 180 (46):0 1-22, 2017.

[Chang et al.(2017)Chang, Lin, and Wang]Chang2017a
X. Chang, S. B. Lin, and Y. Wang.
Divide and conquer local average regression.
Electronic J. Stat., 11:0 1326-1350, 2017.


[Cucker and Zhou(2007)]Cucker2007
F. Cucker and D. X. Zhou.
Learning Theory: An Approximation Theory Viewpoint.
Cambridge University Press, Cambridge, 2007.

[Guo et al.(2017)Guo, Lin, and Zhou]Guo2017
Z. C. Guo, S. B. Lin, and D. X. Zhou.
Learning theory of distributed spectral algorithms.
Inverse Problems, 33:0 074009, 2017.


[Guo and Shi(2019)]Guo2018
Z. C. Guo and L. Shi.
Optimal rates for coefficient-based regularized regression.
Appl. Comput. Harmonic Anal.,  47: 662-701, 2019.

[Guo et al.(2019)Guo, Lin, and Shi]Guo2019a
Z. C. Guo, S. B. Lin, and L. Shi.
Distributed learning with multi-penalty regularization.
Appl. Comput. Harmonic Anal., 46:0 478-499, 2019.


[Dicker et al.(2017)Dicker, Foster, and Hsu]Dicker2017
L. H. Dicker, D. P. Foster, and D. Hsu.
Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators.
Electron. J. Stat., 11:0 1022-1047, 2017.


[Dudley(2002)]Dudley2002
R. M. Dudley.
Real Analysis and Probability, Cambridge Studies in Advanced Mathematics 74.
Cambridge University Press, Cambridge, 2002.

[Györfy et al.(2002)Györfy, Kohler, Krzyzak, and Walk]Gyorfi2002
L. Györfy, M. Kohler, A. Krzyzak, and H. Walk.
A Distribution-Free Theory of Nonparametric Regression.
Springer-Verlag, Berlin, 2002.


[Hu et al.(2019)Hu, Wu, and Zhou]Hu2019
T. Hu, Q. Wu, and D. X. Zhou.
Distributed kernel gradient descent algorithm for minimum error entropy principle.
Appl. Comput. Harmon. Anal., In Press, 2019.



[Huang and Huo(2017)]Huang2015
C. Huang and X. M. Huo.
A distributed one-step estimator.
arXiv preprint arXiv:1511.01443, 2015.


[Li et al.(2014)Li, Andersen, Smola, and Yu]Li2014
M. Li, D. G. Andersen, A. J. Smola, and K. Yu.
Communication efficient distributed machine learning with the parameter server.
 Advances in Neural Information Processing Systems, 19-27, 2014.


 
[Lin et al.(2018)Lin, Rudi, Rosasco, and Cevher]Linj2018
J. Lin, A. Rudi, L. Rosasco and V. Cevher.
Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces.
Appl. Comput. Harmonic Anal., In Press, 2018.


[Lin et al.(2017)Lin, Guo, and Zhou]Lin2017
S. B. Lin, X. Guo, and D. X. Zhou.
Distributed learning with regularized least squares.
J. Mach. Learn. Res., 180 (92):0  1-31, 2017.


[Lin and Zhou(2018)]Lin2018
S. B. Lin and D. X. Zhou.
Distributed kernel-based gradient descent algorithms.
Constr. Approx., 47:0 249-276, 2018.

[Lin et al.(2019)Lin, Lei, and Zhou]Lin2019
S. B. Lin, Y. Lei, and D. X. Zhou.
Boosted kernel ridge regression: optimal learning rates and early stopping.
J.  Mach. Learn. Res., 20:0  1-36, 2019.




[Liu et al.(2018)Liu, Shang, and Cheng]Liu2018
M. Liu, Z. Shang, and G. Cheng.
How many machines can we use in parallel computing for kernel ridge regression?
arXiv preprint arXiv:1805.09948, 2018.

[Mann et al.(2009)Mann, McDonald, Mohri, Silberman, and Walker]Mann2009
G. Mann, R. McDonald, M. Mohri, N. Silberman, and D. Walker.
Efficient large-scale distributed training of conditional maximum entropy models.
 Advances in Neural Information Processing Systems, 19-27, 2009.


[Minsker(2017)]Minsker2017
S. Minsker.
On some extensions of Bernstein's inequality for self-adjoint operators.
Stat. Prob. Letters, 127:0 111-119, 2017.

 
[Mücke and Blanchard(2018)]Blanchard2018
N. Mücke and G. Blanchard.
Parallelizing spectrally regularized kernel algorithms.
J. Mach. Learn. Res., 19:0 1-29, 2018.


 
[Pang and Sun(2018)]Pang2018
M. Pang and H. Sun.
Distributed regression learning with coefficient regularization.
J. Math. Anal. Appl., 4660 (1):0  676-689, 2018.

[Pinelis(1994)]Pinelis1994
I. Pinelis.
Optimum bounds for the distributions of martingales in Banach spaces.
Ann. Prob., 22:0 1679-1706, 1994.








[Schaback and Wendland(2006)]Schaback2006
R. Schaback and H. Wendland.
Kernel techniques: from machine learning to mesheless methods.
Acta Numerica, 15:0  543-639, 2006.

[Shamir et al.(2014)Shamir, Srebro, and Zhang]Shamir2014
O. Shamir, N. Srebro, and T. Zhang.
Communication-efficient distributed optimization using an approximate newton-type method.
In Proceedings of the 31st International Conference on International Conference on Machine Learning, 32:0 1000-1008, 2014.


[Shang and Cheng(2017)]Shang2017
Z. Shang and G. Cheng.
Computational limits of a distributed algorithm for smoothing spline.
J.  Mach. Learn. Res., 18:0  3809-3845, 2017.

 
[Shi(2019)]Shi2018
L. Shi.
Distributed learning with indefinite kernels.
Anal. Appl., In Press, 2019.


[Smale and Zhou(2007)]Smale2007
S. Smale and D. X. Zhou.
Learning theory estimates via integral operators and their approximations.
Constr. Approx., 26:0  153-172, 2007.


[Steinwart et al.(2009)Steinwart, Hush, and Scovel]SteinwartHS
I. Steinwart, D. Hush, and C. Scovel.
Optimal rates for regularized least squares regression.
In S. Dasgupta and A. Klivan, editors, Annual Conference on Learning Theory, 79-93, 2009.







[Tropp(2015)]Tropp2015
J. A. Tropp.
An introduction to matrix conecentation inequalities.
Foundations and Trends in Machine Learning, 8:0 1-230, 2015.


[Wu(1995)]Wu1995
Z. M. Wu.
Compactly supported positive definite radial functions.
Adv. Comput. Math., 4:0 283-292, 1995.

[Zeng and Ying(2018)]Zeng2018
J. Zeng and W. Ying.
On nonconvex decentralized gradient descent.
IEEE Trans. Signal Process, 66:0  2834-2848, 2018.

[Zhang et al.(2013)Zhang, Duchi, and Wainwright]Zhang2013
Y. C. Zhang, J. Duchi, and M. Wainwright.
Communication-efficient algorithms for statistical optimization.
J. Mach. Learn. Res., 14:0 3321-3363, 2013.


[Zhang et al.(2015)Zhang, Duchi, and Wainwright]Zhang2015
Y. C. Zhang, J. Duchi, and M. Wainwright.
Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates.
J. Mach. Learn. Res., 16:0 3299-3340, 2015.






[Zhou(2018a)]Zhou2018Deep
D. X. Zhou.
Deep distributed convolutional neural networks: Universality.
Anal. Appl., 16:0 895-919, 2018.

[Zhou(2018b)]Zhou2018Uni
D. X. Zhou.
Universality of deep convolutional neural networks.
Appl. Comput. Harmonic Anal., 48:0 787-794, 2020.

[Zhou(2018c)]Zhou2018Dis
D. X. Zhou.
Distributed approximation with deep convolutional neural networks.
preprint, 2018.



