#  Robust and Communication-Efficient Federated Domain Adaptation via Random
Features

Zhanbo Feng1  Yuanjie Wang1  Jie Li  Fan Yang  Jiong Lou,
Tiebin Mi  Robert. C. Qiu  Zhenyu Liao2  Z. Feng J. Li, F. Yang, and J. Lou
are with the Department of Computer Science and Engineering (CSE), Shanghai
Jiao Tong University, Shanghai, China. Y. Wang, R. C. Qiu, T. Mi, and Z. Liao
are with the School of Electronic Information and Communications (EIC),
Huazhong University of Science and Technology (HUST), Wuhan, China. Manuscript
received xxxx, 2023; revised xxxx, 2023.

###### Abstract

Modern machine learning (ML) models have grown to a scale where training them
on a single machine becomes impractical. As a result, there is a growing trend
to leverage federated learning (FL) techniques to train large ML models in a
distributed and collaborative manner. These models, however, when deployed on
new devices, might struggle to generalize well due to domain shifts. In this
context, federated domain adaptation (FDA) emerges as a powerful approach to
address this challenge.

Most existing FDA approaches typically focus on aligning the distributions
between source and target domains by minimizing their (e.g., MMD) distance.
Such strategies, however, inevitably introduce high communication overheads
and can be highly sensitive to network reliability.

In this paper, we introduce RF-TCA, an enhancement to the standard Transfer
Component Analysis approach that significantly accelerates computation without
compromising theoretical and empirical performance. Leveraging the
computational advantage of RF-TCA, we further extend it to FDA setting with
FedRF-TCA. The proposed FedRF-TCA protocol boasts communication complexity
that is _independent_ of the sample size, while maintaining performance that
is either comparable to or even surpasses state-of-the-art FDA methods. We
present extensive experiments to showcase the superior performance and
robustness (to network condition) of FedRF-TCA.

###### Index Terms:

Random features, maximum mean discrepancy, kernel method, federated domain
adaptation

##  I Introduction

$*$$*$footnotetext: Equal contribution.$\dagger$$\dagger$footnotetext: Z. Liao
is the corresponding author (email: zhenyu_liao@hust.edu.cn).

In today’s context, marked by the unprecedented growth of machine learning
(ML) and artificial intelligence (AI), increasingly larger ML models [1, 2]
are being trained to address challenges across various fields, ranging from
game [3, 4], text-to-image synthesis [5], natural language processing [1, 6],
to robotics [7] and intelligent decision-making [8]. The training of such
colossal models is generally _impossible_ on a single machine. In this
respect, federated learning (FL) [9, 10] techniques come into play,
accelerating collaboration among different machines in training massive ML
models while safeguarding data privacy across the network of participating
distributed devices. Recent improvements have been focusing on on-device FL,
which involves interactions within the network of distributed clients. In this
context, optimizing the communication costs across the network of distributed
devices, “aligning” the (possibly very heterogeneous) datasets on local
devices, and establishing reliable and efficient models are the major issues
to address.

Models trained using FL techniques, however, may _fail_ to generalize on a new
device due to _domain shift_ , in which case the distribution of the target
(unlabeled) data significantly differs from that of the labeled data collected
at source clients. Unsupervised domain adaptation (DA) [11], in this respect,
allows for knowledge transferring from labeled source domains to unlabeled
target domain, by aligning (in an unsupervised manner say) their feature
distributions.

In this paper, we focus on the federated domain adaptation (FDA) approach to
tackle the issue of domain shift in FL by minimizing their (e.g., maximum mean
discrepancy, MMD [12, 13]) distance through alternate information exchanges
between devices. These information exchanges, crucial to the performance of
FDA methods, typically result in high communication overheads during the
training procedure, see [14, 15, 16]. Moreover, in practical scenarios where
the network of distributed machines is not always reliable – potentially
experiencing message drops and/or limited client availability (e.g., clients
being temporarily unavailable and even dropping out during training) [17, 18]
– existing FDA approaches suffer from severe performance degradation. In light
of this, an asynchronous training scheme that is robust against (possibly
limited) network reliability, without a significant sacrifice in performance
and training time, is highly desirable in FDA.

Figure 1: Illustration of the proposed FedRF-TCA protocol composed of (i)
Feature Extractor with both fixed and learnable weights, denoted
${\mathbf{G}}_{S}$ and ${\mathbf{G}}_{T}$, respectively, obtained by fine-
tuning a pretrained model (like ResNet-50); (ii) RF-TCA Transfer Module using
random features technique (see 1 below) and a linear adaptive layer
(${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(i)}$ or
${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$), with compressed features of the
form $\boldsymbol{\Sigma}_{i}{\boldsymbol{\ell}}_{i}$ exchanged among clients
during training; and (iii) Classifier. Solid arrows for local training and
dashed arrows for global parameter aggregation between clients. See Section IV
for a detailed discussion.

###  I-A Our Approach and Contribution

In this paper, we propose a robust and communication-efficient FDA approach
called Federated Random Features-based Transfer Component Analysis (FedRF-
TCA), as depicted in Figure 1. Aiming to minimize the communication overhead
in training an FDA model, FedRF-TCA extends the random features approximation
technique [19] to the Transfer Component Analysis (TCA) [20] transfer learning
scheme. This extension allows us to obtain compact source and target features
with minimal MMD distance. From an FL perspective, the FedRF-TCA protocol is
carefully designed so that only a _minimal_ amount of _important_ information
is exchanged between clients in the network, in a highly compressed (and thus
secure) fashion. In a multi-source scenario, federated averaging (FedAvg)
technique [10] is employed to train a shared classifier using data from
different source domains. This classifier is then applied on target features.

The primary contributions of this paper are as follows:

  1. 1.

We propose RF-TCA, an extension to standard TCA that significantly accelerates
the vanilla TCA computations without theoretical _and_ empirical performance
degradation (see, e.g., 2 in Section III). This extension enables RF-TCA to be
applied effectively on large-scale datasets, a key challenge for vanilla TCA.

  2. 2.

We introduce FedRF-TCA, a robust and efficient FDA approach. Unlike previous
methods that suffer from high communications and/or computational costs on
large-scale tasks, FedRF-TCA, as an extension of RF-TCA, enjoys a training
communication overhead that is _independent_ of the dataset size and
additional privacy protection, see Section IV.

  3. 3.

Extensive numerical experiments on various datasets are conducted in Section V
to validate the efficiency of computation, reduced communication overhead, and
excellent robustness (to, e.g., network reliability) of FedRF-TCA.

###  I-B Notations and Organization of the Paper

We denote scalars by lowercase letters, vectors by bold lowercase, and
matrices by bold uppercase. We denote the transpose operator by $(\cdot)^{\sf
T}$, and use $\|\cdot\|_{2}$ to denote the Euclidean norm for vectors and
spectral/operator norm for matrices. For a random variable $z$,
$\mathbb{E}[z]$ denotes the expectation of $z$. We use ${\mathbf{1}}_{p}$ and
${\mathbf{I}}_{p}$ for the vector of all ones of dimension $p$ and the
identity matrix of dimension $p\times p$, respectively. For a given p.s.d.
matrix ${\mathbf{K}}$, we denote $\dim({\mathbf{K}})\equiv\operatorname{{\rm
tr}}{\mathbf{K}}/\|{\mathbf{K}}\|_{2}$ the intrinsic dimension of
${\mathbf{K}}$. We use $\Theta,O$ and $\Omega$ notations as in classical
computer science literature [21, 22].

The remainder of this paper is organized as follows. In Section II we review
prior research efforts and revisit both the TCA and FedAvg approaches.
Subsequently, in Section III, we present an extension of the original TCA
transfer learning method, termed RF-TCA, which offers substantial reductions
in both storage and computational complexity. Building upon this, in Section
IV, we further extend RF-TCA to the FL scenario and introduce the FedRF-TCA
protocol. FedRF-TCA not only ensures robust and communication-efficient
training but also provides enhanced privacy protection. To validate the
effectiveness of the proposed FedRF-TCA scheme, we present extensive
experimental results on commonly used DA datasets in Section V, demonstrating
its superior performance compared to state-of-the-art methods.

##  II Previous Efforts and Preliminaries

In this section, we provide a brief review of prior research endeavors
concerning random features approximation, transfer learning, and FL in Section
II-A. We will delve deeper into the Transfer Component Analysis (TCA) and
Federated Averaging (FedAvg) approaches, and provide comprehensive insights
into their methodologies in Section II-B and II-C, respectively.

###  II-A Review of Previous Efforts

####  II-A1 Random features and kernel method

Random features methods were first proposed to alleviate the computational and
storage challenges associated with kernel methods, particularly in scenarios
involving a large number of $n\gg 1$ data points [23, 19]. Notably, Random
Fourier Features (RFFs) are known to approximate the widely used Gaussian
kernel, if a sufficiently large $N$ number of random features are used [19,
24]. Other random feature techniques have been developed to address more
involved kernels, see [25]. For an extensive overview of these approaches,
interested readers are referred to [26], and for their intricate connections
with (deep and/or random) neural networks, we recommend exploring [27, 28,
29].

####  II-A2 Transfer learning and domain adaptation

Transfer learning, and in particular, domain adaptation, aims to “align” the
distribution of source and target data representations in a common feature
space. Different feature alignment strategies have been explored in the
literature: TCA [30] and JDA [31] propose to minimize the maximum mean
discrepancy (MMD) distance between the source and target marginal/joint
distributions. GFK [32] performs subspace feature alignment by exploiting the
intrinsic low-dimensional structures of the data. CORAL [33] proposes to align
data representations via their second-order statistics. DAN [34], DaNN [15],
and DDC [35] leverage the strong expressive power of deep neural networks to
align source and target representations in a reproducing kernel Hilbert space,
based on MMD principle [12, 13]. In contrast, DANN [36] addresses the domain
shift through adversarial learning, upon which CDAN [37] introduces
conditioning strategies to further improve the performance.

####  II-A3 Federated learning and federated domain adaptation

Federated learning (FL) is a decentralized ML paradigm that facilitates model
training on local data while preserving privacy through the sharing of model
updates across a network of devices. Notwithstanding the remarkable progress
achieved in the field of FL [9, 38, 39], the resulting trained models often
falter in generalizing to data at novel devices, primarily due to _domain
shift_ , where the feature distribution in target domain diverges from that in
the source domain. To address this challenge, federated domain adaptation
(FDA) techniques have been proposed to mitigate domain shift by aligning the
feature distributions of both source and target domains. While many FDA
methods have demonstrated considerable empirical success, they often come at
the cost of prohibitively high computational and communicational overheads
[14, 40]. To alleviate the computational and communicational challenges
inherent associated with FDA, recent work [16, 41] propose to compute MMD
distance using a less resource-intensive feature extractor, thereby
significantly reducing both computational and communicational overheads. [41]
take this optimization a step further by introducing an approximate version of
the original MMD loss, resulting in even more pronounced reductions in
communication costs.

In this work, we address the issue of domain shift challenge within FL and
introduce the FedRF-TCA protocol. The proposed FedRF-TCA approach enjoys a
much lower (in fact a data-size-_independent_) communication complexity
compared to existing FDA methods, and is, in addition, robust to network
reliability and possible malicious (source) clients, all while delivering
commendable performance.

###  II-B Maximum Mean Discrepancy Principle and Transfer Component Analysis

The maximum mean discrepancy (MMD) was first introduced as a pivotal test
statistic in the seminal works of [12, 13]. It serves as a tool to determine
whether data points are drawn i.i.d. from the same underlying distribution,
via an evaluation of their features in a reproducing kernel Hilbert space
(RKHS). It quickly gains popularity as the preferred objective function for
the purpose of “aligning” different feature distributions, from different
domains, of particular interest to DA [42]. This further gave rise to numerous
highly efficient transfer learning methods [43, 44], one noteworthy approach
among which is the Transfer Component Analysis (TCA) method [30].

TCA proposes to align the distributions of source
${\mathbf{x}}_{S}\in\mathbb{R}^{p}$ and target data
${\mathbf{x}}_{T}\in\mathbb{R}^{p}$ in some common feature space, via the
following two-step transformation (visualized in Figure 2):

  1. 1.

“lift” both the source and target data to some _predefined_ RKHS, via the
kernel feature map $\phi(\cdot)\colon\mathbb{R}^{p}\to\mathcal{H}$, to form
the kernel matrix

${\mathbf{K}}\equiv\langle\phi({\mathbf{x}}_{i}),\phi({\mathbf{x}}_{j})\rangle_{i,j=1}^{n}\in\mathbb{R}^{n\times
n},\quad n=n_{S}+n_{T},$ (1)

with $\langle\cdot,\cdot\rangle$ the inner product in $\mathcal{H}$;

  2. 2.

find, in an unsupervised manner say, a linear map
$\tilde{{\mathbf{W}}}\in\mathbb{R}^{n\times m}$ that “projects” the kernel
features of both source and target data onto a low-dimensional space
$\mathbb{R}^{m}$ (with $m\ll n$ so that they can be computed or stored much
more efficiently) according to the MMD principle, by solving the following
optimization problem:

$\displaystyle\min_{{\mathbf{W}}}$ $\displaystyle\quad
L_{\gamma}({\mathbf{W}})=\operatorname{{\rm tr}}({\mathbf{W}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\mathbf{W}})+\gamma\operatorname{{\rm tr}}({\mathbf{W}}^{\sf
T}{\mathbf{W}}),$ s.t. $\displaystyle\quad{\mathbf{W}}^{\sf
T}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}{\mathbf{W}}={\mathbf{I}}_{m},$ (TCA)

with
${\mathbf{W}}={\mathbf{K}}^{-1/2}\tilde{{\mathbf{W}}}\in\mathbb{R}^{n\times
m}$, regularization penalty $\gamma\geq 0$,
${\mathbf{H}}={\mathbf{I}}_{n}-{\mathbf{1}}_{n}{\mathbf{1}}_{n}^{\sf
T}/n\in\mathbb{R}^{n\times n}$, and ${\boldsymbol{\ell}}\in\mathbb{R}^{n}$ the
(normalized) source and target “label” vector
${\boldsymbol{\ell}}\in\mathbb{R}^{n}$ with its $i$th entry given by

$\ell_{i}=\frac{1}{n_{S}}1_{{\mathbf{x}}_{i}\in{\mathbf{X}}_{S}}-\frac{1}{n_{T}}1_{{\mathbf{x}}_{i}\in{\mathbf{X}}_{T}},$
(2)

for ${\mathbf{X}}_{S}\in\mathbb{R}^{p\times n_{S}}$ the (set of) source data
and ${\mathbf{X}}_{T}\in\mathbb{R}^{p\times n_{T}}$ the (set of) target data,
so that $\|{\boldsymbol{\ell}}\|_{2}^{2}=\frac{n}{n_{S}n_{T}}$. The solution
to (TCA) is explicitly given by ${\mathbf{W}}\in\mathbb{R}^{n\times m}$, the
$m$ top eigenvectors (that correspond to the largest $m$ eigenvalues) of
$(\gamma{\mathbf{I}}_{n}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}$ satisfying

$(\gamma{\mathbf{I}}_{n}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}\cdot{\mathbf{W}}={\mathbf{W}}\cdot\boldsymbol{\Lambda}$
(3)

with diagonal $\boldsymbol{\Lambda}=\operatorname{{\rm
diag}}\\{\lambda_{i}\\}_{i=1}^{m}$ containing the largest $m$ eigenvalues of
$(\gamma{\mathbf{I}}_{n}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}$, with the obtained
low-dimensional and “aligned” representations (of both source and target data)
given by the columns of ${\mathbf{W}}^{\sf
T}{\mathbf{K}}\in\mathbb{R}^{m\times n}$.

This two-step transformation from $\mathbb{R}^{p}$ to RKHS $\mathcal{H}$ and
then to $\mathbb{R}^{m}$ is visualized in Figure 2, where we denote
${\mathbf{X}}_{\mathbb{R}^{p}},{\mathbf{X}}_{\mathcal{H}},{\mathbf{X}}_{\mathbb{R}^{m}}$
the features in different spaces, and
${\mathbf{K}}_{\mathbb{R}^{p}},{\mathbf{K}}_{\mathcal{H}},{\mathbf{K}}_{\mathbb{R}^{m}}$
the corresponding kernel matrices, respectively.

$\mathbb{R}^{p}$${\mathbf{X}}_{\mathbb{R}^{p}}=[{\mathbf{X}}_{S},~{}{\mathbf{X}}_{T}]$
${\mathbf{K}}_{\mathbb{R}^{p}}={\mathbf{X}}_{\mathbb{R}^{p}}^{\sf
T}{\mathbf{X}}_{\mathbb{R}^{p}}$$\mathcal{H}$${\mathbf{X}}_{\mathcal{H}}=\phi({\mathbf{X}}_{\mathbb{R}^{p}})$
${\mathbf{K}}_{\mathcal{H}}={\langle\phi({\mathbf{x}}_{i}),\phi({\mathbf{x}}_{j})\rangle}^{n}_{i,j=1}$$\mathbb{R}^{m}$${\mathbf{X}}_{\mathbb{R}^{m}}=\tilde{{\mathbf{W}}}^{\sf
T}{\mathbf{K}}_{\mathcal{H}}^{1/2}$
${\mathbf{K}}_{\mathbb{R}^{m}}={\mathbf{X}}_{\mathbb{R}^{m}}^{\sf
T}{\mathbf{X}}_{\mathbb{R}^{m}}$kernel
map$\phi(\cdot)\colon\mathbb{R}^{p}\to\mathcal{H}$linear
map$\tilde{{\mathbf{W}}}\colon\mathcal{H}\to\mathbb{R}^{m}$$\hat{\mathcal{H}}\approx\mathcal{H}$$\boldsymbol{\Sigma}=\sigma(\boldsymbol{\Omega}{\mathbf{X}}_{\mathbb{R}^{p}})$
in 1 ${\mathbf{K}}_{\hat{\mathcal{H}}}=\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}\approx{\mathbf{K}}_{\mathcal{H}}$
$\mathbb{R}^{m}$${\mathbf{X}}_{\operatorname{{\rm
RF}}}={\mathbf{W}}_{\operatorname{{\rm RF}}}^{\sf T}\boldsymbol{\Sigma}$
${\mathbf{K}}_{\operatorname{{\rm RF}}}={\mathbf{X}}_{\operatorname{{\rm
RF}}}^{\sf T}{\mathbf{X}}_{\operatorname{{\rm RF}}}$RF
map$\sigma(\boldsymbol{\Omega}~{}\cdot)\colon\mathbb{R}^{p}\to\hat{\mathcal{H}}$linear
map${\mathbf{W}}_{\operatorname{{\rm
RF}}}\colon\mathbb{R}^{2N}\to\mathbb{R}^{m}$ Figure 2:  Top: Two-step
“transformation” in TCA, from raw data space $\mathbb{R}^{p}$ to (possibly
infinite-dimensional) RKHS $\mathcal{H}$, and then to the low-dimensional
$\mathbb{R}^{m}$. Bottom: Two-step “transformation” in the proposed RF-TCA,
from $\mathbb{R}^{p}$ to random features kernel space
$\hat{\mathcal{H}}\subset\mathbb{R}^{2N}$, and then to the low-dimensional
$\mathbb{R}^{m}$.

To distinguish the original TCA approach in (TCA) from its forthcoming random-
features-based variant, we will henceforth refer to it as _vanilla_ TCA.

Notably, it is worth mentioning that the matrix inverse
$(\gamma{\mathbf{I}}_{n}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}$, being a rank-one update of the inverse of
$\gamma{\mathbf{I}}_{n}$, can be _explicitly_ computed using the
Sherman–Morrison formula (see 3 in Appendix A). This is discussed in the
following result.

######  Lemma 1 (Equivalent form of vanilla TCA).

The matrix
$\gamma{\mathbf{I}}_{n}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}$ is invertible _if and only if_
$\gamma+{\boldsymbol{\ell}}^{\sf T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}\neq 0$,
and one has
$(\gamma{\mathbf{I}}_{n}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}=\frac{1}{\gamma}({\mathbf{I}}_{n}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}})$, so that the “transformed” feature
${\mathbf{H}}{\mathbf{K}}{\mathbf{W}}$ obtained from vanilla TCA, with
${\mathbf{W}}$ solution to (TCA), is given by the top eigenspace that
corresponds to the largest $m$ eigenvalues of

${\mathbf{A}}\equiv{\mathbf{H}}\left({\mathbf{K}}^{2}-\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}\right){\mathbf{H}}.$ (4)

The advantage of the formulation in 1 is that one no longer needs to invert
the $n$-by-$n$ matrix (that takes $O(n^{3})$ time in general) for vanilla TCA
in (3), but only to perform matrix additions and matrix-vector multiplication
via, e.g., Lanczos iteration that takes $O(n^{2})$ time [45] to retrieve the
top eigenvectors.

In Appendix B of the appendix, we provide further discussions and numerical
results on vanilla TCA.

###  II-C Federated Averaging

Model aggregation is a key enabler in federated learning (FL) that allows for
collaborative training of large-scale ML models by, e.g., combining the model
parameters from different clients. In this respect, FedSGD and federated
averaging (FedAvg) [10] allows users to collaboratively benefit from shared
models trained on diverse data without central storage. FedMA [46], on the
other hand, proposes to construct a shared ML model (e.g., a deep neural
network) in a layer-by-layer manner by “matching” and averaging the hidden
elements.

In the proposed FedRF-TCA protocol, we utilize federated averaging to update
the model parameters in both the classifier ${\mathbf{C}}$ and the linear
adaptive layer ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ in Figure 1, due to
its simplicity and low communication cost. Federated averaging (FedAvg) was
introduced in [10] to train a ML model in a decentralized way by iteratively
aggregating locally computed updates. Consider a FL scenario where the
training data are available at $K$ clients, the FedAvg protocol proposes, in
each iteration, to first locally update the model parameter at each client and
then send the updated parameter to a central server. The server then
aggregates the model parameters ${\mathbf{W}}_{i},i\in\\{1,\ldots,K\\}$ from
the selected clients. FedAvg allows one to collectively reap the benefits of
shared models trained on a large number of data partitioned over $K$ clients,
without centrally storing these data in a server.

##  III A Random Features Approach to TCA

In this section, we propose RF-TCA, a random features-based computationally
efficient approach to TCA. Under standard assumptions, we demonstrate in 2
that RF-TCA substantially mitigates the computational overhead associated with
vanilla TCA, while exhibiting (virtually) no degradation in transfer learning
performance compared to vanilla TCA.

###  III-A An Alternative Regularization Scheme for TCA

Instead for employing regularization on the Frobenius norm of the linear map
${\mathbf{W}}$, as done in vanilla TCA in Section II-B, an alternative
approach is to penalize the “projector”
$\tilde{\mathbf{W}}\colon\mathcal{H}\to\mathbb{R}^{p}$ on the RKHS. This novel
approach, referred to as Regularized TCA (R-TCA) in the subsequent section,
formulates the following optimization problem:

$\displaystyle\min_{{\mathbf{W}}}$
$\displaystyle\quad\tilde{L}_{\gamma}({\mathbf{W}})=\operatorname{{\rm
tr}}({\mathbf{W}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\mathbf{W}})+\gamma\operatorname{{\rm tr}}({\mathbf{W}}^{\sf
T}{\mathbf{K}}{\mathbf{W}}),$ s.t. $\displaystyle\quad{\mathbf{W}}^{\sf
T}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}{\mathbf{W}}={\mathbf{I}}_{m},$ (R-TCA)

and differs from (TCA) _only_ in the regularization term. An inspection
reveals the following close relationship between the objective functions of
the two approaches.

######  Lemma 2 (TCA versus R-TCA).

Let the kernel matrix ${\mathbf{K}}$ be defined as in (1) and let
$\lambda_{\max}({\mathbf{K}})\geq\lambda_{\min}({\mathbf{K}})\geq 0$ be its
maximum and minimum eigenvalue, respectively. Then, for any given
${\mathbf{W}}\in\mathbb{R}^{n\times m}$, one has

$\displaystyle
L_{\gamma\lambda_{\min}({\mathbf{K}})}({\mathbf{W}})\leq\tilde{L}_{\gamma}({\mathbf{W}})\leq
L_{\gamma\lambda_{\max}({\mathbf{K}})}({\mathbf{W}}).$

###### Proof of 2.

Since
$\lambda_{\min}({\mathbf{K}}){\mathbf{I}}_{n}\preceq{\mathbf{K}}\preceq\lambda_{\max}({\mathbf{K}}){\mathbf{I}}_{n}$,
one has for any given ${\mathbf{W}}\in\mathbb{R}^{n\times m}$ that
$0\leq\lambda_{\min}({\mathbf{K}})\operatorname{{\rm tr}}({\mathbf{W}}^{\sf
T}{\mathbf{W}})\leq\operatorname{{\rm tr}}({\mathbf{W}}^{\sf
T}{\mathbf{K}}{\mathbf{W}})\leq\lambda_{\max}({\mathbf{K}})\operatorname{{\rm
tr}}({\mathbf{W}}^{\sf T}{\mathbf{W}})$. By $\gamma\geq 0$, we conclude the
proof of 2. ∎

As elucidated by 2, it becomes evident that the two optimization problems in
(TCA) and (R-TCA) are “equivalent” concerning their loss functions, differing
only by a scaling factor on the regularization parameter $\gamma$.

As for vanilla TCA in (3), the R-TCA approach in (R-TCA) also admits an
_explicit_ solution ${\mathbf{W}}_{\rm R}$ , given by the top $m$ eigenvector
of
$(\gamma{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}$ (the proof of which
is the same as [30, Proposition 1] and is omitted), that is

${\mathbf{H}}{\mathbf{K}}(\gamma{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}\cdot{\mathbf{H}}{\mathbf{K}}{\mathbf{W}}_{\rm
R}={\mathbf{H}}{\mathbf{K}}{\mathbf{W}}_{\rm R}\cdot\boldsymbol{\Lambda}_{\rm
R},$ (5)

where we denote $\boldsymbol{\Lambda}_{\rm R}$ the diagonal matrix containing
the $m$ largest eigenvalues of
$(\gamma{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}{\mathbf{K}}$.

###  III-B A Random Features Approach to Large-scale TCA

Here, we present RF-TCA, a random features-based approach to computationally
efficient TCA, by focusing on random Fourier features (RFFs) and Gaussian
kernel.

######  Definition 1 (Random Fourier features for Gaussian kernels, [19]).

For data matrix
${\mathbf{X}}=[{\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{n}]\in\mathbb{R}^{p\times
n}$ of size $n$, the random Fourier feature (RFF) matrix
$\boldsymbol{\Sigma}\in\mathbb{R}^{2N\times n}$ of ${\mathbf{X}}$ is given
by111Extensions of RFFs to other shift-invariant kernels (such as the
Laplacian and Cauchy kernels) also exists, see [19].

$\boldsymbol{\Sigma}=\frac{1}{\sqrt{N}}\begin{bmatrix}\cos(\boldsymbol{\Omega}{\mathbf{X}})\\\
\sin(\boldsymbol{\Omega}{\mathbf{X}})\end{bmatrix}\in\mathbb{R}^{2N\times n},$
(6)

with $N$ the number of random features,
$\boldsymbol{\Omega}\in\mathbb{R}^{N\times p}$ a random matrix having i.i.d.
standard Gaussian entries with mean zero and variance $1/\sigma^{2}$, i.e.,
$[\boldsymbol{\Omega}]_{ij}\overset{i.i.d.}{\sim}\mathcal{N}(0,1/\sigma^{2})$,
and nonlinear functions $\cos(\cdot),\sin(\cdot)$ applied entry-wise on
$\boldsymbol{\Omega}{\mathbf{X}}$.

Denote $\dim({\mathbf{K}})\equiv\operatorname{{\rm
tr}}{\mathbf{K}}/\|{\mathbf{K}}\|_{2}$ the intrinsic dimension of the Gaussian
kernel matrix ${\mathbf{K}}={\mathbf{K}}_{\operatorname{{\rm Gauss}}}$, it is
known that an order of $N=O(\dim({\mathbf{K}})\log(n))$ RFFs suffices to well
approximate the Gaussian kernel matrix ${\mathbf{K}}$ in a spectral norm
sense, as given in the following result.

######  Theorem 1 (RFFs approximation of Gaussian kernels, [47, Section 6.5]).

For random Fourier features $\boldsymbol{\Sigma}\in\mathbb{R}^{2N\times n}$ of
data ${\mathbf{X}}\in\mathbb{R}^{p\times n}$ as defined in 1, one has

$\mathbb{E}\|\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-{\mathbf{K}}\|_{2}\leq
C\left(\sqrt{\frac{n\log(n)}{N}\|{\mathbf{K}}\|_{2}}+\frac{n\log(n)}{N}\right),$

holds for some universal constant $C>0$ independent of $N$ and $n$, with
${\mathbf{K}}={\mathbf{K}}_{\operatorname{{\rm
Gauss}}}=\\{\exp(-\|{\mathbf{x}}_{i}-{\mathbf{x}}_{j}\|^{2}/(2\sigma^{2}))\\}_{i,j=1}^{n}$
the Gaussian kernel matrix of ${\mathbf{X}}$.

Given $\varepsilon\in(0,1)$, taking $N\geq
C^{\prime}\dim({\mathbf{K}})\log(n)/\varepsilon^{2}$ for some universal
constant $C^{\prime}>0$ independent of $n$, with
$\dim({\mathbf{K}})\equiv\operatorname{{\rm
tr}}{\mathbf{K}}/\|{\mathbf{K}}\|_{2}=n/\|{\mathbf{K}}\|_{2}$ the _intrinsic
dimension_ of Gaussian kernel matrix
${\mathbf{K}}={\mathbf{K}}_{\operatorname{{\rm Gauss}}}$, it follows from 1
that the _expected_ relative error satisfies

$\mathbb{E}\|\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-{\mathbf{K}}\|_{2}/\|{\mathbf{K}}\|_{2}\leq\varepsilon,$
(7)

and it suffices to have an order of $\dim({\mathbf{K}})\log(n)$ RFFs so that
the RFF Gram matrix $\boldsymbol{\Sigma}^{\sf T}\boldsymbol{\Sigma}$ is a good
approximation of the Gaussian kernel matrix in a _spectral norm_ sense.

Following the idea of vanilla TCA in (TCA), we aim to find a matrix
${\mathbf{W}}_{\operatorname{{\rm RF}}}\in\mathbb{R}^{2N\times m}$ that
“projects” the RFFs $\boldsymbol{\Sigma}$ onto an $m$-dimensional space, with
$m\ll\min(2N,n)$, to obtain the “transferred and aligned” representations
${\mathbf{W}}_{\operatorname{{\rm RF}}}^{\sf
T}\boldsymbol{\Sigma}\in\mathbb{R}^{m\times n}$ with kernel matrix
$\tilde{\mathbf{K}}=\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm RF}}}{\mathbf{W}}_{\operatorname{{\rm
RF}}}^{\sf T}\boldsymbol{\Sigma}$. We propose to determine
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ by solving the following optimization
problem:

$\displaystyle\min_{{\mathbf{W}}\in\mathbb{R}^{2N\times m}}$
$\displaystyle\quad\operatorname{{\rm tr}}({\mathbf{W}}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf T}{\mathbf{W}})+\gamma\operatorname{{\rm
tr}}({\mathbf{W}}^{\sf T}{\mathbf{W}})$ s.t.
$\displaystyle\quad{\mathbf{W}}^{\sf
T}\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}={\mathbf{I}}_{m},$ (RF-TCA)

with regularization $\gamma$ and ${\mathbf{H}}$ as for vanilla TCA in (TCA).

Assume $\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}\in\mathbb{R}^{2N\times 2N}$ is invertible and let
$\tilde{\mathbf{W}}\equiv(\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T})^{\frac{1}{2}}{\mathbf{W}}\in\mathbb{R}^{2N\times m}$, the problem (RF-TCA)
then writes

$\displaystyle\min$ $\displaystyle\quad\operatorname{{\rm
tr}}\left(\tilde{\mathbf{W}}^{\sf
T}(\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T})^{-\frac{1}{2}}(\boldsymbol{\Sigma}{\mathbf{L}}\boldsymbol{\Sigma}^{\sf
T}+\gamma{\mathbf{I}}_{2N})(\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T})^{-\frac{1}{2}}\tilde{\mathbf{W}}\right)$ s.t.
$\displaystyle\quad\tilde{\mathbf{W}}^{\sf
T}\tilde{\mathbf{W}}={\mathbf{I}}_{m},$ (8)

which also takes the form of a trace minimization, see [30, Proposition 1] and
[48]. It then follows from the Rayleigh–Ritz theorem that the optimal solution
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ is given by the top $m$ eigenvectors
of $(\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}+\gamma{\mathbf{I}}_{2N})^{-1}\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}$ associated to the $m$ largest eigenvalues.

Also, as in 1 for vanilla TCA, the inverse
$(\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf T}+\gamma{\mathbf{I}}_{2N})^{-1}$ takes an explicit
form per the Sherman–Morrison formula (see again 3 described in Appendix A).
This leads to the RF-TCA method in Algorithm 1.

Algorithm 1 Random features-based TCA (RF-TCA)

1: Input: Source data ${\mathbf{X}}_{S}\in\mathbb{R}^{p\times n_{S}}$, target
data ${\mathbf{X}}_{T}\in\mathbb{R}^{p\times n_{T}}$, number of random
features $N$, and projected dimension $m$.

2: Output: “Aligned” features ${\mathbf{F}}_{\operatorname{{\rm
RF}}}=[{\mathbf{F}}_{S},~{}{\mathbf{F}}_{T}]$ with
${\mathbf{F}}_{S}\in\mathbb{R}^{m\times
n_{S}},{\mathbf{F}}_{T}\in\mathbb{R}^{m\times n_{T}}$ of ${\mathbf{X}}_{S}$
and ${\mathbf{X}}_{T}$, respectively.

3: Compute RFFs $\boldsymbol{\Sigma}\in\mathbb{R}^{2N\times n}$ of the source
and target data
${\mathbf{X}}=[{\mathbf{X}}_{S},~{}{\mathbf{X}}_{T}]\in\mathbb{R}^{p\times
n},n=n_{S}+n_{T}$ as in (6).

4: Compute ${\mathbf{W}}_{\operatorname{{\rm RF}}}\in\mathbb{R}^{2N\times m}$
as the $m$ dominant eigenvectors (that correspond to the largest $m$
eigenvalues) of  $\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}-\frac{\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}}{\gamma+{\boldsymbol{\ell}}^{\sf T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}},$ (9) for
${\mathbf{H}}={\mathbf{I}}_{n}-{\mathbf{1}}_{n}{\mathbf{1}}_{n}^{\sf T}/n$ and
${\boldsymbol{\ell}}\in\mathbb{R}^{n}$ defined in (2).

5: return RF-TCA “transferred” features as ${\mathbf{F}}_{\operatorname{{\rm
RF}}}={\mathbf{W}}_{\operatorname{{\rm RF}}}^{\sf T}\boldsymbol{\Sigma}$.

As one may expect from the spectral norm approximation in 1, we show, in the
following result that for RF-TCA in Algorithm 1, an order of
$\dim({\mathbf{K}})\log(n)$ random features suffices to get an accuracy
approximation of the transferred features using R-TCA, and thus of the vanilla
TCA (up to a proper tuning of hyperparameter $\gamma$, see again 2), the proof
of which is given in Appendix C.

######  Theorem 2 (Performance guarantee for RF-TCA).

For the random Fourier features matrix
$\boldsymbol{\Sigma}\in\mathbb{R}^{2N\times n}$ defined in 1 with associated
Gaussian kernel matrix ${\mathbf{K}}={\mathbf{K}}_{\operatorname{{\rm
Gauss}}}\in\mathbb{R}^{n\times n}$, let ${\mathbf{W}}_{\rm
R}\in\mathbb{R}^{n\times m}$ be the R-TCA solution to (R-TCA) and let
${\mathbf{W}}_{\operatorname{{\rm RF}}}\in\mathbb{R}^{2N\times m}$ be the
solution to (RF-TCA). Then, one has, for any given $\varepsilon\in(0,1)$ that

$\mathbb{E}\|{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm
RF}}}-{\mathbf{H}}{\mathbf{K}}{\mathbf{W}}\|_{F}\leq\varepsilon,$ (10)

holds as long as $N\geq C\dim({\mathbf{K}})\log(n)/\varepsilon^{2}$ for some
positive constant $C$ that depends on the _relative eigen-gap_
$\tilde{\Delta}_{\lambda}\equiv\min_{1\leq i\leq
m}\left|\lambda_{i}({\mathbf{A}}_{\rm R})-\lambda_{i+1}({\mathbf{A}}_{\rm
R})\right|/\|{\mathbf{K}}\|_{2}>0$, with $\lambda_{i}({\mathbf{A}}_{\rm R})$
the eigenvalues of ${\mathbf{A}}_{\rm
R}\equiv{\mathbf{H}}{\mathbf{K}}(\gamma{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}$ listed in a numerically
decreasing order.

######  Remark 1 (Eigen-gap condition).

Note that the bound in 2 becomes vacuous when the _relative_ eigen-gap
condition $\tilde{\Delta}_{\lambda}\equiv\min_{1\leq i\leq
m}\left|\lambda_{i}({\mathbf{A}})-\lambda_{i+1}({\mathbf{A}})\right|/\|{\mathbf{K}}\|_{2}>0$
is violated. This condition is needed in the application of the Davis–Kahan
theorem and is rather standard in the literature of spectral methods, see also
[49, 48].

Theorem 2 states, under the eigen-gap condition, that it suffices to have
$N=O(\dim({\mathbf{K}})\log(n))$ random features to obtain RF-TCA transferred
features as an accurate “proxy” of the features from R-TCA, and thus from the
vanilla TCA. Recall from 1 that one needs $N=O(\dim({\mathbf{K}})\log(n))$
random feature to _spectrally_ approximate a given kernel matrix. In this
vein, 2 tells us that it suffices to approximate the kernel matrix in a
spectral norm sense so as to obtain RF-TCA solutions that are _as good as_ the
original R-TCA, and thus the TCA solution.

We have shown in this section that the proposed RF-TCA approach in Algorithm 1
enjoys the numerical (and thus communicational in a FL context) advantage of
operating on a much lower dimensional space ($2N$ instead of $n$, with
$N=O(\dim({\mathbf{K}})\log(n))$ that is significantly smaller than $O(n)$ if
$\dim({\mathbf{K}})\ll n$) and at the same time, obtains “transferred”
features close to those of TCA. Following our framework in Figure 1 of Section
I-A, we discuss next how the proposed RF-TCA serves as a cornerstone to the
robust and communication-efficient FedRF-TCA approach, and, at the same time,
provides additional privacy guarantee.

##  IV Robust and Communication-efficient Federated Domain Adaptation via RF-
TCA

The majority, if not all, of the DA methods based on MMD, while known for
their effectiveness in aligning feature distributions between source and
target data, impose a substantial computational burden. This computational
complexity primarily arises from the necessity of operations involving the
_large_ kernel matrices of both source and target data, as highlighted in
prior works [34, 35]. This makes them unsuitable for use in an FL context, for
which low communication and computational costs are desired [16].

In response to this challenge, we propose Federated Random Features-based
Transfer Component Analysis (FedRF-TCA), a novel FDA approach designed to
alleviate the computational and communicational demands and enhance privacy
protection. FedRF-TCA achieves this by employing compression and randomization
techniques during the (asynchronous) training procedure, leveraging the RF-TCA
methodology introduced in Section III, to optimize information exchange within
the MMD-based FDA scheme. In comparison to existing MMD-based FDA protocols,
FedRF-TCA offers significant reductions in both communication and
computational overheads while maintaining commendable performance.

Specifically, we are primarily focused on a federated multi-source
classification task, which involves multiple source clients coexisting
alongside one target client. Each source client is characterized by a distinct
domain, comprising its own dataset and corresponding labels. In contrast, the
target client solely possesses data without accompanying labels. The
overarching goal of FDA is to train a model that can effectively classify the
target data while also addressing concerns such as data leakage.

The FedRF-TCA protocol comprises a structured framework for each client,
encompassing three distinct local components, as illustrated in Figure 1:

  * (i)

Feature Extractor: For each source and target domain, an dedicated local
feature extractor is trained by fine-tuning a pretrained model, such as
ResNet-50. These feature extractors are denoted as
${\mathbf{G}}_{S}^{(1)},\ldots,{\mathbf{G}}_{S}^{(K)}$ for the $K$ source
domains $\mathcal{D}_{S}^{(1)},\ldots,\mathcal{D}_{S}^{(K)}$, and
${\mathbf{G}}_{T}$ for the target domain $\mathcal{D}_{T}$ in Figure 1. This
training process yields local and “unaligned” source features
${\mathbf{X}}_{S}^{(1)}\in\mathbb{R}^{p\times
n_{S}^{(1)}},\ldots,{\mathbf{X}}_{S}^{(K)}\in\mathbb{R}^{p\times n_{S}^{(K)}}$
and target features ${\mathbf{X}}_{T}\in\mathbb{R}^{p\times n_{T}}$,
respectively.

  * (ii)

RF-TCA Transfer Module: In this module, the random feature map in 1 is applied
on ${\mathbf{X}}_{S}^{(1)},\ldots,{\mathbf{X}}_{S}^{(K)}$ and
${\mathbf{X}}_{T}$ to intermediate representations
$\boldsymbol{\Sigma}_{S}^{(1)},\ldots,\boldsymbol{\Sigma}_{S}^{(K)}$ and
$\boldsymbol{\Sigma}_{T}$. Subsequently, an _adaptive_ linear layer
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ is applied to these RFFs, aligning
the source and target feature distributions, by minimizing their MMD distance.

  * (iii)

Classifier: Finally, source classifiers ${\mathbf{C}}_{S}^{(i)}$ are trained
on the “aligned” source features from RF-TCA module, and their outputs are
aggregated to obtain the target classifier, serving the desired classification
purpose.

In the remainder of section, we discuss in Section IV-A how, for a given pair
of source and target domain $(\mathcal{D}_{S}^{(i)},\mathcal{D}_{T})$,
features are extracted from data in distinct domains, and “transferred” into a
common domain via random feature maps and a trainable linear layer
${\mathbf{W}}_{\operatorname{{\rm RF}}}$; and then in Section IV-B how, in a
multi-source FDA setting, the local models of source clients are updated and
subsequently aggregated to construct the target model. Finally, in Section
IV-C, we undertake a comprehensive analysis of the advantages conferred by the
proposed FedRF-TCA protocol, in terms of its computational and communication
overhead, in addition to its enhanced robustness as well as privacy protection
mechanisms.

###  IV-A MMD-based Random Features Alignment

To minimize the MMD distance between source and target feature distributions,
FedRF-TCA proposes to use

  * (i)

a (local) feature extractor ${\mathbf{G}}_{S}$; followed by

  * (ii-i)

a random features “compressor” as in 1; and

  * (ii-ii)

a linear layer ${\mathbf{W}}_{\operatorname{{\rm RF}}}\in\mathbb{R}^{2N\times
m}$ that aligns features from source and target domains.

Specifically, for a given pair of source-target domain
$(\mathcal{D}_{S}^{(i)},\mathcal{D}_{T})$, $i\in\\{1,\ldots,K\\}$, we define
the following MMD loss between the $i$th source domain $\mathcal{D}_{S}^{(i)}$
and the target domain $\mathcal{D}_{T}$ as

$\displaystyle L_{\rm
MMD}^{(i)}({\mathbf{G}}_{S}^{(i)},{\mathbf{G}}_{T},{\mathbf{W}}_{\operatorname{{\rm
RF}}})$ (11)
$\displaystyle=(\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}+\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T})^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm RF}}}{\mathbf{W}}_{\operatorname{{\rm
RF}}}^{\sf
T}(\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}+\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}),$

in the same spirit as in (RF-TCA) for RF-TCA but without the regularization
term, where the RF matrices $\boldsymbol{\Sigma}_{S}^{(i)}$ and
$\boldsymbol{\Sigma}_{T}$ are computed as in 1 with input
${\mathbf{X}}_{S}^{(i)}$ and ${\mathbf{X}}_{T}$, respectively,
${\boldsymbol{\ell}}_{S}^{(i)}={\mathbf{1}}_{n_{S}^{(i)}}/n_{S}^{(i)}$ for
data from the $i$th source domain and
${\boldsymbol{\ell}}_{T}=-{\mathbf{1}}_{n_{T}}/n_{T}$ for target from target
domain as in (2), with $N$ the number of random features.

Note that the MMD loss in (11) is defined for the $i$th source domain
$\mathcal{D}_{S}^{(i)}$ and the target domain $\mathcal{D}_{T}$, and depends
on the source and target _local_ features extractors ${\mathbf{G}}_{S}^{(i)}$
and ${\mathbf{G}}_{T}$, as well as the local linear (RF-based) feature
“aligner” ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ at source or target client.

The proposed MMD formulation in (11) extends the RF-TCA thoroughly approach
disused in Section III, by relaxing the second-order constraint
${\mathbf{W}}_{\operatorname{{\rm RF}}}^{\sf
T}\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm RF}}}={\mathbf{I}}_{m}$ in (RF-TCA), and
thereby allows for _learnable_ linear feature aligner
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ _and_ local feature extractors
${\mathbf{G}}_{S},{\mathbf{G}}_{T}$. This makes the MMD minimization in (11)
more flexible, e.g., by avoiding the need of simultaneous access to _all_
source and target data. Notably, the linear layer
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ can now be improved (e.g., via
backpropagation) by exploiting the information in a mini-batch of source and
target data, a property of particular interest to federated learning.

In the context of multi-source federated domain adaptation, the frequent
message passing between clients results in communication overhead and imposes
robustness requirements on the network. In this respect, the proposed
formulation in (11) is both communication-efficient and robust in that:

In the context of multi-source federated domain adaptation, the frequent
exchange of messages between clients can lead to significant communication
overhead and impose robustness requirements on the network infrastructure. In
this context, our proposed formulation in (11) offers notable advantages in
terms of communication efficiency and robustness:

  1. 1.

Efficient Communication: Messages shared between source and target clients are
highly compressed and take the form of summed features as
$\boldsymbol{\Sigma}{\boldsymbol{\ell}}\in\mathbb{R}^{2N}$. Importantly, the
size of such messages is solely dependent on the number of random features
$N$, and is _independent_ of the (source and/or target) sample size.

  2. 2.

Robust Asynchronous Training: The federated domain adaptation process can be
performed in an asynchronous manner. This is made possible due to the proposed
decomposable MMD loss in (11), for a specific pair of source-target domains
$(\mathcal{D}_{S}^{(i)},\mathcal{D}_{T})$. Consequently, the FDA system can
continue to improve during the training/transferring procedure, even in the
presence of stragglers or irregularities in client participation.

###  IV-B FedRF-TCA: multi-source FDA via RF-TCA and FedAvg

While most existing DA methods are designed for a single pair of source-target
domain, here we show how the proposed FedRF-TCA protocol naturally extends to
a multi-source FDA scenario.

Consider $K$ source domains $\mathcal{D}_{S}^{(i)}$ with associated data and
labels $({\mathbf{X}}_{S}^{(i)},{\mathbf{Y}}_{S}^{(i)}),i\in\\{1,\ldots,K\\}$,
and a single target domain $\mathcal{D}_{T}$ with unlabelled data
${\mathbf{X}}_{T}$, upon which some decision (e.g., classification) should be
made in an FDA fashion.

The FedRF-TCA approach proposes to perform FDA in two steps:

##### Local Domain Alignment via RF-TCA

Here, the source and target model are trained respectively by minimizing the
MMD-loss $L_{T}=L_{\rm MMD}$ as in (11) on the target client and the following
hybrid loss on the $i$th source client:

$L_{S}^{(i)}=L_{C}^{(i)}+\lambda L_{\rm MMD}^{(i)},$ (12)

where $L_{C}^{(i)}$ denotes the classification loss computed on (a min-batch
of) $({\mathbf{X}}_{S}^{(i)},{\mathbf{Y}}_{S}^{(i)})$, $L_{\rm MMD}^{(i)}$ the
MMD-loss in (11), and $\lambda>0$ some trade-off hyperparameter.

Notably, during the training process, the target client disseminates
$\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}\in\mathbb{R}^{2N}$ to _all_
source clients. In contrast, each individual source client transmits _solely_
$\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}\in\mathbb{R}^{2N}$
to the target client, and _no_ messages are exchanged between source clients
themselves.

Also, the Gaussian random matrix $\boldsymbol{\Omega}$ to compute the random
Fourier features in 1 is generated by some predefined random seed
$\mathfrak{S}$ shared by _all_ source and target clients, so that no
additional communication and/or storage is needed.

This local training procedure is summarized for source and target models in
Algorithm 2 and Algorithm 3, respectively.

##### Global Parameter Aggregation via FedAvg

The collection of linear adaptive layers ${\mathbf{W}}_{\operatorname{{\rm
RF}}}$ and/or the source classifiers ${\mathbf{C}}$, originating from a
potentially unordered set of source clients and the target client, is
aggregated using the federated averaging (FedAvg) protocol [10]. Precisely,
for a given around number $t$, we randomly draw from the (discrete) uniform
distribution ${\rm Unif}\\{0,K\\}$ to determine the cardinality
$|\mathcal{S}_{t}|$ of the set $\mathcal{S}_{t}$, then to get
$\mathcal{S}_{t}$ by randomly sampling without replacement $|\mathcal{S}_{t}|$
elements from the index set $\\{1,\ldots,K\\}$.

This random sampling procedure emulates potential client and/or message drops
during training, which can occur due to factors such as limited network
reliability. It plays a crucial role in enhancing the robustness of the
proposed FedRF-TCA approach. The resulting global parameter aggregation
protocol is described in Algorithm 4.

Algorithm 2 Local training of the $i$th source model

1: Input: Training set $({\mathbf{X}}_{S}^{(i)},{\mathbf{Y}}_{S}^{(i)})$,
local feature extractor ${\mathbf{G}}_{S}^{(i)}$ and classifier
${\mathbf{C}}_{S}^{(i)}$ at the $i$th source domain $\mathcal{D}_{S}^{(i)}$,
(summarized) target message $\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}$,
random index set $\mathcal{S}_{t}$, some predefined random seed
$\mathfrak{S}$, and number of random features $N$.

2: Output: Source message
$\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}$, updated linear
layer ${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(i)}$ and classifier
${\mathbf{C}}_{S}^{(i)}$.

3: Sample a mini-batch from $({\mathbf{X}}_{S}^{(i)},{\mathbf{Y}}_{S}^{(i)})$.

4: Compute source message
$\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}$ as in 1 with
random seed $\mathfrak{S}$ and number of random features $N$.

5: if $i\in\mathcal{S}_{t}$ then

6: Update ${\mathbf{G}}_{S}^{(i)},{\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(i)},{\mathbf{C}}_{S}^{(i)}$ by minimizing $L_{S}^{(i)}$ in (12)
via back-propagation.

7: else

8: Update ${\mathbf{G}}_{S}^{(i)},{\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(i)},{\mathbf{C}}_{S}^{(i)}$ only by minimizing $L_{C}^{(i)}$ in
(12) via back-propagation.

9: end if

10: return $\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}$
,${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(i)}$ and
${\mathbf{C}}_{S}^{(i)}$.

Algorithm 3 Local training of the target model

1: Input: Unlabelled data ${\mathbf{X}}_{T}$ and local feature extractor
${\mathbf{G}}_{T}$ at the target domain $\mathcal{D}_{T}$, (summarized) source
messages
$\\{\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}\\}_{i\in\mathcal{S}_{t}}$,
some predefined random seed $\mathfrak{S}$, and number of random features $N$.

2: Output: Target feature $\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}$ and
linear layer ${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$.

3: Sample a mini-batch from ${\mathbf{X}}_{T}$.

4: Compute target message $\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}$ as
1 with random seed $\mathfrak{S}$ and number of random features $N$.

5: Update ${\mathbf{G}}_{T},{\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$ to
minimize the MMD loss in (11).

6: return $\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}$ and
${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$.

Algorithm 4 Global parameter aggregation

1: Input: round number $t$, time interval for classifier aggregation $T_{C}$,
source parameters $\\{{\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(i)}\\}_{i\in\mathcal{S}_{t}}$ and
$\\{{\mathbf{C}}_{S}^{(i)}\\}_{i\in\mathcal{S}_{t}}$, target parameters
${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$.

2: Output: Averaged weight ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ or
averaged classifier ${\mathbf{C}}$.

3: Compute the aggregated weight ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ as
the average of source weights $\\{{\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(i)}\\}_{i\in\mathcal{S}_{t}}$ in the set $\mathcal{S}_{t}$ and
target weight ${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$.

4: if $t\hskip 2.84544pt\%\hskip 2.84544ptT_{C}=0$ then

5: Compute the aggregated ${\mathbf{C}}$ as the average of the source
classifiers $\\{{\mathbf{C}}_{S}^{(i)}\\}_{i\in\mathcal{S}_{t}}$ in the set
$\mathcal{S}_{t}$.

6: end if

7: return aggregated ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ and
${\mathbf{C}}$.

To further alleviate the communication overhead associated with global
parameter aggregation in FedRF-TCA, we introduce a modification outlined in
Algorithm 4. Under this scheme, the classifier ${\mathbf{C}}$ is aggregated
_only once_ every $T_{C}\gg 1$ time intervals, while the weight
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ is exchanged in each round of
communication. This adjustment results in a substantial reduction in
communication overhead during training, without any significant compromise in
performance.

The whole FedRF-TCA training procedure is summarized in Algorithm 5 and
illustrated in Figure 1.

Algorithm 5 Federated RF-TCA (FedRF-TCA)

1: Model initialization.

2: Generate a random seed $\mathfrak{S}$ and send to all clients.

3: Determine $T_{C}$ the time interval to aggregate the classifiers.

4: for each round $t=1,2,\ldots$ do

5: Sample a random subset $\mathcal{S}_{t}$ from the source index set
$\\{1,\ldots,K\\}$ as in Section IV-B.

6: Local Domain Alignment:

7: Compute
$\\{\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)},{\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(i)},{\mathbf{C}}_{S}^{(i)}\\}_{i=1}^{K}$ at source clients as in
Algorithm 2.

8: Compute ${\mathbf{W}}_{\operatorname{{\rm
RF}}_{T}},\boldsymbol{\Sigma}_{T}{\boldsymbol{\ell}}_{T}$ at the target client
as in Algorithm 3.

9: Global Parameter Aggregation:

10: For each client $i\in\mathcal{S}_{t}$, aggregate
${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$ and
${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(i)}$ to get
${\mathbf{W}}_{\operatorname{{\rm RF}}}$ as in Algorithm 4.

11: if $t\hskip 2.84544pt\%\hskip 2.84544ptT_{C}=0$ then

12: For each client $i\in\mathcal{S}_{t}$, aggregate ${\mathbf{C}}_{S}^{(i)}$
to get ${\mathbf{C}}$ as in Algorithm 4.

13: end if

14: Update Client Models:

15: Assign ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ to both
${\mathbf{W}}_{\operatorname{{\rm RF}}_{T}}$ and
$\\{{\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(i)}\\}_{i\in\mathcal{S}_{t}}$,

16: if $t\hskip 2.84544pt\%\hskip 2.84544ptT_{C}=0$ then

17: Assign ${\mathbf{C}}$ to ${\mathbf{C}}_{T}$ and
$\\{{\mathbf{C}}_{S}^{(i)}\\}_{i\in\mathcal{S}_{t}}$.

18: end if

19: end for

20: return target classifier ${\mathbf{C}}_{T}$.

###  IV-C Advantages of FedRF-TCA

In this section, we discuss the advantages of FedRF-TCA in terms of its
communication overhead, robustness, and additional privacy guarantee.
Precisely, when compared to popular federated DA methods such as FADA [14],
FedKA [16], and FDA [41], the communication complexity of FedRF-TCA is
_independent_ of the sample size $n$ (but depends _only_ on $N$ the dimension
of random features that can be significantly smaller than $n$, see 2), and
thus (up to) a factor of $n$ times smaller than existing federated DA
approaches. In addition to the extremely low communication overhead, FedRF-TCA
also offers robustness (to both clients dropouts and messages drops due to,
e.g., unstable network connection) and additional privacy preserving, while
achieving comparably good performance to state-of-the-art federated DA
methods.

Table I compares the proposed FedRF-TCA protocol to popular federated DA
methods, in terms of their communication complexity, robustness (flagged by
whether asynchronous training is supported), and additional privacy
guarantee222By “additional privacy guarantee” we mean that the federated DA
protocol adopts privacy preserving technique in addition to the (innate) data
isolation of FL. For example, the Paillier homomorphic encryption method [50]
is used in the training of FDA [41] as additional privacy protection. .

In the remainder of this section, we analyze the communication complexity and
additional privacy guarantee of FedRF-TCA, in Section IV-C1 and Section IV-C2,
respectively.

####  IV-C1 Analysis of communication overhead and robustness

The communication overhead of the proposed FedRF-TCA protocol depends on the
dimension $N$ of the random features (which, according to 2, suffices to be of
order $\log(n)$ and thus depends on the sample size $n$, but _only_ in a
logarithmic fashion), the dimension of the projected feature space $m$, and
the number of the source clients $K$. During training, each pair of source and
target client will need to exchange the compressed features
$\boldsymbol{\Sigma}{\boldsymbol{\ell}}\in\mathbb{R}^{2N}$ to compute the MMD
loss in (11), the communication overhead of which is $O(KN)$. Then, the server
collects an aggregation of the linear layer weights
${\mathbf{W}}_{\operatorname{{\rm RF}}}\in\mathbb{R}^{2N\times m}$ from all
source and target clients. This leads to a communication overhead of $O(KNm)$.
As such, the total communication complexity of the proposed FedRF-TCA is
$O(KN+KNm)$, and is, in particular, _independent_ of the sample size $n$.

TABLE I: Comparison between different federated DA methods, with $K$ the
number of clients, $n$ the sample size, $N$ the dimension of features (i.e.,
the number of random features in FedRF-TCA, the dimension of feature generator
in FADA [14], of feature representation in FedKA [16], and the latent feature
length $L$ in FDA [41]), and $P\geq 1$ is the ciphertext size of Paillier
encryption used in FDA.

Federated DA methods |  Communication overhead |  Asynchronous training |  Added privacy
---|---|---|---
FADA [14] | $O(KnN)$ | ✗ | ✗
FedKA [16] | $O(KnN)$ | ✗ | ✗
FDA [41] | $O(KnNP)$ | ✗ | ✓
FedRF-TCA (ours) | $O(KN)$ | ✓ | ✓

In contrast, other federated DA protocols in Table I show a much higher
communication overhead, with a complexity growing (at least) linearly in both
the feature dimension $N$ _and_ the sample size $n$. As a concrete example,
the FDA protocol [41] proposes to exchange the encrypted source features of
size $O(MP+n_{S}NP)$ (with encryption cost $MP$ and encrypted source features
cost $n_{S}NP$, $P\geq 1$ the ciphertext size of Paillier encryption), as well
as target features of size $n_{T}N$ [41], yielding an overall communication
overhead of $O(nNP)$, for a single source-target pair.

The proposed FedRF-TCA protocol offers not only a _sample-size-independent_
communication overhead, but also robustness to client dropouts and/or messages
drops, an important feature for cross-device FL. In practical FL scenarios,
clients may be temporarily unavailable, dropping out or joining during the
training procedure, and the sent messages may be lost due to the limited
reliability of the network. We show with extensive experiments in Section V
below that the proposed FedRF-TCA is robust to:

  1. 1.

clients dropout, see FedRF-TCA model (II) in Table IV and table V; and

  2. 2.

less frequent classifier aggregation (e.g., every $T_{C}$ time intervals) as
in Algorithm 4, see FedRF-TCA model (III) in Table IV and table V; and

  3. 3.

partial drop of message, such as weights ${\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}$ or $C_{S}$ in Table II.

####  IV-C2 Additional privacy guarantee

Note from Figure 1 and the discussion above in Algorithm 2–1 that with the
proposed FedRF-TCA protocol, the messages exchanged between different clients
are either in form of “compressed” random features
$\boldsymbol{\Sigma}{\boldsymbol{\ell}}\in\mathbb{R}^{2N}$ of linear layer
weights ${\mathbf{W}}_{\operatorname{{\rm RF}}}\in\mathbb{R}^{2N\times m}$
and/or the classifier ${\mathbf{C}}$. In the following, we discuss the
additional privacy guarantee offered by FedRF-TCA.

######  Remark 2 (Privacy protection via compressed random features).

Note that the data representations exchanged between clients during the
training of FedRF-TCA are sum of compressed random features
$\boldsymbol{\Sigma}_{S,T}{\boldsymbol{\ell}}_{S,T}=\pm\boldsymbol{\Sigma}_{S,T}{\mathbf{1}}_{n_{S,T}}/n_{S,T}\in\mathbb{R}^{2N}$,
the dimension of which is _independent_ of the sample size $n_{S,T}$. It is
thus (a priori) _impossible_ for a malicious third party to infer the sample
size $n_{S,T}$, nor the (random) features $\boldsymbol{\Sigma}_{S,T}$ involved
in training from a mere observation of the compressed features
$\boldsymbol{\Sigma}{\boldsymbol{\ell}}$. Moreover, by its definition in 1, we
have $\boldsymbol{\Sigma}=\sigma(\boldsymbol{\Omega}{\mathbf{X}})$ for
_periodic_ function $\sigma(t)=\cos(t)$ or $\sin(t)$ and Gaussian random
matrix $\boldsymbol{\Omega}$, it is also _impossible_ to reveal the raw data
${\mathbf{X}}$ from a mere observation of $\boldsymbol{\Sigma}$, unless
additional constraints are imposed.

##  V Experiments

In this section, we provide extensive numerical results on the proposed RF-TCA
and FedRF-TCA approaches on various datasets, showing their advantageous
performance as well as computational/communicational efficiency and
robustness. In Section V-A, we discuss experimental details on datasets and
baselines. The computational efficiency and robustness of FedRF-TCA are
testified in Section V-B and Section V-C, respectively. In Section V-D, we
provide additional experimental results demonstrating the advantageous
performance of FedRF-TCA with respect to state-of-the-art federated DA
methods. The optimal performance is shown in boldface, and the second optimal
result are displayed as underlined. Code to reproduce the results in this
section are publicly available at https://github.com/SadAngelF/FedRF-TCA.

$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$0.65$$0.7$$0.8$$0.9$$1$TCAJDACORALGFKDaNNRF-
TCARunning time (s)AccuracyRF-TCA Baseline methods  (a) Office-Caltech

$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$0.5$$0.6$$0.7$TCAJDACORALGFKDaNNRF-
TCARunning time (s)AccuracyRF-TCA Baseline methods  (b) Office-31

Figure 3:  Classification accuracy and running time of the proposed RF-TCA
versus baseline DA methods on DeCAF6 features of Office-Caltech and Office-31
datasets. Blue circles for RF-TCA approach with a different number of random
features $N\in\\{100,500,1\,000,2\,000,5\,000\\}$, the red, purple, green,
brown and orange for TCA [20], JDA [31], CORAL [33], GFK [32], and DaNN [15]
approach, respectively. The results are obtained by averaging over _all_
source-target domain pairs ($12$ for Office-Caltech and $6$ for Office-31),
see Appendix D in the appendix for a detailed exposition of these results.

###  V-A Experimental details

####  V-A1 Datasets

  * •

Office-Caltech [32]: This dataset is made up by $10$ common classes shared by
Office-31 and Caltech-256 datasets. It contains four domains: Amazon (A),
Webcam (W), DLSR (D), and Caltech (C).

  * •

Office-31 [51]: This dataset is a standard benchmark for domain adaptation,
with $31$ classes from three different domains: Amazon (A), Webcam (W), and
DLSR (D).

  * •

Digit-Five [52]: This dataset consists handwritten digits from four domains:
MNIST (mn), MNIST-M (mm), SVHN (sv), and Synthetic Digits (sy) dataset.

  * •

Visda-C [53]: This is a challenging and larges-scale dataset with $152\,396$
synthetic 3D model renderings as source domain and $55\,388$ real-world images
as target domain.

####  V-A2 Baselines

In terms of computational efficiency, the proposed RF-TCA approach is compared
against popular DA methods such as TCA [20], JDA [31], CORAL [33], GFK [32],
and DaNN [15]. See Section II-A above for a brief review of these methods. In
a federated DA context, the proposed FedRF-TCA scheme is compared against FADA
[14] and FADE [54]. The baseline results in Table IV, Table V, and Table VI
are repeated from [14, 54].

###  V-B Computational efficiency of RF-TCA

We compare, in Figure 3, the running time and classification accuracy of the
proposed RF-TCA approach against popular DA methods, on both Office-Caltech
[32] and Office-31 [51] datasets. The “transferred” features obtained are
classified using a fully-connected neural network with two hidden layers with
$100$ neurons per layer.

Analysis of Figure 3 clearly demonstrates that our proposed RF-TCA approach
achieves the most favorable trade-off between computational complexity and
performance when compared to other widely recognized DA methods. It
consistently exhibits at least a _tenfold_ reduction in running time while
delivering equally commendable performance.

Notably, our empirical observations indicate that RF-TCA performs
exceptionally well with a relatively modest number of random features $N$,
aligning with the theoretical insights presented in 2.

###  V-C Communication efficiency and robustness of FedRF-TCA

Here, we conduct experiments to demonstrate the communication efficiency and
robustness of the proposed FedRF-TCA approach in a federated DA context over
unreliable networks.

Recall that during the training of FedRF-TCA, messages containing
$\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}$,
${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(j)}$, and
${\mathbf{C}}_{S}^{(k)}$ are exchanged among participating clients. However,
in cases where the network experiences instability, messages and/or clients
may undergo random dropouts during training. Such dropouts could potentially
result in a significant deterioration in the model’s performance. In Table II,
we provide empirical evidence that reassuringly demonstrates this is _not_ the
case for FedRF-TCA. Remarkably, the proposed FedRF-TCA exhibits excellent
robustness to network reliability, maintaining its performance even under
challenging network conditions. Precisely,

  * •

in setting (I), for a given random subset $\mathcal{A}$, all parameters of
$\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}$,
${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(j)}$ and
${\mathbf{C}}_{S}^{(k)}$ are exchanged;

  * •

in setting (II) a (random subset) of classifiers ${\mathbf{C}}_{S}^{(k)}$ are
not involved in training; and

  * •

in setting (III) both ${\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(j)}$ and
${\mathbf{C}}_{S}^{(k)}$ are randomly dropped and only
$\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}$ are fully
exchanged.

We particularly observe from settings (II) and (III) versus (I) that FedRF-TCA
is robust against (random) message drops of ${\mathbf{W}}_{\operatorname{{\rm
RF}}_{S}}^{(j)}$ and ${\mathbf{C}}_{S}^{(k)}$, and demonstrates similar
performance despite different types of message drops. This robustness is also
consistently observed across different TL tasks.

TABLE II:  Classification accuracy ($\%$) of FedRF-TCA approach over unreliable networks, on Digit-Five dataset [52] with communication interval $T_{C}=50$. $\mathcal{A}$ represents a random subset of the (source) index set $\\{1,\ldots,K\\}$ (and corresponds to $\mathcal{S}_{t}$ in Algorithm 5), $\mathcal{B}$ is a random subset of $\mathcal{A}$, and $\mathcal{C}$ is a random subset of $\mathcal{B}$ obtained as in Section IV-B. Settings (II) and (III) model the cases where some messages are dropped due to unstable network connection. For example, in setting (III) only $\boldsymbol{\Sigma}_{S}^{(i)}{\boldsymbol{\ell}}_{S}^{(i)}\,$/$\,{\mathbf{W}}_{\operatorname{{\rm RF}}_{S}}^{(j)}\,$/$\,{\mathbf{C}}_{S}^{(k)}$, $i\in\mathcal{A},j\in\mathcal{B},k\in\mathcal{C}$ are exchanged during the training of FedRF-TCA.  Task/Setting | (I) $\mathcal{A}$ / $\mathcal{A}$ / $\mathcal{A}$ | (II) $\mathcal{A}$ / $\mathcal{A}$ / $\mathcal{B}$ | (III) $\mathcal{A}$ / $\mathcal{B}$ / $\mathcal{C}$
---|---|---|---
mm,sv,sy,up$\to$mt | 97.60 | 97.44 | 97.43
mt,sv,sy,up$\to$mm | 65.16 | 64.03 | 64.34
mt,mm,sv,sy$\to$up | 89.99 | 90.19 | 90.45
$12$$25$$50$$100$$200$$400$$800$$0.85$$0.9$$0.95$$1$Communication interval of
classifiers $T_{C}$Accuracymm,sv,sy,up→mtmm,mt,sv,sy→up Figure 4:
Classification accuracy (mean $\pm$ standard deviation) of FedRF-TCA with
different communication intervals $T_{C}\in\\{10,20,50,100,200,400,800\\}$,
with in total $1\,600$ rounds of communication, under the same setting as (I)
of Table II.

We further show in Figure 4 that this robustness to network reliability can be
consistently observed for different choices of the communication interval
$T_{C}$ in Algorithm 5. In particular, the performance gap in Figure 4 for
$T_{C}$ varying from $10$ to $800$ is less than $2\%$, showing the robustness
of FedRF-TCA to messages drops over unreliable networks.

###  V-D Additional experiments of FedRF-TCA

Here, we provide additional numerical results on Office-31 [51], Office-
Caltech [32], Digit-Five [52], and Visda-C [53], showing the advantageous
performance of the proposed FedRF-TCA approach.

TABLE III: Classification accuracy ($\%$) of different DA methods on Office-31 data [51] with single source domain. FedRF-TCA is applied on raw data while others on DeCAF6 features [55].  Methods |  A$\rightarrow$D |  A$\rightarrow$W |  D$\rightarrow$A |  D$\rightarrow$W |  W$\rightarrow$A |  W$\rightarrow$D | Avg
---|---|---|---|---|---|---|---
TCA [20] |  60.24 |  48.55 |  40.75 |  93.08 |  38.90 |  98.99 | 63.42
JDA [31] |  57.42 |  45.53 |  39.43 |  91.06 |  37.06 |  97.59 | 61.34
CORAL [33] |  54.81 |  49.93 |  35.88 |  89.81 |  33.65 |  91.36 | 59.24
GFK [32] |  55.82 |  52.41 |  34.63 |  87.04 |  33.95 |  90.16 | 59.00
DaNN [15] |  49.80 |  50.63 |  35.76 |  87.25 |  36.76 |  90.60 | 58.47
RF-TCA ($N=500$) |  55.62 |  51.06 |  29.42 |  87.92 |  32.58 |  93.57 | 58.36
RF-TCA ($N=1\,000$) |  56.02 |  51.57 |  31.30 |  87.67 |  30.13 |  94.97 | 58.61
FedRF-TCA ($N=1000$) |  80.46 |  76.56 |  56.25 |  92.96 |  59.37 |  99.21 | 77.46

We compare, in Table III, the classification accuracy of different (not
necessarily federated) DA methods on the Office-31 dataset [51]. We observe
that:

  1. 1.

the performance of the proposed RF-TCA approach matches popular DA baselines,
with a significance reduction in both complexity and storage; and

  2. 2.

the FedRF-TCA approach, when applied on raw data and on a non-federated
setting, also establishes remarkably good performance.

TABLE IV: Classification accuracy (%) on Office-Caltech dataset [32] with different federated DA methods. Baseline results are repeated from [14]. Setting (I): all clients average both ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ and ${\mathbf{C}}$ in each communication round; (II): only a random subset $\mathcal{S}_{t}$ of source clients are involved in training; (III): as for (II) with classifier aggregation interval $T_{C}=50$.  Methods | C,D,W$\to$A | A,D,W$\to$C | A,C,W$\to$D | A,C,D$\to$W | Avg
---|---|---|---|---|---
ResNet101 [56] | 81.9 | 87.9 | 85.7 | 86.9 | 85.6
AdaBN [57] | 82.2 | 88.2 | 85.9 | 87.4 | 85.7
AutoDIAL [58] | 83.3 | 87.7 | 85.6 | 87.1 | 85.9
f-DAN111Here, f-DAN is a federated DA method [14] based on DAN [34]. [34, 14] | 82.7 | 88.1 | 86.5 | 86.5 | 85.9
f-DANN222Here, f-DANN is a federated DA method [14] based on DANN [36]. [36, 14] | 83.5 | 88.5 | 85.9 | 87.1 | 86.3
FADA [14] | 84.2 | 88.7 | 87.1 | 88.1 | 87.1
FedRF-TCA (I) | 94.1 | 98.1 | 98.9 | 88.9 | 95.0
FedRF-TCA (II) | 94.6 | 98.7 | 99.1 | 89.6 | 95.5
FedRF-TCA (III) | 94.5 | 98.6 | 98.8 | 90.0 | 95.5
TABLE V: Classification accuracy (%) on Digit-Five dataset [52] with different federated DA methods. Baseline results repeated from [14]. “$\to$ mt” means “mm,sv,sy,up$\to$mt.” Settings (I), (II), and (III) as in Table IV.  Methods |  $\to$mt |  $\to$mm |  $\to$up |  $\to$sv |  $\to$sy | Avg
---|---|---|---|---|---|---
Source Only | 75.4 | 49.6 | 75.5 | 22.7 | 44.3 | 53.5
f-DANN222Here, f-DANN is a federated DA method [14] based on DANN [36]. [36] | 86.1 | 59.5 | 89.7 | 44.3 | 53.4 | 66.6
f-DAN111Here, f-DAN is a federated DA method [14] based on DAN [34]. [34] | 86.4 | 57.5 | 90.8 | 45.3 | 58.4 | 67.7
FADA [14] | 91.4 | 62.5 | 91.7 | 50.5 | 71.8 | 73.6
FedRF-TCA (I) | 97.3 | 64.6 | 89.2 | 41.5 | 43.9 | $67.3$
FedRF-TCA (II) | 97.5 | 65.3 | 89.2 | 41.9 | 43.8 | $67.5$
FedRF-TCA (III) | 97.4 | 64.3 | 89.5 | 41.9 | 44.4 | $67.5$

In Table IV and V, we present a series of experiments highlighting the
exceptional performance of FedRF-TCA in comparison to state-of-the-art
federated DA methods. Furthermore, we emphasize its robustness in scenarios
involving message and/or client dropouts due to poor network conditions.

Notably, our observations in settings (II) and (III) in relation to (I) in
Table IV and table V reveal that exchanging information of only a random
subset $\mathcal{S}_{t}$ of the source clients and asynchronously aggregating
the classifier does _not_ adversely affect the performance of FedRF-TCA.

It is also worth highlighting that FedRF-TCA attains the optimal performance
on the Office-Caltech dataset (Table IV), and consistently delivers comparable
performance on Digit-Five (Table V) and Visda-C datasets (Table VI), all while
significantly reducing communication complexity.

TABLE VI:  Classification accuracy (%) on Visda-C dataset [53]. Baseline
results using the FADE [54] strategy.

Methods | Source only | DANN [36] | CDAN [37] | FedRF-TCA
---|---|---|---|---
Centralized | 46.6 | 57.6 | 73.9 | 64.5
Federated | 54.3 | 56.4 | 73.1 | 62.5

In Appendix D of the appendix, we provide further numerical experiments
showing the advantageous performance and robustness of the proposed FedRF-TCA
approach with classifier aggregation strategies different than FedAvg.

##  VI Conclusion and Perspectives

In this paper, we propose FedRF-TCA, a robust and communication-efficient
federated DA approach based on the improved random features-based TCA (RF-TCA)
approach. The proposed FedRF-TCA approach has a communication complexity that
is (theoretically and practically) nearly _independent_ of the sample size,
and is robust to messages and/or clients dropouts in the network. We further
provide extensive experiments demonstrating the numerical efficiency and
advantageous performance of FedRF-TCA.

By leveraging the block matrix structure inherent in the random feature maps
in 1, FedRF-TCA can readily extend its applicability to scenarios involving
vertical federated learning [38].

More generally, the FedRF-TCA strategy holds the potential for broader use in
other federated MMD-based DA methods. Importantly, it accomplishes this while
delivering substantial reductions in communication and computational
complexity, all without compromising the performance typically associated with
vanilla MMD-based methods.

## Acknowledgments

Z. Liao would like to acknowledge the National Natural Science Foundation of
China (via fund NSFC-62206101 and NSFC-12141107) and the Fundamental Research
Funds for the Central Universities of China (2021XXJS110) for providing
partial support.

R. C. Qiu would like to acknowledge the National Natural Science Foundation of
China (via fund NSFC-12141107), the Interdisciplinary Research Program of HUST
(2023JCYJ012), and the Key Research and Development Program of Guangxi (GuiKe-
AB21196034) for providing partial support.

J. Li’s work has been has been partially supported by the National Key R&D
Program of China No. 2020YFB1710900 and No. 2020YFB1806700, NSFC Grants
61932014 and 62232011.

## References

  * [1] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _Advances in neural information processing systems_ , vol. 33, pp. 1877–1901, 2020.
  * [2] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer, “High-resolution image synthesis with latent diffusion models,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 10 684–10 695.
  * [3] D. Ye, Z. Liu, M. Sun, B. Shi, P. Zhao, H. Wu, H. Yu, S. Yang, X. Wu, Q. Guo _et al._ , “Mastering complex control in moba games with deep reinforcement learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 04, 2020, pp. 6672–6679.
  * [4] J. S. Park, J. C. O’Brien, C. J. Cai, M. R. Morris, P. Liang, and M. S. Bernstein, “Generative agents: Interactive simulacra of human behavior,” _arXiv preprint arXiv:2304.03442_ , 2023.
  * [5] C. Saharia, W. Chan, S. Saxena, L. Li, J. Whang, E. L. Denton, K. Ghasemipour, R. Gontijo Lopes, B. Karagol Ayan, T. Salimans _et al._ , “Photorealistic text-to-image diffusion models with deep language understanding,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 36 479–36 494, 2022.
  * [6] OpenAI, “Gpt-4 technical report,” 2023.
  * [7] S. Karamcheti, S. Nair, A. S. Chen, T. Kollar, C. Finn, D. Sadigh, and P. Liang, “Language-driven representation learning for robotics,” _arXiv preprint arXiv:2302.12766_ , 2023.
  * [8] R. S. Sutton, “The quest for a common model of the intelligent decision maker,” _arXiv preprint arXiv:2202.13252_ , 2022.
  * [9] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [10] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [11] M. Wang and W. Deng, “Deep visual domain adaptation: A survey,” _Neurocomputing_ , vol. 312, pp. 135–153, 2018.
  * [12] A. Smola, A. Gretton, L. Song, and B. Schölkopf, “Algorithmic Learning Theory,” _Lecture Notes in Computer Science_ , pp. 13–31, 2007.
  * [13] A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, and A. Smola, “A Kernel Method for the Two-Sample-Problem,” in _Advances in Neural Information Processing Systems_ , vol. 19. MIT Press. [Online]. Available: https://proceedings.neurips.cc/paper/2006/file/e9fb2eda3d9c55a0d89c98d6c54b5b3e-Paper.pdf
  * [14] X. Peng, Z. Huang, Y. Zhu, and K. Saenko, “Federated adversarial domain adaptation,” _arXiv preprint arXiv:1911.02054_ , 2019.
  * [15] M. Ghifary, W. B. Kleijn, and M. Zhang, “Domain adaptive neural networks for object recognition,” in _Pacific Rim international conference on artificial intelligence_. Springer, 2014, pp. 898–904.
  * [16] Y. Sun, N. Chong, and H. Ochiai, “Feature distribution matching for federated domain generalization,” in _Asian Conference on Machine Learning_. PMLR, 2023, pp. 942–957.
  * [17] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D’Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konecný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, H. Qi, D. Ramage, R. Raskar, M. Raykova, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao, “Advances and Open Problems in Federated Learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, Jun. 2021.
  * [18] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE signal processing magazine_ , vol. 37, no. 3, pp. 50–60, 2020.
  * [19] A. Rahimi and B. Recht, “Random Features for Large-Scale Kernel Machines,” in _Advances in Neural Information Processing Systems_ , ser. NIPS‘08, vol. 20. Curran Associates, Inc., 2008, pp. 1177–1184. [Online]. Available: https://proceedings.neurips.cc/paper/2007/file/013a006f03dbc5392effeb8f18fda755-Paper.pdf
  * [20] S. J. Pan, I. W. Tsang, J. T. Kwok, and Q. Yang, “Domain adaptation via transfer component analysis,” _IEEE transactions on neural networks_ , vol. 22, no. 2, pp. 199–210, 2010.
  * [21] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to algorithms_. MIT press, 2022.
  * [22] N. G. De Bruijn, _Asymptotic methods in analysis_. Courier Corporation, 1981, vol. 4.
  * [23] B. Schölkopf and A. J. Smola, _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_. The MIT Press, 2018.
  * [24] Z. Liao, R. Couillet, and M. W. Mahoney, “A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent,” in _Advances in Neural Information Processing Systems_ , ser. NIPS’20, vol. 33. Curran Associates, Inc., 2020, pp. 13 939—13 950. [Online]. Available: https://proceedings.neurips.cc/paper/2020/file/a03fa30821986dff10fc66647c84c9c3-Paper.pdf
  * [25] A. Vedaldi and A. Zisserman, “Efficient Additive Kernels via Explicit Feature Maps,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 34, no. 3, pp. 480–492, 2012.
  * [26] F. Liu, X. Huang, Y. Chen, and J. A. K. Suykens, “Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. PP, no. 99, pp. 1–1, 2021.
  * [27] C. Louart, Z. Liao, and R. Couillet, “A random matrix approach to neural networks,” _Annals of Applied Probability_ , vol. 28, no. 2, pp. 1190–1248, 2018. [Online]. Available: https://doi.org/10.1214/17-AAP1328
  * [28] R. Couillet and Z. Liao, _Random Matrix Methods for Machine Learning_. Cambridge University Press, 2022.
  * [29] L. Gu, Y. Du, Y. Zhang, D. Xie, S. Pu, R. Qiu, and Z. Liao, “”lossless” compression of deep neural networks: A high-dimensional neural tangent kernel approach,” in _Advances in Neural Information Processing Systems_ , vol. 35. Curran Associates, Inc., 2022, pp. 3774–3787. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2022/file/185087ea328b4f03ea8fd0c8aa96f747-Paper-Conference.pdf
  * [30] S. J. Pan, I. W. Tsang, J. T. Kwok, and Q. Yang, “Domain Adaptation via Transfer Component Analysis,” _IEEE Transactions on Neural Networks_ , vol. 22, no. 2, pp. 199–210, 2011.
  * [31] M. Long, J. Wang, G. Ding, J. Sun, and P. S. Yu, “Transfer feature learning with joint distribution adaptation,” in _Proceedings of the IEEE international conference on computer vision_ , 2013, pp. 2200–2207.
  * [32] B. Gong, Y. Shi, F. Sha, and K. Grauman, “Geodesic flow kernel for unsupervised domain adaptation,” in _2012 IEEE conference on computer vision and pattern recognition_. IEEE, 2012, pp. 2066–2073.
  * [33] B. Sun, J. Feng, and K. Saenko, “Return of frustratingly easy domain adaptation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 30, no. 1, 2016.
  * [34] M. Long, Y. Cao, J. Wang, and M. Jordan, “Learning transferable features with deep adaptation networks,” in _International conference on machine learning_. PMLR, 2015, pp. 97–105.
  * [35] E. Tzeng, J. Hoffman, N. Zhang, K. Saenko, and T. Darrell, “Deep domain confusion: Maximizing for domain invariance,” _arXiv preprint arXiv:1412.3474_ , 2014.
  * [36] Y. Ganin and V. Lempitsky, “Unsupervised domain adaptation by backpropagation,” in _International conference on machine learning_. PMLR, 2015, pp. 1180–1189.
  * [37] M. Long, Z. Cao, J. Wang, and M. I. Jordan, “Conditional adversarial domain adaptation,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [38] B. Gu, Z. Dang, X. Li, and H. Huang, “Federated doubly stochastic kernel learning for vertically partitioned data,” in _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, 2020, pp. 2483–2493.
  * [39] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar, “Federated multi-task learning,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [40] L. Song, C. Ma, G. Zhang, and Y. Zhang, “Privacy-preserving unsupervised domain adaptation in federated setting,” _IEEE Access_ , vol. 8, pp. 143 233–143 240, 2020.
  * [41] H. Kang, Z. Li, and Q. Zhang, “Communicational and computational efficient federated domain adaptation,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 33, no. 12, pp. 3678–3689, 2022.
  * [42] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira, “Analysis of Representations for Domain Adaptation,” in _Advances in Neural Information Processing Systems_ , vol. 19. MIT Press, 2006.
  * [43] S. J. Pan, J. T. Kwok, Q. Yang _et al._ , “Transfer learning via dimensionality reduction.” in _AAAI_ , vol. 8, 2008, pp. 677–682.
  * [44] S. J. Pan and Q. Yang, “A Survey on Transfer Learning,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 22, no. 10, pp. 1345–1359, Oct. 2010.
  * [45] G. H. Golub and C. F. V. Loan, _Matrix Computations_ , 3rd ed., ser. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, 2013. [Online]. Available: https://jhupbooks.press.jhu.edu/title/matrix-computations
  * [46] H. Wang, M. Yurochkin, Y. Sun, D. Papailiopoulos, and Y. Khazaeni, “Federated learning with matched averaging,” _arXiv preprint arXiv:2002.06440_ , 2020\.
  * [47] J. A. Tropp, “An Introduction to Matrix Concentration Inequalities,” _Foundations and Trends® in Machine Learning_ , vol. 8, no. 1-2, pp. 1–230, 2015.
  * [48] U. V. Luxburg, “A tutorial on spectral clustering,” _Statistics and Computing_ , vol. 17, no. 4, pp. 395–416, 2007. [Online]. Available: https://doi.org/10.1007/s11222-007-9033-z
  * [49] A. Joseph and B. Yu, “Impact of regularization on spectral clustering,” _The Annals of Statistics_ , vol. 44, no. 4, pp. 1765–1791, 2016.
  * [50] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in _Advances in Cryptology—EUROCRYPT’99: International Conference on the Theory and Application of Cryptographic Techniques Prague, Czech Republic, May 2–6, 1999 Proceedings 18_. Springer, 1999, pp. 223–238.
  * [51] K. Saenko, B. Kulis, M. Fritz, and T. Darrell, “Adapting visual category models to new domains,” in _European conference on computer vision_. Springer, 2010, pp. 213–226.
  * [52] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky, “Domain-adversarial training of neural networks,” _The journal of machine learning research_ , vol. 17, no. 1, pp. 2096–2030, 2016.
  * [53] X. Peng, B. Usman, N. Kaushik, J. Hoffman, D. Wang, and K. Saenko, “Visda: The visual domain adaptation challenge,” _arXiv preprint arXiv:1710.06924_ , 2017\.
  * [54] J. Hong, Z. Zhu, S. Yu, Z. Wang, H. H. Dodge, and J. Zhou, “Federated adversarial debiasing for fair and transferable representations,” in _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, 2021, pp. 617–627.
  * [55] J. Donahue, Y. Jia, O. Vinyals, J. Hoffman, N. Zhang, E. Tzeng, and T. Darrell, “Decaf: A deep convolutional activation feature for generic visual recognition,” in _International conference on machine learning_. PMLR, 2014, pp. 647–655.
  * [56] K. He, X. Zhang, S. Ren, and J. Sun, “Deep Residual Learning for Image Recognition,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , ser. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2016, pp. 770–778.
  * [57] Y. Li, N. Wang, J. Shi, J. Liu, and X. Hou, “Revisiting batch normalization for practical domain adaptation,” _arXiv preprint arXiv:1603.04779_ , 2016\.
  * [58] F. Maria Carlucci, L. Porzi, B. Caputo, E. Ricci, and S. Rota Bulo, “Autodial: Automatic domain alignment layers,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 5067–5075.
  * [59] R. A. Horn and C. R. Johnson, _Matrix Analysis_ , 2nd ed. Cambridge University Press, 2012. [Online]. Available: http://www.cambridge.org/9780521548236
  * [60] Y. Yu, T. Wang, and R. J. Samworth, “A useful variant of the Davis–Kahan theorem for statisticians,” _Biometrika_ , vol. 102, no. 2, pp. 315–323, 2015.

##  VII Biography Section

If you have an EPS/PDF photo (graphicx package needed), extra braces are
needed around the contents of the optional argument to biography to prevent
the LaTeX parser from getting confused when it sees the complicated
$\backslash$includegraphics command within an optional argument. (You can
create your own custom macro containing the $\backslash$includegraphics
command to make things simpler here.)

##  Appendix A Useful Lemmas

######  Lemma 3 (Sherman–Morrison).

For ${\mathbf{A}}\in\mathbb{R}^{p\times p}$ invertible and
${\mathbf{u}},{\mathbf{v}}\in\mathbb{R}^{p}$,
${\mathbf{A}}+{\mathbf{u}}{\mathbf{v}}^{\sf T}$ is invertible if and only if
$1+{\mathbf{v}}^{\sf T}{\mathbf{A}}^{-1}{\mathbf{u}}\neq 0$ and

$({\mathbf{A}}+{\mathbf{u}}{\mathbf{v}}^{\sf
T})^{-1}={\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}{\mathbf{u}}{\mathbf{v}}^{\sf
T}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{\sf T}{\mathbf{A}}^{-1}{\mathbf{u}}}.$

######  Theorem 3 (Weyl’s inequality, [59, Theorem 4.3.1]).

Let ${\mathbf{A}},{\mathbf{B}}\in\mathbb{R}^{p\times p}$ be symmetric matrices
and let the respective eigenvalues of ${\mathbf{A}}$, ${\mathbf{B}}$ and
${\mathbf{A}}+{\mathbf{B}}$ be arranged in non-decreasing order, i.e.,
$\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{p-1}\leq\lambda_{p}$. Then,
for all $i\in\\{1,\ldots,p\\}$,

$\displaystyle\lambda_{i}({\mathbf{A}}+{\mathbf{B}})\leq\lambda_{i+j}({\mathbf{A}})+\lambda_{p-j}({\mathbf{B}}),\quad
j=0,1,\ldots,p-i,$
$\displaystyle\lambda_{i-j+1}({\mathbf{A}})+\lambda_{j}({\mathbf{B}})\leq\lambda_{i}({\mathbf{A}}+{\mathbf{B}}),\quad
j=1,\ldots,i.$

In particular, taking $i=1$ in the first equation and $i=p$ in the second
equation, together with the fact
$\lambda_{j}({\mathbf{B}})=-\lambda_{p+1-j}(-{\mathbf{B}})$ for
$j=1,\ldots,p$, implies

$\displaystyle\max_{1\leq j\leq
p}|\lambda_{j}({\mathbf{A}})-\lambda_{j}({\mathbf{B}})|\leq\|{\mathbf{A}}-{\mathbf{B}}\|_{2}.$

######  Theorem 4 (Davis–Kahan theorem, [60]).

Under the same notation as in Theorem 3, assume that for a given
$i\in\\{1,\ldots,n\\}$ one has
$\min\\{|\lambda_{i-1}({\mathbf{A}})-\lambda_{i}({\mathbf{A}})|,|\lambda_{i+1}({\mathbf{A}})-\lambda_{i}({\mathbf{A}})|>0$,
then the corresponding eigenvectors satisfy

$\sin\Theta\left({\mathbf{u}}_{i}({\mathbf{A}}+{\mathbf{B}}),{\mathbf{u}}_{i}({\mathbf{A}})\right)\leq\frac{2\|{\mathbf{B}}\|_{2}}{\min\\{|\lambda_{i-1}({\mathbf{A}})-\lambda_{i}({\mathbf{A}})|,|\lambda_{i+1}({\mathbf{A}})-\lambda_{i}({\mathbf{A}})|\\}},$
(13)

where we denote ‘$\sin\Theta$’ the alignment between two vectors
${\mathbf{u}}_{1},{\mathbf{u}}_{2}\in\mathbb{R}^{n}$ as

$\Theta({\mathbf{u}}_{1},{\mathbf{u}}_{2})\equiv\arccos\left(\frac{{\mathbf{u}}_{1}^{\sf
T}{\mathbf{u}}_{2}}{\|{\mathbf{u}}_{1}\|_{2}\cdot\|{\mathbf{u}}_{2}\|_{2}}\right),$
(14)

that satisfies
$\|{\mathbf{u}}_{1}-{\mathbf{u}}_{2}\|\leq\sqrt{2}\sin\Theta({\mathbf{u}}_{1},{\mathbf{u}}_{2})$.

##  Appendix B Facts and Discussions about Vanilla TCA

Here, we discuss some interesting properties of the vanilla TCA approach in
(TCA).

Recall from 1 that the “transformed” features obtained by vanilla TCA is given
by the top eigenspace of

${\mathbf{A}}\equiv{\mathbf{H}}\left({\mathbf{K}}^{2}-\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}\right){\mathbf{H}},$ (15)

as defined in (4). As a consequence, we have the following remark on the
regularization parameter $\gamma$ of vanilla TCA.

######  Remark 3 (On regularization of vanilla TCA).

Per its definition in (2) and let
$\lambda_{\max}({\mathbf{K}})\geq\lambda_{\min}({\mathbf{K}})\geq 0$ denote
the maximum and minimum eigenvalue of ${\mathbf{K}}$, one has
$\|{\boldsymbol{\ell}}\|_{2}^{2}=\frac{n}{n_{S}n_{T}}$, and that the (only)
non-zero eigenvalue of
$\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$ is $\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$ with

$\frac{\lambda_{\min}^{4}({\mathbf{K}})n}{\gamma
n_{S}n_{T}+\lambda_{\min}^{2}({\mathbf{K}})n}\leq\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}\leq\frac{\lambda_{\max}^{4}({\mathbf{K}})n}{\gamma
n_{S}n_{T}+\lambda_{\max}^{2}({\mathbf{K}})n}.$ (16)

As such, for $\lambda_{\min}({\mathbf{K}}),\lambda_{\max}({\mathbf{K}})$ both
of order $\Theta(1)$ with respect to $n$, one has:

  1. 1.

if the number of source and target data are “balanced”, in the sense that both
$n_{S},n_{T}$ are of order $\Theta(n)$, then the rank-one matrix
$\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$ is of spectral norm order $\Theta(1)$,
and thus “on even ground” with ${\mathbf{K}}^{2}$ (that is, the spectral norm
of the rank-one matrix is of the same order as ${\mathbf{K}}^{2}$ even for $n$
large), _if and only if_ one sets $\gamma=\Theta(n^{-1})$; and

  2. 2.

if the number of source and target data are “unbalanced” with
$n_{S}=\Theta(1)$ and $n_{T}=\Theta(n)$, or $n_{S}=\Theta(n)$ and
$n_{T}=\Theta(1)$ (recall that $n_{S}+n_{T}=n$), then
$\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$ is “on even ground” with
${\mathbf{K}}^{2}$ in a spectral norm sense _if and only if_
$\gamma=\Theta(1)$.

A similar statement can be made for the R-TCA approach introduced in Section
III-A.

###### Proof of 3.

Since $\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\mathbf{K}}^{2}{\boldsymbol{\ell}}={\mathbf{K}}^{2}{\boldsymbol{\ell}}\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$, so the (only) non-zero eigenvalue of
$\frac{{\mathbf{K}}^{2}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$ is $\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$.

$\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}=\frac{\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}},\text{
and }\frac{\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}=1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}$ (17)

We perform an eigenvalue decomposition ${\mathbf{K}}=U\Lambda U^{T}$, where
$\Lambda$ is the eigenvalue matrix, so ${\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}={\boldsymbol{\ell}}^{\sf
T}(U\Lambda^{4}U^{T}){\boldsymbol{\ell}}$. And since
$\lambda_{\max}({\mathbf{K}})$ and $\lambda_{\min}({\mathbf{K}})$ denote the
maximum and minimum eigenvalue of ${\mathbf{K}}$, so we get
$\lambda_{\min}^{2}({\mathbf{K}})\leq\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}\leq\lambda_{\max}^{2}({\mathbf{K}})$
and $\lambda_{\min}^{2}({\mathbf{K}})\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}\leq\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}\leq\lambda_{\max}^{2}({\mathbf{K}})\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}$.

For the right-hand side term in Equation 17, we have the following expression:

$1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\lambda_{\min}^{2}({\mathbf{K}})}\leq
1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}\leq
1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\lambda_{\max}^{2}({\mathbf{K}})}$
(18)

So, we get

$\displaystyle\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}$
$\displaystyle=\frac{\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}\leq\frac{\lambda_{\min}^{2}({\mathbf{K}})\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}=\lambda_{max}^{2}({\mathbf{K}})\left(1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}\right)$
(19)
$\displaystyle\leq\lambda_{max}^{2}({\mathbf{K}})\left(1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\lambda_{\max}^{2}({\mathbf{K}})}\right)=\frac{\lambda_{\max}^{4}({\mathbf{K}})n}{\gamma
n_{S}n_{T}+\lambda_{\max}^{2}({\mathbf{K}})n}$ (20)

$\displaystyle\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{4}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}\geq\lambda_{min}^{2}({\mathbf{K}})\left(1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}\right)\geq\lambda_{min}^{2}({\mathbf{K}})\left(1-\frac{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}}{\frac{\gamma}{\|{\boldsymbol{\ell}}\|_{2}^{2}}+\lambda_{\min}^{2}({\mathbf{K}})}\right)=\frac{\lambda_{\min}^{4}({\mathbf{K}})n}{\gamma
n_{S}n_{T}+\lambda_{\min}^{2}({\mathbf{K}})n}$ (21)

Thus we concludes the proof of 3 ∎

Figure 5 provides numerical evidence for Remark 3, by showing the performance
of vanilla TCA as a function of the regularization parameter $\gamma$, for
Amazon to Webcam from the Office-31 dataset, with $n_{S}=2817$ and
$n_{T}=795$. In accordance with 3, the classification accuracy of vanilla TCA
varies as a function of regularization $\gamma$ _only_ when $\gamma$ belongs
to a specific interval (marked in gray in Figure 5(a)). A similar behavior can
be observed for R-TCA in Figure 5(b).

Remark 3 is of direct algorithmic use in the search of optimal regularization
parameter $\gamma$ for vanilla TCA, R-TCA, and consequently RF-TCA.

$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$0.46$$0.48$$0.5$$0.52$$0.54$$\gamma$Accuracy
(a)

$10^{-2}$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$\gamma$ (b)

Figure 5:  Classification accuracy versus the regularization parameter
$\gamma$ on DECAF6 features of Office-31 data for $n_{S}=2817$ (Amazon),
$n_{T}=795$ (Webcam) using a SVM classifier. Here, ${\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}^{2}{\boldsymbol{\ell}}=10^{-0.793}=0.1607$ and
${\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}=10^{-1.874}=0.01336$.

##  Appendix C Proof of 2

In this section, we present the proof of 2.

Before we go into the detailed proof of 2, recall first from 2 in Section
III-A that the R-TCA approach defined in (R-TCA) is “equivalent” to the
vanilla TCA up to a change of variable in the regularization. As such, it
suffices to study the behavior of the R-TCA, the solution ${\mathbf{W}}_{\rm
R}$ of which satisfies

${\mathbf{A}}_{\rm R}\cdot{\mathbf{H}}{\mathbf{K}}{\mathbf{W}}_{\rm
R}\equiv\frac{1}{\gamma}{\mathbf{H}}\left({\mathbf{K}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}\right){\mathbf{H}}\cdot{\mathbf{H}}{\mathbf{K}}{\mathbf{W}}_{\rm
R}={\mathbf{H}}{\mathbf{K}}{\mathbf{W}}_{\rm R}\cdot\boldsymbol{\Lambda}_{\rm
R},$ (22)

per the Sherman–Morrison lemma (3) for $\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}\neq 0$.

As for R-TCA, it can be checked that also be shown that the transferred
features ${\mathbf{W}}_{\operatorname{{\rm RF}}}$ obtained by RF-TCA take a
similar as

${\mathbf{A}}_{\operatorname{{\rm
RF}}}\cdot{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm
RF}}}\equiv{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}(\boldsymbol{\Sigma}{\mathbf{L}}\boldsymbol{\Sigma}^{\sf
T}+\gamma{\mathbf{I}}_{2N})^{-1}\boldsymbol{\Sigma}{\mathbf{H}}\cdot{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm RF}}}={\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm
RF}}}\cdot\boldsymbol{\Lambda}_{\operatorname{{\rm RF}}},$ (23)

with diagonal $\boldsymbol{\Lambda}_{\operatorname{{\rm
RF}}}\in\mathbb{R}^{m\times m}$ containing the largest $m$ eigenvalues of
$(\boldsymbol{\Sigma}{\mathbf{L}}\boldsymbol{\Sigma}^{\sf
T}+\gamma{\mathbf{I}}_{2N})^{-1}\boldsymbol{\Sigma}{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}$, and thus of the symmetric matrix

${\mathbf{A}}_{\operatorname{{\rm RF}}}={\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}(\boldsymbol{\Sigma}{\mathbf{L}}\boldsymbol{\Sigma}^{\sf
T}+\gamma{\mathbf{I}}_{2N})^{-1}\boldsymbol{\Sigma}{\mathbf{H}}=\frac{1}{\gamma}{\mathbf{H}}\left(\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-\frac{\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}}\right){\mathbf{H}},$ (24)

again up to row and column centering via ${\mathbf{H}}$.

Comparing (22) against (24), we see that the RF-TCA formulation takes a
similar form to the that of R-TCA, with the RFF Gram matrix
$\boldsymbol{\Sigma}^{\sf T}\boldsymbol{\Sigma}$ instead of the Gaussian
kernel matrix ${\mathbf{K}}={\mathbf{K}}_{\operatorname{{\rm Gauss}}}$. Since
$\boldsymbol{\Sigma}^{\sf T}\boldsymbol{\Sigma}$ well approximates
${\mathbf{K}}$ in a spectral norm sense for $N$ large, by Theorem 1, one may
expect that the two matrices ${\mathbf{A}}_{\rm R}$ and
${\mathbf{A}}_{\operatorname{{\rm RF}}}$ are also close in spectral norm. This
is precisely given in the following result, the proof of which follows from an
(almost immediate) application of Theorem 1.

######  Corollary 1.

For a given data matrix ${\mathbf{X}}\in\mathbb{R}^{p\times n}$, denote the
associated Gaussian kernel matrix ${\mathbf{K}}_{\operatorname{{\rm
Gauss}}}={\mathbf{K}}\in\mathbb{R}^{n\times n}$ and the random Fourier
features matrix $\boldsymbol{\Sigma}\in\mathbb{R}^{2N\times n}$ as in 1. Then,
for any given $\varepsilon\in(0,1)$, there exists a universal constant $C>0$
such that if $N\geq C\dim({\mathbf{K}})\log(n)/\varepsilon^{2}$, the following
(expected) relative spectral norm error bound holds

$\frac{\mathbb{E}\left\|{\mathbf{K}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}-(\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-\frac{\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}})\right\|_{2}}{\|{\mathbf{K}}\|_{2}}\leq\varepsilon.$
(25)

###### Proof of 1.

In the sequel, we will use the shortcut notation
$\hat{\mathbf{K}}\equiv\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}\in\mathbb{R}^{n\times n}$. We aim to bound the following
expected operator norm difference

$\mathbb{E}\left\|{\mathbf{K}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}-\left(\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-\frac{\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}}\right)\right\|_{2}=\mathbb{E}\left\|{\mathbf{K}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}-\left(\hat{\mathbf{K}}-\frac{\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}}\right)\right\|_{2}.$ (26)

First, we have, for
$\mathbb{E}\|{\mathbf{K}}-\hat{\mathbf{K}}\|_{2}\leq\varepsilon$, by
$\|{\mathbf{A}}+{\mathbf{B}}\|_{2}\leq\|{\mathbf{A}}\|_{2}+\|{\mathbf{B}}\|_{2}$,
$\|{\mathbf{A}}{\mathbf{B}}\|_{2}\leq\|{\mathbf{A}}\|_{2}\cdot\|{\mathbf{B}}\|_{2}$,
and $\gamma>0$ that

$\displaystyle\mathbb{E}\left\|\frac{\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}\right\|_{2}\leq\mathbb{E}\left[\frac{\left\|\gamma(\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$
$\displaystyle\leq\mathbb{E}\left[\frac{\left\|\gamma(\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]+\mathbb{E}\left[\frac{\left\|{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right].$ (27)

Then, for the first right-hand side term in (C), we have

$\displaystyle\mathbb{E}\left[\frac{\left\|\gamma(\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$
$\displaystyle=\mathbb{E}\left[\frac{\gamma\left\|(\hat{\mathbf{K}}-{\mathbf{K}}){\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$
$\displaystyle\leq\gamma\mathbb{E}\left[\frac{\left\|\hat{\mathbf{K}}-{\mathbf{K}}\right\|_{2}\cdot{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]+\gamma\mathbb{E}\left[\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}\cdot\left\|\hat{\mathbf{K}}-{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$
$\displaystyle\leq\frac{\gamma\mathbb{E}\left\|\hat{\mathbf{K}}-{\mathbf{K}}\right\|_{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}+\frac{\gamma\mathbb{E}\left\|\hat{\mathbf{K}}-{\mathbf{K}}\right\|_{2}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}}\leq 2\varepsilon,$ (28)

where we use the fact that $\frac{{\boldsymbol{\ell}}^{\sf
T}{\mathbf{Z}}{\boldsymbol{\ell}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{Z}}{\boldsymbol{\ell}}}\leq 1$ for p.s.d.
${\mathbf{Z}}=\hat{\mathbf{K}},{\mathbf{K}}$ and $\gamma>0$ in the third
inequality, and that $\frac{\gamma}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{Z}}{\boldsymbol{\ell}}}\leq 1$ as well as
$\mathbb{E}\|{\mathbf{K}}-\hat{\mathbf{K}}\|_{2}\leq\varepsilon$ in the fourth
inequality.

For the second right-hand side term in (C), we have, again for
$\mathbb{E}\|{\mathbf{K}}-\hat{\mathbf{K}}\|\leq\varepsilon$ that

$\displaystyle\mathbb{E}\left[\frac{\left\|\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$
$\displaystyle=\mathbb{E}\left[\frac{\left\|\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}-{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$
$\displaystyle\leq\mathbb{E}\left[\frac{\left\|(\hat{\mathbf{K}}-{\mathbf{K}}){\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]+\mathbb{E}\left[\frac{\left\|{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}({\mathbf{K}}-\hat{\mathbf{K}}){\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]+\mathbb{E}\left[\frac{\left\|{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}(\hat{\mathbf{K}}-{\mathbf{K}})\right\|_{2}}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]$ $\displaystyle\leq
3\cdot\mathbb{E}\left[\frac{\left\|\hat{\mathbf{K}}-{\mathbf{K}}\right\|_{2}({\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})({\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})}{(\gamma+{\boldsymbol{\ell}}^{\sf
T}\hat{\mathbf{K}}{\boldsymbol{\ell}})(\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}})}\right]\leq 3\varepsilon.$

Putting together, this gives, for
$\mathbb{E}\left\|{\mathbf{K}}-\hat{\mathbf{K}}\right\|_{2}\leq\varepsilon$
that

$\mathbb{E}\left[\left\|{\mathbf{K}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}-\left(\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-\frac{\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}}\right)\right\|_{2}\right]\leq
5\varepsilon,$ (29)

which, together with Theorem 1, concludes the proof of Corollary 1. ∎

With 1 at hand, we are ready to present the proof of 2 as follows.

###### Proof of 2.

Note from (22) and (23) that the columns of
${\mathbf{H}}{\mathbf{K}}{\mathbf{W}}_{\rm R}\in\mathbb{R}^{n\times m}$ and
${\mathbf{H}}\boldsymbol{\Sigma}^{\sf T}{\mathbf{W}}_{\operatorname{{\rm
RF}}}\in\mathbb{R}^{n\times m}$ are in fact the top $m$ eigenvectors
${\mathbf{u}}_{i}({\mathbf{A}}_{\rm
R}),{\mathbf{u}}_{i}({\mathbf{A}}_{\operatorname{{\rm
RF}}})\in\mathbb{R}^{n},i\in\\{1,\ldots,m\\}$, of ${\mathbf{A}}_{\rm
R}\equiv{\mathbf{H}}{\mathbf{K}}(\gamma{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}$ and
${\mathbf{A}}_{\operatorname{{\rm
RF}}}\equiv{\mathbf{H}}\boldsymbol{\Sigma}^{\sf
T}(\gamma{\mathbf{I}}_{2N}+\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf T})^{-1}\boldsymbol{\Sigma}{\mathbf{H}}$,
respectively. As such, the Frobenius norm error satisfies

$\mathbb{E}\left[\|{\mathbf{H}}(\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm RF}}}-{\mathbf{K}}{\mathbf{W}}_{\rm
R})\|_{2}^{2}\right]=\sum_{i=1}^{m}\mathbb{E}\left[\|{\mathbf{u}}_{i}({\mathbf{A}}_{\operatorname{{\rm
RF}}})-{\mathbf{u}}_{i}({\mathbf{A}}_{\rm R})\|_{2}^{2}\right].$ (30)

It then follows from Davis–Kahan theorem [60], Theorem 4 in Appendix A, that

$\displaystyle\left\|{\mathbf{u}}_{i}({\mathbf{A}}_{\operatorname{{\rm
RF}}})-{\mathbf{u}}_{i}({\mathbf{A}}_{\rm R})\right\|_{2}$
$\displaystyle\leq\sqrt{2}\sin\Theta\left({\mathbf{u}}_{i}({\mathbf{A}}_{\operatorname{{\rm
RF}}}),{\mathbf{u}}_{i}({\mathbf{A}}_{\rm R})\right)$
$\displaystyle\leq\frac{2\sqrt{2}\left\|{\mathbf{A}}_{\operatorname{{\rm
RF}}}-{\mathbf{A}}_{\rm
R}\right\|_{2}}{\min\\{|\lambda_{i-1}({\mathbf{A}}_{\rm
R})-\lambda_{i}({\mathbf{A}}_{\rm R})|,|\lambda_{i+1}({\mathbf{A}}_{\rm
R})-\lambda_{i}({\mathbf{A}}_{\rm R})|\\}},$ (31)

with ‘$\sin\Theta({\mathbf{u}}_{1},{\mathbf{u}}_{2})$ the “sine similarity”
between two vectors ${\mathbf{u}}_{1},{\mathbf{u}}_{2}\in\mathbb{R}^{n}$ with
$\Theta({\mathbf{u}}_{1},{\mathbf{u}}_{2})\equiv\arccos\left(\frac{{\mathbf{u}}_{1}^{\sf
T}{\mathbf{u}}_{2}}{\|{\mathbf{u}}_{1}\|_{2}\cdot\|{\mathbf{u}}_{2}\|_{2}}\right)$
that satisfies
$\|{\mathbf{u}}_{1}-{\mathbf{u}}_{2}\|_{2}\leq\sqrt{2}\Theta({\mathbf{u}}_{1},{\mathbf{u}}_{2})$.

Further note that for
$\mathbb{E}\left\|{\mathbf{K}}-\frac{{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}}{\boldsymbol{\ell}}}-(\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}-\frac{\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}}{\gamma+{\boldsymbol{\ell}}^{\sf
T}\boldsymbol{\Sigma}^{\sf
T}\boldsymbol{\Sigma}{\boldsymbol{\ell}}})\right\|_{2}\leq\varepsilon\|{\mathbf{K}}\|_{2}$,
one has

$\mathbb{E}\left\|{\mathbf{A}}_{\operatorname{{\rm RF}}}-{\mathbf{A}}_{\rm
R}\right\|_{2}\leq\|{\mathbf{H}}\|_{2}\cdot\varepsilon\|{\mathbf{K}}\|_{2}\cdot\|{\mathbf{H}}\|_{2}\leq\varepsilon\|{\mathbf{K}}\|_{2},$
(32)

where we use the fact that $\|{\mathbf{H}}\|=1$, and therefore

$\displaystyle\mathbb{E}\left[\left\|{\mathbf{H}}(\boldsymbol{\Sigma}^{\sf
T}{\mathbf{W}}_{\operatorname{{\rm
RF}}}-{\mathbf{K}}{\mathbf{W}})\right\|_{2}^{2}\right]=\sum_{i=1}^{m}\mathbb{E}\left[\left\|{\mathbf{u}}_{i}({\mathbf{A}}_{\operatorname{{\rm
RF}}})-{\mathbf{u}}_{i}({\mathbf{A}}_{\rm
R})\right\|_{2}^{2}\right]\leq\frac{8m\varepsilon^{2}}{(\Delta_{\lambda}/\|{\mathbf{K}}\|_{2})^{2}}=\frac{8m\varepsilon^{2}}{\tilde{\Delta}_{\lambda}^{2}},$
(33)

where we recall that $\Delta_{\lambda}\equiv\min_{1\leq i\leq
m}\left|\lambda_{i}({\mathbf{A}}_{\rm R})-\lambda_{i+1}({\mathbf{A}}_{\rm
R})\right|>0$ denotes the _eigen-gap_ of ${\mathbf{A}}_{\rm
R}\equiv{\mathbf{H}}{\mathbf{K}}(\gamma{\mathbf{K}}+{\mathbf{K}}{\boldsymbol{\ell}}{\boldsymbol{\ell}}^{\sf
T}{\mathbf{K}})^{-1}{\mathbf{K}}{\mathbf{H}}$, as well as the _relative eigen-
gap_

$\tilde{\Delta}_{\lambda}\equiv\Delta/\|{\mathbf{K}}\|_{2},$ (34)

as in the statement of 2. Applying Corollary 1, we concludes the proof of
Theorem 2. ∎

##  Appendix D Additional numerical experiments

###  D-A Additional numerical experiments on RF-TCA

####  D-A1 Experiments setting

In this section, we provide additional experimental results on RF-TCA. All
experiments are performed on a machine with Intel(R) Core(TM) i7-7700 CPU @
3.60GHz and 3090Ti GPU.

Below are the details of experiment in this section:

  * •

Datasets: The Office-Caltech [32] dataset has $4$ subsets (Amazon, Caltech,
Dslr and Webcam) with $10$ classes in each subset. The Office-31 [51] dataset
has $3$ subsets (Amazon, Dslr and Webcam) with $31$ classes in each subset.
Experiments are performed on DECAF6 features [55] of both datasets.333All
datasets are available at https://github.com/SadAngelF/FedRF-TCA. Both source
and target data vectors are normalized to have unit Euclidean norms.

  * •

Classifiers: We use $3$ types of classifiers in this section: fully-connected
neural network (FCNN), support vector machine (SVM) and k-nearest neighbor
(kNN). FCNN is a fully-connected neural network with two hidden layers (having
$100$ neurons per layer). SVM uses the (Gaussian) RBF kernel and follows the
same hyperparameter searching protocol as below. And the parameter $k$ of kNN
is $1$.

  * •

Hyperparameters: There are five hyperparameters in RF-TCA: the number of
random features $N$, the dimension of common feature space $m$, the
regularization parameter $\gamma$, and the Gaussian (width) kernel parameter
$\sigma$ in ${\mathbf{K}}_{\operatorname{{\rm
Gauss}}}=\\{\exp(-\|{\mathbf{x}}_{i}-{\mathbf{x}}_{j}\|^{2}/(2\sigma^{2}))\\}_{i,j=1}^{n}$.
We choose $m=100$, and search $\gamma$ in the set
$\\{10^{-3},10^{-2},10^{-1},1,10^{1},10^{2},10^{3}\\}$, the Gaussian (width)
parameter $\sigma$ in the set $\\{5,6,\cdots,14,15\\}$. For each test, we
perform hyperparameter search in the range above and report the best
performance.

####  D-A2 Numerical results on RF-TCA

TABLE VII:  Classification accuracy ($\%$) of different DA methods on Office-Caltech dataset with single source domain. Methods are applied on DeCAF6 features [55]. Methods | TCA |  RF-TCA (with $N=1\,000$) |  RF-TCA (with $N=500$) | Vanilla TCA | JDA | CORAL | GFK | DaNN
---|---|---|---|---|---|---|---|---
A$\rightarrow$C | 81.03 | 76.49 | 76.04 | 80.76 | 81.12 | 84.32 | 82.57 | 83.92
A$\rightarrow$D | 83.43 | 83.43 | 80.25 | 87.89 | 84.07 | 84.71 | 0.8535 | 83.00
A$\rightarrow$W | 74.57 | 66.10 | 68.13 | 73.55 | 65.76 | 73.89 | 75.93 | 75.67
C$\rightarrow$A | 87.89 | 91.02 | 91.44 | 87.78 | 87.99 | 92.37 | 92.42 | 90.30
C$\rightarrow$D | 63.69 | 90.44 | 89.17 | 58.59 | 57.32 | 88.53 | 89.38 | 90.00
C$\rightarrow$W | 62.71 | 79.32 | 77.28 | 61.01 | 58.64 | 79.32 | 83.50 | 79.67
D$\rightarrow$A | 82.15 | 74.53 | 69.93 | 81.31 | 79.64 | 85.07 | 79.91 | 79.60
D$\rightarrow$C | 52.89 | 59.75 | 58.50 | 50.75 | 48.88 | 76.84 | 78.57 | 73.92
D$\rightarrow$W | 80.00 | 90.84 | 90.50 | 80.00 | 80.00 | 97.96 | 99.10 | 96.67
W$\rightarrow$A | 77.55 | 72.86 | 69.93 | 77.97 | 76.82 | 77.66 | 75.21 | 74.00
W$\rightarrow$C | 62.42 | 58.05 | 55.03 | 59.83 | 63.49 | 70.79 | 72.62 | 68.50
W$\rightarrow$D | 91.08 | 100.00 | 100.00 | 91.71 | 86.62 | 100.00 | 100.00 | 100.00
Avg | 74.95 | 78.57 | 77.18 | 74.26 | 72.52 | 84.29 | 84.54 | 83.24
TABLE VIII:  Running time (s) of different DA methods on Office-Caltech dataset with single source domain. Methods are applied on DeCAF6 features [55]. Methods | TCA |  RF-TCA (with $N=1\,000$) |  RF-TCA (with $N=500$) | Vanilla TCA | JDA | CORAL | GFK | DaNN
---|---|---|---|---|---|---|---|---
A$\rightarrow$C | 38.76 | 2.812 | 0.6355 | 3.072 | 604.7 | 92.91 | 117.6 | 983.6
A$\rightarrow$D | 5.231 | 2.349 | 0.4795 | 0.5285 | 180.9 | 90.27 | 191.3 | 973.8
A$\rightarrow$W | 7.981 | 2.438 | 0.4993 | 0.7088 | 203.3 | 87.09 | 191.5 | 957.5
C$\rightarrow$A | 38.63 | 2.892 | 0.6337 | 3.067 | 588.1 | 89.51 | 124.9 | 1004
C$\rightarrow$D | 10.92 | 2.569 | 0.5157 | 0.7563 | 249.0 | 90.99 | 117.9 | 955.6
C$\rightarrow$W | 10.75 | 2.538 | 0.5471 | 0.9705 | 251.8 | 88.10 | 119.8 | 947.4
D$\rightarrow$A | 5.356 | 2.373 | 0.4776 | 0.5294 | 183.9 | 89.27 | 185.1 | 924.4
D$\rightarrow$C | 10.99 | 2.475 | 0.4985 | 0.7536 | 249.1 | 90.44 | 116.3 | 947.4
D$\rightarrow$W | 0.2790 | 0.4151 | 0.4116 | 0.07043 | 81.59 | 87.74 | 187.6 | 908.7
W$\rightarrow$A | 7.774 | 2.459 | 0.4993 | 0.7024 | 210.4 | 86.76 | 184.7 | 959.9
W$\rightarrow$C | 10.66 | 2.527 | 0.5304 | 0.9671 | 245.5 | 87.18 | 123.4 | 965.5
W$\rightarrow$D | 0.2802 | 2.387 | 0.4131 | 0.07328 | 82.09 | 87.92 | 186.6 | 975.3
Avg | 12.30 | 2.353 | 0.5118 | 1.016 | 260.9 | 89.01 | 153.9 | 961.8
TABLE IX:  Classification accuracy ($\%$) of different DA methods on Office-31 dataset with single source domain. Methods are applied on DeCAF6 features [55]. Methods | TCA |  RF-TCA (with $N=1\,000$) |  RF-TCA (with $N=500$) | Vanilla TCA | JDA | CORAL | GFK | DaNN
---|---|---|---|---|---|---|---|---
A$\rightarrow$D | 60.24 | 56.02 | 55.62 | 59.83 | 57.42 | 54.81 | 55.82 | 49.80
A$\rightarrow$W | 48.55 | 51.57 | 51.06 | 47.29 | 45.53 | 49.93 | 52.41 | 50.63
D$\rightarrow$A | 40.75 | 31.30 | 29.42 | 39.61 | 39.43 | 35.88 | 34.63 | 35.76
D$\rightarrow$W | 93.08 | 87.67 | 87.92 | 92.95 | 91.06 | 89.81 | 87.04 | 87.25
W$\rightarrow$A | 38.90 | 30.13 | 32.58 | 39.33 | 37.06 | 33.65 | 33.95 | 36.76
W$\rightarrow$D | 98.99 | 94.97 | 93.57 | 97.79 | 97.59 | 91.36 | 90.16 | 90.60
Avg | 63.42 | 58.61 | 58.36 | 62.80 | 61.34 | 59.24 | 59.00 | 58.47
TABLE X:  Running time (s) of different DA methods on Office-31 dataset with single source domain. Methods are applied on DeCAF6 features [55]. Methods | TCA |  RF-TCA (with $N=1\,000$) |  RF-TCA (with $N=500$) | Vanilla TCA | JDA | CORAL | GFK | DaNN
---|---|---|---|---|---|---|---|---
A$\rightarrow$D | 206.2 | 3.257 | 0.8764 | 13.48 | 2207 | 96.64 | 125.9 | 6078
A$\rightarrow$W | 265.4 | 3.459 | 0.9498 | 17.28 | 2911 | 93.35 | 133.2 | 6066
D$\rightarrow$A | 208.0 | 3.415 | 0.8695 | 13.49 | 2211 | 93.06 | 124.4 | 5783
D$\rightarrow$W | 11.16 | 2.365 | 0.4760 | 0.8867 | 243.8 | 86.94 | 116.5 | 5545
W$\rightarrow$A | 266.9 | 3.428 | 0.9389 | 17.32 | 2779 | 93.38 | 127.3 | 5941
W$\rightarrow$D | 11.13 | 2.343 | 0.4953 | 0.8869 | 251.1 | 88.64 | 128.8 | 5620
Avg | 161.5 | 3.045 | 0.7676 | 10.55 | 1767 | 92.00 | 126.0 | 5839

As demonstrated in Table VII, Table VIII, Table IX and Table X, the RF-TCA
method achieves performance comparable to other methods while requiring
significantly less runtime. Furthermore, as the dataset size increases, the
computational efficiency of the RF-TCA method becomes even more pronounced.

TABLE XI: Classification accuracy ($\%$) of different kernels of RF-TCA (with $N=500$) on Office-Caltech dataset with DECAF6 features. Kernel | A$\rightarrow$C | A$\rightarrow$D | A$\rightarrow$W | C$\rightarrow$A | C$\rightarrow$D | C$\rightarrow$W | D$\rightarrow$A | D$\rightarrow$C | D$\rightarrow$W | W$\rightarrow$A | W$\rightarrow$C | W$\rightarrow$D | Avg
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Laplace | 81.57 | 80.25 | 69.15 | 90.29 | 89.81 | 77.29 | 70.25 | 59.22 | 75.93 | 72.55 | 57.35 | 96.82 | 76.70
Gauss | 76.04 | 80.25 | 68.13 | 91.44 | 89.17 | 77.28 | 69.93 | 58.50 | 90.50 | 69.93 | 55.03 | 100.00 | 77.18
TABLE XII: Classification accuracy ($\%$) of different kernels of RF-TCA (with $N=500$) on Office-31 dataset with DECAF6 features. Kernel | A$\rightarrow$D | A$\rightarrow$W | D$\rightarrow$A | D$\rightarrow$W | W$\rightarrow$A | W$\rightarrow$D | Avg
---|---|---|---|---|---|---|---
Laplace | 59.64 | 50.44 | 35.78 | 87.80 | 34.26 | 93.98 | 60.32
Gauss | 55.62 | 51.06 | 29.42 | 87.92 | 32.58 | 93.57 | 58.36

While our primary focus in this work is on the Gaussian kernel, it is worth
noting that the RF-TCA method is applicable to other kernel functions, as
demonstrated in both Table XI and Table XII.

###  D-B Additional source classifier adaptation strategies on FedRF-TCA

####  D-B1 Experiments setting

In this section, we provide additional experimental results on FedRF-TCA.

Below are the details of experiment in this section:

  * •

Datasets: The Office-Caltech [32] dataset has $4$ subsets (Amazon, Caltech,
Dslr and Webcam) with $10$ classes in each subset. The Digit-Five [36] dataset
has $5$ subsets (Mnist, MNIST-M, USPS, SVHN, Synthetic Digits) with $10$
classes in each subset. . Experiments are performed on raw data oof both
datasets.

  * •

Classifiers: We only use fully-connected neural network (FCNN). FCNN is a
fully-connected neural network with two hidden layers (having $100$ neurons
per layer).

  * •

Hyperparameters: The FedRF-TCA model shares the same five hyperparameters as
the RF-TCA model.

####  D-B2 One-shot performance for FedRF-TCA

In Algorithm 5, though clients only need to transmit source classifiers every
$T_{C}$ round, we attempt to figure out whether the performance remains the
same if clients only transmit source classifiers once at the end of training.
Thus we conduct a ablation experiment as in Figure 6 based on the same setting
as Figure 4 with extra experiment when $T_{C}=1600$. The performance when
source classifiers are only transmitted once (the total round number is $1600$
and $T_{C}=1600$) is very unstable.

$12$$25$$50$$100$$200$$400$$800$$1600$$0$$0.5$$1$communication cycles of
classifiers ($\rm T_{C}$)Accuracymm,sv,sy,up→mtmm,mt,sv,sy→upmt,sv,sy,up→mm
Figure 6: Classification accuracy (%) of FedRF-TCA on Digit-Five dataset [52]
for different communication cycles $\rm
T_{C}\in\\{10,20,50,100,200,400,800,1600\\}$ , and total round number is
$1600$. The setting is the same as (I) in Table II. The red line represents
the average accuracy, while the vertical gray lines indicate the standard
deviation. In order to enhance clarity, we have slightly spaced out the x-axis
values for the experiment at $T_{C}=1600$.

We cancel the source classifiers parameter aggregation step ($T_{C}\to\infty$)
in Algorithm 5 and apply a hard voting strategy utilizing the source
classifiers to vote for target predictions. All source clients transmit the
classifiers only once at the end of the training process. Results are shown in
Table XIII and Table XIV. The results of additional ablation experiments on
robustness and asynchrony are shown in Table XV

####  D-B3 One-shot hard voting strategy

We cancel the source classifiers parameter aggregation step ($T_{C}\to\infty$)
in Algorithm 5 and apply a hard voting strategy utilizing the source
classifiers to vote for target predictions. All source clients transmit the
classifiers only once at the end of the training process. Results are shown in
Table XIII and Table XIV. The results of additional ablation experiments on
robustness and asynchrony are shown in Table XV