Conceptio › Archive › arXiv CS

arXiv CSopen access

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms†

arXiv:2609.11712v1 [stat.ML] 10 Sep 2026

Jun-Yi Meng1 , Yuan Mao2 and Zheng-Chu Guo1

School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, P. R. China

College of Informatics, Huazhong Agricultural University, Wuhan 430070, P. R. China

Abstract In this paper, we investigate the generalization performance of distributed gradient descent algorithms in a reproducing kernel Hilbert space under a robust loss function lσ . By exploiting the spectral characterization of gradient descent together with the intrinsic properties of robust loss functions, we establish optimal learning rates for the distributed kernel-based robust gradient descent (DKRGD) algorithm with an appropriately chosen scale parameter σ. The proposed parameter choice of σ simultaneously alleviates the saturation phenomenon and guarantees statistical robustness. A key technical contribution is a novel error analysis that provides substantially sharper bounds for products of operators, thereby significantly relaxing existing restrictions on the maximum number of local machines while retaining optimal learning rates. Finally, we develop a communication-eﬀicient strategy that further improves the convergence performance of DKRGD.

Keywords: Learning theory, Distributed learning, Robust regression, Gradient descent, Communication Mathematics Subject Classification (2020): 68T05, 68Q32, 68W15, 62G08, 62G35, 62J02

Introduction With the rapid growth of data across a wide range of applications, performing machine learning tasks on a single

machine is becoming increasingly impractical. Meanwhile, privacy constraints and data isolation often prevent data collected by different organizations from being directly pooled. For example, patient records may be stored separately across hospitals, while financial institutions typically maintain their risk-management data independently. These considerations have motivated significant interest in distributed learning, where statistical models are constructed from data stored across multiple local machines without requiring direct access to the entire data set. Among various distributed learning paradigms, the “divide-and-conquer” approach has attracted particular attention due to its conceptual simplicity and computational eﬀiciency [1, 2]. A substantial body of work has investigated the statistical performance of distributed kernel-based learning algorithms. For distributed regularized least-squares algorithms, optimal learning rates in expectation were established in [1, 2]. Subsequently, [3] and [4] extended the analysis to distributed spectral algorithms and derived optimal learning

rates in expectation. More recently, [5] refined the theoretical analysis of distributed kernel ridge regression (DKRR), establishing optimal learning rates both in expectation and with high probability. † The work described in this paper is supported by the National Natural Science Foundation of China (Grants Nos. 12071356, 12271473, 12526595). Yuan Mao is also supported by the Fundamental Research Funds for the Central Universities [Project No. 2662025XXQD001]. The corresponding author is Yuan Mao. Email addresses: [email protected] (J. Y. Meng), [email protected] (Y. Mao), [email protected] (Z. C. Guo).

Despite these advances, the general frameworks developed in [3, 4] exhibit a saturation phenomenon with respect to the maximal admissible number of local machines. More precisely, once the regularity of the regression function exceeds a certain threshold, further improvements in regularity no longer allow for an increase in the number of local machines while preserving the optimal learning rate. Moreover, the results in [5] are restricted to the regularity range 1 2

≤ r ≤ 1. To alleviate this saturation phenomenon, [6] and [7] exploited the specific spectral structure of gradient

descent algorithms to derive improved bounds on the maximum number of local machines. Another important issue in statistical learning is robustness against outliers and heavy-tailed observations. Leastsquares estimators can be sensitive to atypical observations because large residuals are penalized disproportionately heavily. To improve robustness, [8, 9, 10] considered a family of robust loss functions of the form lσ (u) = G

u2 σ2

where G is a windowing function and σ > 0 is a scale parameter. Appropriate choices of G lead to a broad class of robust loss functions that reduce the influence of large residuals while maintaining desirable statistical properties. These developments naturally raise the question of whether robust kernel-based gradient methods can be effectively combined with distributed learning. In particular, it is important to understand whether a distributed robust gradient descent algorithm can simultaneously retain statistical robustness, achieve optimal learning rates, and accommodate a suﬀiciently large number of local machines. The last issue is especially important because the restriction on the number of machines directly determines the extent to which a distributed method can benefit from increasing computational resources. In this paper, we study the generalization performance of DKRGD in a reproducing kernel Hilbert space (RKHS). Each local machine applies a robust gradient descent algorithm to its own data, and the resulting local estimators are subsequently aggregated to form a global estimator. Our analysis characterizes the statistical performance of the last iterate under standard source and capacity conditions, and reveals the interaction among the regularity of the regression function, the capacity of the hypothesis space, the robust scale parameter σ, and the number of local machines. The main contributions of this paper are summarized as follows. First, we establish a generalization theory for DKRGD both in expectation and with high probability. With appropriate choices of the early-stopping time and the scale parameter σ, the proposed algorithm achieves the optimal learning rates determined by the regularity of the regression function and the capacity of the underlying RKHS. In particular, the scale parameter can be selected so that the optimal learning rates do not deteriorate due to the additional error induced by the robust loss, while the estimator retains the robustness associated with the loss function lσ . Second, we develop a refined error analysis that yields sharper estimates for the operator products arising in the study of distributed gradient descent. The resulting bounds substantially relax the restriction on the maximum number of local machines. In particular, the improved analysis alleviates the saturation phenomenon that arises in existing general analyses of distributed spectral algorithms when the regularity of the regression function becomes suﬀiciently high. Third, we develop a DKRGD algorithm with communication based on a Newton–Raphson-type correction. The proposed communication strategy further enlarges the admissible number of local machines while preserving the optimal learning rate with high probability. Moreover, the maximum number of local machines increases with the number of communication rounds, revealing a favorable trade-off between communication cost and distributed scalability. The remainder of this paper is organized as follows. Section 2 outlines the regression setting and robust loss functions, followed by a detailed description of DKRGD and its communication strategy. Under mild assumptions, Section 3 establishes optimal learning rates for DKRGD both with high probability and in expectation, and optimal learning rates for DKRGD with communication under high probability. Additionally, it discusses the corresponding

restrictions on the number of local machines. Section 4 discusses and compares the theoretical results with related distributed learning methods. Section 5 presents the error decomposition and auxiliary results used in the analysis. Finally, the proofs of the main results are provided in Section 6.

Problem Setting and Distributed Kernel-based Robust Gradient Descent |D|

In this paper, we consider the nonparametric regression problem based on i.i.d. samples D = {xi , yi }i=1 drawn from an unknown distribution ρ on Z := X × Y, where input space X is a separable metric space and Y ⊂ R is the output space. The training data are assumed to be generated according to the model Y = fρ (X) + ϵ, where E[ϵ|X] = 0, X is the explanatory variable and Y denotes the corresponding response variable. The regression function fρ is defined as

Z fρ (x) =

ydρ(y|x), Y

x ∈ X,

where ρ(y|x) denotes the conditional distribution at x induced by ρ. The goal of regression is to recover fρ from the observed random samples. Our objective is to investigate the generalization performance of robust gradient descent algorithms in a distributed learning setting. To this end, we adopt the class of robust loss functions introduced in [8], defined by lσ (u) = G(

u2 ), σ2

where G : R+ → R is a windowing function and σ > 0 is a scale parameter controlling the degree of robustness. Hereafter, the windowing function G is assumed to satisfy the following two conditions, which are G′+ (0) > 0, CG := sup |G′ (s)|

with G′ (s) > 0 for s > 0,

(1)

s∈(0,∞)

and there exists some p ≥ 0 and cp > 0 such that G′ (s) − G′+ (0) ≤ cp |s|p ,

∀s > 0.

(2)

By choosing different windowing functions G, the general form lσ (u) = G(u2 /σ 2 ) encompasses a variety of commonly used robust loss functions. Several representative examples for regression are presented below, where IA denotes the indicator function of a set A. Example 1. Huber’s loss combines the advantages of mean squared error and mean absolute error [11]. It takes a quadratic form for small errors and a linear form for larger errors. The balance between two terms is controlled by a threshold parameter σ, providing robustness to outliers while maintaining precision. √ u2 |u| 1 s 1 1 lσ (u) = I{|u|≤σ} 2 + I{|u|>σ} − , G(s) = I{s≤1} + I{s>1} s− , p = 0, cp = . 2σ σ 2 2 2 2 Example 2. Fair loss focuses on balancing treatment for larger errors through a piecewise linear modeling approach. It imposes a smaller penalty on larger errors compared to mean squared error, making it suitable for scenarios where equal treatment of errors across different ranges is desired. √ √ |u| |u| 1 1 , G(s) = s − log(1 + s), p = , cp = . lσ (u) = − log 1 + σ σ 2 2 Both loss functions above are convex, and their curves for different values of σ are shown in Figure 1. 3

(a)

(b)

Figure. 1: Two convex types of lσ with different σ. (a) Huber Loss, (b) Fair Loss. Note that the loss function is not necessarily convex; two illustrative nonconvex losses are given below, and their plots for different values of σ are shown in Figure 2. Example 3. Cauchy loss, motivated by the Cauchy distribution, is designed to aggressively suppress extreme errors. Compared to Huber’s loss, Cauchy loss has a slower decay in the tails, leading to a stronger suppression of outliers. u2 s 1 lσ (u) = log 1 + 2 , G(s) = log 1 + , p = 1, cp = . 2σ 2 4 Example 4. Welsch loss can be induced by the well-known correntropy loss, which resembles mean squared error for small errors and adopts a square root form for larger errors [12]. The roots of the second derivative of Welsch loss are located at u = ±σ, indicating that the loss function is concave for |u| > σ and convex for |u| < σ. Therefore, adjusting scaling parameter σ allows rejecting outliers while keeping a similar prediction accuracy as that of least squares loss. s u2 1 lσ (u) = 1 − exp − 2 , G(s) = 1 − exp − , p = 1, cp = . 2σ 2 4

(a)

(b)

Figure. 2: Two nonconvex types of lσ with different σ. (a) Cauchy Loss, (b) Welsch Loss.

2.1

Distributed Kernel-based Robust Gradient Descent In this subsection, we introduce the DKRGD algorithm. We begin with some notation that will be used throughout

the subsequent analysis. Denote by K : X × X → R a Mercer kernel and (HK , ∥·∥K ) the corresponding RKHS. Given i.i.d samples D = |D|

{(xi , yi )}i=1 drawn from ρ, the empirical risk is defined by a robust loss function lσ as E lσ =

1 |D|

lσ (f (xi ) − yi ) ,

(3)

(xi ,yi )∈D

where |D| is the cardinality of D. Then a robust estimator can be obtained by minimizing the empirical risk Elσ over HK . Let Kx : X → R be the function defined by Kx (·) = K(x, ·) for x ∈ X . By the reproducing property of kernel K and proposition 2.1 in [13], we can compute the gradient of (3) and further define the kernel-based robust gradient descent algorithms as follows with f1,D = 0 and |D|

ft+1,D = ft,D −

η X ′ G (ξt,D,σ (zi ))(ft,D (xi ) − yi )Kxi , |D| i=1

∀t ⩾ 1,

(4)

where η > 0 is the step size, zi = (xi , yi ), and ξt,D,σ (zi ) =

(ft,D (xi ) − yi )2 . σ2

We next extend (4) to a distributed learning setting. Specifically, the full data set D is partitioned into m disjoint Sm subsets {Dj }m j=1 such that D = j=1 Dj and Di ∩ Dj = ∅ for i ̸= j. On the j-th local machine, the robust gradient descent iteration (4) is performed using only the local sample Dj , yielding the local estimator ft,Dj . Subsequently, the local estimators are aggregated through an average weighted by the local sample sizes to produce a global estimator f¯t,D =

m X |Dj | j=1

|D|

ft,Dj .

(5)

When each local machine performs T gradient descent iterations, our analysis focuses on the last iterate f¯T +1,D , where T = T (|D|) : N → N serves as an early-stopping rule to prevent overfitting. The distributed estimator (5) follows the standard divide-and-conquer paradigm: the local machines perform their computations independently, and communication is required only for the final aggregation of the local estimators. Although such a strategy is simple and communication-eﬀicient, weighted aggregation alone may fail to fully compensate for the statistical loss caused by splitting the full sample across multiple local machines [5]. Consequently, to retain the optimal learning rate, the number of local machines typically has to satisfy a restrictive upper bound. A natural approach to alleviating this restriction is to allow additional communication among the local machines. Existing distributed learning methods achieve this by exchanging various types of information, including data [14], gradients [5, 15, 16], and local estimators [17, 18, 19]. In particular, [5] developed a Newton–Raphson-based communication strategy for DKRR, which substantially relaxed the restriction on the admissible number of local machines. Motivated by this idea, we develop an analogous communication strategy for DKRGD in the next subsection. One of the main objectives of this paper is to establish optimal learning rates for the distributed estimator (5), both in expectation and with high probability. By exploiting the concentration inequality developed in [20], our analysis allows a substantially larger number of local machines than that permitted by existing analyses. Furthermore, we introduce a DKRGD algorithm with communication that further relaxes the restriction on the number of local machines, without requiring additional unlabeled data as in [6, 21]. 5

2.2

DKRGD with Communication In this subsection, we propose a novel communication strategy for DKRGD with the aim of further relaxing the re-

striction on the number of local machines. Our construction is motivated by the Newton–Raphson-type communication strategy introduced in [5]. To facilitate the development of the algorithm, we first derive two operator representations of the robust gradient descent iteration (4). Define the empirical integral operator LK,D as follows, 1 |D|

LK,D (f ) = and denote Et,D,σ =

1 |D|

∀f ∈ HK ,

f (xi )Kxi ,

(xi ,yi )∈D

(G′+ (0) − G′ (ξt,D,σ (zi )))(ft,D (xi ) − yi )Kxi ,

(6)

(xi ,yi )∈D

then the algorithm (4) can be rewritten as |D|

ft+1,D = ft,D −

η X ′ G (0)(ft,D (xi ) − yi )Kxi + ηEt,D,σ |D| i=1 +

= (I − ηG′+ (0)LK,D )ft,D + ηG′+ (0)fˆK,D + ηEt,D,σ , P 1 where I denotes the identity operator, and fˆK,D = |D| (xi ,yi )∈D yi Kxi . By adding and subtracting the population integral operator LK , defined in (13), we also obtain ft+1,D = (I − ηG′+ (0)LK )ft,D + ηG′+ (0)(LK − LK,D )ft,D + ηG′+ (0)fˆK,D + ηEt,D,σ . Then by induction, we can derive two representations for ft+1,D as ft+1,D =

t X

ηG′+ (0) I − ηG′+ (0)LK,D

t−i

fˆK,D +

i=1

and ft+1,D = +

t X i=1 t X

t X

η I − ηG′+ (0)LK,D

t−i

(7)

Ei,D,σ ,

i=1

ηG′+ (0) I − ηG′+ (0)LK

t−i

fˆK,D +

t X

ηG′+ (0) I − ηG′+ (0)LK

t−i

(LK − LK,D )fi,D

i=1

(8)

t−i I − ηG′+ (0)LK Ei,D,σ .

i=1

Based on the representation (7), we can design a communication strategy for DKRGD by the Newton-Raphson iteration applied in [5]. For the sake of convenience, we introduce a polynomial denoted by gt (x) =

t X

ηG′+ (0) 1 − ηG′+ (0)x

t−i

∀t > 0,

(9)

i=1

and gt (LK,D ) is defined by the spectral calculus. The invertibility of gt (LK,D ) can be guaranteed by the specific choice of η, which will be given in the main results. Then for any f ∈ HK , we can rewrite ft+1,D as ft+1,D = gt (LK,D )fˆK,D + " = f − gt (LK,D )

t X

η I − ηG′+ (0)LK,D

t−i

Ei,D,σ

i=1

gt−1 (LK,D )f − fˆK,D − gt−1 (LK,D )

t X i=1

t−i I − ηG′+ (0)LK,D Ei,D,σ

(10) ,

where the last equation can be seen as the well known Newton-Raphson iteration. Further, a variant of the global gradient for the empirical risk (3) on HK over f can be expressed as Gt+1,D (f ) = gt−1 (LK,D )f − fˆK,D − gt−1 (LK,D )

t X

η I − ηG′+ (0)LK,D

t−i

(11)

Ei,D,σ ,

i=1

where Ei,D,σ remains invariant to the change of f . In distributed setting, denote the global estimator (5) without Pm |Dj | communication by f¯0 := f¯t+1,D = ft+1,D . Then by applying (10) to each Dj , we can get t+1,D

0 f¯t+1,D =f−

m X |Dj | j=1

|D|

j=1 |D|

" gt (LK,Dj )

gt−1 (LK,Dj )f − fˆK,Dj − gt−1 (LK,Dj )

t X

t−i I − ηG′+ (0)LK,Dj Ei,Dj ,σ

# .

i=1

For any l ∈ N+ , let l−1 βDj ,l−1 = gt (LK,Dj )Gt+1,D (f¯t+1,D ).

Then we can use the Newton-Raphson iteration to design our communication strategy as l−1 l f¯t+1,D = f¯t+1,D −

l−1 = f¯t+1,D −

m X |Dj | j=1

|D|

m X |Dj | j=1 m X

|D|

βDj ,l−1

h i |Dj | l−1 gt (LK,Dj ) gt−1 (LK,D )f¯t+1,D − fˆK,D |D| j=1

gt (LK,Dj )gt−1 (LK,D )

t X

η I − ηG′+ (0)LK,D

t−i

(12) Ei,D,σ .

i=1

Thus, each communication round applies a Newton–Raphson-type correction to the current global estimator by combining information from the local empirical operators. As will be shown in the subsequent analysis, these additional communication rounds enable DKRGD to tolerate a substantially larger number of local machines while retaining the desired generalization performance. It is worth noting that the global quantity Gt+1,D in (11) cannot be recovered by simply taking a weighted average of its local counterparts in general. Consequently, an exact implementation of (12) requires the estimation or communication of certain global operator quantities. Developing more eﬀicient aggregation and operator-estimation procedures for this communication scheme is an interesting direction for future work.

Main Results In this section, we present generalization bounds for DKRGD both with high probability and in expectation. We

then investigate DKRGD with communication and show that, under suitable regularity conditions, communication can further relax the restriction on the number of local machines while preserving the optimal learning rate. To state the main results, we first introduce several standard assumptions concerning the boundedness of the output, the regularity of the regression function, and the capacity of the RKHS HK . Throughout this paper, we assume that the kernel K is a Mercer kernel and X is compact, then K is bounded p and define κ = supx∈X K(x, x) < ∞. Without loss of generality, we will assume κ ≥ 1 in the subsequent analysis. Let ρX be the marginal distribution of ρ and L2ρX be the Hilbert space of ρX square integrable functions on X , with norm denoted by∥ · ∥ρ . The kernel K induces the integral operator LK defined on L2ρX (or the RKHS HK ) by Z LK (f ) = f (x)Kx dρX , f ∈ L2ρX (or f ∈ HK ). X

We first impose a standard boundedness condition on the output variable. 7

(13)

Assumption 1. There exists a constant M > 0 such that |y| ≤ M almost surely with respect to ρ. The boundedness of the outputs is a common assumption in the analysis of regression problems, which is also adopted in [3, 8]. Although it is slightly stricter than some moment conditions in more general settings [22], our analysis in this paper can be easily extended to the case by assuming moment conditions on the outputs. The next assumption characterizes the regularity of the regression function. Assumption 2. There exist r > 0 and uρ ∈ L2ρX such that fρ = LrK uρ ,

(14)

where LrK denotes the r-th power of LK : L2ρX → L2ρX as a compact and positive operator. The regularity condition (14) of the regression function is a common assumption in the analysis of kernel-based learning algorithms [3, 5, 8, 22], which is also known as the source condition in the context of inverse problems. It states that fρ lies in the range of LrK , and the special case r = 1/2 corresponds to the situation where fρ ∈ HK . Intuitively, larger values of r indicate higher regularity of fρ , potentially resulting in improved learning rates. The complexity of the hypothesis space HK with respect to the measure ρX is measured by the effective dimension defined as

N (λ) = Tr (λI + LK )−1 LK ,

λ > 0.

And the capacity assumption is given by the polynomial decay of the effective dimension. Assumption 3. There exists some s ∈ (0, 1] and a constant C0 ≥ 1 which is independent of λ, such that N (λ) ≤ C0 λ−s ,

∀λ > 0.

(15)

Condition (15) with s = 1 is always satisfied by taking the constant C0 = Tr(LK ) ⩽ κ2 . Now we are ready to present the main results, the first of which to be proved in section 6 exhibits optimal learning rates for DKRGD with high probability. Note that the generalization performance of target function estimation is measured by the ρ− distance between the estimator and the regression function, i.e., f¯T +1,D − fρ . ρ

Theorem 1. Let 0 < δ < 1, p > 0 and 0 < η ≤ κ2 max{G1′ (0),CG } . Under Assumption 1-3 with r > 12 and 0 < s ≤ 1, if + l m 1 1 λ = |D|− 2r+s , T = |D| 2r+s , |D1 | = · · · = |Dm | and 2r+s−1

m≤ then with confidence at least 1 − δ, there holds

|D| 4r+2s 5

(log |D|) + 1 (

2 ,

(16)

p+1

f¯T +1,D − fρ ρ ≤ C̃1 max |D|

r − 2r+s

|D| 2r+s , σ 2p

)

48 log δ

6 ,

(17)

where C̃1 is a constant independent of |D| or m, and will be given explicitly in the proof. Here and throughout the paper, ⌈x⌉ denotes the smallest integer greater than or equal to x. As shown in Theorem p+1+r

1, by choosing σ ≥ |D| (2r+s)2p and neglecting the logarithmic factor, the high-probability upper bound in (17) yields the optimal learning rate O(|D|− 2r+s ) in L2ρX , which achieves the mini-max lower bound proved in [22, 23]. r

Remark 1. Theorem 1 establishes a high-probability learning rate for DKRGD under the regularity condition r > 12 of fρ . In the boundary case r = 12 , where fρ ∈ HK , the resulting bound incurs an additional logarithmic factor log |D| compared with (17). The logarithmic factor arises at the final stage of the error aggregation. Since the proof follows the same line as that of Theorem 1, the details are omitted. We next turn to the generalization performance of DKRGD in expectation. Compared with the high-probability analysis, the expectation bound allows a weaker restriction on the number of local machines. Theorem 2. Let p > 0 and 0 < η ≤ κ2 max{G1′ (0),CG } . Under Assumption 1-3 with r > 12 and 0 < s ≤ 1, if + l m 1 1 − 2r+s 2r+s λ = |D| , T = |D| , |D1 | = · · · = |Dm | and  −1 2r+ s −1 2 2  2r+s (log |D|) + 1 , 12 < r ≤ 1, |D|     −1  2  |D| 2r−1 2r+s (log |D|) + 1 , 1 < r ≤ 32 , m≤ −1 2  2 3   |D| 2r+s (log |D|) + 1 , < r ≤ 5−s ,  2 2   2r+s−1  8 5−s −1 |D| 4r+2s ((log |D|) + 1) , r> 2 , then E

(

f¯T +1,D − fρ ρ ≤ C̃2 max |D|

2p+2

2r − 2r+s

|D| 2r+s , σ 4p

(18)

) (19)

where C̃2 is a constant independent of |D| or m, and will be given explicitly in the proof. p+1+r

Analogously, Theorem 2 establishes that with the choice of σ ≥ |D| (2r+s)2p , one can obtain the optimal learning rate O(|D|− 2r+s ) from the expected error bound in (19). As a comparison between Theorem 1 and Theorem 2, we 2r

can see that the upper bound of (16) is tighter than that of (18) for all possible values of r, which shows a stricter restriction on m to guarantee the optimal learning rate with high probability than that in expectation. Note that when the regularity of fρ exceeds a certain level, the restriction on m in Theorem 1 and Theorem 2 reduce to the same order 2r+s−1

|D| 4r+2s , differing only by a logarithmic factor. Remark 2. An logarithmic factor also arises in Theorem 2 for the expected error bound. At the critical level r = 21 , the resulting bound incurs an additional log2 |D| factor compared with (19). This quadratic logarithmic factor results from converting the high-probability estimate into an expectation bound: the logarithmic factor in the high-probability estimate appears squared when moving from tail probability to expectation bounds. The derivation closely parallels that of Theorem 2 and is omitted for brevity. We finally consider DKRGD equipped with the communication strategy introduced in Subsection 2.2. The following theorem quantifies how communication can enlarge the admissible number of local machines while retaining the optimal high-probability learning rate. Theorem 3. Let 0 < δ < 1, p > 0, 0 < η < κ2 max{G1′ (0),CG } and l ∈ N+ . Under Assumption 1-3 with r > 12 and + m l 1 1 − 2r+s 2r+s , |D1 | = · · · = |Dm | and , T = |D| 0 < s ≤ 1, if λ = |D| n o −1 (2r−1)(l+1)+s 2r−1 7 m ≤ min |D| 2r+s , |D| (2r+s)(l+2) (log |D|) + 1 , then with confidence at least 1 − δ, there holds f¯Tl +1,D − fρ ρ ≤ C̃3 max

(

p+1

|D|

r − 2r+s

|D| 2r+s , σ 2p

) log

96 δ

6+3l

where C̃3 is a constant independent of |D| or m, and will be given explicitly in the proof. 9

(20)

(21)

p+1+r

It should be pointed that the optimal learning rate O(|D|− 2r+s ) can be also obtained by setting σ ≥ |D| (2r+s)2p r

in (21). By comparing n(16) with (20), the proposed communication strategy relaxes the restriction on m from order o 2r+s−1

2r−1

(2r−1)(l+1)+s

|D| 4r+2s to order min |D| 2r+s , |D| (2r+s)(l+2)

up to a logarithmic factor. Further, the upper bound of m in (20) is 2r−1

increasing with respect to the number of communications l, and it tends to order |D| 2r+s up to a logarithmic factor as l → ∞, which is significantly larger than the upper bound of m in (16) and coincides with that in [2, 3, 4, 6]. Although this limit is not better than that in Theorem 2 for every value of r, it should be highlighted that the optimal learning rate in Theorem 3 is achieved with high probability, which is stronger than that in expectation in Theorem 2. To conclude, Theorem 3 conducts the generalization analysis with high probability for DKRGD with communication strategy, which significantly relaxes the restriction on the number of local machines to ensure optimal learning rates, and thus enhances the practical applicability of DKRGD in distributed learning.

Related Work As a special instance of spectral algorithms, gradient descent (GD) has received extensive attention in the literature.

A comprehensive overview of gradient-based optimization methods is provided in [24], covering widely used variants of gradient descent, such as mini-batch and stochastic gradient descent, adaptive optimization methods including Adam and AdaMax, and distributed stochastic optimization frameworks such as Hogwild! and TensorFlow. In the context of nonparametric learning, the statistical properties of gradient descent have been rigorously investigated in [21, 25, 26], where optimal learning rates were established under suitable regularity and capacity conditions. More recently, [6] studied kernel-based gradient descent in a distributed setting and established optimal learning rates in probability. An important observation therein is that the intrinsic regularization properties of gradient descent can be exploited to alleviate the saturation phenomenon that typically arises in distributed spectral algorithms. Despite these favorable theoretical properties, standard gradient descent based on the squared loss is generally sensitive to outliers and heavy-tailed noise, and its performance may deteriorate substantially in such settings. Consequently, several approaches have been developed to improve its robustness. Early-stopping strategies, which serve as an implicit regularization mechanism for controlling overfitting to noisy observations, have been extensively studied in [13, 27]. Alternatively, robust loss functions can be employed in place of the squared loss. In particular, [8] investigated gradient descent equipped with a broad class of robust losses, while [28] analyzed the convergence behavior of kernel gradient descent under the maximum correntropy criterion. Motivated by these developments in robust gradient descent and distributed learning [5, 6, 8, 9, 10], we investigate the generalization performance of DKRGD, a problem that has received comparatively little theoretical attention to date. A particularly relevant starting point is [8], which demonstrates that robust gradient descent, combined with an appropriate early-stopping rule and a suitable choice of the scale parameter σ, achieves optimal convergence rates in L2ρX . More precisely, under Assumptions 1–2 and an eigenvalue decay condition slightly stronger than Assumption 3, the following estimate holds with confidence at least 1 − δ: ( ∥fT +1 − fρ ∥ρ ≤ O max |D|

p+1

r − 2r+s

|D| 2r+s , σ 2p

)

! [log(6/δ)]

p+1+r

Consequently, choosing σ ≥ |D| (2r+s)2p yields the optimal convergence rate O(|D|− 2r+s ) r

in the L2ρX -norm. Under Assumptions 2–3 and a condition implied by Assumption 1, optimal learning rate in probability r− 1 2

for robust gradient descent algorithms was established in [6]: if r > 12 and m ≤ |D| 2r+s /[(log |D|)5 + 1], then with 10

confidence at least 1 − δ there holds r 4 f¯T +1,D − fρ ρ ≤ O |D|− 2r+s [log(12/δ)] . This result shows that optimal learning rates can be retained in the distributed setting, provided that the number of local machines is suﬀiciently controlled. In contrast, by deriving sharper estimates for certain operator products through the concentration inequality developed in [20], we establish optimal learning rates in probability for DKRGD while substantially relaxing the restriction on the number of local machines. More specifically, the admissible number m of local machines can be 2r+s−1

enlarged to |D| 4r+2s /[(log |D|)5 + 1]2 . Moreover, the result of [6] permits a nontrivial number of local machines only when r > 12 , and therefore does not cover the boundary case r = 12 . This limitation is largely overcome by Theorem 1, although an additional logarithmic factor log |D| appears in the resulting learning rate. As for the optimal learning rates in expectation, we further sloosen the restriction on m. Compared with [3], the 2r+

2r−1

−1

maximum number m is relaxed slightly from |D| 2r+s to |D| 2r+s [(log |D|) + 1]−1 when 21 ≤ r ≤ 1. In addition, 2

the saturation phenomenon inherent to regularized least squares [3] is effectively mitigated by leveraging the results R∞ in Theorem 1 and the standard tail-expectation formula E[ξ] = 0 Prob(ξ > t)dt. Specifically, while maintaining optimal learning rates in expectation, the admissible upper bound on the number of local machines can scale up with increasing r when r > (5 − s)/2. In distributed learning, numerous studies have focused on relaxing the restriction on the number of local machines by utilizing unlabeled data [6, 21] or introducing communication strategies [5, 14, 16]. Such approaches can compensate for the statistical loss caused by data partitioning and thereby improve the practical applicability of distributed algorithms. For nonparametric regression, the most relevant work is [5], in which a communication strategy based on the Newton-Raphson iteration is proposed for distributed kernel ridge regression. Inspired by this approach, we propose a communication-enhanced version of DKRGD that further relaxes the restriction on the number of local machines without requiring additional unlabeled data. Although our condition on the number of local machines for attaining the optimal learning rate is slightly more restrictive than that obtained in [5], our approach offers two complementary advantages. First, owing to the intrinsic regularization properties of gradient descent, our theoretical results extend beyond the usual range 1/2 ≤ r ≤ 1. More precisely, while the results in [5] are restricted to 1/2 ≤ r ≤ 1, Theorem 3 applies to the entire regime r > 12 . Second, the use of a robust loss makes the resulting distributed algorithm more resistant to outliers and heavy-tailed noise. It would also be interesting to investigate whether the proposed communication strategy can be adapted to other distributed learning frameworks, such as deep distributed convolutional neural networks [29] and distributed gradient descent functional learning [30].

Error decomposition In this section, we conduct the error analysis of DKRGD using the integral operator approach [3, 5, 6, 31,

32]. We first introduce several preliminary lemmas and propositions that will be repeatedly used in the subsequent analysis. We then derive two distinct error decompositions for DKRGD, which serve as the basis for establishing generalization bounds both with high probability and in expectation, respectively. Finally, we develop a corresponding error decomposition for DKRGD with communication and use it to derive a high-probability generalization bound.

5.1

Preliminaries As the intermediate function in the error decomposition, we first introduce the data-free sequence {ft }t≥1 which

can be regarded as the limit of {ft,D }t≥1 when the sample size |D| goes to infinity, and then we will derive two representations for ft+1 by using the integral operator approach. Specifically, it is defined as follows, Z ft+1 = ft − η G′ (ξt,σ (z))(ft (x) − y)Kx dρ,

(22)

where f1 = 0, 1 ≤ t ≤ T and ξt,σ (z) = (y−fσt2(x)) , (x, y) ∈ D. For the simplicity of subsequent calculations, we can further rewrite ft+1 as ft+1 = ft − ηG′+ (0)LK (ft − fρ ) + η

Z Z

(G′+ (0) − G′ (ξt,σ (z)))(ft (x) − y)Kx dρ

= I − ηG′+ (0)LK ft + ηG′+ (0)LK fρ + ηEt,σ , and

where Et,σ =

ft+1 = I − ηG′+ (0)LK,D ft + ηG′+ (0)(LK,D − LK )ft + ηG′+ (0)LK fρ + ηEt,σ ,

R Z

(G′+ (0) − G′ (ξt,σ (z)))(ft (x) − y)Kx dρ.

Analogous to Equation (7) and (8), we can employ mathematical induction to derive the following two representations for ft+1 as ft+1 =

t X

ηG′+ (0) I − ηG′+ (0)LK

t−i

LK fρ +

i=1

and ft+1 =

t X

η I − ηG′+ (0)LK

t−i

Ei,σ ,

t−i

LK fρ +

i=1

t X

ηG′+ (0) I − ηG′+ (0)LK,D

t−i

(LK,D − LK )fi

i=1 t X

(23)

i=1

ηG′+ (0) I − ηG′+ (0)LK,D

t X

(24)

t−i I − ηG′+ (0)LK,D Ei,σ .

i=1

By combining (7) and (24), it is easy to obtain the representation for the difference between fT +1,D and fT +1 as fT +1,D − fT +1 =

T X

ηG′+ (0) I − ηG′+ (0)LK,D

T −i

fˆK,D − LK fρ +

i=1

1 (E − E ) + (L − L )f i,D,σ i,σ K K,D i . (25) G′+ (0)

Moreover, we can combine (8) and (23) to yield another representation for fT +1,D −fT +1 as fT +1,D − fT +1 =

T X

ηG′+ (0)

T −i I − ηG′+ (0)LK

fˆK,D − LK fρ +

i=1

1 (Ei,D,σ − Ei,σ ) + (LK − LK,D )fi,D . (26) G′+ (0)

Building on the operator representations introduced above, we now establish key estimates for operator products and the data-free iterative sequence {ft }t≥1 , which form the foundation of our subsequent error analysis. Throughout this paper, we simply denote the operator norm as ∥ · ∥. The following two lemmas are obtained by adapting the proof in [8, Prop. 4.1, Thm. 1(i)] to accommodate our constant step-size η. For brevity, detailed proofs are deferred to the Appendix. Lemma 1. Define {ft }t≥1 as (22) and f1 = 0. If 0 < η ≤ κ2 max{G1′ (0),CG } , then +

∥ft ∥K ≤ M

ηCG (t − 1) ≤ 12

M 1 (t − 1) 2 , κ

∀ t ≥ 1.

(27)

Lemma 2. For λ > 0, 0 < η ≤ κ2 max{G1′ (0),CG } , and T ∈ N, we have + ( T ) T X X T −i T −i ′ ′ ′ ′ max ηG+ (0)(λI + LK ) I − ηG+ (0)LK , ηG+ (0)(λI + LK,D ) I − ηG+ (0)LK,D i=1

i=1

≤ηG′+ (0)λT + 1. In the end of this subsection, we derive an error decomposition based on (25), which is crucial for the subsequent error analysis of DKRGD in both the high-probability and expectation settings. Proposition 1. Let λ > 0, 0 < η ≤ κ2 max{G1′ (0),CG } , and T ∈ N. If Assumption 2 holds for r ≥ 12 , we have +

(λI + LK ) 2 (fT +1,D − fT +1 )

≤ (1 + ηG′+ (0)λT )A2D,λ (PD,λ + QD,λ ∥fρ ∥K ) +

T X

η (λI + LK,D ) 2 I − ηG′+ (0)LK,D 1

T −i

AD,λ ∥Ei,D,σ − Ei,σ ∥K

i=1

T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

T −i

(28)

A2D,λ QD,λ ∥fi − fρ ∥K ,

i=1

where AD,λ = (λI + LK ) 2 (λI + LK,D )− 2 , 1

1 PD,λ = (λI + LK )− 2 (fˆK,D − LK fρ )

, K

QD,λ = (λI + LK )− 2 (LK − LK,D ) . 1

Proof. With the representation (25) for fT +1,D − fT +1 , we have 1

(λI + LK ) 2 (fT +1,D − fT +1 )

T X

≤ AD,λ

(λI + LK,D ) ( ≤ AD,λ

T X

Ei,D,σ − Ei,σ fˆK,D − LK fρ + + (LK − LK,D )fi G′+ (0)

η(λI + LK,D ) I − ηG′+ (0)LK,D

T −i

(λI + LK,D )− 2 (Ei,D,σ − Ei,σ ) 1

i=1

T −i

i=1

− 21

ηG′+ (0)(λI + LK,D ) I − ηG′+ (0)LK,D

(29)

T X

ηG′+ (0)(λI + LK,D ) I − ηG′+ (0)LK,D

T −i

(λI + LK,D )− 2 (fˆK,D − LK fρ ) 1

i=1

ηG′+ (0)(λI + LK,D ) I − ηG′+ (0)LK,D

T −i

(λI + LK,D )

− 21

(LK − LK,D )fi

i=1

=: AD,λ (A1 + A2 + A3 ). For A1 , applying the triangle inequality of K-norm, we have A1 ≤

T X

η (λI + LK,D ) 2 I − ηG′+ (0)LK,D 1

T −i

∥Ei,D,σ − Ei,σ ∥K .

i=1

To estimate A2 , Lemma 2 yields A2 ≤

T X

)

K T X

ηG′+ (0)(λI + LK,D ) I − ηG′+ (0)LK,D

T −i

1 (λI + LK,D )− 2 (fˆK,D − LK fρ )

i=1

≤ (1 + ηG′+ (0)λT ) (λI + LK,D )− 2 (λI + LK ) 2 1

= (1 + ηG′+ (0)λT )AD,λ PD,λ , 13

(λI + LK )− 2 (fˆK,D − LK fρ ) 1

where the last equality holds since ∥L1 L2 ∥ = ∥(L1 L2 )∗ ∥ = ∥L2 L1 ∥ for any self-adjoint operators L1 and L2 on Hilbert spaces. Concerning A3 , by the decomposition fi = fi − fρ + fρ , we have A3 ≤

T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

T −i

AD,λ QD,λ ∥fi − fρ ∥K

i=1

T X

ηG′+ (0)(λI + LK,D ) I − ηG′+ (0)LK,D

T −i

AD,λ QD,λ ∥fρ ∥K

i=1

≤

T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

T −i

AD,λ QD,λ ∥fi − fρ ∥K + (1 + ηG′+ (0)λT )AD,λ QD,λ ∥fρ ∥K .

i=1

Finally, the proof of Proposition 1 is completed by substituting the bounds on A1 , A2 , and A3 into (29).

5.2

Error decomposition I for DKRGD To derive the generalization bounds in probability, we establish an error decomposition for DKRGD that will

be used to prove Theorem 1. Specifically, by introducing the data-free sequence {ft }t≥1 , we decompose the error f¯T +1,D − fρ into two parts: f¯T +1,D − fT +1 and ∥fT +1 − fρ ∥ . These two components are then estimated in the ρ

following two propositions, respectively. Proposition 2. For λ > 0, 0 < η ≤ κ2 max{G1′ (0),CG } , and T ∈ N. If Assumption 2 holds for r ≥ 12 , we have +

f¯T +1,D − fT +1 ρ ≤ (1 + ηG′+ (0)λT )(PD,λ + QD,λ ∥fρ ∥K ) +

T X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

i=1

T X

m T −i X |Dj | Ei,Dj ,σ − Ei,σ K |D| j=1

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

QD,λ ∥fi − fρ ∥K + max KDj ,λ , 1≤j≤m

i=1

where KDj ,λ =

T X i=2

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

RDj ,λ ADj ,λ ·

(1 + ηG′+ (0)λ(i − 1))ADj ,λ (PDj ,λ + QDj ,λ ∥fρ ∥K ) +

i−1 X

η (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

i−l−1

El,Dj ,σ − El,σ K

l=1

i−1 X

ηG′+ (0)

(λI + LK,Dj )

i−l−1 I − ηG′+ (0)LK,Dj

ADj ,λ QDj ,λ ∥fl − fρ ∥K ,

l=1

and RD,λ := (λI + LK )− 2 (LK − LK,D )(λI + LK )− 2 . 1

Proof. Based on the definition (5) of f¯t,D , we can apply (26) to Dj for each fixed j ∈ 1, ..., m to have that f¯T +1,D − fT +1 =

m X |Dj |

( T X

|D| j=1

i=1

m X |Dj | j=1

|D|

(fT +1,Dj − fT +1 )

ηG′+ (0) I − ηG′+ (0)LK

T −i

1 fˆK,Dj − LK fρ + ′ (Ei,Dj ,σ − Ei,σ ) + (LK − LK,Dj )fi,Dj G+ (0) 14

) .

Since

|Dj | j=1 |D| = 1 and m X |Dj |

|D|

j=1

fˆK,Dj =

we have f¯T +1,D − fT +1 ρ ≤

m X |Dj | 1 |D| |Dj | j=1

T X

yi Kx i =

(xi ,yi )∈Dj

ηG′+ (0) I − ηG′+ (0)LK

T −i

1 |D|

yi Kxi = fˆK,D ,

(xi ,yi )∈D

(fˆK,D − LK fρ )

i=1

ρ T X

η I − ηG′+ (0)LK

T −i

i=1

T X

m X

|Dj | (Ei,Dj ,σ − Ei,σ ) |D| j=1

ηG′+ (0) I − ηG′+ (0)LK

i=1

(30)

m T −i X |Dj | (LK − LK,Dj )fi,Dj |D| j=1

=: I1 + I2 + I3 . 1

2 f Since ∥f ∥ρ = LK

2 for any f ∈ HK and LK (λI + LK )− 2 ≤ 1 for any λ > 0, we have

T X

I1 =

ηG′+ (0)(λI + LK ) I − ηG′+ (0)LK

T −i

(λI + LK )−1 (fˆK,D − LK fρ )

i=1 T X

≤

ηG′+ (0)(λI + LK ) I − ηG′+ (0)LK

T −i

(λI + LK )− 2 (fˆK,D − LK fρ )

(31)

i=1

≤ (1 + ηG′+ (0)λT )PD,λ , where the last inequality holds by Lemma 2. For I2 , it’s easy to derive that I2 ≤

T X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

i=1

m T −i X |Dj | Ei,Dj ,σ − Ei,σ K . |D| j=1

(32)

For I3 , it can be bounded by decomposing fi,Dj as fi,Dj = fi,Dj − fi + fi − fρ + fρ as follows I3 ≤

T X

ηG′+ (0)(λI + LK ) I − ηG′+ (0)LK

i=1

T X

m T −i X |Dj | 1 (λI + LK )− 2 (LK − LK,Dj )(fi,Dj − fi ) |D| j=1

ηG′+ (0)(λI + LK ) I − ηG′+ (0)LK

T −i

(λI + LK )− 2 (LK − LK,D )(fi − fρ ) 1

i=1

T X

ηG′+ (0)(λI + LK ) I − ηG′+ (0)LK

T −i

(33)

(λI + LK )− 2 (LK − LK,D )fρ 1

i=1

=: I3,1 + I3,2 + I3,3 , where I3,2 and I3,3 is derived from the fact that for any f ∈ HK , there holds m X |Dj | j=1

|D|

LK,Dj f =

m X |Dj | 1 X 1 X f (xi )Kxi = f (xi )Kxi = LK,D f. |D| |D | |D| j j=1 x ∈D x ∈D i

For I3,2 , since fi ∈ HK and Assumption 2 with r ≥ 12 implies fρ ∈ HK , then I3,2 ≤

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

i=1

T −i

QD,λ ∥fi − fρ ∥K .

(34)

Analogously, I3,3 can be bounded by Lemma 2 as I3,3 ≤

T X

ηG′+ (0)(λI + LK ) I − ηG′+ (0)LK

T −i

(λI + LK )− 2 (LK − LK,D ) ∥fρ ∥K 1

(35)

i=1

= (1 + ηG′+ (0)λT )QD,λ ∥fρ ∥K . To bound I3,1 , we use f1 = f1,D = 0 and Jensen’s inequality to obtain I3,1 ≤

T X

ηG′+ (0)

(λI + LK )

m X |Dj |

T −i I − ηG′+ (0)LK

|D| j=1

i=2

≤

m X

(λI + LK )− 2 (LK − LK,Dj )(fi,Dj − fi ) 1

T X

T −i |Dj | ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK · |D| i=2 j=1 (λI + LK )− 2 (LK − LK,Dj )(λI + LK )− 2 1

≤ max

T X

1≤j≤m

(λI + LK ) 2 (fi,Dj − fi )

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

K 1 2

RDj ,λ (λI + LK ) (fi,Dj − fi )

i=2

. K

Recall the proof of Proposition 1 with D and T + 1 replaced by Dj and i, we have 1

(λI + LK ) 2 (fi,Dj − fi )

≤ (1 + ηG′+ (0)λ(i − 1))A2Dj ,λ (PDj ,λ + QDj ,λ ∥fρ ∥K ) +

i−1 X

η (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

i−l−1

ADj ,λ El,Dj ,σ − El,σ K

l=1

i−1 X

ηG′+ (0) (λI + LK,Dj ) I − ηG′+ (0)LK,Dj

i−l−1

A2Dj ,λ QDj ,λ ∥fl − fρ ∥K .

l=1

It follows that I3,1 ≤ max

1≤j≤m

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

RDj ,λ ADj ,λ ·

i=2

(1 + ηG′+ (0)λ(i − 1))ADj ,λ (PDj ,λ + QDj ,λ ∥fρ ∥K ) +

i−1 X

η (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

i−l−1

l=1

i−1 X

ηG′+ (0)

(λI + LK,Dj )

(36)

El,Dj ,σ − El,σ K

i−l−1 I − ηG′+ (0)LK,Dj

ADj ,λ QDj ,λ ∥fl − fρ ∥K

l=1

= max KDj ,λ . 1≤j≤m

By substituting (34), (35) and (36) into (33), we have I3 ≤ max KDj ,λ + (1 + ηG′+ (0)λT )QD,λ ∥fρ ∥K 1≤j≤m

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

(37) QD,λ ∥fi − fρ ∥K .

i=1

Finally, the proof of Proposition 2 is completed by substituting (31), (32) and (37) into (30). We are now ready to bound the generalization error ∥fT +1 − fρ ∥ρ , as formalized in the following proposition. The proof adapts the analytical framework established in [13, 33] to our setting. 16

Proposition 3. Define {ft }t≥1 as (22) and f1 = 0. If Assumption 2 holds for r ≥ 12 , then for any t ≥ 2, we have ∥ft − fρ ∥K ≤ and

∥ft − fρ ∥ρ ≤

r eηG′+ (0)

r − 12 eηG′+ (0)

r− 12

∥uρ ∥ρ (t − 1)−(r− 2 ) + 1

t−1 X

η∥Ei,σ ∥K ,

(38)

i=1

r ∥uρ ∥ρ (t − 1)−r +

t−1 X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

t−i−1

∥Ei,σ ∥K .

(39)

i=1

Proof. Firstly, for the sake of convenience, we adopt the notation gt (·) defined in (9). Since for any t ⩾ 2, gt−1 (x) · x =

t−1 X

ηG′+ (0)x 1 − ηG′+ (0)x

t−k−1

k=1

t−1 h X

t−1 X

1 − (1 − ηG′+ (0)x)

1 − ηG′+ (0)x

t−k−1

k=1

t−k−1 1 − ηG′+ (0)x −

t−k 1 − ηG′+ (0)x

=1−

(40)

t−1 1 − ηG′+ (0)x ,

k=1

we have that for any adjoint operator A, t−1

I − gt−1 (A)A = I − ηG′+ (0)A

With the representation (23) of ft , we can rewrite ft − fρ as ft − fρ = gt−1 (LK )LK fρ − fρ +

t−1 X

η I − ηG′+ (0)LK

t−i−1

Ei,σ

i=1

= − I − ηG′+ (0)LK

t−1

fρ +

t−1 X

η I − ηG′+ (0)LK

t−i−1

Ei,σ .

i=1

Further, it can be derived that ∥ft − fρ ∥K ≤ ∥ I − ηG′+ (0)LK

t−1

t−1 X

fρ ∥K +

I − ηG′+ (0)LK

t−i−1

Ei,σ

i=1 r− 1

≤ LK 2 I − ηG′+ (0)LK

t−1

∥uρ ∥ρ +

t−1 X

I − ηG′+ (0)LK

t−i−1

∥Ei,σ ∥K

i=1 r− 1

≤ LK 2 I − ηG′+ (0)LK

t−1

∥uρ ∥ρ +

t−1 X

η∥Ei,σ ∥K ,

i=1

where the second inequality holds by Assumption 2 with r ≥ 12 and ∥uρ ∥ρ < ∞, and the last inequality holds by the t−i−1 fact that I − ηG′+ (0)LK ≤ 1 for any i ∈ {1, ..., t − 1}. Since LK is a compact and positive operator, it admits a spectral decomposition with non-negative eigenvalues {γj }∞ j=1 . Then r− 1

LK 2 I − ηG′+ (0)LK

t−1

r− 12

1 − ηG′+ (0)γj

≤ sup γj j≥1

= sup exp j≥1

t−1

1 (t − 1) log(1 − ηG′+ (0)γj ) + (r − ) log γj 2

1 ≤ sup exp −(t − 1)ηG′+ (0)γj + (r − ) log γj 2 j≥1 For the function

1 f (γ) = −(t − 1)ηG′+ (0)γ + (r − ) log γ, 2 17

γ > 0,

r− 1

it is easy to know that the maximum is attained at γ ∗ = (t−1)ηG2 ′ (0) and +

1 1 1 1 f (γ ∗ ) = −(r − ) + (r − ) log(r − ) − (r − ) log[(t − 1)ηG′+ (0)]. 2 2 2 2 Hence, it yields that r− 1 LK 2

t−1 I − ηG′+ (0)LK

Finally, we have

∥ft − fρ ∥K ≤

∗

≤ exp{f (γ )} =

r − 12 eηG′+ (0)

r − 21 eηG′+ (0)

r− 12 ∥uρ ∥ρ (t − 1)

−(r− 21 )

r− 21

(t − 1)−(r− 2 ) . 1

t−1 X

η∥Ei,σ ∥K .

i=1

On the other hand, by following a similar proof strategy, we can likewise obtain ∥ft − fρ ∥ρ ≤ ∥LrK ≤

t−1 I − ηG′+ (0)LK ∥∥uρ ∥ρ +

r eηG′+ (0)

t−1 X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

t−i−1

∥Ei,σ ∥K

i=1

r ∥uρ ∥ρ (t − 1)

−r

t−1 X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

t−i−1

∥Ei,σ ∥K .

i=1

This completes the proof of Proposition 3. Finally, by combining these two propositions with the triangle inequality and letting t = T + 1, we can easily derive the following error decomposition for DKRGD. Proposition 4. For λ > 0, 0 < η ≤ κ2 max{G1′ (0),CG } , and T ∈ N. If Assumption 2 holds for r ≥ 12 , we have +

f¯T +1,D − fρ ρ ≤ (1 + ηG′+ (0)λT )(PD,λ + QD,λ ∥fρ ∥K ) +

T X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

i=1

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

i=1

5.3

m T −i X |Dj | Ei,Dj ,σ − Ei,σ K |D| j=1

r eηG′+ (0)

r ∥uρ ∥ρ T

−r

T X

T −i

QD,λ ∥fi − fρ ∥K + max KDj ,λ

(41)

1≤j≤m

η (λI + LK ) 2 I − ηG′+ (0)LK 1

T −i

∥Ei,σ ∥K .

i=1

Error decomposition II for DKRGD As established in [6], gradient descent can be interpreted as a special instance of spectral algorithms. To derive the

generalization error bounds in expectation for DKRGD, we adopt the general error decomposition framework provided in [3]. Pm j| Lemma 3. Let f¯T +1,D = j=1 |D f , we have |D| T +1,Dj E

m m i X i X |Dj | |Dj |2 h 2 2 2 E f − f + E fT +1,Dj − fρ ρ . f¯T +1,D − fρ ρ ≤ T +1,Dj ρ ρ 2 |D| |D| j=1 j=1

To estimate the first term on the right-hand side of (42), we introduce the following proposition.

(42)

Proposition 5. For λ > 0, 0 < η ≤ κ2 max{G1′ (0),CG } , and T ∈ N. If Assumption 2 holds for r ≥ 12 , we have +

∥fT +1,Dj − fρ ∥ρ ≤ (1 + ηG′+ (0)λT )A2Dj ,λ (PDj ,λ + QDj ,λ ∥fρ ∥K ) +

T X

η (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

T −i

ADj ,λ Ei,Dj ,σ − Ei,σ K

i=1

T X

ηG′+ (0) (λI + LK,Dj ) I − ηG′+ (0)LK,Dj

i=1

r eηG′+ (0)

r ∥uρ ∥ρ T −r +

T X

T −i

A2Dj ,λ QDj ,λ ∥fi − fρ ∥K

η (λI + LK ) 2 I − ηG′+ (0)LK 1

T −i

(43)

∥Ei,σ ∥K .

i=1

Proof. We first decompose the error into the following two parts, fT +1,Dj − fρ = fT +1,Dj − fT +1 + fT +1 − fρ . The estimates of ∥fT +1 − fρ ∥ρ is guaranteed by(39) in Proposition 3, ∥fT +1 − fρ ∥ρ ≤

r eηG′+ (0)

r ∥uρ ∥ρ T −r +

T X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

T −i

∥Ei,σ ∥K .

i=1

For the estimates of ∥fT +1,Dj − fT +1 ∥ρ , applying (28) with D replaced by Dj yields that 1

∥fT +1,Dj − fT +1 ∥ρ ≤ (λI + LK ) 2 (fT +1,Dj − fT +1 )

≤ (1 + ηG′+ (0)λT )A2Dj ,λ (PDj ,λ + QDj ,λ ∥fρ ∥K ) +

T X

η (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

T −i

ADj ,λ Ei,Dj ,σ − Ei,σ K

i=1

T X

ηG′+ (0) (λI + LK,Dj ) I − ηG′+ (0)LK,Dj

T −i

A2Dj ,λ QDj ,λ ∥fi − fρ ∥K .

i=1

Finally, the proof of Proposition 5 is completed by combining the bounds on fT +1,Dj − fT +1 ρ and ∥fT +1 − fρ ∥ρ with the triangle inequality ∥fT +1,Dj − fρ ∥ρ ≤ fT +1,Dj − fT +1 ρ + ∥fT +1 − fρ ∥ρ . The second term on the right-hand side of (42) requires careful treatment. To establish a rigorous bound, we introduce a semi-supervised learning version of the local estimator fT +1,Dj . Specifically, define fT∗ +1,D := E∗ [fT +1,D ] = E [fT +1,D |D(x)] , |D|

where E∗ denotes the conditional expectation with respect to the output y given the fixed input data D(x) = {xi }i=1 . Since E∗ [yi ] = fρ (xi ), it follows from (7) that fT∗ +1,D =

T X

ηG′+ (0)

T −i I − ηG′+ (0)LK,D LK,D fρ +

i=1

T X

η I − ηG′+ (0)LK,D

T −i

i=1

For any fixed j ∈ {1, 2, . . . m}, from Jensen’s inequality, we have

∗

E[fT +1,Dj ] − fρ ρ = E[E [fT +1,Dj ] − fρ ] ρ ≤ E

fT∗ +1,Dj − fρ

. ρ

E∗ [Ei,D,σ ].

(44)

Hence, to estimate E[fT +1,Dj ] − fρ ρ , it suﬀices to derive the bound of fT∗ +1,Dj − fρ

. With D replaced by Dj in

(44), it follows from (40) that fT∗ +1,Dj − fρ =

T X

ηG′+ (0)

T −i LK,Dj − I I − ηG′+ (0)LK,Dj

! fρ +

i=1

T X

η I − ηG′+ (0)LK,Dj

T −i

E∗ [Ei,Dj ,σ ]

i=1

= − I − ηG′+ (0)LK,Dj

fρ +

T X

η I − ηG′+ (0)LK,Dj

T −i

E∗ [Ei,Dj ,σ ].

i=1

Further, since (14) holds for r ≥ 12 , we can derive the following error decomposition fT∗ +1,Dj − fρ

≤ (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

≤ ADj ,λ (λI + LK,Dj ) +

T X

fρ

+ K

T X

η(λI + LK ) 2 I − ηG′+ (0)LK,Dj

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

T −i

E∗ [Ei,Dj ,σ ]

i=1

T r− 1 I − ηG′+ (0)LK,Dj LK 2

1 2

T −i

∥uρ ∥ρ E∗ [Ei,Dj ,σ ] K .

(45)

i=1

Now we are in a position to estimate the above two terms separately, where the corresponding bounds are derived for different ranges of r. r− 1

r− 1

Case 1: 21 ≤ r ≤ 32 . When 12 ≤ r ≤ 1, by rewriting LK 2 as LK 2 = (λI + LK,Dj )r− 2 (λI + LK,Dj )−(r− 2 ) (λI + 1

r− 12

LK )r− 2 (λI + LK )−(r− 2 ) LK , we can derive 1

fT∗ +1,Dj − fρ

≤ ADj ,λ (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

(λI + LK,Dj )r− 2 · r− 1

(λI + LK,Dj )−(r− 2 ) (λI + LK )r− 2 (λI + LK )−(r− 2 ) LK 2 ∥uρ ∥ρ 1

T X

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

i=1

≤ (λI + LK,Dj )r I − ηG′+ (0)LK,Dj +

T X

T −i

E∗ [Ei,Dj ,σ ] K

(46)

A2r Dj ,λ ∥uρ ∥ρ

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

T −i

E∗ [Ei,Dj ,σ ] K ,

i=1

where the last inequality follows from the fact that for two positive operators A, B on a Hilbert space and s ∈ [0, 1], there holds [34] ∥As B s ∥ ≤ ∥AB∥s .

(47)

When 1 < r ≤ 23 , considering that 2r − 1 > 1, we can employ an approach analogous to the case of 12 ≤ r ≤ 1 to obtain fT∗ +1,Dj − fρ

≤ ADj ,λ (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

T X

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

i=1

≤ (λI + LK,Dj )r I − ηG′+ (0)LK,Dj +

T X

T −i

(48) T −i

i=1

where ÃD,λ = ∥(λI + LK,D )−1 (λI + LK )∥, 20

r− 1

E∗ [Ei,Dj ,σ ] K

ÃrDj ,λ ∥uρ ∥ρ

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

2 (λI + LK,Dj )r− 2 ÃDj ,λ ∥uρ ∥ρ

E∗ [Ei,Dj ,σ ] K .

2 and the last inequality holds by the result that ADj ,λ ≤ ÃD . j ,λ

Case 2. 23 < r ≤ 52 . Note that r − 12 > 1, hence the property in (47) cannot be applied directly. To address this issue, we adopt an operator decomposition technique as follows 1

(λI + LK )r− 2 = (λI + LK )r− 2 − (λI + LK,Dj )r− 2 + (λI + LK,Dj )r− 2 . By (45), we have fT∗ +1,Dj − fρ ρ ≤ ADj ,λ (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

(λI + LK,Dj )r− 2 − (λI + LK )r− 2 T (λI + LK,Dj )r I − ηG′+ (0)LK,Dj ∥uρ ∥ρ

+ ADj ,λ T X

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

T −i

∥uρ ∥ρ (49)

E∗ [Ei,Dj ,σ ] K .

i=1

To estimate the first term of the right-hand side of (49), we introduce an operator decomposition in [3] 1

(λI + LK,Dj )r− 2 − (λI + LK )r− 2 3 1 =(λI + LK,Dj ) (λI + LK,Dj )r− 2 − (λI + LK,Dj )−1 (λI + LK )r− 2 3 3 1 =(λI + LK,Dj ) ((λI + LK,Dj )r− 2 − (λI + LK )r− 2 ) + ((λI + LK )−1 − (λI + LK,Dj )−1 )(λI + LK )r− 2 .

(50)

Combining (50) with (49), we have fT∗ +1,Dj − fρ

≤ JDj ,λ + ADj ,λ (λI + LK,Dj )r I − ηG′+ (0)LK,Dj +

T X

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

T −i

∥uρ ∥ρ (51)

E∗ [Ei,Dj ,σ ] K ,

i=1

where JDj ,λ := ADj ,λ (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

(λI + LK,Dj )r− 2 − (λI + LK )r− 2

(λI + LK,Dj )· ∥uρ ∥ρ

+ ADj ,λ (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

(λI + LK,Dj )·

1 (λI + LK )−1 − (λI + LK,Dj )−1 (λI + LK )r− 2 ∥uρ ∥ρ . In the following, we will estimate JDj ,λ for different ranges of r to derive the error decomposition for ∥fT∗ +1,Dj −fρ ∥ρ . When 23 < r ≤ 52 , we have 0 < r − 32 ≤ 1. With the fact that

3 3 3 3 3 (λI + LK,Dj )r− 2 − (λI + LK )r− 2 = (λI + LK,Dj )r− 2 I − (λI + LK,Dj )−(r− 2 ) (λI + LK )r− 2 ,

and (47), we can derive JDj ,λ ≤ ADj ,λ (λI + LK,Dj )r I − ηG′+ (0)LK,Dj

T T

1 + (λI + LK,Dj )−(r− 2 ) (λI + LK )r− 2 3

QDj ,λ (λI + LK )r− 2 ∥uρ ∥ρ + A2Dj ,λ (λI + LK,Dj ) I − ηG′+ (0)LK,Dj 1 T r− 23 r ′ 2 1 + Ã ≤ ÃD (λI + L ) I − ηG (0)L K,Dj K,Dj + Dj ,λ ∥uρ ∥ρ j ,λ T 3 QDj ,λ (λI + LK )r− 2 ∥uρ ∥ρ , + ÃDj ,λ (λI + LK,Dj ) I − ηG′+ (0)LK,Dj 21

∥uρ ∥ρ

(52)

where the first inequality follows from the fact that 1 1 (λI + LK,Dj ) 2 (λI + LK )−1 − (λI + LK,Dj )−1 (λI + LK ) = (λI + LK,Dj )− 2 (LK,Dj − LK ). Putting (52) into (51), we have 1 T r−1 2 fT∗ +1,Dj − fρ ρ ≤ ÃD + Ã (λI + LK,Dj )r I − ηG′+ (0)LK,Dj ∥uρ ∥ρ Dj ,λ j ,λ T 3 (λI + LK )r− 2 ∥uρ ∥ρ + ÃDj ,λ QDj ,λ (λI + LK,Dj ) I − ηG′+ (0)LK,Dj 1 T 2 + ÃD (λI + LK,Dj )r I − ηG′+ (0)LK,Dj ∥uρ ∥ρ j ,λ +

T X

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

T −i

(53)

E∗ [Ei,Dj ,σ ] K .

i=1

Case 3. r > 25 . Now we have r − 32 > 1 and (47) cannot be adopted directly. Lemma A.6 in [34] states that for any two positive self-adjoint operators A, B on a Hilbert space satisfying ∥A∥ ≤ c and ∥B∥ ≤ c for some constant c > 0, there holds that for all s ≥ 1, ∥As − B s ∥ ≤ scs−1 ∥A − B∥. Recall that ∥LK ∥ ≤ κ2 and ∥LK,Dj ∥ ≤ κ2 . To estimate JDj ,λ in (51), we substitute A = λI + LK,Dj , B = λI + LK , and s = r − 23 into the above inequality to yield 1 T 3 3 2 JDj ,λ ≤ r − κ2r−5 ÃD ∥LK − LK,Dj ∥∥uρ ∥ρ (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj j ,λ 2 T 3 + ÃDj ,λ (λI + LK,Dj ) I − ηG′+ (0)LK,Dj QDj ,λ (λI + LK )r− 2 ∥uρ ∥ρ . By putting the above bound into (51), we have 1 T 3 3 ∗ 2 fT +1,Dj − fρ ρ ≤ r − κ2r−5 ÃD (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj ∥LK − LK,Dj ∥∥uρ ∥ρ j ,λ 2 T 3 (λI + LK )r− 2 ∥uρ ∥ρ + ÃDj ,λ QDj ,λ (λI + LK,Dj ) I − ηG′+ (0)LK,Dj 1 T 2 + ÃD ∥uρ ∥ρ (λI + LK,Dj )r I − ηG′+ (0)LK,Dj j ,λ +

T X

η (λI + LK ) 2 I − ηG′+ (0)LK,Dj 1

T −i

(54)

E∗ [Ei,Dj ,σ ] K .

i=1

Thus, we have completed the error decomposition of fT∗ +1,Dj − fρ ρ .

5.4

Error decomposition for DKRGD with communication In this subsection, we derive an error decomposition for DKRGD with communication based on (12). Firstly, we

adopt ft+1,D as an intermediate function to derive the following error decomposition f¯Tl +1,D − fρ ρ ≤ f¯Tl +1,D − fT +1,D ρ + ∥fT +1,D − fρ ∥ρ . The bound on ∥fT +1,D − fρ ∥ρ has been derived in [8] with the polynomial decay assumption on the eigenvalues of the integral operator LK , in contrast to which we present a more general bound adapted to the capacity assumption as

follows. By substituting Dj with D in (43), we can follow a proof strategy analogous to that of Proposition 5 to derive ∥fT +1,D − fρ ∥ρ ≤ (1 + ηG′+ (0)λT )A2D,λ (PD,λ + QD,λ ∥fρ ∥K ) +

T X

η (λI + LK,D ) 2 I − ηG′+ (0)LK,D 1

T −i

AD,λ ∥Ei,D,σ − Ei,σ ∥K

i=1

T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

i=1

r eηG′+ (0)

r ∥uρ ∥ρ T −r +

T X

T −i

A2D,λ QD,λ ∥fi − fρ ∥K

η (λI + LK ) 2 I − ηG′+ (0)LK 1

T −i

(55)

∥Ei,σ ∥K .

i=1

Next, we will derive the error decomposition for f¯Tl +1,D − fT +1,D ρ . Due to (7) and (12), we get T h i X T −i ˆK,D + fT +1,D − f¯Tl +1,D = − gT (LK,D ) gT−1 (LK,D )f¯Tl−1 − f Ei,D,σ η I − ηG′+ (0)LK,D +1,D

m X |Dj | j=1

−

m X |Dj | j=1

|D| +

|D| |D|

ˆ gT (LK,Dj ) gT−1 (LK,D )f¯Tl−1 +1,D − fK,D gT (LK,Dj )gT−1 (LK,D )

T X

η I − ηG′+ (0)LK,D

T −i

Ei,D,σ

i=1

gT (LK,Dj ) − gT (LK,D )

m X |Dj | j=1

i=1

|D|

i h −1 ˆK,D − f gT (LK,D )f¯Tl−1 +1,D

T X T −i −1 Ei,D,σ . η I − ηG′+ (0)LK,D gT (LK,D ) − gT (LK,Dj ) gT (LK,D ) i=1

¯l−1 In order to simplify the above decomposition and represent fT +1,D − f¯Tl +1,D by fT +1,D − f¯Tl−1 +1,D or fT +1,D − fT +1,D , we rewrite g −1 (LK,D )f¯l−1 − fˆK,D as T

T +1,D

h i ˆK,D = g −1 (LK,D ) f¯l−1 − gT (LK,D )fˆK,D gT−1 (LK,D )f¯Tl−1 − f +1,D T T +1,D h i ˆK,D = gT−1 (LK,D ) f¯Tl−1 − f + f − g (L ) f T +1,D T +1,D T K,D +1,D " # T X T −i −1 l−1 ′ = g (LK,D ) f¯ − fT +1,D + η I − ηG (0)LK,D Ei,D,σ , T

T +1,D

i=1

and further derive that fT +1,D − f¯Tl +1,D =

m X |Dj | j=1

|D|

gT (LK,Dj ) − gT (LK,D ) gT−1 (LK,D ) f¯Tl−1 +1,D − fT +1,D

m X |Dj | j=1

|D|

T X −1 T −i gT (LK,Dj ) − gT (LK,D ) gT (LK,D ) η I − ηG′+ (0)LK,D Ei,D,σ i=1

m X

T X T −i |Dj | + gT (LK,D ) − gT (LK,Dj ) gT−1 (LK,D ) η I − ηG′+ (0)LK,D Ei,D,σ |D| j=1 i=1

m X |Dj | j=1

|D|

gT (LK,Dj ) − gT (LK,D ) gT−1 (LK,D ) f¯Tl−1 +1,D − fT +1,D .

(56)

Note that it follows from the definition (9) of gT (·) that gT (LK,Dj ) − gT (LK,D ) =

T X

ηG′+ (0) I − ηG′+ (0)LK,Dj

T −i

−

i=1

T X

ηG′+ (0) I − ηG′+ (0)LK,D

T −i (57)

i=1

ηG′+ (0)

I − ηG′+ (0)LK,Dj

T −i

− I − ηG′+ (0)LK,D

T −i

i=1

T −i T −i − I − ηG′+ (0)LK,D To obtain a more refined estimate of fT +1,D − f¯Tl +1,D , we need to adjust I − ηG′+ (0)LK,Dj in (57). To this end, we first introduce the following property that for two operators X, Y and n ∈ N+ , there holds X n − Y n = X n − Y X n−1 + Y X n−1 − Y 2 X n−2 + · · · + Y n−1 X − Y n = (X − Y )X n−1 + Y (X − Y )X n−2 + · · · + Y n−1 (X − Y ) = ··· =

n X

Y k−1 (X − Y )X n−k .

k=1

By applying the above property to X = I − ηG′+ (0)LK,Dj , Y = I − ηG′+ (0)LK,D and n = T − i, we can deduce that I − ηG′+ (0)LK,Dj =

T −i X

T −i

− I − ηG′+ (0)LK,D

ηG′+ (0) I − ηG′+ (0)LK,D

k−1

T −i

LK,D − LK,Dj

I − ηG′+ (0)LK,Dj

T −i−k

k=1

T X

ηG′+ (0) I − ηG′+ (0)LK,D

k−i−1

LK,D − LK,Dj

I − ηG′+ (0)LK,Dj

T −k

k=i+1

gT (LK,Dj ) − gT (LK,D ) gT−1 (LK,D ) as follows

Based on the results above, we can obtain an estimate of

gt (LK,Dj ) − gt (LK,D ) gT−1 (LK,D ) = gT−1 (LK,D ) gt (LK,Dj ) − gt (LK,D ) = gT−1 (LK,D )

T X

ηG′+ (0)

I − ηG′+ (0)LK,Dj

T −i

− I − ηG′+ (0)LK,D

T −i

i=1

= gT−1 (LK,D )

T X

ηG′+ (0)

i=1

ηG′+ (0) I − ηG′+ (0)LK,D

k−i−1

(LK,D − LK,Dj ) I − ηG′+ (0)LK,Dj

T −k

k=i+1

where the first equality follows from the fact that gT (LK,Dj ) − gT (LK,D ) and gT−1 (LK,D ) are self-adjoint operators. Furthermore, we can interchange the order of summation to obtain gt (LK,Dj ) − gt (LK,D ) gT−1 (LK,D ) = ≤

T X

ηG′+ (0)gT−1 (LK,D )

k−1 X

k=2

i=1

T X

k−1 X

ηG′+ (0) gT−1 (LK,D )

≤

k=2

≤

T X

k−i−1

ηG′+ (0) I − ηG′+ (0)LK,D

(LK,D − LK,Dj ) I − ηG′+ (0)LK,Dj

k−i−1

T −k

(LK,D − LK,Dj ) I − ηG′+ (0)LK,Dj

T −k

i=1

k=2 T X

ηG′+ (0) I − ηG′+ (0)LK,D

ηG′+ (0) gT−1 (LK,D )

k−1 X

ηG′+ (0) I − ηG′+ (0)LK,D

k−i−1

i=1

ηG′+ (0) (LK,D − LK,Dj ) I − ηG′+ (0)LK,Dj

T −k

k=2

(LK,D − LK,Dj ) I − ηG′+ (0)LK,Dj

T −k

where the last inequality follows from the fact that for any 2 ≤ k ≤ T , gT−1 (LK,D )

k−1 X

ηG′+ (0) I − ηG′+ (0)LK,D

k−i−1

≤ 1.

i=1

Since LK,D − LK,Dj can be decomposed as LK,D − LK + LK − LK,Dj , we see gt (LK,Dj ) − gt (LK,D ) gT−1 (LK,D ) ≤

T X

ηG′+ (0) (LK,D − LK )(λI + LK )− 2

(λI + LK ) 2 (λI + LK,Dj )− 2

(λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj

T −i

i=1

T X

(λI + LK ) 2 (λI + LK,Dj )− 2

ηG′+ (0) (LK − LK,Dj )(λI + LK )− 2

(λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj

T −i

i=1

=(QD,λ + QDj ,λ )ADj ,λ

T X

ηG′+ (0) (λI + LK,Dj ) 2 I − ηG′+ (0)LK,Dj 1

T −i

(58)

i=1

Finally, it can be derived by combining (56) and (58) that fT +1,D − f¯Tl +1,D ρ ≤ ≤ ≤

(m X |Dj | |D| j=1

m X |Dj |

|D| j=1

(QD,λ + QDj ,λ )ADj ,λ

gT (LK,Dj ) − gT (LK,D ) gT−1 (LK,D ) T X

ηG′+ (0)

(λI + LK,Dj )

f¯Tl−1 +1,D − fT +1,D ρ

1 2

T −i I − ηG′+ (0)LK,Dj

1 2

T −i I − ηG′+ (0)LK,Dj

i=1

(QD,λ + QDj ,λ )ADj ,λ

T X

ηG′+ (0)

(λI + LK,Dj )

) f¯Tl−1 +1,D − fT +1,D ρ

(59)

)l f¯T0 +1,D − fT +1,D ρ .

i=1

Recall that f¯T0 +1,D = f¯T +1,D . This decomposes the bound on fT +1,D − f¯Tl +1,D ρ into the product of an operator norm depending on l and the term f¯T +1,D − fT +1,D . The latter can be further bounded via Proposition 2. Finally, the ρ

error decomposition for ∥fT +1,D − fρ ∥ρ is completed by combining (55) and (59).

Proofs of Main Results In this section, we present the proofs of the main results in Section 3. To this end, we need to introduce some

preliminary estimates on the quantities defined in Section 5, which are demonstrated in the following lemmas.

6.1

Preliminary Lemmas |D|

Lemma 4. Let {zi = (xi , yi )}i=1 be drawn independently according to ρ and 0 < δ < 1. Under Assumption 1, each of the following estimates holds with confidence at least 1 − δ:

B|D|,λ 2 √ + 1 log , ≤ AD,λ = (λI + LK ) (λI + LK,D ) δ λ 2 2 B|D|,λ 2 √ +1 log ÃD,λ = (λI + LK )(λI + LK,D )−1 ≤ , δ λ 2 1 ≤ B|D|,λ log , PD,λ = (λI + LK )− 2 (fˆK,D − LK fρ ) δ K 2 1 QD,λ = (λI + LK )− 2 (LK − LK,D ) ≤ B|D|,λ log , δ 4κ2 2 ∥LK − LK,D ∥ ≤ ∥LK − LK,D ∥HS ≤ p log , δ |D| − 12

1 2

(60) (61) (62) (63) (64)

where B|D|,λ =

√2κ |D|

√κ + |D|λ

N (λ)

and ∥ · ∥HS denotes the norm of HS(HK ), the Hilbert space of all Hilbert-

Schmidt operators on HK . The aforementioned bounds are well-established in the literature. Specifically, the proofs for (60), (63), and (64) follow from [2, 22, 35], while (61) and (62) can be found in [3] and [22], respectively. It is crucial to note that the high-probability bounds in Lemma 4 do not hold simultaneously. Consequently, we must invoke the union bound in the subsequent analysis to control the overall failure probability. This necessity is reflected in the accumulation of constants within the logarithmic terms of the final error bound. By leveraging a new concentration inequality for self-adjoint operators in [20], the following bound on RD,λ in Proposition 2 are proved in [5], which contributes to loosening the restriction on the number of local machines m. Lemma 5. Let 0 < δ ≤ 1, if 0 < λ ≤ 1 and N (λ) > 1, then there holds with confidence at least 1 − δ that RD,λ =∥(λI + LK )− 2 (LK − LK,D )(λI + LK )− 2 ∥ s ) 2 ( κ +1 √ 2 1 + log N (λ) 4 1 + log N (λ) ≤ max ,2 κ + 1 + log 3 λ|D| λ|D| δ 1

4 =:R|D|,λ log . δ Furthermore, leveraging Lemma 5, we refine the bound on AD,λ in (60) as follows. Lemma 6. Let 0 < δ ≤ 1, if 0 < λ ≤ 1 and N (λ) > 1, then there holds with confidence at least 1 − δ that ! 12 2 2 2 B 8 8 |D|,λ 2 √ + 1 + R|D|,λ AD,λ ≤ 1 + R|D|,λ log =: A|D|,λ log . δ δ λ Proof. To derive a tighter upper bound for AD,λ than (60), consider i 12 h 1 1 1 1 AD,λ = (λI + LK ) 2 (λI + LK,D )− 2 = (λI + LK ) 2 (λI + LK,D )−1 (λI + LK ) 2 1 2

≤ (λI + LK ) (λI + LK,D )

−1

(λI + LK )

1 2

(65) ,

then we only need to estimate (λI + LK ) 2 (λI + LK,D )−1 (λI + LK ) 2 . 1

It is derived by Lemma 16 in [2] that for any two invertible operators A and B on a Banach space, there holds A−1 − B −1 = B −1 (B − A)B −1 (B − A)A−1 + B −1 (B − A)B −1 . With the above second order decomposition of inverse operator difference, we have 1 1 1 1 1 1 1 1 B 2 A−1 B 2 = B 2 A−1 − B −1 + B −1 B 2 = B − 2 (B − A)B −1 (B − A)A−1 B 2 + B − 2 (B − A)B − 2 + I. Inserting A = λI + LK,D and B = λI + LK into (66), we obtain (λI + LK ) 2 (λI + LK,D )−1 (λI + LK ) 2 = (λI + LK )− 2 (LK − LK,D )(λI + LK )−1 (LK − LK,D )(λI + LK,D )−1 · 1

(λI + LK ) 2 + (λI + LK )− 2 (LK − LK,D )(λI + LK )− 2 + I, 1

and further derive that (λI + LK ) 2 (λI + LK,D )−1 (λI + LK ) 2 1

≤ (λI + LK )− 2 (LK − LK,D )(λI + LK )− 2 (λI + LK )− 2 (LK − LK,D )(λI + LK )− 2 (λI + LK ) 2 (λI + LK,D )−1 · 1

(λI + LK ) 2 + (λI + LK )− 2 (LK − LK,D )(λI + LK )− 2 + I 1

≤1 + R2D,λ A2D,λ + RD,λ . 26

(66)

Then for 0 < δ < 1, by Lemma 4 and Lemma 5 and scaling 2δ to δ, there holds with confidence at least 1−δ that 2 2 2 B|D|,λ 8 4 8 1 1 −1 2 2 2 √ (λI + LK ) (λI + LK,D ) (λI + LK ) ≤ 1 + R|D|,λ log + R|D|,λ log +1 log δ δ δ λ ! (67) 2 4 B|D|,λ 8 2 √ + 1 + R|D|,λ ≤ 1 + R|D|,λ log . δ λ Finally, the proof of Lemma 6 is completed by substituting (67) into (65). To derive explicit learning rates based on Proposition 4, it is essential to first estimate the operator norms appearing T −i T −i in the upper bounds, specifically for I − ηG′+ (0)LK and I − ηG′+ (0)LK,D . These estimates are provided in the following two lemmas. Lemma 7. For any integer T ≥ 3 and 0 < λ ≤ 1, we have T X

ηG′+ (0) (λI + LK,D ) 2 I − ηG′+ (0)LK,D 1

1 1 ≤ Cη′ λ 2 T + T 2 ,

T −i

(68)

i=1

and

T X

ηG′+ (0)

(λI + LK,D )

T −i I − ηG′+ (0)LK,D

≤ 2ηG′+ (0)λT +

4 2ηG′+ (0)κ2 +

√

log T,

i=1

where Cη′ =

(69)

√ ηG′+ (0) 12 2η(1 + κ)G′+ (0) + 2 2 . The same bounds hold with LK,D replaced by LK . e

Proof. By setting θ = 0 and η1 = η, Equation (21) in [8, Prop. 4.2] implies that for any τ, λ > 0 and 1 ⩽ i < T , there holds (λI + LK,D )

T −i I − ηG′+ (0)LK,D

≤2

λ +

τ eG′+ (0)

(η(T − i))

−τ

(70)

To derive the first inequality in Lemma 7, we can set τ = 12 in the above inequality to obtain ! 12 T −1 T −1 T −1 X X X √ T −i 1 1 1 1 ′ ′ − ′ λ2 + (η(T − i)) 2 . ηG+ (0) (λI + LK,D ) 2 I − ηG+ (0)LK,D ≤ 2ηG+ (0) eG′+ (0) i=1 i=1 i=1 Since

T −1 X

(T − i)− 2 = 1

i=1

we have

T −1 X

ηG′+ (0)

(λI + LK,D )

T −1 X

i− 2 ≤ 1 + 1

Z T −1

i=1

1 2

x− 2 dx ≤ 2T 2 ,

T −i I − ηG′+ (0)LK,D

≤

i=1

This together with the fact that (λI + LK,D ) 2 I − ηG′+ (0)LK,D 1

√

1 2ηG′+ (0)λ 2 T + 2

√

ηG′+ (0) e

= (λI + LK,D ) 2 ≤ (λ + κ2 ) 2 ⩽ 1

the proof of the first inequality in Lemma 7. By setting τ = 1 in (70), we can derive that T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

T −i

i=1

≤ ηG′+ (0) ∥λI + LK,D ∥ + 2ηG′+ (0)

T −1 X

λ+

i=1

≤ 2ηG′+ (0)κ2 + 2ηG′+ (0)λT +

T −1 X

i=1

eG′+ (0)

(η(T − i))−1

T −1 X

2 (T − i)−1 e i=1

4 ≤ 2ηG′+ (0)κ2 + 2ηG′+ (0)λT + log T ≤ 2ηG′+ (0)λT + e

4 2ηG′+ (0)κ2 + e

T 2.

log T,

√

2κ completes

which completes the proof of the second inequality in Lemma 7. Finally, the same bounds apply to the population operator LK , as the preceding derivations rely solely on the operator being positive, compact, and satisfying ∥ · ∥ ≤ κ2 , common to both operators. Lemma 8. For any integer T ≥ 3, 0 < λ ≤ 1 and r ≥ 12 , we have T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

i=1

≤

2 ηG′+ (0)(1 + κ2 ) + (2ηG′+ (0) + )Cr,1

T −i

i−(r− 2 ) 1

max λT

−(r− 32 )

log T, λ, T

−(r− 21 )

log T, T

−1

(71)

o ,

where Cr,1 is a constant given by (73). The same bound holds with LK,D replaced by LK . Proof. From (70) with τ = 1, we get for every 1 ≤ i < T ,

(λI + LK,D )(I − ηG′+ (0)LK,D )T −i

1 ≤2 λ+ ′ e G+ (0) η (T − i)

For the index i = T , we have ηG′+ (0)∥λI + LK,D ∥T −(r− 2 ) ≤ ηG′+ (0)(λ + κ2 )T −(r− 2 ) and thus 1

T X

ηG′+ (0) (λI + LK,D )(I − ηG′+ (0)LK,D )T −i i−(r− 2 ) 1

i=1

≤ ηG′+ (0)(λ + κ2 )T

−(r− 21 )

+ 2ηG′+ (0)λ

T −1 X

−(r− 12 )

i=1

2 X i−(r− 2 ) + . e i=1 T − i T −1

(72)

The bound for the first sum follows immediately from Lemma A.1 in [7] that  −(r− 3 ) 2 2T   , 12 < r < 23 ,  3−2r T −1  X 1 i−(r− 2 ) ≤ 2 log T, r = 32 ,   i=1   2r−1 , r > 32 . 2r−3 To bound

PT −1 i=1

(T − i)

−1 −(r− 1 ) 2

, notice that when 1 ≤ i ≤ T2 ,

(T − i)

−1 −(r− 12 )

≤ 2T −1

1≤i≤ T2

and for T2 < i ≤ T − 1, X

i−(r− 2 ) ≤

1≤i≤ T2

(T − i)

−1 −(r− 12 )

≤ 2r− 2 T −(r− 2 ) 1

T 2 <i≤T −1

Therefore, we have

 −(r− 1 ) 2 4T   ,   3−2r

1 ≤ r < 32 , 2

4T −1 log T, r = 32 ,     2(2r−1) T −1 , r > 3 , 2r−3 2

(T − i)

−1

≤ 2r− 2 T −(r− 2 ) log T. 1

T 2 <i≤T −1

T −1 X

(T − i)

−1 −(r− 12 )

o n 1 ≤ Cr,1 max T −(r− 2 ) log T, T −1 ,

i=1

where Cr,1 is a constant given by

 1 4   + 2r− 2 ,  3−2r  Cr,1 =

6,     2(2r−1) + 2r− 12 , 2r−3

1 ≤ r < 23 , 2

r = 32 , r > 32 .

(73)

To ensure consistency in the constant factors across our theoretical results, we alternatively derive T −1 X

n o 1 3 i−(r− 2 ) ≤ Cr,1 max T −(r− 2 ) log T, 1 .

i=1

Finally, putting the bound on each sum term into (72), we have T X

ηG′+ (0) (λI + LK,D ) I − ηG′+ (0)LK,D

T −i

i−(r− 2 ) 1

i=1

n o 2 o n 1 3 1 ≤ηG′+ (0)(λ + κ2 )T −(r− 2 ) + 2ηG′+ (0)Cr,1 max λT −(r− 2 ) log T, λ + Cr,1 max T −(r− 2 ) log T, T −1 e n o 2 1 ′ 2 ′ −(r− 32 ) ≤ ηG+ (0)(1 + κ ) + 2ηG+ (0)Cr,1 + Cr,1 max λT log T, λ, T −(r− 2 ) log T, T −1 , e which completes the proof of Lemma 8. In the end of this subsection, we aim at estimating Et,σ , E∗ [Et,D,σ ] and the difference between Et,D,σ and Et,σ , respectively. Lemma 9. Under Assumption 1, we have that for any 1 ≤ t ≤ T , p+ 2 κcp (M + κ∥ft ∥K )2p+1 2p+1 t ≤ κc (2M ) , p σ 2p σ 2p 1

∥Et,σ ∥K ≤

∗

∥E [Et,D,σ ]∥K ≤ κcp (2M )

2p+1 t

∥Et,D,σ − Et,σ ∥K ≤ 2κcp (2M ) Proof. Recall that Et,σ =

R Z

(74)

p+ 12

σ 2p 2p+1 t

(75)

p+ 12

σ 2p

(76)

2 G′+ (0) − G′ (ξt,σ (z)) (ft (x) − y) Kx dρ and ξt,σ (z) = (y−fσt2(x)) . Since Et,σ is the expecta-

tion of Et,D,σ with respect to the data D, it follows that Z κcp (M + κ∥ft ∥K )2p+1 ∥Et,σ ∥K ≤ , G′+ (0) − G′ (ξt,σ (z)) |y − ft (x)| ∥Kx ∥K dρ ≤ σ 2p Z where the last inequality is due to condition (2) of the function G. Combining the above inequality with the bound on ∥ft ∥K in Lemma 1 yields (74). The uniform bound on Et,D,σ defined in (6) has been established in [8, Proposition 5.1], based on which we can further set η1 = η and θ = 0 to derive that p+ 2 κcp (M + κ∥ft,D ∥K )2p+1 2p+1 t ∥Et,D,σ ∥K ≤ ≤ κc (2M ) . p σ 2p σ 2p 1

Then (76) can be proved by the triangle inequality ∥Et,D,σ − Et,σ ∥K ≤ ∥Et,D,σ ∥K + ∥Et,σ ∥K . Finally, (75) follows from the Jensen’s inequality for conditional expectation and the bound on ∥Et,D,σ ∥K . This completes the proof of Lemma 9.

6.2

Proof of Theorem 1 We now proceed to prove Theorem 1 by leveraging the error decomposition in Proposition 4. Specifically, we

bound each term on the right-hand side of (41) individually, and aggregate these estimates to obtain the desired learning rates.

For the first term of (41), combining Assumption 2, (62) and (63) in Lemma 4 yields that with confidence at least 1 − δ, there holds

4 PD,λ + QD,λ ∥fρ ∥K ≤ 1 + κ2r−1 ∥uρ ∥ρ B|D|,λ log . (77) δ We then turn to estimate the second and third terms. Lemma 9 provides a uniform bound for ∥Et,D,σ − Et,σ ∥K

for any t ∈ {1, . . . , T }. Note that T = ⌈λ−1 ⌉ ∈ N, we have 1 ≤ λT < 2. By combining Lemma 7 and substituting D with Dj in Lemma 9, we have T X

η (λI + LK ) 2 I − ηG′+ (0)LK 1

i=1

≤ max

T X

1≤j≤m

m T −i X |Dj | Ei,Dj ,σ − Ei,σ K |D| j=1

η (λI + LK ) 2 I − ηG′+ (0)LK 1

i=1 ′ p+ 12 Cη 1 1 2p+1 T 2 2 ≤ ′ λ T +T 2κcp (2M ) G+ (0) σ 2p 5

C′

where Cr,2 := 2 2 G′ η(0) κcp (2M )

2p+1

T −i

(78)

Ei,Dj ,σ − Ei,σ K

= Cr,2

T p+1 , σ 2p

is a constant independent of T , λ and σ. Moreover, by (70) with τ = 1, we have

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

i=1

≤2ηG′+ (0) λ +

1 e G′+ (0) η (T − 1)

T −i

∥fi − fρ ∥K

κ2r−1 ∥uρ ∥ρ +

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

∥fi − fρ ∥K .

i=2

From (38), Lemma 7 and Lemma 8, there holds T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

i=2

≤

T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

i=2

∥fi − fρ ∥K "

r − 12 eηG′+ (0)

r− 12 ∥uρ ∥ρ (i − 1)

−(r− 21 )

i−1 X

# η∥El,σ ∥K

l=1

r− 12 n o r − 12 2 −(r− 32 ) ′ 2 ′ −(r− 12 ) −1 ≤ )C max λT ∥u ∥ ηG (0)(1 + κ ) + (2ηG (0) + log T, λ, T log T, T r,1 ρ ρ + + eηG′+ (0) e p+ 32 4 2p+1 T ′ ′ 2 log T ηκcp (2M ) . + 2ηG+ (0)λT + 2ηG+ (0)κ + e σ 2p Therefore, we obtain that T X

ηG′+ (0) (λI + LK ) I − ηG′+ (0)LK

T −i

( ∥fi − fρ ∥K ≤ Cr,3 max T

i=1

where Cr,3 := 2

r− 21 eηG′+ (0)

r− 12

−(r− 12 )

T p+ 2 log T log T, T −1 , σ 2p

) .

(79)

2p+1 ∥uρ ∥ρ ηG′+ (0)(1 + κ2 + 2Cr,1 ) + 2Cer,1 + 2ηG′+ (0)(1 + κ2 ) + 4e ηκcp (2M ) .

For any fixed j ∈ {1, . . . , m}, by applying Lemma 4-6 with D replaced by Dj , we can derive that with confidence δ at least 1− m , there holds

RDj ,λ A2Dj ,λ

PDj ,λ + QDj ,λ ∥fρ ∥K ≤ 1 + κ

2r−1

∥uρ ∥ρ

R|Dj |,λ B|Dj |,λ A2|Dj |,λ

16m log δ

6 .

Since Lemma 7 and Lemma 8 also hold with LK replaced by LK,D , we have the same bound in (78) and (79) when LK is replaced by LK,D . Therefore, combining (78), (79) and the above result, we can derive that with confidence at 30

δ least 1− m , there holds

KDj ,λ ≤

4ηG′+ (0) + 2ηG′+ (0)κ2 + 4/e

log T ·

1 + 2ηG′+ (0)

1+κ

2r−1

∥uρ ∥ρ

R|Dj |,λ B|Dj |,λ A2|Dj |,λ

16m log δ

3 T p+1 16m + log T · Cr,2 2p R|Dj |,λ A|Dj |,λ log σ δ ( ) 6 p+ 32 T log T 16m 1 Cr,3 max T −(r− 2 ) log T, T −1 , + 4ηG′+ (0) + 2ηG′+ (0)κ2 + 4/e log T · R|Dj |,λ B|Dj |,λ A2|Dj |,λ log δ σ 2p 3 T p+1 16m ′ ≤ Cr,2 R|Dj |,λ A|Dj |,λ 2p log T log σ δ ) ( 6 p+ 32 (log T )2 16m ′ 2 −(r− 12 ) 2 T . + Cr,3 R|Dj |,λ B|Dj |,λ A|Dj |,λ max log T, T (log T ) , log σ 2p δ ′ ′ where Cr,2 := 4ηG′+ (0) + 2ηG′+ (0)κ2 + 4/e Cr,2 and Cr,3 := 4ηG′+ (0) + 2ηG′+ (0)κ2 + 4/e 1 + 2ηG′+ (0) (1 + κ2r−1 · ∥uρ ∥ρ ) + 4ηG′+ (0) + 2ηG′+ (0)κ2 + 4/e Cr,3 . 4ηG′+ (0) + 2ηG′+ (0)κ2 + 4/e

Plugging the above estimates into (41), with confidence at least 1−δ, we have r 12 r f¯T +1,D − fρ ρ ≤ (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ )B|D|,λ log + ∥uρ ∥ρ T −r δ eηG′+ (0) ( ) p+ 32 3Cr,2 T p+1 log T 6 −(r− 21 ) −1 T + + Cr,3 B|D|,λ max T log T, T , log 2 σ 2p σ 2p δ (80) 3 T p+1 48m ′ + Cr,2 max R|Dj |,λ A|Dj |,λ log T log 1≤j≤m σ 2p δ ) ( 6 n o p+ 23 48m (log T )2 ′ 2 T 2 −(r− 21 ) log + Cr,3 max R|Dj |,λ B|Dj |,λ A|Dj |,λ max log T, T (log T ) , . 1≤j≤m σ 2p δ Note that the condition on m in (16) implies √ 4r+2s−1 r m|D|− 4r+2s ≤ m|D|− 2r+s

m|D|− 2r+s ≤ 2r+s−1

and

√

m|D|− 4r+2s . 2r+s−1

(81)

Let λ = |D|− 2r+s , then we can adopt Assumption 3 and |D1 | = · · · = |Dm | to obtain that p 4r+2s−1 r r B|D|,λ ≤ 2κ κ|D|− 4r+2s + C0 |D|− 2r+s ≤ C0,1 |D|− 2r+s , 1

and for any j ∈ {1, . . . , m},

p √ 4r+2s−1 r r B|Dj |,λ ≤ 2κ κm|D|− 4r+2s + C0 m|D|− 2r+s ≤ C0,1 m|D|− 2r+s , ) r 2 ( 2r+s−1 2r+s−1 κ +1 √ 2 2s 2s R|Dj |,λ ≤ max ,2 κ + 1 m|D|− 2r+s log |D| + m|D|− 2r+s log |D| 3 2r + s 2r + s √ 2r+s−1 ≤ C0,2 m|D|− 4r+2s log |D|, n 2 oq √ √ 2s where C0,1 := 2κ(κ + C0 ), and C0,2 = 2 max κ 3+1 , 2 κ2 + 1 . 2r+s Additionally, by leveraging the above results, we can derive the following bound for A|D|,λ : A2|Dj |,λ = 1 +

2 R2|Dj |,λ B|D j |,λ

R2|Dj |,λ B|Dj |,λ √ + R2|Dj |,λ + R|Dj |,λ λ 3r+s− 3 2

2 2 2 ≤ 1 + C0,1 C0,2 m2 |D|− 2r+s (log |D|) + 2C0,1 C0,2 m 2 |D|− 2r+s (log |D|) √ 2r+s−1 2r+s−1 2 2 + C0,2 m|D|− 2r+s (log |D|) + C0,2 m|D|− 4r+2s log |D| 4r+s−2

≤ C0,3 + 1. 31

2 2 2 2 where C0,3 = C0,1 C0,2 + 2C0,1 C0,2 + C0,2 + C0,2 and the last inequality follows from l m the condition on m in (16).

Finally, putting the aforementioned results, λ = |D|− 2r+s and T = |D| 2r+s 1

into (80), we can derive that, with

confidence at least 1−δ, there holds r r 12 r ′ 2r−1 ¯ fT +1,D − fρ ρ ≤ C0,1 (1 + 2ηG+ (0))(1 + κ ∥uρ ∥ρ ) + ∥uρ ∥ρ |D|− 2r+s log ′ eηG+ (0) δ   p+ 3 p+1 2   r− 1 2r+s 2r+s log |D| |D| |D| 6 r 1 3 2 − 2r+s − 2r+s − 2r+s p+ 2 + 3 · 2p Cr,2 C C |D| max |D| log |D|, |D| , log + 2 r,3 0,1 2p 2p   σ σ δ 1 ′ Cr,2 (C0,3 + 1) 2 C0,2

√

2 |D|

− 2r+s−1 4r+2s

p+1 2r+s

48m log δ

(log |D|) σ 2p   p+ 3 6 2 3  1 r− 2r+s (log |D|) 48m 2 − 4r+s−1 − 2r+s p+ 32 ′ 2 3 |D| 4r+2s max (log |D|) , |D| (log |D|) , log Cr,3 C0,1 C0,2 (C0,3 + 1)m|D| +2 .   σ 2p δ +2

p+1

Note that log6

m|D|

48m 48 48 ≤ 26 log6 + log6 m ≤ 26 log6 log6 |D| + 1 , δ δ δ r− 1

2 and D−α log |D| = α−1 D−α log |D|α ≤ α−1 with α = 2r+s . Since r > 12 , by combining the condition on m in (16), we

have with confidence at least 1−δ, (

p+1

f¯T +1,D − fρ ρ ≤ C̃1 max |D| where C̃1 := C0,1 (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ ) +

r eηG′+ (0)

r − 2r+s

|D| 2r+s , σ 2p

) log

48 δ

6 ,

′ ∥uρ ∥ρ + 3 · 2p Cr,2 + 2p+ 2 Cr,3 C0,1 4r+2s + 2p+5 Cr,2 (C0,3 + 2r−1 3

′ 1) 2 C0,2 + 2p+ 2 Cr,3 C0,1 C0,2 (C0,3 + 1) 4r+2s . This completes the proof of Theorem 1. 2r−1 1

6.3

Proof of Theorem 2 In this subsection, we aim to derive the explicit learning rates in expectation for the DKRGD based on the error

decomposition in Subsection 5.3. To achieve this, we first establish the error bounds in probability for fT +1,Dj − fρ ρ and fT∗ +1,Dj − fρ

for each j ∈ {1, . . . , m}, and then obtain their expected error bounds by leveraging the formula E[ξ] =

Z ∞ Prob(ξ > t)dt,

(82)

for nonnegative random variables ξ. 2 For the nonnegative random variable ξ = f¯T +1,D − fρ ρ , (17) in Theorem 1 immediately yields that, for any u 2 p+1 r 2r+s 12 satisfying u ≥ C̃12 (log 48) max |D|− 2r+s , |D|σ2p , there holds

Prob(ξ > u) = Prob(

ξ>

√

  ( )− 61 p+1  − 16  2r+s |D| r 1 12 u) ≤ 48 exp − C̃1 max |D|− 2r+s , u .   σ 2p

Then applying the formula E[ξ] = 2 E[ f¯T +1,D − fρ ρ ] ( 12

r − 2r+s

(

=C̃12 (log 48)

Prob(ξ > t)dt to ξ, we have

p+1

≤C̃12 (log 48) max |D|

12 =C̃12 (log 48) max

R∞

|D| 2r+s , σ 2p p+1

|D|

r − 2r+s

|D| 2r+s , σ 2p (

+ 576Γ(12) max |D|

Z ∞ exp

+ 48 0

  

( −(C̃1 )

− 61

( + 576C̃12 max 2p+2

2r − 2r+s

|D| 2r+s , σ 4p

max |D| p+1

|D|

r − 2r+s

)

p+1

|D| 2r+s , σ 2p

r − 2r+s

)2 Z

|D| 2r+s , σ 2p

∞

)− 61 u

1 12

  

du (83)

11 −t

t e dt 0

We now turn to estimate the term fT +1,Dj − fρ ρ . By substituting the bounds in Lemma 4 and Lemma 6 into Proposition 5 and employing the intermediate results in proving Theorem 1, we can derive that with confidence at least 1−3δ, there holds 5 8 fT +1,Dj − fρ ρ ≤ (1 + ηG′+ (0)λT )(1 + κ2r−1 ∥uρ ∥ρ )A2|Dj |,λ B|Dj |,λ log δ p+1 2 r 1 T r 8 + Cr,2 A|Dj |,λ + log + ∥uρ ∥ρ T −r 2p 2 σ δ eηG′+ (0) ( ) 5 p+ 32 8 log T 2 −(r− 21 ) −1 T + Cr,3 A|Dj |,λ B|Dj |,λ max T log T, T , log . σ 2p δ

(84)

Since the condition on m in (18) also implies (81), we can adopt the bounds on B|Dj |,λ , R|Dj |,λ and A|Dj |,λ mentioned in the proof of Theorem 1 to further derive explicit rate in probability for fT +1,Dj − fρ ρ . Since λ = |D|− 2r+s and l m 1 T = |D| 2r+s , scaling 3δ to δ yields that with confidence at least 1−δ, there holds 1

(

T p+1 T p+ 2 log T fT +1,Dj − fρ ρ ≤ C̃r,2 max B|Dj |,λ , 2p , λr , B|Dj |,λ σ σ 2p where C̃r,2 :=

)

24 log δ

5 ,

r r,3 (C0,3 + 1) + eηGr′ (0) ∥uρ ∥ρ . Then, we can easily (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ ) + 32 Cr,2 + 2C 2r−1 +

apply (82) to obtain that for any j ∈ {1, . . . , m}, )2 ( h i p+1 p+ 23 T T log T 2 10 2 max B|Dj |,λ , 2p , λr , B|Dj |,λ E fT +1,Dj − fρ ρ ≤ C̃r,2 (log 24) 2p σ σ   ( )− 15 Z ∞   p+ 32 p+1 T T log T 1 1 10 u du + 24 exp −(C̃r,2 )− 5 max B|Dj |,λ , 2p , λr , B|Dj |,λ   σ σ 2p 0 ( )2 h i p+1 p+ 32 log T T T 10 2 = C̃r,2 (log 24) + 240Γ(10) max B|Dj |,λ , 2p , λr , B|Dj |,λ . σ σ 2p In the following, we will estimate the term

fT∗ +1,Dj − fρ

for each j ∈ {1, . . . , m} by applying the derived

ρ decomposition of fT∗ +1,Dj − fρ for different cases of r in Subsection 5.3.

By invoking Equation (22) in [8, Prop. 4.2]

under the constant step size η, we obtain that for any τ, λ > 0, there holds (λI + LK,D )τ I − ηG′+ (0)LK,D

= Cτ λτ + T −τ .

h τ i where Cτ := 2τ 1 + eG′τ (0) η −τ . For brevity, we denote Cr := Cτ |τ =r . +

(85)

For the regime 21 < r ≤ 1, by substituting the corresponding estimates in Lemma 6, Lemma 7 and Lemma 9 into (46), we obtain that with confidence at least 1 − δ, fT∗ +1,Dj − fρ

≤ Cr λ + T r

−r

A2r |Dj |,λ

8 log δ

p+ 2 Cη′ 1 1 2p+1 T ∥uρ ∥ρ + ′ λ 2 T + T 2 κcp (2M ) . G+ (0) σ 2p 1

l m 1 1 For λ = |D|− 2r+s and T = |D| 2r+s , combining the partition size m specified in (18) and the bound on A|Dj |,λ , the preceding inequality simplifies to the following high-probability guarantee: 4r p+1 8 ∗ r T fT +1,Dj − fρ ≤ Cr,4 max λ , 2p log , σ δ ρ √ C′ 2p+1 where Cr,4 := 2Cr (C0,3 + 1)r ∥uρ ∥ρ + G′ η(0) ( 2 + 1)κcp (2M ) . Finally, applying the tail-expectation identity (82) +

fT∗ +1,Dj − fρ

to the random variable ξ =

yields the expected error bound ρ

fT∗ +1,Dj − fρ

T p+1 ≤ Cr,4 (log 8)4r + 32rΓ(4r) max λr , 2p . σ

For 1 < r ≤ 23 , combining (48), Lemma 4, Lemma 7 and Lemma 9, it follows that with confidence at least 1 − δ, 2r 2r p+ 12 Cη′ 1 B|Dj |,λ 2 1 2p+1 T 2 2 √ κcp (2M ) ≤ Cr λ + T +1 log ∥uρ ∥ρ + ′ λ T +T . δ G+ (0) σ 2p ρ λ m l 1 1 Note that λ = |D|− 2r+s and T = |D| 2r+s . When r > 1 and m satisfies (18), we have fT∗ +1,Dj − fρ

−r

r− 1 √ B|Dj |,λ 2 √ + 1 ≤ C0,1 m|D|− 2r+s + 1 ≤ C0,1 + 1. λ

Then, we have that with confidence at least 1−δ, there holds 2r p+1 2 ∗ r T log . fT +1,Dj − fρ ≤ Cr,5 max λ , 2p σ δ ρ √ C′ 2p+1 where Cr,5 := 2Cr (C0,1 + 1)2r ∥uρ ∥ρ + G′ η(0) ( 2 + 1)κcp (2M ) . Further, we can also derive the expected error bound +

fT∗ +1,Dj − fρ

T p+1 ≤ Cr,5 (log 2)2r + 4rΓ(2r) max λr , 2p . σ

For the case of 23 < r ≤ 52 , putting the estimates in Lemma 4, Lemma 7 and Lemma 9 into (53) yields that with confidence at least 1 − δ,

2r−3 ! 3 B|Dj |,λ B|Dj |,λ 4 √ √ λ +T ∥uρ ∥ρ +1 1+ +1 log δ λ λ 2 3 B|Dj |,λ 4 √ + C1 λ + T −1 ∥uρ ∥ρ (1 + κ2 ) + 1 B|Dj |,λ log δ λ ′ p+ 12 B|Dj |,λ Cη 4 1 1 2p+1 T r −r 2 2 √ + Cr λ + T + 1 ∥uρ ∥ρ log + ′ λ T +T κcp (2M ) . δ G+ (0) σ 2p λ m l 1 1 Analogously, for λ = |D|− 2r+s and T = |D| 2r+s , we have that with confidence at least 1−δ, fT∗ +1,Dj − fρ ρ ≤ Cr

−r

fT∗ +1,Dj − fρ ρ ≤ Cr,6 max

T p+1 λ , λB|Dj |,λ , 2p σ r

4 log δ

3 .

√ C′ 2p+1 where Cr,6 := 6Cr ∥uρ ∥ρ (C0,1 + 1)2r−2 + 2C1 ∥uρ ∥ρ (1 + κ2 )(C0,1 + 1)2 + G′ η(0) ( 2 + 1)κcp (2M ) . Then it can be +

easily derived that E

fT∗ +1,Dj − fρ ρ

T p+1 ≤ Cr,6 (log 4) + 12Γ(3) max λ , λB|Dj |,λ , 2p σ 3

When r > 52 , by (54), Lemma 4, Lemma 7 and Lemma 9, with confidence at least 1 − δ, there holds fT∗ +1,Dj − fρ ρ ≤

2 3 4κ2 B|Dj |,λ 6 − 32 2 p √ κ C 32 λ + T ∥uρ ∥ρ +1 log δ |Dj | λ 3 2 B|Dj |,λ 6 2 r− 32 −1 √ ∥uρ ∥ρ λ + T + C1 (1 + κ ) + 1 B|Dj |,λ log δ λ ′ p+ 12 B|Dj |,λ Cη 6 1 1 2p+1 T r −r 2 2 √ + Cr λ + T + 1 ∥uρ ∥ρ log + ′ , λ T +T κcp (2M ) δ G+ (0) σ 2p λ

3 r− 2

2r−5

− 2r+s −2 Notelthat with and m the partition size m specified in (18), we also have λ B|Dj |,λ ≤ C0,1 + 1. Hence, for λ = |D| 1 2r+s T = |D| , there holds with confidence at least 1−δ that 1

(

λ2 T p+1 , λB|Dj |,λ , 2p fT∗ +1,Dj − fρ ρ ≤ Cr,7 max λr , p σ |Dj |

)

6 log δ

3 .

i h √ 3 C′ 2p+1 where Cr,7 := ∥uρ ∥ρ (C0,1 + 1)2 (8r − 12)κ2r−3 C 32 + 2C1 (1 + κ2 )r− 2 + 2Cr + G′ η(0) ( 2 + 1)κcp (2M ) . Further, we +

can apply (82) to obtain E

fT∗ +1,Dj − fρ ρ

(

T p+1 λ2 , λB|Dj |,λ , 2p ≤ Cr,7 (log 6) + 18Γ(3) max λ , p σ |Dj | 3

)

Before concluding the proof, we remark that for r > 52 , the constraint on partition size m derived from the above 3 3+s 2r bound is more stringent than condition (18). Specifically, ensuring √λ 2 = O(|D|− 2r+s ) requires m ≤ |D| 2r+s , which |Dj |

imposes a tighter restriction on m for lager r. To overcome this bottleneck, we employ (83) to derive the explicit learning rates in Theorem 2 for r > 52 . Conversely, for 5−s < r ≤ 52 , condition (16) is less restrictive than (18); thus, 2 we also apply (83) to establish the rates. This distinction clarifies why the regularity regimes in (18) differ from those implied by the intermediate technical conditions. Finally, to derive the explicit learning rates in Theorem 2, we need the following results 2 2 2 λ2 B|D = C0,1 m|D|− 2r+s ≤ C0,1 |D|− 2r+s , j |,λ 2r+2

and

m X |Dj |2 j=1

|D|

2 B|D = j |,λ 2

m X |Dj |2 j=1

|D|2

2 2 |D|− 2r+s , C0,1 m|D|− 2r+s ≤ C0,1 2r

which can be verified by the partition size m specified in (18). Since E fT +1,Dj − fρ ρ ≤ E

fT∗ +1,Dj − fρ

follows from (42) that E

2 m m i X i X |Dj | |Dj |2 h 2 2 ∗ E f − f + E f − f . f¯T +1,D − fρ ρ ≤ T +1,Dj ρ ρ ρ T +1,Dj |D|2 |D| ρ j=1 j=1

, it ρ

For 12 < r ≤ 5−s , combining (85) and the above bounds on E 2

fT∗ +1,Dj − fρ

yields that ρ

i 2 f¯T +1,D − fρ ρ ( )2 2 3 m m p+1 X X |Dj |2 T p+1 r T p+ 2 log T |Dj | r T + Br max λ , 2p , λB|Dj |,λ ≤ Ar max B|Dj |,λ , 2p , λ , B|Dj |,λ |D|2 σ σ 2p |D| σ j=1 j=1 8(2r + s)2 T 2p+2 2r − 2r+s 2 ≤ 22p+2 C0,1 Ar , + B , max |D| r (2r − 1)2 σ 4p E

2 2 10 3 3 2 2 2 2 where Ar := C̃r,2 (log 24) + 240Γ(10) and Br := Cr,4 [(log 8)4r + 32rΓ(4r)] + Cr,5 (log 2) + 6Γ(3) + Cr,6 (log 6) + 2 18Γ(3) . The proof is completed by combining (83) for r > 5−s and the above bound for 12 < r ≤ 5−s , where 2 2 8(2r + s)2 12 2 C̃2 := C̃12 (log 48) + 576Γ(12) + 22p+2 C0,1 Ar + B r . (2r − 1)2

6.4

Proof of Theorem 3

To prove Theorem 3, we adopt the error decomposition in Subsection 5.4 and establish the high-probability bounds for f¯Tl +1,D − fT +1,D ρ and ∥fT +1,D − fρ ∥ρ , respectively. First, we can directly apply the derived high-probability bounds for fT +1,Dj − fρ ρ to estimate ∥fT +1,D − fρ ∥ρ by substituting Dj with D in (84). Specifically, there holds with confidence at least 1 − δ that

5 24 log δ p+1 2 r 1 T 24 r + Cr,2 A|D|,λ + log + ∥uρ ∥ρ T −r 2 σ 2p δ eηG′+ (0) ) ( 5 p+ 32 24 log T 2 −(r− 21 ) −1 T log + Cr,3 A|D|,λ B|D|,λ max T log T, T , . σ 2p δ

∥fT +1,D − fρ ∥ρ ≤ (1 + ηG′+ (0)λT )(1 + κ2r−1 ∥uρ ∥ρ )A2|D|,λ B|D|,λ

l m 1 r 1 Since λ = |D|− 2r+s and T = |D| 2r+s , it can be directly derived that B|D|,λ ≤ C0,1 |D|− 2r+s and A2|D|,λ ≤ C0,3 + 1 by taking m = 1 on the bounds on B|Dj |,λ , R|Dj |,λ and A|Dj |,λ in the proof of Theorem 1. Hence, we have that with confidence at least 1 − δ,

(

p+1

∥fT +1,D − fρ ∥ρ ≤ C̃r,3 max |D|

r − 2r+s

|D| 2r+s , σ 2p

)

24 log δ

5 (86)

r 3 r where C̃r,3 := C0,1 (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ ) + 3 · 2p Cr,2 + 2p+ 2 C0,1 Cr,3 4r+2s ∥uρ ∥ρ . It (C + 1) + ′ 0,3 2r−1 eηG (0) +

is evident that this result differs from that in [8] only by a constant factor. Now we turn to estimate f¯Tl +1,D − fT +1,D ρ . By (59), we first need to estimate the bound of f¯T0 +1,D − fT +1,D ρ , which equals to f¯T +1,D − fT +1,D . For convenience, the decomposition f¯T +1,D − fT +1,D = f¯T +1,D − fT +1 + fT +1 − ρ

fT +1,D is adopted, which allows us to separately estimate the two terms f¯T +1,D − fT +1 ρ and ∥fT +1,D − fT +1 ∥ρ . To estimate f¯T +1,D − fT +1 , by Proposition 2 and the proof of Theorem 1, we have that with confidence at least

1−δ, there holds 12 f¯T +1,D − fT +1 ρ ≤ (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ )B|D|,λ log δ ( ) p+1 p+ 23 log T 6 T T 1 + Cr,2 2p + Cr,3 B|D|,λ max T −(r− 2 ) log T, T −1 , log 2p σ σ δ 3 T p+1 48m ′ log T log + Cr,2 max R|Dj |,λ A|Dj |,λ 1≤j≤m σ 2p δ ( ) 6 n o p+ 32 (log T )2 48m ′ 2 −(r− 21 ) 2 T + Cr,3 max R|Dj |,λ B|Dj |,λ A|Dj |,λ max log T, T (log T ) , log . 1≤j≤m σ 2p δ Since the condition (20) still implies (81), we can apply the bounds on B|Dj |,λ , R|Dj |,λ and A|Dj |,λ in the proof of Theorem 1 to further simplify the above bound as f¯T +1,D − fT +1 ρ 6 6 (87) T p+1 48m 48m + C̃3,2 max R|Dj |,λ B|Dj |,λ log T log , ≤C̃3,1 max B|D|,λ , 2p log 1≤j≤m σ δ δ √ √ ′ 1 ′ where C̃3,1 := (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ ) + Cr,2 + 2Cr,3 C0,1 4r+2s + Cr,2 C0,2 (C0,3 + 1) 2 + 2Cr,3 C0,1 C0,2 (C0,3 + 1) 2r−1 2 ′ and C̃3,2 := 2r−1 Cr,3 (C0,3 + 1). 1

2 Since for each f ∈ HK , there holds ∥f ∥ρ = LK f

. Considering that fT +1,D , fT +1 ∈ HK , we have

2 ∥fT +1,D − fT +1 ∥ρ = LK (fT +1,D − fT +1 )

≤ (λI + LK ) 2 (fT +1,D − fT +1 )

. K

By Proposition 1, the proof of Theorem 1 and the partition size m specified in (20), we can obtain that with confidence at least 1−δ, there holds ∥fT +1,D − fT +1 ∥ρ ≤ (1 + 2ηG′+ (0))A2D,λ (PD,λ + QD,λ ∥fρ ∥K ) ) ( p+ 23 T p+1 T log T 1 + Cr,2 AD,λ 2p + Cr,3 A2D,λ QD,λ max T −(r− 2 ) log T, T −1 , σ σ 2p 5 T p+1 24 ≤ C̃3,3 max B|D|,λ , 2p log , σ δ √ 1 where C̃3,3 := (1 + 2ηG′+ (0))(1 + κ2r−1 ∥uρ ∥ρ )(C0,3 + 1) + Cr,2 (C0,3 + 1) 2 + 2Cr,3 C0,1 4r+2s (C0,3 + 1). 2r−1

(88)

With the triangle inequality, we combine (87) and (88)to derive that with confidence at least 1−2δ, there holds f¯T0 +1,D − fT +1,D ρ = f¯T +1,D − fT +1,D ρ ≤ f¯T +1,D − fT +1 ρ + ∥fT +1,D − fT +1 ∥ρ 6 T p+1 48m ≤ (C̃3,1 + C̃3,3 ) max B|D|,λ , 2p log σ δ 6 48m . + C̃3,2 max R|Dj |,λ B|Dj |,λ log T log 1≤j≤m δ Then we can adopt (59) to bound f¯Tl +1,D − fT +1,D ρ . Note that bounding the sum term in (59) relies on the highprobability bounds of Q|D|,λ , Q|D |,λ and A|D |,λ , which are also analyzed in deriving the bound of f¯0 − fT +1,D . j

T +1,D

Hence, by Lemma 4 and Lemma 6, we have that with confidence at least 1−2δ, there holds 1 l 1 fT +1,D − f¯Tl +1,D ρ ≤ max (QD,λ + QDj ,λ )ADj ,λ Cη′ λ 2 T + T 2 f¯T0 +1,D − fT +1,D ρ 1≤j≤m

≤(4 + 2

√

l l 2) (Cη′ )l (C0,3 + 1) 2 λ− 2

max

1≤j≤m

T p+1 B|D|,λ , 2p σ

l B|D · (C̃3,1 + C̃3,3 ) max j |,λ

6+3l 48m log δ 6+3l 48m log T log . δ

√ l l l + (4 + 2 2)l (Cη′ )l (C0,3 + 1) 2 λ− 2 max B|D · C̃3,2 max R|Dj |,λ B|Dj |,λ j |,λ 1≤j≤m 1≤j≤m ( ) 6+3l p+1 |D| 2r+s 48 r ≤ C̃3,4 max |D|− 2r+s , log . σ 2p δ i h √ l l where C̃3,4 := (4 + 2 2)l 26+3l (Cη′ )l C0,1 (C0,3 + 1) 2 (C0,1 + 2p+1 )(C̃3,1 + C̃3,3 ) + C0,1 C0,2 C̃3,2 .

(89)

It is observed that the derivation of both high-probability upper bounds for ∥fT +1,D − fT +1 ∥ρ and ∥fT +1,D − fρ ∥ρ relies on the estimation of the bounds of P|D|,λ , Q|D|,λ and A|D|,λ . Consequently, these two bounds hold simultaneously. Applying the triangle inequality and scaling 2δ to δ, we can combine (86) and (89) to derive that with confidence at least 1 − δ, there holds

( f¯Tl +1,D − fρ ρ ≤ C̃3 max

p+1

|D|

r − 2r+s

|D| 2r+s , σ 2p

)

96 log δ

6+3l .

where C̃3 = C̃3,4 + C̃r,3 . This completes the proof of Theorem 3.

Appendix In this appendix, we give the proof of Lemma 1 and Lemma 2. Proof of Lemma 1. We prove (27) by induction, f1 = 0 is obviously satisfies the inequality (27). Then for t = 2, (22) indicates that

M ηCG ≤ , κ Z K R which means that the inequality (27) also holds for t = 2. When t > 2, we denote Ht = Z G′ (ξt,σ (z))(ft (x) − y)Kx dρ ∥f2 ∥K = −η

G′ (ξt,σ (z))(−y)Kx dρ

≤ ηκM CG ≤ M

and have that ∥ft+1 ∥2K = ∥ft − ηHt ∥2K = ∥ft ∥2K − 2η⟨ft , Ht ⟩K + η 2 ∥Ht ∥2K Z 2 ≤∥ft ∥K + −2ηG′ (ξt,σ (z))(ft (x) − y)ft (x) + η 2 κ2 G′ (ξt,σ (z))2 (ft (x) − y)2 dρ ZZ 2 =∥ft ∥K + η ηκ2 G′ (ξt,σ (z))(ft (x) − y)2 − 2(ft (x) − y)ft (x) G′ (ξt,σ (z))dρ (90) Z ( ) 2 Z y y2 2 2 ′ =∥ft ∥K + η ηκ G (ξt,σ (z)) − 2 (ft (x) − y) − 2 ′ + G′ (ξt,σ (z))dρ, 2 G′ (ξ ηκ G (ξ (z)) − 2 2 − ηκ (z)) t,σ t,σ Z where the first inequality is due to the Jensen’s inequality and the fact that K(x, x′ ) ≤ κ2 for any x, x′ ∈ X , and the last equality is due to the completion of squares. Since G′ (ξt,σ (z)) ≤ CG , we have that ηκ2 G′ (ξt,σ (z)) ≤ 1, and further ηκ2 G′ (ξt,σ (z))−2 ≤ 0 and 2−ηκ2 G′ (ξt,σ (z)) ≥ 1 for any z ∈ Z. Putting the above bound with |y| ≤ M and the induction assumption ‖ft ‖2K ≤ ηCG M 2 (t − 1) into (90) yields that ∥ft+1 ∥2K ≤ ∥ft ∥2K + ηCG M 2 ≤ ηCG M 2 t, and thus ∥ft+1 ∥K ≤ M

p M 21 t . ηCG t ≤ κ 38

This completes the proof of Lemma 1. Proof of Lemma 2. With the choice of η, we have I − ηG′+ (0)LK

T −i

≤ 1,

∀i = 0, 1, · · · , T.

Based on the proof of Theorem 1 (i) in [8, Page 15], it can be derived with θ = 0 and η1 replaced by η that T X

ηG′+ (0)(λI + LK,D ) I − ηG′+ (0)LK,D

T −i

≤ ηG′+ (0)λT + 1.

i=1

Analogously, we can replace LK,D with LK to obtain the same bound of the operator norm concerning LK . Therefore, the proof is completed.

Reference [1] Zhang Y, Duchi J, Wainwright M, Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates, Journal of Machine Learning Research, 16(1):3299-3340, 2015. [2] Lin S B, Guo X, Zhou D X, Distributed learning with least square regularization, Journal of Machine Learning Research, 18(92):1-31, 2017. [3] Guo Z C, Lin S B, Zhou D X, Learning theory of distributed spectral algorithms, Inverse Problems, 33(7):074009, 2017. [4] Mücke N, Blanchard G, Parallelizing spectrally regularized kernel algorithms, Journal of Machine Learning Research, 19(1):1069-1097, 2018. [5] Lin S B, Wang D, Zhou D X, Distributed Kernel Ridge Regression with Communications, Journal of Machine Learning Research, 21(93):1-38, 2020. [6] Lin S B, Zhou D X, Distributed kernel-based gradient descent algorithms, Constructive Approximation, 47(2): 249-276, 2018. [7] Hu T, Wu Q, Zhou D X, Distributed kernel gradient descent algorithm for minimum error entropy principle, Applied and Computational Harmonic Analysis, 49(1):229-256, 2020. [8] Guo Z C, Hu T, Shi L, Gradient descent for robust kernel-based regression, Inverse Problems, 34(6):065009, 2018. [9] Hong Q, Guo Z C, Robust kernel-based gradient descent with random features, Advances in Computational Mathematics, 51(6):1-63, 2025. [10] Guo Z C, Christmann A, Shi L, Optimality of Robust Online Learning, Foundations of Computational Mathematics, 24(5):1455-1483, 2024. [11] Huber P J, Robust estimation of a location parameter, Breakthroughs in Statistics: Methodology and Distribution, Springer, 492-518, 1992. [12] Holland P, Welsch R E, Robust regression using iteratively reweighted least-squares, Communications in Statistics - Theory and Methods, 6(9):813-827, 1977. [13] Yao Y, Rosasco L, Caponnetto A, On early stopping in gradient descent learning, Constructive Approximation, 26:289-315, 2007. [14] Bellet A, Liang Y, Garakani A B, et al., A distributed Frank-Wolfe algorithm for communication-eﬀicient sparse learning, Proceedings of the 2015 SIAM International Conference on Data Mining, 478-486, 2015. [15] Zeng J, Yin W, On nonconvex decentralized gradient descent, IEEE Transactions on signal processing, 66(11): 2834-2848, 2018. 39

[16] Yin R, Wang W, Meng D, Distributed nyström kernel learning with communications, International Conference on Machine Learning, 12019-12028, 2021. [17] Huang C, Huo X, A distributed one-step estimator, Mathematical Programming, 174:41-76, 2019. [18] Liu J, Shi L, Distributed learning with discretely observed functional data, Inverse Problems, 41(4):045006, 2025. [19] Wang B, Hu T, Lei L, Distributed Robust Algorithms with Dependent Sampling, Mathematics, 13(23):3813, 2025. [20] Minsker S, On some extensions of Bernstein’s inequality for self-adjoint operators, Statistics & Probability Letters, 127:111-119, 2017. [21] Caponnetto A, Yao Y, Cross-validation based adaptation for regularization operators in learning theory, Analysis and Applications, 8(02):161-183, 2010. [22] Caponnetto A, De Vito E, Optimal rates for the regularized least-squares algorithm, Foundations of Computational Mathematics, 7:331-368, 2007. [23] Steinwart I, Hush D R, Scovel C, Optimal Rates for Regularized Least Squares Regression, Proceedings of the 22nd Annual Conference on Learning Theory, 79-93, 2009. [24] Ruder S, An overview of gradient descent optimization algorithms, arXiv preprint arXiv:1609.04747, 2016. [25] Bauer F, Pereverzev S, Rosasco L, On regularization algorithms in learning theory, Journal of complexity, 23(1): 52-72, 2007. [26] Dicker L H, Foster D P, Hsu D, Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators, Electronic Journal of Statistics, 11(1):1022-1047, 2017. [27] Raskutti G, Wainwright M J, Yu B, Early stopping and non-parametric regression: an optimal data-dependent stopping rule, Journal of Machine Learning Research, 15(1):335-366, 2014. [28] Hu T, Kernel-based maximum correntropy criterion with gradient descent method, Communications on Pure & Applied Analysis, 19(8):4159-4177, 2020. [29] Zhou D X, Deep distributed convolutional neural networks: Universality, Analysis and Applications, 16(6): 895-919, 2018. [30] Yu Z, Fan J, Shi Z, et al., Distributed Gradient Descent for Functional Learning, IEEE Transactions on Information Theory, 70(9):6547-6571, 2024. [31] Smale S, Zhou D X, Learning theory estimates via integral operators and their approximations, Constructive Approximation, 26(2):153-172, 2007. [32] Guo Z C, Shi L, Optimal rates for coeﬀicient-based regularized regression, Applied and Computational Harmonic Analysis, 47(3):662-701, 2019. [33] Engl H W, Hanke M, Neubauer A, Regularization of inverse problems, Springer Science & Business Media, 1996. [34] Blanchard G, Krämer N, Optimal learning rates for Kernel Conjugate Gradient regression, Advances in Neural Information Processing Systems, 226-234, 2010. [35] Zhou D X, The covering number in learning theory, Journal of Complexity, 18(3):739-767, 2002.

Record · ID 673515 · SHA-256 82a2948c08c4b3ac
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.