Distributed Learning of Conditional Quantiles in the Reproducing Kernel Hilbert Space
Authors: Heng Lian
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed learning
Quantile regression
Rademacher complexity
Reproducing Kernel Hilbert Space

Abstract: We study distributed learning of nonparametric conditional quantiles with Tikhonov regularization in a reproducing kernel Hilbert space (RKHS). Although distributed parametric quantile regression has been investigated in several existing works, the current nonparametric quantile setting poses different challenges and is still unexplored. The difficulty lies in the illusive explicit bias-variance decomposition in the quantile RKHS setting as in the regularized least squares regression. For the simple divide-and-conquer approach that partitions the data set into multiple parts and then takes an arithmetic average of the individual outputs, we establish the risk bounds using a novel second-order empirical process for quantile risk. 

Distributed Learning of Conditional Quantiles in the Reproducing Kernel Hilbert Space
Heng Lian
City University of Hong Kong Shenzhen Research Institute, Shenzhen, China and
Department of Mathematics, City University of Hong Kong, Hong Kong, China henglian@eitpe tyy. edu.hk
Abstract
We study distributed learning of nonparametric conditional quantiles with Tikhonov regularization in reproducing kernel Hilbert space (RKHS). Although distributed parametric quantile regression has been investigated in several existing works, the current nonparametric quantile setting poses different challenges and is still unexplored. The difficulty lies in the illusive explicit bias-variance decomposition in the quantile RKHS setting in the regularized least squares regression. For the simple wwvide-and-conquee approach that partitions the data set into multiple parts and then takes an arithmetic average of the individual outputs, we establish the risk bounds using novel second-order empirical process for quantile risk.
1 Introduction
Distributed learning has attracted significant attention recently with the increasing popularity of distributed systems and distributed data. Although the algorithmic aspects have gone far beyond the simple data parallelism paradigm that uses simple divide-and-conquer strategy to carry out computations on each part of the data separately and then combine them in a finalizing step, the theoretical verification has lagged behind even though nowadays there are a lot of cases for which learning rates have been established, including Zhang al. (2013 2015); Rosenblatt and Nadler (2015) Balcan et al. (2015); Chang et al. (201 7): Lee et al. (2017) Lin et al. (2017); Jordan et al. (2018 Volgushev et al. (2019): Lian Fan (2018). It has been shown repeatedly for various models that the divide-and and-d-and-conquer method can achieve the same learning rate the standard estimator (assuming the whole data set is available on single machine and it is computationally feasible to compute this central estimator based on the entire sample), long as the number of partitions/macchinss not too large.
In this work, we investigate the theoretical underpinning of the divide-and-conque strategy for distributed learning of nonparametric quantile regression models in reproducing kernel Hilbert spaces (RKHS). Under this framework, the distributed learning rate for kernel ridge regression with a least squares loss has been established in several works (Lin al., 2017 Guo et al. 2017 Chang et al. 2017). The quantile regression proposed by Koenker and Bassett Jr 1978) is an important class of models that can focus on the tail of the response distribution and more robust the than least squares regression. However, the rate for nonparametric distributed learning other than least squares loss in the RKHS has not been established. The difficulty that the nonparametric quantile estimator in the RKHS does not have an explicit form, which makes the decomposition of the mean squared error into bias and variance illusive, while such decomposition the key to establishing the rates in method. Previously, the quantile regression estimator in the RKHS studied
the divide-and-conguee in Li et al. (2077): Steinwart and Christmann (201 based on standard empirical process theory does not make it possible to decompose the error into bias and variance and thus is not adaptable to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the distributed setting, although the upper bound derived there can be roughly regarded as a sum of a bias term and a variance term. On the other hand, for the dieddddimesioonl parametric quantile regression, the Bahadur representation for the estimator is well-established in the literature which can be used in the distributed setting. Even in high-dimensional parametric quantile regression, Zhao et al.. (2020) used debiasing strategy so that after debiasing the bias term is sufficiently small and can be explicitly controlled. Another related work on distributed high-dimensional parametric quantile regression is Chen et al. (2020), which is more closely related to the gradient method.
To address the challenges in trying to control the bias and the variance, we use what we call the second- empirical process involving the quantile loss function, which makes it possible to approximate more accurately the quantile loss by a weighted least squares loss, and we show that this approximation of the loss leads to approximation of the estimator (the weighted least squares estimator is close to the quantile estimator). The rest of the paper is organized as follows. In the next section, we state and prove the learning rates for both the central estimator and the distributed estimator. Section contains a simple numerical illustration, which is not used to verify the learning rate (which is difficult if not impossible) but just to illustrate the divide-and-conque method can work reasonably. The paper concludes in Section 4
2 Conditional quantile estimation in the RKHS
For the response y. its conditional quantile at quantile level 7 is denoted by (r) -z) For simplicity of notation, we will suppress T in our notations since we will focus on only an individual value of without modelling different quantiles jointly.
In the setting of RKHS, the unknown true function So in the regression problem is assumed to be inside an RKHS H C 1,2((0, 1J) with an associated kernel (..-), with the 1 space defined by probability measure px for x on [o, 1]. Note that here we assume the covariate x E [0, 1] without much loss of generality. In the following we use (e H and I|- to denote the RKHS inner product and
the RKHS norm, respectively, while ||.|| is the L L'-norm for functions. The function fo is estimated by
N
f arg min JEH
Σ Crr fxxx)) + nAllf
where (Vi. 2i); = 1, 1...., N is the entire sample from the true generating model with P(y: < fo(2;) (T.)) = T. Pr (x) = x(T 1xx S 0}) is the quantile loss function, and x > is a tuning parameter. f is referred to as the central estimator since it utilizes the entire sample.
In the distributed setting, the entire sample is distributed onto machines and each machine computes a local estimate
T, = arg min JEH
Σ Pr ( - (xx)) + / j= m,
where 2 =1= 1..., n (suppressing the dependence of the index on j) is the sub-sample on the j-th machine. We assume N/m is integer and m is allowed to diverge with N. The final distributed estimator is given by
+ Let C ()) + (30, 11), L(F) = ((z,))((=)ddx(()) and define C, : L²( 1)) (,, 1)), (,) [ K()=))(<> (f.))))
where (0)xx) is the conditional density of e == y fo(z,) at O. We will assume that (0)xz) is bounded away from zero and infinity for all x and thus the properties of L and L. are almost identical for our purpose. We assume C is compact and has the spectral decomposition L - Σ xo
=== رررء @ Φj. where $ 2 $2 2 .... 0 are the eigenvalues and oy are the eigenfunctions. We assume the following smoothness condition on the true fo
fo =o C" for some g E H.r E 10, 1/2].
(3)
Assumption (3) is often referred to as the "source condition" in the literature. L" is defined as the operator Σ, o & Φj. The condition can be written more explicitly follows. By Lemma 1.1.1 of Wahba (1990), any g E H can be written as g = -E with 0 < co, and C g E, 00 Thus the assumption is the same as /o
1- < <0, where foz = (fo. Q3)
1+2r

---

is the Fourier coefficient of fo in the expansion. Since 8, - 0, larger r implies faster decay of faj. and the decay rate of the Fourier coefficient naturally characterization of its smoothness in functional analysis.
We establish the error bounds for the central regularized quantile estimator well the distributed estimator. For the central estimator, although quantile regression has been studied in several works such Li et al. (007): Zhang al. (2016), these works simply assume f E H. and does not impose the additional assumption (3). As for the least squares regression (Caponnetto and De Vito 2007), lead faster rates. However, different from the least squares case which relies on the closed-form form solution of the regularized estimator, taking into account the assumption (3) requires entirely different technical tricks.
such a regularity condition expected
Throughout the paper, C' denotes generic positive constant. The following assumptions are used.
(A1) 8, S Cj-a a for some > 1. The smoothness assumption
3 holds.
(A2) We have the entropy condition log,V ((1), L.c) (C/e)3/o, where H(1) {f e : If S 1).
(A3) (Sup-norm assumption) |1 - -1 Vf H.
(A4) The conditional density of e = y fo(x)) given z, denoted by ((|=x), and its derivative are uniformly bounded. 7(0/x)) is bounded away from zero uniformly for x E [0, 1].
The assumption (A1) on the polynomial decay of cigenvalues is commonly assumed in the literature. The entropy condition (A2) stronger than assuming 8; S Cj-a. Such an assumption is not uncommon and used in Müller and van de Geer (2015). Theorem 6.26 of Steinwartt and Christmann (2008) showed that is satisfied if the RKHS has kernel with derivatives of sufficiently high orders. The sup-norm assumption is also used in Steeinwart al. (2009): ; (Szzuki and Sugiyama (013), which yields a better control for the sup-norm of a function in the RKHS. The sup-norm assumption is satisfied if the RKHS is Sobolev space is continuously embeddable in Sobolev space.
Assumptions (A1)-(A4) are required for the proof for the distributed estimator. For the central estimator, we can remove (A2) and (A3) and add the following assumption.
(A2') For some sufficiently small constant a > 0, Elp, (y f())) Elp fo(x))] N C'Il- - foll", vf Ilf - foll I u, fl ffol=-flll < 1.
Assumption (A2') is strong convexity condition of the population loss. can be shown that (A2') is
implied by (A3) and (A4). It also holds if the conditional density 7-1xx) is uniformly bounded away from zero ((A4) only requires (00(a)) is uniformly bounded away from zero). The following result gives the bound for the central estimator.
Theorem Assume (AI), (A2') and (A4) hold. Setting X x N (2r+1)a-1 we have |l - foll =
(2++1l
ON
We first state lemma on the relevant empirical process. The proof relies on the Rademacher com- plexity E[sup / $1 E (x;)), where a, E (-1, are i.i.d. Rademacher variables. The Rademacher complexity is characterization of the complexity of the function space. As shown in Mendelsonn (2002), we have a bound
N (xf(x))) (R),
sup 1 SullllsI
where R²(u) V N
E min(sj,u?] v2). When S Cj- it is easy to see R* S C'R(u) with
R(u)= = 1
VN
3

---

Lemma For any with R(u)= I w. with probability at least - CCNR2
N Σ (pr(ys f(x))) pr ff((x)))) - Elp-(y f(x)) pr fo(()))]
1
< C R(w) foll CR(u)llf fullue, Vf E H.
Sketches of Proof of Theorem 1. We prove by way of contradiction. Assuming || foll is large, we try to establish
1 N - ((x))) AIIII
1 N Ep-(u= - (o(=))))))))))))) Allfoll
which will contradict the fact that iis the minimizer of the penalized loss. The difference of the quantile loss on the two sides is approximated by its population version with the help of Lemma and bounded below by assumption (A2'), while the difference of the penalties are carefully bounded by nontrivial application of Young's s inequality for operators, taking into account the source condition.
Proof of Theorem In the proof choose that satisfies R(u) u2+2r (that is, N 12 since R(u) u ul =
By way of contradiction, suppose IIF foll3 2 Lu2(1+2r)) for some sufficiently large constant This means
- ((x)) AIlI 1 E -o(x)) - < <.
inf II La
Allool
2.
N
By the convexity of the functional in f in the above, have
1
inf II
Σ pr (vn f(x))) + Allfll N E - fo(a,)) -\1lo)))) < 0. (5)
(22(442)) (a2-22)) N
On the other hand, by assumption (A2') and Lemma with probability at least 1 e 2- (note
2u
N Nu4thaftt - 20),
Cllf foll Elpr(y - [x))] (y - fo(x))]
< Allfoll Alls 1 + Cu Cu-'R(()) RRu))ls foll + CR(u)lls - foll
-2( fo'N Allf foll +Cu foll CR(u)llf follx
x Cx (If foll + f
Alff - folli
foll +Cu +Cu- R(u))) -6l + CR(u))ls f
< CA " f +oll+ + X
1 |l- folla. ^1I.f foll
+Cu - R(u)]ls (Cu') - foll + R2(w) + 7 |l foll
s C( R(u)
+ + 4 || foll + CA 1+2
Cx1+2 + +0 R2
Cu CuLt2r1ff - foll 24r
(6)
In the 5th line above, used that
If f - fo)
>|(LT g, f so)ml
Algg CT -fo)/al
c - fo)lm
S
Cxt+r V(S - fo. ((1 2r) + 2r - fo))
Cx - -foll * -follx

---

where the first line used assumption (3,, and the second to last line used Young's inequality for
positive operators A1-2r _ < (1-2r) 2 + 2rL (6) implies f S Cuu Cu-+2 +2r contradicting
Il - foll = 2+r for I. sufficiently large, and the proof is complete.
The rate obtained for the central estimator is the same as the rate obtained for kernel ridge regression in Capaonnetto and De Vito (2007); [in et al. (2017) and thus cannot be improved in general. However, the proof of Theorem [ does not yield clearly any bias and variance terms separately. As mentioned in the introduction, separate control of bias and variance is usually the key step in obtaining the learning rate of the distributed estimator. The empirical process of Lemmal I cannot be utilized to get the approximate bias and variance terms, although such type of empirical process was popularly used in the literature (Belloni and Chernozhukov] 2011 [i et al. 2007: Lv et al.] 2018). To deal with this problem, for the distributed estimator, we use the empirical process techniques not on the difference
of the quantile loss as in Lemma [] but instead on a higher-order difference taking into account the gradient of the loss also, resulting in what we will call the second-order empirical process. This will allow us to approximate the quantile loss by a weighted least squares loss, with results on distributed learning for the latter available from the literature (after minor modifications).
More specifically, we define g(2, y, f) - Pr - f())) - (v - fo())) + (T- Ky- fo(x) < (})( fo (.)). If the loss were differentiable, would be the residual in the first-order Taylor's expansion of the loss. For notational simplicity, we denote e
Ife I 0} with e = y fr( The key lemma that controls the difference between the quantile estimator and the weighted least squares estimator is the following result involving second-order empirical processes. Due to the use of an additional term (T Ky- fo(z) S (f(z) fo (x)) representing the first-order expansion in g, the bound in Lemma is typically much smaller than that Lemma for risk difference.
Lemma 2 For any u (0, 1). with probability 1 - exp(u 25/03 where s = 2/2
1
>
1,
20
ut
1/a
u 111a
2/a
sup I fol #11
(Pr - P)9(x, sc
Based on Lemma we can prove our main result for the distributed estimator. It is shown that under suitable conditions, the learning rate for the distributed estimator matches that of the central estimator.
Theorem Under assumptions (A1)-(A4) setting A
X
when m
X
N
min
a (1244))) (8r42)44254)
2a (2
1, we have soll O, 2ul2r 1TTZ).
((2r11)
Remark 1 We note that, unfortunately, the exponent here is quite messy, and the first term in 20r
min! I a (2x+1))(88++ +2-+
aa(2++1441 can be either bigger or smaller than the second term (since the explicit expression on when the first term is bigger is quite messy we do not choose to write it down). Also the expression (2r + 1) (8r + 2)a + 2r + 1 may not even be positive (if it is not positive, the bound becomes void). It is positive if a 2 3.
(2-(24+))2
_ we can show that fy which minimizes the regularized empirical loss can be well-approximated by Fy that minimizes the sum of three terms: ((([(())oo(<<))) (the first-order term in the definition of g). the Tikhorov regularization term, and the second-order term from Taylor's expansion of the expected loss. By definition fú is a weighted kernel ridge estimator and the statistical bound for its average over m machines can be more easily established. However, rigorous establishment of the closeness of ʃ, and f, requires more detailed analysis involving multiple applications of Lemma 2
Sketches of Proof of Theorem 2. From Lemma
Proof of Theorem
2
By Knight's identity that pr (x y) - pr (x) = -y(y---ff - S + (1 S
t} 1f S 0}) dt,, we have
(a(u) - Eprly - fo(x)) E | ((0) fo(x)
Pg(x, v.
F(t[z) F(0)z)
= (b(00))(((())) -
1
fo(x)))1)
2
2 (F (0))))++0,,,a--00
5

---

using EI(f(x) F(.(z) is the conditional edf of E = -- folx).
foll fo(x))) and the sup-non sup-norm assumption, where
Let fj be the minimizer of {E(r()==(((()) - fo(x)) + Pa(((()) - fo(x))e) + AIfl This is basically the least squares problem when the true model is given by y fo(x) + with two differences. One is that the loss weighted by 70(rz) and the other is that the first term is the population counterpart of (f(()))) fo(a;)))² n.. It is easy to see that fy has a closed form f, = (C,, + C, + (C,, + A) 2nh ( If ([)(O))(((()) - fo(z)) by E, (r(0),,))()(z) fo(xx))))² /n, the minimizer would be fj (Cn, + + fo + (Lay 2) Ex=1 ((((..)) where Zay, defined as Larf f E (I .). is the empirical version of L.. We can see analysis of ʃj would be similar to (and actually simpler than) the analysis of Jj. and the latter basically the problem studied in Lin al. (017)), since we assumed (0(z)) is bounded away from zero and infinity and it makes difference in statistical analysis. In
is replaced
a
particular, by Corollary 11 Lin al. (0117), we can get |/ Σソ= J, foll Op(N (1r+1)-)
o(2r=1)
m S N No Furthermore, by combining Corollary 8 and Lemma 21 of Lin al. 2017 we
also get the local estimates satisfy IIβ, foll Op( NN /1+++100+
Now we bound
I F5ll- For simplicity of notation, define the function h(u) = 13-1/a (1)
1/a 1/o
By Lemma and
for any f H. with |lf foll S Cu and |f follx 1,
1
Σ (m - f(xx)) 1 Σ (Bi - fo(a:)) + 1 Σ (T - Ke s (f)((()))) - fo(zz)
- -((0)))))))))
2
< Ch(u).
N Naterthaat1
Let u1
then
Vn
1 Eurmm - - - 1 -pr fo(x)) + E( + Her s ())( fo(x))
1
{ }
2
< Ch(un).
Taking the difference of the two displayed above,
Epr(v f(x)) + 1 Ep.u - Fx())) + AIE
E( -Tes s {0))((())) - -T(()))
+ P((0)))(())) - fo(=))) 2 (h(02))(()))6666)00 ((h(u)+(uu)))
A115 l
(8)
Since J, minimizes 1 P (=(0)))((()) so())) 1 (Ee(((()) so(x:)) + 1 the first
order optimality condition for f, yields
a K( Ex0000001110000000))).)(.))))111 = 0.
(9)

---

Thus we have
2 P(((0))(()) fo())) (()(0)))((00)) - fo(x)))3 -6(0)))))
E (.(s(x)))))) - -f(s))
(f F(=)) (l((0=)(((()) - -)())))))) - fo(z))
- Σ ((f(a))) -(,())
= 2 ( + - - ()(0)))))) (() (o(=))
- - 13 -
Σ K (wi, )
(f(()))(((zz)
Fym.
2
where the last step used
(9. Using this in
8 we get
p Pr f(z f(x))) Allfll 1 Σ
EE pr f)(()))) 1l
n
n
- - - TJYN A115 -
-
Σ -((u - f(x:)) All5112 + 1 Σ ---(0--7(t))
- -3,(2:))
+ >1155
=
1 {f( - F)(0)) + -1Iff F1l
C(h(u) + h(wi)).
(10)
Note that this U2 is the value of u that makes u² x h(u). Let W3 (h(w)) + h(w2). Suppose : (f=(0)=)({} - [=])) + - ク
Let U/ = n
2 Lug for some I, sufficiently large. By (10). and using the same arguments as in the proof of Theorem [ that lead to (5) there exists some f E H with (+ [=
AlIʃ - / = Lug. and also
satisfying , E, P f(x))) AIll s E. pr (y (xx)) Al ll such that
] (f())=)(((()) (z)) Alf F S C(h(V + h(u1)).
1
2
Because the left hand side above Luz, this would lead to contradiction if L is large enough. To see this, we note that Lu3 > Ch( (V[ugg since ug > / //(u)) = U2 and also Lug Ch(u)) since u/z = ((w1) ) + h(u2)) h(u1).
Based on the previous arguments, we then have 115, Fyll S Cug. Finally, the distributed estimator satisfies
|l foll E, 5
Σ, | Ej foll E, J, m
max |1; 85ll
foll-
Zur - the second term above has the optimal rate 1 Σイ F, foll = ON 22(+11)
As mentioned before, when m
To obtain the same rate for I|f folls we would re-
quire
o(2+11)
4- 40-1
< N
(II)
7

---

a (2 (Bm-)))
Using n = N/m, is equivalent to saying m I N (2-(2r) 13) [a
In summary, if
min (2 1) (2mt 2n 202(ar+))+2 1o(2++1)+]
20r
m S N
the optimal rate is achieved.
Remark 2 As stated in the theorem, for J to achieve the same rate as the non-distributed estimator,
min (2 (or++)))((++))aa4 (8+42)a+2+41
1141-1141 J. On the other hand, from the proof, we have the convergence rate N 2x + (N/m) 44440 even if the bound for m is not satisfied (when the bound not satisfied, we just have non-optimal rate). In practice, of course it is hard to check whether specific pair (m, N) satisfies the bound since it is asymptotic in nature. On the other hand, in the setting that data are physically located on m machines and one is unwilling to share data across different machines, then we have no other option and just accept this given m. In this situation, we do not have to be concerned with the choice of m.
we need the constraint m. S N
22r 1)
2(1
3 Some numerical illustrations
Here we illustrate the distributed quantile regression in relatively simple simulations. For a value E (0, 1), the sample is generated from the model y: = fo(=;)) + (1 (1+1;)000 2;)0((G (-)(r), where I; are generated uniformly on [0, 1], e ~ NN. 1). + is the quantile function of the standard normal distribution so that f(x; is indeed the conditional r-quantile of yt- We set fo(z) = sin (222z) and o 0.5. The simulations are carried out for different combinations of E (32, 64, 128, 256, 512, 1024) and m E 2, 8, 16, 32), with the total sample size of N nm.. Note that m = actually corresponds to the central estimator. For the RKHS, we use the Sobolev space of the second order. The tuning parameter À is chosen to minimize the errors on independently generated test data, In each setting, 100 repetitions are used to compute the average squared estimation error []f fo 1o
Choice of À is an important practical matter. Theorem 2 shows the choice of X ~ N fa-rf depends on the total sample size N, which indicates that tuning parameter chosen based on local data is not optimal. In our simulations, we use independently generated data to select the optimal À that ensures f (f implicitly depends on A) is the one that achieves the smallest prediction error on the test data. When independently generated data is not available, either hold-out data or global K-fold cross- validatiin can be used, which requires coordination of the central machine. If the hold-out data is maintained by the central machine, the central machine can evaluate and compare different values of X. If K-fold cross-validation is carried out on the local machines, the central machine needs to send / back to the local machines that the local machines can calculate the cross-validation errors, and then send the errors to the central machine. This needs to be done K times for K-fold CV. [u let al. (2018 2019) developed generalized approximate ross-validation criterion in the saustssuaarss case and established its asymptotic optimality. We expect that similar criterion developed for quantile regression (Yuan| 2006) can be adapted in our case. However, even in the non-distributed setting, Yuan (2006) did not establish the asymptotic properties of the criterion, mainly investigating its performance from a computational viewpoint. Thus remains an open question whether such a criterion has a desirable asymptotic property. The investigation of such problems requires additional study by itself and thus we do not use this in the current work.
The simulation results are shown in Table for 7 = 0.5. We can examine the table in several ways. First, each row of the table indicates what happens when one fixes the number of observations each machine while increasing the number of machines (the total sample size of course also increases). In this case, we see the errors decrease with the number of machines since the total sample size increases. Second, each column of the table indicates what happens if the number of machines are fixed while the number of observations increases proportionally with the total sample size. Here we also see the error decreases. Third, the results along the anti- anti-diagonal directions shows the results when the total sample size N fixed while we change the number of machines m. For example, the numbers shaded in yellow all corresponds to N = 512 while the numbers shaded in blue corresponds to = 1024. Here we see that the error in general increases with the number of machines (up to some random fluctuations). This is natural since the central estimator should perform best if it is feasible to compute. Finally, we observe that the table shows the divide-and-conquee strategy is useful when N is large. For example, in the table, the smallest error is achieved when 1024, m 32,
8

---

Table I: The estimation errors for different pairs of (n1, m) when 0.5. N nm.
The total sample size is
1
4
8
16
32
72
32
2. 2.765
1,211
0.898
0.466
0.316
0.221
64
1.226
0.653
0.371
0.221
0.108
0.062
128
0.616
0.386
0.229
0.099
0.053
0.023
256
0.346
0.199
0.105
0.058
0.029
0.013
512
0.186
0.086
0.046
0.020
0.011
0.008
1024
0.089
0.047
0.020
0.010
0.008
0.004
corresponding to N = 32768. It would be hard to deal with such a large sample size in the standard implementation (the kernel method always computationally burdensome) without using some advanced techniques to approximate the solution, if such techniques exist at all.
The simulation results for other values of presented in Appendix A. We also perform an additional simulation with 3-dimensional predictors in Appendix B.
Conclusion
In this paper, we established the convergence rate of the nonparametric quantile estimator in the distributed learning setting under the RKHS framework. The second-order empirical process allows us approximate the estimator by the estimator obtained from a weighted least squares problem. which in turn has explicit bias and variance decomposition as done in the existing literature. However, the theoretical drawback here is that this strategy currently does not allow us obtain the optimal rate for the entire range E (1, oo) (we require a to be sufficiently large). It may be the case that some other entirely different proof strategy is required to get more elegant result.
In practice, it is always hard to estimate extreme conditional quantiles with T very close to 0 or 1. For any fixed f in the open interval (0, 1), do not have theoretical problems since always require m to be much smaller than N and thus typically the local sample size ı N/M is still quite large in the big data setting. Theoretically, the statistical convergence rate inversely depends on the density (this is well-known in the parametric setting, although in the nonparametric setting we are not aware of explicit mentioning of this in the literature). At the tail of the distribution, the density is typically small and thus the statistical error is large, which can also be seen from our simulation results for т 0.1 and 0.9 in the Supplementary Appendix. Extreme conditional quantile regression is a separate discipline of its own and has been studied, for example, in [Chernozhukov and Du (2008); Wang et al. (20T2): Wang and Li (2013). However, even in the dintiiitdb setting we are not aware of any theoretical study of this problem in the framework of RKHS and it remains unclear whether some techniques can adapted to this setting.
Acknowledgments and Disclosure of Funding
This project is partially supported by NSFC Project 1 11871411 at the Shenzhen Research Institute, City University of Hong Kong, and partially supported by the Hong Kong Research Grants Council (RGC) General Research Fund under Grant 11300519, 11300721, 11311821 and 11301423.

---

References
Balcan, M.-F., Liang, Y. Song, L., Woodruff, D., and Xie, B. "Communication efficient distributed kernel principal component analysis." 0503:0/503.0685 (2015).
Belloni, and Chemozhukov, V. "Il-penalized quantile regression in high-dimensional sparse models." The Annals of Statistics, 39()):2-130 (2011).
Caponnetto, A. and De Vito, E. "Optimal rates for the regularized least-squares algorithm." Founda- tions of Computational mathematics, 7(3):331-368 (2007).
Chang, X., Lin, S.-B., and Zhou, D.-X. "Distributed semi-supervised learning with kernel ridge regression." Journal of Machine Learning Research, 18:1-46 (2017).
Chen, X., Liu, W., Mao, X., and Yang, Z. "Distributed high-dimensional regression under quantile loss function." Journal of Machine Learning Research, 21:1-48 (2020).
Chernozhukov, V. and Du, S. "Extremal quantiles and value-at-risk." In The New Palgrave Dictionary of Economics (2008).
Guo. Z. C.. Lin, S. B., and Zhou, D. X. "Learning theory of distributed spectral algorithms." " Inverse Problems, 77:074009 (2017).
Jordan, M. I., Lee, D., and Yang. Y. "Communication-effiiiii distributed statistical inference." "
Journal of the American Statistical Association, 114:668-66 (2018).
Koenker, R. and Bassett Jr. G. "Regression quantiles." Econometrica: Journal of the Econometric Society, 1(46):33-55 50 (1978).
Koltchinskii, V. Oracle inequalities in empirical risk minimization and sparse recovery problems. New York: Springer (2011).
Lee, J. D., Liu, Q., Sun, Y., and Taylor, J. E. "Communication-efficceen sparse regression." Journal of Machine Learning Research, 18:1-30 (2017).
Li, Y., Liu, Y., and Zhu, "Quantile regression in reproducing kernel Hilbert spaces." Journal of the American Statistical Association, 102:255-266 (2007).
Lian, H. and Fan, Z. aevvide-and-coqque for debiased 11 11-norm support vector machine in ultra-high dimensions." Journal of Machine Learning Research, 1:1-26 (2018).
Lin, S.-B., Guo, X., and Zhou, D.-X. "Distributed learning with regularized least squares." Journal of Machine Learning Research, 18:1-31 (2017).
Lv, S., Lin, H., Lian, H., and Huang, J. "Oracle inequalities for sparse additive quantile regression in reproducing kernel Hilbert space." Annals of Statistics, 46:781-813 (2018).
Mendelson, "Geometric parameters of kernel machines." In International Conference on Compu- tational Learning Theory, 29-43 (2002).
Müller, P. and van de Geer, S. "The partial linear model in high dimensions." Scandinavian Journal of Statistics, 42:580-608 (2015).
Pollard, D. Convergence of stochastic processes. New York: Springer-Verlag. Verlag (1984).
Rosenblatt, J. and Nadler, B. "On the optimality of averaging in distributed statistical learning." arXiv:1407.2722 (2015).
Steinwart, I. and Christmann, A. Support vector machines. New York: Springer (2008).
"Estimating conditional quantiles with the help of the pinball loss." Bernoulli, 17:211-225 (2011).
Steinwart, I., Hush, D., and Scovel, C. "Optimal rates regularized least squares regression." In COLT 2009 The 22nd Conference Learning Theory (2009).
10

---

Suzuki, T. and Sugiyama, M. "Fast learning rate of multiple kernel learning: Trade-off between sparsity and smoothness." The Annals of Statistics, 41:1381-1405 (2013).
Volgushev, S., Chao, S., and Cheng, G. "Distributed inference for quantile regression processes." Annals of Stafistics, 47:1634-1662 (2019).
Wahba, G. Spline models for observational data. Philadelphia, PA: Society for Industrial and Applied Mathematics (1990).
Wang, H. J. and Li, D. "Fstimation of extreme conditional quantiles through power transformation."
Journal of the American Statistical Association, 1066503) (2013).
Wang, H. J., Li, D., and He, X. "Estimation of high conditional quantiles for heavy-tailed distributions." Journal of the American Statistical Association, 107(500):1453-14444 (2012).
Xu, G., Shang, Z., and Cheng, G. "Optimal tuning for divide-and-conquer kernel ridge regression with massive data." " In 35th International Conference on Machine Leurning, ICML 2018, volume 12, 5483-5491 (2018).
"Distributed generalized coss-validation for divide-and-conquee kernel ridge regression and its asymptotic optimality." Journal of Computational and Graphical Statistics, 28(4):891-99) (2019).
Yuan, M. "GACV for quantile smoothing splines." Computational Statistics and Data AnalysisData Analysis, 50(3):813-829 (2006).
Zhang, C., Liu, Y., and Wu, Y. "On quantile regression in reproducing kernel Hilbert spaces with the data sparsity constraint." Journal of Machine Learning Research, 1-45 (2016).
Zhang, Y., Duchi, J. C., and Wainwright, J. "Communication-effccieen algorithms for statistical optimization." " Journal of Muchine Learming Research, 14:3321-3363 (2013).
"Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates." Journal of Machine Learning Research, (6:3299-33444 (2015).
Zhao, W. Zhang, F., and Lian, H. "Debiasing and distributed estimation for high-dimensional quantile regression." IEEE Transactions on Neural Networks and Learning Systems, 31:2569-2577 (2020).


Reviews:
[{"review_id": "owAgXQQ2KNC", "reviewer": "Reviewer_FH6t", "summary": "\n This work is focus theoretically on the distributed learning of nonparametric quantile regression models in RKHS. \n \nThere have been related works about the distributed learning for kernel ridge regression and also the non-distributed learning for quantile regression in RKHS.  The main idea of this paper is to approximate the quantile loss by a weighted least squares loss, then the quantile estimator can be estimated by the weighted least squares estimator.   Based on such approximation,  the authors prove the learning rates for the nonparametric quantile regression learning.", "questions": "\nQ1: The quantile level $\\tau\\in (0,1)$, however in the illustration section,  there are only results for $\\tau = 0.5$ and $\\tau =0.8$. Could you please provide more results for the entire range of $\\tau$ , say setting $\\tau$ 0.1 0.2,...0.8,0.9?\n\nQ2:  What is the performance of this proposed method on real dataset? Quantile regression is a very classical problem and there should be many practical datasets, which have been used in the existing works, to illustrate the distributed quantile regression. \n", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The ideas and logic of this paper are very clear and easy to follow. However, the format (especially for all the detailed proofs) seems not formal.The manuscript will benefit from reorganizing the proof details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lSQs_XWDknn", "reviewer": "Reviewer_LF2z", "summary": "The authors study distributed learning of nonparametric conditional quantiles with Tikhonov regularization in a reproducing kernel Hilbert space (RKHS). The authors establish the risk bounds using a second-order empirical process for quantile risk under the simple divide-and-conquer approach that partitions the data set into multiple parts and then takes an arithmetic average of the individual outputs. ", "questions": "1. My main concern is in the estimation efficiency when \\tau is large/small. When \\tau is large/small, the observations located on the tail of the distribution may have a large influence on the estimation results. However, when dividing the sample into multiple groups, such observations may be very few or even totally missing in the subgroup. In other words, the distribution of the subgroup is no longer the same/similar to the full, and the local estimation may be unreliable. How to deal with such cases in the divide-and-conquer approach for quantile regression?\n\n2. Is there any discussion on the number of nodes m in the algorithm?\n\n3. The experiments only consider the one-dimensional case. How about when the dimension of x increases?\n", "limitations": "The work shows the results for \\tau=.5 and \\tau=.8 for the one-dimensional case. It is better to discuss more cases for more choices of \\tau and dimension.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The manuscript includes enough information needed to support the claims it makes. The proposed method is novel in the sense that the authors investigate the theoretical underpinning of the divide-and-conquer strategy for distributed learning of nonparametric quantile regression models.  The method focuses on only an individual value of \\tau without modeling different quantiles jointly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e5lqvgQTrrB", "reviewer": "Reviewer_TorZ", "summary": "This paper establishes the risk bounds for the divide-and-conquer version of the kernel ridge quantile regression estimator when the reproducing kernel has polynomially decaying eigenvalues. To prove the risk bounds, the paper introduces a novel second-order empirical process for quantile risk that can be used to establish a link between the quantile regression estimator and a regularized least-squares retrogression estimator.", "questions": "The paper is purely theoretical and introduces a theoretical new device (second-order empirical process) that can be potentially useful for other related problems. However, from a methodological point of view, the paper does not produce any change to the current practice of divide-and-conquer estimation for quantile regression in RHKS. \n\nFrom a practical point of view, the tuning parameter $\\lambda$ is of critical importance and the new theoretical device can potentially be used to derive a data-driven criterion for the selection of $\\lambda$, following similar approaches in [1], [2] and [3]. At least some discussions in this direction may strengthen the paper from a practical point of view.\n\nMinor point: Please clarify the meaning of the notation $\\mathcal L^r $ in equation (3).\n\n[1] Xu, G., Shang, Z. and Cheng, G., 2018, July. Optimal tuning for divide-and-conquer kernel ridge regression with massive data. In International Conference on Machine Learning (pp. 5483-5491). PMLR.\n\n[2] Xu, G., Shang, Z., and Cheng, G. (2019). Distributed generalized cross-validation for divide-and-conquer kernel ridge regression and its asymptotic optimality. Journal of computational and graphical statistics, 28(4), 891-908.\n\n[3] Yuan, M., 2006. GACV for quantile smoothing splines. Computational statistics & data analysis, 50(3), pp.813-829.", "limitations": "none", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the proposed approach is novel by introducing a new theoretical tool that may be useful for other related problems.\nWeaknesses: the paper is purely theoretical and lacks practical considerations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DLj9EmH5-6B", "reviewer": "Reviewer_oHGh", "summary": "The work focuses on analysis of distributed learning of nonparametric conditional quantiles with Tikhonov regularization in RKHS. A difficulty in this setting is decomposing the mean squared error into bias and variance terms; a necessity for establishing rates in the divide-and-conquer setting of distributed learning. The authors suggest combating this via approximating the quantile loss by a weighted square loss through a second-order empirical process where an explicit solution to the bias and variance terms is available. Furthermore, the authors suggest approximating the loss leads to approximating the estimator. Through this regime, learning rates for the central and distributed estimators are analyzed. The paper concludes with a simple numerical illustration demonstrating the efficacy of the divide-and-conquer method.", "questions": "I have no questions regarding the technical details of this work as it is not my area of expertise.", "limitations": "The work is theoretical and has no immediate potential negative societal impact. Limitations such as requiring $\\alpha$ to be sufficiently large in their analysis were mentioned by the authors.", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The subject of the paper is not my expertise, so I will leave validation of the mathematics to the other reviewers. Instead, my main concern of this work is that the presentation of the results is rough and seemingly rushed. The paper is mathematically dense and thus rather difficult to follow. The bulk of the main paper is composed of theorems/lemmas followed by their proofs with little explanations in between results for clarifications. The problem tackled in this work appears to have some significance as a thorough study of the risk bounds for quantile risk in the RKHS with the distributed learning setting is to my understanding not well studied. Lastly, the numerical results illustrate the efficacy of distributed learning in this setting, but it appears to be tangential to the analysis of the learning rate which was the focus of the bulk of the work (although the authors have brought up this concern).\n\nMinor: syntactic - in the inequality and equality below line 180 and 183 respectively, replace $(1/2)$ with $\\frac{1}{2}$. Same issue with $(1/N)$ in the inequality below line 111, 112, 118.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept