A Kernel Perspective on Distillation-based Collaborative Learning
Authors: Sejun Park
Kihun Hong
Ganguk Hwang
Venue: NeurIPS 2024 poster (2024)
Keywords: Kernel Regression
Distillation-based Collaborative Learning
Generalization Analysis
Kernel Distillation
Primary area: learning_theory

Abstract: Over the past decade, there is a growing interest in collaborative learning that can enhance AI models of multiple parties.
However, it is still challenging to enhance performance them without sharing private data and models from individual parties.
One recent promising approach is to develop distillation-based algorithms that exploit unlabeled public data but the results are still unsatisfactory in both theory and practice.
To tackle this problem, we rigorously analyze a representative distillation-based algorithm in the view of kernel regression.
This work provides the first theoretical results to prove the (nearly) minimax optimality of the nonparametric collaborative learning algorithm that does not directly share local data or models in massively distributed statistically heterogeneous environments.
Inspired by our theoretical results, we also propose a practical distillation-based collaborative learning algorithm based on neural network architecture.
Our algorithm successfully bridges the gap between our theoretical assumptions and practical settings with neural networks through feature kernel matching.
We simulate various regression tasks to verify our theory and demonstrate the practical feasibility of our proposed algorithm.

A Kernel Perspective on Distillation-based Collaborative Learning
Sejun Park
Kihun Hong Ganguk Hwang"
Department of Mathematical Sciences
Korea Advanced Institute of Science and Technology (sejunpark, muri9911, guhwang Baannng/KKaaaa @@kaist.ackrr
Abstract
Over the past decade, there is a growing interest in collaborative learning that can enhance Al models of multiple parties. However, it is still challenging enhance performance them without sharing private data and models from individual parties. One recent promising approach is develop iistillation-based algorithms that ex- ploit unlabeled public data but the results are still unsatisfactory in both theory and practice. To tackle this problem, based algorithm in the view of kernel regression. This work provides the first theoretical results to prove the (nearly) minimax optimality of the nonparametric collaborative learning algorithm that does not directly share local data or models massively distributed statistically heterogencous environments. Inspired by our theoretical results, we also propose practical distillation-bast collaborative learn- ing algorithm based on neural network architecture. Our algorithm successfully bridges the gap between our theoretical assumptions and practical settings with neural networks through feature kernel matching. We simulate various regression tasks to verify our theory and demonstrate the practical feasibility of our proposed algorithm.
rigorously analyze a representative distillation-
Introduction
Collaborative learning of Al models in decentralized settings is an important problem covered in various fields of machine learning such as distributed learning [0, 70), Federated Learning (FL) 23
In particular, this theme 45 61. In this context, each local party is typically viewed as subordinate entity within the collective learning system. For example, most FL algorithms mandate the exchange of local AI model information among participating local parties. Under this scheme, local Al models are usually subjected to restrictions their architecture. However, from the perspective of collaboration, each local party may have to be regarded as an independent learning agent, meaning they are not obligated to fully share their model information. In short, the model (or parameter) exchange in FL algorithms can emerge a critical issue in collaborative learning.
peer-to-peer learning 3 and miscellaneous collaborative learning
has been most actively discussed in the context of FL [24
Fundamentally, addressing this issue necessitates an alternative medium for sharing learning information distinct from model exchange. Indeed, Distillation-bass Collaborative Learning (DCL) [14] 30 [4] provides good answer. In these algorithms, local training information is
shared via the outcomes of Al models on additional unlabeled public data. The collected information is then utilized for knowledge distillation (1 to each local Al model. As mentioned in [14] 48). this procedure is agnostic to model heterogeneity and avoids the direct sharing of local model information. This is key advantage that distinguishes DCL from traditional FL..
Cooresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Despite its pioneering nature and potential utility, DCL has not been sufficiently explored. A significant reason for this is the lack of theoretical understanding regarding knowledge distillation and its effectiveness in massively distributed statistically heterogeneous environments. Our work stems from the fundamental question of whether DCL algorithms can be theoretically effective in these settings. Inspired by [48] [58) we analyze FedMD 30 41. the most standard DCL algorithm from nonparametric perspective. Specifically, we adopt an aperator-theoretic approach [5 15] 37 [3 65 to obtain an upper rate of convergence for the nonparametric version of FedMD (named DCL-KR) in the expected sense. Remarkably, our analysis reveals that DCL-KR achieves a nearly minimax optimal convergence rate, where the prefactor is independent of the number of participating local parties. It is worth noting that DCL-KR is the first nearly minimax optimal collaborative learning algorithm that does not directly share local data models in massively distributed statistically heterogeneous environments. The novelty of our theoretical results and their comparison to prior works are provided in Section Saationnann and
Nevertheless, our theoretical analysis does not fully demonstrate the efficacy of DCL, algorithms based on neural network architectures. Instead, our theoretical results serve as inspiration for designing novel DCL algorithm for regression that refines existing approaches. Consequently, we propose a Distillation-based Collaborative Learning algorithm over heterogeneous Neural Networks (named DCL-NN) for regression tasks. DCL-NN leverages kernel matching to align the feature kernels from the last hidden layer of each local AI model with an ensemble kernel. This procedure brings heterogeneous neural networks into the regime of DCL-KR.
Finally, we conduct experiments on DCL.KKR and DCL-NN. To illustrate the superiority of our algorithms, we compare them with several baselines on various regression tasks. Experimental results show that DCL-KKR achieves the same performance as the centralized model, even beyond the theoretical results. We also observe that DCL-NN significantly outperforms previous DCL frameworks in most settings.
In summary, our contributions are as follows:
1. In Section 3] we theoretically prove that nonparametric version of the most standard distillation- based collaborative learning algorithm (named DCL-KR) is nearly minimax optimal in mas- sively distributed statistically heterogeneous environments.
2. Inspired by the results provided in Section 3 we propose a distillation- based collaborative learning algorithm with heterogeneous neural networks (named DCL-NN) Section
4
3. In Section we conduct experiments to empirically confirm theoretical results and show the practical feasibility of our proposed algorithms.
2 Related Work
Federated Learning Most FL algorithms [45] communicate model parameters for collaboration. This approach has been extensively studied under various constraints, including data privacy M statistical heterogeneity [24 31. communication efficiency (51), personalization [13 59], and robustness (25] While it has been successful both theoretically and experimentally, this type of FL is limited in terms of the privacy and flexibility of local Al models, as the algorithms directly access the structures and parameters of the local models. Our study focuses on distillation-bel collaborative learning, where the privacy and flexibility of local AI models are fully guaranteed.
Distillation-basel Collaborative (or Federated) Learning The type of algorithms investigate operates by communicating the functional information of local AI models. These algorithms typically assume the availability of additional public data points. In this case, the outcomes of local models on the public dataset are used for collaboration. For instance, Li and Wang [30]. Lin et al. [1]. Park al. 488 iteratively collect predictions of local models on the public dataset and then aggregate them into a naive ensemble (with or without a fixed linear transformation) to distribute. On the other hand, Cho et al. 77) Zhang et al. 69), Fan et al. [14] apply personalized ensemble strategies by additionally learning the mutual trust between models. Makhija et al. 44 propose FedHeNN, which distills training information in the form of matching feature kernels instead of the predictions of local AI models on the public data. Both FedHeNN and DCL-NN utilize centered kernel alignment [8] to match feature kernels of local models, but DCL-NN uses the ensemble distillation for predictions as well. Thus, DCL-NN enables parties to learn from the entire input space.

---

Table 1: Comparative analysis of decentralized environments for (nearly) minimax optimality of representative collaborative learning algorithms with kernel regression. nFedAvg indicates the nonparametric version of FedAvg in [58] Note that IED 48 achieves a weaker version of minimax optimality.
interaction method
local data
massively distributed
non-i..d& unbalanced
Methods
privacy
DKRR 38
divide-and-conque
DC-NY
666
divide-and-conee
DKRR-CM
40
model exchange model exchange
DKRR-RF-CN
43
DKRR-NY-CM
67
model exchange
nFedAvg [58]
model exchange
IED
48
knowledge distillation knowledge distillation
DCL-KR (ours)
Decentralized Learning with Kernel Regression A number of studies have investigated the minimax optimal rate of regularized kernel regression algorithms such as kernel ridge regression and
gradient descent-baai based kernel regression with early stopping [S] 65 In particular, over the past decade, the growing interest in decentralized learning has led to active research in the generalization analysis of decentralized kernel regression. While hivide-and-conquer algorithms
(3 38 66 770
play significant role in this research flow, most of them fail to account for statistical heterogeneity and massively distributed cases, along with privacy preservation, which has received recently. On the other hand, decentralized kernel regression algorithms with multiple communication
of attention
rounds [40] 43
58) (67 achieve superior theoretical results compared to the divide-and-con -nnnqquenddco algorithms. However, the discussions of these algorithms primarily focus the efficiency of resource costs 40 67 while research on relaxing environmental constraints has been scarce. For example, most of these works assume a limited number of parties to prove the optimality in minimax sense.
48
To the best of our knowledge, 48 centralized environments. Similar to our work, Park et al. [88] study the convergence rate of distillation-based collaborative learning with kernel regression. However, their results demonstrate a weaker version of minimax optimality and do not cover statistically heterogeneous environments. In this regard, Su et al. (58) offer a promising methodology. They analyze nonparametric versions of FedAvg [45] and FedProx [31], representative FL algorithms involving model exchange, in general decentralized environments such as statistically heterogeneous and massively distributed scenarios. In this work, we extend their methodology to analyze FedMD [30 4] from nonparametric perspective in massively distributed statistically heterogeneous environments. We summarize the comparison between work and prior studies in Table I Note that algorithms that do not employ Nyström scheme (including nonparametric FedAvg [58]] fail to preserve local data privacy due to the inherent characteristics of kernel regression. On the other hand, DC-NY [66] and DKRR-NY-CM (67 can achieve the local data privacy preservation by utilizing the public data as Nyström centers.
stand as the only investigations that consider general de-
3 DCL-KR: A Nonparametric View of FedMD
In this section, we establish the theory of nonparametric version of FedMD 30 standard distillation- collaborative learning algorithm.
41 the most
3.1 Preliminaries
Let Px.y Px Pylx be a Borel probability measure on X' R where X' is compact subset of Rd and we assume the support Px is X. The goal of the regression problem find a minimizer of the population risk, i.e.,
E(h) 1
min E(h), h.X
(xxx))>xx, hxx))2
Then, the function fo X + R defined by x + E (+1x)) 121, xo X' is a target function.
3

---

Let k x X - RRR be a Mercer kernel [9] where := (supxe, x)) < oc and H2 be reproducing kernel Hilbert space associated k. We set lix k(,, x) and the covariance operator Tk IH4 Hg with respect to any Borel probability measure on X' defined as
TR. 1(x))xx du(x).
Then we can see that Tk 1 to where by : Hig - I., is a natural embedding, L2 (, v)) denotes the I space, and superseript denotes the adjoint operator of given operator. We also define the sampling operator Sn H - R by h + [h(x').
h(x*)] ) and Tx,x := SD when D = {(xx ). (x", ,})) with X {x' .x") } is given. Since Sp depends only on data inputs X, we can define the sampling operator for unlabeled datasets in the same way. See
Appendix A.1 for further details.
3.1.1 Kernel Gradient Descent with Early Stopping
Given a dataset = =[(x,, "r),,"")," y""} generated from Pxay consider the empirical risk ED Hg R given by
(b) = Spp - y
where y -l ,.'...... I" Here, || 1l2 denotes scaled Euclidean norm ||v|22 = ( E v/2 From the functional derivative VED(h) (Sph y), the gradient descent scheme becomes
0, # = I - y) (1 -1= 1,2,....
where {7h Jen is a set of learning rates. In this work, we set 1,. f E N for a fixed E (0, 1/k²) Then, a simple calculation gives 1/2 - (S as t + oo provided that the operator S SDST invertible. The limit is known the minimum regressor generalizes poorly unless there is no noise [3 39, early stopping strategies are usually applied to avoid the overfitting issue. With adequate stopping rules, gradient descent-based kernel regression has an optimal rate in a minimax sense (36 67
interpolation [49 of D. Since the interpolation
3.2 DCL-KR Algorithm
From now on, we consider the setting that there are m parties and the party has private local Assume that all data D U D, are ii.d. with the distribution Px.y but each local dataset does not need to have the same distribution. Let Z (z)
data D; = [(x] v/) : 1.... .n) for i 1.... ........ m.
==o} } c X be the additional public inputs. The goal of all parties is to have their models that perform well on the distribution Px. In other words, each party expects be able to make good predictions not only for its local data distribution but also for unseen data distribution through collaborative learning.
Similar to [58] we construct a nonparametric version of FedMD (called DCL-KR), which pre- sented in Algorithm In Algorithm Gj is one-step local gradient descent update on ED,, i.c., G. - ST (Sp. by)) where y, = [y] 1.. Similarly Gr is a one-step gradient descent update on E. i.c., G.h = h - n (Szh yp.t).
3.3 Theoretical Results
In this subsection, we show the nearly minimax optimality of DCL-KR. To derive theoretical results, we assume the following conditions regarding regularity of noise, the kernel k. and the target function fō as below.
Assumption 3.1. We assume Eyro, 8² < 00 and
( exp
(x)
f (x) -1) dp.)x(Ulx) S 722
Vx E X
M
M
22
where M and positive constants.

---

Algorithm DCL-KR Algorithm
1: Hyperparameters: T: total communication round, E: the number of local iterations at each communication round, 7f: learning rate 2: Initialize local models fu.0 = 0 for i .... m.
3: for = 0,... T 1 do
4:
for party i = 1, m72 do
5: Update the local model E times by gradient descent on the empirical risk Ep,
fl, 9 fr.-
6:
Upload the local predictions on Z to the server
yp.t = Szfi.
7:
end for
8:
The server aggregates the local predictions to compute the consensus prediction
ptt
p.t
and then distributes yp. to all local parties.
9: For party i = 1,..... m), update the local model by infinitely many iterations of gradient descent the empirical risk &(2.)..)
fa,t1
9:00 9t.
(1)
with an initialization 9i, chosen from a subspace spanned by kz', Kgmo. end for
Assumption 3.2. Let \ 2 0 be eigenvalues of Trppx There fixed positive constants C, and C such that
c SAS C. WeN
for some E (0, 1).
Assumption 3.3. The target function fō satisfies
fo E h Hlg h Thips
Tx-1/2 where llglaa. S R
for some E [2, 1] where T/-1/2 is the (r 1/2) power of operator Tk.p. and R > is fixed constant. In particular, fö Hg.
The above assumptions determine the minimax lower rate 3 and are standard assumptions in many prior works [5 33 35). detail,
Assumption 3.1 implies that the noise is not excessively large. This assumption is general noise condition that encompasses wide range of cases. For instance. noise with Bernstein condition such as sub-Gaussian noise satisfies Assumption 3.1
Assumption 3.2 is about the eigenvalue decay of Th. From this assumption, derive bounds on the effective dimension that is related to covering and entropy number conditions [5
Assumption 3.3 is related to the regularity of the target function, specifically how well the RKHS induced by the kernel & represents the target function.
Under these assumptions, we can theoretically show the performance guarantee of DCL-KR. The proof is provided in Appendix A.2 Note that {h)) E(ft) 1 || (h - ft) is the excess risk of regressor and so the quantity ||, (h fo 111,_ indicates the generalization ability h.
5

---

Theorem 3.4. Under Assumption 3.1
3.2 and 3.3 with no 2 n n) public inputs indepen-
dently generated from Px such that the Radon-Nikodye derivative
des satisfies dps
dpx dix
0
S
S
B on X for some B E (1,
DCL-KR gives the performance guarantee
Ell (fiT- - S0)llza, SC. B'n T log
for all i = i......, where oj E 1/21/22) is a fixed learning rate, an adequate stopping rule, and the prefactor C' does not depend on B, and n.
Since the convergence rate 2 is the minimax lower rate under Assumption 3.1 Theorem 3.4 implies that DCL-KR has an almost same convergence rate as the minimax optimal central training when there sufficiently many public inputs. To the best of our knowledge, this the first work to prove the (nearly) minimax optimality of a collaborative learning algorithm that does not directly share local data models in massively distributed statistically heterogeneous environments. For example, divide-and-conquee algorithms work for limited m. Specifically, DC- 2 On and DKRR-NY-CN. 677 assumes S O(n - ). However, Theorem 3.4 does not require any condition on m. Moreover, Theorem 3.4 deals with more general setting than the theory in [88] 58 For example, Su et al. [58) only cover r 1 of Assumption 3.3 On the other hand, Park et al. [48] do not consider Assumption 3.2 which gives a finer result. Compared with 48) condition.
3.2 and 3.3
NY 666 assumes
also reduce the required size of public inputs and drop the statistical homogeneity
The convergence rate in Theorem 3.4 has additional factor log n compared with minimax lower rate [5] 15]. but this logarithm term grows slower than any polynomial. Note that an additional logarithm term commonly appears in the context of gradient descent-based kernel regression with Nyström scheme 335 36
Theorem 3.4 allows that the public input distribution Ax can be different from the local input distribution Px. is natural that the condition (2) is required since Åx should cover Px for fully distilling training information. We can see that the discrepancy between Ax and åx affects the upper bound in Theorem 3.4 as the multiplication of B". We can remove B" in the upper bound by increasing public inputs. See Appendix A.3 for details.
3.3.1 Proof Sketch of Theorem 3.4 and Comments
In the proof of Theorem 3.4 we decompose the term Lp (fi. fō) into four parts, say (I), (II), (III, and (IV) (see Eq. (7)) The proof is to bound the norms of these terms. Note that DCL-KR can also be understood
Nyström version of nonparametric FedAvg (58) from the recurrence relation (6)
(I) and (II) appear similarly in [58], except that (I) and (II) incorporate projections. To handle these terms, we reinterpret the proof presented in (58) in operator form instead of matrix form and extend
to our setting. We obtain a norm bound of (II) containing a quantity linked to the local Rademacher
complexity. (Appendix A.2.2 and A.2.3)
Comparing with [58], (III) and (IV) are additional terms induced by the procedure that distills functional information from the local regressors. We apply techniques used in [35] 4g
53
to bound
(II) and (IV). (Appendix (A2.4)
Note that previous works applying local Rademacher complexity based stopping rule (50 58 deal only. In this work,
with the case of previous works (50 (58) and prove an extended version (Lemma[A.6) of a well-known property (60]. As result, our theory covers [ 1] which affects the minimax lower rate. (Appendix A.2.5
new stopping rule T which is extension of
4 DCL-NN Algorithm
In this section, we retain the problem setting from Section S but employ heterogeneous neural networks as the local models. Based the theoretical results in Section propose novel

---

distillation-baal based collaborative learning algorithm DCL-NN across heterogeneous neural networks in decentralized setting.
key factor contributing to the successful theoretical guarantee of DCL-KR lies not only in the linearity of kernel regression but also in the equality of kernels across local models. In fact, the public data predictions can vary in different directions, even if the same training data points are used when kernels differ (See Appendix B Therefore, we match the kernels of local AI models. Specifically, we use linear feature kernels 18, 64) induced by the features from the last hidden layers of local AI models for kernel matching. For example, for a neural network f : X + where f(-) w g() +
g X - R W E R and E IR we use
xy(xt,x²) g(xx) g(x)x.
x
(3)
as the feature kernel of f. Through this idea, we can bring the setting closer to the regime of DCL-KR. Note that our theoretical results suggest that the target kernel should be a good kernel. Indeed, we observe that the naive ensemble
kf.
(4)
has significantly better performance than individual feature kernels ff..... ky, (See Section and Appendix B). Here, fi is the local model of the ith party with its local feature kernel ky, obtained by 3 (i 1, .... .m). Therefore, we align local feature kernels ff: ,kk, in kernel distillation manner with the ensemble kernel & obtained by 4
For this purpose, introduce Centered Kernel Alignment (CKA) 8 kernel similarity mea- sure. CKA is a typical measure associated with the similarity of two representations of neural networks (27 and is often used for kernel matching in neural networks 44] To compute empirical CKA between two kernels k and 2i on inputs (ct,... c²), we first calculate the Gram matrices K1 c2)) Jishh and K2 [k2( c We then compute the empirical
CKA via
HSIČ(K K2)
CKA(k1, k2)
HSIC(Ki, HSIC((,,, K2)
Here, HSIC is an estimator of the Hilbert-Schmidt Independence Criterion (HSIC) defined as HSIC(K,, K2) (p 1)2 tr( (K,HKHH)
1
where H I= 111 is the centering matrix. In the kernel distillation procedure, the ith local
party maximizes CKA(k;f k) on public inputs Z (i = 1,....,,, Notably, this procedure requires only single communication round for exchanging pairwise feature kernel values on public inputs, ensuring that our algorithm operates exclusively within the function space.
After the kernel distillation procedure, all local AI models have similar feature kernels up to constants. So we can follow an analogous process as in DCL-KR. Note that we perform learning rate scaling described in Appendix B to compensate the kernel scale difference. It makes the impact of local iterations consistent. We also provide the complete algorithm (Algorithm 2 and further details for Section in Appendix B
5 Experiments
In this section, we evaluate the performance of DCL-KR and DCL-NN. We compare them with baselines on various regression tasks.
Datasets We use the following six regression datasets to evaluate the performance. Target variables are one-dimensional in all datasets. (1) Toy-1D 33 and (2) Toy-3D 6 are synthetic datasets with one-dimensional and three-dimensional inputs, respectively. (3) Energy
tabular dataset from the UCI database [2 to predict appliances energy use with 28 features. (4) RotatedMNIST is an image dataset where it aims to predict the rotation angles for given rotated images of the MNIST [II]
images. (5) UTKFace (71) and (6) MMBBWIKK
42
52
are image datascts for age estimation.
7

---

16.-2
4.0 16-2
centre
RMSSE
2.0
1.5
00
200
The number of parties
The number parties
(a) Toy-1D Dataset
(b) Toy-3D Dataset
Figure I: Performance of central Kernel Ridge Regression (centralKRR), central Kernel Regression with Gradient Descent (centralKRGiD, DC-NY, DKRR-NY-CM, IED, and DCL-KR Toy-ID and Toy-3D
2.5
2.5
Averge RMSSES
Zvarage of RMASES
1.5
1.0
1.0
20
40
50
80
100
20
40
100
The rumber parties
The number parties
(a) DCL-KR
(b) IED
Figure 2: Performance of IED and DCL-KR with no 2ー
(log n) Toy-3D
We compare kernel machine-based collaborative learning algorithms on two datasets Toy- 1D and Toy-3D. On the other hand, compare neural network-based collaborative learning algorithms five datasets Toy-3D, Energy, RotatedMNIST, UTKFace, and IMDB-WIKI.
Baselines We compare DCL-KR with two central kernel regression models to verify our theoretical results. These two central models have the minimax optimal convergence rate. We also utilize existing decentralized kernel regression algorithms that does not directly share local data and models (DC-NY (66), DKRR-NY-CM [67], IED [88 baselines for DCL-KR. On the other hand, we
adopt FedMD with unlabeled public inputs 30 FedHeNN 44,, and KT-pFL (69 as basclines
for DCL-NN.
Setup The number of parties ranges from 10 to 100 for kernel machine-based algorithms and 50 for neural network-based algorithms. We construct statistically heterogeneous decentralized environments with Algorithm 3 For neural network- based algorithms, we use 4 different neural network architectures for local models in settings. For instance, use ResNet- 18, ResNet-34. ResNet-50 [20], and MobileNetv2 [54] for large-scale image datasets. We utilize the average of Root Mean Squared Errors (RMSEs) the local Al models on a test dataset performance metric. The test data points have the same distribution as the whole local data distribution. We apply FedMI with few communication rounds for pretraining of DCL-NN. See Appendix C for detailed experimental configurations.
5.1 Results Kernel Machine-based Algorithms
The performance of DCL-KR and its baselines presented Figure We set the number of parties 10, 20. 100, the number of private data points 50m, and the number of public inputs nip . (log10 n))3. We first set As Px: i.e., the public data distribution is the same as the entire local input distribution. As shown in Figure I DCL-KR outperforms the baselines in all

---

-1.
-1.6
RMGEE
2-03
Logartten Avuragee RASGE:
-2.
pe1
-1.8
-222
-2.0
-2.4
Logantam
-266
-2.0
2.6
2.5
3.0
3.5
4.0
4.5
2,5
3.0
3.5
4.0
4.5
login
logm
(a) DCL-KR (log-scale)
(b) IED (log-scale)
Figure 3: Performance of IED and DCI.-KR with ix # px on Toy-3D
experimental settings and achieves comparable performance to the central models. This result implies that DCL-KR has not only the nearly optimal convergence rate but also the same performance as central kernel regression models. In contrast, DC-NY and DKRR-NY-CM exhibit significantly lower performance compared with DCL-KR in massively distributed environments where their theory does not cover. IED does not show significant performance drop in massively distributed environments even though its theory is built on the statistical homogeneity condition of local data distributions.
To further compare the performance of DCL-KR and IED, which show similar results to central models, we analyze the effect of no and Px on their performance (Figure 3 Figure 2 illustrates that, as expected from the theoretical results, IED requires more public inputs than DJCL-KK to achieve good performance. Moreover, when there is public distribution shift, DCL-KR maintains its convergence rate, whereas the convergence rate of IED deteriorates. (See Appendix C.3.3 for experimental details.) Overall, our experiments validate the thcoretical results of DCL-KR and demonstsrate its superiority over previous results. For additional experimental results and analyses, please refer to Appendix C.3
5.2 Results on Neural Network-based Algorithms
Table shows the performance of DCL-NN and baselines on five regression tasks. We also present the performance of standalone models and centralized models to assess the performance of the collaborative algorithms. For some cases exhibiting training instability, we report the best test error (marked with asterisks) observed across all communication rounds, while relying on a fixed number of communication rounds for the other cases.
As be seen in Table 2 DCL-NN outperforms the baselines all regression tasks. Note that FedHeNN employs kernel matching similar to DCL-NN, but it lacks supervision of label prediction through collaboration, resulting in insufficient performance improvement compared standalone models. Given the superior performance of DCL-NN, it is evident that incorporating supervised learning for label prediction alongside kernel matching desirable. the other hand, while FedMD performs significantly better than standalone models, the performance of DCL-NN is consistently better. Considering that we utilize FedMD for pretraining DCL-NN, we can see that it performs better than FedMD-only collaborative learning by first training local models with FedMD and then using DCL-NN. conclusion, the experimental results support the practical effectiveness and superiority of DCL-NN over baselines.
Kernel Distillation Procedure To verify the necessity of kernel distillation, we examine the changes in the performance of local feature kernels and the CKA between them during the kernel distillation procedure. We conduct this experiment on UTKFace. We utilize the RMSE of a kernel linear regression model trained on all local data as a kernel performance measure. The results are presented in Figure 4 As shown in Figure E both kernel performance and CKA undergo temporary degradation due to the change the objective function at the initial stages. However, as training progresses, both metrics recover and kernel performance surpasses its initial level. Since kernel distillation aims to ensure that all local feature kernels are similar with high performance, the experimental results verify the effectiveness of kernel distillation.

---

Table 2: Performance comparison of FedMD, FedHeNN, KT-pFL,, and DCL-NN five datasets. The values are presented as the average of RMSEs along with standard deviations. For calibration, the performance of standalone models and centralized models is also provided.
Toy-3D
Energy
RotatedMNIST
UTKFaace
IMDB-W WIKI
Central
0.041
0.085
0.139
0.143
0.095
Standalone
0.288
0.008
0.095 + 0.000
0.680 + 0.003
0.216 + 0.004
0.137=10.000
FedMD
0.200
0.008
0.093 + 0.000
0.249 + 0.001
0.151 0.004
0.113=0.000
FedHeNN
0.264 = 0.009
0.094" 0.000
0.405 + 0.016
0.177 = 0.000
0.140 10.000
KT-pFL
0.243 + 0.002
0.093* - 0.000
0.317 + 0.003
0.167 = 0.001
0.130 0.130"=0.002 =0.002
DCL-NN
0.079 0.005
0.087 - 0.001
0.227 + 0.003
0.148 + 0.001
0.110=0.000
Local Peature Sarnels get Nome
0.150
Korre Performance
0.149
Avarage of COOs
0.88
0.86
0.148
0.147
0.82
0.146
50
1.00
150
200
50
160
150
200
Epochs
Epochs
(a) Kernel Performance
(b) Centered Kernel Alignment
Figure 4: Kernel performance and CKA (with standard deviations) during the kernel distillation procedure. The performance of the target kernel obtained by is also provided.
For additional experimental results, please refer to Appendix C.4
Conclusions
In this work, we analyze distillation-baaee collaborative learning from nonparametric perspective and propose DCL-NN, a practical algorithm as an extension. We demonstrate that DCL-KR, nonparametric version of FedMD, has nearly minimax optimal convergence rate in massively distributed statistically heterogeneous environments. Inspired by DCL-KR, we propose DCL-NN, novel distillation-basee collaborative learning algorithm for heterogeneous neural networks. Our experiments confirm the theoretical results of DCL-KR KR and demonstrate the practical effectiveness of DCL-NN. For discussion of the limitations of our work, please refer to Appendix D
Broader Impact Our work explores the methodologies collaborative learning under data and model privacy preservation. In this regard, research holds the potential to positively impact the facilitation of collaboration among Al models without raising concern about information disclosure. On the other hand, our work does not pose any particularly noteworthy negative consequences, given its aim to contribute to the advancement of the general field of machine learning.
Acknowledgments and Disclosure of Funding
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea governeen((MSIT) (Grant No. 2S-2019-NR040050).
References
[1] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics, pages 2938-2948. PMLR, 2020.
10

---

[2] P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. The Annals of Statistics, 33(4):1477-1537, 2005.
[3] A. Bellet, Guerraoui, M. Taziki, and M. Tommasi. Personalized and private peer-to-pee machine learning. In International Conference on Artificial Intelligence and Statistics, pages 473-481. PMLR, 2018.
[4] O. Bousquet. Concentration incqualities for sub-additive functions using the entropy method.
In Stochastic Inequalities and Applications, pages 213-247. Springer, 2003.
[5] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
[6] X. Chang, S.-B. Lin, and D.-X. Zhou. Distributed semi-supervised learning with kernel ridge regression. The Journal of Machine Learning Research, 18(1):1493-1514 2017.
[7] Y. J. Cho, J. Wang, T. Chirvolu, and G. Joshi. Communication-effcieeet and model- heterogeneous personalized federated learning via clustered knowledge transfer. IEEE Journal of Selected Topics Signal Processing, 17(1):234-247, 2023.
[8] C. Cortes, M. Mohri, and A. Rostamizadeh. Algorithms for learning kernels based on centered alignment. The Journal of Machine Learning Research, 13(1):795-228 2012.
[9] F. Cucker and D. X. Zhou. Learning theory: an approximation theory viewpoint, volume 24. Cambridge University Press, 2007.
[10] Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, Tucker, K. Yang, et al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
[11] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-143) 2012.
[12] D. Dheeru and E. Karra Taniskidou. UCI machine learning repository, 2017. URthttpp //archive. www.uc......uueee..
[13] A. Fallah, A. Mokhtari, and Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. In Advances in Neural Information Processing Systems, volume 33, pages 3557-3568, 2020.
[14] D. Fan, C. Mendler-Dümner, and M. Jaggi. Collaborative learning via prediction consensus. In Advances in Neural Information Processing Systems, 2023.
[15] S. Fischer and I. Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. The Journal of Machine Learning Research, 21(():8464 8501, 2020.
[16] J. Fujii, M. Fujii, T. Furuta, and R. Nakamoto. Norm inequalities equivalent to heinz inequality. Proceedings of the American Mathematical Society, 118(3):827-330, 1993.
[17] Z.-C. Guo, S.-B. Lin, and D.-X. Zhou. Learning theory of distributed spectral algorithms. Inverse Problems, 33(7):074009, 2017.
[18] B. He and M. Ozay. Feature kernel distillation. In International Conference on Learning Representations, 2021.
[19] C. He, M. Annavaram, and S. Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. Advances in Neural Information Processing Systems, -4080, 2020.
[20] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[21] G. Hinton, O. Vinyals, and Dean. Distilling the knowledge neural network, arXiv preprint 1033v2150. 2015.

---

[22] S. Ioffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pages 4484556. PMLR, 2015.
[23] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and Trends Machine Learning, 14(1-2)11-20,, 2021.
[24] P. Karimireddy, Kale, M. Mohri, S. Reddi, Stich, and A. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[25] S. P. Karimireddy, L. He, and M. Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In International Conference on Learning Representations, 2022.
[26] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference Learning Representations, 2015.
[27] S. Kornblith, M. Norouzi, H. Lee, and G. Hinton. Similarity of neural network representations revisited. In International Conference on Machine Learning, pages 3519-3529, PMLR, 2019.
[28] A. Krizhevsky, G. Hinton, al. Learning multiple layers of features from tiny images. 2009.
[29] M. Ledoux and M. Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer Science & Business Media, 2013.
[30] D. Li and J. Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv preprint arXiv: 1910,0391 2019.
[31] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization heterogeneous networks. Proceedings of Muchine Learning and Systems, 2:429-450, 2020.
[32] Y. Li, H. Zhang, and Q. Lin. Kernel interpolation generalizes poorly. Biometrika, 2023.
[33] Y. Li, H. Zhang, and Q. Lin. On the saturation effect of kernel ridge regression. In International Conference on Learning Representations, 2023.
[34] J. Lin and V. Cevher. Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms. Journal of Machine Learning Research, 21(147):1-63, 2020.
[35] Lin and L., Rosasco. Optimal rates for learning with Nyström stochastic gradient methods. arXiv preprint 1rXt::1710.07997, 2017. 2017.
[36] J. Lin and L. Rosasco. Optimal rates for multi-pass stochastic gradient methods. The Journal of Machine Learning Research. 18(1):337533421, 2017.
[37] J. Lin, A. Rudi, L. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least- squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48(3): 868-890, 2020.
[38] S. Lin, X. Guo, and D.-X. Zhou. Distributed learning with regularized least squares. The Journal of Machine Learning Research, 18(1):3202-322 3232, 2017.
[39] S.-B. Lin, X. Chang, and X. Sun. Kernel interpolation of high dimensional scattered data. arXiv preprint arXiv:2009.013 544, 2020.
[40] S.BB. Lin, D. Wang, and D.-X. Zhou. Distributed kernel ridge regression with communications. Journal of Machine Learning Research, 21(93):1-38, 2020.
[41] T. Lin, L. Kong, S. U. Stich, and M. Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances in Neural Information Processing Systems, 33:2351-2363, 2020.
[42] Y. Lin, J. Shen, Wang, and M. Pantic. Fp-age: Leveraging face parsing attention for facial age estimation in the wild. arXiv, 2021.
12

---

[43] Y. Liu, J. Liu, and S. Wang. Effective distributed learning with random features: Improved bounds and algorithms. In International Conference on Learning Representations, 2020.
[44] D. Makhija, X. Han, N. Ho, and Ghosh. Architecture agnostic federated learning for neural networks. In International Conference on Machine Leurning, pages 14860-14870, PMLR, 2022.
[45] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communication-effiiieni learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[46] S. Mendelson. Geometric parameters of kernel machines. In International Conference on Computational Learning Theory, pages 29-43 Springer, 2002.
[47] C. Bendder-Düiner, W. Guo, S. Bates, and M. Jordan. Test-time collective prediction. Advances in Neural Information Processing Systems, 34: 17719-133331, 2021.
[48] S. Park, K. Hong, and G. Hwang. Towards understanding ensemble distillation in federated learning. In International Conference on Machine Learning, pages 27132-27187. PMLR, 2023.
[49] V. I. Paulsen and M. Raghupathi. An introduction to the theory of reproducing kernel Hilbert spaces, volume 152. Cambridge University Press, 2016.
[50] G. Raskutti, M. J. Wainwright, and B. Yu. Early stopping and -orrameettiicc regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1): 335-366, 2014.
[51] D. Rothchild. A. Panda, E. Ullah, N. Iykin, I. Stoica, V. Braverman, J. Gonzalez, and R. Arora. FetchSGD: Communication-effin ference on Machine Learning, pages 1253-8265 PMIR, 2020.
federated learning with sketching. International Con-
[52] R. Rothe, R. Timofte, and L. V. Gool. Deep expectation of real and apparent age from a single image without facial landmarks. International Journal of Computer Vision, 126(2-4):144-157 2018.
[53] A. Rudi, R. Camoriano, and L. Rosasco. Less is more: Nyström computational regularization. Advances in Neural Information Processing Systems, 28, 2015.
[54] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages
2018
[55] R. Schaback and H. Wendland. Kernel techniques: from machine learning to meshless methods. Acta Numerica, 15:543-639, 2006.
[56] B. Sen. A gentle introduction empirical process theory and applications. Lecture Notes, Columbia University, 11:28-29, 2018.
[57] I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
[58] L. Su, J. Xu, and Yang. non-parametric view of fedavg and fedprox: Beyond stationary points. The Journal of Machine Learning Research, 24(203):1-48, 2023.
[59] C. T Dinh, N. Tran, and J. Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:21394-21405, 2020.
[60] M. Wainwright. High- High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[61] H. Wang, M. Yurochkin, Y. Sun, D. S. Papailiopoulos, and Y. Khazaeni. Federated learning with matched averaging. International Conference on Learning Representations, 2020.
[62] C. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume MIT press Cambridge, MA, 2006.
13

---

[63] A. G. Wilson, Z. Hu. R. Salakhutdinov, and E. P. Xing, Deep kernel learning. In International Conference on Artificial Intelligence and Statistics, pages 370-378. PMLR, 2016.
[64] G. Yang and E. J. Hu, Tensor programs iv: Feature learning in indinite-width neural networks. In International Conference on Machine Learning, pages 11727-11737. PMLR, 2021.
[65] Y. Yao, L. Rosasco, and A. Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26:289-313, 2007.
[66] R. Yin, Y. Liu, L.. Lu, W. Wang, and D. Meng. Divide-and-conquer learning with nyström: Optimal rate and algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 34, pages 6696-6703, 2020.
[67] R. Yin, W. Wang, and D. Meng. Distributed nyström kernel learning with communications, In International Conference on Machine Learning, pages 12019-12028. PMLR, 2021.
[68] H. Zhang, Y. Li, and Q Lin. the optimality misspecified spectral algorithms. arXiv preprint arXiv: 14942, 2023.
[69] Zhang, S. Guo, X. Ma, H. Wang, W. Xu, and F. Wu. Parameterized knowledge transfer for personalized federated learning. Advances in Neural Information Processing Systems, 34: 10092-10104, 2021.
[70] Y. Zhang, J. Duchi, and M. Wainwright. Divide and conquer kernel ridge regression: distributed algorithm with minimax optimal rates. The Journal of Machine Learning Research, 16(1):3299-33)) -3409, 2015.
[71] Z. Zhang, Song, and H. Qi. Age progression/regrssion by conditional adversarial autoen- coder. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5810-5818, 2017.
[72] Z. Zhu, J. Hong. and J. Zhou. Data-free knowledge distillation for heterogeneous federated learning. In International conference machine learning, pages 22878-12889 PMLR, 2021.
14

---

Table 3: List of some notations
Notation
Meaning
A
minimum of and maximum of a and b d-dimensional Euclidean space the input space contained in IR
V
Rd
X
(())
the collection of all continuous functions from X' into R the data generating distribution on X' the marginal distribution of Px.y on A' and R. respectively the conditional distribution on w.r.t. Xy X and Px.y
Px.y
Px. Py
Pulx ( (X)
Dx
the public input distribution on X' given Mercer kernel x(,,x)
k
kx
(supxex kxx, x)2
K
L2
the L space on X' w.r.t. measure y
Hr
reproducing kernel Hilbert space associated to kernel &
Tk.
the covariance operator on HI; w.r.t. measure v. Tk. h + Sx h(x) du(xx)
by
natural embedding from Hlg into L?
SD
sampling operator from HIg into R"
Sp + [h(x*), ),... [x")]] where D = ((x', 1')
Sz
sampling operator from HI, R"
Sz + [h(z²), ... ]]] where Z (2))
Tex
Sx
E(h)
the population risk of h, {h) = (.(x))))pe - h(())²
(h)
the empirical risk of h over D {(x', y') } (h) S1 y
fo
target function from X' into TR defined as 1ö (mo) = Ey-ppin [5]. Xp E X
learning rate, (0, 1/x²)
m
the number of parties
D,
private local data of the ith party, {x} v!) :j =, ... (i.......... m)
X,
inputs of D,, {x]
: = 1,... ni 1,).,
Yi
labels of D;. [yt
V. " (i
,))
D
D - D;
Z
unlabeled public data, .z,..... "0
M,y
the parameters related to the regularity of noise (Assumption 3.1 eigenvalues and eigenvectors of Tr.p. such that A1 2 X2 ...
((s, 1.
from Mercer's representation (5)
8, Ca.ca Ca
the parameters related to the eigenvalue decay of Tr (Assumption
C
C1/11-8 TT(T + A where is probability measure No,(A)
(X)
N(X)
R
the parameters related to the regularity of fö (Assumption 3.3
B
the uniform bound of the Radon-Nikodym derivative des
dos
E
the number of local iterations at each communication round in DCL-KR (Algorithm) D total communication round in DCL-KR (Algorithm)
T
A
Details Section
Before we start the proof of Theorem we present basic notions.
A.1 Basic Notions
In Subsection 3.1 the reproducing kernel Hilbert space HI, is a subset of C(X²), i.e., all elements in
HA are continuous [57] Since
= =I M(x)k(;; dpx(x),
(()) = (1 h. = -hv, lp R.) 1.) =
1x
15

---

we have Tr.px = - 'px The compactness of 55 gives the fact that Te is compact, self-adjoint, and positive. Furthermore, Mercer's theorem 62 gives Mereer representation
A(x' x2)
(5)
The fact that Hi& C (()) and Tk,px 1pxx lpx implies the injectivity of TR.px and ), o 0 for all i N. We define
N₂(A) == un(TR,n + AT)
for any probability measure For convenience, (\) == Na (A). From 15 we have M(A) <
C²A=* where C² == C s) and (A) - x²² Given dataset D ((x), y')) similar argument as above gives
cnl + 1 Σ ciks'
ST c [c,,
i=1
and TR,x h + 1 E== ((x*) 1xo.
Note that Assumption 3.1 implies that
E(G) = 2 10 S 2² <<<0 00.
We have
(xx)))>xx. |// - 1(x)12 (xmxxll(xx - [x)()) B -xx.))~e.. 16
and so the excess risk becomes
E(h) E(( Exx [1(x) (o [x)) =1l 1o 10)
Therefore, || (h fō) lنا indicates the generalization ability of h.
Table 3 presents meaning of some notations.
A.2 Proof of Theorem 34
Without loss of generality, we assume n Tip 2 x2e.
A.2.1 Recurrence Relation of DCL-KR
Consider a subspace W of HI, spanned by (lizt,.. ... k2o0) We first show that for a fixed h² E THg and a gradient update Gu u - n (Szu - Szhh") ) we have G'u, - Pzh as t + oc for any #1 E W where Pz is an orthogonal projection onto the subspace W. Set ue+1 = Gu, for t 2 1. Then
M1+1 -1 (1 S2h (1 S2)
(1- S
k=
Since Szh* = S2 Pzh", we have
S1-n ns Szh Σ - ( = Pzh" - (I - n Sz) Pzh"
kmo
Note that there exists (2) ... 200 c Z such that (kiz,
Kano is basis of W. Define a matrix
bu
biag
B
bno
buooo_
such that l:z: = Eje biykws. Then K2Ø = BK 22 where
k(22 (1')
k(x² 200)
K 223
:
E B no
k(x00,2 xt)
k(z"0, )
16

---

and
ko(z | ,²')
k(ž², x50)
K22
kk(
2²)
k 2200
Set Pzh = Ei= Ao
askaz,
Then we can see that
Ag
Ag
no
(1- (1-1182 8x)
>
ayka;
ar
7
ag (6), kiz.
r=1
7 [B T BK 2K2 he.
Σ [ 77 B BK22) a). her
ar
where Hr is the rth component of the given vector and a = lal.-.. anol IT. Note that Kzz is invertible since v K22v= = 0 implies v = O. We can also see that Kzz = BK BK22B' B
where
M(z', x2)²,²²) ".
M(z' 2"0)
Kzz=
Rooxno
k(z"0,z))
k(z"0 22
So
|K// BK
= |B || s BB222B
Snna.
22
Thus, 0 < 2 BB B
BK2/ 1/2 < and
22
8g
(1- n5 Sz) P2h = Σ
K/1/2
K22
1--"k22 22 BK 1//3a
K22a]
kz. +0
as l + co. Similarly, we get (1 n nS552)))))))) Sz)'u1 + 0 as 1 - x. Therefore, we attain G'un - Pzh as + oo for any U1 E W.
From this fact, DCL-KR has the recurrence relation
R-11 The ft- + Th Th.,,
T2 ft = Pz
(6)
n
where Se = Sit for any = 1,... ... m and TR,x; := I - n/Tx,x; for = 1,,.. m. Then we obtain closed form
ft =
Pv.
T n
k
fo +
Σ
m Px
T x.X,
Pz
m
Tx,, Sb,y..
72
1=
i=1
We first compute
1-1
E-1
fö
Pz
mi T x,x1
56 +
Σ
Pz
Thi
T xixi
Pz
n
TE Tu.x
i=1
1=0
x=1
i=1
s=0
From
B-1
T x. Tu.x, = Σ
(I - )
= TT,,, -1-
0
we have
fō
Pz
m
T h:x:
fö +
Pz
m
TTE.
k,X;
Pz
m
14
T
n
n
n
1=0
1=1
1=1
==0
t-1
= fo
Pz
ni T E
Hix;
Sō +
Pz
Th T
K,X;
Pz 1
7.
x.X;
n
n
n2
J-u
1-11
1+
ni
TTTx k.x;
+...+
Pz T Tex;
N.X;
(I Pz)S
= - (C) + I
Σ
n4
P
k.X:;
Pz
Σ
ni 7 h.x; - -1) (1 (1-P))
n
n
17

---

where the last equality follows from Pz(I P2) = 0. Thus, we obtain the equality
Lxx (ft
lpx
Pz
T
R.X:
(fo
-
f6)
n
1-1
i
R-1
+ Lix
Pz
ni
k.X;
Pz
n4
"1
Σ
Txx, Sp (y. SD, -1p P2)56
n
n
1=0
==0
+ tpx
The
P
x.
Px
I
m
Ri T B x,
(I 1-P2s5o.
1=1
A.2.2 Norm Bound of First Term in
We first bound the norm of the first term in 7 as
1px
Pz
T4 T
k.X,
(So f6)
1=1
1/xx
<
1/2 kipx
(Tx,x + 27) 1121 (Tax + 21/1/2
Pz
T
K.X:
PzJó
n1
H4.
+ kipx (Tx.x A1)
(Te.X + A7)
Pz
m
T
K.X:
11T
P2) f1.
(8)
n2
where x > 0. The first term in 8 is bounded as
|T12 (Tx.x + X1) 2/2
(Ta.x + A1/1/2
Pz
Σ 1-1
ns Th K,X,
P2fó
$ 1//2 (Tx,x 21)-1/11
(Ix,x + 21)2/2
P2
11 T kixi
P2(TE,X + 1/)
n
||(caxx + -rr (1-11/11/)) kipx 90 114""
Note that
[Txx +
Pz
n T.T R.X:
i=1
1/2r
< (Trx +1)x+1
Pz
n4 Tr. x. Pz
nt
by Lemma
A.8 Set A; =T =TE,,
+> Tr,x,
1(1 A/P1) 7)
We observe that
///rr| 2r
(Tr.x + 21/2/2
Pz >
Th TiTE
E.X, Pz
mml
m Pz
1/2r
n0 Pz
1/2r
T k.
Pz
PZ + +1))2
E
K.X,
Pz
[=]
1/2r
m
1/2r
Σ
P2A1Pz
1
P2A.P2
Σ
PzA.Pz
+
n
where the equality follows from 0 < A ST + A 2 A; and I 2 Pz. Since sup 20/(11-
x)) = + ( we attain the inequality
1/2r 2r
< 1/ t 1/4 +2)
(Tx. + 21)
Pz
Σ
T4i
TR,, Pz
(9)
n
t+r (ttr)
18

---

Next, Lemma A.8 gives
(Tux [Txx (111011-11// 1/2 (Ta.x + A1) 1/2) (Tr.x +1)
(Txx + X1) 21)11
and
1 (Tx, + A1)-1/21 $ (Th + (2)) + A1 1/2- $ [[Thii + A1)(2,x + A1)
By Lemma A.I0
((
2x² 1d
(AA nd
2
[[ + AT)(T + 2
+
log (2/0)
(10)
holds with confidence at least 1 8 where 8 E (0, 1). Combining //r S yield
(9) and 10)
and applying
S
1+
and
T1/2 (Te,x 27) 1/1
(Th,x AT)
m Pz
B K,X,
Pz
H4
1/r
2x²
(x nd
log (2g() ))
+2
1196
2+2
+
t+r n (++
nd
1
+ )
2n²
I R
22+
+
(log(4/0))
2nt
nd
nd
with confidence at least 1 - Ō where 8 E (0, Therefore, putting X = n1 अर. yields
E
T 1/2 k.px (Txxx + A1) 21) (1L, (1 +
Pz
T TR.x
Pa
n2
+ n 3r
R (1 +1)++))))) 1) (2+ (2+2(2r* 2(2x² + 2x 2 /C))2)
2nt
2 n ェーサ
Here, we apply the fact that EAA fo PPA 2 () dl for A 2 0.
We next turn to bound the second term in g Note that
(Th.x + 122
Pz
K.X.
n
1/2
m
m Pz
T K. Pz
(Te,x + AI)
T h.X:
m
1-1
m
1-1
K,X;
Pz
ny T k, Pz
PT A1)Pz
Pz
B TT. x,
Pz
1/2
m
P4
T k.
P2
Pz
Px + A1)Pz
Pz
n
T
k.
P2
Set A; = T
T..,
Using a similar argument as before gives
1-1 1/1 1/2
ni T
x
Pz
PZ + +1)Pz
Pz
n4 T
x,
Pz
i=1 n
i=1
1/2
(
1/2
1/2t 1) +12
<
+1
1t
19

---

Since Z and X are independent, we have
E
kipx (Th,x
112-
(Tx,x + 11)
P2
TiT TTix x.X:
114 P2)52 lI..
n
1/2 +*)
-
T2//2 hiss (Te.x + +11)
RBI(TT
P2)fölla.
1/8
We already see that
1/2
TM/2 (Tx,x Ar)-1/2 5 2+2
2xx²
log(2/6)
nd
nd
1/2
2n²
(A)
2 2
nd +
log(4/6)
nd
holds with confidence at least 1 8 where 8 E (0, 1) and so
12 k,px E
(Te,
1/2 + 1/2
1/2 < 4 2 + 2(2x² + 2x 2 ( 1/2
by putting À n शा1क as before.
The remaining part is to bound -I l1r Applying Lemma A. yields I| P2)ff S
I A 1/2Tx - 1/2 kxp= 111 11 11 where Ao 0. Then Lemma A.8 gives
A [[Tx,, Aal) -1/2772/270--00 2/2/// 1/2 111 lIE.
(r- RX 1/2 [Tx.2 + 201) - + Ao1) 1o 1/2) 1/2
k,0
RX 1/2 1(Tk, >01) 1/2711/1 112-11
From dox
< B, obtain
dpx
[T (Tr.2 + Aol) 11/11 = (Tx.2 -oo)
$ <B </1,2 (Tk,2 + Ao1)-1/311 1///// (Te, + Aol) \o2)-1/31.
Set Ao = 128(n²2 1)2g n0)33/ /no where we assume n sufficiently large such that Ao S 1 and
No. (Ao) 2 1 for no 2 n T n)o By Lemma A.8 and Lemma A.12
|T (Tr.z + 2o1)-11 S (T + Aol) 1/2 (Tx.z + AoI) 1/1 22
holds with confidence least 1 8 where 8 (eexp(11/4(6 B)),), 1) and
B. 1 Nox
1 + (ox
+
Agzia
Aani
Since
- Pz).f < 11,
11T 1/2
96 11, S TR. 1/2 ll., R
we have
BI Px) S RR2-112 12/////1111/1 11////2--111/////// R 2-11 4exp
4(n²² + 1)Bo
From no 2 nZe, we get
log 2e + log ni
log e + log nig
Bo S 128(x² + (log no
+
128( + 1)o n
2 no < 128(x² + 1)a (log no) 1
2 log no 128( + (log no
+
< 4(x² + 1) log no
20

---

and so Rx 1 .eepp ( { S 4R 1, Therefore,
m T k,X, || |1[ |144- P2) 11..
E
12/2 kipx
(T,,x 111 (2h,x 21)
Px
Σ 1=1
1
+
))tt)))))))
1/2
4 (2+ 2(2n2 + 2x 2 (2)))
1/2
RAo
1/2 //22222222--- 1/2 4 4Rk 20-1
4Rx
17
1/2
$ Br-1/2 1/2
+
where the last inequality comes from no 2 n (log n)
A.2.3
Norm Bound of Second Term in
Set
EE- Sb,)
0
Em- (T nSp
P
E SS ST. )
Note that
171
E-1
PDS 1
11
SSD:
D:
Σ
nSD Sb.'
1=1
==0
m
n4 T K,X, m
(T (I - nT SD ))
(11)
n
Then the second term in becomes
R-1
Pz
Mi
=
k,X;
n 7
kx
ST. -Sp,f,
Pz 1P2SIPSD) Ply
1px
1=
We can see that
Σ PP2-nP2SBPS)
- SSSo))
Lix
1=0
17x
1////2 (Tr.x + 21) 1/211
[Tr.x + A1) 1/2
Pz - -1P2PPPPPP)) nPpSIP(y- Spf6)
E4
< / (Tx,x + X1)-112111
Pz - - nP2SIP(y So (1,33 Σ
1=
H4
1/2
Σ
P22 (P2-1P2SPPSD) "P2SDP(y SDf6)
We first bound the expectation of the first term in the above. By the Schhhr-S inequality, we have
E
|T h.pw (Th.x + 1/22
1/2
Pz -2SDPSD) nP2SDP(y
- Spfo)
1=0
1/2
< <EEITH// (Tx,x + 112-1/2122 1/2
12/2
1-1
Pz nPPSBPSD) nP2SDPly SDf6)
j=n
21

---

Observe that
Pz P2-0P2SDPSD) -
KiX
1=0
1-1
SD
Σ
Pz (Px-1P3SPPSh) n - -
==0
2
and
[-1
SD
Σ ==0
Pz - 1P25 nP25hPly- SDfo)
= p p- (1 (1 SDff)
= (T - (1 - Py Sofo).
Using Ely (y -p(ii) < , have
(1 - (I 1/Spp> P) (y Snfo) 1x 2
Lr (II (I-(( (I -1-11//SSPP (0x Sy (D.o) (I- ( (-NSpP=SSbb)))
-
L (T - (T nS P))
-
2 ||(TT (1 -1-
SD Pz (p-pp!/
p1/20))) us
H8
where the last inequality follows from the fact that |AB|IHS S ||||ms|| and
|| S
F-
|1" 1/2 S 1a-
SE
Since
5 n/pl////p/ SD Pz SD P1/2 pl/2 S s spSpls SI
(12)
which follows from 11I we can see that
0 <
p1/2) s 0 < A, (I Sp Pp p1/2)) s Al (I -I- (USS S
1 pp
Sp
where 2.)-) is the ith largest cigenvalue given operator. Therefore.
>² (I - (1
FF || (1 Sp p1/22/111111
Sp Sp
I HS
HS
Using 12 and A 2² < a for u 2 lead to
A1 (I n SpST -MM
(1- (1- SA(PP
$ (
where Åσ 2 ... 2 dn are eigenvalues of SDSJ, the first inequality comes from the Bernoulli inequality, and the last inequality follows from the fact that [| < E. We define
R(c)
Σ (M))).
Then
2B (1 (1 ppS/ p2 /2/2)( / < SnmE R
1
2
V1tLE
Similarly in Appendix A.2.2 putting X )= サーー gives
2/2 (Ti.x A1) 1/2 52 (2 2x 0
/Z)
22

---

Therefore, the Cauchy-Schwand inequality gives a bound as
B | (Ti,x + X1) 11)
1/21
Tx
Σ
Pz - -nppspppp))
mP2ShPly Snft)
ER
VrttEE
We now bound the expectation of
1T R.p. (Ta,x + 1/1-1/21
Σ
Pz (Po- nP2SIPLy Solo)
1=0
By the Cauchy- Serch--Schwartz inequality and the same argument as before, we have
E X / kipx (Ta,x 1/211
Σ
P2z (P2- -p2SSS0))))))
"P2STP(y Spfa)
1/2
S (2 (23) 2x 1
A
Σ
Pz 1フ--1 PPPShPPPPP) nP2Shply - Sof6)
Also, the same argument before yields
E
Σ Pz nP2SDPSPPs) nPPSDPly - Spfo)
E [yy Spfo) T A(y- - SSn
H1
Blu(AA]]
where
= PPSPP
Pz nPPSSPSPPP)
NPZSIP
P2
PPS.PP
To bound [)], note that
tr(A) s E tr
npllspp2
Σ
1 (I-MPSSPPSOP2)) SP2SIP'/
1pt//8pp2STT 11/2
Σ -1- / (U--niPSSoP2SSPlly
Let B = rppp// SIST p1/2 PISPP// Then 0 s B < and
1E lr
pp 1/2
Σ [I -
So Sp Sp
1-1
nE
Σ
(1- (LBB)
nE Σ
A,B)) (1 (1- (1 (1)))
1=1
1=0
1=1
E -
(PAi(B)) S 5E Σ (A
X:
1=1
where the first inequality follows from 1- x² <AA - x) and the second inequality follows from 1/x A Pr SIA 12x for all / and j0, 1]. From the fact that
X(BB "1 (ED(TT) nEXi
23

---

we have
E (A(x)(()) S nE
Σ
t A =
VttLE
i=1
Therefore, we obtain
B A 1/2 1 k.p (Ta. 11)
Pz - P2-nP2ShPSD) PP SDfO) Σ
1/2
$ V2 (2 (2) + 2x/ (()
ER
In conclusion, we have an upper bound of the norm of the second term in
7 as
E
Pz P2-nP2ShPSD) nP SDfō)
jm0
1.2
1/2
V (T3))23)222221 2N 2n
ER
VntLE
1/2
+ V (2 + (1)) + 2x (3)
ER
VTJLE
1/ #
ER
VinLE
2
by taking À = n 2 We will bound ER
in Appendix A.2.5
VittE
A.2.4 Norm Bound of Third and Last Term in Note that
m
)
1-2
m
Lxx
I I+..+
PTT
K,
Pz
1
n4
T x;
(I
Pz)5o
Y
1=1
17
1|T//2 (Tr.x + 112-11111
)
1-2
1/2
(Tx,x + 11)
I+..+ Σ
Th TTTEE k,X:
Pz
1
Σ
n2
T k,X;
n
i=
m nl To kiX;
1/2
1
(1 - P2)
where 0 < A 1. From 11 and 0 < P < E1, we have 0 S 1 Em TTT
nSSPSD s
k.X,
n
SE nEETx.x. Using this fact, we find that
1/2
(Tx,x + 12)
1+...+
Th P2TxXX R.X;
Pz
1
7i T
n K:X;
n
m Σ
< 12 1/2
14..+
PrThix kix;
P2T
i=l
1-2
+1112
1+-.++
Σ
n;
P
P
E.X;
n
i=
24

---

To bound this, we first observe that
m
K,X
14..
+
Σ
Py
K,X,
P R.X
m
1
1x Pz
P K
P2
n2
3/2
3/2
S - (1+
P2TExxPP
P2Tx,x22
Σ P2TE, Pz
ni
where the last inequality follows by a similar calculation as before. On the other hand, we have
P2TR.x R.X,
n
Σ
T1e Σ
P2 Pz
PETH!
71
P2Te
P2InxP2
P2 x, P2
1 vT
1+
1-2
n
n2
22j
by the same argument. Using a simple calculation, we get
1 1+
S EE
(2 + E)
and
Σ
22 1)
(TE))// VoLE.
2m
Note that the norm of the third term in 7 is bounded as
P2)56 || (I - P2)ff < | (Tr.x + - + -1)))
Therefore, the norm of the sum of the third and last terms in 7 is bounded by
(1 + 2E' + Eloot + (BtLAE | (Tk.x + A1) 1/2
(Tx,x + X1) (2))o
To bound [1(Tr,x + //) Pz)Sō Ia observe that
[[ + P2) ll,, $ [1(Tx.x + 21) + -111-//11l + (1) P2)56 Ila
and
[[(T..z + (I- 11 Pa)56112 + +A[[(T P2).6 lh.
BBllaa P2)56 1l,.2 +XI((I f2)
-BI(Tk, + 121 P2)5f
Under Assumption 3.3 we have
B1/2 1//21 (Th.i + +1) 12 fol.
< [B + A1) -1 +
2/2
+ xI)
11/21/2) 1/2 11111116
ksp0
Since
[[(Th.p + 12- < (T + XT) 11/2 2
I|T Ripz (Tr. + AT) -1/2
k,px
k.pz
which follows from Lemma A.8 and
//2/// (Ik, + 112 1 (Trr,
+ 11111/111 - /1/2111422 (1 + 111-11211
< B /2/21
k.ps (Te,ix + A1) -1/21 < B1/
25

---

we have pl --)
kip= S Br2 On the other hand,
11(Tk + (17)(( (2) + 1/21
< [(T.,p + +1 P2) P2) 23 (2)))-((Taa (Tr.2 + 1/2-1
$ (TT,i + (1
by Lemma A.8
Therefore,
Th/2 (TE.X + Xn) -1/2 1/111/// (/T/x + (1 P2)
- RB" (Ihi + +21) 11) 112-1/1
||(T,, + A1) (Tx,oo + 11) 1/2 112111/111[(11 1/1 + -1 Px)l
Since X and Z are independent, we have
E 1 (Th,x 11) |1 [2 + (1) P2)16 -
< RB'E (Trip +
|((T.x 21) + 211-1/111
& + (1-211=
P2)l
By Lemma A.8 and Lemmal A.10
((22² nd
2x²
Ak2A((A)
4x2
1/2
[(TR..p + A1) (Tr,x + 1/2-1/211
2+2
log(2/6)
nd
holds with confidence least
where 8 (0, 1). Also, by Lemma A.8 and Lemma A.11
1/2
2n²
(AA)
[[(T,,x + +1) + A1) 1 s 1+
log(2/8)
nd
nd
holds with confidence at least 1 where E (0, 1). Thus,
[[TR.x + +A1) + AT) 1//11//1 + AT) 1/2 (Tn.ex + +XI)
2x²
4ARA((A)
1/2
2n²
+ ('meN(c)) ))
1/2
2
1+
+
(log(4/8))37
nd
nd
nd
nd
with confidence at least 1- 5 where 8 (0,1). Set À 128(x² + +1?n शाकन where n sufficiently large such that À I 1 and 2 2 Then
E (Te + XT) (Tk,x (T,,x + 112
|(Tx,, 12)
(Tk + A1) 1/21]
< (2.5) (2 + 2(2x² 2x /x (1 + 2n² + 2x C2)/2/2
We now bound (T + \1) 1/2( P²) By Lemma A.9 we have
[[ + 11) - 12) & &X + 1/2.2 + A1) 1/312
By Lemma A.12
[[Tk, + A2) + 1/21 & 22 with confidence at least
4exp(-1/4(m
1)))) where
1 + log (A)
1 + No (A)
Bo
+
Ano
Xnp
Also, [I(Tr,p, + +1) -P)1 S (k² + 1)1122 almost surely. Thus,
(- 4(k²2 (-4(k²2 1)Bo
El[(Te + X1) 1/2 -2))1 <2'x + (x²2 + 1)" 4exp
Note that
log e log(1//))
1(x² + +1) log log 2e log Anto
Bo <
+
Anio
26

---

and so (x2 + 11" 4xp (( I 1(K² +1) 1. Therefore.
AT + A1) Px)l 22" (n² + +1)² Iu + 4(k² + 1)" .1 x
We can conclude that
- lpx (I -2)) + lpx 1 1+...+
1h P2T K.X. n
Pz Σ
T x,X, (1- P2)
Px
S (1 + 2E Elogt t + /6ttE) (2.5) (2 2(2n² 2xy (2) 22)
2x² + 22x/ /2)
(2'128" (n² + 1) nn ボデ 4(K² 2 1)" .n
2 B" (1 log L L 1/2 2 2-1
1/2
A.2.5 Stopping Rule and Rademacher Complexity Bound
For convenience, we abuse the notation D {(x², 22 ),, ... (x" ,""" and X (xt,... ,x",
Define the local empirical Rademacher complexity
Qn(c) =
sup Isllay Sh.1l 63
Σ wig((') X
and the local population Rademacher complexity
(c) =
sup
Σ
lolls, 11.191
where " Wn, are independent Rademacher random variables and px, Di= Ext. We also define
1 Ti
R(C)=
=
Σ
A
A
where A A2 2 2 0 are eigenvalues of Tk.p.. We recall the following well-known property.
Lemma A.1 (166. 660). We have
Q.(c) 5 R(c)
for 0.
We can prove the following lemma using similar argument as [46]
Lemma A.2. There is an absolute constant >> 0 which satisfies that for every e >> 0,
RR(e) s Qn(c).
Proof of Lemma A.2 We divide the proof into three parts.
Part Since Te.x STSD. Å ' 2 ... 2 Ån 2 0 are eigenvalues of TE.x. For convenience,
set \ = 0 for > n and define S n such that Ån > 0 and da+1 = Choose an orthonormal basis
( of HI, such that di; is an eigenvector of Tk.x corresponding to ÅŞ. Then (6e, {3) 1.2.... SSD (Tx.x S.)a, = -(i=s) S.. We will show that
hxx E (x)))
where E fxl....
xx). Let W, be the subspace of Hi, spanned by { i 1.... .)) and W2 be the subspace of H2, spanned by (kx i 1, n).. Observe that W,L ker Tr.x and Wy C Tx. by the reproducing property. Thus, W1 W2. Conversely, choose a basis (kg: i 1.... n?} C {lxe i 1,... n) of Ws. Then, using similar argument as in Appendix A.... A.2.II that there exists matrix
bu biar
B
:. :
bal ... ban'
27

---

such that Rxz- E== bigkes. Then K xx = BK xxxx where
xx
1(x'' xx)
k(x², xx²)
K Kxx= =
E IR =R"
((xx,xx)
k(x", (("),)")
and
k(** xx)
k(x), (x%)
Kxx*
E IR Xm
k(x" x+
"(x²" ,x1)
Since xx,* and BT B are invertible,
n² Σ b,
Te.x
Σ
I 2 B) bbj.iis
for any b b [b,, bar]] E Rea where |-]r is the rth component of the given vector. Therefore, W2 C ran Tx,x = (ker xx,x))+ = W1 and so Wi = W2- From this fact, we can see that hxt = Σx=1 ard,, for some a1. .aa E R. Then or = (lxx,, Br)E, = (x') for all r 1,...... n. and we are done. Note that hx Ei= dx((x) where x fxx,---. xx) since (x) 0 for fx' ....... xx) and i > n.
Part 2. Define
80 havi
F: = h: [|Al|,, I 1 and [1llle s
h S 1
and
duh S e²
i=1
and
8
d
==
h S 1
de e
i=1
where 0 = 1. Then & C F since
x Σ
8
8
A A, A
v
Σ
1v
h = Σ
h S1
for h = Eie hape E. Thus,
2 )
E
sup kee
Σ cx(('')
)
x
E hEF
sup
Σ
cx((('))
x
1=1
where fi,".., en are i.i.d. Rademacher variables. By the reproducing property,
Σ ch(x') (lc. Σ akka)a (11,
Σ
(x))a)
1=1
Si A2 n )
E (x')
Σ 1=1
Σ E (x') (x
Ae 2
where h = Eie he Thus,
R A 2 n
Σ eah('')
Ex 105s
sup REe
Since
A
2
n
(b))
8
R, A2 A
Σ 1=1
n
G (x0))
Ex
1=1
28

---

we have
2
X A 2
Σ (ans((t) ) x
E sup
cx((x')
x = E
X A
Σ (x())
Σ iU ne?
A
i=1
Therefore,
13
1/2
Σ AARSE
sup NER
ch((x))
X
Part 3. By Khintchine's 's inequality,
1/2
B3
sup RET
Σ cx)(x') )
sup E heT
Σ cx((')
X 2 v2
sup NET
Σ n(x
V
Set = g( ... 6n) where
9(1,
.b.) = sup hET
4k(x*)
By Remark A.14 9 is convex and supREr Ei (xx1)2)11/2 Lemma A.13 we have
Vnc-Lipschitz on [-1,
By
ts 2 [Z[ S exp (- 16 [
t
Pz E|Z
S
exp
32
From
E
[[2
E [z [(<
+ Σ E 2 (10--132Z11S3<<0-233111111
m==
8
$ [[Z|X]+
Σ
(m 1)B[2| (m 2
m=0
m²
1+ Σ
(m + 2)² exp
32
m=0
we have
1/2
A
n
112
where c = (1+ +>>>mmmm
(m + 2)2 exp
m
is an absolute constant. Therefore,
32
n
A
<
B
sup REF
Σ
ch(('))
x
1=1
mml
We set the population radius as
c 2+
en inf c 12 Q,(cc) <
16x
We also define
i. = inf { < 0: R(() -
c 1+2r
16
By Lemma we have 6n S En We can easily see that R. R, Qn. and Q,, are increasing functions. The following lemma can be shown by similar argument in 22.
29

---

Lemma A.3. g [0, o0) - [0, oo) is a function such that is non-decreasing and r + g(r)/r is non-increasing, then g is continuous on (0, oo).
Since
R(e)
1 ==1
A 1
R(O)
Σ
and
+ R(e)/e and + R(e)/e are non-increasing and so R and R are continuous.
Lemma A.4. e (n(e)/e and + Qu(t)/e are non-increasing. In particular, Qn is continuous and 6n <0.
Proof. From the fact that
(x(c)
-E
sup lalin اh,1اa 22 px..
wxg((;)
X
1=1
sup lolls S1/c.lll
w.g( xx)
Te
we can easily see that e + Qn (e)//e non-increasing. Similarly, we can show that e + (n)e)//is non-increasing. Note that
Qn(c) c++
Q,(c)
lim
> 0
and
lim <-
> O.
Also, we can observe that
(c(c) 0 and
(c)
lim
lim
0.
<-
Since ++ 2²r /16k increasing, goes 0+, and goes oo as e - oo, we can conclude that En < oC.
Similarly, we have én < oo. In fact, we can find the lower and the upper bound of žn under Assumption 3.2
Lemma A.5. We have
2011u+220, 1/(2tt)) g/(Ar420) /
Adg 1/2
1/20
n Ar S En
8 ++
2 1/(4r+20)
(2)(1r+20) aut..
1-3
Proof. Since c,i-1/s < A 1,i-1/8,
1/8 we have
8
1 20 (C.)-M
We first consider the lower bound of é, We first observe that
(caj (c)--/=)
1 n
Σ
c/j-1/4
8=
[1
Set
8 1/20
20((4442) e/(ar+20) ^ c//2
15422
3+2
Note that
Co -1/s
I- - ((()))] +1)
(6-1)/o
2 and
2
30

---

hold. The first formula is trivial. To show the second formula, we observe that the function (t) = =1-1)" (1+)) is an increasing function. Thus, fort f 2 2/s
( (t) 2 u 2
2
2
(1 - x)* 2
22 2 1.
Here, we apply an elementary inequality: a=b'~s
sa + -
(1-s)6 Va, b 0. Since
Es 02/2
1/2"
[(x) 2 ( - 12
2
(+2
8
putting& / /= = gives
[(9)" (1-s) (1+ + [(%) "I) ) 21
and the second formula holds. Therefore,
20
1/$
++2 12/a dt sC,,
1-8 ((( +1 +1) (0-1)/-
2
|
11/0
2 e
[4))]
+1
holds and so we have
-
[(
2
-//5 1/s
Co
+ +1)+2
22
2/2
1-8
clt2r
1122
26
- (=)
+1
where the last inequality follows from S 29/(14220) k1/(2r+5) e (f(1)220) n कमक that
We can conclude
1/20)
En 2 20((r+22), ( g/(or+2)) g(rtt A 1/2
n -r12
(
by Lemma
A.4
We now derive the upper bound of ēn. Note that
1 n [(()))
Σ
a+ Σ Caj-1/e
(=1(())]
Since
Σ
Caj
[((9))
C. tic
dt s C.
([())] +1)
-1/8
==1 |+
and
|
C, dt = 1-8
sCa,
(1(=)) 5
1-1//
2 1-8 8 (1(=)) +
sC,
-1/-
[())))11 B/
+1
we have
Σ
ni
C.j
1 10
C.
dt = C - 2-20
(2))
f1/
1- s
(++
Hence, we have
C.
2 +
Σ
Caj-1/a
S V n
1
c: +
C²
2-20.
n
1 1-
5=
Set
6 20(
N 1/(2r+s)
(2-5)
1/(4r+20)
C2/(4r+20)
ns -
1-8)
C2 which is equivalent to v / (C
x2
112r
Therefore, we attain the upper bound of on;
I-s
16v2x
En S 244
x 1/(mm)))
(2-8)
1/(4r+2x)
C2/(44220 n Ihn.
1-8)
31

---

Without loss of generality, we assume n is sufficiently large such that
2 2 2 2"x²
1 1-8 C. + ( K /
( 1/(4r422)
Collamizonn ााे S 1.
1 1-8
Then Gn S én 1. We now prove the following lemma. It is extended version of Theorem 14.1 in [60].
Lemma A.6. We have
1111122
P
sup [Mlla,
2 1 exp 221-epp-cnnt
||b|l;
82
for any t [Cn 1] where 01 a constant independent of and n.
Proof of Lemma A.6
We use similar argument as in the proof of Theorem 14.1 in [60]. Define
(t)
sup
11hli
Millig
where t E (0, 1]. Let
||Al px.n
-
e²)
tl+2r
=
sup [Mlleg S1
| t
A = Zm(tt
2
A Zn((t) 2
2
We first show that & c A. On the event E, there exists h E IHlg such that |Ai|EE and
||
- |11l122
Px
1/hl12 2g +
2'
If |1//l 22, S we have | ux.m
||/1112,.
1/2 1111122
2
+ 2 2t2 Otherwise, set h [ x.x
then |1hll1z_ = and |1011 12
117.13...
1 x*
+
2 2 2 Therefore, & C A.
g
Since 2 2 21'2 for E (0, 1]. we have C A C A. To find an upper bound of EZ,, (t), we use the symmetrization argument follows:
E.Z. (t) E
sup [Ablln SLiI
Σ h(x²)² RB(())
PM
E
sup
((x+)²
-
1 > 1(xt))²
X
[ |1,1|A|| 12, S(
1 n
< T
sup
Σ i=1
W/
(n(x')) -
[Allas $1,11R 22_
St
wih (x)))
< 2E
sup ||ble S1,1|1112 22
St
where w Wn are i.i.d. Rademacher variables. By Lemma
A.15
2R.
wxh(xi)2
< 4x (t).
| la sh,1/b L2,
St
For t. 2 6n have 4x (t) < 1+20
since
142r
(4x)
c and (c)
Vc 2 Cn.
(13)
16k
16k
32

---

Since
E (1((2))² [h(x)}}²
E [h(x))*] S x2t?
sup
sup
Ahi S1, 1 St
|klm, $1.1011 22x St
Px
Lemma A.16 gives
1 1 4x² -n.Z, (t)
P (t) EZ.(()+
4
exp
2mx2 + gK2= +
2
24
A Au A
$ exp
-an
[1+2r
where C1
1
Putting u gives
96n
142
P(A) - P (t) > (t)
S exp (-cin (1) A(T)) S expl (xp(-c)ntt").
4
i... P(E)) 2 P ((A) > - exp( exp(-cgnt*h)
Let us return to our problem. Consider the event
|1 px
- -111112z 1
E =
sup || $1
||Al12 + Ez.
2
By Lemma A.6 A.6 we have IP(E)= > exp( cinEE"") where is constant that does not depend on n. Define
T= min {
tEN:
S En
By the definition, we can easily obtain the upper bound of T as T < 1+ nEZ non-decreasing,
Since R(-) is
(VILTT
S RR())) 1
(E.))
VTTT
a
for absolute constant a where the second inequality follows from Lemma
A.2
Note that
[ Px.m |1,1122,
(1N1222 + +
11Al22 Pa...
|1ll2
22
2 fn
for all h such that ||alee I on the event 8 Thus,
Qn (E.) = EE
sup [|alls 22.llell L2x,0
wig(x') )
x SE
sup IIllay 21.11=11 23
wig(x")
X
Sta
Ti
Ti
on the event 8 Set Set
{g: gg: + R: ||l|| $ 1, 11 113 S 2 }.
Then the ranges of functions
in F are contained [-K, k6] and F. By Lemma A.17 we have
E
sup 199l
wxg(x')
S 2F
sup [slla 11.10 2 S
vig(x))
+ +a
lola,
$2in.
with probability at least exp(
nin 1+2r) 2 exp( - Ci cine
Hence,
R
2
Q2,2
C 22+2
V
a
holds with probability at least 1 - 2 exp( -c(ne()) Here, the second inequality follows from 13 Therefore,
ER
ViET
5
KCI
RC1
Q
En
(0V (1 - 2exp(-c;ne,) ))) + x 2exp(-ccnet) 24
KC1
En
22
2x
Ci
since R
< k. From the fact that exp(-anntt) 2+hr
S 1, we have S n 2 expl sapl-c/ni - 2
2rl1
(TETT)
2
1/2
ER
6n S n
11
2++1 4=
VNET
33

---

A.2.6 Conclusion
Note that
7 2 24. and 1
S naite.
Therefore, we bound the expected risk as
1 Blllep (Sr fo)ll23,
2 1/2 (
+ 1 2044
2n
1/2
nt
1-1/2
20te
+
T1/2 + 25 T)
1/2
ER
VNTE E
1/2
B¹ (1 log T// n
2r44 25
1/2
B'n 2ाे log n.
A.3
Corollary of Theorem 3.4
As mentioned in Section 3.3 one can remove 1" in the upper bound in Theorem 3.4 by using more public inputs. The precise statement is as follows:
Corollary A.7. Under Assumption
3.1 3.2 and 3.3 with ny 2 BB+ (log( Bn) public inputs
independently generated from Px satisyying 22)
DCL-KR gives the performance guarantee
E Elppp (Já.T - lo)llzz SC. 2
log
for all j = 1.... m where > O is a fixed constant, E 1/²2)) is a fixed learning rate, ' is an adequate stopping rule, and the prefactor C. does not depend m, and
Proof. In the proof of Theorem 3.4 there two terms in the upper bound affected by B. One is
(log no)
r- 1/2
1/21/2
T10
in the norm bound of the first term in
The other is
[T,, + 2T (0)(T-P,,)))
< 2"X + (n22 + 1) 4 (-x(0++) + 1)Bo
1
in the bound of the third and fourth terms implies
7 For the first part, no 2 Bl+en कमे (log( Bn))s
B" 1r2 ( nloggn))*
r-1/2
ng
3r-3/2
B c(r-1/2))
1-2 20t4
(log(Br)) 3r-3/2
(1++)) B
1
log + 3og log (ng
2r +
r-1/2 <
2rth
For the latter part, set 128(k22
1 /B. Then
log 22 + log(1/A)
log 2e + log(1/2)
1 4(x2 + 1) log(Bn)
Bo
+
<
Anu
Ano
and hence
(Tk, + 12 <x'
(-a(==+ + 1)Bo
1
SB 2rte +
Bn
Since it eliminates 3" in the upper bound, are done.
34

---

A.4
Useful Lemmas
Recall Cordes' inequality [6]
Lemma A.8 (Cordes' Inequality). Let A, B be two bounded positive linear operators on seperable Hilbert space. Then for any [0, 1]
||
|AB||
holds.
We also recall a property of projection operators.
Lemma A.9 (53)) Let Z be bounded linear operator and P be projection operator such that P ZT. Then for any bounded operator X and X we have
(I(T P)XII S (2 + X1) 1/2
There are some useful lemmas for PAC bounds.
Lemma A.10 ((17). Let X (x1, ... xx1 be a dataset where data points are independently generated v. Then
2x²
4R)
[[T + (T) + XI) -1 522
log(2/8)
nd
nd
holds with confidence least 1 8 where 5 (0, 1).
Lemma A.11 ((88). Let {x).- ... xx"} be a dataset where data points are independently generated from v. Then
2n²
(x)
4k
[[TR, + (TEx + AT)I S 1+
+
log(2/6)
nd
nd
holds with confidence at least 1 - 8 where ò E 10.
Lemma A.12 (148)). Let X [xt,... _x") } be dataset where data points independently generated from v. For E (0, such that (A) 2 1,
[1(Tk,u + (T) + 1
holds with confidence at least where
N,
+ log An
exp
<ō<1 11
4(x² + 1)
An
To prove Lemma A.2 in Appendix A.2.5 we introduce a concentration inequality for Lipschitz functions.
Lemma A.13 (160). Let XI.... Xn, be independent random variables whose supports are con-
tained in (a, b] and f R. + IR be convex and L-Lipschitz with respect to the Euclidean norm. Then
we have
P((()) 2 (((X)+1)+ exp
+
412 a)
where X = [X1,,... Xx) and 0.
Precisely, use the following fact in Appendix A.2.5 Remark A.14 (160)) Let A C R be bounded set and
f(x) = sup agXa a k=1
where x = =[XI," "x Xn] E [-11
and a = [a], an). Since
n
f(x) - f(x'x sup Σ
O:X; - sup
a4 I sup (a, - X)R== S sup ||a|| g- x ||R",
a
is a suPacA Ilpssz= function where || ||R- the Fuclidean norm on R can observe
that f is convex since f is supremum of convex functions defined convex compact set.
35

---

To prove Lemma A.6 in Appendix A.2.5
we recall the Ledoux Sedoux-Talagrand contraction inequality
29 56 and Talagrand's 's inequality 56
Lemma A.15 (Ledoux-Talagrand Contraction Inequality). f then
R - R is a L-iipshitz
sup Σ c(((h(xi)) AEF i=1
S L.E E
sup WEF n2
1
Σ i=1
cxn(xs)
Lemma A.16 (Talagrand's Inequality). Let XI,'.. X, independent X X-valued random variables. Let F be countably family of measurable real-valued functions on X such that |l S U < oo and (X.) = for all f F.F Let
Z = sup f(Xi), FEF 1=1
o²
sup
([f(X)))) FEF
Vn 2UEZ + +no².
Then
t²
P(Z 2 EZ - exp
2U U0
for all I 2 0.
Lastly, we recall the following well-known property used in Appendix A.2.5
Lemma A.17 (22). Let F be class of functions with ranges in ia, b] and wi, Wn be i.dd Rademacher variables. Then
X + (b - a) log(1/6)
EE sup
(x')
S inf (E((..)
E
sup Σ wi fx+)) hEF i=1
REF
a
4ma(1 (x)
1=1
holds with probability at least Also,
E
sup heFF
Wt fxx")
X
1 (1+
(b- (--a)lo log(1/0)
/1 1 3)
inf as0
E
sup
Σ
w. fx+))
n
heF
2n 2a
holds with probability at least
1 1 5.
B Details on DCL-NN Algorithm
As we mentioned before, DCL-NN considers the same problem as in Section 3 but local models are 1,... nn
heterogeneous neural networks. That is, there are m parties and D; = ((x, v. the private dataset of the ith party (i 1.... , .)) where D = U D, are i.i.d. whose distribution is Px.y. One remark that the local data distributions parties are not the same in general. To commu- nicate training information, we introduce an unlabeled public input dataset Z {z'.... .2" C X.
The goal of parties is to find a minimizer of the population risk & defined in Section
To extend DCL-KR heterogeneous neural network settings, it is necessary ensure that the assumptions of DCLL-KR are satisfied as much as possible. Specifically, one important assumption in DCL-KR is the equality of kernels across local models. Indeed, public data predictions vary in conflicting directions after the local training procedure, even when using the same local datasets, if the kernels differ.
For further explanation this claim, we consider the simple case of in DCL-KR where E is the number of local iterations. After the consensus prediction is distributed to local parties, the server then receives the updated local prediction on Z:
Jl Kzx, T4
xx 22 ni
7 Kzx,y;
(14)
from the local party. (The notation consistent with Appendix Aj Suppose two parties have exactly the same dataset. If the same kernel is used in these two parties, the updated local predictions
36

---

Algorithm 2 DCL-NN Algorithm
1: Hyperparameters: Dj: local dataset of party (i 1,... .m). 2 !z!,.... ,00))
J: public inputs, E: the number local iterations at each communication round, T: total communication rounds, Ts: epochs of kernel distillation
2: Pretrain: Pretrain local Al models f((-) - g((:) + b, (i (i= ,
3: # Feature Kernel Distillation Procedure
4: For party (i =, m), compute the feature kernel values on public inputs (ky, (z x/22
I J1.J2 S no) via (3) and upload them to the server.
5: The server aggregates the local feature kernel values to the target kernel values (k(2211 2²²)
S ji, J2 < n with (4) and distributes them to all parties.
6: for party i 1, ... m77 do
7:
for lx 0, T2 7 do
8:
for mimi-matee Zo C do
9:
Update parameters of its model f. by maximizing CKA(k; k,)) on Zo defined as (16)
via gradient descent where & is fixed.
10: end for
11: end for
12:
end for
13: # Collaborative Learning Procedure
Initialize the consensus prediction Pp.0
15: for f. = 0, ... T do
16:
for party: = 1, i, m do Update and b; by maximizing MSE (Mean Squared Error) the public inputs Z with consensus prediction y,t via gradient descent with sufficiently many iterations.
17:
18:
e 1, Update w, and b, by maximizing MSE on D; via gradient descent. end for Upload the local prediction y on Z to the server. end for
do
19:
20:
21:
22:
23:
The server aggregates the local predictions to compute the consensus prediction yp,4+1 =
Σ
ni "p and distributes yp1++ to all parties.
-==1-
24:
end for
will be identical. However, if the kernels are different, this will not be the case. For kernels like the Gaussian kernel, which have high correlation between close inputs, the updated local predictions will be strongly influenced by data points close to each input. On the other hand, for kernels like the linear kernel, which have high correlation between distant inputs, the updated local prediction on Z will be influenced more by data points farther from each input. We can observe this fact from the above formula (14). This observation implies that aggregating local learning information becomes very challenging when the kernels differ. In short, using the same kernel ensures that the shift mechanisms of predictions Z at the edges are identical, making it possible for the aggregation through simple weighted averaging to work well. This is key element of the strong thcoretical results of DCL-KR and explains why kernel matching between neural networks is necessary in DCL-NN.
Let fa be a local model of the ith party such that fe(-) w. g.(+) + b, 9: X - R W; E R E N, and b, E IR for i = 1,... m. Since most modern neural network architectures have linear layer the last layer, this setting general enough. As (3), we the feature kernel of f: (i (i=1, 1. m) to be
ky (x x²) = (x'))) (x(),,
x!,x² T E
To bring the setting the DCL-KR scheme, DCL-NN matches kf., kksm via kernel distillation procedure. Obviously, the target kernel in this procedure is key factor in enhancing performance. Theoretically, using the ensemble kernel
n4
k
(15)
i=1
37

---

can be good way to construct a good kernel derived from local feature kernels. The reason is that this ensemble kernel is identical the kernel induced by the (scaled) concatenation of the local feature maps, i.e.,
xxx²xx)==
n2 (x
74 (
n2
n
9
9 (x²) 92
[ 91 (x+)T
92
n Im (x
Im (x2)
In other words, the ensemble kernel has greater expressive power than individual feature kernels, and with sufficient amount of data, it leads better performance. We empirically verify that the performance of this ensemble kernel surpasses that of individual feature kemels in Figure 4
DCL-NN sets this ensemble kernel k the target kernel and local parties match their local feature kernels "..... k,m with the kernel k using the public dataset Z. For this purpose, we introduce Centered Kernel Alignment (CKA) 8 kernel similarity measure. The CKA between two kernels kj and 2 on the public input distribution 7x is given by
HSIC 12)
CKA 12)
HH1IC( k1 HHSIC(22, k2)
where HSIC(.,-) is Hilbert-Schmidt Independence Criterion (HSIC) defined as HSIC kz) Ext x2 [xf x² 16, [xxxxxxx) x²)]
and the centered kernel ky is given by (x x2) = kx x2) Eg (x+ x²)]
Rxtt [k: (x+ x2)
Exi xe~p (xx(x,, x²)),
x², x E X (i 1, However, since we have a finite number of samples, we employ the empirical CKA. The empirical CKA between two kernels kn and l2 on inputs {ct,.... c²) is given by
HSIČ(KI, K2)
CKA(k1, =
(16)
K, K2)
where
ci(ct,ct)
ki(ct,c")
ka(ct,c") ka(c',
K1 =
and K2 =
ki(c",c) c²)
(1 cP)
ke(cP, c!)
k2(c²,c²)
are Gram matrices and HSIC is an estimator of HSIC defined as
HSIC(L, M) (p 1)2 ULHMHH, L, R2xP
where : 4 111 the centering matrix, I, is a p identity matrix, and 1 [1, 1 a p-dimensional one vector. During the kernel distillation procedure, the ith local party maximizes CKA(K,,, k)) on Z where l is fixed target kernel given by (4). In practice, we use batching to perform the kernel distillation to reduce computational costs.
Due to the definition of the empirical CKA. it is necessary to calculate the Gram matrix of over Z. To this end, the ith local party calculates the Gram matrix of ky. over Z and uploads it to the server for = 1.... m. Then the server computes the Gram matrix of by weighted averaging the Gram matrices of local feature kernels k k Since this process only requires communication of feature kernel values, DCL-NN still preserves the privacy local model information.
While (empirical) CKA is good metric for kernel matching, it is invariant to scaling, and therefore the local feature kernels resulting from the kernel distillation may have different scales. This affects the degree to which each local training influences during the DCL-KR KR-like follow-up procedure. To
38

---

illustrate this point, consider the following example: Let the feature kernels of two local models fi and fz be as follows:
k (x,y) ((x) doy),
(x, = (aι(x)) (ax(()))
After distilling on the public data with consensus predictions, these two models become like
h+) - o-)
f2()
(aσ(-)) + +b w wo)(-)- +
ie., two models are the same. Nevertheless, gradient descent update on data point (xo, yo) with learning rate 77 is
Wi (--((w]) (oxo) y0)
for fi and
1
n7( n o(xx) + b--200
for f2. Thus, after the gradient descent step we have
(:(.) = (w 17( (xx)) + b (b-30) y00) (nn)) +
and
f2(-) = r/((" o(xo) + b- v0)) (ar(())) + t (w-ann(w 6(x)) +b-))+b-)))) x(-) +b.
Hence the scale affects the collaborative learning procedure. To address this issue, compute the scale a using the estimator HSIC. Specifically, at the beginning of the collaborative learning phase, we compute ae HSIC(K;, Ki) where K; is the Gram matrix with respect to the feature kernel of the ith party Z (i 1,. ..). Then we the learning rate for the ith party
1/2
max maxisjs Sism O
1J0
1/2
0g
where 7/ is a base learning rate. In practice, computing HSIC over all public inputs is costly and unnecessary. Using only small subset of public inputs is sufficient.
present DCL-NN Algorithm Here are some remarks.
(1) The feature kernel distillation procedure requires only round of two-way communication between the server and the parties.
(2) The collaborative learning procedure follows the same process as in DCL-KR with 01 9m fixed. Note that kernel gradient descent reduces to standard gradient descent since the kernels have finite rank. In this process, if possible, optimization on the public dataset can performed using the closed-form solution of kernel linear regression instead of gradient descent.
(3) In this work, we apply FedMD for the pretraining of DCL-NN in the experiment. However, DCL-NN is a general algorithm that can use any algorithm for pretraining obtain good local feature kernels. For example, kernel learning techniques [63 may be applied for pretraining.
(4) Our algorithm can be naturally extended to regression problems with calti-dimenssonal outputs.
C Details and Further Discussion on Experiments
C.1 Dataset Description
For datasets, we follow Algorithm 3 to construct non-i.i.d. settings. Note that this procedure is similar to the non-i.id. data generation procedure in classification tasks 44 69].
39

---

end for Algorithm 3 Data Generating Procedure
1: Inputs: the number of parties m, the total number of private data nt, the number of public inputs
fig, the partition of input space = {A1.-.. AA. [Ae}
2: Generate the whole private dataset size of n from Px.y and the public inputs size of no from Px-
3: Sample a base private data ratio (a1, am from Dir([10, 10,-.. 10]).
4: while _j=1 Cy # 0 for all i 1, 1,..,,, do
5: for party j = -, m do
6: Sample two elements uniformly from the partition A.
7: end for
8:
Set Cij-
if A; is chosen at the jth party and Ci5 0 otherwise.
9:
end while
for 1, 1,..,, do
11: Put the private data points where inputs are in A; into the datasets of parties with ratio
O Cik
m Σイ= CyCij
k=1...mm
C.1.1 Toy-1D
Let X' 10, IR and pr be the uniform distribution on X. The space
H { fe AC f(0) 0, f(x)) dpx(a) < ca)
the reproducing kernel Hilbert space associated to the kernel k(x,, y) = min(x, 3) where AC 1]
the collection of all absolutely continuous functions on [0, 1] [33 60). As mentioned in [33], the covariance operator Trp,. has eigenpairs {(Ar, ex) where
2i
2i - T.
A;
ex = sin
2
Thus, the eigenvalue decay rate is 1. Set target function
20
2i
f0(x)
sin
2
1=1
1=1
From the fact that
T
k,p=
12-
hee
<
R
I R2
1=1
1=1
we have fö 1/122 90 such that
20
1
2i
11
1/2
R<
66
2
Then 1. We generate data points from Pa Pala such that Pa is the uniform distribution on A' as above and
Pyla = =N (.4.4.
We divide X' into partition A == { ++1 : 0........ We follow Algorithm with [10, ....... 100), 50m, and R अमक (logı0 m)3. With no n म (log10 n)3 we also achieve the same bound (with different prefactors) Theorem 3.4 In the main experiments, we set Px ix.
40

---

C.1.2 Toy-3D
Let X = [0. C R and Ax be the uniform distribution on X. Define a kernel k(x,y) (1- ||x 1xx-7 --ll=))) }. The reproducing kernel Hilbert space H2 associated to the kernel k is norm-
equivalent to Sobolev space (X) [53] and the eigenvalue decay of ok is s = [68]. Note that y) = (1 ||x - >lIk=) (35 y + 18|[x - yIlRa + 3) is a kernel and its reproducing kernel Hilbert space is norm norm-equivan equivalent to Sobolev space H (X)). Using the interpolation relation between H² (X)) and (x)) gives that
(x) (1 | (35|lxx + 18| +
is in Hş and the regularity is 1. Similarly as before, we generate data points from Px Py/x such that Px is the uniform distribution on X' and
Pu|x (x)
We divide X' into partition = (1 اليط
x NS - 12 ا R (k1, k2)
{0, 133). Again, we follow Algorithm with m E [10, 20, ........ 100), n = 50m, no RS n 10 m)3, and Px Ax for kernel machine- based algorithms. For neural network-based algorithms, m = 50, no = 2500, and the other configurations are the same.
C.1.3 Real World Datasets
Energy Energy dataset is a real-world tabular dataset from the UCI database [12] It has 28 input features including measurement time, temperature and humidity of each room, outside temperature, and wind speed. The output is the appliances energy use. We normalize all features, including the output, using MinMaxScaler. There are 12,000 training data points distributed across the parties. We use 6,000 samples public inputs and 1,000 samples for testing. To construct non-i.i.. setting, we set a partition A consisting of subsets, each formed by splitting three normalized variables (measurement time, visibility, and dewpoint) at their midpoints. We apply Algorithm 3 with m 50.
RotatedMNIST RotatedMNIST is a dataset derived from MNIST []]. The task is to predict the rotated angle of a given rotated MNIST image. Each image is 28 28 image, and we normalize all images by their mean and variance. To generate RotatedMNISST we rotate MNIST images by a random angle between each image is rotated at multiple angles to generate multiple data instances. For training data, we additionally inject Gaussian noise with standard deviation of 0.2 to each label. We use 200,000 images as the entire training data, 50,000 images as public inputs, and 50,000 images as test data. The whole training input distribution, public input distribution, and test input distribution are uniformly distributed across digits 0 to 9. For example, there are 20,000 rotated images of the digit '4' in the training set. For non-i.i.d. setting, we partition the data into A where AA 10, based on the digit (0 ~ 9) and follow Algorithm 3 with m 50.
and 2 and use the angle the label. To construct large-scale dataset,
UTKFace UTKFace dataset 71 is an image dataset used for age estimation. Since the image sizes vary, we resize all images to 3 x 128 x 128 and normalize them by their mean and variance for each channel. The labels are normalized to the range [0, 1] using MinMaxScaler. For training data, we inject Gaussian noise with standard deviation of 0.5 to each label before normalization. We use 12,544 samples for training and 1,039 samples for testing. We have 6,234 public inputs. These three datasets have the same distribution for metadata (gender and race). Based on this metadata, we construct a partition A with AA 10 and distribute the training data among 50 parties according to Algorithm
IMDB-WIKI MDBBWWKK dataset [52] is also an image dataset for age estimation. experiments, we utilize a clean version 42 We further resize all images to 3 x 64 x 64 and normalize them as UTKFace. The labels are also normalized to the range [0, 1] using MinMaxScaler. We use 147,107 images as the entire training data, 36,780 images as public inputs, and 56,087 images as test data. In this dataset, we utilize the triplet (head_roll, head_yaw, head_ _ead_pptchh as metadata. Both training inputs and public inputs have the same distribution for metadata. We construct decentralized setting among 50 parties using a partition A based on the metadata, following Algorithm 3 The partitioning is performed by dividing the dataset into regions based on the median values of each metadata variable.
41

---

Table 4: Hyperparameters C and D on kernel machine-based algorithms in main results
centralKRR
centralKRGD
DC-NY
DKRR-NY-CM
IED
DCL.KRR
Toy-ID C' 0.055
D
C 0.006
C 0.008
0.025
2.5
Toy-3D
C' 0.016
D = 50
C 0.002
C = 0.005
C 0.007
= 12.5
C.2 Implementation
The experiments are implemented in PyTorch. We simulate decentralized setting on single deep learning workstation (Intel(R) Xeon(R) Gold 6430 with one NVIDIA GeForce RTX 4090 GPU and 189GB RAM). All DCL-KR implementations take less than 10 minutes per simulation. The non-parallel implementation of DCL-NN for large-scale datasets is completed within 48 hours. With parallel computing, the execution time for the same setup is expected to reduced to within hours.
C.3 Experimental Setup and Results on Kernel Machine- based Algorithms
C.3.1 Experimental Setup Details and Main Results
In this experiment, evaluate DCL-KR by comparing its performance against central models and three baselines. Specifically, we employ DC-NY [66]. DKRR-NY-CM (67], and IED [48] as baselines. We also compare DCL-KR with central Kernel Ridge Regression (centralKRR) and central Kernel Regression with Gradient Descent (centralKRGD), As mentioned earlier, we evaluate the performance of these algorithms on Toy- ID and Toy-3D datasets.
There are several hyperparameters for kernel machine- based algorithms: the ridge regularization hyperparameter À in the ridge regressions and the number of iterations (or communication rounds) in the gradient descent-basse based regressions. We À C n 2 and int D (++++))) ) which are the optimal choices from theory. We determine the best values for C' and D by grid search in our experiments (see Table 4 for the selected hyperparameter values). For centralKRGD and DCL-KR, we set the learning rate 7 0.5 which satisfies y (0, 1/k²) in Theorem 3.4 The number of local iterations E for DCL-KR is set to 5. For DKRR-NY-CM, we modify its Newton- Newton-Raphson iteration as shown below due to an instability issue, and set the learning rate 17 0.01:
(PZTR,X Pz AT) + AT)u P2SDy).
The communication round for DKRR-NY-CM set to 10.
To measure performance, we sample data from the distribution presented in Appendix C.1 for each simulation and compute Elllp on the dataset. We conduct 500 simulations for each setting, and the results are summarized in Figure I As shown in Table I DC-NY and DKRR-NY-CM. have theoretical performance guarantees under the statistically homogeneous condition for a limited number of parties. However, they do not exhibit sufficiently good performance in massively distributed statistically heterogeneous settings. The performance degradation of DKRR-NY-CM appears to be linked to its second-order optimization scheme, which leads to ineffective batching in statistically heterogeneous settings. The performance degradation of DC-NY is expected, given the inherent limitations of divide-and-conquee algorithms.
1l1 by averaging the Root Mean Squared Errors (RMSEs)
In contrast, IED demonstrates relatively better performance, despite the strong assumptions underlying its theory. Nevertheless, it still exhibits performance degradation compared to centralized models. DCL-KR, the other hand, achieves performance comparable to centralized models, validating both the theoretical results and its practical feasibility.
C.3.2 Effect of To
As public inputs directly affect the training information sharing, we anticipate that the performance of DCL-KR will vary depending the number of public inputs no. To examine this effect,
42

---

2.0
2.0
7-05
7-05
1.8
Rverace WASES
1.6
d= -005
Reerage RMSES
1.6
d- 45505
1.4
1.4
1.0
0.8
The number parties
The number parties
(a) DCL-KR
(b) IED
Loganthim of ROASES
Logarithm of Average of RMSSS
-B- p=
2.0
0.55
-1.0
-
2.0
-2.4
-22
-2.4
-2.0
-26
logm
logm
(c) DCL-KR (log-scale)
(d) IED (log-scale)
Figure 5: Performance of IED and DCL-KR with Px & Px on Toy-3D
measure the performance of DCL-KR on Toy-3D for no = a -rー (logıu n) with various a {0.1, 0.5, 1,2]. Additionally, we conduct the same experiment with IED, the most competitive baseline, for comparison.
The results are summarized in Figure 2 Consistent with theoretical results, the value a does not affect the convergence rate of IED and DCL--KR. However, IED displays significant performance variations across different a values. In contrast, DCL--KR achieves its maximum performance when is not too small (i.e., a 0.3 Figure 2). This implies that DCL-KR requires fewer public inputs to achieve its maximal performance compared to IED, as predicted by theoretical results.
C.3.3 Effect of Px
So far, we consider the settings with Px = Px However, Theorem 3.4 covers the general case where 7x + Px. To verify this, we define the public input distribution in Toy-3D with the following density function (parametrized by 3):
3
2121,12,2213)
II ((2 23)xr + 3), (2, E 10, 1=1
B E (0,
The Radon-Nikodym derivative des satisfies 0 < dos < (t) We conduct additional experiments dpx
Tp
to verify Theorem 3.4 and Corollary A.7 considering the case where 3 0.5 (with 1) and the case where 0.5 but a = 4 to compensate. The results are provided in Figure In the log-scale plot, the slope represents the convergence rate.
First, we observe that the convergence rate of DCL-KR remains unchanged when 3 is changed from 1 (i.e., Px = (xx to 0.5. This observation is consistent with Theorem 3.4 Additionally, regarding Corollary A.7 we confirm that DCL-KR achieves performance almost identical
case /x = ix by increasing rig- In contrast, the convergence rate of IED worsens when /x changes, even when Tig is increased. These experimental results highlight the advantages of DCL-KR in statistically heterogencous environments.
43

---

Table 5: Hyperparameters for Standalone
Toy-3D
Energy
MNIST
UTKFaaee
IMDB
batch
10
128
16
learning rate
le-2
2e-2
5e-3
le-4
5e-3
Table 6: Hyperparameters for FedMD
Toy-3D
Energy
MNIST
UTKFace
IMDB
communication rounds sample size of public data
100
50
500
1000
5000
2000
5000
learning rate local epochs
2c-4
lc-4
lc-4
5c-5
2c-4
10
10
5
5
distillation epochs batch size (local) batch size (public)
1
20
20
20
10
16
32
32
32
16
16
32
Table Hyperparameters for FedHeNN
Toy-3D
Energy
MNIST
UTKFace
IMDB
communication rounds sample size of public data
<100
<100
100
<50
500
500
5000
1000
5000
learning rate distillation coefficient batch size (local) batch size (public)
2e-4
2e-4
le-4
le-4
5e-4
1
0.1
10
10
32
32
32
C.4 Experimental Setup and Results on Neural Network- -based Algorithms
C.4.1 Experimental Setup Details
In the experiments on neural network-based collaborative learning algorithms, we evaluate three baselines (FedMD, FedHeNN, KT-pFL) and our algorithm DCL-NN. Note that while KT-pFL is a personalized collaborative learning algorithm. it also performs well in non non-personalized settings, so we include for comparison. Additionally, evaluate centralized models as ideal cases and standalone models as worst cases. Centralized models are trained using all local data.
We tabular datasets, Toy-3D and Energy, and three image datasets, RotatedMNIST, UTKFace, and IMDB-WV WIKI. The number parties set to 50 for all settings. For the tabular datasets, we employ four different fully connected neural networks (FNNs) with ratio of 30%, 30%, 20%, and 20%. Specifically, There are fifteen 4-layer FNNs with 32 hidden units, fifteen 4-layer FNNs with 64 hidden units, ten 5-layer FNNs with 32 hidden units, and 3-yerr FNNs with 64 hidden units. Similarly, for the image datasets, we use four different convolutional neural networks (CNNs) with the same ratio of 30%. 30%, 20%, and 20%. For the large-scale image datasets (RotatedMNNIST and HIDB-WIKI), we construct 50 local parties using fifteen ResNet-18, fifteen ResNet-34, ten ResNet- 50 200) and ten MobileNetv2 [54]. For UTKFace, which is image dataset with limited data, we utilize four simpler CNN architectures due to the ineffectiveness of knowledge distillation with large underperforming models. The first and third CNNs share a similar architecture, featuring two convolutional layers with batch normalization [22, two max pooling layers, and two fully-con colleccoddeted layers the end. They differ only in the number of channels. In contrast, the second and fourth CNNs are more complex, featuring four convolutional layers with batch normalization, two max pooling layers, and two fully-connected layers at the end. They also differ the number of channels. We use the ReLU activation function throughout.
44

---

Table 8: Hyperparameters for KT-pFL
Toy-3D
Energy
MNIST
UTKFace
IMDB
communication rounds sample size of public data
<50
50
500
500
5000
2000
1000
learning rate distillation epochs batch size (local) batch size (public)
2c-4
le-4
le-4
le-4
2c-4
1
10
2
10
10
10
16
16
16
Table 9: Hyperparameters for DCL-NN
Toy-3D
Energy
MNIST
UTKFace
IMDB
epochs (kernel matching)
100
100
200
200
200
base learning rate (local)
Se-2
le-2
8e-3
8e-3
8e-3
local epochs
50
50
25
25
25
All optimizers used are Adam 26 One remark that baseline algorithms only utilize a subset of public inputs through random sampling in each communication round, performance tends to deteriorate due to overfitting when all public inputs are used in every round. Hyperparameters are tuned via grid search.
Standalone models are trained with pross-validation and early stopping prevent overfitting. To evaluate centralized models, we first compute the averaged test Root Mean Squared Error (RMSE) from at least 10 simulations for each neural network architecture and then calculate the weighted average of the performances of all architectures according their ratio. For standalone models, use the average of the test RMSEs local models with the hyperparameters listed Table 5 In table, RotatedMNIST is abbreviated as MNIST, and IMDB-WII is abbreviated as IMDB.
For FedHeNN, we set the number local epochs to 30 in all experiments. For KT-pFL, we set the number of local epochs to 10, the distillation coefficient to 0.5, and the learning rate of knowledge coefficient to 1e-3. Lastly, for DCL.NNN in the main experiment, we set the learning rate for kernel matching to 1e-4 and the number of communication rounds in the collaborative learning phase to We use the closed-form solution train public data and full-batch gradient descent train local data in the collaborative learning phase of DCL-NN and utilize FedMD for pretraining in DCL-NN. In the pretraining phase, the hyperparameters are the same as the FedMD setting, except that the number of communication rounds is 100 for tabular data and 50 for image data. The remaining hyperparameters are presented in Table S and For all distillation-basee collaborative learning algorithms, simulate each setting least 5 times with different initializations.
Communication Efficiency Compared with FedMD and KT-pFL, DCL-NN incurs higher commu- nication costs Onn)) due to the transmission of the Gram matrix. FedHeNN also utilizes kernel matching but performs it in batches for each communication round. Thus, in scenarios requiring many communication rounds, DCL-NN more efficient than FedHeNN. However, pretraining also demands more communication cost. We leave the study of communication-cfficii methods in DCL-NN for future work.
C.4.2 Effect of Public Inputs
In practice, the public inputs can be sampled from distribution whose support is disjoint from that of the whole local input distribution. In this case, the assumption of DCL-KR does hold; however, DCL-NN can still be applicable. To evaluate the performance of DCL-NN under these conditions, we compare the performance DCL-NN and FedMD when the distribution of public inputs differs, as in Table [0
We use CIFAR1O 10 28 for public inputs on UTKFace. As shown in Table [0] DCL-NN
Note that while DCL-NN should use vanilla gradient descent according to DCL-KR, Adam performs better practice.
45

---

Table 10: Performance comparison of FedMD and DCL-NN on UTKFaae with different public datasets. In addition to performance, the kernel performance of local feature kernlls, computed in the same way as before, shown parantheses.
FodMD
DCL-NN
UTKFace
0.151 + 0.004 (4.1
0.148 +: 0.001 (0.146)
w/ CIFARIO
0.160 = 0.000 (0.159)
0.162 = 0.001 (0.158)
does not yield better results in this case. Note that the kernel performance of local feature kernels is improved compared to FedMD, leading conclude that the performance degradation of DCL-NN with CIFARIO 10 due to the violation of the DCL-KR assumption rather than the ineffectiveness of the kernel distillation procedure.
D Limitations and Future Works
Privacy Benefits of Distillation-base Collaborative Learning Due to its black-box nature, distillation -aseed information interaction is expected to offer privacy preservation benefits com- pared to parameter exchange (mainly done in FL) as mentioned in [19]. To the best of our knowledge, there is no rigorous study that discusses the privacy preservation advantages of distillation-bis based collaborative learning. We hope to see further discussion on this as well.
Public Input Distribution Theorem 3.4 covers the case where the public input distribution Px differs from that of local data inputs Px. but at least the support of Px must include the support of Px. Therefore, we experimentally observe a performance drop DCL-NN, a practical extension of DCL-KR, when A and Ax have different supports. Enhancing the robustness of DCL-NN in this scenario is considered a promising direction for future work. Our theory does not cover situations where collecting public inputs is difficult, In such cases, seperate generative model is usually trained to generate public inputs [72). We leave the theoretical discussion that includes these cases for future work.
46

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction accurately describe the motivations, theoreti- cal/experimental contributions, and scope of our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix D
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
47

---

The theoretical results and its assumptions are clearly described in Section 3 and Appendix A Idea of the proof is briefly described in Section and the full proof is provided in Appendix A
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The proposed algorithms are clearly stated in Algorithm D and Algorithm 2
Experimental details such experimental setting, performance measure, data preprocessing. and hyperparameter setting are also explained in Section 5 and Appendix C The code is also provided via the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
48

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
The code is provided via the supplementary material. Regarding datasets, the paper contains data source and preprocessing descriptions. The paper also provides sufficient experimental details to reproduce the experimental results. See Section and Appendix
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss://iip..ce)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e-g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details such data split, hyperparameters, optimizers, and model architectures are provided in Section 5 and Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experimental results contains 1-sigma error bars and the explanations about the error bars are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
49

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g,, Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Descriptions of computer resources are provided in Appendix C.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htt
Answer: [Yes]
Justification: The authors verify that the research is conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Section
50

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All data and models used in the paper are credited through citations according to the license.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
51

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papprssitthheeeee thcode cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
The code is provided via the supplementary material with well-written documentation.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
52

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "9Zr2WFjQhh", "reviewer": "Reviewer_Dtec", "summary": "In this paper, the authors perform a study of distillation-based collaborative learning (DCL) in massively distributed statistically heterogeneous environments. In particular, the study focuses on analyzing DCL-KR, a non-parametric version of FedMD, and proves its near-minimax optimality. The authors proposed DCL-NN, a method that leverages kernel matching to implement DCL with heterogeneous neural networks. Experimental results support the theoretical analysis of DCL-KR and demonstrate the effectiveness of DCL-NN.", "questions": "Could the authors avoid mentioning privacy as no formal privacy study is conducted?", "limitations": "The paper unnecessarily emphasizes privacy while admitting that privacy is not formally defined (cf. question). It would be nice to provide more discussion on this aspect or to present some empirical evidence of the claimed benefit (e.g., performing privacy attacks such as membership inference)", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper provides a theoretical analysis of DCL-KR and proposes a practical algorithm for using neural networks in massively distributed statistically heterogeneous environments. The authors perform experiments with both synthetic and real-world datasets to support the theoretical results and evaluate the performance of DCL-NN.", "weaknesses": "The paper does not perform any formal privacy analysis. As such, I believe using terms like \"privacy-preserving\" can be misleading in this context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the detailed comments and hope to address all of the questions and concerns raised by the reviewer.\n\n> The paper does not perform any formal privacy analysis. As such, I believe using terms like \"privacy-preserving\" can be misleading in this context.\n\n> Could the authors avoid mentioning privacy as no formal privacy study is conducted?\n\nIn our manuscript, we use the term “privacy-preserving” to describe distillation-based collaborative learning (DCL) in the sense that it exchanges the predictions on public data (functional information) rather than directly exchanging local data. As we mentioned in lines 1383 - 1385, we believe that this black-box nature allows DCL to protect local data privacy.\n\nIn a similar vein, as mentioned in Section 1 and 2, DCL has been studied mainly in the context of Federated Learning (FL) that aims to preserve local data privacy on decentralized learning. Therefore, we can see that previous studies have also been conducted based on this intuitive (though not rigorous) reasoning.\n\nHowever, as the reviewer pointed out (and as mentioned in Appendix D of our manuscript), there has not been a rigorous study addressing the privacy concerns of DCL. Fundamentally, we agree that it is necessary to discuss comprehensively the privacy preservation advantage of functional information transfer through knowledge distillation. This seems to be a very interesting topic, but it is beyond the scope of our work and left for a further study.\n\nIn summary, our work shares the belief widely assumed in the previous DCL works (particularly in the context of FL), but we understand the reviewer’s concern about using terms like “privacy-preserving” without rigorous discussion. We will strive to soften these expressions in future versions to ensure that readers understand accurately.", "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": "", "extra_scores": {}}, {"review_id": "JVghw9tBCJ", "reviewer": "Reviewer_1rrx", "summary": "This paper theoretically proves a nonparametric version of the most standard distillation based collaborative learning algorithm (named DCL-KR) is nearly minimax optimal in massively distributed statistically heterogeneous environments.\nExtensive experiments demonstrate their theoretical results and show the practical feasibility of DCL-NN.", "questions": "Please see Limitations", "limitations": "This is not my field of study and I can only give a Borderline Reject. I will adjust my score based on the scores of other more specialised judges.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is well-written.\n2. The authors conducted extensive experiments to verify the effectiveness of the proposed method.", "weaknesses": "Please see Limitations", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the detailed comments. We briefly describe the main contribution of our work as below:\n* Applying kernel regression theory, we analyze the most representative DCL algorithm, FedMD, from a non-parametric perspective (called DCL-KR). Compared with the existing studies, our work is the first to theoretically demonstrate the effectiveness of DCL algorithm on statistically heterogeneous and massively distributed environments.\n* Based on the theoretical results, we propose a novel neural network-based DCL algorithm (called DCL-NN) using kernel matching.\n* Through experiments, we validate the theoretical results and demonstrate the superiority of our algorithms (DCL-KR and DCL-NN) by comparing its practical performance with baselines.\n\nKindly let me know if you require any further clarification or have additional comments.", "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": "", "extra_scores": {}}, {"review_id": "KEdbydMZ8a", "reviewer": "Reviewer_UU4M", "summary": "The paper investigates the theoretical underpinnings and practical implementation of distillation-based collaborative learning (DCL) from a kernel regression perspective. The authors propose DCL-KR, a nonparametric version of the FedMD algorithm, which achieves nearly minimax optimal convergence rates in massively distributed and statistically heterogeneous environments. Building on these theoretical insights, the authors introduce DCL-NN, a practical DCL algorithm designed for neural networks, which incorporates feature kernel matching to align local models. Extensive experiments on various regression tasks demonstrate the superiority of DCL-KR and DCL-NN over existing methods.", "questions": "1. How does the choice of kernel affect the performance/theoretical guarantee of the proposed approach?\n\n2. Is transferring predictions a common practice in collaborative learning for regression? If not, how does it compare with the other approaches in terms of privacy and efficiency?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a rigorous theoretical analysis of DCL-KR, proving its nearly minimax optimality in distributed and heterogeneous settings.\n\n2. Experiments are comprehensive. Six datasets are included.\n\n3. The improvement of DCL-NN is significant over the other baselines in some datasets.", "weaknesses": "1. The paper lacks a discussion on the privacy risk and communication efficiency of DCL-KR and DCL-NN.\n\n2. The paper is based on distillation-based collaborative learning method that requires public data, which limits the applications on private domains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the detailed comments and hope to address all of the questions and concerns raised by the reviewer.\n\n> The paper lacks a discussion on the privacy risk and communication efficiency of DCL-KR and DCL-NN.\n\nBasically, our work shares the typical (widely used) assumption of distillation-based federated learning (that the collaborative distillation method, interacting through the predictions on public inputs, can preserve privacy due to its black-box nature). However, as explained in Appendix D, privacy concerns for DCL algorithms have not been sufficiently explored. This issue is not straightforward because it requires fundamental analysis on privacy preservation of functional information transfer through knowledge distillation. This topic seems to be a very interesting topic, but it appears to be beyond the scope of our work and left for a further study.\n\nRegarding communication efficiency, both DCL-KR and kernel regression-based baselines require a communication cost of $O(n_0)$ per communication round (except the download of public inputs) where $n_0$ is the number of public inputs. DCL-NN communicates the gram matrix (with communication cost $O(n_0^2)$) and requires $O(n_0)$ communication cost per communication round in collaborative learning phase. Compared with FedMD and KT-pFL, DCL-NN has higher communication costs due to transmitting the gram matrix. Since FedHeNN also uses kernel matching but performs it in batches for each communication round, in cases that many communication rounds are needed, DCL-NN is more efficient than FedHeNN. However, when we use DCL algorithms for pretraining of DCL-NN, more communication cost is required for pretraining. Therefore, there is a trade-off between performance and communication cost.\n\nTo reduce the communication cost of DCL-NN, we can use the following idea: If the feature dimension $d$ of the local model is smaller than $n_0$ (# of public inputs), a direct transmission of the raw feature (whose dimension $n_0 \\times d$) or the decomposition of the gram matrix can reduce the communication cost. \n\n> The paper is based on distillation-based collaborative learning method that requires public data, which limits the applications on private domains.\n\nAs the reviewer pointed out, there may be cases where it is difficult to collect public data. However, as explained in Section 1, we would like to emphasize that our problem involves prohibiting the direct exchange of not only local data but also model information. These restrictions necessitate an additional information sharing medium.\n\nIn this context, our theoretical findings highlight a strength of our algorithm. According to Theorem 3.4 and Corollary A.7, as long as the public data distribution covers the support of the local data distribution, theoretical performance guarantees are provided. Moreover, when the public data has a different distribution from the local data but there is a large amount of public inputs, it can compensate for the distribution gap and ultimately achieve the same performance as central training.\n\n> How does the choice of kernel affect the performance/theoretical guarantee of the proposed approach?\n\nIn our theoretical analysis, the kernel is related to the quantity $r$ and $s$ when the target function is given. These quantities determine the minimax lower rate $O(n^{–r/(2r+s)})$ in Theorem 3.4, meaning that the convergence rate varies depending on the choice of kernel. Hence, the faster eigenvalue decay of the kernel (smaller $s$) and the better regularity of the target function (larger $r$) in the RKHS induced by this kernel (which means the RKHS represents the target function well in some sense) give a better performance (faster convergence rate). We can also see that a good choice of the kernel reduces the number of the required public data $(n^{1/(2r+s)}log^3 n)$ in Theorem 3.4.\n\n> Is transferring predictions a common practice in collaborative learning for regression? If not, how does it compare with the other approaches in terms of privacy and efficiency?\n\nIn terms of not directly sharing local data, Federated Learning (FL) with parameter exchange can be considered as a similar approach to Distillation-based Collaborative Learning (DCL). However, to the best of our knowledge, in scenarios where neither model nor local data can be directly shared, DCL methods are the only option. As stated in Section 1, our setting is distinguished from traditional FL (that exploits parameter exchange) by the inability to directly share the local model. Therefore, a direct comparison between DCL and traditional FL may not be appropriate in general.\n\nOf course, putting these points aside, we can simply compare DCL with traditional FL in terms of privacy and efficiency. As noted in Appendix D of our manuscript, there is an intuition that DCL may be better than parameter exchange-based FL in terms of privacy. In more detail, parameter exchange has a white-box nature in which the internal information of the model is shared, while the predictions of public data have a black-box nature because the structure of each local model is not known externally. However, we acknowledge that more rigorous discussions on privacy for DCL is required as mentioned earlier. \n\nFrom an efficiency standpoint, a simple comparison of communication cost is possible. When using large models, DCL-NN (that communicates public inputs and gram matrix only once and shares predictions in each communication round) can be more efficient than communicating model parameters in each communication round.\n\nHowever, DCL algorithms still exhibit worse performance compared with traditional FL in general. This is because DCL addresses a more challenging problem. We believe that DCL needs to improve its effectiveness before focusing on efficiency improvements, and we expect our work to play a significant role in this aspect.", "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": "", "extra_scores": {}}, {"review_id": "ZBQgPlGvts", "reviewer": "Reviewer_UpcW", "summary": "The authors propose a nonparametric version of FedMD, a distillation-based collaborative learning methodology. They also propose a neural network variant of the nonparametric approach as an extension for heterogeneous local neural network models. They provide both theoretical results on the nonparametric approach and experimental results demonstrating efficacy of the neural network extension. The theoretical results prove the nearly minimax optimality of this nonparametric collaborative learning algorithm in massively distributed statistically heterogeneous environments.", "questions": "(1) How do you handle the computational burden associated with the calculation of Gram matrices for large datasets? (2) How do you handle cases where these representations before the last layers of the neural networks are suitable for kernel matching?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) The authors prove the (nearly) minimax optimality of a privacy-preserving collaborative learning algorithm using kernel regression in massively distributed, statistically heterogeneous environments. (2) Theorem 3.4 addresses a more general setting than prior works [48, 58]. Su et al. [58] only cover r = \\frac{1}{2}​ of Assumption 3.3. Park et al. [48] do not consider Assumption 3.2, which provides a finer result. Furthermore, compared to [48], the required size of public inputs is reduced and the statistical homogeneity condition is dropped. (3) The rate n^{-\\frac{r}{2r+s}} is the minimax lower rate under Assumptions 3.1, 3.2, and 3.3, making DCL-KR nearly optimal in a minimax sense. (4) On the difference between public and local distributions: Theorem 3.4 allows the public input distribution \\tilde{\\rho}_x to differ from the local input distribution \\rho_x​. (5) Finally, The difference between \\rho_x​ and \\tilde{\\rho}_x​ impacts the expected risk upper bound as a multiplication of B_r​, which can be removed by increasing public inputs.", "weaknesses": "(1) The need to perform learning rate scaling to ensure the impact of local iterations is consistent across models introduces additional complexity. The exact method for scaling may vary and might not be trivial to determine or implement. (2) The computation of Gram matrices for CKA involves O(p^2) operations, where p is the number of public data points. This quadratic complexity can become prohibitive as the size of the public dataset increases. (3) The method assumes that the ensemble kernel k = \\sum_{i=1}^{m} \\frac{n_i}{n} k_{f_i} will perform better than individual feature kernels. This assumption might not hold in cases where local models are highly heterogeneous, as the averaged kernel could lose important characteristics of individual models, leading to suboptimal performance. The authors empirically verify the superiority of the ensemble in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the detailed comments and hope to address all of the questions and concerns raised by the reviewer.\n\n> (1) The need to perform learning rate scaling to ensure the impact of local iterations is consistent across models introduces additional complexity. The exact method for scaling may vary and might not be trivial to determine or implement.\n\nAs the reviewer pointed out, we calculate and utilize the empirical CKA on the whole public inputs of local feature kernels for learning rate scaling. We use this approach for precise calculation, but we agree that it can be computationally intensive. Therefore, we additionally conduct experiments on RotatedMNIST by sampling a few public inputs and calculating the empirical CKA based on them. The experimental results are as follows:\n\n|GD, 50 data points used|GD, full data points used|\n|---|---|\n|$0.243\\pm 0.006$|$0.243\\pm 0.006$|\n\nWe can observe that when using vanilla gradient descent, calculating empirical CKA with 50 public inputs is sufficient for learning rate scaling. When using Adam, we obtain the following results, also indicating that calculating empirical CKA with 50 samples is sufficient. \n\n|Adam, 50 data points used|Adam, full data points used|\n|---|---|\n|$0.227\\pm 0.003$|$0.227\\pm 0.003$|\n\nConsequently, calculating empirical CKA for learning rate scaling can be done with a small number of public inputs and then it does not require extensive computational resources. We will include these results in the manuscript.\n\n> (2) The computation of Gram matrices for CKA involves O(p^2) operations, where p is the number of public data points. This quadratic complexity can become prohibitive as the size of the public dataset increases.\n\nWe think this is a good point. The kernel distillation procedure is a crucial component in enhancing performance by maintaining the theoretical assumptions of DCL-KR in the neural network setting, so calculating the gram matrix is unavoidable. However, we can apply some tricks to compute it more efficiently. \n\nFor example, we can perform this calculation on the server to reduce the computational burden imposed on local parties. First, the local parties directly upload the raw features of public inputs (whose dimension is $n_0 \\times d$ where $n_0$ is the number of public inputs and $d$ is the dimension of the local feature) to the server. Then the server can compute the feature kernels. Since this approach only requires the local party to perform forward propagation for the public inputs, it significantly reduces the computational cost on the local parties. Additionally, this method can also reduce communication costs when dealing with a large amount of public data. For reducing the overall computational burden (including the server), we believe that an additional study is needed and we will strive to address this issue in future work.\n\n> (3) The method assumes that the ensemble kernel k = \\sum_{i=1}^{m} \\frac{n_i}{n} k_{f_i} will perform better than individual feature kernels. This assumption might not hold in cases where local models are highly heterogeneous, as the averaged kernel could lose important characteristics of individual models, leading to suboptimal performance. The authors empirically verify the superiority of the ensemble in the appendix.\n\nIn fact, the ensemble kernel theoretically has stronger expressivity than each individual local feature kernel, so with a sufficiently large amount of data, a better regressor will be trained when we use the ensemble kernel. We demonstrate this in Appendix B (lines 1142 - 1145). Therefore, with enough data, it is not possible for the ensemble kernel to perform worse than individual local feature kernels.\nHowever, fully distilling the ensemble kernel is challenging. Thus, there is a possibility of losing important characteristics (that the reviewer concerned with) during the kernel distillation process. Precisely, some important features may have a lower portion in the ensemble kernel and so they can be potentially missed during the distillation process. One possible solution is for each local party to construct local feature kernels by selecting important features and adjusting weights accordingly. \n\n> (1) How do you handle the computational burden associated with the calculation of Gram matrices for large datasets?\n\nPlease refer to our responses above.\n\n> (2) How do you handle cases where these representations before the last layers of the neural networks are suitable for kernel matching?\n\nIn our work, we assume that the local model is of the form $f(\\cdot) = w^\\top g(\\cdot) + b$ and design our algorithm accordingly. All neural network architectures with this form (that is, the last layer is a fully connected layer) are suitable for kernel matching. Note that most modern neural networks have this structure. Therefore, in most cases, our algorithm is applicable.\n\nIf other forms of neural networks need to be utilized, we anticipate that significant changes to the algorithm would be required. Fundamentally, DCL-NN is inspired by DCL-KR. DCL-KR is based on kernel regression (a type of linear model) and this nature plays a crucial role in its theoretical results. Exploring the ways to generalize the extension from DCL-KR to neural network settings would be a valuable direction for future work.", "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": "", "extra_scores": {}}, {"review_id": "2JbOZ2lwBn", "reviewer": "Reviewer_Zad8", "summary": "This work presents an analysis of a distillation-based collaborative learning algorithm called FedMD from a nonparametric perspective. The method is to adopt an operator theoretic approach to obtain an upper rate for the expected generalization error of local models. Then, the authors propose DCL-KR to achieve a privacy-preserving nearly minimax optimal collaborative learning algorithm with kernel regression in massively distributed statistically heterogeneous environments.", "questions": "The related work only gives a rough summary of the previous works. When the authors focus on the theoretical analysis, could the authors compare their theoretical bounds to other works?\n\nThere are many important experiments in the appendix, such as C.3.1. Can the authors summarize empirical findings with a better paper structure? \n\nIn Section 3.3, the paper starts with \"To derive theoretical results\" and lists a lot of assumptions without any intuitive understanding behind them. Could the authors give an overview and intuition of theoretical results?\n\nMinor: I feel very confused when reading the paper as it introduces many conclusions/results without too much explanation. I suggest the authors elaborate on the intuitions before going into the details.", "limitations": "The paper presents a discussion of limitations, which is not convincing. For example, \"there is no rigorous study that discusses the privacy preservation advantages of distillation-based collaborative learning\". Actually, the standard technique for privacy is not distillation.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "+ The idea seems to be interesting.\n+ The first work tries to prove the (nearly) minimax optimality of a privacy-preserving collaborative learning algorithm.", "weaknesses": "- The paper's organization and structure are not clear.  \n- The writing looks like combining different parts of different papers without a clear clue.\n- The paper suddenly gives many assumptions in Section 3 for analysis but does not give any intuition or insight into them.\n- Some important experimental results are in the appendix. I would suggest that the authors extract insight into the experimental findings in the main body.\n- The language used in the paper is not concise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the detailed comments and hope to address all of the questions and concerns raised by the reviewer.\n\n> The paper's organization and structure are not clear.\n> The writing looks like combining different parts of different papers without a clear clue.\n\nWe attempted to write the manuscript well, but it seems that our manuscript did not effectively convey its content to the reviewer. Please refer to the general response. Our general response contains the outline of the overall flow of our manuscript and an additional explanation on the connection between DCL-KR and DCL-NN. Through this general response, we hope that the reviewer finds our manuscript to have a natural flow.\n\n> In Section 3.3, the paper starts with “To derive theoretical results” and lists a lot of assumptions without any intuitive understanding behind them. Could the author give an overview and intuition of theoretical results?\n\nWe are sorry to hear that the reviewer had a difficulty to read our theoretical analysis. In the future version, we will provide overview and intuition of theoretical results at the beginning of Section 3.3 as follows:\n* In this subsection, we prove the nearly minimax optimality of DCL-KR;\n* This result implies that DCL-KR has an almost same convergence rate as the minimax optimal central training when there are sufficiently many public inputs;\n* To the best of our knowledge, this is the first work to prove the nearly minimax optimality of a privacy-preserving collaborative learning algorithm with kernel regression in massively distributed statistically heterogeneous environments (Lines 179 – 181 in our manuscript).\n\nWe also provide a detailed explanation of assumptions from Section 3 in the general response. Please refer to the general response for details on this matter.\n\n> There are many important experiments in the appendix, such as C.3.1. Can the authors summarize empirical findings with a better paper structure?\n\nDue to the page limitation, we only included some of the experimental results and discussions in the main body. However, we agree with the reviewer that some important experimental discussions should be included in the main text to convey meaningful content and improve its structure. If permitted, we will utilize an additional page to incorporate the following results from the appendix into the main body.\n* We will include Figure 3, 4, and 5(c)-(d) in the main body.\n\nWe will include the following discussions in the main text:\n* As shown in Figure 3, DCL-KR outperforms the baselines in all experimental settings and achieves comparable performance to the central models. In contrast, DC-NY and DKRR-NY-CM exhibit significantly lower performance compared with DCL-KR in massively distributed environments where their theory does not cover. \n* IED does not show a significant performance drop in massively distributed environments. However, as predicted by the theoretical results, to perform well, IED requires more public inputs compared with DCL-KR. Moreover, when there is a public distribution shift, the convergence rate of DCL-KR is maintained, whereas that of IED worsens. We can also confirm that DCL-KR can address this distribution shift effectively with a large amount of public inputs.\n* Overall, our experiments validate the theoretical results of DCL-KR and demonstrate its superiority over previous results.\n\n> The language used in the paper is not concise.\n\nIf allowed, we will make effort to revise the manuscript to ensure it is concise and clear.\n\n> The related work only gives a rough summary of the previous works. When the authors focus on the theoretical analysis, could the authors compare their theoretical bounds to other works?\n\nIndeed, the previous works similarly aim to achieve (nearly) minimax optimality (i.e., prove inequalities that are similar to (2) in our manuscript). Thus, there is no difference in the bound itself except for logarithm rates and prefactors. Note that the prefactors are not considered in the analysis of minimax optimality. In addition, $\\log n$ grows slower than any polynomial.\n\nThe main differences lie not in the theoretical bound itself but in the decentralized environment settings that guarantee the bound, as summarized in Table 1. Some prior works have limitations on the number of local parties. For example, DKRR-NY-CM assumes $m\\leq O(n^{(2r+s-1)/(2r+s)})$ (with the same notation in our manuscript). In contrast, nFedAvg directly communicates local data and IED does not consider statistically heterogeneous cases. We elaborate on these points in lines 105 – 117 and lines 179 – 209. Our experimental results also demonstrate performance degradation of baselines when they are applied outside their assumed settings.\n\n> The paper presents a discussion of limitations, which is not convincing. For example, \"there is no rigorous study that discusses the privacy preservation advantages of distillation-based collaborative learning\". Actually, the standard technique for privacy is not distillation.\n\nAs the reviewer pointed out, distillation is not a standard technique for privacy. However, as mentioned in Section 1, Distillation-based Collaborative Learning (DCL) algorithms have been proposed in the context of Federated Learning (FL) where local data privacy preservation is crucial. This is because, as mentioned in Lines 1383 – 1385, the communicated information is predictions on public data, which is expected to preserve local data privacy due to its black box nature. Initially, traditional FL algorithms that exploit parameter exchange also do not provide clear evidence for local data privacy concerns, but recent discussions address these issues extensively. In summary, we emphasize in Appendix D that DCL has the potential to preserve local privacy and that there is a need to study privacy concerns in DCL, similar to the research flow in traditional FL algorithms.", "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": "", "extra_scores": {}}]

Author rebuttal:
We appreciate all reviewers for the detailed comments. In this general response, we provide additional explanations to help the reviewers better understand our work. In detail, we (1) briefly outline the overall flow of our manuscript, (2) provide additional explanations on the connection between DCL-KR and DCL-NN, and (3) provide additional explanations on Assumptions introduced in Section 3. If permitted, we will include them in the revised version.

**Overall Flow of Our Manuscript**

As explained in Section 1 of our paper, we first provide a theoretical foundation for a nonparametric version of FedMD [1] (called DCL-KR) and use this result to design its neural network version (called DCL-NN). In detail, we first obtain the nearly minimax optimality of DCL-KR through kernel regression theory. This implies that DCL-KR with sufficiently large public inputs has an almost same convergence rate as minimax optimal central training. (Section 3)

While this theoretical analysis represents significant improvements compared to previous results (Table 1, lines 179 – 209), it does not fully explain the performance guarantee of neural network-based DCL. So, we design a new DCL algorithm (DCL-NN) inspired by the theory of DCL-KR (lines 50-56).

[1] D. Li and J. Wang. Fedmd: Heterogeneous federated learning via model distillation. arXiv preprint arXiv:1910.03581, 2019.

**Additional Explanation on Connection between DCL-KR and DCL-NN**

Indeed, we explicitly state that the equality of local kernels contributes the successful analysis of DCL-KR (lines 215-218) and DCL-NN is a natural extension of DCL-KR in this view. Here, we provide a detailed explanation on this point.

For simplicity, consider the case of $E=1$ in DCL-KR where $E$ is the number of local iterations. After the consensus prediction $u$ is distributed to local parties, the server receives the updated local prediction on $Z$ : $(I-\frac{\eta}{n_i} K_{ZX_i}K_{X_i\tilde{Z}}K_{\tilde{Z}\tilde{Z}}^{-1})u + \frac{\eta}{n_i} K_{ZX_i}y_i$ from the $i$-th local party. (The notation is consistent with the main body and Appendix A.2.1) Suppose the data at the $i$-th local party and the $j$-th local party are exactly the same. If the same kernel is used in these two parties, the updated local predictions will be identical. However, if the kernels of the two parties are different, this will not be the case. For kernels like the Gaussian kernel, which has high correlation between close inputs, the updated local prediction will be strongly influenced more by data points close to each input. We can observe this fact from the above formula. On the other hand, for kernels like the linear kernel, which has high correlation between distant inputs, the updated local prediction on $Z$ will be influenced more by data points farther from each input. This observation implies that aggregating local learning information becomes very challenging when the kernels differ.

In summary, using the same kernel ensures that the shift mechanisms of predictions on $Z$ at edges are identical, which makes it possible for the aggregation through simple weighted averaging to work well. This is a key of the strong theoretical results of DCL-KR. Therefore, DCL-KR and DCL-NN are deeply connected.

**Additional Explanation on Assumptions in Section 3**

Note that, as mentioned in lines 160 – 162, Assumption 3.1, 3.2, and 3.3 are commonly used when deriving the upper rate of expected generalization error. In recent decades, these assumptions have been used as the standard setting in kernel regression analysis. Relevant literature [2, 3] often introduces these assumptions without detailed explanations.

Nonetheless, we acknowledge that these assumptions might seem unfriendly to those unfamiliar with this research context. Therefore, we provide an explanation of these assumptions here.

Basically, as noted in line 160-162, Assumption 3.1 is about the regularity of noise, Assumption 3.2 is about the regularity of the kernel, and Assumption 3.3 is about the regularity of the target function. These assumptions influence the minimax lower rate [4]. In detail,

* Assumption 3.1 implies that the noise is not excessively large. In fact, noise with Bernstein condition satisfies Assumption 3.1. For instance, Gaussian/sub-Gaussian noises and bounded noises satisfy Assumption 3.1. Therefore, this assumption is a very general noise condition that encompasses a wide range of cases.
* Assumption 3.2 is about the eigenvalue decay of the kernel. This is a crucial factor when studying the behavior and properties of kernel. For example, from this assumption, one can derive bounds on the effective dimension that is related to covering and entropy number conditions.
* Assumption 3.3 is related to the regularity of the target function, specifically how well the RKHS induced by the kernel represents the target function. 

Under the above assumptions, the minimax lower rate is given by $O(n^{-r/(2r+s)})$. Thus, under these assumptions that precisely specify the minimax lower rate, our work analyzes whether DCL-KR has a similar upper rate. As a result, we demonstrate that DCL-KR is nearly minimax optimal and so we can conclude that DCL-KR has an almost same performance as the central kernel regresion model.

Many prior works also study the minimax optimality of other kernel regression-based algorithms under similar assumptions (Lines 92-117, Table 1, Lines 179 – 209 in our manuscript).

[2] Y. Li, H. Zhang, and Q. Lin. On the saturation effect of kernel ridge regression. In International Conference on Learning Representations, 2023.

[3] S. Park, K. Hong, and G. Hwang. Towards understanding ensemble distillation in federated learning. In International Conference on Machine Learning, pages 27132-27187. PMLR, 2023.

[4] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithms. Foundations of Computational Mathematics, 7:331-368, 2007.

Meta-review: The paper studies distillation-based collaborative learning (DCL) in a massively distributed heterogeneous setting. The authors analyze DCL kernel regression and prove its near-minimax optimality in their theoretical results. The paper also presents supporting experiments to demonstrate the effectiveness of the proposed method.

There is a consensus among reviewers that this work is theoretically sound and provides complementary experimental results to back the theoretical analysis. There are several suggestions by the reviewers to improve the paper further, especially the ones regarding the paper organization and the addition of discussions on (i) potential shortcomings if the local data belongs to a private domain without appropriate public data, and (ii) comparison of the theoretical bound in this work to those in prior works. 

Overall the reviews consistently agree that the paper makes a significant contribution over the prior work and provides a useful contribution to the domain. I would request the authors to consider the discussions summarized above and appropriately update the draft before the final submission.
Decision: Accept (poster)