{'fraction_non_alphanumeric': 0.03756960046888737, 'fraction_numerical': 0.017426980560711146, 'mean_word_length': 4.238027015963978, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards Model Agnostic Federated Learning Using Knowledge Distillation

Is it possible to design an universal API for federated learning using which an ad-hoc group of data-holders (agents) collaborate with each other and perform federated learning? Such an API would necessarily need to be model-agnostic i.e. make no assumption about the model architecture being used by the agents, and also cannot rely on having representative public data at hand. Knowledge distillation (KD) is the obvious tool of choice to design such protocols. However, surprisingly, we show that most natural KD-based federated learning protocols have poor performance. To investigate this, we propose a new theoretical framework, Federated Kernel ridge regression, which can capture both model heterogeneity as well as data heterogeneity. Our analysis shows that the degradation is largely due to a fundamental limitation of knowledge distillation under data heterogeneity. We further validate our framework by analyzing and designing new protocols based on KD. Their performance on real world experiments using neural networks, though still unsatisfactory, closely matches our theoretical predictions.


INTRODUCTION
"I speak and speak, but the listener retains only the words he is expecting... It is not the voice that commands the story: it is the ear." -Invisible Cities, Italo Calvino.
Federated learning (and more generally collaborative learning) involves multiple data holders (whom we call agents) collaborating with each other to train their machine learning model over their collective data. Crucially, this is done without directly exchanging any of their raw data (McMahan et al., 2017;Kairouz et al., 2019). Thus, communication is limited to only what is essential for the training process and the data holders (aka agents) retain full ownership over their datasets.
Algorithms for this setting such as FedAvg or its variants all proceed in rounds (Wang et al., 2021). In each such round, the agents first train their models on their local data. Then, the knowledge from these different models is aggregated by averaging the parameters. However, exchanging knowledge via averaging the model parameters is only viable if all the agents use the same model architecture. This fundamental assumption is highly restrictive. Different agents may have different computational resources and hence may want to use different model architectures. Further, directly averaging the model parameters can fail even when all clients have the same architecture (Wang et al., 2019b;Singh & Jaggi, 2020;Yu et al., 2021). This is because the loss landscape of neural networks is highly non-convex and has numerous symmetries with different parameter values representing the same function. Finally, these methods are also not applicable when using models which are not based on gradient descent such as random forests. To overcome such limitations, we would need to take a functional view view of neural networks i.e. we need methods that are agnostic to the model architecture and parameters. This motivates the central question investigated in this work: Can we design model agnostic federated learning algorithms which would allow each agent to train their model of choice on the combined dataset?
Our Contributions. The main results in this work are • We formulate the model agnostic learning problem as two agents with local datasets wanting to perform kernel regression on their combined datasets. Kernel regression is both simple enough to be theoretically tractable and rich enough to capture non-linear function fitting thereby allowing each agent to have a different kernel (hence different models). • We analyze alternating knowledge distillation (AKD) and show that it is closely linked to the alternating projection method for finding the intersection of convex sets. Our analysis reveals that AKD sequentially loses information, leading to degradation of performance. This degradation is especially severe when the two agents have heterogeneous data. • Using the connection to alternating projection, we analyze other possible variants such as averaged knowledge distillation (AvgKD) and attempt to construct an 'optimal' scheme. • Finally, we evaluate all algorithms on real world deep learning models and datasets, and show that the empirical behavior closely matches our insights from the theoretical analysis. This demonstrates the utility of our framework for analyzing and designing new algorithms.

RELATED WORK
Federated learning (FL). In FL (Kairouz et al., 2019), training data is distributed over several agents or locations. For instance, these could be several hospitals collaborating on a clinical trial, or billions of mobile phones involved in training a voice recognition application. The purpose of FL is to enable training on the union of all agents' individual data without needing to transmit any of the raw sensitive data. Typically, the training is coordinated by some trusted server. One can also instead use direct peer-to-peer communications (Nedic, 2020). A large body of work has designed algorithms for FL under the identical model setting where we either learn a single global model (McMahan et al., 2017;Reddi et al., 2020;Karimireddy et al., 2020b;a;Wang et al., 2021), or multiple personalized models (Wang et al., 2019a;Deng et al., 2020;Mansour et al., 2020;Grimberg et al., 2021).
Knowledge distillation (KD). Initially, KD was introduced as a way to compress models i.e. as a way to transfer the knowledge of a large model to a smaller model (Bucilua et al., 2006;Hinton et al., 2015). Since then, it has found much broader applications such as improving generalization performance via self-distillation, learning with noisy data, and transfer learning (Yim et al., 2017). We refer to a recent survey (Gou et al., 2021) for progress in this vast area.
KD in FL. Numerous works propose to use KD to transfer knowledge from the agent models to a centralized server model (Seo et al., 2020;Sattler et al., 2020;Lin et al., 2020;Li et al., 2020;Wu et al., 2021). However, all of these methods rely on access to some common public dataset which may be impractical. KD has also been proposed to combine personalization with model compression (Ozkara et al., 2021), but our focus is for the agents to learn on the combined data. In the closely related codistillation setting (Zhang et al., 2018;Anil et al., 2018;Sodhani et al., 2020), an ensemble of students learns collaboratively without a central server model.  (2020) consider self-distillation in a kernel regression setting i.e. the model is retrained using its own predictions on the training data. They show that iterative self-distillation induces a strong regularization effect. We significantly extend their theoretical framework in our work to analyze KD in federated learning where agents have different models and different datasets.

FRAMEWORK AND SETUP
Notation. We denote a set as A, a matrix as A, and a vector as a. A[i, j] is the (i, j)-th element of matrix A, a[i] denotes the i'th element of vector a. ||a|| denotes the 2 norm of vector a.
Centralized kernel regression (warmup). Consider, as a warm-up, the centralized setting with a training dataset , where x n ∈ X ⊆ R d and y n ∈ Y ⊆ R. Given training set D, our aim is to find best function f ∈ F : X → Y. To find f we solve the following regularized optimization problem: Here, F is defined to be the space of all functions such that (2) is finite, c is the regularization parameter, and u(x, x ) is a kernel function. That is, u is symmetric u(x, x ) = u(x , x) and positive with R u (f ) = 0 only when f = 0 and R u (f ) > 0 o.w. Further, let k(x, t) be the function s.t.
Now, we can define the positive definite matrix K ∈ R N ×N and vector k x ∈ R N as: Note that k x is actually a vector valued function which takes any x ∈ X as input, and both k x and K depend on the training data D. We can then derive a closed form solution for f .
Proposition I (Schölkopf et al. (2001)). The f which minimizes (1) is given by Note that on the training data X ∈ R N ×d with X[i, :] = x i , we have f (X) = K(cI + K) −1 y. Kernel regression for an input x outputs a weighted average of the training {y n }. These weights are computed using a learned measure of distance between the input x and the training {x n }. Intuitively, the choice of the kernel u(x, x ) creates an inductive bias and corresponds to the choice of a model in deep learning, and the regularization parameter c acts similarly to tricks like early stopping, large learning rate, etc. which help in generalization. When c = 0, we completely fit the training data and the predictions exactly recover the labels with f (X) = K(K) −1 y = y. When c > 0 the predictions f (X) = K(cI + K) −1 y = y and they incorporate the inductive bias of the model. In knowledge distillation, this extra information carried by the predictions about the inductive bias of the model is popularly referred to as "dark knowledge" (Hinton et al., 2015).
Federated kernel regression (our setting). We have two agents, with agent 1 having dataset Agent 1 aims to find the best approximation mapping g 1 ∈ F 1 : X → Y using a kernel u 1 (x, x ) and objective: Note that the objective of agent 1 is defined using its individual kernel u 1 (x, x ), but over the joint dataset (D 1 , D 2 ). Correspondingly, agent 2 also uses its own kernel function u 2 (x, x ) to define the regularizer R u2 (g 2 ) over the space of functions g 2 ∈ F 2 and optimum g 2 . Thus, our setting has model heterogeneity (different kernel functions u 1 and u 2 ) and data heterogeneity (D 1 and D 2 are not i.i.d.). Given that the setting is symmetric between agents 1 and 2, we can focus solely on error in terms of agent 1's objective (5) without loss of generality.
Proposition I can be used to derive a closed form form for function g 1 minimizing objective (5). However, computing this requires access to the datasets of both agents. Instead, we ask "can we design an iterative federated learning algorithm which can approximate g 1 "?

ALTERNATING KNOWLEDGE DISTILLATION
In this section, we describe a popular iterative knowledge distillation algorithm and analyze its updates in our framework. Our analysis leads to some surprising connections between KD and projection onto convex sets, and shows some limitations of the current algorithm.
Algorithm. Denote the data on agent 1 as D 1 = (X 1 , y 1 ) where X 1 [i, :] = x 1 n and y 1 [i] = y 1 i . Correspondingly, we have D 2 = (X 2 , y 2 ). Now starting fromŷ 1 0 = y 1 , in each rounds t and t + 1: a. Agent 1 trains their model on dataset (X 1 ,ŷ 1 t ) to obtain g 1 t . b. Agent 2 receives g 1 t and uses it to predict labelsŷ 2 t+1 = g 1 t (X 2 ). c. Agent 2 trains their model on dataset (X 2 ,ŷ 2 t+1 ) to obtain g 1 t+1 . d. Agent 1 receives a model g 1 t+1 from agent 2 and predictsŷ 1 t+2 = g 1 t+1 (X 1 ). Thus the algorithm alternates between training and knowledge distillation on each of the two agents. We also summarize the algorithm in Figure 1a. Importantly, note that there is no exchange of raw data but only of the trained models. Further, each agent trains their choice of a model on their data with agent 1 training {g 1 t } and agent 2 training {g 1 t+1 }. Superscript 1 means we start AKD from agent 1.

THEORETICAL ANALYSIS
Similar to (3), let us define functions k 1 (x, x ) and k 2 (x, x ) such that they satisfy For such functions, we can then define the following positive definite matrix L ∈ R (N1+N2)×(N1+N2) : Note L is symmetric (with L 12 = L 21 ) and is also positive definite. Further, each component L a,b measures pairwise similarities between inputs of agent a and agent b using the kernel k 1 . Correspondingly, we define M ∈ R (N1+N2)×(N1+N2) which uses kernel k 2 : We can now derive the closed form of the AKD algorithm repeatedly using Proposition I. Proposition II. The model in round 2t learned by the alternating knowledge distillation algorithm is First, note that if agents 1 and 2 are identical with the same data and same model, we have M 12 = M 22 = L 11 = L 12 . This setting corresponds to self-distillation where the model is repeatedly retrained on its own predictions. Proposition II shows that after 2t rounds of self-distillation, we obtain a model is of the form g 1 2t (x) = l x (cI + L 11 ) −1 L 11 (cI + L 11 ) −1 2t y. Here, the effect of c is amplified as t increases. Thus, this shows that repeated self-distillation induces a strong regularization effect, recovering the results of (Mobahi et al., 2020).
Perhaps more strikingly, Proposition II shows that not only does AKD fail to converge to the actual optimal solution g 1 as defined in (5), it will also slowly degrade and eventually converges to 0. We next expand upon this and explain this phenomenon.

DEGRADATION AND CONNECTION TO PROJECTIONS
While mathematically, Proposition II completely describes the AKD algorithm, it does not provide much intuition. In this section, we rephrase the result in terms of projections and contractions which provides a more visual understanding of the method.
Oblique projections. A projection operator P linearly maps (projects) all inputs onto some linear subspace A = Range(A). In general, we can always rewrite such a projection operation as Here, A defines an orthonormal basis of the space A and W is a positive definite weight matrix which defines the geometry x, y W := x W y. When W = I, we recover the familiar orthogonal projection. Otherwise, projections can happen 'obliquely' following the geometry defined by W .

Contractions.
A contraction is a linear operator C which contracts all inputs towards the origin: Cx ≤ x for any x .
Given these notions, we can rewrite Proposition II as follows. Proposition III. There exist oblique projection operators P 1 and P 2 , contraction matrices C 1 and C 2 , and orthonormal matrices V 1 and V 2 such that the model in round 2t learned by the alternating knowledge distillation algorithm is In particular, the predictions on agent 2's inputs are Further, the projection matrices satisfy P 1 P 2 x = x only if x = 0 .
The term C 1 P 2 C 2 P 1 t is the only one which depends on t and so captures the dynamics of the algorithm. Two rounds of AKD (first to agent 1 and then back to 2) correspond to a multiplication with C 1 P 2 C 2 P 1 i.e. alternating projections interspersed by contractions. Thus, the dynamics of AKD is exactly the same as that of alternating projections interspersed by contractions. The projections P 1 and P 2 have orthogonal ranges whose intersection only contains the origin 0. As Fig. 1b shows, non-orthogonal alternating projections between orthogonal spaces converge to the origin. Contractions further pull the inputs closer to the origin, speeding up the convergence. Remark 1. To understand the connection to projection more intuitively, suppose that we had a 4-way classification task with agent 1 having data only of the first two classes, and agent 2 with the last two classes. Any model trained by agent 1 will only learn about the first two classes and its predictions on the last two classes will be meaningless. Thus, no information can be transferred between the agents in this setting. More generally, the transfer of knowledge from agent 1 to agent 2 is mediated by its data X 2 . This corresponds to a projection of the knowledge of agent 1 onto the data of agent 2. If there is a mismatch between the two, knowledge is bound to be lost.

Train Train 2 rounds
(a) Alternating KD starting from agent 1. We predict and train using predictions, alternating between the two agents. (b) Intuition behind ensemble scheme. In each round, AKD alternates between overfitting the data of agent 1 or of agent 2. We can construct an ensemble out of these models to correct for this bias and quickly converge to the true optima.
Speed of degradation. The alternating projection algorithm converges to the intersection of the subspaces corresponding to the projection operators (their range) (Boyd & Dattorro, 2003). In our particular case, the fixed point of P 1 and P 2 is 0, and hence this is the point the algorithm will converge to. The contraction operations C 1 and C 2 only speed up the convergence to the origin 0 (also see Fig. 1b). This explains the degradation process notes in Proposition II. We can go further and examine the rate of degradation using known analyses of alternating projections (Aronszajn, 1950). Proposition IV (Informal). The rate of convergence to g 1 t (x) to 0 gets faster if: • a stronger inductive bias is induced via a larger regularization constant c, • the kernels k 1 (x, y) and k 2 (x, y) are very different, or • the difference between the datasets D 1 and D 2 as measured by k 1 (x, y) increases.
In summary, both data and model heterogeneity may speed up the degradation defeating the purpose of model agnostic FL. All formal proofs and theorem statements are moved to the Appendix.

ADDITIONAL VARIANTS
In the previous section, we saw that the alternating knowledge distillation (AKD) algorithm over multiple iterations suffered slow degradation, eventually losing all information about the training data. In this section, we explore some alternative approaches which attempt to correct this. We first analyze a simple way to re-inject the training data after every KD iteration which we call averaged distillation. Then, we show an ensemble algorithm that can recover the optimal model g 1 .

AVERAGED KNOWLEDGE DISTILLATION
As we saw earlier, each step of knowledge distillation seems to lose some information about the training data, replacing it with the inductive bias of the model. One approach to counter this slow loss of information is to recombine it with the original training data labels such as is commonly done in co-distillation (Sodhani et al., 2020).
b. Agents exchange their models g 1 t and g 2 t between each other. c. Agents use exchanged models to predict labelsŷ 1 t+1 = The summary the algorithm is depicted in Figure 2a. Again, notice that there is no exchange of raw data but only of the trained models. The main difference between AKD and AvgKD (averaged knowledge distillation) is that we average the predictions with the original labels. This re-injects information y 1 and y 2 at every iteration, preventing degradation. We theoretically characterize its dynamics next in terms of the afore-mentioned contraction and projection operators. Proposition V. There exist oblique projection operators P 1 and P 2 , contraction matrices C 1 and C 2 , and orthonormal matrices V 1 and V 2 such that the model of agent 1 in round t learned by the averaged knowledge distillation (AvgKD) algorithm is where F = l x (cI + L 11 ) −1 V 1 . Further, in the limit of rounds for any fixed x we have This shows that the model learned through AvgKD does not degrade to 0, unlike AKD. Instead, it converges to a limit for which we can derive closed-form expressions. Unfortunately, this limit model is still not the same as our desired optimal model g 1 . We next try to overcome this using ensembling.

ENSEMBLED KNOWLEDGE DISTILLATION
We first analyze how the limit solution of AvgKD differs from the actual optimum g 1 . We will build upon this understanding to construct an ensemble that approximates g 1 . For simplicity, we assume that the regularization coefficient c = 0.
Understanding AvgKD. Consider AvgKD algorithm, then Proposition VI. There exist matrices A 1 and A 2 such that the minimizer g 1 of objective (5) predicts In contrast, for the same matrices A 1 and A 2 , the limit models of AvgKD predict g 1 By comparing the equations (7) and (8), the output 2(g 1 ) is close to the output of g 1 (x), except that the off-diagonal matrices are scaled by 1 2 and we have −y 2 on the right hand side. We need two tricks if we want to approximate g 1 : first we need an ensemble using differences of models, and second we need to additionally correct for the bias in the algorithm.
Correcting bias using infinite ensembles. Consider the initial AKD (alternating knowledge distillation) algorithm illustrated in the Fig. 1a. Let us run two simultaneous runs, ones starting from agent 1 and another starting from agent 2, outputting models {g 1 t }, and {g 2 t } respectively. Then, instead of just using the final models, we construct the following infinite ensemble. For an input x, we output: That is, we take the models from odd steps t with positive signs and from even ones with negative signs and sum their predictions. We call this scheme Ensembled Knowledge Distillation (EKD). The intuition behind our ensemble method is schematically visualized in 1-dimensional case in the Fig.  2b where numbers denote the t variable in the equation (9). We start from the sum of both agents models obtained after learning from ground truth labels (0-th round). Then we subtract the sum of  Figure 3: AKD, AvgKD, and EKD methods for linear regression on synthetic data with same data (left), different data (middle), and strong regularization (right). EKD (black) eventually matches centralized performance (dashed green), whereas AvgKD (solid blue) is worse than only local training (dashed blue and red). AKD (in solid red) performs the worst and degrades with increasing rounds.
both agents models obtained after the first round of KD. Then we add the sum of both agents models obtained after the second round of KD and so on. From the section 4.2 we know that in the AKD process with regularization model gradually degrades towards 0, in other words, intuitively each next round obtained model adds less value to the whole sum in the EKD scheme. Although, in the lack of regularization models degradation towards 0 is not always the case (see App. C). But under such an assumption we we gradually converge to the limit model, which is the point ∞ in the Fig. 2b. We formalize this and prove the following.
Thus, not only did we succeed in preventing degeneracy to 0, but we also managed to recover the predictions of the optimal model. However, note that this comes at a cost of an infinite ensemble. While we can approximate this using just a finite set of models (as we explore experimentally next), this still does not recover a single model which matches g 1 . The toy experiments solve a linear regression problem of the form Ax = b. The data A and b is split between the two agents randomly in the 'same data' case, whereas in the 'different data' case the data is sorted according to b before splitting to maximize heterogeneity.
The real world experiments are conducted using Convolutional Neural Network (CNN), Multi-Layer Perceptron network (MLP), and Random Forest (RF). We use squared loss since it is closer to the theoretical setting. In the 'same model' setting both agents use the CNN model, whereas agent 2 instead uses an MLP in the 'different model' setting. Further, we split the training data randomly in the 'same data' setting. For the 'different data' setting, we split the data by labels and take some portion Alpha of data from each agent and randomly shuffle taken points between agents. By varying hyperparameter Alpha we control the level of data heterogeneity between agents. Notice that if Alpha = 0 then datasets are completely different between agents, if Alpha = 1 then we have the 'same data' setting with i.i.d. split of data between two agents. All other details are presented in the Appendix A. We next summarize and discuss our results.

RESULTS AND DISCUSSION
AvgKD > AKD. In all settings (both synthetic in Fig. 3 and real world in Fig. 4), we see that with the increasing number of rounds the performance of AKD significantly degrades whereas that of AvgKD stabilizes (Fig. 5) regardless of regularization, model and data heterogeneity. Moreover, from the experiments on MNIST in Fig. 4, we see the following: AKD degrades faster if there is regularization used, model heterogeneity or data heterogeneity between agents, and the last plays the most significant role. AvgKD, on the other hand, quickly converges in a few rounds and does not degrade. However, it fails to match the centralized accuracy as well. Test Acc. of agents in AKD Figure 4: Test accuracy of centralized (dashed green), and AKD on MNIST using model starting from agent 1 (blue) and agent 2 (red) with varying amount of regularization, model heterogeneity, and data heterogeneity. In all cases, performance degrades with increasing rounds with degradation speeding up with the increase in regularization, model heterogeneity, or data heterogeneity. Test Acc. of agents in AvgKD Figure 5: Test accuracy of AvgKD on MNIST using model starting from agent 1 (blue) and agent 2 (red) with varying model heterogeneity, and data heterogeneity. During training regularization is used. In all cases, there is no degradation of performance, though the best accuracy is obtained by agent 1 in round 1 with only local training. Test Acc Figure 6: Test accuracy on MNIST with varying data heterogeneity in the setting of 'same model'. In case of high data heterogeneity (small Alphas), both agents benefit from the AvgKD, PKD and EKD schemes. Moreover, AvgKD and EKD consistently outperform FedAvg scheme.
EKD works but needs large ensembles. In the synthetic setting (Fig. 3), in 250 rounds (ensemble of 500 models) it even matches the centralized model. However, in the real world setting (Fig. 6) the improvement is slower and it does not match centralized performance. This might be due to the small number of rounds run (only 20). EKD is also the only method that improves with subsequent rounds. Finally, we observed that increasing regularization actually speeds up the convergence of EKD in the synthetic setting (Fig. 3).
Data heterogeneity is the main bottleneck. In all our experiments, both data and model heterogeneity degraded the performance of AKD, PKD (Parallel KD introduced in App. E) and AvgKD. However, data heterogeneity has a much stronger effect. This confirms our theory that mismatch between agents data leads to loss of information when using knowledge distillation. Overcoming this data heterogeneity is the crucial challenge for practical model agnostic FL. Fig. 6 shows how all schemes behave in dependence on data heterogeneity. Indeed, the higher data heterogeneity the faster speed of degradation for the AKD and PKD schemes. In the case of the AvgKD scheme, we see that agents do improve over their local models and this improvement is larger with more data heterogeneity.

ADDITIONAL EXTENSIONS AND EXPERIMENTS
In App. G, we extend our algorithms to M agents and show experimentally in App. H.5 for AvgKD algorithm that the same trends hold there as well. Our conclusions also hold for the cross-entropy loss (Figs. 11,12), for highly heterogeneous model case with MLP and Random Forests (Figs. 13,14), as well on other datasets and models (VGG on CIFAR10 in Figs. 9, 10). In the latter, we see the same trends as on MNIST for all the schemes except EKD which is probably due to the use of cross-entropy loss function and, as a result, models being further from the kernel regime. Moreover, speed of degradation is higher if there is the model heterogeneity (Figs. 8, 10) and EKD does not help even on MNIST dataset (Fig. 8). Finally, all the schemes are compared to the more standard FedAvg that is not applicable in the 'different model' setting and is outperformed by the AvgKD scheme at highly data heterogeneous regimes. That is, AvgKD consistently outperforms all the methods at highly data heterogeneous regimes indicating it is the most promising variant.

CONCLUSION
While the stochastic optimization framework has been very useful in analyzing and developing new algorithms for federated learning so far, it fundamentally cannot capture learning with different models. We instead introduced the federated kernel regression framework where we formalized notions of both model and data heterogeneity. Using this, we analyzed different knowledge distillation schemes and came to the conclusion that data heterogeneity poses a fundamental challenge limiting the knowledge that can be transmitted. Further, these theoretical predictions were exactly reflected in our deep learning experiments as well. Overcoming this data heterogeneity will be crucial to making KD based model agnostic federated algorithms practical.
We also utilized our framework to design a novel ensembling method motivated by our theory. However, this method could require very large ensembles (up to 500 models) in order to match the centralized performance. Thus, we view our method not as a practical algorithm, but more of a demo on how our framework can be leveraged. Similarly, our experiments are preliminary and are not on real world complex datasets. We believe there is great potential in further exploring our results and framework, especially in investigating how to mitigate the effect of data heterogeneity in knowledge distillation.

A EXPERIMENTS DETAILS
In all real world experiments we use the Adam optimizer with a default regularization (weight decay) of 3 × 10 −4 , unless in the 'no regularization' case when it is set to 0. We split the data between 2 agents by giving a bigger part of data to agent 1 at all 'same data' experiments. That is, for 'different data' experiments and heterogeneous data experiments where we vary Alpha hyperparameter we split data equally between 2 agents. The non-equal split can help us to see another effect in the experiments: if agent 2 (with less data) benefits from the communication with agent 1 (with more data). In heterogeneous data experiments, we explore the significance of data heterogeneity effect on the behavior of KD scheme. That is why we design an almost ideal setting at all such experiments: the 'same model' setting (except experiments with RF and MLP), the equal split of data in terms of its amount between agents.
Toy experiments. The toy experiments solve a linear regression problem of the form Ax = b where A ∈ R n×d and x ∈ R d is randomly generated for n = 1.5d and d = 100. Then, the data A and b is split between the two agents at proportion 0.6/0.4. This is done randomly in the 'same data' case, whereas in the 'different data' case the data is sorted according to b before splitting to maximize heterogeneity. This experiment with the linear kernel is supposed to show if our theory is correct, especially if the EKD scheme really works.
Real world experiments. The real world experiments are conducted using CNN and MLP networks on MNIST, MLP network and RF model on MNIST, and VGG16 1 (Simonyan & Zisserman, 2015) and CNN models on CIFAR10 datasets. Further, we split the training data randomly at proportion 0.7/0.3 in the 'same data' setting. For the 'different data' setting, we split the data by labels: agent 1 has '0' to '4' labeled data points, agent 2 has '5' to '9'. Then we take randomly from each agent some Alpha = 0.1 portion of data, combine it and randomly return data points to both agents from this combined dataset.

B ALTERNATING KD WITH REGULARIZATION
Different models. Keeping the notation of section 4 we can construct the following matrix: Notice that each of the sub-blocks L and M are symmetric positive semi-definite matrices. This makes matrix K symmetric positive semi-definite matrix and it has eigendecomposition form: where D and V are R 2(N1+N2)×2(N1+N2) diagonal and orthogonal matrices correspondingly. This means that the R 2(N1+N2)×2(N1+N2) matrices V 1 , V 2 ,Ṽ 1 ,Ṽ 2 are also orthogonal to each other. Then one can deduce: In AKD setting only agent 1 has labeled data. The solution of learning from the dataset D 1 evaluated at set X 2 is the following: Let us introduce notation: . These are well known oblique (weighted) projection matrices on the subspaces spanned by the columns of matrices V 1 andṼ 2 correspondingly, where the scalar product is defined with Gram matrix G = cI + D. Similarly one can define P 2 andP 1 .
Given the introduced notation and using the fact that V 2 V 1 = 0, we can rewrite equation 10 as: Similarly, given X 1 ⊆ D 1 and agent 1 learned fromŶ 2 = g 1 0 (X 2 ), inferred predictionŶ 1 = g 1 1 (X 1 ) by agent 2 can be written as: At this point we need to introduce additional notation: These are matrices of contraction linear mappings.
One can now repeat the whole process again with replacement Y 1 byŶ 1 . The predictions by agent 1 and agent 2 after such 2t rounds of AKD are: If one considers the case where agents have the same kernel u 1 = u 2 = u then one should 'remove all tildas' in the above expressions and the obtained expressions are applied. This means M = L, V 1 =Ṽ 1 and V 2 =Ṽ 2 . Crucial changes in this case are C 1 =C 2 → I and C 1P 2C2 P 1 t → P 2 P 1 t . The matrix P 2 P 1 t is an alternating projection (Boyd & Dattorro, 2003) operator after t steps. Given 2 closed convex sets, alternating projection algorithm in the limit finds a point in the intersection of these sets, provided they intersect (Boyd & Dattorro, 2003;Lewis et al., 2007). In our case matrices operators P 1 and P 2 project onto linear spaces spanned by columns of matrices V 1 and V 2 correspondingly. These are orthogonal linear subspaces, hence the unique point of their intersection is the origin point 0. This means that P 2 P 1 t −−−→ t→∞ 0 and in the limit of such AKD procedure both agents predict 0 for any data point.
Speed of degradation. The speed of convergence for the alternating projections algorithm is known and defined by the minimal angle φ between corresponding sets (Aronszajn, 1950) (only non-zero elements from sets one has to consider): where v is one of the columns of matrix V 1 . In our case we can write the expression for the cosine: where v 1 and v 2 are the vectors from subspaces spanned by columns of matrices V 1 and V 2 correspondingly. Hence the speed of convergence depends on the elements of the matrix L 12 . Intuitively these elements play the role of the measure of 'closeness' between data points. This means that the 'closer' points of sets X 1 and X 2 the higher absolute values of elements in matrix L 12 . Moreover, we see inversely proportional dependence on the regularization constant c. All these sums up in the following proposition which is the formal version of the proposition IV: Proposition VIII (Formal). The rate of convergence of g 1 t (x) to 0 gets faster if: • larger regularization constant c is used during the training, • smaller the eigenvalues of the matrix V 1Ṽ 1 , or • smaller absolute value of non-diagonal block L 12

C ALTERNATING KD WITHOUT REGULARIZATION
Before we saw that models of both agents degrade if one uses regularization. A natural question to ask if models will degrade in the lack of regularization. Consider the problem (1) with c → 0, so the regularization term cancels out. In the general case, there are many possible solutions as kernel matrix K may have 0 eigenvalues. Motivated by the fact that Stochastic Gradient Descent (SGD) tends to find the solution with minimal norm (Wilson et al., 2017), we propose to analyze the minimal norm solution in the problem of alternating knowledge distillation with 2 agents each with private dataset. For simplicity let us assume that agents have the same model architecture. Then the agent I solution evaluated at set X 2 with all the above notation can be written as: where † stands for pseudoinverse. In this section let us consider 3 possible settings one can have: 1. Self-distillation: The datasets and models of both agents are the same. 2. Distillation with K > 0: The datasets of both agents are different and private. Kernel matrix K is positive definite.
3. Distillation with K ≥ 0: The datasets of both agents are different and private. Kernel matrix K is positive semi-definite.
Self-distillation. Given the dataset D = X × Y, the solution of the supervised learning with evaluation at any x ∈ R d is: Then the expression for the self-distillation step with evaluation at any x ∈ R d is: where property of pseudoinverse matrix was used: That is, self-distillation round does not change obtained model. One can repeat self-distillation step t times and there is no change in the model: Hence in the no regularization setting self-distillation step does not give any change in the obtained model.
Distillation with K > 0. In this setting we have the following identity K † = K −1 and results are quite similar to the setting with regularization. But now the Gram matrix of scalar product in linear space is D instead of cI + D in the regularized setting. By assumption on matrix K it follows that D is of full rank and the alternating projection algorithm converges to the origin point 0. Therefore in the limit of AKD steps predictions by models of two agents will degrade towards 0.
Distillation with K ≥ 0. In this setting kernel matrix K has at least one 0 eigenvalue and we take for the analysis the minimal norm solution (13). We can rewrite this solution: One can notice the following projection properties of matrixP 1 : That is,P 1 is a projection matrix with eigenspace spanned by columns of the matrix V 1 (V 1 DV 1 ) † . Similarly, one can defineP 2 . Then the solution for the first AKD step evaluated at set X 1 is: and after t rounds we obtain for agent I and agent II correspondingly: g 2t (X 2 ) = V 2P 1 (P 2P 1 ) t z 1 and g 2t+1 (X 1 ) = V 1 (P 2P 1 ) t+1 z 1 .
In the limit of the distillation rounds operator (P 2P1 ) t tends to the projection on the intersection of 2 subspaces spanned by the columns of matrices V 1 (V 1 DV 1 ) † and V 2 (V 2 DV 2 ) † . We should 0 (a) Illustrative projection 3D Train Train 1 round (b) PKD scheme highlight that in general, the intersection set in this case consists not only from the origin point 0 but some rays that lie simultaneously in the eigenspaces of both projectorsP 1 andP 2 . The illustrative example is shown in the Fig. 7a. We perform the alternating projection algorithm between orthogonal linear spaces that have a ray in the intersection and we converge to some non-zero point that belongs to this ray. The intersection of eigenspaces of both projectorsP 1 andP 2 is the set of points
The illustration of this process is presented in the Fig. 2a.
Consider the sequence of solutions for the agent 1 with evaluation at X 2 : • Supervised Learning: g 1 0 (X 2 ) = V 2 P 1 z 1 • 1st round of KD: • 2nd round of KD: • 3rd round of KD: • t-th round of KD: • The limit of KD steps: where † stands for pseudoinverse.
Let us analyze the limit solution and consider the first term of its expression. One can deduce the following identity: 2 In a similar manner, we can deal with the second term: Now, we notice Schur complement expression in the equation (18): This means that we can consider the following problem: and derive that g 1 ∞ (X 2 ) = V 2 DV1 2 β 1 and g 2 ∞ (X 1 ) = −Ṽ 1 DṼ2 2 β 2 , where β 1 , β 2 are defined as the solution to the problem (19). Given this, we can derive the following: As one can see, there is a strong relation between the limit KD solutions and the solution of a linear system of equations with modified matrix K and right-hand side. Mainly, we take the kernel matrix and divide its non-diagonal blocks by 2, which intuitively shows that our final model accounts for the reduction of the 'closeness' between datasets D 1 and D 2 . And on the right-hand side, we see −y 2 instead of y 2 which is quite a 'artificial' effect. Overall these results in the fact that both limit solutions (for each agent) do not give a ground truth prediction for X 1 and X 2 individually, which one can see from equation (20) with c = 0. That is, we need combine the predictions of both agents in a specific way to get ground truth labels for datasets D 1 and D 2 . Moreover, the way we combine the solutions differs between datasets D 1 and D 2 that one can see from comparison of right-hand sides of expressions (20) and (21). Given all the above, to predict optimal labels we need to change we way we combine models of agents in dependence on a dataset, but an usual desire is to have one model that predicts ground truth labels for at least both training datasets.
To obtain the expressions for the case of identical models one should 'remove all tildas' in the above expressions and by setting V 1 =Ṽ 1 , V 2 =Ṽ 2 , C 1 =C 2 → I and (C 1P 2C2 P 1 ) t → (P 2 P 1 ) t

E PARALLEL KD
In this section, we theoretically analyze a slight modification of the AvgKD algorithm which we call Parallel KD (PKD). Keeping the notation of sections B and C, denote the data on agent 1 as D 1 = (X 1 , y 1 ) where X 1 [i, :] = x 1 n and y 1 [i] = y 1 i . Correspondingly, for agent 2 we have D 2 = (X 2 , y 2 ). Now starting fromŷ 1 0 = y 1 ,ŷ 2 0 = y 2 , in each round t ≥ 0: a. Agents 1 and 2 train their model on datasets (X 1 ,ŷ 1 t ) and (X 2 ,ŷ 2 t ) to obtain g 1 t and g 2 t . b. Agents exchange g 1 t and g 2 t between each other. c. Agents use exchanged models to predict labelsŷ 1 t+1 =ŷ The summary of the algorithm is depicted in Figure 7b. That is, we learn from the average of 2 agents' predictions. For simplicity, we are going to analyze the scheme without regularization and we take always a minimum norm solution. Notice that there is no exchange of raw data but only of the trained models.
Let us analyse KD algorithm where solutions for agent I (g 1 ) and agent II (g 2 ) obtained as: where Consider g 1 t for t ≥ 1: The form of the solutions reminds the method of averaged projection (Lewis et al., 2007) with operatorP 1 +P 2 , which is similar to alternating projection converges to the intersection point of 2 subspaces 3 . That is, similarly to AKD in the case with the regularization we expect the solution to converge to the origin point 0 in the limit of the distillation steps. As a result, after some point, one expects steady degradation of the predictions of both agents in the PKD scheme.
One can find β 1 , β 2 and deduce the following prediction by the model associated with the system (27) for i = 1, 2: From this one can easily deduce (28) which means that for datasets of both agents this model predicts ground truth labels. To obtain the expressions for the case of identical models one should 'remove all tildas' in all the above expressions and by setting The last question is how one can construct the scheme of iterative KD rounds to obtain the above expression for the limit model. From the form of the prediction, we conclude that one should use models obtained in the process of AKD. There are many possible schemes how one can combine these models to obtain the desired result. One of the simplest possibilities is presented in the section 5.2.

G M-AGENT SCHEMES
The natural question to ask is how one could extend the discussed schemes to the setting of M agents.
In this section, we address this question and explicitly provide the description of each algorithm for the setting of M agents.
Scalability and privacy. Before diving into particular algorithms we investigate some important concerns about our KD based framework. A naive implementation of our methods will require each agent sharing their model with all other agents. This will incur significant communication costs (M 2 ), storage costs (each agent has to store M models), and is not compatible with secure aggregation (Bonawitz et al., 2016) potentially leaking information. One potential approach to alleviating these concerns is to use an server and homomorphic encryption (Graepel et al., 2012). Homomorphic encryption allows agent 1 to compute predictions on agent 2's data f 1 (X 2 ) without learning anything about X 2 i.e. there exists a procedure Hom such that given encrypted data Enc(X 2 ), we can compute Hom(f 1 , Enc(X 2 )) = Enc(f 1 (X 2 )) .
Given access to such a primitive, we can use a dedicated server (agent 0) to whom all models f 1 , . . . , f M are sent. Let us define some weighted sum of the predictions as f α (X) : . Then, using homomorphic encryption, each agent i can compute Enc(f α (X i ))) in a private manner without leaking any information to agent 0. This makes the communication cost linear in M instead of quadratic, and also makes it more private and secure. A full fledged investigation of the scalability, privacy, and security of such an approach is left for future work. With this caveat out of the way, we next discuss some concrete algorithms.
AKD with M agents. To extend AKD scheme to a multi-agent setting and corresponding theory we need to start by understanding what the alternating projection algorithm is in the case of M convex sets. Suppose we want to find the intersection point of M affine sets C i , for i = 1, ..., M . In terms of alternating projection algorithm we can write the following extension of it (Halperin, 1962): For our algorithm, it means that agent 1 passes its model to agent 2, then agent 2 passes its model to agent 3 and so until agent M that passes its model to agent 1, and then the cycle repeats. That is, as before, we denote the data on agent 1 as D 1 = (X 1 , y 1 ) where X 1 [i, :] = x 1 n and y 1 [i] = y 1 i ., for all other agents we have D i = (X i , y i ), for i = 2, ..., M . Now starting fromŷ 1 0 = y 1 , in each rounds t, ..., t + M − 1, t ≥ 0: a. Agent 1 trains their model on dataset (X 1 ,ŷ 1 t ) to obtain g 1 t . b. for i = 2, ..., M : b.1 Agent i receives g 1 t+i−2 and uses it to predict labelsŷ i t+i−1 = g 1 t+i−2 (X i ). b.2 Agent i trains their model on dataset (X i ,ŷ i t+i−1 ) to obtain g 1 t+i−1 . c. Agent 1 receives a model g 1 t+M −1 from agent M and predictsŷ 1 t+M = g 1 t+M −1 (X 1 ). As before, there is no exchange of raw data but only of the trained models. And given all the results deduced before, all the models from some point will start to degenerate. The rate of convergence of such an algorithm is defined similarly to alternating projection in case 2 sets and can be found in Smith et al. (1977).

H.1 MNIST WITH VARYING DATA HETEROGENEITY
In this section, we present the results for MNIST dataset with varying data heterogeneity in the setting of 'different model'. The results one can see in Fig. 8. There is a faster degradation trend for both AKD and PKD schemes if different models for agents are used (Fig. 8) comparing to rhe 'same model' setting (Fig. 6) at all data heterogeneity regimes. The PKD scheme is a slight modification of the AvgKD scheme which is proven to degrade through rounds of distillation. We see the degradation trend for PKD scheme which is suggested by our theory presented in App. E. EKD does not improve with subsequent rounds in the setting of 'different models'. AvgKD scheme outperforms both PKD and AKD in all settings. However, its convergence is not stable in extremely high heterogeneous settings, showing large oscillations. Investigating and mitigating this could be interesting future work. In this section, we present the results for CIFAR10 dataset with varying data heterogeneity. Note that we use cross-entropy loss function here. The results one can see in Fig. 9 and 10 that again show data heterogeneity plays key role in the behavior of all the schemes. All the trends we saw on the MNIST dataset are repeated here except one: EKD does not improve in subsequent rounds in the 'same model' setting.  Figure 9: Test accuracy of on CIFAR10 with varying data heterogeneity in the setting of 'same model'. As on MNIST: performance of PKD and AKD degrade with degradation speeding up with the increase in data heterogeneity; performance of AvgKD scheme converges to steady behavior; both agents benefit from AvgKD, PKD and EKD schemes in early rounds of communication.

H.3 CROSS-ENTROPY OBJECTIVE
In this section, we present the results of experiments on MNIST with Cross-Entropy (CE) loss for 2 main schemes under investigation: AKD and AvgKD. In Fig. 11 and 12 one can see the results of AKD and AvgKD schemes correspondingly for CE loss. The results are aligned with our theory: in  Figure 10: Test accuracy of on CIFAR10 with varying data heterogeneity in the setting of 'different model'. All the schemes behave similarly to the 'same model' setting. Fig. 11 we see the degradation trend for AKD which is dependent on the amount of the regularization, model and data heterogeneity. In Fig. 12 we see steady behavior of AvgKD scheme for both agents models: there is no degradation even if model and data are different. Test Max Acc. of agents in AKD Figure 11: Test accuracy of AKD on MNIST using CE loss and model starting from agent 1 (blue) and agent 2 (red) with varying amount of regularization, model heterogeneity, and data heterogeneity. In all cases, performance degrades with increasing rounds with degradation speeding up with the increase in regularization, model heterogeneity, or data heterogeneity. Test Max Acc. of agents in AvgKD Figure 12: Test accuracy of AvgKD on MNIST using CE loss and model starting from agent 1 (blue) and agent 2 (red) with varying model heterogeneity, and data heterogeneity. In all cases, there is no degradation of performance, though the best accuracy is obtained by agent 1 in round 1 with only local training.

H.4 COLLABORATION BETWEEN MLPS AND RANDOM FORESTS
In this section, we present the results for MNIST dataset for Random Forests (RF) and MLP models with MSE loss. That is, the experiments are in the setting 'different model', where agent 1 has MLP model and agent 2 has RF model. These experiments can show how AKD and AvgKD schemes behave in the setting of fundamentally different models. In the Figs. 13 and 14 the results for accuracy are presented. We see the alignment of these results with theory and other experiments with deep learning models. Mainly, there is a degradation trend for AKD scheme which is speeding up with the increase in data heterogeneity, there is no degradation for AvgKD scheme, and the performance of both agents in AvgKD scheme is highly dependent on data heterogeneity. Test Acc. of agents Figure 13: Test accuracy of AKD and AvgKD on MNIST using models MLP (blue) and RF (red) with varying data heterogeneity. For AKD performance degrades with increasing rounds. Degradation is speeding up with the increase in data heterogeneity. For AvgKD there is no degradation of performance. Test Acc. of agents in AvgKD Figure 14: Test accuracy of AvgKD on MNIST using models MLP (blue) and RF (red) with varying data heterogeneity. The increase in data heterogeneity lowers the performance of both agents without degradation trend through rounds.

H.5 AVGKD WITH M AGENTS
The AvgKD scheme does not degrade in comparison with AKD and PKD schemes that degrade already in the case of 2 agents. In this section, we present the results of the AvgKD scheme with M agents and use 5 agents on the MNIST dataset in the setting of the 'same model' with varying data heterogeneity. In case of full data heterogeneity (Alpha = 0) we assign the labels (2(i − 1), 2i − 1) to the actor number i, for i = 1...5. The results are presented in the Fig. 15. We see that all the agents repeat the behavior pattern in all cases of data heterogeneity. In cases of Alpha < 0.05 (high data heterogeneity) early stopping is beneficial.