Towards Sharp Analysis for Distributed Learning with Random Features

1 Introduction

A fundamental problem in machine learning is to achieve tradeoffs between statistical properties and computational costs [Bottou and Bousquet, 2008; Li et al., 2018], while this challenge is more severe in kernel methods. Despite the excellent theoretical guarantees, kernel methods do not scale well in large-scale settings because of high time and memory complexities, typically at least quadratic in the number of examples. To break the scalability bottlenecks, researchers developed a wide range of practical algorithms, including distributed learning, which produces a global model after training disjoint subset on individual machines with necessary communications [Zhang et al., 2015; Lin et al., 2017], Nystr¨om approximation [Williams and Seeger, 2001; Rudi et al., 2015; Li et al., 2019a] and random Fourier features [Rahimi and Recht, 2007; Rudi and Rosasco, 2017] to alleviate memory bottleneck, as well as stochastic methods [Lin and Cevher, 2020] to improve the training efficiency.

From the theoretical perspective, many researchers have studied the statistical properties of those large-scale approaches together with kernel ridge regression (KRR) [Rudi et al., 2015; Lin and Rosasco, 2016; Lin et al., 2017]. Using integral operator techniques [Smale and Zhou, 2007] and the effective dimension to control the capability of RKHS [Caponnetto and De Vito, 2007], the generalization bounds have achieved the optimal learning rates. Recent statistical learning studies on KRR together with large-scale approaches demonstrate that these approaches can not only obtain great computational gains but still remain the optimal theoretical properties, such as KRR together with divide-and-conquer [Guo et al., 2017; M¨ucke and Blanchard, 2018], with random projections including Nystr¨om approximation [Rudi et al., 2015] and random features [Rudi and Rosasco, 2017; Carratino et al., 2018; Li et al., 2020; Li, 2021]. Since the communication cost is high to combine local kernel estimators in RKHS, it's more practical to combine the linear estimator in the feature space, e.g. federated learning [McMahan et al., 2017].

∗Corresponding author

The existing works on DKRR [Guo et al., 2017; Lin et al., 2017; M¨ucke and Blanchard, 2018] and random features [Rudi and Rosasco, 2017; Li et al., 2019b; Li, 2021] have primarily focused on attainable cases, ignoring the nonattainable cases where the true regression is out of the hypothesis space. Since it's hard to select the suitable kernels to guarantee the attainable cases, the non-attainable cases are more common in practice. Therefore, the statistical guarantees for the non-attainable are of practical and theoretical interest in the context of the statistical learning theory. The optimal rates for DKRR have been extended to a part of the non-attainable case via sharp analysis for the distributed error [Lin and Cevher, 2020] and multiple communications [Lin et al., 2020; Liu et al., 2021], but these techniques are hard to improve the results for random features. Meanwhile, recent studies extended the capacity-independent optimality to the non-attainable cases, including distributed learning [Sun and Wu, 2020], random features [Sun et al., 2018] and Nystr¨om approximation [Kriukova et al., 2017], but these capacity-independent results are suboptimal when the capacity of RKHS is small. The capacity-optimality for the combination of distributed learning and random features to the non-attainable case is still an open problem.

In this paper 1 , we aim at extending the capacity-dependent optimal guarantees to the non-attainable case and improve the computational efficiency with more partitions and fewer random features. Firstly, using the refined estimation of operators' similarity, we refine the optimal generalization error bound that allows much more partitions and pertains to a part of the non-attainable case. Then, generating random features in a data-dependent manner, we relax the restriction on the dimension of random features, and thus fewer random features are sufficient to reach the optimal rates. By using additional unlabeled data to reduce label-independent error terms, we further enlarge the number of partitions and improve the applicable scope in the non-attainable case. Finally, we validate our theoretical findings with extensive experiments. Note that, we leave proofs and experiments in the full version

1 Full version: https://arxiv.org/abs/1906.03155

1.1 Our Contributions

We highlight our contributions as follows:

1) On algorithmic front: higher computational efficiency

This work presents the currently maximum number of partitions and the minimal dimension of random features, extremely improving the computational efficiency.

More partitions. To achieve the optimal learning rate, the traditional distributed KRR methods [Lin et al., 2017; Guo et al., 2017] impose a strict constraint on the number of partitions m ≲ N 2r-1 2r+γ , which heavily limits the computational efficiency. In this paper, using a novel estimation of the key quantity, we first relax the restriction to m ≲ N 2r+γ-1 2r+γ . Then, introducing a few additional unlabeled examples, we improve the number of partitions to m ≲ N 2r+2γ-1 2r+γ for the first time.

Fewer random features. By generating random features in a data-dependent manner rather than in a data-independent manner, we reduce the requirement on the number of random features from M ≳ N (2r-1)γ+1 2r+γ ∀r ∈ [1/2, 1] to M ≳ N 2r+γ-1 2r+γ ∨N γ 2r+γ ∀r ∈ (0, 1], whereM is the number of random features and ∨ indicates the bigger one.

2) On theoretical front: covering non-attainable cases

The conventional optimal properties for KRR [Caponnetto and De Vito, 2007; Rudi and Rosasco, 2017; Guo et al., 2017] only pertain to the attainable case r ∈ [1, 1/2], assuming the true regression belongs to the hypothesis space fρ ∈ H where the problems can not be too difficult. However, the condition fρ ∈ H is too ideal and the non-attainable r ∈ (0, 1/2) assuming fρ /∈ H deserve more attention. In this paper, we first restate the classic results in the attainable r ∈ [1/2, 1]. Then, by relaxing the restriction on the number of partitions, we extend the optimal theoretical guarantees to the non-attainable case with the constraints 2r + γ ≥ 1 and 2r + 2γ ≥ 1. Note that we prove KRR with random features applies to all nonattainable cases r ∈ (0, 1/2).

3) Extensive experimental validation

To validate our theoretical findings, we conduct extensive experiments on simulated data and real-world data. We first construct simulated experiments under different difficulties to validate the learning rate and training time. Then, we perform comparison on a small real-world dataset to verify the effectiveness of data-dependence random features (with a novel approximate leverage score function) and additional unlabeled examples. Finally, we compare the proposed DKRR-RF with related work in terms of the performance on three realworld datasets.

4) Technical challenges

More partitions with additional unlabeled examples. In the error decomposition, only sample variance is labeldependent. At the same time, other terms are labelindependent, and thus we employ additional unlabeled examples to reduce the estimation of label-independent error terms. We further improve the applicable scope in the non-attainable case to m ≲ N 2r+2γ-1 2r+γ .

Random features error in all non-attainable cases. Using an appropriate decomposition on the operatorial level for random features error, we prove KRR with random features pertains to both attainable and non-attainable case r ∈ (0, 1].

Overall, by overcoming several technical hurdles, we present the optimal theoretical guarantees for the combination of DKRR and RF. With more partitions and fewer random features, the theoretical results not only obtain significant computational gains but also preserve the optimal learning properties to both the attainable and non-attainable case r ∈ (0, 1]. Indeed, KRR [Caponnetto and De Vito, 2007], DKRR [Guo et al., 2017], and KRR-RF [Rudi and Rosasco, 2017] are special cases of this paper. Thus, the techniques presented here pave the way for studying the statistical guarantees of other types kernel approaches (even neural networks) that can apply to the non-attainable case.

2 Distributed Learning with RandomFeature

In a standard framework of supervised learning, there is a probability space X ×Y with a fixed but unknown distribution ρ, where X = Rd is the input space and Y = R is the output space. The training set D = {(xi, yi)}Ni=1 is sampled i.i.d. from X × Y with respect to ρ. The primary objective is to fit the target regression fρ on X × Y. The Reproducing Kernel Hilbert Space (RKHS) H induced by a Mercer kernel K is defined as the completion of the linear span of {K(x, ·), x ∈ X} with respect to the inner product ⟨K(x, ·),K(x′ , ·)⟩H = K(x, x′ ). In the view of feature mappings, an underlying nonlinear feature mapping ϕ : X → H associated with the kernel K is ϕ(x) := K(x, ·), so it holds f(x) = ⟨f, ϕ(x)⟩H.

2.1 Kernel Ridge Regression (KRR)

With an RKHS norm term, kernel ridge regression (KRR) is one of the popular empirical approaches to conducting a nonparametric regression. KRR can be stated as

Using the representation theorem, the nonlinear regression problem (1) admits a closed form solution ̂ fλ(x) = ∑Ni=1 ̂ αiK(xi, x) with

where λ > 0, yN = [y1, · · · , yN]T and KN is the N × N kernel matrix with KN(i, j) = K(xi, xj). Although KRR characterizes optimal statistical properties [Smale and Zhou, 2007; Caponnetto and De Vito, 2007], it is unfeasible for large-scale settings because of O(N 2 ) memory to store kernel matrix and O(N 3 ) time to solve the linear system (2).

2.2 Distributed KRRwith RandomFeatures (DKRR-RF)

Assume that the kernel K have an integral representation

where (Ω, π) is a probability space and ψ : X × Ω → R. We define analogous operators for the constructed kernel KM(x, x′ ) = ϕM(x)⊤ϕM(x′ ) to approximate the primal kernel K(x, x′ ) in (3) with its corresponding random features via Monte Carlo sampling

where ω1, · · · , ωM ∈ Ω are sampled w.r.t. p(ω).

Let the training set D be randomly partitioned into m disjoint subsets {Dj}mj=1 with |D1| = · · · = |Dm| = n. The local estimator ̂wj on the subset Dj is defined as

where the estimator is f(x) = ⟨w, ϕM(x)⟩. It admits a closed-form solution

where λ > 0. Note that for j-th subset Dj , it holds ∀(x, y) ∈ Dj,ΦM = 1 √n [ϕM(x1), · · · , ϕM(xn)]⊤ ∈ Rn×M and ̂ yn = 1 √n (y1, · · · , yn)⊤. The average of local estimators (6) yields a global estimator

3 Theoretical Assessment

In this section, we present the theoretical analysis on the generalization performance of kernel ridge regression with divide-and-conquer and random features.

The generalization ability of a regression predictor f : X → R is measured in terms of the expected risk

In this case, the target regression fρ = ∫Y ydρ(y|x), ∀x ∈ X minimizes the expected risk over all measurable functions f : X → R. The generalization ability of a KRR estimator f ∈ L2ρX is measured by the excess risk, i.e. E(f)-E(fρ), where L2ρX = {f : X → R | ∥f∥2ρ = ∫X |f(x)|2dρX < ∞} is the square integral Hilbert space with respect to the marginal distribution ρX on the input space X.

3.1 Assumptions

We first introduce two standard assumptions, which are also used in statistical learning theory [Smale and Zhou, 2007; Caponnetto and De Vito, 2007; Rudi and Rosasco, 2017].

Assumption 1 (Random features are continuous and bounded). Assume that ψ is continuous and there is a κ ∈ [1, ∞), such that |ψ(x, ω)| ≤ κ, ∀x ∈ X , ω ∈ Ω.

Assumption 2 (Moment assumption). Assume there exists B > 0 and σ > 0, such that for all p ≥ 2 with p ∈ N,

According to Assumption 1, the kernel K is bounded by K(x, x) ≤ κ2 . The moment assumption on the output y holds when y is bounded, sub-gaussian or sub-exponential. Assumptions 1 and 2 are standard in the generalization analysis of KRR, always leading to the learning rate O(1/√N) [Smale and Zhou, 2007] in general cases.

Definition 1 (Integral operators). ∀ g ∈ L2ρX (X, ρX), the integral operators L, LM are defined by the kernel K and the random features ϕM, respectively

Definition 2 (Effective dimension). The effective dimension of the RKHS H induced by the kernel K is defined as

The effective dimension N(λ) is used to measure the complexity of RKHS H, and its empirical counterpart is also called degree of freedom [Bach, 2013]. Similarly, we define the effective dimension NM(λ) for the random features mapping ϕM to measure the size of the approximate RKHS HM, which is induced by finite dimensional random features ϕM : X →RM .

Assumption 3 (Capacity assumption). Assume there exists Q > 0 and γ ∈ [0, 1], such that for any λ > 0

Assumption 4 (Regularity assumption). Assume there exists R > 0, r > 0, and g ∈ L2ρX , such that

where fρ is the target regression, ∥g∥ρ ≤ R and the operator Lr denotes the r-th power of the integral operator L : L2ρX → L2ρX , thus it is also a positive trace class operator.

The above two conditions are commonly used to prove the optimal statistical properties of the exact KRR [Caponnetto and De Vito, 2007; Smale and Zhou, 2007], and its large-scale extensions including divide-and-conquer [Lin et al., 2017; Guo et al., 2017] and random features [Rudi and Rosasco,

2017]. Those two assumptions reflect the capacity of the RKHS H and the regularity of fρ, respectively. We provide some intuitive interpretations of the above assumptions, and more details can be found in [Caponnetto and De Vito, 2007]. Assumption 3 holds when the eigenvalues of the integral operator have a polynomial decay i-1/γ , ∀i > 1 [Rudi and Rosasco, 2017; Li et al., 2019b]. Thus, faster convergence rates are derived when the eigenvalues decay faster, a.k.a. γ approaches 0, while γ = 1 corresponds to the capacity-independent case. Assumption 4 (source condition) controls the regularity of the target function fρ. The bigger the r is, the stronger regularity of the regression is, and the easier the learning problem is. Both these two assumptions are widely used in the optimal theory for KRR [Caponnetto and De Vito, 2007; Rudi and Rosasco, 2017; Guo et al., 2017].

3.2 General Results with Fast Rates

One can prove the optimal generalization guarantees for DKRR-RF by combining the theories in KRR-DC [Lin et al., 2017] and KRR-RF [Rudi and Rosasco, 2017]. The attainable case r ∈ [1/2, 1] requires the existence of fH = minf∈H E(f), such that fρ = fH almost surely [Steinwart and Christmann, 2008], which is widely used in KRR and its variants including distributed KRR and random features based KRR [Caponnetto and De Vito, 2007; Rudi and Rosasco, 2017; Guo et al., 2017].

Theorem 1. Under Assumptions 1, 2, 3 and 4, if r ∈ [1/2, 1], γ ∈ [0, 1], and λ = N - 1 2r+γ , then

are enough to guarantee, with a high probability, that

The optimal learning rate O (N - 2r 2r+γ ) stated in Theorem 1 in the above bound is optimal in a minimax sense for KRR approaches [Caponnetto and De Vito, 2007]. Distributed KKR methods have obtained the same optimal error bounds with a stronger condition on the number of partitions, such as KRR-DC [Lin et al., 2017; M¨ucke and Blanchard, 2018] with m ≲ N 2r-1 2r+γ . In particular, for the general case r = 1/2, the number of local processors m = O(1) becomes a constant number that is independent of the sample size N. The time complexity of DKRR-RF is O(NM 2 /m) and the space complexity O(NM/m), thus we report the computational complexities of Theorem 1 in Figure 1.

Remark 1. The general results in Theorem 1 have three fatal drawbacks: 1) the above bound is only suitable for the attainable case r ∈ [1/2, 1] and fail to apply to the nonattainable case r ∈ (0, 1/2) induced by more complicated problems; 2) random features generated via Monte Carlo are data-independent, which requires much more features than the data-dependent generating features; 3) the constraint on the number of partitions m ≲ N 2r-1 2r+γ is too strict, leading to a constant number of partitions when r is close to 1/2.

3.3 Refined Results in the Non-attainable Case

Theorem 2. Under Assumptions 1, 2, 3 and 4, if r ∈ (0, 1], γ ∈ [0, 1], 2r +γ ≥ 1 and λ = N - 1 2r+γ , then the number of partitions corresponding to

and the number of random features M satisfying

are enough to guarantee, with a high probability, that

Compared to Theorem 1, Theorem 2 allows more partitions and extends the optimal learning guarantees to the nonattainable case r ∈ (0, 1/2) where the true regression does not lie in RKHS H. Thus, it achieves significant improvements in both computational efficiency and statistical guarantees. With the same optimal learning rates, Theorem 2 relaxes the restriction on m from m ≲ N 2r-1 2r+γ to m ≲ N 2r+γ-1 2r+γ , which allows more partitions and relaxes the constraints from r ≥ 1/2 to 2r + γ ≥ 1. More importantly, for the general cases when r = 1/2, the number of partitions becomes m ≲ N γ 2r+γ , which increases as the sample size N becomes larger and avoids the constant number of partitions m = O(1) in the conventional KRR-DC methods [Guo et al., 2017; Lin et al., 2017]. When r ∈ (0, 1/2), the number of random features M ≳ N 1 2r+γ increases as the r approaches zero, because fρ becomes far away from H when r is near zero. When r ∈ [1/2, 1], we obtain the same level of the number of random features M ≳ N (2r-1)γ+1 2r+γ as KRR-RF [Rudi and Rosasco, 2017], which is continuous to M ≳ N 1 2r+γ at the critical points r = 1/2. Compared to Figure 1, Figure 2 illustrates Theorem 2 not only enlarge the applicable case but also improve the computational efficiency.

Remark 2. The common optimal generalization learning of KRR [Smale and Zhou, 2007] with random features techniques [Rudi and Rosasco, 2017] and divide-and-conquer [Zhang et al., 2015; Lin and Rosasco, 2016] focus on the generalization properties on the standard setting fρ ∈ H

under the condition r ∈ [1/2, 1]. Note that, in this paper, we extend the range of regularity assumption to r ∈ (0, 1/2) for considering the situation fρ /∈ H. Meanwhile, when r > 1, the divide-and-conquer approach can only reduce the sample error and computational variance, but not bias. The situation is called the saturation phenomenon and observed in KRR-DC approaches [Zhang et al., 2015; Lin and Cevher, 2020]. In the future, it's worthy to reducing the bias with multi-communications using stochastic methods rather than the divide-and-conquer strategy.

Remark 3. Theorem 2 extends the optimal generalization theories from only attainable case r ∈ [1/2, 1] to the nonattainable case 2r + γ ≥ 1, which include a part of difficult problems r ∈ (0, 1/2). However, there are also many cases satisfying 2r+γ < 1 in the non-attainable case r ∈ (0, 1/2), where the optimal learning guarantees in Theorem 2 are no longer valid. Inspired the literature [Chang et al., 2017], we employ additional unlabeled samples to relax the restriction 2r + γ ≥ 1 in Section 3.5.

3.4 Fewer Features with Data-dependent Sampling

Assumption 5 (Compatibility assumption [Rudi and Rosasco, 2017]). Define the maximum effective dimension as

Assume there exists α ∈ [0, 1] and F > 0, such that

Using the definition of N(λ), we characterize the lower bounds for N∞(λ):

Compared to the (average) effective dimension used in Assumption 3, the maximum effective dimension offers a finergrained estimate for the capacity of RKHS [Alaoui and Mahoney, 2015; Rudi and Rosasco, 2017; Rudi et al., 2018], which often leads to shaper estimate for the related quantities. Using the compatibility assumption, we relax the constraints on the dimension of random features and the number of partitions by generating features in a data-dependent manner, as shown in [Rudi et al., 2018; Bach, 2017; Li et al., 2019b].

Theorem 3. Under the same assumptions of Theorem 2 and Assumption 5, if r ∈ (0, 1], γ ∈ [0, 1], 2r + γ ≥ 1 and λ = N - 1 2r+γ , then the number of partitions m satisfying

and the number of random features M satisfying

is sufficient to guarantee, with a high probability, that

The learning rates of the above theorem are optimal, same as Theorems 2. Achieving the same optimal learning rates, Theorem 3 reduce the computational costs with fewer random features. The number of required random features is reduced from O(N 1 2r+γ ) to O(N α 2r+γ ) when r ∈ (0, 1/2) and O(N (2r-1)γ+1 2r+γ ) to O(N (2r-1)γ+1+2(r-1)(1-α) 2r+γ ) when r ∈ [1/2, 1], where the term 2(r - 1)(1 - α) ≤ 0. We report the applicable area and computational complexities of Theorem 3 in Figure 3. It shows the use of data-dependent sampling significantly reduce both the time and space complexities. The situations near the boarderline 2r + γ = 1 are away from the same computational complexities as the exact KRR.

Remark 4. From Theorem 1 in [Li et al., 2019b], we find that the requirement on the data-dependent random features is bounded as M ≳ d˜l := supw∈Ω lλ(w)/q(w), where d˜l ∝ N∞(λ) ≤ FN α 2r+γ . The condition is the same as Theorem 3 in the non-attainable r ∈ (0, 1/2) and milder than Theorem 3 in the attainable case r ∈ [1/2, 1]. However, the theoretical analysis provided in [Li et al., 2019b] only pertains to the general case (r = 1/2, γ = 1) and obtains error bounds with the convergence rate O(1/√N).

Remark 5. According to the definition of N∞(λ), the sampling probability of random features π(ω) is independent of data, which leads to a pessimistic estimate of α. However, generating random features in a data-dependent manner relaxes the estimate of α closer to γ. A theoretical example of data-dependent random features was given in Example 2 [Rudi and Rosasco, 2017], which guarantees N∞(λ) = N(λ) (such that α = γ) by constructing random features generated in a data-dependent way. In practice, leverage sampling algorithms were proposed to obtain data-dependent random features [Li et al., 2019b], where α is close to γ. To intuitively illustrate the improvement of data-dependent random features, we boldly assume α = γ by generating datadependent random features.

3.5 More Partitions with Unlabeled Data

Theorem 2 illustrates the optimal learning rates for DKRR-RF needs the number of local partitions satisfying

The number of partitions avoids a constant number of partitions when r ∈ [1/2, 1], but it is still unfeasible for many challenging problems in the non-attainable case r ∈ (0, 1/2). In this part, we introduce the additional unlabeled samples ˜Dj to relax this restriction further. We consider the merged dataset D∗ on the j-th processor, D∗ j =Dj ∪ ˜Dj with

Let D∗ = ⋃mj=1 D∗ j , |D∗ | = N ∗ and |D∗ 1 | = · · · = |D∗m| = n∗ . We define semi-supervised kernel ridge regression with divide-and-conquer and random features by

Theorem 4. Under the same assumptions of Theorem 3, if r ∈ (0, 1], γ ∈ [0, 1], 2r + 2γ ≥ 1 and λ = N - 1 2r+γ , then the total number of samples corresponding to

the number of local processors satisfying

and the number of random features M satisfying

are sufficient to guarantee, with a high probability, that

To our best knowledge, for the first time, we prove that the number of partitions can achieve m ≲ N 2r+2γ-1 2r+γ , while the existing constraints on m of the existing work [Lin and Cevher, 2020; Liu et al., 2021] are m ≲ N 2r+γ-1 2r+γ . Such that, much more partitions are allowed in distributed KRR methods. The relaxation of condition on the partition number m can not only lead to better computational efficiency but also covers more difficult problems, where the suitable problems are enlarged from the situation 2r + γ ≥ 1 to the situation 2r + 2γ ≥ 1. Figure 4 reveals the advantages of DKRR-RF with unlabeled data. Theorem 4 provides the largest applicable area 2r + 2γ ≥ 1 but also the highest computational efficiency owing to more partitions.

Remark 6. From the error decomposition, there are two error terms related to the number of partitions m: sample variance and empirical error. Sample variance depends on the number of labeled samples n, while empirical error is input-dependent but output-independent; thus, it is related to the number of total samples n∗ . Meanwhile, the similarity between empirical and expected covariance operators ∥ ̂ C -1/2 M,λ C 1/2 M,λ ∥ is also label-free, and thus it is related to the total sample size n∗ rather than n. To achieve the optimal learning rates, we consider the constraints on both the required labeled samples n and the total samples n∗ . Considering both conditions for supervised learning m = N/n and semi-supervised learning m = N ∗ /n∗ , we then obtain two constraints on the number of partitions m and consolidate them together.

4 Compared with RelatedWork

The existing optimal learning guarantees of KRR [Caponnetto and De Vito, 2007], KRR-DC [Guo et al., 2017; M¨ucke and Blanchard, 2018] and KRR-RF [Rudi and Rosasco, 2017; Liu et al., 2021] only apply to the attainable case r ∈ [1/2, 1]. In this paper, we apply the optimal generalization error bounds to the non-attainable case r ∈ (0, 1/2) with some restrictions, including 2r + γ ≥ 1 in Theorem 2 and 2r + 2γ ≥ 1 in Theorem 4. Using refined estimation, we extend the random features error to the non-attainable case.

4.1 Applicable Area from r ∈ [1/2, 1] to 2r+γ ≥ 1 The key to obtaining the optimal learning rates with integral-operator approach is to bound the identity ∥( ̂ CM + λI)-1/2 (CM + λI)1/2 ∥ as a constant, where CM and ̂ CM are the expected and empirical covariance operators defined in Definition 4. In conventional distributed KRR [Lin et al., 2017; Chang et al., 2017], they estimated the operator difference after first order (or second order) decomposition

To bound the identity as a constant, the local sample size should be larger enough n ≥ N(λ) λ . It holds m ≲ N 2r-1 2r+γ

for KRR-DC and only applies to r ≥ 1/2. However, this paper directly estimates the identity in total (rather than in parts after decomposition) based on concentration inequalities for self-adjoint operators and obtain

To bound the identity as a constant, the local sample size only needs n ≥ 1λ , which is smaller than [Guo et al., 2017] with N(λ). Therefore, our estimation of ∥(CM + λI)-1/2 ( ̂ CM + λI)1/2 ∥ in Theorem 2 is √N(λ) tighter than that in [Guo et al., 2017]. To bound identity as a constant, we then have m ≲ N 2r+γ-1 2r+γ , which is the key to obtainmore partitions and extends the optimal learning guarantees to the non-attainable case 2r + γ ≥ 1.

4.2 Applicable Area from 2r +γ ≥ 1 to

Only sample variance is dependent on the labeled samples, while other error terms involving the estimate of ∥(C + λI)-1/2 ( ̂ CM + λI)1/2 ∥ are label-free. Thus, there are two restrictions on the number of partitions m: sample variance (label-dependent) and the estimate of ∥(C + λI)-1/2 ( ̂ CM + λI)1/2 ∥ (label-free).

As shown in the proof of Theorem 3, the global sample variance (label-dependent) can be estimated

To achieve the optimal learning rates O(N -2r 2r+γ ), the number of partitions should satisfy m ≲ N 2r+2γ-1 2r+γ . Then, we utilize additional unlabeled samples to relax the condition on the estimate of ∥(C + λI)-1/2 ( ̂ CM + λI)1/2 ∥. Using Assumption 5, one can further relax the condition of m due to

To guarantee the key quantity ∥(CM + λI)-1/2 ( ̂ CM + λI)1/2 ∥ be a constant, we have m ≲ λαN ∗ = O(N ∗N -α 2r+γ ). We then consider the dominant constraints:

• The case α < 1-γ. It holds 2r+2γ-1 < 2r+γ-α, thus the number of partition is m ≲ N 2r+2γ-1 2r+γ .
• The case α ≥ 1-γ. It holds γ+α-1 ≥ 0 and we make use of additional unlabeled examples N ∗ ≳ NN γ+α-1 2r+γ to guarantee m ≲ N 2r+γ-α 2r+γ ≤ N 2r+2γ-1 2r+γ .

4.3 RandomFeatures Error in the Non-attainable Case

Using appropriate decomposition on operatorial level, we derive the random features error for both attainable and nonattainable case, where the dimension of random features should satisfy M ≳ N γ 2r+γ for the non-attainable case r ∈ (0, 1/2). The extension from the attainable case to the nonattainable case is non-trivial, where the non-attainable case requires refined estimations for operators similarity.

The operatorial definitions of intermediate estimators ˜ f M Dj,λ , f M λ and fλ in Lemma 1 involve the true regression fρ, where fρ = Lr g (under Assumption 4) is related to the range of r. Such that, we estimate the last three error items (empirical error ∥ ˜ f M Dj,λ - f M λ ∥, random features error ∥f M λ - fλ∥ and approximation error ∥fλ - fρ∥) that involve ˜ f M Dj,λ , f M λ and fλ for the non-attainable case. Meanwhile, because the empirical error satisfies ∥ ˜ f M Dj ,λ - f M λ ∥ ≤ (√2 + 2) (∥f M λ - fλ∥+∥fλ - fρ∥) and the approximation error ∥fλ - fρ∥ naturally applies to the non-attainable case, only random features error ∥f M λ - fλ∥ is needed to specifically estimated for the non-attainable case.

5 Conclusion

This paper explores the generalization performance of kernel ridge regression with two commonly used efficient largescale techniques: divide-and-conquer and random features. We first present a general result with the optimal learning rates under standard assumptions. We then refine the theoretical results with more partitions and applicability in the nonattainable case. Further, we reduce the number of random features by generating features in a data-dependent manner. Finally, we present the theoretical results that substantially relax the constraint on the number of partitions with extra unlabeled data, which apply to both the attainable case and non-attainable case. The proposed optimal theoretical guarantees are state-of-the-art in the theoretical analysis for KRR approaches. We validate our theoretical findings with extensive experimental results.

This paper can be extended in several ways: (a) the combination with gradient algorithms such as multi-pass SGD [Lin and Cevher, 2018; Lin and Cevher, 2020] and preconditioned conjugate gradient [Avron et al., 2017] to further reduce the time complexity. (b) using asynchronous distributed methods or a few of communications [Lin et al., 2020; Liu et al., 2021] instead of one-shot approach to alleviate the saturation phenomenon when r ≥ 1.

Acknowledgments

This work was supported in part by the Excellent Talents Program of Institute of Information Engineering, CAS, the Special Research Assistant Project of CAS, the Beijing Outstanding Young Scientist Program (No. BJJWZYJH012019100020098), Beijing Natural Science Foundation (No. 4222029), and National Natural Science Foundation of China (No. 62076234, No. 62106257).