Distributed Least Square Ranking with Random Features
Authors: Rong Yin
Yong Liu
Weiping Wang
Dan Meng
Venue: Submitted to ICLR 2023 (2023)
Keywords: least square ranking
distributed learning
learning theory
random features

Abstract: In this paper, we study the statistical properties of pairwise ranking using distributed learning and random features (called DRank-RF) and establish its convergence analysis in probability. Theoretical analysis shows that DRank-RF remarkably reduces the computational requirements while preserving a satisfactory convergence rate. An extensive experiment verifies the effectiveness of DRank-RF. Furthermore, to improve the learning performance of DRank-RF, we propose an effective communication strategy for it and demonstrate the power of communications via theoretical assessments and numerical experiments.

Under review as a conference paper at ICLR 2023
DISTRIBUTED LEAST SQUARE RANKING WITH RANDOM FEATURES
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we study the statistical properties of pairwise ranking using dis- tributed learning and random features (called DRank-RF) and establish its con- vergence analysis in probability. Theoretical analysis shows that DRank-RF re- markably reduces the computational requirements while preserving satisfactory convergence rate. An extensive experiment verifies the effectiveness of DRank- RF. Furthermore, to improve the learning performance of DRank-RF, we propose effective communication strategy for it and demonstrate the power of commu- nications via theoretical assessments and numerical experiments.
INTRODUCTION
Distributed learning has attracted much attention in the literature and has been widely used for kemee learning in large scale scenarios (Zhang al., 2013; Chang al. 2017: Lin et al. 2020b). The distributed kernel learning has mainly three ingredients: Processing the data subset in the local kernel machines and producing local estimator; Communicating exclusive information such as the data (Bellet et al. 2015), gradients (Zeng & Yin 2018) and local estimator (Huang & Huo 2019) between the local processors and the global processor; Synthesizing the local estimators and the communicated information on the global processor to produce a global estimator. Note that, in the divide-and-conquer learning, the second ingredient communications is not necessary. In the terms of practical challenges and theoretical analysis, the distributed learning has made significant breakthroughs in the multi-penalty regularization (Guo al. [2019), coefficient- based regularization (Pang & Sun 2018). spectral algorithms (Mücke & Blanchard 2018 20TT8 Lin et al.) (020a)). kernel ridgel regression (Yin et al., 2020. 2021). and semi-supervised regression (Li et al. 2022). All the above are restricted to pointwise kernel learning. However, the distributed learning in pairwise kernel learning still has a long way to go. The existing distributed pairwise learning (Chen et al. 2019 2021) has high computational requirements, which motivates us to explore theoretic foundations and efficient methods for pairwise ranking kernel methods under distributed learning.
Random features methods (Rahimi & Recht 2007 Carratino al. 2018 Liu al. 2021 have long and distinguished history. which embed the non- non-linear feature space (i.c. the Reproducing Ker- nel Hilbert Space associated with the kernel) into low dimensional Euclidean space while incurring an arbitrarily small additive distortion in the inner product values. This enables one to overcome the high computational requirements of kernel learning since one can now work in an explicit low di- mensional space with explicit representation whose complexity depends only on the dimensionality of the space. Random features have gained rapid progress in reducing the complexity of the ker- nel ridge regression (Liu et al.) (021)) and semi-supervised regression (Li et al. 2022) However, it remains unclear for complexity reduction and learning theory analysis to the distributed pairwise ranking kernel learning.
In this paper, to reduce the computational requirements of pairwise ranking kernel learning, we investigate the method of combining distributed learning and random features for pairwise ranking kernel learning, called distributed least square ranking with random features (DRank-RF), to deal with large-scale applications, and study its statistical properties in probability by integral operators framework. To further improve the performance of DRank-Re RF, we consider communications among follows: 1) We construct different local processors. The main contributions of this paper performance of the distributed a novel method DRank-RF to improve the existing state-of-the-ar pairwise ranking kernel learning. This work is the first time apply random features least square

---

Under review as a conference paper at ICLR 2023
ranking and derive the theoretical guarantees, which is new exploration of random features in least square ranking. In theoretical analysis, we derive the convergence rate of the proposed method, which is sharper than that of the existing state-of-the-ar afrt distributed pairwise ranking kernel learning (See Theorem [). In computational complexity, DRank-RF requires essentially (m (Dy)) time and (mm)D))) D2I) memory, where m is the number of random features, m < DPyl and Dyl is the number of data in each local processor. The proposed method can greatly reduce the computational requirements compared with the state-of-the-art works (See Table D. Experimental results verify that the proposed method keeps the similar testing error as the exact and state-of- of-the-art approximate kernel least square ranking and has great advantage over the exact and state-of-the of--the-attttttt approximate kernel least square ranking in the training time, which is consistent with our theoretical analysis. 2) We propose a communication strategy to further improve the performance of DRank-RF, called DRank-RF-C. Statistical analysis shows that DRank-RF-C obtains faster convergence rate with the help of communication strategy than DRank- -FF. And the numerical results validate the power of the proposed communication strategy.
The paper is organized as follows:
In section we briefly introduce the least square ranking problem and the distributed least square ranking. In section B introduce the proposed methods. Section 4 shows the theoretical analysis the proposed DRank-Rt and DRank RF-C. In section [5] we compare the related works with the proposed methods. The following sections are the experiments and conclusions.
2 BACKGROUND
There is a compact metric space 2 : = (X.J) C R9+1, where X' C R2 and y C [-6, b] for some positive constant b. The sample set D := {x, D1) b)) of size N = |D] is drawn independently from an intrinsic Borel probability measure p on 2. ply|X = x) denotes the conditional distribution for given input The hypothesis space used is the reproducing kernel Hilbert space (RKHS) (Hx) associated with a mercer kernel K : X' x + R (Aronszajn) 1950). We will denote the inner product in HK by (,,)), and corresponding norm by || |x.
2.1 LEAST SQUARE RANKING (LSRANK)
Least square ranking (LSRank) is one of the most popular learning methods in the machine learn- ing community (Chen 2012 Zhao et al. 2017 Chen al. 2019). which can be stated as fD.
arg min {fD(f) + A I and Ep(f)
Σ kik== (3i yk (f (xx) (xx)))
where the regularized parameter À 0.
The main purpose of LSRank is to find function f: X - IR through empirical observation, so that the ranking risk
- (f(x) - (x'))) E(f) (
dp(x. v)dp (x.,v)
(I)
can be as small as possible, where x, x' X.
The optimal predictor (Chen 2012 Chen et al.
2013
Kriukova et al. 2016) under Eq. 1 is the
regression function fx) pyl x), X
Complexity Analysis LSRank requires O(ID)3) time and O(DD?) space, which is prohibitive for large-scale settings.
2.2 DISTRIBUTED LEAST SQUARE RANKING (DRANK)
Let the dataset D = DI Dj and each subset Dj = {xx
1D5l
be stored in the j-th local
processor for 1 < j < p. The DRank is defined by
P Σ
D
fD
Σ
DA
1=1
k=
2

---

Under review as a conference paper at ICLR 2023
where the least squares ranking (LSRank) fD A arg SEH {ED,(f) + } and Pyl Ep, (f) 10,1a -ik=1
u u
(x.)
Complexity Analysis The time complexity, space complexity, and communication complexity of DRank for each local processor are ((D)) (( and D,D), where j = = -,...,? and is the number of partitions.
PROPOSED ALGORITHMS
3.1 DISTRIBUTED LEAST SQUARE RANKING WITH RANDOM FEATURES (DRANK-RF)
Here we first introduce the main properties of the shift-invariant kernel and the basic idea random
Lo t0(x w) 1b( w)bb (x', w e(w (WW if the spectral measure has density function e(-) (i et al. 2019 Carratino et al. 2018 where v X2 -> IR a bounded and continuous function with respect to w and x. The basic idea random features is approximate the kernel function K(x, x') by its Monte-Carlo estimation (Li et al.)
features. The shift-invariant kernel can be written as K ((x,x (x,x)) x')
2019 Rahimi & Recht 2007): (x,x') = 1 m i==1 10(x, ())'b('' (x)) = (Øm (x), Om (x')), mm
where 6m (x)
(+) X. w1)............. "......,,((,,,,,.
wm)) (x,,w)))"
Back to supervised learning (Chen 2012), combining random features with the least squares ranking leads to, (x) = B,, Pm x) with
B., ( (m,D W T M.D
+
-1] I) 1 m.D WDdn,
(3)
2
for 1 D VDi
(0m (x1) ... (m )), WD p
pb 1 D 1 DJ
bb)
(
1
the identity matrix dld 1|d (L,..., 1)T R | and YD-
v (11 N1.............................. B|D))
DRank with random features (DRank-RF) is defined as
P..D. = Σ 1Dz1²
S..DAAA.
(4)
3=1 EL D&l
where J,. = T Dy. Am (x) with gm. PM, W TT m. - W WD
Random features have long history and have been studied different learning, for example kernel ridge regression (Liu et al., 2021), kernel classification (Liu et al. 2022), kernel k-means (Chitta itt al. 2012). However, random features have not been studied in least square ranking. Our work is the first time to apply random features to least square ranking and derive the theoretical guarantees, which is a new exploration of the application of random features. In addition, due to the different objective functions and integral operators, the proof of proposed method is different from the existing methods (See Appendix). Finally, the proposed methods greatly reduce the computational requirements (See Table
The method of synthesis operation in Eq.(4) is to weighted average the estimated values in each local processor.
Complexity Analysis In time complexity, solving the inverse of T D, W D. D, > needs Omm²) time and computing the matrices multiplication T m, W $T m, requires O(m31D,l cost, where is the number of random features. In space complexity, the key to store $ m,, whose space complexity is (m D,l). Therefore, the time complexity. space complexity, and com- munication complexity of DRank-RF for each local processor are (m)))D))) ((m) (mnDD)) and (m)) where m < [Dyl- Not that, the computational cost of random features model is far less than m² Dyl. It is ignored when expressing the computational complexity. In the experiments, the training time of our methods includes the time of calculating the random features model.
The way of weighted averaging in Eq. 4 cannot improve the approximation ability of DRank RF in each local processor (Huang Huo 2019; Lin et al.) 20206]] (Yin et al. 202T). ) To further improve the performance, we bring efficient communication strategy into DR
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Distributed Least Square Ranking with Random Features and communications (DRank-RF-OC
Initialize: 2n B.D For 1 = to M do
Local processor: compute the local gradient G...D,.ABB,.D... and communicate back to the
global processor.
Global processor: compute Gm, (BH, = Σ, D.P D& (, in Eq. and communicate each local processor.
Local processor: compute 5 in Eq. and communicate back the global processor.
Global processor: compute S,,D,A in Eq and communicate to each local processor.
End For
MM Output: D,A
D,A and fi, (gm, (m,,D, D,A (-)())
3.2 DRANK-RE -F WITH COMMUNICATIONS IDRANK-RF-CR
In this section, we introduce the DRank-R with communications (DRank-RF-C), which can not only improve the approximation ability but also protect the data privacy in each local processor.
For any g, according to Eq. 3 one has the following equation:
D, =g
( m.
W D T D D + 1)
[ - M.D W W M.D + 1)g - &m,D Dm.DWDDP WD
2
(5)
=
c m.
W
T D +
- Gmm.D.)))..
2
where D,.,D. (
D.
④ m.
W $ T
T)
WWND
Define go
D.A
Σ}=1
D;
D Dm,
obtain that
D212
0 Dm = g
o
WD,
T D, + I] Gm.D),)(g)
(6)
Σ1 k=
DE
22"
1=1
Note that, the gradient of the empirical risk of [DI Σ (Bi yk - (g" om (x,) g" om (xx)
|||g|| on g is 4Gm,D,,.. D,.A (g) for all (x,,y.,, (Xx: Mea E D,.
Comparing 55) and (4. we consider the communication strategy based on the well-known
Newton Raphson iteration (Lin et al. 2020b; Yin et al. which is formed as:
2021 Chen et al. 2021) for DRank-RF,
D0I
1-1 D.
gi-1
Bm,
DD
f=1
where
1 HD,,
(.
(8)
G Gm, Σ D2y²²
E Dxl Gm,
j=1
HD,,A m,,, WD, TT M, + I and the number of iteration.
The method of synthesis operation DRank-RF-C {3,} of each local processor obtained in the last iteration.
weighted average the model parameters
Algorithm shows the detail of DF-C.-RF-C. In step 1, let go. D.A be 0. In the following steps, we update the global gradients and model parameters iteratively. For | = 1,..., .....,M M, we distribute D. D.A to each local processor. In step (on each local processor), compute p local gradient vee- tors Dy (gt-. and communicate them back to the global processor. In step 3 (on global
4

---

Under review as a conference paper at ICLR 2023
processor), according the received p local gradient vectors, compute the global gradient D.D D, and communicate each local processor. In step 4 (on each local processor), each local processor computes 18-1 and communicates them back to the global processor. In step (on global processor), the global processor obtains the solution B D,A Then transmit sm.. to each local processor and go back to step 2.
Complexity Analysis In the terms of time complexity, one needs to compute the inverse of Dm WD, T m,,, I and the matrices multiplication & D, W T m, once for each lo- cal processor, and one needs to solve the local gradient Dn.D and model parameter B3 in each iteration for each local processor. Thus, the total time complexity for each local processor is 1D mM D2l). where M is the number of communications. In the terms of space com- plexity, for each local processor, the key is to store e D, thus the space complexity of each local processor is (ml In the terms of communication complexity, the global processor sends the gradient D.DD. and D.D each local processor and receives the local gradient Cm.Dy.A and model parameter 83 from each local processor in each iteration. Therefore, the total communication complexity is ((mM). Note that, if the number of communications M < m, the time complexity and space complexity DRank-RF-C are the same as those of DRank-RF.
THEORETICAL ANALYSIS
Here, analyze the convergence rate DRank-RF and DRank-RF-C in probability. Define the optimal hypothesis fx in 1k as fx = arg menj {E(f) + x We assume fx exists.
4.1 CONVERGENCE RATE OF DRANK-RF
In the following, we state and discuss the convergence rate of DRank-RF probability. Theorem 1. Suppose ib continuous, such that (b(x, w)l S almost surely, T [L) As- sume that LK" So HK with 0 S where L'k is the r-th power of LK. If the reg- ularization parameter
1P1 =0 E De
and the number of random features
m 1--2(E30 En Eh-,
T#7
.for P., defined in Eq.44) and every E (0, there holds
Sm.D. - J0 =
I Ex log with confidence at least 1 5
Remark
From Theorem
mentioned above, one can see that if the number of random the convergence rate of the proposed DRank-RF which is sharper than the existing convergence rate of the state-of -hre--rr- distributed pairwise ranking kernel learning
features m is Ω ((E)
ID
EV
DEl
can reach o
((E)
1D,l
EV
(E)A EP 1DmP?
3//
Itr
(Chen al. 2027).
When the number of partitions p the convergence rate of the proposed
DRank-RF RF is O (ID)=*) with 5 (DD)
2r TTr) When |D,l = _... 1Dpl, the convergence
rate of the proposed DRank-RF is O ((1()) (L with m = Ω (( D ) Theoretical analysis
demonstrates that the proposed DRank-RF RF sound and effective.
Remark From a theoretical perspective, this paper is non-trivial extension of these approximate pairwise ranking methods. The existing papers mainly use capacity concentration estimation (Rudin 2009 Rudin & Schapire 2009: Rejchel (2012) and algorithmic stability (Cossock & Zhang 2008 Chen al. (2044) for the learning theory analysis of pairwise ranking. In this paper, apply the integral operator framework and introduce a novel technique of error decomposition so that the proposed method can achieve tight bound under the basic condition. The details can be seen in
II Logarithmic terms of convergence rates and complexity are hidden in this paper.
5

---

Under review as a conference paper at ICLR 2023
Table 1: The computational complexity of different algorithms. is the number of random features and
m < D is the number of communications, g the dimension data. |D < Dl
Algorithms
Time
Space
Communication
LSRank (Chen al. 2019)
D|3
D DjP Dj ? ml m[Dj m m[D
DRank Chen et al. 2021 2019
D 3
D QMID
DRank- CCChn et al. 2021
D 3 + IIlllII
DRank- RF (This Paper)
m² Dj
m mM
DRank-RF-C (This Paper)
m² Dj1 + mM Dj1
Appendix. This is the first time that combined distributed learning and random features in LSRank and achieved such a breakthrough.
4.2 CONVERGENCE RATE OF DRANK-RF-C
Here, we introduce and discuss the convergence analysis of DRank-RF-C in probability.
Theorem 2. Suppose is continuous, such that | w)l almost surely, т E [1) Assume that L fo E H. with < r S L, where L'g is the r-th power of Lg. If O(IDI itr),
|Di] = ... = Dp D and the number of random features m = [D] 2r
for every
E (0, 11, with confidence at least 1 - 6, we have |M.DA - fell==0 =0 ((p @ |
M+2)
Proof. The proof of Theorem I aad 2 is in Appendix.
The assumption of L fo E HK with 0 < < 1 is commonly used in approximation theory SSaale & Zhou 2007), which can be seen as regularity assumption.
Remark 3. Theoretical analysis shows that, when p < |D] ア.P the convergence rate DRank- RF-Cis is sharper than that of DRank-RF at the same settings. Note that is monotonically increasing with the number of communications M, which can demonstrate the power of the proposed commu- nications. For M + oc, it is clear that the convergence rate of DRank-RF-C is always sharper than that of DRank-RF. The convergence rate in Theorem 2 is also related to ô. To simplify the representation, we omit it here. Their detailed relationship is shown in Appendix C.2.
5 COMPARED WITH THE RELATED WORKS
In this section, we introduce the related distributed pairwise ranking in kernel learning. In Chen ct al. (2019), Chen et al. construct the ervide-and-conquee pairwise ranking in kernel learning. called DRank. They study the statistical properties of DRank and establish its convergence analysis in pectation. The time complexity, space complexity, and communication complexity of DRank are O(D))1), ((),, and O(D))), respectively. The convergence rate in expectation only demon- strates the average information for multiple trails but fails to capture the learning performance for single trail. Therefore. the probability version of the convergence rate of DRank in a single trial is proposed subsequently in Chen et al. (22IT) The statistical properties and the convergence rate of DRank in probability are carefully analyzed and established in Chen al.) (202T). In addition, the paperChhen et al. (2021) proposes communication strategy for DRank, called DRank-C, to improve the learning performance and provides convergence rate probability. The time complexity and space complexity of DRank-C are O(D,) 3 + M D [DI and ((DD, respectivell. However, its communication strategy requires communicating the input data between each local processor. Thus, it is difficult protect the data privacy of each local processor. Furthermore, for each iteration, the communication complexity of each local processor is ((qM)D)) where g denotes the dimension, which is infeasible in practice for large-scale datasets.
Table T shows the detail complexity of the related methods. We see that the proposed DRank- RF only requires O(m²l (Dyl) time, O(ml (Dy)) memory, and (mm) communications, which are smaller

---

Under review as a conference paper at ICLR 2023
0.0000
Bitaak (itanb-413
Training Tioe (hegtt)
0,822
Dilakk
Tratting Time (tegre))
DRank DRank-K2
Dibnk-R1
DRaak-K2
0.19922
04821
0,1992
6.0
881915
Partilian
Partition
(a) Testing error
(b) Training time
(c) Testing error
(d) Training time
Figure I: The testing error and training time simulated datascts. (a) and (b) are about the number of random
features m with p = 2. (c) and (d) are about the number partitions p with m = 200 in DRank-RF.
than other methods. For BRank-RF-C. it requires less complexity than the communication-baln based method. In addition, the communication strategy proposed in this paper only requires communicat- ing the gradient and the model parameters, rather than the data, therefore the proposed DRank-RF-C do better privacy protection.
The convergence rate of the proposed DRank-RF Theorem is sharper than the convergence
((>) Σ Dz1
rate O
of the existing state-of-the-art DRank (without communications) (Chen et al. 2021 2019). And the convergence rate of the proposed DRank-RFF in Theorem
M+1
.ID zांZ })
is also sharper than the convergence rate O max [på अहं))
of the
existing cummuunccation-basee DRank (Chen al. 2021
EMPIRICAL EVALUATIONS
We perform experiments to validate our theoretical analysis of DRank-RF RF and the communication strategy on simulated and real datasets. The server is 32 cores (2.40GHz) and 32 GB of RAM.
6.1 PARAMETERS AND CRITERION
We use the Gaussian kernel K (x,x') cxp (- x' /2d2)) The optimal bandwidth d
2(05:0.5:5 and regularization parameter 2.- 13:2::3) are selected via 5-fold volss-aaliation. The criterion of evaluating the methods on testing data is as follows (Chen et al. 2021 Kriukova et al.)
2016;; R(F) >m ((Gx))))) where [pp is if &p is true and 0 otherwise.
ΣT ((v:")))
We use the exact LSRank as a baseline, which trains all samples in batch. And we compare the proposed DRank-RF and DRank- (M 2, 4, 8) with DRank, DRank-C, and LSRank by carrying out various settings. We repeat the training 5 times and estimate the error on testing data.
6.2 SIMULATED EXPERIMENTS
Inspired by the numerical experiments in Chen al. (2021 Kriukova et al. (2016). consider the following way to generate the synthetic data. The inputs (x, ==1 E D!D'x are randomly chosen from {1,..., 100), and the corresponding outputs {ye 1,1
D'1 are generated from the model 3: |||x|||| /7] + E,, < [D", where [-] means the integer part of inputs and is the noise independently sampled from Gaussian distribution (0, 0.01). Dimension q is We generate 20000 samples. 70% is used for training and 30% for testing.
Figure (a) and Figure I(b) show the testing error and training time (logarithmizing it) in seconds about the number of random features with p 2 and indicate that DRank-RF has an obvious ad- vantage over DRank and LSRank, even one order of magnitude less, in time cost. the testing error, the gap between DRank-BR RF and DRank decreases increases. Finally, there is significant dif-

---

Under review as a conference paper at ICLR 2023
0.0202
DRtanbCC
0.02
DRtank-
DRaan-C
DRank-RF
Error
0.0198
DRank-RE BE-l-RR-C..
RF-C
0.0196
DRank RF-C
0.0194
0.0192
0.019
15
20
25
Partition #p
The testing error about the number of partitions p on simulated datasets. 4, and represent the number of communications with m 300.
Figure 2:
ference between DRank-RF and DRank, both of which are close to the optimal level. These results are consistent with our theoretical analysis. With the increase of the number of random features the training time of DRank-RF increases, and the testing error becomes smaller, which are in line with the theoretical reasoning. And the testing error of DRank-RF declines significantly when m small number. Therefore, in practice, we only need to take a small m to obtain a satisfactory error, which will result in the savings of computing resources. Note that, DRank and ISRank have nothing to do with m.
Figure I(c) and Figure I(d) show the testing error and training time about the number of partitions p with m 200 for DRank-RF. Figure [cc] shows DRank-RF keeps the same accuracy level as DRank. With the increase of the number of partitions p, the testing errors increase in p-related algorithms, which is in line with the theoretical analysis. In Figure ([d) with the increase of p. the training time decreases in distributed algorithms (DRank-RF and DRank). Our algorithm DRank- RF has a significant advantage over ISRank and DRank in the training time. In particular, the time cost of DRank with p 30 higher than that of DRank-RF with p 15, that is say, the proposed DRank-RF requires less expensive hardware devices, under the same scenario and time cost. Combining Figure I(c) and Figure [(d] we obtain that DRank-RF can use fewer hardware devices (local processors) to achieve smaller testing error under the same training time, which is consistent with the theoretical analysis.
Figure 2 shows the relation between the testing error, p. and different numbers of communications (M 2, 4, 8) with m 300 and indicates the following information: With the increase of p. the testing error gaps between p-related algorithms and exact LSRank become larger and larger. There exists an upper bound of p for DRank-PP RF and DRank-RFa respectively, when larger than it, the testing error increases and is far from the exact LSRank. This is in line with Theorem and Theorem 2 2) The upper bound p of DRank-RFa RF-C much larger than DRank-RR RR. which is aligned with our theoretical analysis that the bound of p is determined by the communication times. 3) Under the same p. the performance number of communications M, the testing error of DRank-RF-C is smaller. These verify the power of the communication strategy for DRank-RF. 4) Under the same conditions, the testing errors of the proposed DRank-RF and DRank-Ru RF-C are similar to those of DRank and DRank-C.
FRank-RF-C
better than DRank-RE RF. And with the increase of the
6.3 REAL DATA
which a 62423 x 162541 rating matrix where (i.j) entry is the rating score of the j-th reviewer on the i-th movie. We group the reviewers into 500-1000 movies according to the number of movies they have rated. And 500 reference reviewers are selected at random from this group. In addition, we select the test reviewers from those users who had rated more than 5000 movies. So, we obtain a small matrix with the scale of at least 5000 x 501, where the last column corresponds to the test reviewer and the other columns correspond the 500 reference reviewers. Then the columns without non-zero elements are deleted and the rows without the rating of any reference reviewers the test reviewer deleted. Finally, missing review values of every left movie were replaced
The real dataset of MovieLens is from website http://www..rrupler www.grruplles..or/raxoooooo www.//axoooo//eemm//////oooooo/e
8

---

Under review as a conference paper at ICLR 2023
Table 2: Comparison of the average testing error (standard deviation) and training time (in seconds) Movie- Lens dataset, with partitions p 2, 10, 15 and random features m 100, 150. and are the number of communications.
p=2
p=10
p=15
Algorithm (m=100)
Error
Time
Error
Time
Error
Time
LSRank
0.4902 + 0.0283
4.01
0.4902 + 0.0283
4.01
0.4902 0.0028
4.01
DRank
0.4904 = 0.0219
2.35
0.4906 0.0220
0.08
0.4907 0.0222
0.05
DRank-C #2
0.4904 0.0221
2.73
0.4905 0.0219
0.10
0.4906 0.0181
0.08
DRank-C #8
0.4903 = 0.0192
3.69
0.4903 0.0192
0.19
0.4905 = 0.0212
0.10
DRank-RF
0.4904 + 0.0221
0.16
0.4907 + 0.0211
0.02
0.4908 + 0.0199
0.01
DRank-RF-CC #2
0.4904 + 0.0210
0.22
0.4906 0.0171
0.03
0.4907 + 0.0217
0.02
DRank-RF-C #8
0.4903 = 0.0187
0.32
0.4903
= 0.0210
0.03
0.4905 = 0.0211
0.02
DRank-RF-C #16
0.4903 + 0.0103
0.41
0.4903 - 0.0185
0.04
0.4904
0.0236
0.03
p=2
p=10 Error
p=15
Algorithm (m=150)
Error
Time
Time
Error
Time
DRank-RF
0.4904 + 0.0201
0.17
0.4906 + 0.0197
0.03
0.4907 + 0.0232
0.01
DRank-RF-CC #2
0.4904 + 0.0191
0.23
0.4905 + 0.0197
0.04
0.4906 + 0.0180
0.01
DRank-RF Maank-RFCCHae #8
0.4903 = 0.0167
0.35
0.4903 = 0.0187
0.05
0.4904
= 0.0221
0.02
DRank-REE Maank-F-CCFFe #16
0.4903 = 0.0092
0.44
0.4903 + 0.0121
0.06
0.4904
= 0.0111
0.03
with the median review score of those left reference reviewers on this movie. Here, we obtain smaller matrix. Each row of it is data pair (x,, (x) and the last entry was the label y/i of the input features x;. The experimental dataset is similar to that in Chen et al. (202T). On the obtained dataset, 70% is used for training and 30% for testing. The empirical evaluations are given in Table 2 where m = 100, 150 and p = 2, 10, 15. In Table 2 we can find that the experimental results similar to those on the simulated data. The average testing error gaps between our methods and the exact methods are particularly small, which verify the effectiveness of our methods on the real dataset. Under the conditions of M=16, p=2, and y=10, the testing error of DRank-RF-C is convergent and does not change with the increase of the number of communications. Under the condition of p=15, the testing error of DRank-RF-C decreases with the increase of the number of communications, which demonstrates the effectiveness of the communication strategy on the real dataset and is consistent with our Theorem 2 The training time in the distributed algorithms decreases with the increase of p. The training time in communication- with the increase of the number of communications. The proposed DRank-RF and Drank-RF-C have significant advantages over LSRank, DRank, and DRank-C in the training time. These are consistent with the theoretical analysis. More experiments on different datasets are given in Appendix
algorithms increases
7 CONCLUSIONS
We propose novel pairwise ranking method (DRank-RF) to scale large-scale scenarios. Our work is the first time to apply random features to least square ranking, which is a new exploration of the application of random features. Our theoretical analysis based the techniques of integral oper- ators shows that its convergence rate is sharper than that of the existing state-of-the-art DRank with- out communications, In computational complexity, DRank-RF only requires O(m² D2I) time and (mm|D)) memory, which are the least compared with the existing state-of-ther of-the-rrt DRank. Experi- ments verify that our proposed method keeps the similar testing error as the exact and state-of-the-ar approximate methods and has greatly advantage over the exact and sate-of-the-an approximate methods in the training time, which are consistent with our theoretical analysis. To further improve the performance of DRank-RF, we propose communication strategy to DRank-RF, which is called DRank-RF-C Statistical analysis shows that DRank -F-C obtains a faster convergence rate than RF.. Compared with the existing state-of-te oatee--f-hheeeee art DRank with communications, DRank-RF RF-C requires less complexity and keeps a sharper convergence rate. And the numerical results validate the power of the communication strategy.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3):337-400 1950.
Aurélien Bellet, Yingyu Liang, Alireza Bagheri Garakani, Maria-Florina Balcan, and Fei Sha. A distributed woank-wolfe algorithm for communication-efffieenn sparse learning. In Proceedings of the International Conference on Data Mining, pp. 478-486, 2015.
Gilles Blanchard and Nicole Krämer. Optimal learning rates for kernel conjugate gradient regres- sion. In Proceedings of the International Conference on Neural Information Processing Systems, pp. 226-234, 2010.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with sgd and random features. In Advances in Neural Information Processing Systems, pp. 10192-10203, 2018.
Xiangyu Chang, Shao-Bo Lin, and Ding- Xuan Zhou. Distributed semi- supervisee learning with kernel ridge regression. The Journal of Machine Learning Research, 18(1):1493-1514 2017.
Hong Chen. The convergence rate of regularized ranking algorithm. Journal of Approximation Theory, 164(12:1513-1519, 2012.
Hong Chen, Yi Tang, Luoqing Li, Yuan Yuan, Xuelong Li, and Yuanyan Tang. Error analysis of stochastic gradient descent ranking. IEEE transactions cybernetics, 43(3):898-909, 2013.
Hong Chen, Jiangtao Peng, Yicong Zhou, Luoqing Li, and Zhibin Pan. Extreme learning machine for ranking: Generalization analysis and applications. Neural Networks, 53:1 19-1199 2014.
Hong Chen, Han Li, and Zhibin Pan. Error analysis of distributed least squares ranking. Neurocom- puting, 361:222-221 2282,22222222 2019.
Hong Chen, Yingjie Wang, Yulong Wang, and Feng Zheng. Distributed ranking with communi- cations: Approximation analysis and applications. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 7037-7045. 2021.
Radha Chitta, Rong Jin, and Anil K Jain. Efficient kernel clustering using random fourier features. In 2012 IEEE 12th International Conference on Data Mining, pp. 161-170. IEEE, 2012.
Corinna Cortes, Mehryar Mohri, and Ashish Rastogi. Mugnitude-preserring ranking algorithms. In Proceedings of the 24th international conference on Machine learning, pp. 169-176, 2007.
David Cossock and Tong Zhang. Statistical analysis of bayes optimal subset ranking. IEEE Trans- actions on Information Theory, 54(11))5140-514 2008
Felipe Cucker and Ding Xuan Zhou. Learning theory: an approximation theory viewpoint, vol- 24, Cambridge University Press, 2007.
Zheng- ChenggChuuuee Guo, Shao-Bo Lin, and Lei Shi. Distributed learning with multi-penalty regularization. Applied and Computational Harmonic Analysis, 46(3):478-499, 2019.
Cheng Huang and Xiaoming Huo. A distributed one-step estimator. Mathematical Programming, 174(1):41-76, 2019.
Galyna Kriukova, Sergei V Pereverzyev, and Pavlo Tkachenko. On the convergence rate and some applications regularized ranking algorithms. Journal of Complexity, 33:14-29, 2016.
Jian Li, Yong Liu, and Weiping Wang. Distributed learning with random features. arXiv preprint arXiv: 03555, 2019.
Jian Li, Yong Liu, and Weiping Wang. Optimal rates for distributed learning with random features.
In Proceedings of the s1 International Joint Conference Artificial Intelligence, 2022.
10

---

Under review as a conference paper at ICLR 2023
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral al- gorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48(3):868 11888888,,,,,88 2020a.
Shao-Bo Lin, Di Wang, and Ding-Xuan Zhou. Distributed kernel ridge regression with communi- cations. Journal of Machine Learning Research, 21(93)11-38) 2020b.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel ap- proximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis Machine Intelligence, 44(1):7128-71) 2022.
Yong Liu, Jiankun Liu, and Shuqiang Wang. Effective distributed learning with random features: Improved bounds and algorithms. In International Conference on Learning Representations, 2021.
Nicole Mücke and Gilles Blanchard. Parallelizing spectrally regularized kernel algorithms. The Journal of Machine Learning Research, 19()):006--099, 2018.
Mengjuan Pang and Hongwei Sun. Distributed regression learning with coefficient regularization. Journal of Mathematical Analysis and Applications, 466(1):676-689, 2018.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pp. 1177-1184 184, 2007.
Wojciech Rejchel. On ranking and generalization bounds. Journal of Machine Learning Research, 13(46):1373-1333 2012.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Proceedings of the International Conference on Neural Information Processing Systems, pp- 2218-3228, 2017.
Cynthia Rudin. The p-norm push: A simple convex ranking algorithm that concentrates at the top of the list. Journal of Machine Leurning Research, 10:2233-2271, 2009.
Cynthia Rudin and Robert E Schapire. Margin- based ranking and an equivalence between adaboost and rankboost. The Journal of Machine Learning Research, 0121193-2232 2009.
Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their ap- proximations. Constructive approximation, 26(2):153-172, 2007.
Rong Yin, Yong Liu, Lijing Lu, Weiping Wang, and Dan Meng. Divide-and-cooquee learning with nyström: Optimal rate and algorithm. In Proceedings of the AAAI Conference on Artificial Intel- ligence, pp. 6696-6703, 2020.
Rong Yin, Weiping Wang, and Dan Meng. Distributed nyström kernel learning with communica- tions. In International Conference on Machine Learning, pp. 12019-12028, 2021.
Jinshan Zeng and Wotao Yin. On nonconvex decentralized gradient descent. IEEE Transactions on signal processing,
2018.
Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression. In Conference on Learning Theory, pp. 592-617, 2013.
Yulong Zhao, Jun Fan, and Lei Shi. Learning rates for regularized least squares ranking algorithm. Analysis and Applications, 15(06)8815-88) 8366, 2017.

---

Under review as a conference paper at ICLR 2023
A PRELIMINARY DEFINITIONS
There is a compact metric space := : (X) C Ro+1 where &' C R2 and y [-bb bj for some positive constant b. The sample set D == {(x;; vi) from an intrinsic Borel probability measure p on 2. p(y) x) denotes the conditional distribution for given input The hypothesis space used is the reproducing kernel Hilbert space (RKHS) (Hk) associated with a mercer kernel K X' x 2 + (Aronszajn [950 Cucker Zhou 2007). We will denote the inner product in HK by (+, -). and corresponding norm by || [K-- Kx K Kxx,) -).
of size N = |D] is drawn independently
Let Px be the margin distribution of with respect to X' and I. be the Hilbert space of px square integrable functions X.
The Mercer kernel K defines an integral operator LK on Hx (or 1xxx) Chen et al. 2021 by
Lkf S. f(x) (Kx dxx (x').
Suppose v is continuous, such that | w)l S almost surely, [1, 00). Assume that L So HK with 0 < r S 1, where L'x is the r-th power of LK.
Before the proof,
give some definitions: RT S = fxx (xxxx)( S L2x + R" " [Di Ex,EDx Qm f Sm and 4 D M.D = S Sm are self-adjoint and positive
S. : Rm + L 2 (Sm.) (x) (g. om (x))).
ST : ox
I
operators, with spectrum is [0,+²] (Caponnetto & Vito 2007
This part is organized as follows: In section B introduce the proof of Theorem | Section B.1 contains the main lemmas used for the proof of Theorem [ and Theorem 2 Section [22 is the detail proof process of Theorem [ In section C introduce the proof of Theorem 2 Section C.1
contains the main lemmas used for the proof of Theorem 2 Section C.2 is the detail proof process of Theorem In section D introduce the propositions used for the proof of Theorem and Theorem Section D is the experiments on Jester Joke dataset.
B PROOF OF THEOREM
B. BOUND TERMS
Lemma 1. We have
VĀ D. - gm,all
11/2
1/2
2
DD W D T mD
+
211)
S Sm + 111)
St Sm +
211
A
1/2
$
m. W WDYD - S WDfe)
+
Sm + +
A -1/2
(S: Wo.
- W
Wofe!
+ 1+
4 m W
D M.D
+ -
-1/2
S Sm + 211)
A
1/2
1) Il1ma - -Sollx
Proof.
Note that 1.,.D.A - -mm,l1 S
Bm.D.A -
-g Bm.D.. |
Bm, - -Bm.
Define Sm,D.A =
g D...D. (m))),
Bm,DA
arg min
[Dp Ex.NED (g (xs) vi) (gT om (xx) vx)) 2 >||g|3]]
gERm
fo = B (.),()))
B,D = arg min gERm
{ [op En.ZED @m (x,) - fo (x:)) - (g om (xx) Sp (xx+)) 2 + Allel?
One have S,,DAA Smgm,,,,, D,,
an 1) $ mm W DyD,
12

---

Under review as a conference paper at ICLR 2023
D,A Smgm, D and D.A (Dm.D WD T m
"
S D W WDfp= so we have
D.,
D,A
-1
2 D W D $
+
1
Dm.DWDDD - S W WDD
D.D
2
-1/2
m, W T M. + 211) -1/2
A
1/2
(10)
D W
T
+
1
Sm + 2
M,
A +S +
2/1
1/2
D W WDDD S W WDff).
Note that
( m Wo m,D + 1)
-
1/2
S 2/X. Thus we can obtain that
D, 8m, D.ll
A
-1/2
X _11
1/2
5V2/X 2/A
(D..D Dm.DWDDth W M. +
Sm Sm
2
-1/2
St Sm Sm +
1
$ m, W WDYD - SmmD Wofe)
2 112
A 1
1/2
2/A
$ @m..WD W WD D, +
St Sm
2
2
1/2
5th Sm
+ 2
111
Dm,DDDDD
W WD8D - S WDf, + S W DSp
S W WDDD)
5V2/X
1 m. W
WD T m.D
+
211
A
11/2
S S +
1
1/2
2
(1(
Sth Sm + +121)
-1/2
D, W WDdn - S W pfa)
+
S Sm +
1
-1/2 -1/2
(S W pf - Wott
(11)
Define fm, 8m,, (-) with
(1 L ((gT (x) - "T - fx())))) dpx(xx. v)dpx (x, + A|la||
gm.A = arg min
BER"
We know fm,d Sm8m, and gm,d (8th W WD =1 S.n W WDfp- So one can obtain
Bm.DA A
1 -1
S" D WDJo - (5% -5 W + 1 "
1 Lm.D W D T
D +
2/11
St WWWf
-1
Φ mD W D T
D + |11
(Sm WpJp S Wnlb]
( (mm.D @m.DDDDTT T
-S + ) -1
2 !) - S WDS
+
D +
St WoJe
For any self-adjoint and positive operators A and B,
-1 1 1 A)B A B --1 B B -
13

---

Under review as a conference paper at ICLR 2023
we have
X -1
D,A
gm,
$ mD
W
T
M, +
_11
|m, WDJ0 Sm W D
X
-1
2 m.
W $ M.
+
2
(S WDW Dm. W D D)
gm.
$
m
W
D T
D
+
| Wh 5 Wnfol
21) m.
-1
+ m.
D T
(S P
T m, gm,.-
We know that +
D
T
D.
S Sm
Caponnetto & Vito 2007), thus obtain that
Bm, gm,A
② DD, W W
& T
D + 11 211
-1
1 mD W +
D Φ
(mmmmm - St, Sm
m.
D
W
T
+
1
[5m Smmm.)
A
+ 4 D W $ T
M.D
+
2
1S Smmmmmmm - SmmPl
-1
-1
Φ mD W
D T
+
I
[Sm S Dmmpl + Fm.DD (m..D in +
WD
2
111
[SmIm, S Spl
m.
2
$ @ W 27 MDD + A
Sth 15p smal+ Lm.DD W m. + 2
21)²
211
STh 1fm, - fpl.
(12)
Thus, have
Bm.D.> gm.A
1 mn W T D. + 21)
-1
+ +
( @
DD m, 1 -1
5: S
Sm
115m sollx-
(13)
Note that
-1/2
1
$ mD W
D
D
2
mDD
① PD,D WD WD
D.
111
A
-1/2
o
m. W
WD
@m.D W M.D
1
-1/2 1/2
and
-1/2
Bm.DWDe DD
1
S
2
1/2
A
1/2
-1/2
② Lm,D Wn.DWDDb 67 D.
-1
St Sm + -1
Sp, +
5t
2
2
-1/2
1/2
A
-1/2
④
Dm,D W DT
2
St Sm + 1/11
5t Sm +
Sm
5
D.
14

---

Under review as a conference paper at ICLR 2023
since [(Sh + 21) 1/2
Sm
(S Sm + +1)
1/2 Sm (S + 11 - -1//111 1/2
S 1.
Substituting the above two inequalities into Eq. 13 we have
(
21)
A
112
S Sm + -/11 1/2
1)
Bm.D.A- - 8m.al Vx
1+
T M. +
+221
1ffm - follx.
(14)
Combining Eq. and Eq.14)
(14. we finish this proof.
Lemma 2. We have
(omo W WD D + A
211
-1/2
1/2
- 1 S
S Sm + 2
2
* ( Sm + 21)
-1/2
( (DmDD
W WDdn - S W wDl
+
(
( Sm +
2
-1/2
(S WDJ - SmmD WDlp)
2
(1(0mm @mm.D W
WD T D
+
1
A
2
-1/2
S Sm +
A 21
1/2
+
PD, W
T
M.D
+
211)
2
112
S S Sm + A
_11
1/2/12]
* +Ilfma> x-
Proof. Note that
- - S IIS Sm, + 1| - small
According to fm.D.> - -i = Sm Bm.Did - B..D.)). by 10). we have
Dm,DA- - D.. = Sm D. - B,))
-1/2
1/2
-1/2
-1/2
SSm
Sm + #22
1
S Sm +
W D
mD 2
+ 1
$
mD + 1
2
2
1/2
11/2
S Sm + 2/21
21
Sm +
( m W WD&D - St W.WD.. wSo + S W vlo - S. W WDfp).
m
(15)
Note that
Sm S Sm + +2/1
-1/2
{ 5th Sm + _
>
-1/2
S
S Sm +
-1/2 1/2
=
-1/2
-1/2 1/2
St Sm 2/1) 2
1/11
S Sm
St.
2
<1.
So, by 15) we have
fm fn p. - ( < @mm W DT DD +
21)
-1/2
S* Sm + A
21)
1/2
2
(1(55i Sm +
112
*
2
( W - S W WDfo)
(16)
+/
+
* (S/Smm + 2
-1/2
(S W p - S S.S.D.DWDoll Wa/s
15

---

Under review as a conference paper at ICLR 2023
Similarly, according Eq.
12
we have
D. - -m,, S. D.A gm.a)
Smm
Lm.D W +
211
2
Sm.D 1so smial + 55
WDDDD
m.D
_
S [fm,> Sol
=Sm
Sm + 1 111
11/2
S Sm
A
2
1/2
o M. W
W
m.D
+
1111
A
-1/2
$ m.
W D M,D + -
-1/2
1
11/2
A
1/2
1
-1/2
Dm - Smii + Sm
S Sm +
$22
S Sm +
2
o
mDD W
$ T
D
+
2
<MMDDDDTT.
1 WD M. +
-1/2
1/2
-1/2
S Sm +
2
S Sm +
S [m,, - fpl.
2
Note that
Sm ( Sm + 31)
-
(SthSm Sm + 11)
11/2
S Sm ( + I1) -/21| 1/2
1,
so we have
S&M fmalk
A 1
-1/2
)
211 1/2
Pm.DWD' D DDD +
211
S Sm +
2
(17)
11/2
Sm Sm + A 2
1/2
|)
+
2 m. W
D D +
115m,1 - foll
Combining Eq. and Eq.17 we finish this proof.
Lemma 3. For 8 E (0, 11. with probability at least - 6, we have
(Sin + 21) 11/2
+ @m.DD W WNDD - S,, WWWWDDf -o (o((AL) +
(A)
log
[D]
where Nm (A) = Tr 1OTT((1 (Lmm + 211) Lm) Lm is the integral operator associated with the approx- imate kernel function Km (Lmf) (x) = fx Km (x,x') ) f (x') dpx (x').
Proof. We have
( St Sm
21)
112
mDDD WoDD St W DfA) S ( ( 21) -1/2
D Smfo)
According to Lemma 6 in Rudi & Rosasco (017))
know, with probability least - 5,
( S Sm + -
- 1/2
(Lm,DDD - So) = -o ((>in) +
N (A) D V
log
where Nn (A) = Tr (Tmm + 111)= T.m) T'm is the integral operator associated with the approx-
imate kernel function Km f) (x) Sx Km (x,x') (x') dpx (x'). Thus, we complete this proof.
Lemma 4. For 8 E (0, 1), with probability at least - ō, we have
|( (snASm + A 11)
11/2
Tslog }
Nm [D]
(S WD St Wofo) <
DIva + /2Cl
where Nn (A) = Tr ((mm + -)= -1 Lm))
16

---

Under review as a conference paper at ICLR 2023
Proof. We have
( (s ( Sm
21)
1122
(S. Sm Fo.DDWofo $
{ 21) )
-1/2
(Smfo S Sm.Dtte
According to Proposition in Liu et al. (0221, with probability at least 1 - 8, we have
( Sm Sm +
211
- 1/2
(Smfo SinDfee
5 1og DIVA
Nm
+ + D
where Nm Tr (Lm 1) Lm). Combining them, we complete this proof.
Lemma 5. For any > with probability at least 1 6. we have
1/1)
Sm +
(5 Sm &m W m.D)
m
> 111
-1/2
Sm 211)
-1/2
Sth Sm
2
(S Sm
$ m W D
2
2log 2 (2/8) (272X-1) 111+1 1)
llg(221)) (2 +1
+
D
D
Proof. Since Sm is self-adjoint operator, we have
S Sm + 2
S Sm DD WD m.
1/2
-1/2
S Sm + 1
(S Dm. W WD p)
S Sm + 2
According to Proposition
with Ci om (xi), can obtain
(
(Stnm Sm + )//
21og (2/8) (N (A) +1)
2 log((2/8) (Noc (A) + +1
(S Sm DD No.DWDohh WD TT m.
(T.D)
<
(D
D)
where
A [x
-1/2
NN) sup wen
111
(l(, w)
2T
2
Lkf = Sx K(x, -) (Rudi & Rosasco
2017), ej and 02 are two constants.
Therefore, we have
( (sx (S 11)² Sm: &m,D W DT mTD))
2 2log2(2/3 (272 1)
2 2log(2/0) (2+2x-1+1))1+1
D
[
17

---

Under review as a conference paper at ICLR 2023
Lemma 6.
We have
b D,A D.Al
D21²
( W W m, m. +
(
11
11/2
Sth Sm + A
2
1/2
P
1Dxl
j=1 kmm
1/2
5 Sm + A -1/2
S S Sm +
(S Sm
DD. D 2 mD
2/1)
(18)
2
-1/2
S SmSm D, WD $ B..)))
S Sm + / -1/2
SmSm Sm +
1m.. - -8m,al
mm WDWyyyy DyD. Thus we have Proof. Note that gm.D.A (D WD m.D + +111) 2
0
D,A
B,A
2
A
4 D, WD, D7 D2 +
1 1) D, DD,
Dk=1 DE
2
D. WDD D. + X
2 1) 1)
1 1 m. Wnÿn
DJ1²
-1 - -
A -1 W MD +
Dm W D, $ T
+ 1
111
D Lm.D, W WDDDD,
D k=
2
D,
2
D3
mD W T T MD + 21)
-1
$ mD W W MD 4m W D, x k..,))
Di& 2
k=1
D, WD, T D,
+ 21)
$ D, WD,YD,
P
D21
P W T D + 21) -1
(
Pm.DD W M.D Dm WD, T D, gm.
DD1
k=
(19)
By introducing Sm term, convert the above formula into
D. Bm,D.A
k=1 |D
DD/
2
o mDD Wn W
T
M.D
+
211
$ m. W WD
St Sm) Dy,
P
D21²
-1
mD W D T
111
St S m, WD, D D,A
P 1=1
D21
2
m,
+
j=1
DD/
A
DD
Lm,D W
D.
+
211
o W WDD D. Sm)) (gm,Dy,A 8m.))
D
1
Fm.D W.bDDD& D. +
211)
o (DmDD W WD DT
S Sm)) Bm.d
k== D
P
D
+ 21) -1
MD.D W T
Sm D, WD, LTDD) D,..
D
D
m.
1=1
Σk=1
(20)
18

---

Under review as a conference paper at ICLR 2023
So have
Bm, D2A
D,A
D
o D W T D + 21)
4 m Wo M.D Sm) (Bm.Dj,a - 8m.A)
Ek=1 Dxl=
==1
Term-A
1Dj22
$ mD
W
WD m.D 2
Sm @ D, Wn, $ m,.D)) (gm,D3,> Bm.))
P ==1
Term-B
(21)
Note that
D21²
@ W W m. + A 2/
S S Sm + A -//1
> 211) S SyS,n Sm
Term-A
E
k= DD1
* p mD W D m.D
S Sm) (gm.D,i> - Bm,))
and
PD.D W m. + 2 Sm + 2
Term-B
1=1 Ek= |Dx
1
21)
STH Sm
S + D, WD, T D,.D)) (Bm, Bm,))
Substituting the above equations into Eq.
21 we have
0 D.A
D.A
2
Ln, M.D + A
-1/2
8th Sm +
_11
X
1/2
P kml
1
1=1
11/2
S Sm + A
-1/2
Shh SySS Sm + 21)
(S Sm PD W n DT m)
21
11/2
Sth D, WD, T7 BT.,)) Stn Sm + - -1/2
S Sm +
Dm., xm
Here, we complete this proof. Lemma 7. We have
[ - Sm,D.All
1212
-1/2
1/2
② (RmDD W DD m.D + 1
S
711)
2
km
(1S Sm +
A
-1/2
5th Sm + A
-1/2
*
-11)
S5t Sm + mn W DT TTD)
_1/
(22)
21)
>
-1/2
Sm DD WD, T Bm)D)) Sm + A 11)
-1/2
Sim Sm +
(1..DD. Sm,llx + VT /llBm,DD. Bm,A1
19

---

Under review as a conference paper at ICLR 2023
Proof. Note that Sm (m,,D. D,A
Sm.D.>) = (...D.)=fm.D.x> - Sm.D.Y.
According to Eq.21 we have
D,A - S,,DAA
D,l²
1
Sm
L W
WDD
D, +
mm.DD m.D WD m.D - Sm) (gm.D,,> - Bm,a)
Dxd 2
Term-A
P
D
2
Sm L D W WDD MD + A 21)
S 2 Dm WD, & m,.,)) (D. 8m.))
Σ
D
2
1=
Term-B
(23)
Note that
Term-A
11/2
1/2 211
-1/2
SSm
Sio + 211)
Sm Sm
m. W DJ M.D
WD
211)
2
Pm.D W DJ M.
DT
111
A
1/2
St Sm + 2!
1/2
8t Sm +
2
A I
-1/2
o D W
W Sm))
Sm + I1)
2
-1/2
8 Sm + A
211)
-1/2
S Sm + 2
(gm Bmi)).
So, we have
Term-Al| K
-1/2
1/2
A
④ PD W WD D.D +
+1211
St Sm + 211
-1/2
Sm + +²21 2 )
>1 -1/2
*
S Sm +
Sm
$ M. W D a TT.))
S + 2
-1/2
5th Smim + 211)
-1/2
Sm + _ (Bm, - 8m,))
*
Sm
-1/2
1/2 2
1 m. 1) W TT D
211)
St Sm +
1
2/1
5t Sm + 11
-1/2
(SmSm 211) -127
(S
T M.D W D T b).
S Sm + >
211
-1/2
Sm + (11) 15m,DyyA-mmm.)
|m.m (5 Sm + 21) - = (St Sm + 2/1) 1/2 s Sm (St, Sm + 21) 119111/2 1/2 1.
Since
20

---

Under review as a conference paper at ICLR 2023
So, we have Term-All K
X -1/2
1/212
1 D W T DD
+ 2/1
Sm + 2
-1/2
1122
5t m
Sm + 2
(S Sm
Pm.D D D m)
Sm + +z21)
S Sm +
2
A
-1/2
Sm + *
(//
(Bm.DjiA - -mma))
-1/2
S Sm + 1 21
1/2112
1 Pm.D W
W T
D
+
111
2
A
112
DD W W x p) (
( (5 + 211 -1/2
2
1
Sth m +
1
(S (5msm m
m.
2
1
-1/2
Sm + 2 (Bm.Dj, 8m/))
S Sm +
A
-1/2
Sm + A 2
1/2
1 m W D TT
+
2/1)
MDD
St m
Sm +
211)
-1/2
(S Dn, W 13 x m.
Sm Sm + 2
2
-1/2
St Sm +
1
11/2
S S Sm (Bm,Dy, - -mm,))
+ 1
1 L W Wo m, +
111
A
-1/2
S Sm + A 1/212
2
2
2
S* Sm +
2/1
A
1/2
(S - D p)
(
S Sm + 2
-1/2
-1/2
Sth Sm + 21
(8m.Dj.a Bm,)
A
-1/2
X 1/2
$ D W WD $ T
+
1
Sm +
1
-1/2
Sm + +221) 2/21/11 -1/2
S* Sm + 211
(S - 2 DD,D W WD sm.p)
m
St S +
11)
2
1/2
S
[Im. Sm,Duslx vā
o @mm.D W BT
M.
+
A
T
-1/2
S
2/1)
1/212
1/2
-1/2
St Sm + 111
2
S Sm DD.DDDDD
Sm + 2111
Bm.DD,> Bm,))|
$ mD W W T D + A -1/2
> 1/2 2
1111
S S Sm + 2
Sth + 21)
1/2
(5 - -mm WD t mm. ( (5 Sm + A -1/2 -1/2
x21)
(1Um,DS - -mm..ill x + +V1 VAllBm,.DiA - 8mall),
(24)
21

---

Under review as a conference paper at ICLR 2023
the last inequality uses the fact that
( Sm Sm + 21)
1/2
5m
=
( Sm +
21)
-1/2
Sm
S Sm + 2
11
-1/2 1/2
|
S1.
2
2
Similar as the above process, we can obtain that
Term-Bi B
-1/2
A
1/2
M, W WD
+
2
S Sm + 2
M.
2
(25)
(
8t
m Sm +
121)
1
-1/2
S
St
12 W D3 & ...D.)
(s (Sth.... + 2
-1/2
(I.m.D D.D.D
VX
- -mm.)l--Bmmll)
Combining Eq. Eq. 24 and Eq. 25
we obtain this result.
Lemma 8. For 8 (0, 1] and X > 0, when
Ω (x-2r x-- log 1 28 11)
with probability at least 1 - 5, we have
11 - fxllx S cN
where is constant.
Proof. Note that FM,A- = SmBm. and gm,a (S W Sm + 111) S W DSp-
We have 1lfm, fallK
Sm (S W + 1111) S W wfo fA K
|mm (St Sm -/1= fm -fx where f arg min (f(x) f +
) According to Lemma 2 in Liu al. 2021 (can be also seen in Li et al. (011 and Rudi 8.
& Rosasco (2017), one has, when m 92 (A
-1 loog 2.) with probability least
Sm + 211 Smfo - f SC.
Sm
K
Combining the above, we complete this proof.
B.2 PROOF OF THEOREM 1
Proof. We have
PM. -follx
Pm.D.A fm.D,A + fm.DA fm. + fm, + + fA - -foll
(26)
IM.D.. Sm..DA K + IlS.D.DA - fm,ilxx + [l5m, - fall + 11.fa fllx-
Combining Lemma
Lemma 2 and Lemma 7 have
22

---

Under review as a conference paper at ICLR 2023
Jm, fm..DNll
Dz12
A
-1/2
SS
Ck=1 1DD2
M.D
+
2
88 1/2 (S Dm, WD DD WD D)
Sm + A
2
-1/2
1 -1/2
S5 1/2 (S D; W $ D.
Sm Sm
S
((v3) V2
1 D, W WD, o D, + 211)
1/2 /
+
2
D, W D, D mn + A
2
-1/2
s
|SS 1/2 2 D, WD,YD, Sth W D, b2.
|StnSm z1))
1/2
(8 W -DD W Wo,foll
+ 2 (((( 2 (m..D, W WD, T" D; + 11) 1/2
S5
+|
+
a D, W
T m.D; + 1 21)
2
112
x
112
+1
2
m15 spllk),
where SSx = (S + 12
From Lemma 5 we know that if [D] 2 32 log(2/6) (1 (1+ 2-
( (S S Sm + 2/1)
1/2
A
-1/2
(DM.D W D Sm) S Sm +
S 2'
Combining the above inequality and Proposition 2 for any 8 >> 0, with probability at least 1 - 6, we can obtain,
2
-1/2
St Sm Sm + 1 2//)
1/2
mm.
W
T MD +
s 22.
(27)
From Lemma 2 we have
[l - fmillk
-1/2
X
1/2
Lm,D Lm.DD WD $ D.D
+
2/1)
S Sm +
21
(55 Sm =z/)
-1/2
m, W
nynn
S W nl/)
+
S S + 211
A -1/2
(S W S WnSn)
(B
④ @m..D W H
+
1
-1/2
St S
S + 1
A
1/21
D.
2
(
112
> 1
1/2
+
2 mn W W D
2
Sy Sm +
2
Il5m,,x Sollx
From Proposition 3 Lemma
Lemma 4 and 27 we know that if ( we have
(12x111),
Dm - Smallx = = (Tm.DA log + 11mmA - fallx + 1152 - sollx): (28)
23

---

Under review as a conference paper at ICLR 2023
where
-
T M,,DA= =0
(29)
VATDi
Note that
-1/2
A -1/2
S m
Sm
+ 2
(SmS D WDDT mm
S Sm
2
S
Sth n
Sm +
211)
A
1/2
S Sm m, W D. m.D,)
S + A (
-1/2
According to Proposition and Lemma
have
P., - fm.D.all
D21
( Sm Sm +
A -1/2
Sm T D, WD, m.DD)) ( (5 + A
-1/2
=0
Smn
2
T mm Dy, log
Ek=1 Dui22
/=1
(Sin (Shmm Sm + _
-1/2
(
Sth Sm Sm + 2 21 ))
1/2
+X"
S Sm D, WD, T B.DD,)
(30)
Combining Eq. Eq.26 26), Eq. 28 Eq. 30
Proposition 4 and Lemma one can obtain,
Q aA 2r V x log X6 ). with probability 8, we have
pm D.A føllx
=0
Σ
1211
5m Sm +
-/2)
-1/2
5th SmSm -0 D,,D WD, (..,)) ( (5 Sm +
2
-1/2
D, log
D E 2
1=1
1 + D.A log x
+ xr
Sm S Sm +
2 211)
-1/2
S $ m, W D, & pmD,, S Sm + 1/11
-1/2
+
(31)
According to Lemma
we have
1/2
St Sm + 21)
-1/2
S
Sm
$ MDD W Wo .)
(32)
log
( (2/0)
22
2lo((2/))
<
+
[
D
Set A = 0
D21
r+r
we have the number of random features
1D,3
Σ DL 1
D
Ω
Dz
Combining (1) Eq. 29 and Eq. (2), we have
((2
itr log
Dj
[P sollx =
Σの D21
We complete this proof.
24

---

Under review as a conference paper at ICLR 2023
C PROOF OF THEOREM 2
C.I BOUND TERMS
Lemma 9, We have
Dj 2
(I
S
Σ
2 Jm
Sm.D.al + VTllBB.D. Bm.D.al).
k=1
D
where
Im =2
① m; W D2 $ m.
+
11
A
1/2
St Sm + 2
1/212
2
1/2
112
S Sm + 1
Stth S Sm
$ m, W WD 20 p)
S Sm +
2
2
+
D, WD, & D,
+ A
2
1/2
S Sm + 2
1/212
S Sm Sm + 111 2
-1/2
Sm Sm
$ Pm W D, T B..D))
St Sm + 2
+221 -21)
-1/2
Proof. Note that
o W M.D + 111 -1
[((00
M.D + > 1
S.,D.A
- 1-1
D.,
m.D
W W
Bm.D.> #m.DWoDD
2
and
B.,D.A
-.,.D.A
1-1
1Di12
Pm.D WD, :" D,
+ 2
111
-1
[
1
@m.D W
W
m. + I
A
B
J-1
- W WDYD
2
2
k==
Thus, we have
gm,D.
B.A
-1
Sm.
1-1
1 @D,D W D TT D
2
1
1 m, W DT mDD 2
1
Bm.D.
Lm.DD WDDD
Dj12
D.DD.A
1/-1
+
1 2
$ D, WD, T7 D,D
+ 1
2
==
D. W T D 2
+ X,
gl-l
Bm.D.> $ DD WDND
=k=1 DE
D212
D,, WD, T Dr
+ 111
2
-1
$
m W
D
11
2
-17
j=l
$
m. W W T
D, + 1
Bm,DDA
1-1
- $ m. W WDND
2
(33)
25

---

Under review as a conference paper at ICLR 2023
The above can be convert into
Bm, D.A
D,,
D
o Dm.D, WD, T D, + A
21)
$ fm.D Fm.DWDDY. D Dm.D, WD, o D.
E k=
DD 2
D W D D
211
[(
$ m.
W
D D
D. 2 Bm.D.. Pm.DWDyD
Dj1
L Dm.D, WD, o D,
+ A
2
p @m.DDWi W WD mn 2 Dm.D, W D, & D,
p k=
D& 2
D.A - B..D.A
Dj
Dm.Dj WD. T D, 2
+ 1
-1
gi-1 c mn W WD DT m Sm
D,, D.
k=1 D&l 2
1=1
Term-A
1Dj1
D, W W,, T7 D, + A 2
Sm & DD W T m,
[ D..D.A
P mm1 Dx
2
Term-B
(34)
Note that
Sm Term-AA
A1 -1/2
A A 1/2
-1/2
=Sm S Sm
+
2
S Sm + +11)
1
Dm WD, T m, + 22
-1/2
1/2
- 1/22
$ Pm D, $ D,
111
5 Sm +
21
S Sm + 211)
2
A
-1/2
P W W m
Sm]
(mn +
tz21)
S
+z21) 22)
2)1
-1/2
Sth Sm + ) (Bmm... Bm.D,>).
5m (St + 1) 11/1//1 = (Stn Sm + 1) -1/2
-||||
5 S Sm Sm + 11 -1/qq11 $
Note that 8o, we have
||5m * Term-All K
-1/2
> 1/2 S* Sm +
② D, W D. T D; + 11
2
2 2
11/2
-1/2
(35)
S* Sm + [/1
(S Sm 1 DD W WD m)
St S + 2
1/2
5t S S + 1
St Sm + 211 (Bm.b Bm.D)))
Note that
Sm
Dm, Bm, = 5th (Fu-pa,x Smm
[/-1
m
26

---

Under review as a conference paper at ICLR 2023
Substituting the above into (3) we have
1|5m * *Term-All. l
A
-1/2
1/212
Pm.D, W D2 & D,
2
S Sm + 2
Sth m + 1 2
-1/2
Sm + 2
-1/2
(S Sm
$ D, W. $ m.
5 S. + 1
1/2
(mm... SmmD.))
Stm
-1/2
1/211
+
Dy WD,
T M,
+
1
Sm + 2/1
2
2
5 Sm +
11
-1/2
Sm Sm
T
DD W WD m)D)
(Sm + A
-/1
-1/2
2
-1/2
m Sm + 2
g D,, - Bm,D.a)
① D. W Dj $ D,
+
A
2
112
S Sm + 2
1/212
S Sm + 2 -1/2
(Si.Si + 22) -1/2
(5
DD W WD x mn
(mmbb - SmpDill
vā
B 8m.D2a)
the last inequality use the fact that
|| S Sm +
-1/2
|
(
A -1/2
1/2
2
S
=
Sth SmSm Sm + 211)
S Sm.m Sm + AT) -1/2
$1.
Using the same process, we can obtain that
|| SSmm * Term-Bll k
-1/2
1/2
① D, WD, D, Tm,,, + 2211
Sm + 11
2
St S Sm + 2
1/2
Sm - D, W D, & T mm.D))
( + 2
X )
-1/2
(1 - Sm,Da// K
+ VA B Bm.D.\
27

---

Under review as a conference paper at ICLR 2023
Thus, have
M,, - -Pm Dmm k
Sm D.,, B,m, K
10y1
||5m Term-All + 115m Term-Bl B
km |
2
1=1
12j1
(1(
((m..,, WD, T Dj
+
A
1/2
5 Sm + 2
1/2112
Σk= |Dx 2
2
j=1
Sn + 2 TT)
11/2
Sm
DD W W D
Sin
+
I
-1/2
(36)
2
$ Dy W WD, T m,
111
-1/2
Sym Sm + 1 2
1/2
2
112
-1/2
5 Sm + 211)
Sm Sm
$ Pm,D, W WD, D.,D)))
Sm
8
+ 2
D.D Sm.Da/l
Vx
Bm..D. Bm,D.a
According to (4). know that D.A
D,,
Dj
(Term-A + Term-B)
k= Da&
Dj1²
-1
Dm,D, WD, $ D2 +
2
P WDD Sm D,, - D.
[Dx] 2
|Dj1² 1
1
-1
E DD 2
2 D, WD Φ T
D,
+
2
St Sm - -0 Dm WD, x TT D.
BBm.... D..
P
D
A I1]
-1
S Sm + 2))) (Smmm + 1 211
-1
D k=
D 2
$ Dm.D, W
$ D2
+
2
2
W T D.D
S m.
J1-1 Sm
Bm,D.d
D
D, WD. DT D,
+ a
2/1)
Sth Sm Sm + 2
(smm S Sm + +22)²
St
DR
2
8th Sm 1 D, WD, DT D,
BmID.A Bm,D.s
Thus, we obtain that
Bm,DDA Bm.D.il
D21
21 -1/2
A
1/2 2
mm W TT D, 2
St Sm +
2
Ek=1 1= |nnl
S: Sm + A
11/2
A _
-1/2
*
m
211)
S5t Sm pm W DT T.D)
Sm 5th Sm +
(37)
11)
-1/2
St Sm -D,,D, WD, T Bm,,,) Sm + A 1
-1/2
Si Sm +
2
BmD - 8.,
1-1
*
28

---

Under review as a conference paper at ICLR 2023
Combining (6) and Eq.(3 we have
Im, - D.l K
+ VA B..D.A - B.m
Dz1
(1
4 D, WD, T D, + A
#221/ 211
-1/2
211)
A
1/212
S Sm +
Σ 1= |Dol
2
1=1
-1/2
S Sm + 2 -1/2
*
m Sm
+ 2 2
( - Dm, WD DD TT.D)
i D, W D, T D; + 2
1/2
1/212
S S. + 211)
WD,
- 1/2
A -1/2
)
S Sm + 211
Sm Dm.D, W WD, $ pm.D)))
(m + t2))
p-1 m. - Sm.Dia
+ +V2
B BmbDN))
K
1
(Bm.D) W WD, T m, + i / -1/2
S Sm + A 111
1/212
Ek=1 k= Dx12
)
+ A
-1/2
Sm + 2 2 -1/2
Sm S m
2
(S Sm Sm - D W D D m..)))
A
-1/2
-1/2
))
+
S Sm +
I
Sm Sm - D, W WD. T D,D,,)
S Sm + 2
v1
D. - Bm.D.>
2
2
D21² 2
1/2
1/2112
2
D. WD, & D,
+ 2 1
S Sm + 2
> k=1 |D&l 1
1=1
Sy Sm + 211
(5% >
-1/2
$ D, W D, $ ,,. )
-1/2
S S + 2
+2
Φ Dy W Dj $ T M,
+ A
111
-1/2
mn
Sm + 2
1/2 2
S Smn Sm + A 2
1/2
S Sm Sm
$ D, W Dj Dzm Bm.D,)))
(Sism + A 211)
(
-1/2
1)
2
R-1 D.D - -m.paa/
+ +V
Bm.DDA 8mmDas))
12I12
(DmD,,W,,
(Dm.D, WD. $ D. + 1 2
-1/2
St S Sm + 1
1/212
2 1=1 kk=1 |Da2
p
2-)
-1/2
-2/2
St Sm + 1
$ $D,D W WD M.
S Sm Sm + 2
+ A
-1/2
1/2 2
+
Dm W W,,00 T D,
St Sth Sm + 2
St + =11 -1/2
SS 1/2 (Smam- Dm.D, WD, $ )
A.P.ppAAS..D.l + + -
29

---

Under review as a conference paper at ICLR 2023
C.2 PROOF OF THEOREM
Proof. Note that
I| - follx = Dmm.D. - SM,DA + SM.DA - Sm, f fm, -
-mmammaaa + f2 -Fllk
1 Pm.DD fm.DAal fm.D,. fm, || fm, fa +1x++Il fx fllk.
(38)
Substituting Lemma have
Lemma
Lemma
Lemma
Eq. and Eq. 28 into Lemma 6 and
Lemma
7
D.A f..DDalk + VA Bb.A Bm.D.ll22
D
Σ E Dio?
Km,D,)
(155
SSx 1/2
(
#m.DWDb. S WDFf) + 155 1/2 WD S WDDe) 1l follx))
P
D
=0
(Km,Ds + Km,D,) Qm
Σ
k==
Dio?
where SSA = Sm 1),, (5 21
1/2 11/2
( Pm,D W W m) (S Sm + 2) -
and 2m (Tm.D,,> + ml.fm.. fall llfx ))
Combining the above inequality and Lemma 9 and note that
-1/2
SST 1/2 S Sm DD W WDDD
S Sm + 2
SS 1/2 (5th D, WD, D WD. D...D)) SS SS 1/2
S
we can obtain that
P.M Sm,DDAllx
SS
Sm D, W & (m.D))))
SS 1/2
E
k=
DD
2
(39)
Dj1 ?
|SS
1/2
S5 + D, W T7 T..)) ss 1/2
Qm
k D
Combining Eq. 38
Eq. 39 Proposition and Lemma one can obtain, if m = have
Ω (A V x log 2τ with probability
1| ffll
121
SS 1/2
1/2 (5t - P WD, D SST S
Ch D
p 12112
SS
(5 D,DD W WD, _ B,,,,) SS (ImD).AA))
P k= |D&
1
+ m.A.A log z
+ +
Set À -+D DDl
Dpp
D and the number of random features
[ 2z
we have
P. - S = =((piiD) (02tr) M+2)
(40)
30

---

Under review as a conference paper at ICLR 2023
where M = L. We complete this proof.
D PROPOSITIONS
Proposition 1 (QLiu et al.
2021)). ). Let St...., Sn. with n. 2 1, be i.idd random vectors on separable
Hilbert spaces such that H = EC 8 ( is a trace class, and for any there exists No (X) < oo such that (C, (H + 3 I))-1) I
(A). Denote Hn as n Di= So @ G. Then for any 8 2 with
probability at least 26, the following holds
|I + 2 1/2 (1 - H.) (11 2
21og (2/0) (N)(
2 (2g)
1/2
n1
n
Proposition 2 (Blanchard & Krämer 20100). For any self- adfoont and positive semidefinite opera- tors and B. if there exists 1j > 0 such that the following inequality holds
(A + 1 1111// A)(A+ 1/2
X 11
- 1 - 17.
2
2
then
1/2 | 21 2) 1-
1
V'i
Proposition 3 (Proposition 10 Rudi & Rosasco (2017); ). For any E (0,1).m 2 1 22r22-1log 20) then with probability at least
(N - -V(A) S 1.55.
where Nm (A) =Tr Tr (1Tm + 1)
Tmm
Proposition 4 (9) in Chen al. 2021) Chen 2012)). Assume that L Sp HK with <rs
1, where Lig is the r-th power of LK, we have f - Jollx = O(X))
1 Σ (yi - yk - (g (m((x)) - -g" (Fom(xx) (xx))) Here we prove the gradient of the empirical risk of [D
||| on g DG,,D,, (g) for all (x), (Xk: yka E Dj.
Proof. We have
i 1
Σ (y: yk (g" 2m (x;) - g" pm (xx))) A||g|1
Ög
4
Σ (yrdm (xx) - 3:dm (x:) + +g (x:) 8" Om (m: + 2Xg
=4 ( (m, WD, TT D, + 2
211 Dm,D, WD,FD,
So, have the results.
E SUPPLEMENTARY EXPERIMENTS
We add the experiments on the dataset Jester Joke. Jester Joke is publicly available from the fol- lowing URL: anonymous ratings 10.00 to + 10.00) of 100 jokes from 73,421 users. We group the reviewers according to the number of jokes they have reviewed. The grouping is 40-60 jakes. For given test reviewer, 300 reference reviewers are chosen at random from the group and their rating are used to form the input vectors. 70 percent of the test reviewer's joke ratings are used for training and the rest for testing. Missing review values in the input features are populated with the median review score of the given reference reviewer. Here, add the comparison with MPRank algorithm (Cortes jet al. 2007). is not a distributed algorithm related to this paper, but is a representative algonithm in the field of least square ranking, is compared here.
and contains over 4.1 million continuous
31

---

Under review as a conference paper at ICLR 2023
Table 3: Comparison of the average testing (standard deviation) and training time (in seconds) Jester Joke dataset, with partitions p 2 and random features 30 and 8, and are the number of communications.
p=2
p=4
Algorithm (m=30)
Error
Time
Error
Time
LSRank
0,411 = 0.002
0.301
0.411 0.002
0.301
MPRank
0,418 0.006
0.285
0.418 = 0.006
0.285
DRank
0.194
0.421 = 0.003
0.105
DRank-C #2
0.415 0.002
0.211
0.418 = 0.002
0.155
DRank-C #8
0.414 +: 0.001
0.252
0.415 + 0.005
0.198
DRank-RF
0.420 + 0.001
0.022
0.421 + 0.002
0.010
DRank-RFaa. #2
0,417 + 0.002
0.027
0.419 = 0.007
0.014
DRank-RF- RF-KKK-FCCHHH
0.415 = 0.003
0.031
0.416 0.002
0.017
DRank #16
0.413 + 0.003
0.040
0.415 + 0.004 p=4
0.021
p=2
Algorithm (m=50)
Error
Time
Error
Time
LSRank
0.411 + 0.002
0.301
0.411 + 0.002
0.301
MPRank
0.418 0.006
0.285
0.418 = 0.006
0.285
DRank
0,419 0.002
0.194
0.421 = 0.003
0.105
DRank-C
0,415 0.002
0.211
0.418 = 0.002
0.155
DRank-C #8
0.414 0.001
0.252
0.415 + 0.005
0.198
DRank-R
0.419 0.002
0.025
0.420 0.001
0.013
DRank #2
0.416 + 0.004
0.029
0.418 = 0.001
0,016
DRank-RE- -F-C #8
0.414 + 0.001
0.034
0.415 + 0.002
0.020
DRank-RF-CK #16
0.413 + 0.002
0.047
0.414 = 0.002
0.026
Table Comparison of the average testing error and training time (in seconds) on simulated and real datasets under the same conditions as (Chen et al. 2021).
Simulated Data
Real Data
Algorithm
Error
Time
Error
Time
LSRank
0.0206
2.5643
0,4902
4.0127
DRank
0.0216
0.0089
0.4913
0.0179
DRank-C C #8
0.0206
0.0213
0.4910
0.0454
DRank-RFF
0.0217
0.0003
0.4914
0.0021
DRank-RF-C #8
0.0207
0.0021
0.4910
0.0087
The empirical evaluations are given in Table 3 where the number of random features is m 30 and 50 and the number of partitions is p and 4. In Table 3 results are similar to those on the simulated data and MovieLens dataset. The average testing errors of our methods, the exact method, MPRank, and DRank remain at the same level, which verify the effectiveness of our methods on the real dataset. The testing error of DRank-RF-C decreases with the increase of the number of communications, which demonstrates the effectiveness of the com- munication strategy on the real dataset, The proposed DRank-RF RF and Drank-RF- have significant advantages over LSRank, MPRank, DRank, and DRank- C in the training time. These are consistent with the theoretical analysis.
find that the experimental
We add the experiments under the same experiments setting as (Chen al., 2021) on the datasets mentioned in the main paper. Table | shows the experimental results with partitions = 60, di- mension q = and random features m 150 on simulated dataset with the same data generating distribution (Chen et al.] 202T), and 60 and m 150 on Moviel dataset. Our algorithm DRank-RF has a significant advantage over DRank and LSRank in the training time. Under the same conditions, the testing errors of the proposed DRank-R RF and DRank-RE RF-C are similar to those of DRank and DRank-C.
32


Reviews:
[{"review_id": "YSZBw9liC9o", "reviewer": "Reviewer_9DzG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "1. They study the convergence of pairwise ranking using distributed learning and random features (DRank-RF) via both theoretical assessments and numerical experiments.\n2. They claim that prior work in distributed learning mainly focuses on pointwise kernel learning, and the existing work for pointwise kennel learning suffers from high computational requirements. This work explores the efficient way of doing distributed pairwise ranking kernel learning by combining distributed learning and random features for pairwise ranking kernel learning.\n3. Both theoretical analysis and extensive experiments are conducted. They derive the convergence rate of the proposed method, which is sharper than that of the existing state-of-the-art distributed pairwise ranking kernel learning.\n4. They propose a communication strategy to further improve the performance of DRank-RF, called DRank-RF-C.\n", "summary_of_the_review": "I did not fully verify all the proof in the supple. Given that is correct, I don’t observe errors in the theoretical analysis.", "strength_and_weaknesses": "Strength\nThe theoretical bound they derived for DRank-RF is sharper than existing state-of-the-art distributed pairwise ranking kernel learning.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Snb9g-AwLI", "reviewer": "Reviewer_NK1r", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This study proposes variants of DLSRank and DLSRank-C by (Chen et al., 2021) that apply random features (RF).\nIn the experiment, RF speeded them up without reducing prediction performance in the pairwise comparison task.", "summary_of_the_review": "I see this study as an RF-version of (Chen et al., 2021).\nI cannot find a sufficient (for ICLR) novelty from (Chen et al., 2021) (see [2*]).\nAlso, I think that it may have critical mistakes (see [6*]).\n", "strength_and_weaknesses": "I place special emphasis on comments with the mark *.\n\n---\n\nStrength:\n\n[1] This is the first study to apply RF to DLSRank and DLSRank-C by (Chen et al., 2021).\n\n---\n\nWeakness:\n\n[2*] I think that this study should be viewed as an RF-version of (Chen et al., 2021).\nThe authors should clearly state this perspective in Section 1.\nFor example, communication strategy has also proposed in (Chen et al., 2021), but it sounds like the authors considered the strategy newly in the current style of writing.\nI cannot find a sufficient (for ICLR) novelty from (Chen et al., 2021).\n\n[3] Some results of Table 2 overlap.\nIt can be simplified.\n\n[4] I do not know the notation manner of $2^{[-2:0:5:5]}$ and $2^{[-13:2:-3]}$.\nPlease define it.\n\n---\n\nQuestion:\n\nRegarding the following points, it may be that the authors' description is appropriate and there is no problem, just because I have not understood it correctly.\nI do not reflect these points in my current recommendation score.\nDepending on the authors' response, I may change my recommendation score.\n\n[5] Almost all of the theorems in this paper are similar to those of (Chen et al., 2021).\nAre there any difficulties in theoretical analysis associated with application of RF?\n\nAs noted in Remark 1, the authors provide a sharper convergence rate than in that of (Chen et al., 2021).\nIt would be better to clearly describe the reason of this improvement (is it a miss of (Chen et al., 2021) or merit of RF?).\n\n[6*] I cannot prove the statement \"Note that, the gradient ~ all $(x_i,y_i), (x_k,y_k)\\in D$.\" located between (6) and (7).\nIs this statement correct?\nPairwise learning and distributed learning may have bad compatibility:\nIn distributed learning, one cannot calculate the cross term between an object depending on $(x_i,y_i)\\in D_1$ and an object depending on $(x_j,y_j)\\in D_2$ of original pairwise objective.\nI think that the statement is incorrect.\n\n[7] Why did the authors change the experimental setting (e.g., data generating distribution in Section 6.2, and $p$ in Section 6.3) from (Chen et al., 2021)?\nIf the proposed methods did not work well with the previous settings, it would be better to conduct experiments with the previous settings and the changed settings, and consider and describe the reasons why the proposed methods work or do not work well.\n\n[8*] Even for a random prediction $f$, $R(f)$ is 0.5.\nI am not satisfied with all the experimental results in Table 2 in Section 6.3.\nI fear that the LSRank (and DLSRank) on which this study is based may not be good.\nThus, I want the authors to additionally try other type methods such as OLS (and ordinal regression or standard classification methods since $\\{y_i\\}$ of MovieLens are discrete).\n\nResults of this paper are similar to those of (Chen et al., 2021), but I think that the experiment of (Chen et al., 2021) also may not be sufficient (see [6*]).\n\n[9*] This comment relates to [8*].\nWhat is the advantage of LSRank compared with ordinary least squares (OLS) regression?\nI am interested in the relationship between LSRank and OLS since their optimal predictors are the same conditional mean.\nI would like the authors to make an experimental comparison at least.\nAdditionally, if there are advantages, it would be better to mention them in the paper.\nI think distributed OLS is more easy.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6a493QplPFk", "reviewer": "Reviewer_R27i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the statistical properties of pairwise ranking using distributed learning and random features ( DRank-RF) and establish its convergence analysis in probability. Numerical results confirm the practical aspects of the theory. ", "summary_of_the_review": "The authors develop the DRank-RF approach and study its theoretical properties. Empirical results confirm its practical utility.", "strength_and_weaknesses": "The paper is rigorous, but several results are based on the prior work of DX Zhou and collaborators. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject