# Private Multi-Task Learning:
Formulation and Applications to Federated Learning

Shengyuan Hu
CMU
<EMAIL_ADDRESS>Zhiwei Steven Wu
CMU
<EMAIL_ADDRESS>Virginia Smith
CMU
<EMAIL_ADDRESS>
###### Abstract

Many problems in machine learning rely on multi-task learning (MTL), in which
the goal is to solve multiple related machine learning tasks simultaneously.
MTL is particularly relevant for privacy-sensitive applications in areas such
as healthcare, finance, and IoT computing, where sensitive data from multiple,
varied sources are shared for the purpose of learning. In this work, we
formalize notions of client-level privacy for MTL via _joint differential
privacy_ (JDP), a relaxation of differential privacy for mechanism design and
distributed optimization. We then propose an algorithm for mean-regularized
MTL, an objective commonly used for applications in personalized federated
learning, subject to JDP. We analyze our objective and solver, providing
certifiable guarantees on both privacy and utility. Empirically, we find that
our method provides improved privacy/utility trade-offs relative to global
baselines across common federated learning benchmarks.

##  1 Introduction

Multi-task learning (MTL) aims to solve multiple learning tasks simultaneously
while exploiting similarities/differences across tasks [6]. Multi-task
learning is commonly used in applications that warrant strong privacy
guarantees. For example, MTL has been used in healthcare, as a way to learn
over diverse populations or between multiple institutions [4, 44, 22]; in
financial forecasting, to combine knowledge from multiple indicators or across
organizations [18, 7]; and in IoT computing, as an approach for personalized
federated learning [43, 20, 21, 17, 42, 10, 37]. While MTL can significantly
improve accuracy when learning in these applications, there is a dearth of
work studying the privacy implications of multi-task learning.

Figure 1: Naively using current client-level DP formulations with MTL results
in models that are no better than a random guess.

In this work, we develop and theoretically analyze methods for MTL with formal
privacy guarantees. Motivated by applications in federated learning, we aim to
provide client-level privacy, where each task corresponds to a
client/user/data silo, and the goal is to protect sensitive information in
each task’s data [39]. We focus on ensuring _differential privacy_ (DP) [13],
which (informally) requires an algorithm’s output to be insensitive to changes
in any entity’s data.

For multi-task learning, where a separate model is generated for each client,
using client-level DP directly would require the entire set of predictive
models across all tasks to be insensitive to changes in the private data of
any single task. This requirement is too stringent for most applications, as
it implies that the predictive model for task $k$ must have little dependence
on the training data for task $k$, thus preventing the usefulness of the model
(see Figures 1 and 2).

To address this issue, we leverage a variant of DP known as _joint
differential privacy_ (JDP) [28], which requires that for each task $k$, the
set of output predictive models for all other tasks except $k$ is insensitive
to $k$’s private data. As a result, the client’s private data in task $k$ is
protected even if all other clients/tasks collude and share their private data
and output models. In contrast to standard DP, JDP allows the predictive model
for task $k$ to depend on $k$’s private data, helping to preserve each task’s
utility.

Figure 2: An MTL problem consists of $m$ different tasks and a learning
algorithm that jointly produces one model for each task (Left). For example,
in cross-device federated learning, each ‘task’ may represent data from a
mobile phone client (as depicted), and MTL can be used to learn shared, yet
personalized models for each client [43]. In traditional differential privacy,
if the private data of task $k$ (e.g., Task 1) changes, the models produced by
the MTL algorithm should be indistinguishable from the models derived without
changing data from task $k$ (Middle). In contrast, JDP allows the model of
task $k$ to be dependent on task $k$’s data while still protecting other tasks
from leaking information about their private data (Right).

Using JDP, we then develop new learning algorithms for MTL with rigorous
privacy and utility guarantees. Specifically, we propose Private Mean-
Regularized MTL, a simple framework for learning multiple tasks while ensuring
client-level privacy. We show that our method achieves
$(\epsilon,\delta)$-JDP. Our scalable solver builds on FedAvg [38], a common
method for communication-efficient federated optimization. We analyze the
convergence of our solver on both nonconvex and convex objectives,
demonstrating a tradeoff between privacy and utility, and evaluate this trade-
off empirically on multiple federated learning benchmarks. We summarize our
contributions below:

  * •

Our work is the first we are aware of to provide formal definitions of client-
level (joint) differential privacy for general multi-task learning objectives
(Section 3), including multi-task relationship learning objectives commonly
used in federated learning.

  * •

Using our privacy definitions, we propose Private Mean-Regularized MTL, a
simple MTL framework that provides client-level privacy (Section 4). We prove
that our method achieves $(\epsilon,\delta)$-JDP, and we analyze the
convergence of our communication-efficient solver on convex and nonconvex
objectives. Our convergence analysis extends to non-private settings with
partial participation, which may be of independent interest for problems in
cross-device federated learning.

  * •

Finally, we explore the performance of our approach on common federated
learning benchmarks (Section 5). Our results show that we can retain the
accuracy benefits of MTL in these settings relative to global baselines while
still providing meaningful privacy guarantees. Further, even in cases where
the MTL and global objectives achieve similar accuracy, we find that
privacy/utility benefits exist when employing our private MTL formulation.

##  2 Background and Related Work

Multi-task learning. Multi-task learning considers jointly solving multiple
related ML tasks. Our work focuses on the general and widely-used formulation
of multi-task relationship learning [49], as detailed in Section 3. This form
of MTL is particularly useful in privacy-sensitive applications where datasets
are shared among multiple heterogeneous entities [4, 43, 18]. In these cases,
it is natural to view each data source (e.g., financial institution, hospital,
mobile phone) as a separate ‘task’ that is learned in unison with the other
tasks. This allows data to be shared, but the models to be personalized to
each data silo. For example, in the setting of cross-device federated
learning, MTL is commonly used to train a personalized model for each device
in a distributed network [43, 35].

Federated learning. A motivation for our work is the application of federated
learning (FL), in which the goal is to collaboratively learn from a number of
private data silos, such as remote devices or servers [38, 26, 32]. To ensure
client-level DP in FL, a common technique is to learn one global model across
the distributed data and then add noise to the aggregated model to
sufficiently mask any specific client’s update [26, 39, 16]. However, a
defining characteristic of federated learning is that the distributed data are
likely to be heterogeneous, i.e., each client may generate data via a distinct
data distribution [26, 32]. To model the (possibly) varying data distributions
on each client, it is natural to instead consider learning a separate model
for each client’s local dataset. To this end, a number of recent works have
explored multi-task learning as a way to improve the accuracy of learning in
federated networks [43, 20, 21, 17, 42, 10, 37]. Despite the prevalence of
multi-task federated learning, we are unaware of any work that has explored
client-level privacy for commonly-used multi-task relationship models (Section
3) in federated settings.

Differentially private MTL. Prior work in private MTL differs from our own
either in terms of the privacy formulation or MTL objective. For example, Wu
et al. [45] explore a specific MTL setting where a shared private feature
representation is first learned, followed by task-specific models. We instead
study multi-task relationship learning (Section 3), which is a general and
widely-used MTL framework, particularly in federated learning [43]. While our
work focuses on client-level privacy, there has been work on data-level
privacy for MTL, which aims to protect any single sample of local data rather
than protecting the entire local dataset. For example, Xie et al. [46] propose
a method for data-level privacy by modeling each task as a sum of a public
shared weight and a task-specific weight that is only updated locally, and
Gupta et al. [19] study data-level privacy for a mean estimation MTL problem.
Finally, Li et al. [31] study multiple notions of DP for meta-learning.
Although similarly motivated by personalization, their framework does not
cover the multi-task setting, where there exists a separate model for each
task. Concurrent to our work, Jain et al. [25] study a personalization method
that learns a private shared representation. Although they similarly leverage
the Billboard model, their formulation cannot be applied to the general form
of multi-task learning in this work. Their results are also limited to the
special case of linear regression, unlike the broad set of convex and
nonconvex objectives considered herein.

##  3 Multi-Task Learning Setup and Privacy Formulation

In this section, we first formalize the multi-task learning objectives of
interest (Section 3.1), and then discuss our proposed privacy formulation
(Section 3.2).

###  3.1 Problem Setup

Multi-task learning aims to improve generalization by jointly solving and
exploiting relationships between multiple tasks [6, 3]. The classical setting
of multi-task relationship learning [48, 49] considers $m$ different tasks
with their own task-specific data, learned jointly through the following
objective:

$\min_{W,\Omega}\left\\{F(W,\Omega)=\left\\{\frac{1}{m}\sum_{k=1}^{m}\sum_{i=1}^{n_{k}}l_{k}(x_{i},w_{k})+\mathcal{R}(W,\Omega)\right\\}\right\\}.$
(1)

Here $w_{k}$ is model for task $k$, $\\{x_{1},\dots,x_{n_{k}}\\}$ is the local
data for the $k^{th}$ task, $l_{k}(\cdot)$ is the empirical loss,
$W=[w_{1};\cdots;w_{m}]$, and $\Omega\in\mathbb{R}^{m\times m}$ characterizes
the relationship between every pair of tasks. A common choice for setting the
regularization term $\mathcal{R}(W,\Omega)$ in prior works [49, 43] is:

$\mathcal{R}(W,\Omega)=\lambda_{1}\text{tr}(W\Omega W^{T})\,,$

where $\Omega$ can be viewed as a covariance matrix, used to learn/encode
positive, negative, or unrelated task relationships. In this paper, we focus
primarily on the mean-regularized multi-task learning objective [14]: a
special case of (1) where $\Omega=(\bf{I}_{m\times
m}-\frac{1}{m}\bf{1}_{m}\bf{1}_{m}^{T})^{2}$ is fixed. Here $\bf{I}_{m\times
m}$ is the identity matrix of size $m\times m$ and
$\bf{1}_{m}\in\mathbb{R}^{m}$ is the vector with all entries equal to 1. By
picking $\lambda_{1}=\frac{\lambda}{2}$, we can rewrite (1) as:

$\min_{W}\left\\{F(W)=\left\\{\frac{1}{m}\sum_{k=1}^{m}\frac{\lambda}{2}\|w_{k}-\bar{w}\|^{2}+\sum_{i=1}^{n_{k}}l_{k}(x_{i},w_{k})\right\\}\right\\}\,,$
(2)

where $\bar{w}$ is the average of task-specific models, i.e.,
$\bar{w}=\frac{1}{m}\sum_{i=1}^{m}w_{k}$. Note that $\bar{w}$ is shared across
all tasks, and each $w_{k}$ is kept locally for task learner $k$. During
optimization, each task learner $k$ solves:

$\min_{w_{k}}\bigg{\\{}f_{k}(w_{k};\bar{w})=\frac{\lambda}{2}\|w_{k}-\bar{w}\|^{2}+\sum_{i=1}^{n_{k}}l_{k}(x_{i},w_{k})\bigg{\\}}.$
(3)

Application to Federated Learning. In federated learning, where the goal is to
learn over a set of $m$ clients in a privacy-preserving manner, initial
approaches focused on learning a single global model across the data [38].
However, as data distributions may differ from one client to another, MTL has
become a popular alternative that enables every client to collaborate and
learn a separate, personalized model of its own [43]. Specifically, in the
case of mean-regularized MTL, each client solves Equation 3 and utilizes
$w_{k}$ as its final personalized model. Unlike finetuning from a global
model, MTL itself learns a separate model for each client by solving Objective
1 in order to improve the generalization performance [48, 49], which is not
equivalent to simple finetuning from a global model (see Section 5). Despite
the prevalence of mean-regularized multi-task learning and its recent use in
applications such as federated learning with strong privacy motivations [e.g.,
43, 20, 21, 11], we are unaware of prior work that has formalized client-level
differential privacy in the context of solving Objective (2).

###  3.2 Privacy Formulation

To consider privacy for MTL, we start by introducing the definition of
differential privacy (DP) and then discuss its generalization to joint
differential privacy (JDP). In the context of multi-task learning, each of the
$m$ task learners owns a private dataset
$D_{i}\in\mathcal{U}_{i}\subset\mathcal{U}$. We define
$D=\\{D_{1},\cdots,D_{m}\\}$ and
$D^{\prime}=\\{D_{1}^{\prime},\cdots,D_{m}^{\prime}\\}$, and call two sets
$D,D^{\prime}$ neighboring sets if they only differ on the index $i$, i.e.,
$D_{j}=D_{j}^{\prime}$ for all $j$ except $i$.

######  Definition 1 (Differential Privacy (DP) for MTL [13]).

A randomized algorithm $\mathcal{M}:\mathcal{U}^{m}\rightarrow\mathcal{R}^{m}$
is $(\epsilon,\delta)$-differentially private if for every pair of neighboring
sets that only differ in arbitrary index $i$: $D,D^{\prime}\in\mathcal{U}$ and
for every set of subsets of outputs $S\subset\mathcal{R}$,

$\text{Pr}(\mathcal{M}(D)\in S)\leq
e^{\epsilon}\text{Pr}(\mathcal{M}(D^{\prime})\in S)+\delta.$ (4)

In the context of MTL, an algorithm outputs one model for every task. In this
work we are interested in studying client-level differential privacy, where
the purpose is to protect one task’s data from leakage to any other task [38].
As mentioned previously and illustrated in Figure 3, since the output of MTL
is a collection of models, traditional client-level DP would require that all
the models produced by an MTL algorithm are insensitive to changes that happen
in the private dataset of any single client/task.

Why can’t we apply traditional client-level DP? With the above definition in
mind, note that DP has a severe restriction: the model of any task learner
must also be insensitive to changes in its own data, effectively rendering
each model useless. Although it is intuitive that this would result in
unacceptable performance, we verify it empirically in Figure 1. For a common
federated learning benchmark (FEMNIST, discussed in Section 5), we apply DPSGD
on the joint model that concatenates all clients’ parameters. We compare MTL
with vanilla client-level DP relative to training a global model with client-
level DP and our proposed MTL approach using JDP (below). With the naive DP
formulation, MTL is significantly worse than the other approaches—improving
only marginally upon random guessing.

Joint Differential Privacy. To overcome this limitation of traditional DP, we
propose employing joint differential privacy (JDP) [28], a relaxed notion of
DP, to formalize the client-level privacy guarantees for MTL algorithm.
Intuitively, JDP requires that for each task $k$, the set of output models for
all other tasks except $k$ is insensitive to $k$’s private data. We provide a
formal definition below.

######  Definition 2 (Joint Differential Privacy (JDP) [28]).

A randomized algorithm $\mathcal{M}:\mathcal{U}^{m}\rightarrow\mathcal{R}^{m}$
is $(\epsilon,\delta)$-joint differentially private if for every $i$, for
every pair of neighboring datasets that only differ in index $i$:
$D,D^{\prime}\in\mathcal{U}^{m}$ and for every set of subsets of outputs
$S\subset\mathcal{R}^{m}$,

$\text{Pr}(\mathcal{M}(D)_{-i}\in S)\leq
e^{\epsilon}\text{Pr}(\mathcal{M}(D^{\prime})_{-i}\in S)+\delta,$ (5)

where $\mathcal{M}(D)_{-i}$ represents the vector $\mathcal{M}(D)$ with the
$i$-th entry removed.

JDP allows the predictive model for task $k$ to depend on the private data of
$k$, while still providing a strong guarantee: even if all the clients from
all the other tasks collude and share their information, they still will not
be able to learn much about the private data in the task $k$. JDP has mostly
been used in applications related to mechanism design [23, 27, 24, 9, 41, 28].
Although it is a natural choice for achieving client-level privacy in MTL, we
are unaware of any work that studies the general MTL formulations considered
herein subject to JDP. We also note that we can naturally connect joint
differential privacy to standard differential privacy. Informally, if we take
the output of a differentially private process and run some algorithm on top
of that locally for each task learner without communicating to the global
learner or other task learners, this whole process can be shown to be joint
differentially private. This is formalized as the Billboard Lemma [23],
presented in Lemma 1 below.

######  Lemma 1 (Billboard Lemma).

Suppose $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{W}$ is
$(\epsilon,\delta)$-differentially private. Consider any set of functions:
$f_{i}:\mathcal{D}_{i}\times\mathcal{W}\rightarrow\mathcal{W}^{\prime}$. The
composition $\\{f_{i}(\Pi_{i}\mathcal{D},\mathcal{M}(\mathcal{D}))\\}$ is
$(\epsilon,\delta)$-joint differentially private, where
$\Pi_{i}:\mathcal{D}\rightarrow\mathcal{D}_{i}$ is the projection of
$\mathcal{D}$ onto $\mathcal{D}_{i}$.

With the Billboard Lemma, we are able to obtain JDP by first training a
differentially private model with data from all tasks, and then finetuning on
each task with its local data. We formally introduce our algorithm and
corresponding JDP guarantee by using Lemma 1 in Section 4.

Remark (Generality of Privacy Formulation). Finally, note that our privacy
formulation itself is not limited to the multi-task relationship learning
framework. For any form of multi-task learning where each task-specific model
is obtained by training a combination of global component and local
component(e.g. [34]), we can provide a JDP guarantee for the MTL training
process by using a differentially private global component.

##  4 PMTL: Private Multi-Task Learning

We now present PMTL, a method for performing joint differentially-private MTL
(Section 4.1). We provide both a formal privacy guarantee (Section 4.2) and
utility guarantee (Section 4.3) for our approach.

###  4.1 Algorithm

We summarize our solver for private multi-task learning in Algorithm 1. Our
method is based off of FedAvg [38], a communication-efficient method widely
used in federated learning. FedAvg alternates between two steps: (i) each task
learner selected at one communication round solves its own local objective by
running stochastic gradient descent for $E$ iterations and sending the updated
model to the global learner; (ii) the global learner aggregates the local
updates and broadcasts the aggregated mean. By performing local updating in
this manner, FedAvg has been shown to empirically reduce the total number of
communication rounds needed for convergence in federated settings relative to
baselines such as mini-batch FedSGD [38]. Our private MTL algorithm differs
from FedAvg in that: (i) instead of learning a single global model, all task
learners collaboratively learn separate, personalized models for each task;
(ii) each task learner solves the local objective with the mean-regularization
term; (iii) individual model updates are clipped and random Gaussian noise is
added to the aggregated model updates to ensure client-level privacy.

To aggregate updates from each task, we assume that we have access to a
trusted global learner, i.e., it is safe for some global entity to
observe/collect the individual model updates from each task. This is a
standard assumption in federated learning, where access to a trusted server is
assumed in order to collect client updates [26]. However, even with this
assumption, note that it is possible for any single task learner to infer
information about other tasks from the global model, since it is a linear
combination of all task specific models and is shared among all clients.

Algorithm 1 PMTL: Private Mean-Regularized MTL

1: Input: $m$, $T$, $\lambda$, $\eta$, $\\{w_{1}^{0},\cdots,w_{m}^{0}\\}$,
$\widetilde{w}^{0}=\frac{1}{m}\sum_{k=1}^{m}w_{k}^{0}$

2: for $t=0,\cdots,T-1$ do

3: Global Learner randomly selects a set of tasks $S_{t}$ and broadcasts the
mean weight $\widetilde{w}^{t}$

4: for $k\in S_{t}$ in parallel do

5: Each client updates its weight $w_{k}$ for $E$ iterations, $o_{k}$ is the
last iteration task $k$ is selected
$w_{k}^{t+1}=\texttt{ClientUpdate}(w_{k}^{o_{k}})$

6: Each client sends $g_{k}^{t+1}=w_{k}^{t+1}-w_{k}^{t}$ back to the global
learner.

7: end for

8: Global Learner computes a noisy aggregator of the weights
$\widetilde{w}^{t+1}=\widetilde{w}^{t}+\frac{1}{|S_{t}|}\sum_{k\in
S_{t}}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}+\mathcal{N}(0,\sigma^{2}\bf{I}_{d\times
d})$

9: end for

10: Output $w_{1},\cdots,w_{m}$ as differentially private personalized models

11: ClientUpdate(w)

12: for $j=0,\cdots,E-1$ do

13: Task learner performs SGD locally
$w=w-\eta(\nabla_{w}l_{k}(w)+\lambda(w-\widetilde{w}^{t}))$

14: end for

There are several ways to overcome this privacy risk and thus achieve
$(\epsilon,\delta)$-differential privacy. In this paper, we use the Gaussian
Mechanism [12] during global aggregation as a simple yet effective method,
highlighted in red in line 8 of Algorithm 1. In this case, each client
receives a noisy aggregated global model, making it difficult for any task to
leak private information to the others. To apply the Gaussian mechanism, we
need to bound the $\ell_{2}$-sensitivity of each local model update that is
communicated to lie in $\mathcal{B}=\\{\Delta w|\|\Delta
w\|_{2}\leq\gamma\\}$, as highlighted in blue in line 8 of Algorithm 1. Hence,
at each communication round, the global learner receives the model updates
from each clients, and clips the model updates to $\mathcal{B}$ before
aggregation. Note that different from DPSGD [2], when we solve the local
objective for each selected task at each communication round, our algorithm
doesn’t clip and perturb the gradient used to update the task-specific model.
Instead, since the purpose is to protect task or client-level privacy in
multi-task learning, we perform standard SGD locally for each task and only
clip and perturb the model update that is sent to the global learner. We
formalize the privacy guarantee of Algorithm 1 in Section 4.2.

###  4.2 Privacy Analysis

We now rigorously explore the privacy guarantee provided by Algorithm 1. In
our optimization scheme, for each task $k$, at the end of each communication
round, a shared global model is received. After that the task specific model
is updated by optimizing the local objective. We formalize this local task
learning process as
$h_{k}:\mathcal{D}_{k}\times\mathcal{W}\rightarrow\mathcal{W}$. Here we simply
assume $\mathcal{W}\subset\mathbb{R}^{d}$ is closed. Define the mechanism for
communication round $t$ to be

$\mathcal{M}^{t}(\\{D_{i}\\},\\{h_{i}(\cdot)\\},\widetilde{w}^{t},\sigma)=\widetilde{w}^{t}+\frac{1}{|S_{t}|}\sum_{k\in
S_{t}}h_{k}(D_{k},\widetilde{w}^{t})+\beta^{t},$ (6)

where $\beta^{t}\sim\mathcal{N}(0,\sigma^{2}\text{I}_{d\times d})$. Note that
$\mathcal{M}^{t}$ characterizes a Sampled Gaussian Mechanism given
$\widetilde{w}^{t}$ as a fixed model rather than the output of a composition
of $\mathcal{M}^{j}$ for $j<t$. To analyze the privacy guarantee of Algorithm
1 over $T$ communication rounds, we define the composition of
$\mathcal{M}^{1}$ to $\mathcal{M}^{T}$ recursively as
$\mathcal{M}^{1:T}=\mathcal{M}^{T}(\\{D_{i}\\},\\{h_{i}(\cdot)\\},\mathcal{M}^{T-1},\sigma)$.

######  Theorem 1.

Assume $|S_{t}|=q$ for all $t$ and the total number of communication rounds is
$T$. There exists constants $c_{1},c_{2}$ such that for any
$\epsilon<c_{1}\frac{q^{2}}{m^{2}}T$, the mechanism $\mathcal{M}^{1:T}$ is
$(\epsilon,\delta)$-differentially private for any $\delta>0$ if we choose
$\sigma\geq c_{2}\frac{\gamma\sqrt{T\log(1/\delta)}}{\epsilon m}$. When $q=m$,
$\mathcal{M}^{1:T}$ is $(\epsilon,\delta)$-differentially private if we choose
$\sigma=\frac{4\gamma\sqrt{T\log(1/\delta)}}{\epsilon m}$.

Theorem 1 provides a provable privacy guarantee on the learned model. When all
tasks participate in every communication round, i.e. $q=m$, the global
aggregation step in Algorithm 1 reduce to applying Gaussian Mechanism without
sampling rather than Sampled Gaussian Mechanism on the average model updates.
We provide a detailed proof of Theorem 1 in Appendix A.1. Note in particular
that Theorem 1 doesn’t rely on how task learners optimize their local
objective. Hence, Theorem 1 is not limited to Algorithm 1 and could be
generalized to other local objectives and other global aggregation methods
that produce a single model aggregate.

Now we show that Algorithm 1, which outputs $m$ separate models, satisfies
joint differential privacy. Given $\widetilde{w}^{t}$ for any $t\leq T$, we
formally define the process that each task learner $k$ optimize its local
objective to be
$h_{k}^{\prime}:\mathcal{D}_{k}\times\mathcal{W}\rightarrow\mathcal{W}$. Note
that $h_{k}^{\prime}$ is not restricted to be $h_{k}$ and could represent the
optimization process for any local objective. In order to show that Algorithm
1 satisfies JDP, we would apply the Billboard Lemma introduced in Section 3.
In our case, the average model that is broadcast by the global learner at
every communication round is the output of a differentially private learning
process. Task learners then individually train their task specific models on
the respective private data to obtain personalized models. We now present our
main theorem of the JDP guarantee provided by Algorithm 1:

######  Theorem 2.

There exists constants $c_{1},c_{2}$, for any
$0<\epsilon<c_{1}\frac{q^{2}}{m^{2}}T$ and $\delta>0$, let
$\sigma\geq\frac{c_{2}\gamma\sqrt{T\log(1/\delta)}}{\epsilon m}$. Algorithm 1
that outputs $h_{k}^{\prime}(D_{k},\mathcal{M}^{1:T})$ for each task is
$(\epsilon,\delta)$-joint differentially private.

From Theorem 2, for any fixed $\delta$, the more tasks involved in the
learning process, the smaller $\sigma$ we need in order to keep the privacy
parameter $\epsilon$ the same. In other words, less noise is required to keep
the task-specific data private. When we have infinitely many tasks
($m\rightarrow\infty$), we have $\sigma\rightarrow 0$, in which case only a
negligible amount of noise is needed for the model aggregates to make the
global model private to all tasks. We provide a detailed proof in Appendix
A.1.

Remark (Generality of Theorem 2). Note that the privacy guarantee provided by
Theorem 2 is not limited to mean-regularized MTL. For any form of multi-task
relationship learning with fixed relationship matrix $\Omega$, as long as we
fix the $\ell_{2}$-sensitivity of model updates and the noise scale of the
Gaussian mechanism applied to the statistics broadcast to all task learners,
the privacy guarantee induced by this aggregation step is fixed, regardless of
the local objective being optimized. For example, as a natural extension of
mean-regularized MTL, consider the case where task learners are partitioned
into fixed clusters and optimize the mean-regularized MTL objective within
each cluster, as in [15]. In this scenario, Theorem 2 directly applies to the
algorithm run on each cluster.

###  4.3 Convergence Analysis

As discussed in Section 3, we are interested in the following task-specific
objective:

$f_{k}(w_{k};\widetilde{w})=l_{k}(w_{k})+\frac{\lambda}{2}\|w_{k}-\widetilde{w}\|_{2}^{2}\,$
(7)

where $\widetilde{w}$ is an estimate for the average model $\overline{w}$;
$l_{k}(w_{k})$ is the empirical loss for task $k$; $w_{k}\in\mathbb{R}^{d}$.

Here, we analyze the convergence behavior in the setting where a set $S_{t}$
of $q$ tasks participate in the optimization process at every communication
round. Further, we assume the total number of communication round $T$ is
divisible by the number of local optimization steps $E$: $T=0\mod E$. We
present the following convergence result:

######  Theorem 3 (Convergence under nonconvex loss).

Let $f_{k}$ be $(L+\lambda)$-smooth. Assume $\gamma$ is sufficiently large
such that
$\gamma\geq\max_{k,t}\|\nabla_{w_{k}^{t}}f_{k}(w_{k}^{t};\widetilde{w}^{t})\|_{2}$.
Further let $f_{k}^{*}=\min_{w,\bar{w}}f_{k}(w;\bar{w})$ and $p=\frac{q}{m}$.
If we use a fixed learning rate
$\eta_{t}=\eta=\frac{1}{pL+\left(p+\frac{1}{p}\right)\lambda}$, Algorithm 1
satisfies:

$\displaystyle\frac{1}{mT}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\leq\mathcal{O}\left(\frac{1}{mT}\right)+\frac{\mathcal{O}\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\sum_{i=1}^{\lfloor
T/E\rfloor}B_{iE}}{T}+\mathcal{O}\left(d\sigma^{2}\right).$ (8)

where

$\displaystyle B_{t}=\max_{k}f_{k}(w_{k}^{t};\widetilde{w}^{t}).$ (9)

Let $\sigma$ chosen as we set in Theorem 2. Take
$T=\mathcal{O}\left(\frac{m}{\lambda d\gamma^{2}}\right)$, the right hand side
is bounded by

$\displaystyle\frac{\lambda
d\gamma^{2}}{m^{2}}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\leq\mathcal{O}\left(\frac{d\gamma^{2}}{m^{2}}\right)+\mathcal{O}\left(d\gamma^{2}\right)\sum_{i=1}^{\lfloor
T/E\rfloor}B_{iE}+\mathcal{O}\left(\frac{1}{m}\right)\frac{\log(1/\delta)}{\epsilon^{2}}.$
(10)

We provide a formal statement and full proof of Theorem 3 in Appendix A.2. The
upper bound in (30) consists of two parts: error induced by the gradient
descent algorithm and error induced by the Gaussian Mechanism. When
$\sigma=0$, Algorithm 1 recovers a non-private mean-regularized multi-task
learning solver.

######  Corollary 4.

When $\sigma=0$, Algorithm 1 with $(L+\lambda)$-smooth and nonconvex $f_{k}$
satisfies

$\displaystyle\frac{1}{mT}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\leq\mathcal{O}\left(\frac{1}{mT}\right)+\frac{\mathcal{O}\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\sum_{i=1}^{\lfloor
T/E\rfloor}B_{iE}}{T}.$ (11)

By Theorem 2, given fixed $\epsilon$, $\sigma^{2}$ grows linearly with respect
to $T$. Hence, given the same privacy guarantee, larger noise is required if
the algorithm is run for more communication rounds. Note that in Theorem 3,
the upper bound consists of $\mathcal{O}(\frac{1}{m\epsilon^{2}})$, which
means when there are more tasks, the upper bound becomes smaller while the
privacy parameter remains the same. On the other hand, Theorem 3 also shows a
privacy-utility tradeoff using our Algorithm 1: the upper bound grows
inversely proportional to the privacy parameter $\epsilon$. We also provide a
convergence analysis of Algorithm 1 with strongly-convex losses in Theorem 5
below (formal statement and proof in Appendix A.3).

######  Theorem 5 (Convergence under strongly-convex loss).

Let $f_{k}$ be $(L+\lambda)$-smooth and $(\mu+\lambda)$-strongly convex.
Assume $\gamma$ is sufficiently large such that
$\gamma\geq\max_{k,t}\|\nabla_{w_{k}^{t}}f_{k}(w_{k}^{t};\widetilde{w}^{t})\|_{2}$.
Further let $w_{k}^{*}=\operatorname*{arg\,min}_{w}f_{k}(w;\bar{w}^{*})$,
where $\bar{w}^{*}=\frac{1}{m}\sum_{k=1}^{m}w_{k}^{*}$ and $p=\frac{q}{m}$. If
we use a fixed learning rate $\eta_{t}=\eta=\frac{c}{\frac{L-2}{p}+\lambda p}$
for some constant $c$ such that $\frac{1}{2}\leq\eta p(c-2)(\mu+\lambda)\leq
1$, Algorithm 1 satisfies:

$\displaystyle\frac{1}{m}\Delta_{T}\leq\frac{1}{2^{T}}\left(\frac{1}{m}\Delta_{0}-C\right)+\frac{C}{1-\frac{1}{2^{E}}},$
(12)

where
$\Delta_{t}=\sum_{k=1}^{m}f_{k}(w_{k}^{t};\widetilde{w}^{t})-f_{k}(w_{k}^{*};\widetilde{w}^{*})$,
$C=\mathcal{O}\left(\lambda\left(\sqrt{d}\sigma+\sqrt{\frac{2}{\lambda}B}\right)^{2}\right)$,
$B=\max_{t}\max_{k}f_{k}(w_{k}^{t};\widetilde{w}^{t})$.

Let $\sigma$ be chosen as in Theorem 2, then there exists
$T=\mathcal{O}\left(\frac{m}{\lambda d\gamma^{2}}\right)$ such that

$\displaystyle\frac{1}{m}\Delta_{T}\leq\frac{1}{2^{T}}\left(\frac{1}{m}\Delta_{0}-\frac{\log(1/\delta)}{m\epsilon^{2}}-\mathcal{O}\left(B\right)\right)+\frac{\frac{\log(1/\delta)}{m\epsilon^{2}}+\mathcal{O}\left(B\right)}{1-\frac{1}{2^{E}}}.$
(13)

As with Corollary 4, we recover the bound of the non-private mean-regularized
MTL solver for $\sigma$=$0$.

######  Corollary 6.

When $\sigma=0$, Algorithm 1 with $(L+\lambda)$-smooth and
$(\mu+\lambda)$-strongly convex $f_{k}$ satisfies

$\frac{1}{m}\Delta_{T}\leq\frac{1}{2^{T}}\left(\frac{1}{m}\Delta_{0}-B\right)+\frac{B}{1-\frac{1}{2^{E}}}.\vspace{-0.2cm}$
(14)

It is worth noting that for both convex and non-convex case, given the nature
of the mean-regularized MTL objective, the local objective will only converge
to within a neighborhood of the optimal. Consider the following simple mean-
estimation problem as an example. Assume that we have $m$ different
clients/tasks, each with local data $x_{i}$ and local model $w_{i}$. The mean-
regularized MTL objective for this problem would be
$\frac{1}{m}\sum_{i}(x_{i}-w_{i})^{2}+\frac{1}{m}\sum_{i}(w_{i}-\bar{w})^{2}$,
which is greater than
$\frac{1}{2m}\sum_{i}(x_{i}-w_{i}+w_{i}-\bar{w})^{2}=\frac{1}{2m}\sum_{i}(x_{i}-\bar{w})^{2}$.
Note that this lower bound neither converges to 0 as $\bar{w}$ changes over
time nor diminishes with increasing $m$. This result is therefore
expected/standard, and is in line with other previous works that study the
same objective but with different solvers, where similar dependencies on
$\eta$ and $B$ can be seen [20].

(a) StackOverflow tag prediction

(b) FEMNIST

(c) CelebA

Figure 3: Loss and privacy parameter vs. communication rounds for PMTL. The
blue line shows the change of privacy parameter $\epsilon$ in terms of number
of communication rounds during training. The orange line shows the average
training loss across all tasks.

##  5 Experiments

We empirically evaluate our private MTL solver on common federated learning
benchmarks [5]. We first demonstrate the superior privacy-utility trade-off
that exists when training our private MTL method compared with training a
single global model (Section 5.2). We also compare our method with simple
finetuning—exploring the results of performing local finetuning after learning
an MTL objective vs. a global objective (Section 5.3).

###  5.1 Setup

For all experiments, we evaluate the test accuracy and privacy parameter of
our private MTL solver given a fixed clipping bound $\gamma$, variance of
Gaussian noise $\sigma^{2}$, and communication rounds $T$. All experiments are
performed on common federated learning benchmarks as a natural application of
multi-task learning. We provide a detailed description of datasets and models
in Appendix A.4. Each dataset is naturally partitioned among $m$ different
clients. Under such a scenario, each client can be viewed as a task and the
data that a client generates is only visible locally.

(a) StackOverflow tag prediction

(b) FEMNIST

(c) CelebA

Figure 4: Comparison of training PMTL vs. a private global model. PMTL is able
to retain advantages over global approaches in private settings (e.g.,
StackOverflow). In addition, even in settings where the non-private MTL and
global baselines are similar (e.g., FEMNIST, CelebA), there exist utility
benefits at all levels of $\epsilon$ when using PMTL.

###  5.2 Privacy-Utility Trade-off of PMTL

We first explore the training loss ( orange) and privacy parameter $\epsilon$
( blue) as a function of communication rounds across three datasets (Figure
3). Specifically, we evaluate the average loss for all the tasks and
$\epsilon$ given a fixed $\delta$ after each round, where $\delta$ is set to
be $\frac{1}{m}$ for all experiments. In general, for a fixed clipping bound
$\gamma$ and $\sigma$, we see that the method converges fairly quickly with
respect to the resulting privacy, but that privacy guarantees may be
sacrificed in order to achieve very small losses.

To put these results in context, we also compare the test performance of our
private MTL solver with that of training a global model. In particular, we use
FedAvg [38] to train a global model. At each communication round, task
learners solve their local objective individually. Assuming the global learner
is trustworthy, while aggregating the model updates from all tasks, the global
learner applies a Gaussian Mechanism and sends the noisy aggregation back to
the task learners. As a result, private FedAvg differs from our private MTL
solver in the following two places: (i) the MTL objective solved locally by
each task learner has an additional mean-regularized term; (ii) the MTL method
evaluates on one task-specific model for every task while the global method
evaluates all tasks on one global model. For each dataset, we select privacy
parameter $\epsilon\in[0.05,0.1,0.2,0.4,0.8,1.6,2.0,4.0]$. For each
$\epsilon$, we select the $\gamma$, $\sigma$, and $T$ that result in the best
validation accuracy for a given $\epsilon$ and record the test accuracy. A
detailed description of hyperparameters is listed in Appendix 5.4. We plot the
test accuracy with respect to the highest validation accuracy given one
$\epsilon$ for both private MTL model and private global model. The results
are shown in Figure 4.

In all three datasets, our private MTL solver achieves higher test accuracy
compared with training a private global model with FedAvg given the same
$\epsilon$. Moreover, the proposed mean regularized MTL solver is able to
retain an advantage over global model even with noisy aggregation. In
particular, for small $\epsilon<1$, adding random Gaussian noise during global
aggregation amplifies the test accuracy difference between our MTL solver and
FedAvg. Under the StackOverflow task, both methods obtain test accuracy close
to the non private baseline for large $\epsilon$. To demonstrate that applying
private MTL has an advantage over private global training more generally, we
also compared our PMTL method with private FedProx [33]. The results (which
mirror Figure 4) are in Appendix A.5.

FEMNIST | ${\epsilon=0.1}$ | ${\epsilon=0.8}$ | ${\epsilon=2.0}$ | ${\epsilon=\infty}$
---|---|---|---|---
| MTL | Global | MTL | Global | MTL | Global | MTL | Global
Vanilla Finetuning | $\mathbf{0.645\pm 0.013}$ | $0.606\pm 0.017$ | ${0.640\pm 0.016}$ | $\mathbf{0.648\pm 0.017}$ | $\mathbf{0.677\pm 0.008}$ | $0.653\pm 0.010$ | $\mathbf{0.832\pm 0.005}$ | $0.812\pm 0.009$
Mean-regularization | $\mathbf{0.608\pm 0.011}$ | $0.581\pm 0.011$ | $\mathbf{0.605\pm 0.008}$ | $0.574\pm 0.006$ | $\mathbf{0.656\pm 0.009}$ | $0.633\pm 0.003$ | $0.826\pm 0.011$ | $\mathbf{0.839\pm 0.006}$
Symmetrized KL | $\mathbf{0.486\pm 0.012}$ | $0.348\pm 0.005$ | $\mathbf{0.584\pm 0.012}$ | $0.481\pm 0.016$ | $\mathbf{0.662\pm 0.016}$ | $0.565\pm 0.019$ | $\mathbf{0.839\pm 0.006}$ | $0.829\pm 0.015$
EWC | $\mathbf{0.663\pm 0.002}$ | $0.556\pm 0.001$ | $0.595\pm 0.004$ | $\mathbf{0.607\pm 0.007}$ | $\mathbf{0.681\pm 0.002}$ | $0.666\pm 0.001$ | $\mathbf{0.837\pm 0.001}$ | $0.823\pm 0.005$

Table 1: Comparison of PMTL vs. a private global model with different local
finetuning methods. $\epsilon=\infty$ corresponds to no noise and clipping,
i.e., training non-privately. The higher accuracy between MTL and Global given
the same $\epsilon$ and finetuning method is bolded.

###  5.3 PMTL with local finetuning

Finally, in federated learning, prior work has shown local finetuning is
helpful for improving utility after training a differentially private global
model [47]. In this section, after obtaining a private global model, we
explore locally finetuning the task specific models by optimizing different
local objective functions. In particular, we use common objectives which (i)
naively optimize the local empirical risk (Vanilla Finetuning), or (ii)
encourage minimizing the distance between local and global model under
different distance metrics (Mean-regularization, Symmetrized KL, EWC [29,
47]). The results are listed in Table 1. When $\epsilon=\infty$ (the non-
private setting), global with mean-regularization finetuning outperforms all
MTL+finetuning methods. However, when we add privacy to both methods, private
MTL+finetuning has an advantage over global with finetuning on different
finetuning objectives. In some cases, e.g. using Symmetrized KL as the
finetuning objective, the test accuracy gap between private MTL+fintuning and
private global+finetuning is amplified when $\epsilon$ is small compared to
the case where no privacy is added during training.

###  5.4 Hyperparameters

In this section we introduce how different hyperparameters affect the privacy-
utility trade-off on different datasets. Each fixed privacy parameter
$\epsilon$ could be computed by different combinations of noise scale
$\sigma$, clipping norm $\gamma$, number of communication rounds $T$, and
subsampling rate $p=\frac{q}{m}$. In all our experiments, we subsample 100
different tasks for each round, i.e. $q=100$, to perform local training as
well as involved in global aggregation. For FEMNIST and CelebA, we choose
$\sigma\in\\{0.02,0.05,0.1\\}$ and $\gamma\in\\{0.2,0.5,1\\}$. For
StackOverflow, we choose $\sigma\in\\{0.01,0.05,0.1\\}$ and
$\gamma\in\\{0.1,0.5,1\\}$. We summarize both utility and privacy performance
for different hyperparameters below.

Figure 5: FEMNIST results

Figure 6: CelebA results

Figure 7: StackOverflow results

##  6 Conclusion and Future work

In this work, we define notions of client-level differential privacy for
multi-task learning and propose a simple method for private mean-regularized
MTL. Theoretically, we provide both privacy and utility guarantees for our
approach. Empirically, we show that private MTL retains advantages over
training a private global model on common federated learning benchmarks. In
future work, we are interested in building on our results to explore privacy
for more general forms of MTL, e.g., the family of objectives in (1) with
arbitrary $\Omega$. We are also interested in studying how client-level
privacy relates to algorithmic fairness in MTL settings.

##  7 Acknowledgements

This work was supported in part by a Google Faculty Award, Facebook Faculty
Award, and Carnegie Mellon University’s College of Engineering Moonshot Award
for Autonomous Technologies for Livability and Sustainability (ATLAS). Any
opinions, findings, and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect any funding
agency.

## References

  * [1] Tensorflow federated: Machine learning on decentralized data.  URL https://www.tensorflow.org/federated.
  * Abadi et al. [2016] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang.  Deep learning with differential privacy.  In _ACM SIGSAC Conference on Computer and Communications Security_ , 2016.
  * Ando and Zhang [2005] R. K. Ando and T. Zhang.  A framework for learning predictive structures from multiple tasks and unlabeled data.  _Journal of Machine Learning Research_ , 6:1817–1853, 2005\.
  * Baytas et al. [2016] I. M. Baytas, M. Yan, A. K. Jain, and J. Zhou.  Asynchronous multi-task learning.  In _International Conference on Data Mining (ICDM)_ , 2016.
  * Caldas et al. [2018] S. Caldas, P. Wu, T. Li, J. Konečnỳ, H. B. McMahan, V. Smith, and A. Talwalkar.  Leaf: A benchmark for federated settings, https://leaf.cmu.edu/.  _arXiv preprint arXiv:1812.01097_ , 2018.
  * Caruana [1997] R. Caruana.  Multitask learning.  _Machine Learning_ , 28:41–75, 1997.
  * Cheng et al. [2020] Y. Cheng, Y. Liu, T. Chen, and Q. Yang.  Federated learning for privacy-preserving ai.  _Communications of the ACM_ , 63(12), 2020.
  * Cohen et al. [2017] G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik.  Emnist: Extending mnist to handwritten letters.  In _2017 International Joint Conference on Neural Networks (IJCNN)_ , pages 2921–2926, 2017.
  * Cummings et al. [2015] R. Cummings, M. J. Kearns, A. Roth, and Z. S. Wu.  Privacy and truthful equilibrium selection for aggregative games.  In _Web and Internet Economics Conference (WINE)_ , 2015.
  * Deng et al. [2020] Y. Deng, M. M. Kamani, and M. Mahdavi.  Adaptive personalized federated learning.  _arXiv preprint arXiv:2003.13461_ , 2020.
  * Dinh et al. [2020] C. T. Dinh, N. H. Tran, and T. D. Nguyen.  Personalized federated learning with moreau envelopes.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Dwork and Roth [2014] C. Dwork and A. Roth.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Dwork et al. [2006] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In _Conference on Theory of Cryptography (TCC)_ , 2006.
  * Evgeniou and Pontil [2004] T. Evgeniou and M. Pontil.  Regularized multi-task learning.  In _Conference on Knowledge Discovery and Data Mining_ , 2004.
  * Evgeniou et al. [2005] T. Evgeniou, C. A. Micchelli, M. Pontil, and J. Shawe-Taylor.  Learning multiple tasks with kernel methods.  _Journal of Machine Learning Research_ , 6(4), 2005.
  * Geyer et al. [2017] R. C. Geyer, T. Klein, and M. Nabi.  Differentially private federated learning: A client level perspective.  _arXiv preprint arXiv:1712.07557_ , 2017.
  * Ghosh et al. [2020] A. Ghosh, J. Chung, D. Yin, and K. Ramchandran.  An efficient framework for clustered federated learning.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Ghosn and Bengio [1997] J. Ghosn and Y. Bengio.  Multi-task learning for stock selection.  In _Advances in Neural Information Processing Systems_ , 1997.
  * Gupta et al. [2016] S. K. Gupta, S. Rana, and S. Venkatesh.  Differentially private multi-task learning.  In _Pacific-Asia Workshop on Intelligence and Security Informatics_ , pages 101–113. Springer, 2016.
  * Hanzely and Richtárik [2020] F. Hanzely and P. Richtárik.  Federated learning of a mixture of global and local models.  _arXiv preprint arXiv:2002.05516_ , 2020.
  * Hanzely et al. [2020] F. Hanzely, S. Hanzely, S. Horváth, and P. Richtarik.  Lower bounds and optimal algorithms for personalized federated learning.  _Advances in Neural Information Processing Systems_ , 2020.
  * Harutyunyan et al. [2019] H. Harutyunyan, H. Khachatrian, D. C. Kale, G. Ver Steeg, and A. Galstyan.  Multitask learning and benchmarking with clinical time series data.  _Scientific data_ , 6(1):1–18, 2019.
  * Hsu et al. [2016a] J. Hsu, Z. Huang, A. Roth, T. Roughgarden, and Z. S. Wu.  Private matchings and allocations.  _SIAM Journal of Computing_ , 45(6), 2016a.
  * Hsu et al. [2016b] J. Hsu, Z. Huang, A. Roth, and Z. S. Wu.  Jointly private convex programming.  In _Symposium on Discrete Algorithms, SODA_ , 2016b.
  * Jain et al. [2021] P. Jain, J. Rush, A. Smith, S. Song, and A. G. Thakurta.  Differentially private model personalization.  In _Neural Information Processing Systems_ , 2021.
  * Kairouz et al. [2019] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Kannan et al. [2015] S. Kannan, J. Morgenstern, A. Roth, and Z. S. Wu.  Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy).  In _Symposium on Discrete Algorithms, SODA_ , 2015.
  * Kearns et al. [2014] M. J. Kearns, M. M. Pai, A. Roth, and J. R. Ullman.  Mechanism design in large games: incentives and privacy.  In M. Naor, editor, _Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014_ , pages 403–410. ACM, 2014.
  * Kirkpatrick et al. [2017] J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, et al.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the National Academy of Sciences_ , 114(13):3521–3526, 2017.
  * Laguel et al. [2021] Y. Laguel, K. Pillutla, J. Malick, and Z. Harchaoui.  A superquantile approach to federated learning with heterogeneous devices.  In _55th Annual Conference on Information Sciences and Systems, CISS 2021, Baltimore, MD, USA, March 24-26, 2021_ , pages 1–6. IEEE, 2021\.
  * Li et al. [2019] J. Li, M. Khodak, S. Caldas, and A. Talwalkar.  Differentially private meta-learning.  In _International Conference on Learning Representations_ , 2019.
  * Li et al. [2020a] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, 2020a.
  * Li et al. [2020b] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith.  Federated optimization in heterogeneous networks.  In _Conference on Machine Learning and Systems_ , 2020b.
  * Li et al. [2021] T. Li, S. Hu, A. Beirami, and V. Smith.  Ditto: Fair and robust federated learning through personalization.  In _International Conference on Machine Learning_ , pages 6357–6368. PMLR, 2021.
  * Liu et al. [2017] S. Liu, S. J. Pan, and Q. Ho.  Distributed multi-task relationship learning.  In _International Conference on Knowledge Discovery and Data Mining (ICDM)_ , pages 937–946, 2017.
  * Liu et al. [2015] Z. Liu, P. Luo, X. Wang, and X. Tang.  Deep learning face attributes in the wild.  In _International Conference on Computer Vision_ , 2015.
  * Mansour et al. [2020] Y. Mansour, M. Mohri, J. Ro, and A. T. Suresh.  Three approaches for personalization with applications to federated learning.  _arXiv preprint arXiv:2002.10619_ , 2020.
  * McMahan et al. [2017] 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_ , pages 1273–1282. PMLR, 2017.
  * McMahan et al. [2018] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang.  Learning differentially private recurrent language models.  In _International Conference on Learning Representations_ , 2018.
  * Mironov [2017] I. Mironov.  Rényi differential privacy.  In _2017 IEEE 30th Computer Security Foundations Symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Rogers and Roth [2014] R. M. Rogers and A. Roth.  Asymptotically truthful equilibrium selection in large congestion games.  In _ACM Conference on Economics and Computation_ , 2014.
  * Sattler et al. [2020] F. Sattler, K.-R. Müller, and W. Samek.  Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2020\.
  * Smith et al. [2017] V. Smith, C. Chiang, M. Sanjabi, and A. Talwalkar.  Federated multi-task learning.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Suresh et al. [2018] H. Suresh, J. J. Gong, and J. V. Guttag.  Learning tasks for multitask learning: Heterogenous patient populations in the icu.  In _International Conference on Knowledge Discovery & Data Mining_, 2018.
  * Wu et al. [2020] H. Wu, C. Chen, and L. Wang.  A Theoretical Perspective on Differentially Private Federated Multi-task Learning.  _arXiv e-prints_ , art. arXiv:2011.07179, Nov. 2020.
  * Xie et al. [2017] L. Xie, I. M. Baytas, K. Lin, and J. Zhou.  Privacy-preserving distributed multi-task learning with asynchronous updates.  In _International Conference on Knowledge Discovery and Data Mining_ , 2017.
  * Yu et al. [2020] T. Yu, E. Bagdasaryan, and V. Shmatikov.  Salvaging federated learning by local adaptation.  _arXiv preprint arXiv:2002.04758_ , 2020.
  * Zhang and Yang [2017] Y. Zhang and Q. Yang.  A survey on multi-task learning.  _arXiv preprint arXiv:1707.08114_ , 2017.
  * Zhang and Yeung [2010] Y. Zhang and D.-Y. Yeung.  A convex formulation for learning task relationships in multi-task learning.  In _Conference on Uncertainty in Artificial Intelligence_ , 2010.

##  Appendix A Appendix

###  A.1 Privacy Analysis: Proof for Theorem 1 and 2

In the proofs of Theorem 1 and 2 we follow the line of reasoning in [2], which
analyzes the privacy of DPSGD. We first state the following lemma from [2].

######  Lemma 2.

[2, Theorem 1] There exists constants $c_{1}$ and $c_{2}$ such that given the
sampling probability $p=\frac{q}{m}$ and the number of steps $T$, for any
$\epsilon<c_{1}p^{2}T$, DPSGD is $(\epsilon,\delta)$-differentially private
for any $\delta>0$ if we choose $\sigma\geq
c_{2}\frac{p\sqrt{T\log(1/\delta)}}{\epsilon}$.

To prove Theorem 1, we also need the following definitions and lemmas.

######  Definition 3 ($\ell_{2}$-sensitivity).

Let $f:\mathcal{U}\rightarrow\mathbb{R}^{d}$ be some arbitrary function, the
$\ell_{2}$-sensitivity of $f$ is defined as

$\displaystyle\Delta_{2}f=\max_{\text{adjacent
}D,D^{\prime}\in\mathcal{U}}\|f(D)-f(D^{\prime})\|_{2}$ (15)

######  Definition 4 (Rényi Divergence).

[40, Definition 3] Let $P,Q$ be two probability distribution over the same
probability space, and let $p,q$ be the respective probability density
function. The Rényi Divergence with finite order $\alpha\neq 1$ is:

$D_{\alpha}(P\|Q)=\frac{1}{\alpha-1}\ln\int_{\mathcal{X}}q(x)\bigg{(}\frac{p(x)}{q(x)}\bigg{)}^{\alpha}dx$
(16)

######  Definition 5 ($(\alpha,\epsilon)$-Rényi Differential Privacy).

[40, Definition 4] A randomized mechanism
$f:\mathcal{D}\rightarrow\mathcal{R}$ is said to have
$(\alpha,\epsilon)$-Rényi Differential Privacy if for all adjacent
$D,D^{\prime}\in\mathcal{D}$ it holds that:

$D_{\alpha}(f(D)\|f(D^{\prime}))\leq\epsilon.$ (17)

######  Lemma 3.

[40, Corollary 3] The Gaussian mechanism is
$(\alpha,\alpha(2(\Delta_{2}f)^{2}/\sigma^{2}))$-Renyi Differentially Private.

######  Lemma 4.

[40, Proposition 3] If $f$ is $(\alpha,\epsilon)$-RDP, then it is
$(\epsilon+\frac{\log(1/\delta)}{\alpha-1},\delta)$-DP for all $\delta>0$.

We begin by proving the first part of Theorem 1, where $q\neq m$.

###### Proof for Theorem 1: $q\neq m$.

Note that aggregation step in line 8 of Algorithm 1 can be rewritten as

$\displaystyle\widetilde{w}^{t+1}$
$\displaystyle=\widetilde{w}^{t}+\frac{1}{|S_{t}|}\sum_{k\in
S_{t}}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}+\mathcal{N}(0,\sigma^{2}\bf{I}_{d\times
d})$ (18) $\displaystyle=\widetilde{w}^{t}+\frac{1}{q}\sum_{k\in
S_{t}}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}+\mathcal{N}\left(0,\left(\frac{\sigma}{\gamma}\right)^{2}\gamma^{2}\bf{I}_{d\times
d}\right)$ (19) $\displaystyle=\widetilde{w}^{t}+\frac{1}{q}\left(\sum_{k\in
S_{t}}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}+\mathcal{N}\left(0,\left(\frac{q\sigma}{\gamma}\right)^{2}\gamma^{2}\bf{I}_{d\times
d}\right)\right).$ (20)

From here, we can directly apply Lemma 2 with $\sigma$ set to be
$\frac{q\sigma}{\gamma}$. Hence, we conclude that when $q\neq m$, there exists
constants $c_{1}$ and $c_{2}$ such that given the number of steps $T$, for any
$\epsilon<c_{1}\frac{q^{2}}{m^{2}}T$, $\mathcal{M}^{1:T}$ is
$(\epsilon,\delta)$-differentially private for any $\delta>0$ if we choose
$\sigma\geq c_{2}\frac{\gamma\sqrt{T\log(1/\delta)}}{m\epsilon}$. ∎

This proof can extend to the case where $q=m$. In the remainder of this
section, we provide a proof that gives a more specific bound on the variance
$\sigma^{2}$ in the case where $q=m$.

###### Proof for Theorem 1: $q=m$.

Define
$H^{t}:\prod_{i=1}^{m}\mathcal{D}_{i}\times\mathcal{W}\rightarrow\mathcal{W}$
as

$\displaystyle
H^{t}(\\{D_{i}\\},\\{h_{i}(\cdot)\\},\widetilde{w}^{t})=\widetilde{w}^{t}+\frac{1}{m}\sum_{i=1}^{m}h_{i}^{t}(D_{i},\widetilde{w}^{t}).$
(21)

As a result, we have
$\mathcal{M}^{t}(\\{D_{i}\\},\\{h_{i}(\cdot)\\},\widetilde{w}^{t},\sigma)=H^{t}(\\{D_{i}\\},\\{h_{i}(\cdot)\\},\widetilde{w}^{t})+\beta^{t}$.

By Lemma 3, $\mathcal{M}^{t}$ is
$(\alpha,2\alpha(\Delta_{2}H^{t})^{2}/d\sigma^{2})$-Renyi Differentially
Private. Note that

$\displaystyle(\Delta_{2}H^{t})^{2}$
$\displaystyle=\max_{j}\max_{\text{adjacent
}D_{j},D_{j}^{\prime}\in\mathcal{D}_{j}}\left\|H^{t}(\\{D_{1},\cdots,D_{j},\cdots,D_{m}\\})-H^{t}(\\{D_{1},\cdots,D_{j}^{\prime},\cdots,D_{m}\\})\right\|^{2}$
(22) $\displaystyle=\max_{j}\max_{\text{adjacent
}D_{j},D_{j}^{\prime}\in\mathcal{D}_{j}}\left\|\frac{1}{m}h_{j}^{t}(D_{j},\widetilde{w}^{t})-\frac{1}{m}h_{j}^{t}(D_{j}^{\prime},\widetilde{w}^{t})\right\|^{2}$
(23) $\displaystyle=\frac{1}{m^{2}}\max_{j}\max_{\text{adjacent
}D_{j},D_{j}^{\prime}\in\mathcal{D}_{j}}\left\|h_{j}^{t}(D_{j},\widetilde{w}^{t})-h_{j}^{t}(D_{j}^{\prime},\widetilde{w}^{t})\right\|^{2}$
(24) $\displaystyle=\frac{1}{m^{2}}\max_{j}(\Delta_{2}h_{j}^{t})^{2}.$ (25)

Hence, by sequential composition of Rényi Differential Privacy [40,
Proposition 1], $\mathcal{M}^{1:T}$ is
$(\alpha,\sum_{i=1}^{T}2\alpha\max_{j}(\Delta_{2}h_{j}^{t})^{2}/m^{2}\sigma^{2})$-RDP.

By Lemma 4, we know that $\mathcal{M}^{1:T}$ is
$(\sum_{i=1}^{T}2\alpha\max_{j}(\Delta_{2}h_{j}^{t})^{2}/m^{2}\sigma^{2}+\frac{\log(1/\delta)}{\alpha-1},\delta)$-DP.

Plugging in $\alpha=\frac{4\log(1/\delta)}{\epsilon}$,
$\sigma=\frac{4\gamma\sqrt{T\log(1/\delta)}}{\epsilon m}$, we have

$\displaystyle\sum_{i=1}^{T}2\alpha\max_{j}(\Delta_{2}h_{j}^{t})^{2}/m^{2}\sigma^{2}+\frac{\log(1/\delta)}{\alpha-1}$
$\displaystyle\leq\sum_{i=1}^{T}2\alpha\gamma^{2}/m^{2}\sigma^{2}+\frac{\log(1/\delta)}{\alpha-1}$
(26)
$\displaystyle=\frac{2\frac{4\log(1/\delta)}{\epsilon}\gamma^{2}}{m^{2}(\frac{4\gamma\sqrt{T\log(1/\delta)}}{\epsilon
m})^{2}}+\frac{\log(1/\delta)}{\frac{4\log(1/\delta)}{\epsilon}-1}$ (27)
$\displaystyle\leq\frac{\epsilon}{2}+\frac{\epsilon}{2}$ (28)
$\displaystyle=\epsilon.$ (29)

Hence, $\mathcal{M}^{1:T}$ is $(\epsilon,\delta)$-JDP if we choose
$\sigma=\frac{4\gamma\sqrt{T\log(1/\delta)}}{\epsilon m}$. ∎

By Theorem 1 and Billboard Lemma, it directly follows that Algorithm 1 is
$(\epsilon,\delta)-$JDP.

###### Proof for Theorem 2.

Theorem 1 shows that Algorithm 1 consists of a $(\epsilon,\delta)$-DP process
to produce global model. After that each task learner trains local model with
the DP global model and its private data. By Lemma 1, it directly follows that
Algorithm 1 is $(\epsilon,\delta)$-JDP. ∎

###  A.2 Convergence Analysis(nonconvex):

We first present the formal statement of Theorem 3.

######  Theorem 7 (Convergence under nonconvex loss).

Let $f_{k}$ be $(L+\lambda)$-smooth. Assume $\gamma$ is sufficiently large
such that
$\gamma\geq\max_{k,t}\|\nabla_{w_{k}^{t}}f_{k}(w_{k}^{t};\widetilde{w}^{t})\|_{2}$.
Further let $f_{k}^{*}=\min_{w,\bar{w}}f_{k}(w;\bar{w})$ and $p=\frac{q}{m}$.
If we use a fixed learning rate
$\eta_{t}=\eta=\frac{1}{pL+\left(p+\frac{1}{p}\right)\lambda}$, Algorithm 1
satisfies:

$\displaystyle\frac{1}{mT}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\leq$
$\displaystyle\frac{\left(4\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{2\lambda}{E\left(Lp^{2}+\lambda
p^{2}+2\lambda\right)}\right)\sum_{k=1}^{m}(f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*})}{mT}$
(30)
$\displaystyle+\frac{\mathcal{O}\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\sum_{i=1}^{T/E}B_{iE}}{T}+\mathcal{O}\left(\frac{Ld\lambda+d\lambda^{2}+d\lambda^{2}/p^{2}}{mE}\right)\sigma^{2}.$

where

$\displaystyle B_{t}=\max_{k}f_{k}(w_{k}^{t};\widetilde{w}^{t}).$ (31)

Let $\sigma$ chosen as we set in Theorem 2. Take
$T=\mathcal{O}\left(\frac{m}{\lambda d\gamma^{2}}\right)$, the right hand side
is bounded by

$\displaystyle\frac{\lambda
d\gamma^{2}}{m^{2}}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\leq$
$\displaystyle\frac{\left(4\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{2\lambda}{E\left(Lp^{2}+\lambda
p^{2}+2\lambda\right)}\right)\sum_{k=1}^{m}(f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*})}{m^{2}}$
(32)
$\displaystyle+\mathcal{O}\left(\frac{L+\lambda+\frac{\lambda}{p^{2}}}{m}\right)\lambda
d\gamma^{2}\sum_{i=1}^{\lfloor
T/E\rfloor}B_{iE}+\mathcal{O}\left(\frac{L+\lambda+\frac{\lambda}{p^{2}}}{mE}\right)\frac{\log(1/\delta)}{\epsilon^{2}}.$

###### Proof for Theorem 7.

Let $w_{k}^{*}=\operatorname*{arg\,min}_{w}f_{k}(w;\bar{w}^{*})$. Let
$I_{k}^{t}$ be the random variable indicating whether task $k$ is selected in
communication round $t$. Note that the probability task learner $k$ is
selected in any arbitrary communication round
$p_{k}=\frac{\begin{pmatrix}m-1\\\ q-1\end{pmatrix}}{\begin{pmatrix}m\\\
q\end{pmatrix}}=\frac{q}{m}$. Thus $\mathbb{E}[I_{k}^{t}]=p_{k}=\frac{q}{m}$.
By $L$-smoothness of $f_{k}$, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]$
$\displaystyle\leq\mathbb{E}\left[\langle\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t}),w_{k}^{t+1}-w_{k}^{t}\rangle+\frac{L}{2}\|w_{k}^{t+1}-w_{k}^{t}\|^{2}\right]$
(33) $\displaystyle=\mathbb{E}\left[\langle\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t}),\eta_{t}I_{k}^{t}\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\rangle+\frac{L}{2}\|\eta_{t}I_{k}^{t}\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\right]$ (34)
$\displaystyle=\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}.$ (35)

In the case where $t+1\not\equiv 0\mod E$, i.e. $t+1$ is not a communication
round, $\widetilde{w}^{t+1}=\widetilde{w}^{t}$. Therefore, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]\leq\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}.$ (36)

In the case where $t+1\equiv 0\mod E$, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]\leq\underbrace{\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t+1};\widetilde{w}^{t})]}_{\text{B}}+\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}.$ (37)

It suffices to bound B:

B
$\displaystyle=\mathbb{E}\Bigg{[}\frac{\lambda}{2}\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}-\frac{\lambda}{2}\|w_{k}^{t+1}-\widetilde{w}^{t}\|^{2}\Bigg{]}$
(38)
$\displaystyle=\frac{\lambda}{2}\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|\|2w_{k}^{t+1}-\widetilde{w}^{t}-\widetilde{w}^{t+1}\|]$
(39)
$\displaystyle\leq\frac{\lambda}{2}\sqrt{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]\mathbb{E}[\|2w_{k}^{t+1}-\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}$
(40)
$\displaystyle=\frac{\lambda}{2}\sqrt{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}\sqrt{\mathbb{E}[\|(\widetilde{w}^{t+1}-\widetilde{w}^{t})+2(w_{k}^{t+1}-\widetilde{w}^{t+1})\|^{2}]}$
(41)
$\displaystyle\leq\frac{\lambda}{2}\sqrt{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}\sqrt{\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|^{2}]+4\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}+4\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|]}$
(42)
$\displaystyle\leq\frac{\lambda}{2}\sqrt{\underbrace{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}_{\text{C}_{1}}}\sqrt{\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|^{2}]+4\underbrace{\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}}_{\text{C}_{2}}+4\sqrt{\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|^{2}]\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}}}$
(43)

where the first and third inequality follows from Cauchy-Schwartz Inequality:
$\mathbb{E}[XY]\leq\sqrt{\mathbb{E}[X^{2}]\mathbb{E}[Y^{2}]}$. We can then
upper bound $\text{C}_{1}$ and $\text{C}_{2}$.

$\displaystyle\text{C}_{1}$
$\displaystyle=\mathbb{E}\left[\left\|\frac{1}{q}\sum_{k\in
S_{t}}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}+\beta^{t}\right\|^{2}\right]$
(44)
$\displaystyle\leq\left(\sqrt{\mathbb{E}\left[\left\|\frac{1}{q}\sum_{k=1}^{m}I_{k}^{t+1}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{\mathbb{E}[\|\beta^{t}\|^{2}]}\right)^{2}$
(45)
$\displaystyle=\left(\sqrt{\mathbb{E}\left[\left\|\frac{1}{q}\sum_{k=1}^{m}I_{k}^{t+1}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{d}\sigma\right)^{2}$
(46)
$\displaystyle\leq\left(\sqrt{\frac{m}{q^{2}}\sum_{k=1}^{m}\mathbb{E}\left[\left\|I_{k}^{t+1}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{d}\sigma\right)^{2}$
(47)
$\displaystyle\leq\left(\sqrt{\frac{m}{q^{2}}\sum_{k=1}^{m}\mathbb{E}\left[\left\|I_{k}^{t+1}\eta_{t}\nabla
f_{k}(w_{k}^{t})\min\bigg{(}1,\frac{\gamma}{\eta_{t}\|\nabla
f_{k}(w_{k}^{t})\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{d}\sigma\right)^{2}$
(48)
$\displaystyle\leq\left(\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left\|\eta_{t}\nabla
f_{k}(w_{k}^{t})\min\bigg{(}1,\frac{\gamma}{\eta_{t}\|\nabla
f_{k}(w_{k}^{t})\|_{2}}\bigg{)}\right\|^{2}}+\sqrt{d}\sigma\right)^{2}.$ (49)

Denote $h(t)=\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left\|\eta_{t}\nabla
f_{k}(w_{k}^{t})\min\bigg{(}1,\frac{\gamma}{\eta_{t}\|\nabla
f_{k}(w_{k}^{t})\|_{2}}\bigg{)}\right\|^{2}}$. We have:

$\displaystyle\text{C}_{2}$
$\displaystyle\leq\frac{2}{\lambda}\frac{\lambda}{2}\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}$
(50)
$\displaystyle\leq\frac{2}{\lambda}f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})$
(51) $\displaystyle=\frac{2}{\lambda}B_{t+1}$ (52)

Plugging the bounds for $\text{C}_{1}$ and $\text{C}_{2}$ into B yields:

B
$\displaystyle\leq\frac{\lambda}{2}(h(t)+\sqrt{d}\sigma)\left(h(t)+\sqrt{d}\sigma+2\sqrt{\frac{2}{\lambda}B_{t+1}}\right).$
(53)

Denote the right hand side as $\beta(t)$, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]\leq\beta(t)+\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}.$ (54)

Let
$\delta_{t}=\mathbb{E}[f_{k}(w_{k}^{t};\widetilde{w}^{t})-f_{k}(w_{k}^{*};\bar{w}^{*})]$,
we have

$\displaystyle\delta_{t+1}$
$\displaystyle\leq\delta_{t}+\beta(t)+\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}.$ (55)

In the nonconvex case, we have

$\displaystyle\sum_{t=0}^{T-1}\left(\eta_{t}p_{k}-\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}-\beta(t)\leq
f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*}$ (56)

Summing over $k$ on the left handed side, when $\gamma$ is large enough so
that no clipping happens we have

$\displaystyle\sum_{k=1}^{m}\sum_{t+1\equiv 0\mod
E}\left(\left(\eta_{t}p_{k}-\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}-\beta(t)\right)+\sum_{t+1\not\equiv
0\mod
E}\left(\eta_{t}p_{k}-\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}$ (57) $\displaystyle=\sum_{t+1\equiv
0\mod
E}\left(\eta_{t}p-\frac{L+\lambda}{2}\eta_{t}^{2}p^{2}\right)\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}-m\beta(t)+\sum_{t+1\not\equiv 0\mod
E}\left(\eta_{t}p-\frac{L+\lambda}{2}\eta_{t}^{2}p^{2}\right)\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}$ (58) $\displaystyle=\begin{aligned}
&\sum_{t+1\equiv 0\mod
E}\left(\eta_{t}p-\frac{L+\lambda}{2}\eta_{t}^{2}p^{2}\right)\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\\\
&-\frac{\lambda}{2}\left(mh^{2}(t)+\left(2\sqrt{d}\sigma+2\sqrt{\frac{2}{\lambda}B_{t+1}}\right)mh(t)+m\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{t+1}}\right)\right)\\\
&+\sum_{t+1\not\equiv 0\mod
E}\left(\eta_{t}p-\frac{L+\lambda}{2}\eta_{t}^{2}p^{2}\right)\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\end{aligned}$ (59)
$\displaystyle=\sum_{t=0}^{T-1}\left(\eta_{t}p-\frac{L+\lambda}{2}\eta_{t}^{2}p^{2}\right)G_{t}^{2}+\sum_{t+1\not\equiv
0\mod
E}-\frac{\lambda}{2}\eta_{t}^{2}G_{t}^{2}-\lambda\sqrt{m}\left(\sqrt{d}\sigma+\sqrt{\frac{2}{\lambda}B_{t+1}}\right)\eta_{t}G_{t}-\frac{\lambda
m}{2}\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{t+1}}\right)$ (60)
$\displaystyle\leq\sum_{k=1}^{m}f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*},$
(61)

where $G_{t}=\sqrt{\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}}$. Picking
$\eta_{t}=\frac{p}{p^{2}L+(p^{2}+1)\lambda}$ yields

$\displaystyle\sum_{t+1\equiv 0\mod
E}\frac{p^{2}}{2(p^{2}L+(p^{2}+1)\lambda)}G_{t}^{2}-\frac{\lambda\sqrt{m}\left(\sqrt{d}\sigma+\sqrt{\frac{2}{\lambda}B_{t+1}}\right)p}{p^{2}L+(p^{2}+1)\lambda}G_{t}-\frac{\lambda
m}{2}\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{t+1}}\right)$ (62)
$\displaystyle+\sum_{t+1\not\equiv 0\mod
E}\frac{p^{2}(p^{2}L+(p^{2}+2)\lambda)}{2(p^{2}L+(p^{2}+1)\lambda)^{2}}G_{t}^{2}$
(63)
$\displaystyle\leq\sum_{k=1}^{m}f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*}.$
(64)

This is equivalent to

$\displaystyle\sum_{t=0}^{T-1}G_{t}^{2}+\sum_{t+1\equiv 0\mod
E}-2\lambda\sqrt{m}\left(\sqrt{d}\sigma+\sqrt{\frac{2}{\lambda}B_{t+1}}\right)\frac{m}{q}G_{t}-\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\lambda
m\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{t+1}}\right)$ (65)
$\displaystyle\leq\left(2\frac{1}{E}\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+2\frac{E-1}{E}\frac{\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)^{2}}{L+\lambda+\frac{2}{p^{2}}\lambda}\right)\sum_{k=1}^{m}f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*}$
(66)
$\displaystyle=\left(2\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{\frac{1}{p^{2}}\lambda}{E\left(L+\lambda+\frac{2}{p^{2}}\lambda\right)}\right)\sum_{k=1}^{m}f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*}.$
(67)

Hence, we have

$\displaystyle\sum_{t+1\equiv 0\mod E}\left(G_{t}-\lambda
m\left(\sqrt{d}\sigma+\sqrt{\frac{2}{\lambda}B_{t+1}}\right)\frac{1}{p}\right)^{2}+\sum_{t+1\not\equiv
0\mod E}G_{t}^{2}$ (68)
$\displaystyle\leq\left(2\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{\frac{1}{p^{2}}\lambda}{E\left(L+\lambda+\frac{2}{p^{2}}\lambda\right)}\right)\sum_{k=1}^{m}f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*}$
(69) $\displaystyle+\sum_{t+1\equiv 0\mod E}(L\lambda
m+m\lambda^{2})\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{t+1}}\right)+2\frac{m\lambda
B_{t+1}}{p^{2}}.$ (70)

This implies

$\displaystyle\sum_{t=0}^{T-1}G_{t}^{2}$ $\displaystyle\leq
2\left(2\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{\frac{1}{p^{2}}\lambda}{E\left(L+\lambda+\frac{2}{p^{2}}\lambda\right)}\right)\sum_{k=1}^{m}f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*}$
(71) $\displaystyle+2\left(\sum_{t+1\equiv 0\mod E}(L\lambda
m+m\lambda^{2}+\frac{2\lambda^{2}m}{p^{2}})\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{t+1}}\right)+4\frac{m\lambda
B_{t+1}}{p^{2}}\right).$ (72)

Hence, we conclude that

$\displaystyle\frac{1}{mT}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}$ (73)
$\displaystyle\leq\frac{\left(4\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{2\lambda}{E\left(Lp^{2}+\lambda
p^{2}+2\lambda\right)}\right)\sum_{k=1}^{m}(f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*})}{mT}+\frac{\mathcal{O}\left(L\lambda+\lambda^{2}+\frac{\lambda^{2}}{p^{2}}\right)\sum_{i=1}^{T/E}\left(d\sigma^{2}+2\sigma\sqrt{\frac{2d}{\lambda}B_{iE}}+\frac{2B_{iE}}{\lambda}\right)}{T}$
(74)
$\displaystyle\leq\frac{\left(4\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{2\lambda}{E\left(Lp^{2}+\lambda
p^{2}+2\lambda\right)}\right)\sum_{k=1}^{m}(f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*})}{mT}+\frac{\mathcal{O}\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\sum_{i=1}^{T/E}\left(\sqrt{d\lambda}\sigma+\sqrt{2B_{iE}}\right)^{2}}{T}$
(75) $\displaystyle\leq\begin{aligned}
\frac{\left(4\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{2\lambda}{E\left(Lp^{2}+\lambda
p^{2}+2\lambda\right)}\right)\sum_{k=1}^{m}(f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*})}{mT}&+\frac{\mathcal{O}\left(L+\lambda+\frac{\lambda
m^{2}}{q^{2}}\right)\sum_{i=1}^{T/E}B_{iE}}{T}\\\
&+\mathcal{O}\left(\frac{Ld\lambda+d\lambda^{2}+d\lambda^{2}/p^{2}}{mE}\right)\sigma^{2}\end{aligned}.$
(76)

Taking $\sigma=\frac{c_{2}\gamma\sqrt{T\log(1/\delta)}}{m\epsilon}$ and
$T=\mathcal{O}\left(\frac{m}{\lambda d\gamma^{2}}\right)$, we have

$\displaystyle\frac{1}{mT}\sum_{t=0}^{T-1}\sum_{k=1}^{m}\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}$
$\displaystyle\leq\frac{\left(4\left(L+\lambda+\frac{1}{p^{2}}\lambda\right)+\frac{2\lambda}{E\left(Lp^{2}+\lambda
p^{2}+2\lambda\right)}\right)\sum_{k=1}^{m}(f_{k}(w_{k}^{0};\widetilde{w}^{0})-f_{k}^{*})}{mT}$
(77)
$\displaystyle+\frac{\mathcal{O}\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\sum_{t=0}^{T-1}B_{t+1}}{T}+\frac{1}{mE}\mathcal{O}\left(L+\lambda+\frac{\lambda}{p^{2}}\right)\frac{\log(1/\delta)}{\epsilon^{2}}.$
(78)

∎

###  A.3 Convergence Analysis (Convex):

We first present the formal statement of Theorem 5.

######  Theorem 8.

Let $f_{k}$ be $(L+\lambda)$-smooth and $(\mu+\lambda)$-strongly convex.
Assume $\gamma$ is sufficiently large such that
$\gamma\geq\max_{k,t}\|\nabla_{w_{k}^{t}}f_{k}(w_{k}^{t};\widetilde{w}^{t})\|_{2}$.
Further let $w_{k}^{*}=\operatorname*{arg\,min}_{w}f_{k}(w;\bar{w}^{*})$,
where $\bar{w}^{*}=\frac{1}{m}\sum_{k=1}^{m}w_{k}^{*}$ and $p=\frac{q}{m}$. If
we use a fixed learning rate $\eta_{t}=\eta=\frac{cp}{Lp^{2}+\lambda
p^{2}-2\lambda}$ for some constant $c$ such that $0\leq 1-\eta
p(c-2)(\mu+\lambda)\leq\frac{1}{2}$, Algorithm 1 satisfies:

$\displaystyle\Delta_{T}\leq\frac{1}{2^{T}}\left(\Delta_{0}-m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)\right)+\frac{m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)}{1-\frac{1}{2^{E}}},$
(79)

where
$\Delta_{t}=\sum_{k=1}^{m}f_{k}(w_{k}^{t};\widetilde{w}^{t})-f_{k}(w_{k}^{*};\widetilde{w}^{*})$
and $B=\max_{t}\max_{k}f_{k}(w_{k}^{t};\widetilde{w}^{t})$.

Let $\sigma$ be chosen as in Theorem 2, then there exists
$T=\mathcal{O}\left(\frac{m}{\lambda d\gamma^{2}}\right)$ such that

$\displaystyle\frac{1}{m}\Delta_{T}\leq\frac{1}{2^{T}}\left(\frac{1}{m}\Delta_{0}-\frac{\log(1/\delta)}{m\epsilon^{2}}-\mathcal{O}\left(B\right)\right)+\frac{\frac{\log(1/\delta)}{m\epsilon^{2}}+\mathcal{O}\left(B\right)}{1-\frac{1}{2^{E}}}.$
(80)

###### Proof for Theorem 8.

Let $w_{k}^{*}=\operatorname*{arg\,min}_{w}f_{k}(w;\bar{w}^{*})$. Let
$I_{k}^{t}$ be the random variable indicating whether task $k$ is selected in
communication round $t$. Thus $\mathbb{E}[I_{k}^{t}]=p_{k}$. By
$L+\lambda$-smoothness and $\mu+\lambda$-strong convexity of $f_{k}$, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]$
$\displaystyle\leq\mathbb{E}\left[\langle\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t}),w_{k}^{t+1}-w_{k}^{t}\rangle+\frac{L}{2}\|w_{k}^{t+1}-w_{k}^{t}\|^{2}\right]$
(81) $\displaystyle=\mathbb{E}\left[\langle\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t}),\eta_{t}I_{k}^{t}\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\rangle+\frac{L}{2}\|\eta_{t}I_{k}^{t}\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}\right]$ (82)
$\displaystyle=\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)\|\nabla
f_{k}(w_{k}^{t};\widetilde{w}^{t})\|^{2}$ (83)
$\displaystyle\leq\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)2(\mu+\lambda)(f(w_{k}^{t};\widetilde{w}^{t})-f(w_{k}^{*};\widetilde{w}^{t}))$
(84)
$\displaystyle\leq\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)2(\mu+\lambda)(f(w_{k}^{t};\widetilde{w}^{t})-f(w_{k}^{*};\widetilde{w}^{*})).$
(85)

In the case where $t+1\not\equiv 0\mod E$, i.e. $t+1$ is not a communication
round, $\widetilde{w}^{t+1}=\widetilde{w}^{t}$. Therefore, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]\leq\left(\frac{L+\lambda}{2}\eta_{t}^{2}p_{k}^{2}-\eta_{t}p_{k}\right)2(\mu+\lambda)(f(w_{k}^{t};\widetilde{w}^{t})-f(w_{k}^{*};\widetilde{w}^{*})).$
(86)

In the case where $t+1\equiv 0\mod E$, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]\leq$
$\displaystyle\underbrace{\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t+1};\widetilde{w}^{t})]}_{\text{B}}$
(87)
$\displaystyle+\left((L+\lambda)\eta_{t}^{2}p_{k}^{2}-2\eta_{t}p_{k}\right)(\mu+\lambda)(f(w_{k}^{t};\widetilde{w}^{t})-f_{k}^{*}).$

It suffices to bound B:

B
$\displaystyle=\mathbb{E}\Bigg{[}\frac{\lambda}{2}\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}-\frac{\lambda}{2}\|w_{k}^{t+1}-\widetilde{w}^{t}\|^{2}\Bigg{]}$
(88)
$\displaystyle=\frac{\lambda}{2}\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|\|2w_{k}^{t+1}-\widetilde{w}^{t}-\widetilde{w}^{t+1}\|]$
(89)
$\displaystyle\leq\frac{\lambda}{2}\sqrt{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]\mathbb{E}[\|2w_{k}^{t+1}-\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}$
(90)
$\displaystyle=\frac{\lambda}{2}\sqrt{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}\sqrt{\mathbb{E}[\|(\widetilde{w}^{t+1}-\widetilde{w}^{t})+2(w_{k}^{t+1}-\widetilde{w}^{t+1})\|^{2}]}$
(91)
$\displaystyle\leq\frac{\lambda}{2}\sqrt{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}\sqrt{\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|^{2}]+4\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}+4\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|]}$
(92)
$\displaystyle\leq\frac{\lambda}{2}\sqrt{\underbrace{\mathbb{E}[\|\widetilde{w}^{t}-\widetilde{w}^{t+1}\|^{2}]}_{\text{C}_{1}}}\sqrt{\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|^{2}]+4\underbrace{\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}}_{\text{C}_{2}}+4\sqrt{\mathbb{E}[\|\widetilde{w}^{t+1}-\widetilde{w}^{t}\|^{2}]\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}}}$
(93)

where the first and third inequality follows from Cauchy-Schwartz Inequality:
$\mathbb{E}[XY]\leq\sqrt{\mathbb{E}[X^{2}]\mathbb{E}[Y^{2}]}$. It suffices to
find the upper bound of $\text{C}_{1}$ and $\text{C}_{2}$.

$\displaystyle\text{C}_{1}$
$\displaystyle=\mathbb{E}\left[\left\|\frac{1}{q}\sum_{k\in
S_{t}}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}+\beta^{t}\right\|^{2}\right]$
(94)
$\displaystyle\leq\left(\sqrt{\mathbb{E}\left[\left\|\frac{1}{q}\sum_{k=1}^{m}I_{k}^{t+1}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{\mathbb{E}[\|\beta^{t}\|^{2}]}\right)^{2}$
(95)
$\displaystyle=\left(\sqrt{\mathbb{E}\left[\left\|\frac{1}{q}\sum_{k=1}^{m}I_{k}^{t+1}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{d}\sigma\right)^{2}$
(96)
$\displaystyle\leq\left(\sqrt{\frac{m}{q^{2}}\sum_{k=1}^{m}\mathbb{E}\left[\left\|I_{k}^{t+1}g_{k}^{t+1}\min\bigg{(}1,\frac{\gamma}{\|g_{k}^{t+1}\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{d}\sigma\right)^{2}$
(97)
$\displaystyle\leq\left(\sqrt{\frac{m}{q^{2}}\sum_{k=1}^{m}\mathbb{E}\left[\left\|I_{k}^{t+1}\eta_{t}\nabla
f_{k}(w_{k}^{t})\min\bigg{(}1,\frac{\gamma}{\eta_{t}\|\nabla
f_{k}(w_{k}^{t})\|_{2}}\bigg{)}\right\|^{2}\right]}+\sqrt{d}\sigma\right)^{2}$
(98)
$\displaystyle\leq\left(\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left\|\eta_{t}\nabla
f_{k}(w_{k}^{t})\min\bigg{(}1,\frac{\gamma}{\eta_{t}\|\nabla
f_{k}(w_{k}^{t})\|_{2}}\bigg{)}\right\|^{2}}+\sqrt{d}\sigma\right)^{2}.$ (99)

Denote $h(t)=\sqrt{\frac{1}{m}\sum_{k=1}^{m}\left\|\eta_{t}\nabla
f_{k}(w_{k}^{t})\min\bigg{(}1,\frac{\gamma}{\eta_{t}\|\nabla
f_{k}(w_{k}^{t})\|_{2}}\bigg{)}\right\|^{2}}$. On the other hand,

$\displaystyle\text{C}_{2}$
$\displaystyle\leq\frac{2}{\lambda}\frac{\lambda}{2}\|w_{k}^{t+1}-\widetilde{w}^{t+1}\|^{2}$
(100)
$\displaystyle\leq\frac{2}{\lambda}f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})$
(101) $\displaystyle=\frac{2}{\lambda}B_{t+1}.$ (102)

Plug the bounds for $\text{C}_{1}$ and $\text{C}_{2}$ into B:

B
$\displaystyle\leq\frac{\lambda}{2}(h(t)+\sqrt{d}\sigma)\left(h(t)+\sqrt{d}\sigma+2\sqrt{\frac{2}{\lambda}B_{t+1}}\right)$
(103)
$\displaystyle\leq\lambda\left(h^{2}(t)+d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B_{t+1}}+\frac{1}{\lambda}B_{t+1}\right)$
(104)

Denoting the right hand side as $\beta(t)$, we have

$\displaystyle\mathbb{E}[f_{k}(w_{k}^{t+1};\widetilde{w}^{t+1})-f_{k}(w_{k}^{t};\widetilde{w}^{t})]\leq\beta(t)+\left((L+\lambda)\eta_{t}^{2}p_{k}^{2}-2\eta_{t}p_{k}\right)(\mu+\lambda)(f(w_{k}^{t};\widetilde{w}^{t})-f_{k}^{*}).$
(105)

Letting
$\delta_{k}^{t}=\mathbb{E}[f_{k}(w_{k}^{t};\widetilde{w}^{t})-f_{k}(w_{k}^{*};\bar{w}^{*})]$,
we have

$\displaystyle\delta_{k}^{t+1}\leq\left(1-\left((L+\lambda)\eta_{t}^{2}p_{k}^{2}-2\eta_{t}p_{k}\right)(\mu+\lambda)\right)\delta_{k}^{t}+\beta(t)$
(106)

Summing over $k$ on the left handed side, when $\gamma$ is large enough so
that no clipping happens we have

$\displaystyle\sum_{k=1}^{m}\delta_{k}^{t+1}$
$\displaystyle\leq\left(1-\left((L+\lambda)\eta_{t}^{2}p^{2}-2\eta_{t}p\right)(\mu+\lambda)\right)\sum_{k=1}^{m}\delta_{k}^{t}+m\beta(t)$
(107) $\displaystyle=\left(1-\left((Lp^{2}+\lambda
p^{2}-2\lambda)\eta_{t}^{2}-2\eta_{t}p\right)(\mu+\lambda)\right)\sum_{k=1}^{m}\delta_{k}^{t}+m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B_{t+1}}+\frac{1}{\lambda}B_{t+1}\right).$
(108)

Let $\Delta_{t}=\sum_{k=1}^{m}\delta_{k}^{t}$. Assume $\max_{t\leq T}B_{t}=B$.
Pick
$C=\frac{m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)}{\left((Lp^{2}+\lambda
p^{2}-2\lambda)\eta_{t}^{2}-2\eta_{t}p\right)(\mu+\lambda)}$, we have

$\displaystyle\Delta_{t+1}-C\leq\left(1-\left((Lp^{2}+\lambda
p^{2}-2\lambda)\eta_{t}^{2}-2\eta_{t}p\right)(\mu+\lambda)\right)(\Delta_{t}-C).$
(109)

Note that in the case where $t+1\not\equiv 0\mod E$, we have

$\displaystyle\Delta_{t+1}$ $\displaystyle\leq\left(1-\left((Lp^{2}+\lambda
p^{2})\eta_{t}^{2}-2\eta_{t}p\right)(\mu+\lambda)\right)\Delta_{t}$ (110)
$\displaystyle\leq\left(1-\left((Lp^{2}+\lambda
p^{2}-2\lambda)\eta_{t}^{2}-2\eta_{t}p\right)(\mu+\lambda)\right)\Delta_{t}.$
(111)

Choose $\eta_{t}=\eta=\frac{cp}{Lp^{2}+\lambda p^{2}-2\lambda}$ for some
constant $c$ such that $0<\left(1-\left((Lp^{2}+\lambda
p^{2}-2\lambda)\eta_{t}^{2}-2\eta_{t}p\right)(\mu+\lambda)\right)<\frac{1}{2}$.
We have

$\displaystyle\Delta_{t+1}-C$
$\displaystyle\leq\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)(\Delta_{t}-C)$
(112)
$\displaystyle\leq\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)\left(\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)^{E-1}\Delta_{t-E+1}-C\right).$
(113)

This is equivalent to

$\displaystyle\Delta_{t+1}-D\leq\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)^{E}(\Delta_{t-E+1}-D)$
(114)

where

$\displaystyle D$
$\displaystyle=\frac{\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}}{1-\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)^{E}}C$
(115)
$\displaystyle=\frac{m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)}{1-\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)^{E}}$
(116)
$\displaystyle\in\left(m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right),\frac{m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)}{1-\frac{1}{2^{E}}}\right].$
(117)

Apply recursively to all $t$, we obtain

$\displaystyle\Delta_{T}$
$\displaystyle\leq\left(1-\frac{(c^{2}-2c)(\mu+\lambda)}{L+\lambda-\frac{2\lambda}{p^{2}}}\right)^{T}\left(\Delta_{0}-D\right)+D$
(118)
$\displaystyle\leq\frac{1}{2^{T}}\left(\Delta_{0}-m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)\right)+\frac{m\lambda\left(d\sigma^{2}+2\sqrt{d}\sigma\sqrt{\frac{2}{\lambda}B}+\frac{1}{\lambda}B\right)}{1-\frac{1}{2^{E}}}.$
(119)

Take $\sigma=\frac{c_{2}\gamma\sqrt{T\log(1/\delta)}}{m\epsilon}$ and we can
find $T=\mathcal{O}\left(\frac{m}{\lambda d\gamma^{2}}\right)$ such that,

$\displaystyle\Delta_{T}\leq\frac{1}{2^{T}}\left(\Delta_{0}-\frac{\log(1/\delta)}{\epsilon^{2}}-\mathcal{O}\left(mB\right)\right)+\frac{\frac{\log(1/\delta)}{\epsilon^{2}}+\mathcal{O}\left(mB\right)}{1-\frac{1}{2^{E}}}.$
(120)

Divide both side by $m$, we have

$\displaystyle\frac{1}{m}\Delta_{T}\leq\frac{1}{2^{T}}\left(\frac{1}{m}\Delta_{0}-\frac{\log(1/\delta)}{m\epsilon^{2}}-\mathcal{O}\left(B\right)\right)+\frac{\frac{\log(1/\delta)}{m\epsilon^{2}}+\mathcal{O}\left(B\right)}{1-\frac{1}{2^{E}}}.$
(121)

∎

###  A.4 Datasets and Models

We summarize the details of the datasets and models we used in our empirical
study in Table 2. Our experiments include both convex (Logistic Regression)
and non-convex (CNN) loss objectives on both text (StackOverflow) and image
(CelebA and FEMNIST) datasets. We provide anonymized code in the supplementary
material for reproducibility. Our code makes use of the FL implementation from
the public repo of Laguel et al. [30] and Li et al. [34].

Table 2:

Dataset | Number of tasks | Model | Task Type
---|---|---|---
FEMNIST [8, 5] | 205 | 4-layer CNN | 62-class image classification
StackOverflow [1] | 400 | Logistic Regression | 500-class tag prediction
CelebA [36, 5] | 515 | 4-layer CNN | Binary image classification

###  A.5 Comparison with FedProx

Besides FedAvg, we also compared private mean-regularized MTL with other
methods that aims to train a global model privately. In particular, we studied
private FedProx [33] as an alternative global baseline. Note that although the
local objective being solved in FedProx is similar to that in mean-regularized
MTL, FedProx is a fundamentally different method to handle data heterogeneity
in FL from MTL. Specifically, FedProx learns a global model where each client
solves an inexact minimizer by optimizing local empirical risk with a
regularization term. We instead explore learning a multi-task objective where
each client solves a mean-regularized objective and learns a separate, client-
specific model. The results are shown in Figure 8. In all three datasets,
private FedProx is very similar to private FedAvg under different private
parameters $\epsilon$ and worse than private MTL. In particular, in FEMNIST
and Stackoverflow, private MTL significantly outperforms training a private
global model (FedAvg and FedProx), for all $\epsilon$’s.

(a) StackOverflow tag prediction

(b) FEMNIST

(c) CelebA

Figure 8: Comparison of PMTL and training a private global
model(FedAvg/FedProx).