# Faithful Edge Federated Learning:
Scalability and Privacy

Meng Zhang, , Ermin Wei, , Randall Berry  Part of this work has been presented
at NetEcon 2021 [1]. This work was supported in part by NSF grants
CNS-1908807, AST-2037838, and ECCS-2030251. Meng Zhang is with the Zhejiang
University/University of Illinois at Urbana–Champaign Institute, Zhejiang
University, Haining 314400, China (e-mail:jackeymzhang@gmail.com). Part of
this work was performed while he was at Northwestern University. Ermin Wei and
Randall Berry are with the Department of Electrical and Computer Engineering,
Northwestern University, Evanston, IL 60208 USA (e-mail:
<EMAIL_ADDRESS>rberry@northwestern.edu).

###### Abstract

Federated learning enables machine learning algorithms to be trained over
decentralized edge devices without requiring the exchange of local datasets.
Successfully deploying federated learning requires ensuring that agents (e.g.,
mobile devices) faithfully execute the intended algorithm, which has been
largely overlooked in the literature. In this study, we first use risk bounds
to analyze how the key feature of federated learning, unbalanced and
non-i.i.d. data, affects agents’ incentives to voluntarily participate and
obediently follow traditional federated learning algorithms. To be more
specific, our analysis reveals that agents with less typical data
distributions and relatively more samples are more likely to opt out of or
tamper with federated learning algorithms. To this end, we formulate the first
faithful implementation problem of federated learning and design two faithful
federated learning mechanisms which satisfy economic properties, scalability,
and privacy. First, we design a Faithful Federated Learning (FFL) mechanism
which approximates the Vickrey–Clarke–Groves (VCG) payments via an incremental
computation. We show that it achieves (probably approximate) optimality,
faithful implementation, voluntary participation, and some other economic
properties (such as budget balance). Further, the time complexity in the
number of agents $K$ is $\mathcal{O}(\log(K))$. Second, by partitioning agents
into several clusters, we present a scalable VCG mechanism approximation. We
further design a scalable and Differentially Private FFL (DP-FFL) mechanism,
the first differentially private faithful mechanism, that maintains the
economic properties. Our DP-FFL mechanism enables one to make three-way
performance tradeoffs among privacy, the iterations needed, and payment
accuracy loss.

###### Index Terms:

Federated learning, mechanism design, game theory, differential privacy,
faithful implementation.

##  I Introduction

###  I-A Motivation

Machine learning applications often rely on cloud-based datacenters to collect
and process the vast amount of needed training data. Due to the proliferation
of Internet-of-Things (IoT) applications, much of this data is generated by
devices in wireless edge networks. In addition, relatively slow growth in
network bandwidth, high latency, and data privacy concerns may make it
infeasible or undesirable to upload all the data to a remote cloud, leading
some to project that $90\%$ of the global data will be stored and processed
locally [2]. Federated learning is a nascent solution to retain data in
wireless edge networks and perform machine learning training distributively
across end-user devices and edge servers (also called edge clouds) (e.g., [3,
4, 5, 6, 8, 9, 7, 12, 13, 14, 15, 10, 11, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25]).

Federated learning algorithms aim to fit models to data generated by multiple
distributed devices. The large-scale deployment of federated learning relies
on overcoming the following two main technical challenges: the statistical
challenge and the communication challenge [3, 4, 5]. Specifically, each agent
(the owner of each device) generates data in a non-independently and
identically distributed (non-i.i.d.) manner, with the dataset on each device
being generated by a distinct distribution and the local dataset size varying
greatly. Second, communication is often a significant bottleneck in a
federated learning framework, motivating the design of communication-efficient
federated learning algorithms. These have been motivating extensive studies on
improving efficiency by designing new training models, fast algorithms and
quantization techniques (e.g., [12, 13]). Other studies have been designing
algorithms for resource allocation, mobile user selection, energy efficient,
scheduling, and new communication techniques in wireless edge networks (e.g.,
[17, 18, 19, 20, 21, 22, 23, 24, 25]).

Nevertheless, whereas many existing federated learning algorithms assume that
agents are obedient, i.e., they are willing to follow the algorithms (e.g.,
[3, 4, 5, 6, 8, 9, 7, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25]), edge devices in practice may be strategic and may tamper with or opt out
of federated learning algorithms to their own advantages. Such strategic edge
devices would be more likely to arise in a wireless setting, where different
devices may connect and participate in federated learning at different times.
Therefore, the success of deploying federated learning relies on strategic
agents’ voluntary participation (into the federation) and faithful execution
of distributed federated learning algorithms. Generally speaking, there are
two key factors that may incentivize agents to strategically manipulate
federated learning:

  * •

federated learning may incur significant resource consumption (e.g., energy,
bandwidth, and time) for mobile devices;

  * •

agents have different preferences over prediction outcomes (due to, e.g.,
non-i.i.d and unbalanced data).

The above issues reflect an agent’s dual role as a contributor and a client in
a federated learning setting, respectively. That is, agents demand for both
rewards for contributing and preferred prediction outcomes. This work focuses
on the latter issue that has been overlooked in the literature, whereas
existing studies mainly have been attempting to solve the former one (see the
survey in [26] and references [27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39]) by designing incentive mechanisms to reward agents according to agents’
data quality, quantity, and reputation. Specifically, non-i.i.d. and
unbalanced data may render different prediction objectives for different
individual agents and hence may incentivize strategic manipulation. In this
case, each strategic agent can choose either to opt out of or to tamper with
the federated learning algorithms to its own advantage. Such a behavior may
result in the failure of large-scale deployments of edge federated learning.
To this end, this paper will first answer the following question:

######  Question 1.

How do unbalanced data and non-i.i.d. data distributions disincentivize agents
to obediently follow and voluntarily participate into federated learning
algorithms?

To overcome this issue of manipulation, one approach for the server is to
leverage (economic) mechanism design, by anticipating agents’ strategic
behaviors. As a seminal example, the Vickrey–Clarke–Groves (VCG) mechanism
[40] is a generic truthful mechanism for achieving a socially-optimal
solution, while ensuring agents’ voluntary participation and incentive
compatibility, i.e., truthful reports of their local information. However,
many such mechanisms use a central authority that computes the optimal
solution, which is not applicable in the framework of federated learning. To
achieve distributed implementation of mechanisms, existing studies have
developed faithful mechanisms (e.g. [41, 42, 43, 44]), which prevent agents
from deviating from the intended algorithms (e.g., by manipulating computation
or information reporting).

We note that existing studies on centralized and distributed mechanisms,
however, have not addressed the problem of federated learning due to the
following important considerations:

  * •

Scalability: Mobile devices are expected to be massively distributed (i.e.,
the number of agents may be much larger than the average samples per agent)
and have limited communication capability [3, 4, 5]. However, existing VCG-
based approaches [40] involve solving $K+1$ optimization problems (where $K$
is the number of agents), which makes them impractical for large-scale
systems.

  * •

Unknown data distributions: Existing mechanisms assume that agents know their
exact objectives, whereas in federated learning agents’ expected objectives
are unknown to themselves, since their underlying data distributions are
unknown.

  * •

Privacy: Federated learning often involves training predictive models based on
individuals’ private local datasets that contain highly sensitive information
(e.g., medical records and web browsing history). For instance, multiple
hospitals forecast cancer risks by performing federated learning over the
whole patient population, while privacy laws prohibit sharing private patient
data [9]. However, existing economic mechanisms require strategic agents to
reveal their objective values, which may violate such privacy
requirements.111Specifically, Roberts’ theorem states that, under mild
conditions, the only incentive compatible mechanisms are VCG variants, which
requires the revelation of agents’ private information of their loss functions
[40].

These motivate the following key question:

######  Question 2.

How should one design a faithful federated learning mechanism that also
achieves voluntary participation, scalability, and privacy preservation?

###  I-B Our Work

In light of the challenges above, this paper studies mechanism design for two
representative edge federated learning scenarios aiming at achieving scalable,
privacy-preserving, and faithful edge federated learning. Similar ideas could
be applied to other federated learning algorithms.222We note that designing
federated learning algorithms with state-of-the-art performances (e.g.,
convergence speed, cost-effectiveness, privacy, and robustness) is beyond the
scope of this work. We summarize our key contributions in the following:

  * •

Analysis of risk bounds. We analyze how the key feature in federated learning,
non-i.i.d. and unbalanced data, affects agents’ incentives to voluntarily
participate and obediently follow the algorithms. Specifically, our analysis
reveals that an agent with a less typical data distribution and relatively
more data samples tends to have a greater incentive to opt out of or tamper
with federated learning algorithms.

  * •

Faithful federated learning. We design the first faithful mechanism for
federated learning. It approximates the VCG mechanism and achieves (probably
approximate) optimality, faithful implementation, voluntary participation, and
some other economic properties (such as budget balance). Further, the time
complexity in the number of agents $K$ is $\mathcal{O}(\log(K))$.

  * •

Differentially private faithful federated learning. By partitioning agents
into several clusters, we present a scalable VCG mechanism approximation with
square root iteration complexity. Based on it, we further design a
Differentially-Private Faithful Federated Learning (DP-FFL) mechanism that is
scalable while maintaining VCG’s economic properties. In addition, our DP-FFL
mechanism enables one to make three-way performance tradeoffs among privacy,
convergence, and payment accuracy loss. To the best of our knowledge, this is
the first differentially private and faithful mechanism.

##  II Literature Review

Federated Learning. The existing literature has studied how to make the model
sharing process more privacy-preserving (e.g., [6, 7, 8, 9]), more secure
(e.g., [10, 11]), more efficient (e.g., [12, 13]), and more robust (e.g., [14,
15]) against heterogeneity in the distributed data sources among many other
works. For a more detailed survey, please refer to [16]. On the other hand,
extensive studies attempting to improve the efficiency can be categorized into
two directions: algorithmic and communication design. First, by designing new
techniques including quantization (e.g., [12]) and new novel learning models
(e.g., multi-task federated learning [13]). Second, in wireless edge networks,
efforts have studied resource allocation algorithms for edge nodes (e.g.,
[18]), scheduling policies against interference (e.g., [19, 25]), mobile user
selection and resource allocation algorithms (e.g., [21, 22]) and new
communication techniques (e.g., over-the-air computation [23]). However, this
line of work assumes that agents (in addition to malicious attackers as in
[10, 11]) are willing to participate into federated learning and obey the
algorithms, whereas agents in practice are strategic and require proper
incentives to do so.

In terms of incentive design for federated learning, which has been listed as
an outstanding problem in [5], only a few recent studies attempted to address
this issue [27, 28, 29, 30, 31, 32, 33, 34, 35, 5, 36, 37, 38, 39]. Reference
[36] describes a payoff sharing algorithm that maximizes the system designer’s
utility without considering agents’ strategic behaviors. Yu et al. in [37]
introduced fairness guarantees to the previous reward system. Other studies
have been considering economic approaches to compensating agents’
communication and computation costs based on economic approaches such as
contract theory (e.g., [38, 31, 28]), Stackelberg game [35, 32], auction
theory (e.g., [33, 29]), and reputation [31]. However, this line of work
focused on incentivizing agent participation by compensating them for their
costs and eliciting their truthful cost information, but assumed that agents
are obedient to follow federated learning algorithms without strategic
manipulation.

Faithful Mechanisms. Only a few studies in the literature considered faithful
mechanism design (e.g., [41, 42, 43, 44]). Faithful implementation was first
introduced by Parkes et al. in [41]: a mechanism is faithful if no one can
benefit from deviating, including information revelation, computation, and
message passing. Feigenbaum et al. proposed a faithful policy-based inter-
domain routing in [42]. Petcu et al. in [43] generalized the above results and
achieve faithfulness for general distributed constrained optimization
problems. However, none of the existing studies on faithful implementation
guaranteed differential privacy or scalability, or performed risk bound
analysis in a (statistical) learning framework.

##  III System Model and Problem Formulation

###  III-A System Overview

In this section, we introduce our federated learning model which aims to fit a
global model over data that resides on, and has been generated by, a set
$\mathcal{K}\triangleq\\{k:1\leq k\leq K\\}$ of agents (with distributed edge
devices). The model also consists of a trusted (parameter) server. Each agent
(e.g., a mobile device) has access to a local dataset
$\mathcal{D}_{k}=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{n_{k}}$, where
$\boldsymbol{x}_{i}\in\mathcal{X}\subset\mathbb{R}^{d}$,
$y_{i}\in\mathcal{Y}\subset\mathbb{R}$, $n_{k}=|\mathcal{D}_{k}|$ is the
number of agent $k$’s data samples, and $|\cdot|$ denotes the cardinality of a
set. Sets $\mathcal{X}$ and $\mathcal{Y}$ are compact. We use
$n\triangleq\sum_{k\in\mathcal{K}}n_{k}$ to denote the total number of data
samples and $\mathcal{D}\triangleq\bigcup_{k\in\mathcal{K}}\mathcal{D}_{k}$ to
denote the global dataset. The training data across the agents are often
non-i.i.d., since the data of a given client is typically based on the usage
of the particular edge device and may not be representative of the population
distribution (e.g., [3]). To model the non-i.i.d. nature of the data, we
assume that, every agent $k\in\mathcal{K}$ generates data via a distinct
distribution $P_{k}(\boldsymbol{x},y)$.

###  III-B Federated Learning Setup

####  III-B1 Expected risk

Ideally, a federated learning problem fits a global model
$\boldsymbol{w}\in\mathbb{R}^{d}$ via expected risk minimization, i.e., by
minimizing the following (weighted average) expected risk:

$\displaystyle{E}(\boldsymbol{w})=\sum_{k\in\mathcal{K}}p_{k}{E}_{k}(\boldsymbol{w}),$
(1)

where $p_{k}\geq 0$ represents the weight for each agent $k$, satisfying
$\sum_{k\in\mathcal{K}}p_{k}=1$,333As an example, FedAvg in [3] selects
$p_{k}=n_{k}/n$ for all $k\in\mathcal{K}$. and ${E}_{k}(\boldsymbol{w})$ is
agent $k$’s local expected risk:

$\displaystyle{E}_{k}(\boldsymbol{w})\triangleq\int\ell(\boldsymbol{w},\boldsymbol{x},y)dP_{k}(\boldsymbol{x},y),~{}\forall
k\in\mathcal{K},$ (2)

where $\ell(\cdot,\cdot,\cdot)$ is a per-sample loss function dependent on the
model $\boldsymbol{w}$ applied to the input $\boldsymbol{x}_{i}$ and the label
$y_{i}$.

####  III-B2 Agent Modeling

The non-i.i.d. nature of data implies that agents have different
$P_{k}(\cdot)$ and hence may have heterogeneous prediction objectives
${E}_{k}(\boldsymbol{w})$ and different preferences over the prediction
outcome $\boldsymbol{w}$. Note that as the first work considering agent
strategic manipulation in federated learning due to heterogeneous prediction
objectives, we disregard the impact of resource consumption incurred in
federated learning, which was considered in [31, 32, 33, 34, 35, 37, 38, 39].

Note that, under traditional mechanisms that do not account for federated
learning (e.g., [40, 41, 42, 43, 44]), agents were assumed to know their exact
objectives before participating. However, this is not the case here since
their data distributions are unknown to themselves. Therefore, we assume that
agents make their decisions based on probably approximate properties (instead
of the deterministic ones in [40, 41, 42, 43, 44]) of the mechanisms to be
formally introduced later.

####  III-B3 Empirical risk

Each agent’s local expected risk ${E}_{k}$ is, however, not directly
accessible since $P_{k}(\cdot,\cdot)$ is unknown. To solve (1) approximately,
the induction principle of empirical risk minimization suggests to optimize an
objective that averages the loss function on the training sets
$\\{\mathcal{D}_{k}\\}_{k\in\mathcal{K}}$ instead [45]. Mathematically,
federated learning algorithms aim to solve the following (Empirical Risk
Minimization (ERM)) problem [3]:

$\displaystyle{\rm
FL}:\quad\min_{\boldsymbol{w}}~{}F(\boldsymbol{w})\triangleq\sum_{k\in\mathcal{K}}p_{k}F_{k}(\boldsymbol{w}),$
(3)

where $F_{k}(\boldsymbol{w})$ is the agent $k$’s local empirical risk (loss),
given by

$\displaystyle
F_{k}(\boldsymbol{w})=\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\ell(\boldsymbol{w},\boldsymbol{x}_{i},y_{i}),~{}\forall
k\in\mathcal{K}.$ (4)

One can anticipate that the optimal solution $\boldsymbol{w}^{o}$ to (3)
approximates the solution to (1).444Throughout this work, we use empirical
risk functions (e.g., $\\{F_{k}\\}$) in the objectives of federated learning
problems and agents’ payments, while we use expected risk functions (e.g.,
$\\{E_{k}\\}$) for risk bound analysis.  To quantify such a risk bound, we
first adopt the following standard assumptions on the per-sample loss function
$\ell(\cdot,\cdot,\cdot)$ throughout this paper (as in, e.g., [46, 8, 9]):

######  Assumption 1 ($L_{g}$-Smoothness).

The gradients of the per-sample loss function
$\nabla_{\boldsymbol{w}}\ell(\boldsymbol{w},\boldsymbol{x},y)$ are well-
defined and continuous such that there exists a constant $L_{g}$ satisfying

$\displaystyle\left\lVert\nabla_{\boldsymbol{w}}\ell(\boldsymbol{w}_{1},\boldsymbol{x},y)-\nabla_{\boldsymbol{w}}\ell(\boldsymbol{w}_{2},\boldsymbol{x},y)\right\rVert_{2}\leq
L_{g}\left\lVert\boldsymbol{w}_{1}-\boldsymbol{w}_{2}\right\rVert_{2},$ (5)

for any $\boldsymbol{w}_{1},\boldsymbol{w}_{2}\in\mathbb{R}^{d}$ and
$(\boldsymbol{x},{y})\in(\mathcal{X},\mathcal{Y})$.

######  Assumption 2 ($\mu$-Strong Convexity).

The per-sample loss function $\ell(\boldsymbol{w},\boldsymbol{x},y)$ is
$\mu$-strongly convex in $\boldsymbol{w}$ for all
$(\boldsymbol{x},{y})\in(\mathcal{X},\mathcal{Y})$, i.e., for any
$\boldsymbol{w}_{1},\boldsymbol{w}_{2}\in\mathbb{R}^{d},(\boldsymbol{x},{y})\in(\mathcal{X},\mathcal{Y})$,

$\displaystyle\ell(\boldsymbol{w}_{2},\boldsymbol{x},y)\geq~{}$
$\displaystyle\ell(\boldsymbol{w}_{1},\boldsymbol{x},y)+\nabla\ell(\boldsymbol{w}_{1},\boldsymbol{x},y)^{T}(\boldsymbol{w}_{2}-\boldsymbol{w}_{1})$
$\displaystyle+{\frac{\mu}{2}}\left\lVert\boldsymbol{w}_{2}-\boldsymbol{w}_{1}\right\rVert_{2}^{2}.$
(6)

Typical examples that satisfy these assumptions include ridge regression,
$l2$-norm regularized logistic regression, and softmax classifiers. We further
use $L_{\ell}$ denote the maximal norm of the gradient of the per-sample loss
at $\boldsymbol{w}^{o}$:

$\displaystyle
L_{\ell}\triangleq\max_{(\boldsymbol{x},y)\in(\mathcal{X},\mathcal{Y})}\left\lVert\nabla_{\boldsymbol{w}}\ell({\boldsymbol{w}^{o},\boldsymbol{x},y})\right\rVert_{2}.$
(7)

We can now characterize the risk bound in the following:

######  Proposition 1 (Proof in Appendix IX-A).

The following inequality is true with a probability of $1-\delta$:

$\displaystyle
E(\boldsymbol{w}^{o})-\min_{\boldsymbol{w}}E(\boldsymbol{w})\leq\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{4\mu},$
(8)

where $\boldsymbol{w}^{o}$ is the optimal solution to the federated learning
problem in (3), $d$ is the dimension of $\boldsymbol{w}$.

The proof of Proposition 1 involves bounding
$\nabla_{\boldsymbol{w}}E(\boldsymbol{w}^{o})$ by the Hoeffding’s inequality
and leveraging the strong convexity of $E(\cdot)$. In the case of the FedAvg
algorithm in [3], which selects $p_{k}={n_{k}}/{n}$ for all $k\in\mathcal{K}$,
the right hand side of (8) becomes $\frac{L_{\ell}^{2}d\log(2d/\delta)}{4\mu
n}$, which implies that the bound in this case converges to $0$ as
$n\rightarrow\infty$. The rate $\mathcal{O}(1/n)$ and is comparable to the
result in [46], while we do not assume boundedness on $\boldsymbol{w}$ as [46]
did.

###  III-C Goals

The federated learning problem in (3) can be solved efficiently in a
centralized manner if the server has the access to the global dataset
$\mathcal{D}$, which is, however, impractical in the federated learning
setting. Hence, as we mentioned in Section I, the focus of federated learning
algorithms is on distributed learning that achieves privacy preservation and
scalability. Moreover, here we also seek to ensure that agents will not opt
out or tamper with the system. This requires a joint design of a federated
learning algorithm and a proper (economic) mechanism. Specifically, a
mechanism aims to achieve the following economic properties:

  * •

(E1) Efficiency: The optimal solution (or its approximation, e.g., in
Proposition 1) to (1) is achieved.

  * •

(E2) Faithful Implementation555Faithful implementation is also known as
incentive compatibility or strategyproofness.: Every agent does not have the
incentive to deviate from the suggested federated learning algorithm.

  * •

(E3) Voluntary Participation: Every agent should not be worse off by
participating into the mechanism.

  * •

(E4) (Weak) Budget Balance (BB): The total payment from agents to the server
is non-negative, i.e., the server is not required to inject money into the
system.

As we have mentioned, we aim to achieve properties (E1)-(E4) in a probably
approximate (but not deterministic) manner, due to the unavailability of data
distributions $\\{P_{k}\\}_{k\in\mathcal{K}}$.

###  III-D Mechanism Design

In order to achieve the above properties (E1)-(E4), the server designs an
(economic) mechanism
$\mathcal{M}=(\mathcal{A},\mathcal{S}^{m},\boldsymbol{w}^{*},\mathcal{P})$,
described in the following:

  * •

Strategy space $\mathcal{A}=\prod_{k\in\mathcal{K}}\mathcal{A}_{k}$: each
agent can select a strategy $A_{k}\in\mathcal{A}_{k}$, representing the
messages (potential misreports) to be submitted to the server in each
iteration of a federated learning algorithm (such as gradient reporting in
FedAvg [3]);

  * •

(Suggested) protocol/algorithm
$\mathcal{S}^{m}=\\{s^{m}_{k}\\}_{k\in\mathcal{K}}$: the server would like
every agent to follow $\mathcal{S}^{m}$ by playing $A_{k}=s^{m}_{k}$ (e.g.,
agents truthfully reporting their gradients in each iteration in FedAvg [3]);

  * •

Learning updates $\boldsymbol{w}^{*}:\mathcal{A}\rightarrow\mathbb{R}^{d}$
describes how the algorithm updates the model $\boldsymbol{w}$ in each
iteration, which depends on agents’ strategies $\boldsymbol{A}$;

  * •

Payment rule
$\mathcal{P}=\\{\mathcal{P}_{k}\\}_{k\in\mathcal{K}}:\mathcal{A}\rightarrow\mathbb{R}^{K}$
describes the payment each agent $k\in\mathcal{K}$ needs to pay to the server,
depending on agents’ strategies $\boldsymbol{A}$.

For a given mechanism $\mathcal{M}$, each agent $k$ aims at minimizing its
empirical cost, defined next.

######  Definition 1 (Overall loss).

Each agent $k$ has a (quasi-linear) overall loss, defined as

$\displaystyle
J_{k}(A_{k},\boldsymbol{A}_{-k})=\mathcal{P}_{k}(\boldsymbol{A})+F_{k}(\boldsymbol{w}^{*}(\boldsymbol{A})),~{}\forall
k\in\mathcal{K}.$ (9)

In (9), we assume that each agent’s objective is quasi-linear in its monetary
loss, which is a standard assumption in economics [40].

There are two classical choices of the payment rules in the literature:

  * •

The (weighted) VCG payment for each agent $k\in\mathcal{K}$ [40]:

$\displaystyle\mathcal{P}_{k}^{\rm VCG}=\frac{1}{p_{k}}\left[\sum_{j\neq
k}p_{j}F_{j}(\boldsymbol{w}^{o})-\min_{\boldsymbol{w}}\sum_{j\neq
k}p_{j}F_{j}(\boldsymbol{w})\right].$ (10)

The VCG mechanism is known as a generic truthful mechanism for achieving a
socially-optimal solution (E1) and satisfies incentive compatibility and (E3)
and (E4). Intuitively, the first term in (10) serves to align each agent’s
objective to the server’s so that each agent also aims to minimize the global
loss; the second term ensures that each agent does not overpay so as to ensure
voluntary participation (E3). Detailed analysis of the VCG mechanism can be
found in [40]. Nevertheless, as we have mentioned, the VCG payment cannot be
directly applied here due to the communication/computation overhead. (3).
Moreover, it assumes that agents know their exact objectives, which is not
true here due to the unavailability of $P_{k}(\cdot)$. Hence, in this paper,
we will design distributed algorithms and corresponding mechanisms that lead
to an approximate VCG payment in (10), to address the above issues and attain
(E2) and (E3).

  * •

Another possible payment rule is the Shapley value, which achieves other
important properties in cooperative game theory [30, 47], but will not be
addressed in this paper.

##  IV Federated Learning Failure due to Strategic Manipulation

In this section, to illustrate the fact that agents to have incentives to opt
out of the federated learning framework and manipulate the algorithms, we will
demonstrate how non-i.i.d. and unbalanced data incentivizes strategic agents’
misbehaviors. Specifically, we will analyze the conditions under which a pure
federated learning algorithm (i.e. the one that does not leverage any economic
mechanism) for optimizing (3) does not satisfy (E2) and (E3).

###  IV-A Why May Agents Prefer Local Learning?

In this subsection, we first understand why agents may rather not to
participate into federated learning. In particular, for each agent
$k\in\mathcal{K}$, we compare the achievable performances of federated
learning (when all agents participate into and obey the algorithm, i.e., to
solve (3))) and a local learning algorithm to independently solve the
following local learning problem based on its local dataset $\mathcal{D}_{k}$:

$\displaystyle\boldsymbol{w}^{L}_{k}\triangleq\arg\min_{\boldsymbol{w}}{F}_{k}(\boldsymbol{w}),~{}\forall
k\in\mathcal{K}.$ (11)

In contrast, we use $\boldsymbol{w}^{o}$ to denote the optimal solution to the
federated learning problem in (3):

$\displaystyle\boldsymbol{w}^{o}\triangleq\arg\min_{\boldsymbol{w}}\sum_{k\in\mathcal{K}}p_{k}F_{k}(\boldsymbol{w}).$
(12)

We start with the following corollary to understand the performance of local
learning:

######  Corollary 1 (Proof in Appendix IX-A).

The following inequality is true with a probability of $1-\delta$:

$\displaystyle
E_{k}(\boldsymbol{w}_{k}^{L})-\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})\leq\frac{L_{\ell}^{2}d\log(2d/\delta)}{4\mu
n_{k}},\forall k\in\mathcal{K}.$ (13)

The result in Corollary 1 is interpreted as a special case of Proposition 1,
as shown in Appendix IX-A.

We next introduce the following result that compares local learning and
federated learning:

######  Proposition 2 (Proof in Appendix IX-B).

With a probability of $1-\delta$, federated learning in (3) leads to a risk
bound of: for every agent $k\in\mathcal{K}$,

$\displaystyle
E_{k}(\boldsymbol{w}^{o})-\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})\leq$
$\displaystyle\sum_{j\in\mathcal{K}}\frac{p_{j}^{2}}{n_{j}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{4\mu}$
$\displaystyle+2\left\lVert
P_{k}(\cdot)-\sum_{j\in\mathcal{K}}p_{j}P_{j}(\cdot)\right\rVert,$ (14)

where $\left\lVert f(\cdot)\right\rVert\triangleq\int_{t}|f(t)|dt$.

The proof of Proposition 2 uses the envelope theorem [48].

The first term in the right-hand side of (14) characterizes the estimation
error. The second term stands for the distance between its data distribution
and the weighted average data distribution
$\sum_{j\in\mathcal{K}}p_{j}P_{j}(\cdot)$, which characterizes how “typical”
agent $k$ is; a larger value of the second term implies that agent $k$ is less
typical. Intuitively, agent $k$ being more typical implies that training
samples of other agents are more useful in solving the agent $k$’s prediction
problem and hence resulting in a smaller bound in (14).

We note that the bounds in (13) and (14) are upper bounds that do not show
which of the actual (expected) risks is worse. However, since agents do not
know their exact data distributions but may estimate how typical they are
based on some type of side information, they may rely on comparing these upper
bounds in (13) and (14) to decide whether to participate into federated
learning. Specifically, suppose that $p_{k}=n_{k}/n$ for all $k\in\mathcal{K}$
so that $1/n=\sum_{j\in\mathcal{K}}p_{j}^{2}/n_{j}$. For an agent with many
samples so that $n_{k}/n$ is close to one, then the first term in (14) will be
close to the term in (13). Moreover, in such a case if the second term is
large enough (i.e. the data is less typical), then this risk bound will be
larger than that in (13). On the other hand, if an agent $k$ has only a few
samples so that $n_{k}/n$ is small and the second term in (14) is small enough
(i.e., its data is typical), then this risk bound in (14) will be smaller than
that in (13). Collectively, we make an important observation from Corollary 1
and Proposition 2:

######  Remark 1.

The classical federated learning framework in (3) disincentivizes non-typical
agents with sufficiently large datasets (such that $1/n_{k}$ is close to
$\sum_{j\in\mathcal{K}}p_{j}^{2}/n_{j}$).

###  IV-B Why May Agents Be Untruthful?

We next understand the incentive for agents to not follow a suggested
federated learning algorithm even if they choose to participate.

Consider a heuristic (manipulation) strategy for agent $k$ to amplify its
reports (e.g., its gradients in FedAvg [3]) by a constant $\gamma>1$, in each
iteration of a federated learning algorithm. When agents other than $k$ are
obedient, the resultant manipulated federated learning algorithm is equivalent
to solving the following problem:

$\displaystyle\boldsymbol{w}_{k,\gamma}=\arg\min_{\boldsymbol{w}}\left(\sum_{j\neq
k}p_{j}F_{j}(\boldsymbol{w})+\gamma p_{k}F_{k}(\boldsymbol{w})\right).$ (15)

We can derive a risk bound for such a manipulation:

######  Proposition 3 (Proof in Appendix IX-C).

Suppose that agent $k$ amplifies its report of its gradient by a constant
coefficient $\gamma$ and agents other than $k$ report their truthful gradients
for FedAvg. With a probability of $1-\delta$, the following inequality holds:

$\displaystyle
E_{k}(\boldsymbol{w}_{k,\gamma})-\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})$
(16) $\displaystyle\leq$
$\displaystyle\frac{1}{(1+(\gamma-1)p_{k})^{2}}\left(\sum_{j\neq
k}\frac{p_{j}^{2}}{n_{j}}+\frac{\gamma^{2}p_{k}^{2}}{n_{k}}\right)\frac{L_{\ell}^{2}d\log(2d/\delta)}{4\mu}$
$\displaystyle+2\left\lVert
P_{k}(\cdot)-\frac{1}{{1+(\gamma-1)p_{k}}}\left(\sum_{j\neq
k}p_{j}P_{j}(\cdot)+\gamma p_{k}P_{k}(\cdot)\right)\right\rVert.$

Proposition 3 is a direct application of Proposition 2. Note that, (16)
becomes exactly the same as in (13) as by letting $\gamma$ approach $\infty$,
whereas (16) becomes exactly the same as in (14) when $\gamma=1$. This
indicates that, as stated in Remark 1, non-typical agents with sufficiently
large datasets can benefit from choosing a relatively large $\gamma$.666It
also implies that a strategic non-typical agent with a sufficiently large
dataset may manipulate federated learning and lead to a system performance as
worse as that of local learning. Further, since local learning and federated
learning without manipulation can be regarded as the special cases of the
manipulated federated learning in (15), tampering with federated learning
renders more capability and incentives to manipulate the system outcomes,
compared to opting out of federated learning.

Figure 1: An illustrative example of Proposition 3. In (a) and (b), we set
$\text{mean}=0.1$ and $2$, respectively, fix $\delta=0.01$, and compare the
incurred local loss at different $\gamma$; in (c), we fix $\gamma=3$ and
$\text{mean}=0.1$ and compare the incurred local loss at different $\delta$.

We consider an illustrative example of Proposition 3 (and Remark 1), as
descried in the following. We consider a federate learning framework for two
agents with $n_{1}=50$ and $n_{2}=400$ data samples, respectively. For each
data sample $(x_{i},y_{i})$ in either dataset $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$, $x_{i}\in\mathbb{R}$ is randomly generated from a uniform
distribution over $[0,1]$. Labels $y_{i}$ satisfy
$y_{i}=-2x_{i}+1+\kappa_{i}$, where $\kappa_{i}$ follows normal distributions
$\mathcal{N}(\text{mean},2)$ and $\mathcal{N}(0,2)$, truncated over $[-3,3]$,
for each data sample $(x_{i},y_{i})$ generated in datasets $\mathcal{D}_{1}$
and $\mathcal{D}_{2}$, respectively. Therefore, a mean closer to $0$ implies
that both agents’ data distributions are closer. In Fig. 1, we study the
impacts of the amplifying coefficient $\gamma$ and $\delta$ on agent $1$’s
empirical loss and its analytical (probably approximate) upper bound derived
according to Proposition 3. We consider a scenario where two data
distributions are close (as $\text{mean}=0.1$) in Fig. 1(a). First, we observe
that the agent $1$’s optimal coefficients $\gamma$ to minimize its analytical
and empirical local risks are both slightly larger than $1$. On the other
hand, when two data distributions are very distant (as $\text{mean}=2$) as
shown in Fig. 1(b), agent $1$ prefers an infinitely large $\gamma$. Note that
each agent’s local loss as $\gamma\rightarrow\infty$ corresponds to its local
loss under local learning. By comparing the values of local losses at
$\gamma=1$ and $\gamma=\infty$, Fig. 1 also validates our result in Remark 1:
A non-typical agent prefers not to participate. Fig. 1(a)-(b) shows that
analytical and empirical loss functions tend to have close minimizers.
Finally, Fig. 1(c) demonstrates that $\delta$ only has a small impact on the
tightness of the analytical bound since $\delta$ appears in a logarithmic
function; $\delta=0.01$ is already enough to ensure a reasonably tight
analytical upper bound.

###  IV-C When is Federated Learning Socially Efficient?

Even from the system-level perspective, with respect to minimizing the global
expected risk in (1), federated learning may not be always more beneficial
than local learning in (11), as we will analyze next.

With a probability of at least $1-\delta$, agents performing their respective
local learning algorithms leads to an expected risk bound of

$\displaystyle\sum_{k\in\mathcal{K}}p_{k}E_{k}(\boldsymbol{w}_{k}^{L})-\sum_{k\in\mathcal{K}}p_{k}\left(\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k\in\mathcal{K}}\frac{p_{k}}{n_{k}}\frac{L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu}.$
(17)

Similarly, with a probability of at least $1-\delta$, federated learning in
(3) leads to an expected risk bound of

$\displaystyle
E(\boldsymbol{w}^{o})-\sum_{k\in\mathcal{K}}p_{k}\left(\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})\right)\leq$
$\displaystyle\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu}$
$\displaystyle+\sum_{k\in\mathcal{K}}2p_{k}\left\lVert
P_{k}-\sum_{j\in\mathcal{K}}p_{j}P_{j}\right\rVert.$ (18)

Consider a system with $n_{k}=n_{j}$ and $p_{k}=p_{j}$ for all $k$ and $j$.
Subtracting the risk bound of local learning from that of federated learning
yields

$\displaystyle\frac{(K-1)L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu
n}-\frac{2}{K}\sum_{k\in\mathcal{K}}\left\lVert
P_{k}-\sum_{j\in\mathcal{S}}\frac{P_{j}}{K}\right\rVert.$ (19)

We observe that the first term in (19) always increases in $K$ while the
second term needs not to do so, which implies that the federated learning is
more likely to have a smaller risk bound when there are many agents in the
system.

To generalize the above results, we can further cluster agents into several
disjoint clusters $\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{L}$, and
let agents in each cluster perform intra-cluster learning, i.e., they solve

$\displaystyle\boldsymbol{w}^{\mathcal{C}_{l}}\triangleq\arg\min_{\boldsymbol{w}}\sum_{k\in\mathcal{C}_{l}}p_{k}F_{k}(\boldsymbol{w}).$
(20)

Let $\hat{\mathcal{C}}(k)$ denote the cluster that agent $k$ belongs to, i.e.,
if $k\in\mathcal{C}_{l}$, then $\hat{\mathcal{C}}(k)=\mathcal{C}_{l}$. The
risk bound of such clustering and intra-cluster learning is given by

$\displaystyle\sum_{k\in\mathcal{K}}p_{k}E_{k}(\boldsymbol{w}^{\hat{\mathcal{S}}(k)})-\sum_{k\in\mathcal{K}}p_{k}\left(\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})\right)$
$\displaystyle\leq$
$\displaystyle~{}\sum_{k\in\mathcal{K}}\frac{p_{j,\hat{\mathcal{C}}(k)}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu}+\sum_{k\in\mathcal{K}}2p_{k}\left\lVert
P_{k}-\bar{P}_{\hat{\mathcal{C}}(k)}\right\rVert$ $\displaystyle\triangleq$
$\displaystyle~{}{\rm RB}_{\mathcal{C}},$ (21)

where $\mathcal{C}$ denotes the set of all clusters, i.e.,
$\mathcal{C}=\\{\mathcal{C}_{1},\mathcal{C}_{2},...,\mathcal{C}_{L}\\}$,
$p_{k,\mathcal{A}}=p_{k}/\sum_{j\in\mathcal{A}}p_{j}$, and
$\bar{P}_{\mathcal{A}}(\cdot,\cdot)=\sum_{j\in\mathcal{A}}p_{j,\mathcal{A}}P_{j}(\cdot,\cdot)$,
for all clusters $\mathcal{A}$ in $\mathcal{C}$.

It is possible to design a clustering algorithm, based on agents’ non-i.i.d.
data distributions, to minimize the risk bound, which is beyond the scope of
this work. Instead, we focus on the scenario in which federated learning is
more beneficial than any clustering $\mathcal{C}$ for the system, by adopting
the following assumption:

######  Assumption 3.

The federated learning leads to a tighter risk bound than any possible intra-
cluster federated learning, i.e.,

$\displaystyle{\rm RB}_{\\{\mathcal{K}\\}}\leq{\rm
RB}_{\mathcal{C}},~{}\forall\mathcal{C}.$ (22)

Assumption 3 can be true in a massively distributed federated learning
framework [3], in which the average number of samples per agents $n/K$ is much
smaller than $K$. Even under Assumption 3, agents may still benefit from
opting out of and tampering with a federated learning algorithm, which
motivates the faithful federated learning mechanisms to be discussed in the
following sections.

##  V Faithful Federated Learning

In this section, we apply mechanism design for FedAvg in [4] to achieve a
scalable federated learning algorithm (with the associated mechanism) that
satisfies (E1)-(E3) approximately and (E4) exactly. Similar techniques could
also be applied to other federated learning algorithms.

1

2The server initializes a model $\boldsymbol{w}[0]$ and step sizes $\eta_{1}$
and $\eta_{2}$ for Phase I and Phase II;

3

// Phase I: Federated learning phase

4

5for  _iterations $t\in\\{0,1,...,T_{1}\\}$_ do

6 The server broadcasts the current model $\boldsymbol{w}[t]$ to all agents;

7

8 Each agent $k$ computes and reports its gradient to the server
$\nabla{F}_{k}(\boldsymbol{w}[t])$.;

9

10 The server updates the model
$\displaystyle\boldsymbol{w}[t+1]=\boldsymbol{w}[t]-\eta_{1}\sum_{k\in\mathcal{K}}p_{k}\nabla{F}_{k}(\boldsymbol{w}[t]).$
(23)

11 end for

12Return the approximately optimal model:
$\boldsymbol{w}^{*}\triangleq\boldsymbol{w}[{T}_{1}]$;

// Phase II: Payment computation phase

13 for  _agents $k\in\mathcal{K}$_ do

14 The server initializes the model
$\boldsymbol{w}_{-k}[0]=\boldsymbol{w}^{*}$;

15

16 while  _iterations $t\in\\{0,1,...,T_{2}\\}$ or
$\frac{1}{2\mu}\left\lVert\sum_{j\neq k}p_{j}\nabla
F_{j}(\boldsymbol{w}_{-k}[t])\right\rVert_{2}^{2}>p_{k}\epsilon$_ do

17 Set $t\rightarrow t+1$;

18 The server broadcasts the current model $\boldsymbol{w}_{-k}[t]$ to all
agents excluding $k$;

19

20 Agents $j\neq k$ compute and report their gradients to the server
$\nabla{F}_{j}(\boldsymbol{w}_{-k}[t])$;

21

22 The server updates the model and agent $k$’s payment:
$\displaystyle\boldsymbol{w}_{-k}[t+1]$
$\displaystyle=\boldsymbol{w}_{-k}[t]-\eta_{2}\sum_{j\neq
k}p_{j}\nabla{F}_{j}(\boldsymbol{w}_{-k}[t]),$ (24a)
$\displaystyle\mathcal{P}_{k}[t+1]$
$\displaystyle=\mathcal{P}_{k}[t]+(\boldsymbol{w}_{-k}[t+1]-\boldsymbol{w}_{-k}[t])^{T}\cdot$
$\displaystyle~{}~{}~{}~{}~{}\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\nabla{F}_{j}(\boldsymbol{w}_{-k}[t]).$ (24b)

23 end while

24 Return the payment for agent $k$:
$\mathcal{P}_{k}^{*}\triangleq\mathcal{P}_{k}[T_{2}]$;

25

26 end for

Algorithm 1 Faithful Federated Learning

###  V-A Algorithm and Mechanism Description

We present the Faithful Federated Learning (FFL) algorithm in Algorithm 1,
consisting of two phases: a federated learning phase (lines 1-1) and a payment
computation phase (lines 1-1). In the first phase (consisting of $T_{1}$
iterations), we present a gradient-based federated learning algorithm to
(approximately) attain the globally optimal solution $\boldsymbol{w}^{*}$ to
(3), similar to FedAvg in [3].777Throughout this paper, we use superscript $o$
to denote the exact optimal solution, and $*$ to denote the solution output by
algorithms. The second phase consists of $K$ outer iterations, with each
computing each agent’s payment without the need of directly revealing agents’
private local empirical risk functions. We note that
$\frac{1}{2\mu}\left\lVert\sum_{j\neq k}p_{j}\nabla
F_{j}(\boldsymbol{w}_{-k}[t])\right\rVert_{2}^{2}>p_{k}\epsilon$ in line 1 is
to ensure the accurate computation of each agents payment. As we will show
later, accurately computed payments incentivize strategic agents to faithfully
follow the intended federated learning algorithm in the first phase.

Based on Algorithm 1, we introduce the FFL mechanism. The reporting of each
agent’s true gradient (lines 1 and 2) in each iteration corresponds to the
intended algorithm (that the server would like agents to follow), whereas each
agent $k$ report $\nabla\tilde{F}_{k}(\boldsymbol{w}[t])\in\mathbb{R}^{d}$ is
a potential misreport of its gradient. Formally, we have:

######  Definition 2 (The FFL Mechanism).

The FFL mechanism
$\mathcal{M}=(\mathcal{A},\mathcal{S}^{m},\boldsymbol{w}^{*},\mathcal{P})$ is
described as: for every agent $k\in\mathcal{K},$

$\displaystyle s^{m}_{k}=\\{\nabla
F_{k}(\boldsymbol{w}[t])\\}_{t\in\mathcal{T}_{-k}}\quad{\rm and}\quad
A_{k}=\left\\{\nabla\tilde{F}_{k}(\boldsymbol{w}[t])\right\\}_{t\in\mathcal{T}_{-k}},$
(25)

where
$\mathcal{T}_{-k}=\bigcup_{j\in\\{0\\}\cup\mathcal{K}\backslash\\{k\\}}\\{1\leq
t\leq T_{2}\\}$. The output global model $\boldsymbol{w}^{*}$ and each agent
$k$’s payment $\mathcal{P}_{k}$ are determined in (23) and (24), respectively.

In the following, we explain the intuition behind Algorithm 1 and the FFL
mechanism. We first define

$\displaystyle\boldsymbol{w}_{-k}^{o}\triangleq\arg\min_{\boldsymbol{w}}\sum_{j\neq
k}p_{j}F_{j}(\boldsymbol{w}).$ (26)

Following Algorithm 1, the final payment for each agent $k$ can be
approximately expressed by

$\displaystyle\mathcal{P}_{k}^{*}$
$\displaystyle=\sum_{t=1}^{T_{2}}\sum_{j\neq k}\frac{p_{j}}{p_{k}}\nabla
F_{j}(\boldsymbol{w}[t])^{T}(\boldsymbol{w}[t+1]-\boldsymbol{w}[t])$
$\displaystyle\approx\sum_{j\neq
k}\int_{\boldsymbol{w}_{-k}[0]}^{\boldsymbol{w}_{-k}[T_{2}]}\frac{p_{j}}{p_{k}}\nabla
F_{j}(\boldsymbol{w})^{T}\boldsymbol{d}\boldsymbol{w}$
$\displaystyle\approx\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\left[F_{j}(\boldsymbol{w}^{o})-F_{j}(\boldsymbol{w}^{o}_{-k})\right],~{}\forall
k\in\mathcal{K}.$ (27)

Therefore, the payment rule defined in Algorithm 1 is a VCG-like payment rule
(i.e., it approximates (10)). As we have discussed, it can align each agent’s
objective to the server’s objective, and hence potentially satisfies
properties (E1)-(E4).

###  V-B Federated Learning Phase

With Assumptions 1-3, the gradient-based learning algorithm in the federated
learning phase of Algorithm 1 leads to the following standard linear
convergence result [49]:

######  Lemma 1.

In the federated learning phase of Algorithm 1, if we choose a constant step
size such that $\eta_{1}=1/L_{g}$, the gradient descent has a linear
convergence rate of

$\displaystyle
F(\boldsymbol{w}^{*})-F(\boldsymbol{w}^{o})\leq\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o})).$
(28)

Lemma 1 along with Proposition 1 implies that we can achieve (E1) in a
probably approximate manner, as shown in the following:

######  Proposition 4 (Proof in Appendix).

In the federated learning phase of Algorithm 1, if we choose a constant step
size such that $\eta_{1}\leq 1/L_{g}$, the following risk bound is true with a
probability of $1-\delta$:

$\displaystyle E(\boldsymbol{w}^{*})-$
$\displaystyle\min_{\boldsymbol{w}}E(\boldsymbol{w})\leq\Phi(\delta),$ (29)

for any $\delta\in(0,1)$, where

$\displaystyle\Phi(\delta)\triangleq$
$\displaystyle\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{2\mu}$
$\displaystyle+\frac{2L_{g}}{\mu}\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o})).$
(30)

###  V-C Payment Computation Phase

In this subsection, we analyze the payment computation phase. We start with
defining an optimal solution set $\mathcal{W}^{*}$ for all possible
$\\{p_{k}\\}$:

$\displaystyle\mathcal{W}^{*}\triangleq\left\\{\arg\min_{\boldsymbol{w}}\sum_{k\in\mathcal{K}}p_{k}F_{k}(\boldsymbol{w}):\forall
p_{k}\geq 0~{}{\rm and}~{}\sum_{k\in\mathcal{K}}p_{k}=1\right\\},$ (31)

and introduce the following gradient bound:

######  Definition 3 (Gradient Bound).

The gradient bound $L_{f}$ is defined as, for each agent $k\in\mathcal{K}$,

$\displaystyle\left\lVert\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w})\right\rVert_{2}\leq
L_{f},$ (32)

for all
$\boldsymbol{w}\in\\{\boldsymbol{w}[t]\\}_{t\in\\{0,1,...,T_{1}\\}}\cup\\{\boldsymbol{w}_{-k}[t]\\}_{k\in\mathcal{K},t\in\\{0,1,...,T_{2}\\}}\cup\mathcal{W}^{*}$,
where $\\{\boldsymbol{w}[t]\\}_{t\in\\{0,1,...,T_{1}\\}}$ and
$\\{\boldsymbol{w}_{-k}[t]\\}_{k\in\mathcal{K},t\in\\{0,1,...,T_{2}\\}}$ are
described in Algorithm 1.

Note that such a gradient bound always exists as the set
$\\{\boldsymbol{w}[t]\\}_{t\in\\{0,1,...,T_{1}\\}}\cup\\{\boldsymbol{w}_{-k}[t]\\}_{k\in\mathcal{K},t\in\\{0,1,...,T_{2}\\}}\cup\mathcal{W}^{*}$
is compact888 By the maximum theorem and the strong convexity of
$F_{k}(\boldsymbol{w})$,
$\arg\min_{\boldsymbol{w}}\sum_{k\in\mathcal{K}}p_{k}F_{k}(\boldsymbol{w})$ is
continuous in $\\{p_{k}\\}_{\in\mathcal{K}}$. Therefore, the compactness of
the set of all $\\{p_{k}\\}_{\in\mathcal{K}}$ satisfying $p_{k}\geq 0~{}{\rm
and}~{}\sum_{k\in\mathcal{K}}p_{k}=1$ indicates the compactness of
$\mathcal{W}^{*}$.  so that there always exists a large enough upper bound for
all values of
$\left\lVert\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w})\right\rVert_{2}$
taken over the set.

We now present a formal bound of the absolute difference of the payment
$\mathcal{P}_{k}^{*}$ and the exact VCG payment in the following:

######  Proposition 5 (Proof in Appendix IX-E).

The payment accuracy loss (the absolute difference between
$\mathcal{P}_{k}^{*}$ and the VCG payment $\mathcal{P}_{k}^{\rm VCG}$ in (10))
is bounded by:

$\displaystyle~{}\left|\mathcal{P}_{k}^{*}-\mathcal{P}_{k}^{\rm
VCG}\right|\leq\frac{1-p_{k}}{p_{k}}L_{g}L_{f}^{2}(T_{2}+1)\eta_{2}^{2},~{}\forall
k\in\mathcal{K}.$ (33)

Intuitively, as Proposition 5 indicates, $\mathcal{P}_{k}^{*}$ converges to
the VCG payment in (10) as the step sizes converge to zeros, i.e.,
$\eta_{2}\rightarrow 0$.

In the following, we study the iteration complexity of the FFL mechanism,
starting with the following lemma:

######  Lemma 2 (Proof in Appendix IX-F).

With equal weights ($p_{k}=1/K$ for all $k\in\mathcal{K}$), the (Euclidean)
distance between $\boldsymbol{w}_{-k}^{o}$ and $\boldsymbol{w}^{o}$ satisfies

$\displaystyle\left\lVert\boldsymbol{w}_{-k}^{o}-\boldsymbol{w}^{o}\right\rVert_{2}\leq\frac{L_{f}}{\mu
K},~{}\forall k\in\mathcal{K}.$ (34)

Lemma 2 implies that the distance of $\boldsymbol{w}_{-k}^{o}$ to
$\boldsymbol{w}^{o}$ is inversely proportional to the total number of agents
$K$. In the following throughout this paper, we choose equal weights
$p_{k}=1/K$ for all $k\in\mathcal{K}$. Let $\lceil\cdot\rceil$ be the ceiling
operator such that $\lceil x\rceil$ is the smallest non-negative integer that
is no less than $x$. Define
$G\triangleq\left\lVert\boldsymbol{w}[0]-\boldsymbol{w}^{o}\right\rVert_{2}$.
Based on Lemma 2, we now have one of the main results of this work:

######  Theorem 1.

Set $\eta_{1}={1}/{L_{g}}$, $\eta_{2}={1}/(KL_{g})$, and
$T_{1}\geq\frac{2\ln(KG/{\Delta})}{\ln((1-\mu/L_{g})^{-1})}$. Set the number
of iterations
$T_{2}=\left\lceil\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right)\right\rceil$,
for any $K>0$ and $\epsilon>0$ such that
$\left[\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right),\frac{L_{g}\epsilon
K}{2L_{f}^{2}}\right]$ is not empty, we have a bounded payment accuracy loss,
satisfying

$\displaystyle|\mathcal{P}_{k}[T_{2}]-\mathcal{P}_{k}^{\rm
VCG}|\leq\epsilon,~{}\forall k\in\mathcal{K}.$ (35)

and a constant time complexity of

$\displaystyle
KT_{2}\leq\left(1+\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{2\mu^{2}e\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right)=\mathcal{O}(1).$
(36)

Note that, for every $\epsilon$, there always exists a large enough $K$ such
that the interval

$\displaystyle\left[\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right),\frac{L_{g}\epsilon
K}{2L_{f}^{2}}\right]$ (37)

is not empty.

Theorem 1 implies that, by ensuring the number of iterations in Phase I to
satisfy $T_{1}=\mathcal{O}(\log(K))$, the time complexity of the payment
computation phase in Algorithm 1 is in fact $KT_{2}=\mathcal{O}(1)$ with
respect to $K$. In particular, a sufficiently large $K$ such that
$K\geq(L_{f}+\Delta\mu)^{2}L_{g}/(2\mu^{2}\epsilon)$ ensures that
$|\mathcal{P}_{k}[0]-\mathcal{P}_{k}^{\rm VCG}|\leq\epsilon$ for all
$k\in\mathcal{K}$. In other words, when $K$ is sufficiently large, we can set
$T_{2}=0$, in which case Phase II of Algorithm 1 will end without any
iterations. Intuitively, the gradient-based nature benefits significantly from
the Euclidean distance (between the $\boldsymbol{w}_{-k}^{o}$ and
$\boldsymbol{w}^{o}$) inversely proportional to $K$. On the other hand, since
the per-iteration communication complexity is $\mathcal{O}(K)$, the overall
communication complexity is also $\mathcal{O}(K)$.

###  V-D Properties

In this subsection, we will show that the FFL mechanism satisfies (E2) and
(E3) approximately and (E4) exactly. We first introduce the following
definition of (probably approximate) faithfulness as to achieve (E2)
approximately:

######  Definition 4 (Faithfulness).

A mechanism $\mathcal{M}$ is $(\tilde{\epsilon},\tilde{\delta})$-faithful if
the following bound holds for all agents $k\in\mathcal{K}$,

$\displaystyle{\rm
Pr}\left\\{\mathbb{E}[J_{k}(s_{k}^{m},\boldsymbol{s}_{-k}^{m})]-\min_{A_{k}\in\mathcal{A}_{k}}\mathbb{E}[J_{k}(A_{k},\boldsymbol{s}_{-k}^{m})]\leq\tilde{\epsilon}\right\\}\geq
1-\tilde{\delta},$ (38)

where $J_{k}(\cdot)$ is the overall loss introduced in Definition 1.

That is, the $(\tilde{\epsilon},\tilde{\delta})$-faithfulness suggests that,
when all other agents are following the suggested protocol, the incentive for
agent $k$ to deviate from doing so is small with a high probability of
$1-\tilde{\delta}$. The bound $\tilde{\epsilon}$ may depend on
$\tilde{\delta}$ and the number of agents’ data samples
$\\{n_{k}\\}_{k\in\mathcal{K}}$ and is anticipated to vanish as
$n\rightarrow\infty$. It follows that:

######  Proposition 6 (Faithful Implementation).

If we choose $\eta_{1}={1/L_{g}}$, $\eta_{2}=\frac{1}{KL_{g}}$,
$T_{1}\geq\frac{2\ln(KG/\Delta)}{\ln((1-\mu/L_{g})^{-1})}$, and
$T_{2}=\left\lceil\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right)\right\rceil$
for all $\epsilon>0$ such that
$\left[\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right),\frac{L_{g}\epsilon
K}{2L_{f}^{2}}\right]$ is not empty, then the FFL mechanism is
$\left(\tilde{\epsilon},\tilde{\delta}\right)$-faithful, where
$\tilde{\epsilon}$ satisfies

$\displaystyle\tilde{\epsilon}=2{\epsilon}$
$\displaystyle+K\Phi(\tilde{\delta}),~{}~{}\forall\tilde{\delta}\in(0,1),$
(39)

where $\Phi(\delta)$ is defined in (30).

We note that $K\Phi(\tilde{\delta})\leq
C_{1}\log(1/\delta)\sum_{k\in\mathcal{K}}\frac{{1}}{n_{k}}+C_{2}$ for some
constants $C_{1}$ and $C_{2}$ (independent of $K$) when
$T_{1}=\mathcal{O}(\log(K))$. We present the proof of Proposition 6 in
Appendix IX-H. The proof of Proposition 6 is an application of Theorem 1 and
Proposition 1. An interesting observation is that, different from (16), data
distributions $\\{P_{k}(\cdot)\\}$ do not appear in (39). Thus, we remark
that:

######  Remark 2.

The faithful implementation property achieved by the FFL mechanism is robust
against non-i.i.d. data. This differs substantially from the classical
federated learning settings, in which non-typical agents may have incentives
to manipulate federated learning algorithms, as shown in Propositions 2 and 3.

To show the voluntary participation property, we consider the following
probabilistic inequalities. From (17), the following inequality holds with a
probability of $1-\delta$, for all $k\in\mathcal{K}$,

$\displaystyle
E_{k}(\boldsymbol{w}^{L}_{k})-\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})$
$\displaystyle\leq$ $\displaystyle\left(\sum_{j\neq
k}\frac{p_{j}^{2}}{n_{j}(1-p_{k})^{2}}+\frac{p_{k}}{n_{k}}\right)\frac{L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu}+\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\min_{\boldsymbol{w}}E_{j}(\boldsymbol{w})$
$\displaystyle-\min_{\boldsymbol{w}}\sum_{j\neq
k}\frac{p_{j}}{p_{k}}E_{j}(\boldsymbol{w})+2\sum_{j\neq k}p_{j}\left\lVert
P_{j}-\bar{P}_{\mathcal{K}\backslash\\{k\\}}\right\rVert\triangleq{\rm
RB}^{L}_{k,\delta}.$ (40)

Following (21), the following inequality holds with a probability of
$1-\delta$, we have that the difference between each agent $k$’s expected
overall loss from participation into the FFL mechanism and
$\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})$ satisfies

$\displaystyle E_{k}(\boldsymbol{w}^{o})+\mathbb{E}[\mathcal{P}_{k}^{\rm
VCG}]-\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})$ $\displaystyle\lessapprox$
$\displaystyle\sum_{j\in\mathcal{K}}\frac{p_{j}^{2}}{n_{j}p_{k}}\frac{L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu}+\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\min_{\boldsymbol{w}}E_{j}(\boldsymbol{w})$
$\displaystyle-\min_{\boldsymbol{w}}\sum_{j\neq
k}\frac{p_{j}}{p_{k}}E_{j}(\boldsymbol{w})+2\sum_{k\in\mathcal{K}}p_{k}\left\lVert
P_{k}-\bar{P}_{\mathcal{K}}\right\rVert\triangleq{\rm RB}^{FFL}_{k,\delta}.$
(41)

Based on the above probabilistic bounds and Assumption 3, we can derive the
following result:

######  Proposition 7 (Risk-Bound-Based Voluntary Participation).

If we choose $\eta_{1}={1/L_{g}}$, $\eta_{2}={1}/(KL_{g})$,
$T_{1}\geq\frac{2\ln(KG/\Delta)}{\ln((1-\mu/L_{g})^{-1})}$, and
$T_{2}=\left\lceil\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right)\right\rceil$
for all $\epsilon>0$ such that
$\left[\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right),\frac{L_{g}\epsilon
K}{2L_{f}^{2}}\right]$ is not empty, then the following inequality holds, for
all $k\in\mathcal{K}$,

$\displaystyle{\rm RB}^{FFL}_{k,\delta}\leq~{}$ $\displaystyle{\rm
RB}^{L}_{k,\delta}+\epsilon$
$\displaystyle+\frac{2KL_{g}}{\mu}\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o})).$
(42)

We present the proof of Proposition 7 in Appendix IX-I. Intuitively, although
agents do not know their exact data distributions, Proposition 7 suggests that
the risk bound of the FFL mechanism is smaller than that of local learning
plus $\epsilon$. This incentivizes agents to voluntarily participate into the
FFL mechanism, achieving (E3).

Finally, we show that the FFL mechanism satisfies (E4) in the following:

######  Proposition 8 (Budget Balance, Proof in Appendix IX-J).

The FFL mechanism $\mathcal{M}$ achieves budget balance (E4):

$\displaystyle\sum_{k\in\mathcal{K}}\mathcal{P}_{k}^{*}\geq 0.$ (43)

To summarize, our FFL algorithm and the FFL mechanism achieve all the desired
economic properties of (E1)-(E4). In addition, our FFL mechanism is also
scalable as it only incurs an iteration complexity of $\mathcal{O}(\log(K))$
preserves agent privacy as it does not directly require agents to reveal their
empirical risks or training data.

##  VI Differentially Private Faithful Federated Learning

In this section, we aim to design a faithful federated learning mechanism
achieving a more rigorous guarantee of privacy. We design a scalable VCG
payment, and leverage differential privacy and secure multi-party computation
to design a differentially private faithful federated learning algorithm and
the corresponding mechanism.

###  VI-A Scalable VCG Payment

The VCG payment in (10) for a system with $K$ agents requires one to solve
$K+1$ optimization problems, which incurs considerable communications and
computation overheads for a large-scale system. We showed in Section V that
the time complexity of solving these problems using a gradient-based algorithm
is $\mathcal{O}(\log(K))$ with respect to $K$. However, to achieve
differential privacy, as we will show next, one relies on gradient
perturbation under which the number of iterations for each problem no longer
decreases in $K$. To this end, we introduce a scalable approximation of the
VCG payment in (10) by reducing the number of problems to be solved.

We formally introduce the Scalable VCG payment in the following:

######  Definition 5 (Scalable VCG Payment).

We randomly divide the set of agents $\mathcal{K}$ into
$\mathcal{L}=\\{1,2,...,L\\}$ disjoint clusters. Each cluster is indexed by
$l$ and denoted by $\mathcal{C}_{l}$. We properly divide $\mathcal{K}$ in such
a way that each cluster $\mathcal{C}_{l}$ has either $\lceil\frac{K}{L}\rceil$
or $\lfloor\frac{K}{L}\rfloor$ agents.999As an example, a set of $K=18$ agents
can be divided into the following $4$ clusters:
$\mathcal{C}_{1}=\\{1,4,5,14\\},\mathcal{C}_{2}=\\{2,3,7,10,15\\},\mathcal{C}_{3}=\\{11,13,16,17\\},$
and $\mathcal{C}_{4}=\\{6,8,9,12,18\\}.$

The scalable VCG payment for each agent $k$ is

$\displaystyle\mathcal{P}^{\rm S}_{k}=\frac{1}{p_{k}}\sum_{j\neq
k}p_{j}\left(F_{j}(\boldsymbol{w}^{o})-F_{j}(\boldsymbol{w}^{o}_{l})\right),~{}\forall
k\in\mathcal{C}_{l},~{}l\in\mathcal{L},$ (44)

where

$\displaystyle\boldsymbol{w}_{l}^{o}=\arg\min_{\boldsymbol{w}}\sum_{k\in\mathcal{K}/\mathcal{C}_{l}}p_{k}F_{k}(\boldsymbol{w}),~{}\forall
l\in\mathcal{L}.$ (45)

Hence, we approximate $\boldsymbol{w}_{-k}^{o}$ for all $k\in\mathcal{C}_{l}$
by $\boldsymbol{w}^{o}_{l}$. In this case, instead of solving $K$ optimization
problems, we only need to solve $L$ optimization problems. In the following
theorem, we introduce a proper way to select $L$:

######  Theorem 2 (Proof in Appendix IX-K).

If we select

$\displaystyle
L\geq\min\left\\{K,\sqrt{\frac{L_{g}(K-1)}{2\epsilon}}\frac{L_{f}}{\mu}\right\\}=\mathcal{O}\left(\sqrt{\frac{K}{\epsilon}}\right),$
(46)

then the Scalable VCG Payment in Definition 5 leads to an approximation error
of

$\displaystyle\left|\mathcal{P}_{k}^{\rm S}-\mathcal{P}_{k}^{\rm
VCG}\right|\leq\epsilon,~{}\forall k\in\mathcal{K},$ (47)

where $\mathcal{P}_{k}^{\rm VCG}$ is the VCG payment for agent $k$ in (10).

The proof of Theorem 2 uses a similar technique to that of Lemma 2, as
$\left\lVert\boldsymbol{w}^{o}_{-k}-\boldsymbol{w}^{o}_{l}\right\rVert_{2}$ is
inversely proportional to the number of agents within each cluster
$\mathcal{C}_{l}$.

Theorem 2 indicates that, to maintain a bounded approximation error, the
number of optimization problems to be solved grows at a square root rate,
compared to the classical VCG mechanism with a linear rate. Therefore, the
Scalable VCG payment in Definition 5 allows us to design a more scalable
mechanism when we cannot rely on a gradient-based algorithm.

###  VI-B Differentially Private FFL Algorithm and Mechanism

1 The server initializes $\boldsymbol{w}[0]$ and step sizes
$\eta_{1},\eta_{2}$;

2

// Phase I: Federated learning phase

3

4for  _iterations $t\in\\{0,1,...,T_{1}\\}$_ do

5 The server broadcasts $\boldsymbol{w}[t]$ to all agents;

6

7 Each agent $k$ computes and reports its gradient to the server
$\nabla{F}_{k}(\boldsymbol{w}[t]))$;

8

9 The server securely aggregates agents’ gradients, adds noise, and updates
the model according to:
$\displaystyle\boldsymbol{w}[t+1]=\boldsymbol{w}[t]-\eta_{1}\left(\sum_{k\in\mathcal{K}}p_{k}\nabla{F}_{k}(\boldsymbol{w}[t])+\boldsymbol{n}\right),$
(48) where $\boldsymbol{n}$ is a random vector sampled from
$\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})$ and $\sigma^{2}$ is
given in (53);

10

11 end for

12Return $\boldsymbol{w}^{*}=\boldsymbol{w}[{T}_{1}]$;

13

14for  _clusters $l\in\mathcal{L}$_ do

// Phase II: Payment computation phase

15

16 The server initializes the model
$\boldsymbol{w}_{l}[0]=\boldsymbol{w}^{*}$;

17

18 for  _iterations $t\in\\{0,1,...,T_{2}\\}$_ do

19

20 The server broadcasts $\boldsymbol{w}_{l}[t]$ to all agents not in
$\mathcal{C}_{l}$;

21

22 Each agent $k\notin\mathcal{C}_{l}$ computes and reports its gradient to
the server $\nabla{F}_{k}(\boldsymbol{w}_{l}[t])$;

23

24 The server securely aggregates agents’ gradients and adds noise to update
the model:  $\displaystyle\boldsymbol{w}_{l}[t+1]$
$\displaystyle=\boldsymbol{w}_{l}[t]-\eta_{2}\left(\sum_{j\in\mathcal{C}_{l}}p_{j}\nabla{F}_{j}(\boldsymbol{w}_{l}[t])+\boldsymbol{n}\right),$
(49) where $\boldsymbol{n}$ is a random vector sampled from
$\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})$ and $\sigma^{2}$ is
given in (53);

25

26 end for

27

28 Each agent $k\in\mathcal{K}$ reports the value
$F_{k}(\boldsymbol{w}^{*})-F_{k}(\boldsymbol{w}_{l}[T_{2}])$ and the server
computes  $\displaystyle\mathcal{P}_{k}^{*}=\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\left({F}_{j}(\boldsymbol{w}^{*})-{F}_{j}(\boldsymbol{w}_{l}[T_{2}])\right)+n_{P,k},$
(50) for all $k\in\mathcal{C}_{l}$, where $n_{P,k}$ is sampled from
$\mathcal{N}(0,\sigma_{P}^{2})$ and $\sigma_{P}^{2}$ is given in (53);

29

30 Return the payment $\mathcal{P}_{k}^{*}$ for agent $k\in\mathcal{C}_{l}$;

31

32 end for

Algorithm 2 Differentially Private Faithful Federated Learning (DP-FFL)

Motivated by a recent differentially private federated learning algorithm in
[8], we next introduce the techniques to ensure differential privacy by
combining secure multi-party computation (to aggregate agents’ local
gradients) and gradient perturbation. Jayaraman et al. in [8] showed that this
allows the server to add only a single noise copy, and can outperform the
algorithms requiring local gradient perturbation before aggregation.

Before we describe and analyze the algorithm, we first formally introduce the
following concepts:

####  VI-B1 Differential Privacy

We aim to guarantee differential privacy, which is a crypographically-
motivated notion of privacy [50]. We define $\alpha\geq 0$ as privacy risk.
Formally, we have:101010Note that $(\alpha,\beta)$-differential privacy is
also known as $(\epsilon,\delta)$-differential privacy, as in [8].

######  Definition 6 ($(\alpha,\beta)$-differential privacy (DP)).

Let $\alpha$ be a positive real number and ${\mathcal{Z}}$ be a randomized
algorithm. The algorithm ${\mathcal{Z}}$ is said to provide
$(\alpha,\beta)$-DP if, for any two datasets $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$ that differ on a single element, ${\mathcal{Z}}$ satisfies

$\displaystyle\displaystyle\Pr[{\mathcal{Z}}(\mathcal{D}_{1})=y]\leq\exp\left(\alpha\right)\cdot\Pr[{\mathcal{Z}}(\mathcal{D}_{2})=y]+\beta,~{}\forall
y.$ (51)

The above definition is reduced to the $\alpha$-DP when $\beta=0$, as in [51].
As we will show, one can achieve $(\alpha,\beta)$-DP by adding noise sampled
from Gaussian distributions to gradients.

####  VI-B2 Secure Multi-Party Computation

For preserving the privacy of agents’ inputs without revealing them to others,
the server aims to securely aggregate their gradients in each
iteration.111111Note that MPC protocols are only able to protect the training
data during the learning process, whereas the resulting model of a federated
learning algorithm still relies on the differential privacy techniques (by
adding noise in our proposed DP-FFL algorithm) against inferring private data
of each agent. To this end, we consider secure multi-party computation (MPC)
protocols that enable one to jointly aggregate their private inputs. Examples
of these are protocols that employ cryptographic techniques (e.g., homomorphic
encryption and secret sharing). In this work, we do not focus on improving or
evaluating the MPC protocols, since the methods we propose can be implemented
using standard MPC techniques.121212A concrete example of the standard MPC
technique in federated learning frameworks can be found in [8, 9].

####  VI-B3 Algorithm and Mechanism Description

We are ready to introduce the Differentially Private Faithful Federated
Learning (DP-FFL) algorithm in Algorithm 2, which also consists of two phases.
Compared to the FFL algorithm in Algorithm 1, we add noise in lines 9, 24, and
28 based on

$\displaystyle\sigma^{2}$
$\displaystyle=\frac{16L_{f}^{2}(T_{1}+KT_{2})\log(1/\beta)}{K^{2}n_{(1)}^{2}\alpha^{2}}$
(52) $\displaystyle\sigma_{P}^{2}$
$\displaystyle=\frac{16K\log(1/\beta)}{n_{(1)}^{2}\alpha^{2}},$ (53)

where $n_{(1)}$ is the size of smallest local dataset among all agents
$\mathcal{K}$. We also adopt the Scalable VCG payment from Definition 5 in the
payment computation phase of Algorithm 2.

In the following, we introduce the DP-FFL mechanism associated to Algorithm 2:

######  Definition 7 (The DP-FFL Mechanism).

The DP-FFL mechanism $\mathcal{M}^{\rm
P}=(\mathcal{A},\mathcal{S}^{m},\boldsymbol{w}^{*},\mathcal{P})$ satisfies,
for all agents $k\in\mathcal{K},$

$\displaystyle s^{m}_{k}=\\{\nabla
F_{k}(\boldsymbol{w}[t])\\}_{t\in\mathcal{T}_{-k}}\quad{\rm and}\quad
A_{k}=\\{\nabla\tilde{F}_{k}(\boldsymbol{w}[t])\\}_{t\in\mathcal{T}_{-k}},$
(54)

where
$\mathcal{T}_{-l}=\bigcup_{j\in\\{0\\}\cup\mathcal{L}\backslash\\{l\\}}\\{1\leq
t\leq T_{2}\\}$. The output global model $\boldsymbol{w}^{*}$ and each agent
$k$’s payment $\mathcal{P}_{k}$ are determined in (48) and (50), respectively.

We re-define the gradient bound specific for Algorithm 2 in the following:

######  Definition 8 (Gradient Bound).

The gradient bound $L_{f}$ is defined as for each agent
$k\in\mathcal{K}$,131313For readability, we are overloading the notation
$L_{f}$ to avoid introducing additional parameter names.

$\displaystyle\left\lVert\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w})\right\rVert_{2}\leq
L_{f},$ (55)

for all
$\boldsymbol{w}\in\\{\boldsymbol{w}[t]\\}_{t\in\\{0,1,...,T_{1}\\}}\cup\\{\boldsymbol{w}_{l}[t]\\}_{l\in\mathcal{L},t\in\\{0,1,...,T_{2}\\}}\cup\mathcal{W}^{*},$
where
$\\{\boldsymbol{w}[t]\\}_{t\in\\{0,1,...,T_{1}\\}}\cup\\{\boldsymbol{w}_{l}[t]\\}_{l\in\mathcal{L},t\in\\{0,1,...,T_{2}\\}}$
are described in Algorithm 2 and $\mathcal{W}^{*}$ is defined in (31).

We now show that DF-FFL achieves the following privacy property:

######  Proposition 9 (Proof in Appendix IX-L).

Algorithm 2 is $(\alpha,\beta)$-differentially private.

Proof of Proposition 9 is based on [8] and [53]. Similar to Proposition 4, we
can also prove (E1) for the DF-FFL mechanism in the following:

######  Proposition 10 (Proof in Appendix IX-M).

In Algorithm 2, if we choose step sizes such that $\eta_{1}=\eta_{2}\leq
1/L_{g}$ and numbers of iterations
$T_{1}=\mathcal{O}\left(\log\left(\frac{K^{2}n_{(1)}^{2}\alpha^{2}}{dL_{f}^{2}\log(1/\beta)}\right)\right)$
and
$T_{2}=\mathcal{O}\left(\log\left(\frac{K^{2}n_{(1)}^{2}\alpha^{2}}{dL_{f}^{2}\log(1/\beta)}\right)\right)$,141414the
big-$\mathcal{O}$ notation hides other $\log$, $L_{g}$, and $\mu$ terms. the
following risk bound is true with a probability of $1-\delta$:

$\displaystyle
E(\boldsymbol{w}^{*})-\min_{\boldsymbol{w}}E(\boldsymbol{w})\leq$
$\displaystyle~{}C_{1}\frac{L_{f}^{2}d\log(Kn_{(1)})\log(1/\beta)}{Kn_{(1)}^{2}\alpha^{2}}$
$\displaystyle~{}+\sum_{k\in\mathcal{K}}\frac{1}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{2\mu
K^{2}},$ (56)

for some constants $C_{1}>0$.

###  VI-C Three-Way Tradeoffs between Privacy, Accuracy, and the Iterations
Needed

Figure 2: Impacts of $\eta_{2}$ and $\alpha$ on the iterations needed
$T_{1},T_{2}$ and payment accuracy loss bounds
$\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm VCG}_{k}\right|$.

We will discuss three-way performance tradeoffs in the following:

######  Proposition 11 (Proof in Appendix IX-N).

If we choose constant step sizes $\eta_{1}\leq 1/L_{g}$,
$\eta_{2}\leq\frac{1}{(K-1)L_{g}}$,
$L\geq\min\left\\{K,\sqrt{\frac{L_{g}(K-1)}{2\epsilon}}\frac{L_{f}}{\mu}\right\\}$,
for any $\epsilon>0$, and the iterations as

$\displaystyle
T_{1}=T_{2}=\left\lceil\frac{\log\left(\frac{B\log(C^{-1})}{A}\right)}{\log(C^{-1})}\right\rceil,$
(57)

then Algorithm 2 leads to a bounded expected payment accuracy loss:

$\displaystyle\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm
VCG}_{k}\right|\leq$
$\displaystyle~{}A\left(\frac{1+\log(\frac{B\log(C^{-1})}{A})}{\log(C^{-1})}\right)+\epsilon,$
(58)

for all agents $k\in\mathcal{K}$, where

$\displaystyle A$
$\displaystyle=\frac{8\eta_{2}dL_{f}^{2}(K+1)\log(1/\beta)}{\mu
K^{2}(K-1)n_{(1)}^{2}\alpha^{2}},$ (59a) $\displaystyle B$
$\displaystyle=\frac{(K-1)L_{f}^{2}}{2\mu},$ (59b) $\displaystyle C$
$\displaystyle=1-(K-1)\mu\eta_{2}.$ (59c)

Proposition 11 suggests a three-way tradeoff among privacy $(\alpha,\beta)$,
the iterations needed ($T_{1}$ and $T_{2}$), and accuracy
$\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm VCG}_{k}\right|$. That
is, by fixing $\beta$ and properly selecting $\alpha$ and $\eta_{2}$, one can
improve two performance metrics by trading off the third. To see this, we
consider the following three scenarios as guidelines to make such a three-way
tradeoff:

  1. 1.

To improve both privacy and iteration complexity by sacrificing accuracy, one
can set $\alpha\rightarrow 0$ to ensures privacy and set $\eta_{2}$ as a
positive constant. In this case, we have that $A\rightarrow\infty$, and hence
$T_{1}=T_{2}\rightarrow 0$. However, the payment accuracy loss in (58)
diverges to infinity, i.e.,
$\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm
VCG}_{k}\right|\rightarrow\infty$.

  2. 2.

To improve both accuracy and iteration complexity by sacrificing privacy, one
can set $\alpha$ and $\eta_{2}$ in such a way that $\eta_{2}/\alpha^{2}$ is
constant (and hence $A$ is also constant). Further, by increasing $\eta_{2}$
(and hence increasing $\alpha$ as well), we have that $C$ decreases, and hence
$\log(\log(C^{-1}))/\log(C^{-1})$ decreases. Therefore, such a strategy
decreases $T_{1}$, $T_{2}$, and
$\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm VCG}_{k}\right|$ at
the same time. However, $\eta_{2}$ is upper-bounded by the maximal step size
$\frac{1}{(K-1)L_{g}}$.

  3. 3.

To achieve perfect accuracy
$\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm
VCG}_{k}\right|\rightarrow 0$, one needs to sacrifice both iteration
complexity, privacy, and scalability. Specifically, by setting
$\alpha\rightarrow\infty$, it follows that $A\rightarrow 0$ and hence
$T_{1}=T_{2}\rightarrow\infty$. Letting $L=K$ as well, we have
$\left|\mathbb{E}[\mathcal{P}_{k}^{*}]-\mathcal{P}^{\rm
VCG}_{k}\right|\rightarrow 0$.

We present a numerical example of Proposition 11 in Fig. 2, which compares the
iterations needed and payment accuracy loss bounds at different $\alpha$ and
$\eta_{2}$. An interesting observation is that the payment accuracy loss bound
hardly changes when $\eta_{2}$ decreases. This results from the fact that
$\log((1-(K-1)\mu\eta_{2})^{-1})\approx(K-1)\mu\eta_{2}$, which makes
$A/\log(C^{-1})$ almost constant if we only tune $\eta_{2}$. On the other
hand, fixing the step size $\eta_{2}$, $T_{1}$ and $T_{2}$ decrease in
$\alpha$ and the payment accuracy loss bound increases in $\alpha$.

###  VI-D Properties

Collectively, in this subsection, we will show that the DP-FFL algorithm (and
the DP-FFL mechanism) satisfies (E2) and (E3) approximately and (E4) exactly.

######  Corollary 2 (Faithful Implementation).

If we choose $\eta_{1}\leq{1}/{L_{g}}$, $\eta_{2}\leq\frac{1}{(K-1)L_{g}}$
$T_{1}=T_{2}=\left\lceil\log\left(\frac{B\log(C^{-1})}{A}\right)/\log(C^{-1})\right\rceil$,
and
$L\geq\min\left\\{K,\sqrt{\frac{L_{g}(K-1)}{2\epsilon}}\frac{L_{f}}{\mu}\right\\}$,
then the DP-FFL mechanism is $(\tilde{\epsilon},\tilde{\delta})$-faithful,
where

$\displaystyle\tilde{\epsilon}=$ $\displaystyle
2\epsilon+2A\left(\frac{1+\log(\frac{B\log(C^{-1})}{A})}{\log(C^{-1})}\right)+\sum_{k\in\mathcal{K}}\frac{1}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\tilde{\delta})}{2K\mu}$
$\displaystyle+D\frac{L_{f}^{2}d\log(Kn_{(1)})\log(1/\beta)}{n_{(1)}^{2}\alpha^{2}},$
(60)

and $A,B,$ and $C$ are defined in (59), and $D$ is some positive constant.

Corollary 2 is a direct application of Propositions 6 and 11 and Theorem 2;
the three terms on the right-hand side of (60) come from Theorem 2,
Proposition 11, and Proposition 6, respectively.

######  Corollary 3 (Risk-Bound-Based Voluntary Participation).

If we choose $\eta_{1}\leq\frac{1}{L_{g}}$, $\eta_{2}\leq\frac{1}{(K-1)L_{g}}$
$T_{1}=T_{2}=\left\lceil\log\left(\frac{B\log(C^{-1})}{A}\right)/\log(C^{-1})\right\rceil$,
and
$L\geq\min\left\\{K,\sqrt{\frac{L_{g}(K-1)}{2\epsilon}}\frac{L_{f}}{\mu}\right\\}$,
then the DP-FFL algorithm and the DP-FFL mechanism lead to the following
inequality:

$\displaystyle{\rm RB}^{FFL}_{k,\delta}\leq~{}~{}{\rm
RB}^{L}_{k,\delta}+\epsilon+D\frac{L_{f}^{2}d\log(Kn_{(1)})\log(1/\beta)}{n_{(1)}^{2}\alpha^{2}}$
$\displaystyle+A\left(\frac{1+\log(\frac{B\log(C^{-1})}{A})}{\log(C^{-1})}\right)$
(61)

for all agents $k\in\mathcal{K},$ where ${\rm RB}^{L}_{k,\delta}$ and ${\rm
RB}^{FFL}_{k,\delta}$ are defined in (40) and (41), respectively.

We note that, as implied in Corollary 3, performing local learning does not
incur privacy loss for individual agents. Therefore, comparing the results in
Corollary 3 and Proposition 7, the DP-FFL algorithm leads to a worse risk
bound than the FFL algorithm.

Finally, Proposition 11 also implies that the DP-FFL mechanism achieves budget
balance (E4) approximately. We present the detailed analysis in [55].

##  VII Evaluation

Figure 3: Impacts of training data samples $n$ on (a) training loss and
overall costs and (b) test accuracy. We set $K=10$, $\alpha=0.1$,
$\beta=0.01$, $\Delta=0.05$, $T_{1}=80$, and $T_{2}=20$.

Figure 4:  Impacts of non-i.i.d. data, characterized by $\Delta$, on (a)
training loss and overall costs and (b) test accuracy. We set $K=10$,
$\alpha=0.1$, $\beta=0.01$, $n=10000$, $T_{1}=80$, and $T_{2}=20$.

In this section, we evaluate our proposed FFL and DP-FFL mechanisms with
$K=10$ agents. We consider regularized multinomial logistic regression for the
MNIST dataset with 60,000 training samples and 10,000 testing samples [54]. We
uniformly randomly allocate samples with label $y$ to all agents whose last
digits of their indices are $y$. For each sample allocated to agents, with a
probability of $1-\Delta$, we reallocate this sample to a random agent with
equal probabilities. Therefore, the degree of heterogeneity in this non-i.i.d.
data can be characterized by $\Delta$; a larger $\Delta$ leads to greater data
heterogeneity.

For performance comparison, we compare our proposed FFL and DP-FFL schemes
against two benchmarks: i) a gradient-based local learning benchmark, in which
agents independently solve (11), and ii) a manipulated FedAvg benchmark, in
which the server intends to execute FedAvg [3], while one agent manipulates
the federated learning algorithm by multiplying its gradient report by an
amplifying coefficient $\gamma$ in each iteration. We compare the global loss,
$F(\boldsymbol{w})$, and the weighted average test accuracy achieved by
different schemes.

Impact of the total number of training samples: We study the impact of the
number of total training data samples $n$ in Fig. 4. First, we show that our
proposed schemes significantly outperform the manipulated FedAvg, implying
that federated learning manipulated even only by one agent can lead to
significant performance loss. Therefore, it demonstrates the importance of
faithful implementation of federated learning algorithms. Second, both
proposed schemes outperform local learning with respect to either global loss
and test accuracy. This also indicates that agents are willing to voluntarily
participate in federated learning, as both proposed schemes achieve smaller
overall losses. We observe that the total number of training data samples $n$
has a greater impact on both local learning and the manipulated FedAvg
benchmarks than the proposed (FFL and DP-FFL) mechanisms. This is because the
performances both benchmarks are more sensitive to the sizes of local
datasets, compared to federated learning.

Figure 5: Impacts of (a) $\alpha$ and (b) $L$. We set $K=10$, $n=10000$,
$\beta=0.01$, $\Delta=0.05$, $T_{1}=80$, and $T_{2}=20$. We further set $L=10$
in (a) and $\alpha=0.1$ in (b).

Impact of non-i.i.d. data: We next study the impact of varying the
heterogeneity in the data given by $\Delta$ in Fig. 4. As shown in Fig. 4,
$\Delta$ only has an impact on local learning but not on the proposed
mechanisms. In Fig. 4(a), we show that, in terms of each individual agent’s
objective (overall loss), the DP-FFL and the FFL mechanisms outperform local
learning, when $\Delta\leq 0.15$. Local learning is more beneficial, compared
to federated learning, when the agents have considerably non-i.i.d. data
distributions (i.e., $\Delta\geq 0.15$). In particular, a higher degree of
heterogeneous data implies each agent has a higher portion of (both training
and test) data samples with labels corresponding to its own index (e.g., agent
$3$ may have more (both training and test) data samples with label $3$ when
$\Delta$ increases). This means that individual local datasets are more
“useful” when $\Delta$ is large, therefore, incurring a higher test accuracy
for local learning. Finally, Fig. 4 (a) and (b) imply whenever local learning
is less beneficial than the proposed mechanisms regarding the test accuracy,
the FFL and the DP-FFL schemes are more profitable for individual agents,
which is consistent with our risk-bound-based voluntary participation results
in Proposition 7 and Corollary 3 under Assumption 3.

Impacts of privacy risk $\alpha$ and the number of group $L$. We study the
impacts of the privacy risk $\alpha$ and the number of groups $L$ in Fig. 5.
Note that the manipulated FedAvg and the proposed FFL algorithm are not
directly comparable here, as they cannot guarantee differential privacy. We
set $\Delta=0.05$ and $K=10$. Fig. 5 (a) shows that both the mean and the
standard deviation of the payment accuracy loss decrease in $\alpha$, as a
larger privacy risk $\alpha$ leads to less noise in the DP-FFL algorithm. An
interesting observation is that, to attain a reasonably small payment accuracy
loss, one should choose a small $T_{2}$ for a small $\alpha$, which is
consistent with Proposition 11. Fig. 5 (b) shows that increasing the number of
groups $L$ reduces the payment accuracy loss. In addition, a relatively large
enough number of groups (i.e., $L\geq 4$) is enough to maintain a relative
small payment accuracy loss.

##  VIII Conclusions

We have studied an economic approach to federated learning robust against
strategic agents’ manipulation. We have analyzed how the key feature of
federated learning, unbalanced and non-i.i.d. data, affects agents’ incentive
to voluntarily participate and obediently follow federated learning
algorithms. We have designed the first faithful mechanism for federated
learning, achieving (provably approximately) optimality, faithful
implementation, voluntary participation, with the time complexity (in terms of
the number of agents $K$) of $\mathcal{O}(\log{K})$. We have further presented
the differentially private faithful federated learning mechanism, which is the
first differentially private faithful mechanism. It provides scalability,
maintains the economic properties, and enables one to make three-way
performance tradeoffs among privacy, convergence, and payment accuracy loss.

There are a few future directions. First, we assume that the (energy) cost of
computation and communication is negligible. It is important to consider and
analyze the impacts of such cost, and design economic mechanisms that is not
only faithful but also elicits the right amount of efforts. Second, it is also
interesting to design faithful algorithms and corresponding economic
mechanisms for other more sophisticated federated learning architectures
(e.g., multi-task federated learning [13]).

## References

  * [1] M. Zhang, E. Wei, and R. Berry, “Faithful federated learning,” in Proc. 16th Workshop Econ. Netw., Syst. Comput. (NetEcon), 2021.
  * [2] R. Kelly, “Internet of Things data to top 1.6 zettabytes by 2020,” Apr. 2015. [Online]. Available: https://campustechnology.com/articles/2015/04/15/internet-of-things-data-to-top-1-6-zettabytes-by-2020.aspx
  * [3] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, et al. “Communication-efficient learning of deep networks from decentralized data,” arXiv:1602.05629, 2016.
  * [4] A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage, “Federated learning for mobile keyboard prediction,” [Online]. Available: https://arxiv.org/abs/1811.03604.
  * [5] 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, 2019.
  * [6] S. Truex, N. Baracaldo, A. Anwar, T. Steinke, H. Ludwig, R. Zhang, and Y. Zhou, “A hybrid approach to privacy-preserving federated learning,” in Proc. ACM Workshop on Artificial Intelligence and Security (AISec), 2019.
  * [7] N. Papernot, S. Song, I. Mironov, A. Raghunathan, K. Talwar, and Ú. Erlingsson, “Scalable Private Learning with PATE,” [Online]. Available: https://arxiv.org/abs/1802.08908.
  * [8] B. Jayaraman, L. Wang, D. Evans, and Q. Gu, “Distributed learning without distress: Privacy-preserving empirical risk minimization,” Proc. Advances in Neural Info. Process. Sys. (NIPS), 2018.
  * [9] M. Hao, H. Li, X. Luo, G. Xu, H. Yang, and S. Liu, “Efficient and privacy-enhanced federated learning for industrial artificial intelligence,” IEEE Trans. Industrial Informatics, vol. 16, no. 10, pp. 6532-6542, 2019.
  * [10] X. Cao, J. Jinyuan, and N. Z. Gong, “Provably Secure Federated Learning against Malicious Clients,” in Proc. AAAI Conf. Artificial Intelligence, vol. 35, no. 8, pp. 6885-6893, 2021.
  * [11] T. D. Nguyen, et al., “BAFFLE: Towards resolving federated learning’s dilemma-thwarting backdoor and inference attacks,” under review by ICLR, 2021.
  * [12] R. D. Nowak M. G. Rabbat, “Quantized incremental algorithms for distributed optimization,” IEEE J. Sel. Areas Commun., vol. 23, pp. 798–808, 2005.
  * [13] V. Smith, C. K. Chiang, M. Sanjabi, and A. Talwalkar, “Federated multi-task learning,” In Advances in Neural Information Processing Systems, pp. 4424–4434. 2017.
  * [14] R. E. Shostak L. Lamport and M. C. Pease. “The Byzantine generals problem,” ACM Trans. Program. Lang. Syst., vol. 4, pp. 382–401. 1982.
  * [15] K. Pillutla, S. M. Kakade, and Z. Harchaoui, “Robust aggregation for federated learning,” arXiv preprint arXiv:1912.13445, 2019.
  * [16] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. Nitin Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, “Advances and open problems in federated learning,” [Online]. Available: arXiv: 1912.04977.
  * [17] G. Zhu, D. Liu, Y. Du, C. You, J. Zhang and K. Huang, “Toward an intelligent edge: Wireless communication meets machine learning,” IEEE Commun. Mag., vol. 58, no. 1, pp. 19-25, January 2020.
  * [18] S. Wang et al., “Adaptive federated learning in resource constrained edge computing systems,” IEEE J. Sel. Areas Commun., vol. 37, no. 6, pp. 1205-1221, June 2019.
  * [19] H. H. Yang, Z. Liu, T. Q. S. Quek and H. V. Poor, “Scheduling policies for federated learning in wireless networks,” IEEE Trans. Commun., vol. 68, no. 1, pp. 317-333, Jan. 2020.
  * [20] K. Yang, T. Jiang, Y. Shi and Z. Ding, “Federated learning via over-the-air computation,” IEEE Trans. Wireless Commun., vol. 19, no. 3, pp. 2022-2035, March 2020.
  * [21] T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” [Online]. Available: https://arxiv.org/abs/1804.08333.
  * [22] M. Chen, Z. Yang, W. Saad, C. Yin, H. V. Poor and S. Cui, “A joint learning and communications framework for federated learning over wireless networks,” IEEE Trans Wireless Commun., vol. 20, no. 1, pp. 269-283, Jan. 2021.
  * [23] Z. Yang, M. Chen, W. Saad, C. S. Hong and M. Shikh-Bahaei, “Energy efficient federated learning over wireless communication networks,” accepted to IEEE Trans. Wireless Commun..
  * [24] T. Zeng, O. Semiari, M. Chen, W. Saad, and M. Bennis, “Federated learning on the road: Autonomous controller design for connected and autonomous vehicles,” [Online]. Available: https://arxiv.org/abs/1804.08333.
  * [25] M. M. Amiria, D. Gündüzb, S. R. Kulkarni and H. Vincent Poor, “Convergence of update aware device scheduling for federated learning at the wireless edge,” accepted to IEEE Trans. Wireless Commun.
  * [26] Y. Zhan, J. Zhang, Z. Hong, L. Wu, P. Li, and S. Guo, “A survey of incentive mechanism design for federated learning”, IEEE Transactions on Emerging Topics in Computing, 2021\.
  * [27] J. Weng, J. Weng, J. Zhang, M. Li, Y. Zhang, and W. Luo, “Deepchain: Auditable and privacy-preserving deep learning with blockchain-based incentive,” IEEE Transactions on Dependable and Secure Computing, 2019.
  * [28] W. Y. B. Lim, Z. Xiong, C. Miao, D. Niyato, Q. Yang, C. Leung, and H. V. Poor, “Hierarchical incentive mechanism design for federated machine learning in mobile networks,” IEEE Internet Things J., 2020.
  * [29] R. Zeng, S. Zhang, J. Wang, and X. Chu, “Fmore: An incentive scheme of multi-dimensional auction for federated learning in mec,” in Proc. IEEE ICDCS, 2020.
  * [30] R. H. L. Sim, Y. Zhang, M. C. Chan, and B. K. H. Low, “Collaborative machine learning with incentive-aware model rewards,” in Proc. International Conference on Machine Learning (ICML), 2020.
  * [31] J. Kang, Z. Xiong, D. Niyato, S. Xie, and J. Zhang, “Incentive mechanism for reliable federated learning: A joint optimization approach to combining reputation and contract theory,” IEEE Internet Things J., vol. 6, no. 6, pp. 10700–10714, Dec. 2019.
  * [32] S. R. Pandey, N. H. Tran, M. Bennis, Y. K. Tun, A. Manzoor, and C. S. Hong, “A crowdsourcing framework for on-device federated learning,” IEEE Trans. Wireless Commun., vol. 19, no. 5, pp. 3241-3256, May 2020.
  * [33] Y. Jiao, P. Wang, D. Niyato, B. Lin, and D. I. Kim, “Toward an automated auction framework for wireless federated learning services market,” IEEE Trans. Mobile Comput., May 14, 2020.
  * [34] Y. Zhan, P. Li, Z. Qu, D. Zeng, and S. Guo, “A learning-based incentive mechanism for federated learning,” IEEE Internet Things J., vol. 7, no. 7, pp. 6360–6368, Jul. 2020.
  * [35] Y. Sarikaya and O. Ercetin, “Motivating workers in federated learning: A Stackelberg game perspective,” IEEE Netw. Lett., vol. 2, no. 1, pp. 23–27, Mar. 2020.
  * [36] H. Yu, Z. Liu, Y. Liu, T. Chen, M. Cong, X. Weng, D. Niyato, and Q. Yang, “A sustainable incentive scheme for federated learning,” IEEE Intelligent Systems, 2020.
  * [37] H. Yu, Z. Liu, Y. Liu, T. Chen, M. Cong, X. Weng, D. Niyato, and Q. Yang, “A fairness-aware incentive scheme for federated learning,” in Proc. AAAI/ACM AIES, pp. 393–399, 2020.
  * [38] N. Ding, Z. Fang, and J. Huang, “Optimal contract design for efficient federated learning with multi-dimensional private information,” IEEE J. Sel. Areas Commun., vol. 39, no. 1, pp. 186-200, 2020.
  * [39] P. Sun, H. Che, Z. Wang, Y. Wang, T. Wang, L. Wu, and H. Shao. “Pain-FL: Personalized privacy-preserving incentive for federated learning,” to appear in IEEE J. Sel. Areas Commun., 2021.
  * [40] V. V. Vazirani, N. Nisanm, T. Roughgarden, and E. Tardos, Algorithmic Game Theory. Cambridge University Press, 2007.
  * [41] D. C. Parkes, and J. Shneidman, “Distributed implementations of Vickrey-Clarke-Groves mechanisms,” 2004.
  * [42] J. Feigenbaum, R. Sami, and S. Shenker, “Mechanism design for policy routing,” Distributed Computing, vol. 18, no. 4, pp. 293-305, 2006.
  * [43] A. Petcu, B. Faltings, and D. C. Parkes, “M-DPOP: Faithful distributed implementation of efficient social choice problems.” J. Artif. Intell. Res. (JAIR), vol. 32, pp. 705-755, 2008.
  * [44] T. Tanaka, F. Farokhi and C. Langbort, “Faithful implementations of distributed algorithms and control laws,” IEEE Trans. Control Netw. Sys., vol. 4, no. 2, pp. 191-201, June 2017.
  * [45] V. Vapnik, “Principles of risk minimization for learning theory,” in Proc. Adv. Neural Info. Process. Syst. (NeurIPS), pp. 831-838, 1992.
  * [46] K. Sridharan, S. Shalev-Shwartz, and N. Srebro, “Fast rates for regularized objectives,” in Proc. Adv. Neural Info. Process. Syst. (NeurIPS), 21, pp.1545-1552, 2008.
  * [47] A. Ghorbani and J. Zou, “Data shapley: Equitable valuation of data for machine learning,” in Proc. International Conference on Machine Learning (ICML), 2019.
  * [48] P. Milgrom and I. Segal, “Envelope theorems for arbitrary choice sets,” Econometrica, vol. 70, no. 2, pp. 583-601, 2002.
  * [49] H. Karimi, J. Nutini, and M. W. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition,” in: CoRRabs/1608.04636 (2016).
  * [50] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of Cryptography, vol. 3876, March 2006, pp. 265–284.
  * [51] S. Song, K. Chaudhuri and A. D. Sarwate, “Stochastic gradient descent with differentially private updates,” in Proc. IEEE Global Conference on Signal and Information Processing, Austin, USA, pp. 245-248, 2013.
  * [52] M. J., Wainwright, High-dimensional statistics: A non-asymptotic viewpoint, vol. 48,. Cambridge University Press, 2019.
  * [53] M. Bun and T. Steinke. “Concentrated differential privacy: Simplifications, extensions, and lower bounds,” in Proc. Theory of Cryptography Conference, 2016.
  * [54] Y. Lecun, L. Bottou, Y. Bengio and P. Haffner, “Gradient-based learning applied to document recognition,” Proc. IEEE, vol. 86, no. 11, pp. 2278-2324, Nov. 1998.
  * [55] M. Zhang, E. Wei, and R. Berry, “Faithful edge federated learning: Scalability and Privacy”, Technical Report. [Online]. Available: https://arxiv.org/abs/1804.08333.

|  Meng Zhang (S’15 – M’19) is an Assistant Professor with the Zhejiang
University/University of Illinois at Urbana-Champaign Institute (ZJU-UIUC
Institute), Zhejiang University. He has been a Postdoctoral Fellow with the
Department of Electrical and Computer Engineering at Northwestern University
from 2020 to 2021. He received his Ph.D. degree in Information Engineering
from the Chinese University of Hong Kong in 2019. He was a visiting student
research collaborator with the Department of Electrical Engineering at
Princeton University from 2018 to 2019. His primary research interests include
network economics and wireless networks, with a current emphasis on mechanism
design and optimization for age of information and federated learning.
---|---
|  Ermin Wei is currently an Assistant Professor at the Electrical and
Computer Engineering Department and Industrial Engineering and Management
Sciences Department of Northwestern University. She completed her PhD studies
in Electrical Engineering and Computer Science at MIT in 2014, advised by
Professor Asu Ozdaglar, where she also obtained her M.S.. She received her
undergraduate triple degree in Computer Engineering, Finance and Mathematics
with a minor in German, from University of Maryland, College Park. Wei has
received many awards, including the Graduate Women of Excellence Award, second
place prize in Ernst A. Guillemen Thesis Award and Alpha Lambda Delta National
Academic Honor Society Betty Jo Budson Fellowship. Her team also won the 2nd
place in the Grid Optimization (GO) competition 2019, an electricity grid
optimization competition organized by Department of Energy. Wei’s research
interests include distributed optimization methods, convex optimization and
analysis, smart grid, communication systems and energy networks and market
economic analysis.
---|---
|  Randall Berry (F’14) is the John A. Dever Professor and Chair of Electrical
and Computer Engineering at Northwestern University. He is also a Principle
Engineer with Roberson and Associates and has been on the technical staff of
MIT Lincoln Laboratory. He received the M.S. and Ph.D. degrees from the
Massachusetts Institute of Technology in 1996 and 2000, respectively, and the
BS degree from the University of Missouri Rolla in 1993. Dr. Berry is the
recipient of a NSF CAREER award and an IEEE Fellow. He has served as an Editor
for the IEEE Transactions on Wireless Communications from 2006 to 2009, and an
Associate Editor for the IEEE Transactions on Information Theory from 2009 to
2011. He is currently a Division Editor for the Journal of Communications and
Networks and an Area editor for the IEEE Open Journal of the Communications
Society. He has also been a guest editor for special issues of the IEEE
Journal on Selected Topics in Signal Processing, the IEEE Transactions on
Information Theory and the IEEE Journal on Selected Areas in Communications.
He has served on the program and organizing committees of numerous conferences
including serving as a chair of the 2012 IEEE Communication Theory Workshop, a
TPC chair of 2010 IEEE ICC Wireless Networking Symposium, and a TPC chair of
the 2018 ACM Mobihoc conference.
---|---

Technical Report of “Faithful Edge Federated Learning: Scalability and
Privacy”

##  IX Technical Report of “Faithful Edge Federated Learning: Scalability and
Privacy”

###  IX-A Proof of Proposition 1 and Corollary 1

In this appendix, we prove Proposition 1, which also proves Corollary 1 as a
special case ($p_{k}=1$ and $p_{j}=0$ for all $j\neq k$).

We start with the following the Hoeffding’s Inequality. Consider independent
$X_{i}\in[a_{i},b_{i}]$ and their sum, $S_{n}=\sum_{i=1}^{n}X_{i}$. The
Hoeffding’s Inequality states that

$\displaystyle{\rm
Pr}(S_{n}-\mathbb{E}[S_{n}]\geq\epsilon)\leq\exp\left(\frac{-2\epsilon^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$
(62)

The optimality condition of (11) is

$\displaystyle\sum_{k\in\mathcal{K}}p_{k}\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w}^{o})=\boldsymbol{0}.$
(63)

Since $\mathbb{E}[F_{k}(\boldsymbol{w})]={E}_{k}(\boldsymbol{w})$ for all
$\boldsymbol{w}$, it follows that

$\displaystyle\mathbb{E}[\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w}^{o})]=\nabla_{\boldsymbol{w}}{E}_{k}(\boldsymbol{w}^{o}),~{}\forall
k\in\mathcal{K}.$ (64)

Let ${w}_{l}$ be the $l$-th entry of $\boldsymbol{w}$. Recall that
$L_{f}=\max_{(\boldsymbol{x},y)\in\mathcal{D}}\left\lVert\nabla_{\boldsymbol{w}}\ell(\boldsymbol{w}^{o},\boldsymbol{x},y)\right\rVert_{2}$.
For a given $l$, we have

$\displaystyle~{}~{}~{}{\rm Pr}\left(\left|\frac{\partial
F(\boldsymbol{w}^{o})}{\partial w_{l}}-\frac{\partial
E(\boldsymbol{w}^{o})}{\partial w_{l}}\right|>\epsilon\right)$
$\displaystyle={\rm Pr}\left(\left|\frac{\partial
E(\boldsymbol{w}^{o})}{\partial w_{l}}\right|>\epsilon\right)$
$\displaystyle\leq
2\exp\left(\frac{-2\epsilon^{2}}{L_{f}^{2}\sum_{k\in\mathcal{K}}p_{k}^{2}/n_{k}}\right).$
(65)

it follows that

$\displaystyle{\rm Pr}\left(\exists l\in\\{1,...,d\\}~{}{\rm
s.t.}~{}\left|\frac{\partial E(\boldsymbol{w}^{o})}{\partial
w_{l}}\right|>\epsilon\right)$ $\displaystyle=~{}$ $\displaystyle{\rm
Pr}\left(\left(\left|\frac{\partial E(\boldsymbol{w}^{o})}{\partial
w_{1}}\right|>\epsilon\right)\cup...\cup\left(\left|\frac{\partial
E(\boldsymbol{w}^{o})}{\partial w_{d}}\right|>\epsilon\right)\right)$
$\displaystyle\leq~{}$ $\displaystyle\sum_{l=1}^{d}{\rm
Pr}\left(\left|\frac{\partial E(\boldsymbol{w}^{o})}{\partial
w_{l}}\right|>\epsilon\right)$ $\displaystyle\leq~{}$ $\displaystyle
2d\exp\left(\frac{-2\epsilon^{2}}{L_{\ell}^{2}\sum_{k\in\mathcal{K}}p_{k}^{2}/n_{k}}\right).$
(66)

By setting
$\delta=2d\exp\left(\frac{-2\epsilon^{2}}{L_{\ell}^{2}\sum_{k\in\mathcal{K}}p_{k}^{2}/n_{k}}\right)$,
we have that, with a probability of $1-\delta$, the following inequality
holds:

$\displaystyle-\sqrt{\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{f}^{2}\log(2d/\delta)}{2}}\boldsymbol{1}\preceq$
$\displaystyle\nabla_{\boldsymbol{w}}{E}_{k}(\boldsymbol{w}^{o})$
$\displaystyle\preceq$
$\displaystyle\sqrt{\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{f}^{2}\log(2d/\delta)}{2}}\boldsymbol{1}$
$\displaystyle\iff\quad\left\lVert\nabla_{\boldsymbol{w}}{E}(\boldsymbol{w}^{o})\right\rVert_{2}^{2}\leq$
$\displaystyle\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{f}^{2}d\log(2d/\delta)}{2},$
(67)

where $\boldsymbol{1}$ denotes an all-ones vector. By strict convexity of
$E(\boldsymbol{w})$, we have that, with a probability of $1-\delta$, the
following inequality holds:

$\displaystyle
E(\boldsymbol{w}^{o})-\min_{\boldsymbol{w}}E(\boldsymbol{w})\leq$
$\displaystyle\frac{1}{2\mu}\left\lVert\nabla_{w}E(\boldsymbol{w}^{o})\right\rVert_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{f}^{2}d\log(2d/\delta)}{4\mu}.$
(68)

We complete the proof of Proposition 1. By replacing $\boldsymbol{w}^{o}$ by
$\boldsymbol{w}^{L}_{k}$ and ${E}(\cdot)$ by ${E}_{k}(\cdot)$ and setting
$p_{k}=1$ and $p_{j}=0$ for all $j\neq k$, we also complete the proof of
Corollary 1.

###  IX-B Proof of Proposition 2

Define $\lambda\in[0,1]$ and $\tilde{E}(\boldsymbol{w},\lambda)$ such that

$\displaystyle\tilde{E}_{k}(\boldsymbol{w},\lambda)=(1-\lambda)\sum_{j\in\mathcal{K}}p_{j}E_{j}(\boldsymbol{w})+\lambda
E_{k}(\boldsymbol{w}).$ (69)

We have $\tilde{E}_{k}(\boldsymbol{w},1)=E_{k}(\boldsymbol{w})$ and
$\tilde{E}_{k}(\boldsymbol{w},0)=E(\boldsymbol{w})$ for all $\boldsymbol{w}$.
Define

$\displaystyle\boldsymbol{w}_{k}^{*}(\lambda)$
$\displaystyle\triangleq\arg\min_{\boldsymbol{w}}\tilde{E}_{k}(\boldsymbol{w},\lambda),~{}\forall
k\in\mathcal{K},$ (70) $\displaystyle V_{k}(\lambda)$
$\displaystyle\triangleq\min_{\boldsymbol{w}}\tilde{E}_{k}(\boldsymbol{w},\lambda),~{}\forall
k\in\mathcal{K}.$ (71)

By the envelope theorem [48],

$\displaystyle\frac{\partial V_{k}(\lambda)}{\partial\lambda}=$
$\displaystyle\frac{\partial\tilde{E}_{k}(\boldsymbol{w}_{k}^{*}(\lambda),\lambda)}{\partial\lambda}$
$\displaystyle=$
$\displaystyle\int\ell(\boldsymbol{w}^{*}_{k}(\lambda))dP_{k}-\sum_{j\in\mathcal{K}}\int\ell(\boldsymbol{w}^{*}_{k}(\lambda))p_{j}dP_{j}.$
(72)

Therefore, we have

$\displaystyle\left|\min_{\boldsymbol{w}}E(\boldsymbol{w})-\min_{\boldsymbol{w}}E_{k}(\boldsymbol{w})\right|$
$\displaystyle=$
$\displaystyle\left|\int_{0}^{1}\frac{\partial\tilde{E}_{k}(\boldsymbol{w}_{k}^{*}(\lambda),\lambda)}{\partial\lambda}d\lambda\right|$
$\displaystyle=$
$\displaystyle\left|\int_{0}^{1}\int\ell(\boldsymbol{w}^{*}_{k}(\lambda))\left(dP_{k}-\sum_{j\in\mathcal{K}}p_{j}dP_{j}\right)d\lambda\right|$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\left|\int\ell(\boldsymbol{w}^{*}_{k}(\lambda))\left(dP_{k}-\sum_{j\in\mathcal{K}}p_{j}dP_{j}\right)\right|d\lambda$
$\displaystyle\leq$ $\displaystyle\left\lVert
P_{k}(\cdot)-\sum_{j\in\mathcal{K}}p_{j}P_{j}(\cdot)\right\rVert.$ (73)

In addition, we have

$\displaystyle|E(\boldsymbol{w}^{o})-E_{k}(\boldsymbol{w}^{o})|=$
$\displaystyle\left|\int\ell(\boldsymbol{w}^{o})dP_{k}-\sum_{j\in\mathcal{K}}p_{j}\int\ell(\boldsymbol{w}^{o})dP_{j}\right|$
$\displaystyle\leq$ $\displaystyle\left\lVert
P_{k}(\cdot)-\sum_{j\in\mathcal{K}}p_{j}P_{j}(\cdot)\right\rVert.$ (74)

Combining (73), (74), and Proposition 1, we complete the proof of Proposition
2.

###  IX-C Proof of Proposition 3

The problem in (15) is equivalent to

$\displaystyle\min_{\boldsymbol{w}}\sum_{k\in\mathcal{K}}\tilde{p}_{k}F_{k}(\boldsymbol{w}),$
(75)

where $\tilde{p}_{k}=\frac{\beta p_{k}}{1+(\beta-1)p_{k}}$ and
$\tilde{p}_{j}=\frac{p_{j}}{1+(\beta-1)p_{k}}$. Since (75) is similar to the
FL problem in (3), replacing $p_{k}$ by $\tilde{p}_{k}$ for all
$k\in\mathcal{K}$ in Proposition 2 proves Proposition 3.

###  IX-D Proof of Proposition 4

From Lemma 1, we have that

$\displaystyle\frac{1}{2L_{g}}\left\lVert\nabla
F(\boldsymbol{w}^{*})\right\rVert_{2}^{2}\leq$
$\displaystyle~{}F(\boldsymbol{w}^{*})-F(\boldsymbol{w}^{o})$
$\displaystyle\leq$
$\displaystyle\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o})).$
(76)

As in the proof of Proposition 1, we have

$\displaystyle{\rm Pr}\left(\left|\frac{\partial
F(\boldsymbol{w}^{*})}{\partial w_{l}}-\frac{\partial
E(\boldsymbol{w}^{*})}{\partial w_{l}}\right|>\epsilon\right)\leq
2\exp\left(\frac{-2\epsilon^{2}}{L_{\ell}^{2}\sum_{k\in\mathcal{K}}p_{k}^{2}/n_{k}}\right),$
(77)

based on which we can prove Proposition 4.

By setting
$\delta=2d\exp\left(\frac{-2\epsilon^{2}}{\sum_{k\in\mathcal{K}}p_{k}^{2}/n_{k}}\right)$,
we have that, with a probability of $1-\delta$, the following inequality
holds:

$\displaystyle\sqrt{\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{g}^{2}\log(2d/\delta)}{2}}\boldsymbol{1}$
$\displaystyle\preceq\nabla_{\boldsymbol{w}}{E}(\boldsymbol{w}^{*})-\nabla_{\boldsymbol{w}}{F}(\boldsymbol{w}^{*})$
$\displaystyle\preceq\sqrt{\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}\log(2d/\delta)}{2}}\boldsymbol{1}.$
(78)

We have

$\displaystyle~{}~{}\left\lVert\nabla_{\boldsymbol{w}}{E}(\boldsymbol{w}^{*})\right\rVert_{2}^{2}$
$\displaystyle\overset{(a)}{\leq}\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}L_{\ell}^{2}d\log(2d/\delta)+2\left\lVert\nabla_{\boldsymbol{w}}{F}(\boldsymbol{w}^{*})\right\rVert_{2}^{2}$
$\displaystyle\overset{(b)}{\leq}\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}L_{\ell}^{2}d\log(2d/\delta),$
$\displaystyle~{}~{}~{}+4L_{g}\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o})),$
(79)

where $(a)$ results from
$\left\lVert\boldsymbol{x}+\boldsymbol{y}\right\rVert^{2}\leq\left\lVert\boldsymbol{x}+\boldsymbol{y}\right\rVert^{2}+\left\lVert\boldsymbol{x}-\boldsymbol{y}\right\rVert^{2}=2\left\lVert\boldsymbol{x}\right\rVert^{2}+2\left\lVert\boldsymbol{y}\right\rVert^{2}$
for any two vectors, and $(b)$ is from (76). By strict convexity of
$E(\boldsymbol{w})$, we have that, with a probability of $1-\delta$, the
following inequality holds:

$\displaystyle E(\boldsymbol{w}^{*})-\min_{\boldsymbol{w}}E(\boldsymbol{w})$
$\displaystyle\leq\frac{1}{2\mu}\left\lVert\nabla_{w}E(\boldsymbol{w}^{*})\right\rVert_{2}^{2}$
$\displaystyle\leq\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{2\mu}$
$\displaystyle~{}~{}+\frac{2L_{g}}{\mu}\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o})).$
(80)

###  IX-E Proof of Proposition 5

In this proof, we introduce the following definitions:

$\displaystyle\Delta\boldsymbol{w}_{-k}[t]\triangleq$
$\displaystyle~{}\boldsymbol{w}_{-k}[t+1]-\boldsymbol{w}_{-k}[t]$
$\displaystyle=$ $\displaystyle~{}\eta_{2}\sum_{j\neq k}\nabla
F_{j}(\boldsymbol{w}_{-k}[t]),~{}\forall
k\in\mathcal{K},t\in\\{0,1,...,T_{2}\\},$ (81)
$\displaystyle\boldsymbol{G}_{-k}(\boldsymbol{w})\triangleq\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\nabla{F}_{j}(\boldsymbol{w})\leq\frac{1-p_{k}}{p_{k}}L_{f},~{}\forall
k\in\mathcal{K},$ (82)

and

$\displaystyle g_{k,t}(x)=$ $\displaystyle
x\boldsymbol{G}_{-k}(\boldsymbol{w}[t])^{T}\Delta\boldsymbol{w}[t]$
$\displaystyle-\int_{0}^{x}\boldsymbol{G}_{-k}(\boldsymbol{w}[t]+z\cdot\Delta\boldsymbol{w}[t])^{T}\Delta\boldsymbol{w}[t]dz,$
(83)

for all $k\in\mathcal{K},t\in\\{0,1,...,T_{2}\\}$. It follows that

$\displaystyle\frac{\partial g_{k,t}}{\partial x}=$
$\displaystyle~{}\boldsymbol{G}_{-k}(\boldsymbol{w}[t])^{T}\Delta\boldsymbol{w}[t]-\boldsymbol{G}_{-k}(\boldsymbol{w}[t]+x\cdot\Delta\boldsymbol{w}[t])^{T}\Delta\boldsymbol{w}[t]$
$\displaystyle\leq$
$\displaystyle~{}(\boldsymbol{G}_{-k}(\boldsymbol{w}[t])-\boldsymbol{G}_{-k}(\boldsymbol{w}[t]+x\cdot\Delta\boldsymbol{w}[t]))^{T}\Delta\boldsymbol{w}[t]$
$\displaystyle\leq$
$\displaystyle~{}\frac{1-p_{k}}{p_{k}}L_{g}x\left\lVert\Delta\boldsymbol{w}[t]\right\rVert_{2}^{2}.$
(84)

We have

$\displaystyle\sum_{t=1}^{T_{2}}\left\lVert\Delta\boldsymbol{w}[t]\right\rVert_{2}^{2}$
$\displaystyle=\sum_{t=1}^{T_{2}}\left\lVert\eta_{2}p_{k}\boldsymbol{G}_{-k}[t]\right\rVert_{2}^{2}$
$\displaystyle\leq L_{f}^{2}T_{2}\eta_{2}^{2}.$ (85)

Collectively, we have

$\displaystyle\left|\mathcal{P}_{k}^{*}-\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\left[F_{j}(\boldsymbol{w}^{*})-F_{j}(\boldsymbol{w}_{-k}^{*})\right]\right|$
$\displaystyle\leq\sum_{t=1}^{T}g_{k,t}(1)$
$\displaystyle\leq\frac{1-p_{k}}{p_{k}}L_{g}\sum_{t=1}^{T_{2}}\left\lVert\Delta\boldsymbol{w}[t]\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{1-p_{k}}{p_{k}}L_{g}L_{f}^{2}T_{2}\eta_{2}^{2},$ (86)

which completes the proof.

###  IX-F Proof of Lemma 2

Define $\boldsymbol{\lambda}=\\{\lambda_{k}\\}_{k\in\mathcal{K}}$ and
$\lambda_{k}\in[0,1]$. Define a vector function

$\displaystyle\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda})=\sum_{k\in\mathcal{K}}\lambda_{k}p_{k}\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w}).$
(87)

Define $\boldsymbol{w}^{*}(\boldsymbol{\lambda})$ to be the solution to the
following implicit function:

$\displaystyle\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda})=\sum_{k\in\mathcal{K}}\lambda_{k}p_{k}\nabla_{\boldsymbol{w}}F_{k}(\boldsymbol{w})=\boldsymbol{0},~{}\forall\lambda_{k}\in[0,1].$
(88)

Note that $\boldsymbol{w}_{-k}^{*}$ in (26) is the same as
$\boldsymbol{w}^{*}(\hat{\boldsymbol{\lambda}})$ given
$\hat{\boldsymbol{\lambda}}$ such that $\hat{\lambda}_{k}=0$ and
$\hat{\lambda}_{j}=1$ for all $j\neq k$. By the implicit function theorem, we
have

$\displaystyle\left[\frac{\partial
w_{k}}{\partial\lambda_{j}}\right]_{k,j}=-(\nabla_{\boldsymbol{w}}\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda}))^{-1}\cdot\nabla_{\boldsymbol{\lambda}}\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda}),$
(89)

where

$\displaystyle\nabla_{\boldsymbol{w}}\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda})=\sum_{k\in\mathcal{K}}\lambda_{k}p_{k}\nabla^{2}_{\boldsymbol{w}}F_{k}(\boldsymbol{w}),$
(90)

and

$\displaystyle\nabla_{\boldsymbol{\lambda}}\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda})=\begin{pmatrix}p_{1}\nabla
F_{1}(\boldsymbol{w})&p_{2}\nabla
F_{2}(\boldsymbol{w})&\cdot\cdot\cdot&p_{K}\nabla
F_{K}(\boldsymbol{w})\end{pmatrix}.$ (91)

Note that, $F_{k}(\boldsymbol{w})$ is positive definite due to the strong
convexity of $F_{k}(\boldsymbol{w})$. Therefore,
$(\nabla_{\boldsymbol{w}}\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda}))^{-1}$
is well defined.

Equation (89) can be re-expressed as

$\displaystyle\frac{\partial\boldsymbol{w}^{*}(\boldsymbol{\lambda})}{\partial\lambda_{k}}=-(\nabla_{\boldsymbol{w}}\mathcal{F}(\boldsymbol{w},\boldsymbol{\lambda}))^{-1}p_{k}\nabla
F_{k}(\boldsymbol{w}),~{}\forall k\in\mathcal{K}.$ (92)

The distance between $\boldsymbol{w}^{o}$ and $\boldsymbol{w}^{*}_{-k}$ is
then bounded by, where $\lambda_{j}=1$ for all $j\neq k$ and
$p_{k}=\frac{1}{K}$ for all $k$,

$\displaystyle~{}~{}\left\lVert\boldsymbol{w}^{o}-\boldsymbol{w}^{*}_{-k}\right\rVert_{2}$
$\displaystyle=\left\lVert\int_{0}^{1}\frac{\partial\boldsymbol{w}^{*}(\boldsymbol{\lambda})}{\partial\lambda_{k}}d{\lambda_{k}}\right\rVert_{2}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\frac{\partial\boldsymbol{w}^{*}(\boldsymbol{\lambda})}{\partial\lambda_{k}}\right\rVert_{2}d{\lambda_{k}}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\left(\sum_{k\in\mathcal{K}}\nabla_{\boldsymbol{w}}^{2}F_{k}(\boldsymbol{w},\boldsymbol{\lambda})\right)^{-1}\nabla
F_{k}(\boldsymbol{w})\right\rVert_{2}d{\lambda_{k}}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\left(\sum_{k\in\mathcal{K}}\nabla_{\boldsymbol{w}}^{2}F_{k}(\boldsymbol{w},\boldsymbol{\lambda})\right)^{-1}\right\rVert_{2}\left\lVert\nabla
F_{k}(\boldsymbol{w})\right\rVert_{2}d{\lambda_{k}}$
$\displaystyle\overset{(a)}{\leq}\int_{0}^{1}\frac{L_{f}}{\mu
K}d{\lambda_{k}}=\frac{L_{f}}{\mu K},$ (93)

where $(a)$ is from $\mu$-strong convexity (Assumptions 1) and Definition 3.

###  IX-G Proof of Theorem 1

######  Lemma 3.

In Algorithm 1, the following inequality holds:

$\displaystyle\left\lVert\boldsymbol{w}[t]-\boldsymbol{w}^{o}\right\rVert_{2}^{2}\leq(1-\mu\eta)^{t}\left\lVert\boldsymbol{w}[0]-\boldsymbol{w}^{o}\right\rVert_{2}^{2},\forall
t\in\\{0,1,...,T_{1}\\}.$ (94)

From Lemma 3, we have that the distance between the exact solution and the
output solution is
$\left\lVert\boldsymbol{w}^{o}-\boldsymbol{w}^{*}\right\rVert_{2}\leq
G\sqrt{\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}}$, where
$G\triangleq\left\lVert\boldsymbol{w}[0]-\boldsymbol{w}^{o}\right\rVert_{2}$.
We set $T_{1}$ such that

$\displaystyle
G\sqrt{\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}}\leq\frac{\Delta}{K},$ (95)

which is equivalent to

$\displaystyle
T_{1}\geq\frac{2\ln\left(\frac{KG}{\Delta}\right)}{\ln\left((1-\frac{\mu}{L_{g}})^{-1}\right)}.$
(96)

From Lemma 2, we have

$\displaystyle\left\lVert\boldsymbol{w}_{-k}^{o}-\boldsymbol{w}^{*}\right\rVert_{2}^{2}\leq$
$\displaystyle(\left\lVert\boldsymbol{w}_{-k}^{o}-\boldsymbol{w}^{o}\right\rVert_{2}+\underbrace{\left\lVert\boldsymbol{w}^{o}-\boldsymbol{w}^{*}\right\rVert_{2}}_{\text{Suboptimality
in Phase I}})^{2}$ $\displaystyle\leq$ $\displaystyle\left(\frac{L_{f}}{\mu
K}+\frac{\Delta}{K}\right)^{2},\forall k\in\mathcal{K}.$ (97)

Based on a similar argument as in Lemma 3, we have

$\displaystyle\left\lVert\boldsymbol{w}_{-k}[t]-\boldsymbol{w}_{-k}^{o}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(1-\frac{\mu}{L_{g}}\right)^{t}\left\lVert\boldsymbol{w}^{*}-\boldsymbol{w}_{-k}^{o}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(1-\frac{\mu}{L_{g}}\right)^{t}\left(\frac{L_{f}}{\mu
K}+\frac{\Delta}{K}\right)^{2},~{}\forall t\in\mathbb{N}.$ (98)

By $L_{g}$-smoothness, we have

$\sum_{j\neq
k}\left(F_{j}(\boldsymbol{w}_{-k}[t])-F_{j}(\boldsymbol{w}_{-k}^{*})\right)\leq\frac{L_{g}(K-1)}{2}\left\lVert\boldsymbol{w}_{-k}[t]-\boldsymbol{w}_{-k}^{*}\right\rVert_{2}^{2}.$

Combining (98) and Proposition 5, we have

$\displaystyle|\mathcal{P}_{k}[T_{2}]-\mathcal{P}_{k}^{\rm VCG}|\leq$
$\displaystyle\frac{L_{g}(K-1)}{2}\left(1-\frac{\mu}{L_{g}}\right)^{T_{2}}\left(\frac{L_{f}}{\mu
K}+\frac{\Delta}{K}\right)^{2}$
$\displaystyle+(K-1)L_{g}L_{f}^{2}\left(\sum_{t=1}^{T_{2}}\eta^{2}[t]+\eta^{2}[1]\right).$
(99)

By selecting $\eta_{2}=\frac{1}{KL_{g}}$ and

$\displaystyle
T_{2}\in\left[\ln\left(\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{\mu^{2}K\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right),\frac{\epsilon
L_{g}K}{2L_{f}^{2}}\right],$ (100)

we have $|\mathcal{P}_{k}[T_{2}]-\mathcal{P}_{k}^{\rm
VCG}|\leq\epsilon,~{}\forall k\in\mathcal{K}$, and

$\displaystyle
KT_{2}\leq\left(1+\frac{(L_{f}+\Delta\mu)^{2}L_{g}}{2\mu^{2}e\epsilon}\right)/\ln\left(\frac{L_{g}}{L_{g}-\mu}\right)=\mathcal{O}(1).$
(101)

We completed the proof.

###  IX-H Proof of Proposition 6

Let $A_{k}$ be an arbitrary action chosen by every agent $k\in\mathcal{K}$.
Given an arbitrary action $A_{k}$ played by agent $k$, let
$\boldsymbol{w}^{\prime}$ be the solution in Phase I and
$\\{\boldsymbol{w}^{\prime}_{-k}\\}_{k\in\mathcal{K}}$ be the solution in
Phase II of Algorithm 1, respectively, and $\mathcal{P}_{k}^{\prime}$ be the
agent $k$’s payment for all $k\in\mathcal{K}$.

Recall that one of the termination criteria for Phase II in Algorithm 1 is:

$\displaystyle\frac{1}{2\mu}\left\lVert\sum_{j\neq k}p_{j}\nabla
F_{j}(\boldsymbol{w}_{-k}[t])\right\rVert_{2}^{2}\leq p_{k}\epsilon.$ (102)

Such a termination criteria ensures that, no matter what action $A_{k}$ agent
$k$ plays, as long as all other agents are faithful (i.e., following the
intended algorithm), we must have

$\displaystyle\sum_{j\neq
k}\frac{p_{j}}{p_{k}}\left(F_{j}(\boldsymbol{w}_{-k}^{\prime})-F_{j}(\boldsymbol{w}_{-k}^{*})\right)\leq\epsilon,$
(103)

from the $\mu$-strong convexity of $F_{j}$ for all $j\in\mathcal{K}$.

On the other hand, define $\mathcal{P}_{k}^{\rm VCG,II}\triangleq\sum_{j\neq
k}\left(F_{j}(\boldsymbol{w}^{\prime})-F_{j}(\boldsymbol{w}^{\prime}_{-k}[T_{2}])\right)$
as the VCG payment the algorithm approximates when agent $k$ plays $A_{k}$. We
have

######  Claim 1.

The following inequality is true:

$\displaystyle\mathcal{P}_{k}^{\rm VCG,II}$ $\displaystyle=\sum_{j\neq
k}\left(F_{j}(\boldsymbol{w}^{\prime}_{-k}[0])-F_{j}(\boldsymbol{w}^{\prime}_{-k}[T_{2}])\right)$
$\displaystyle=\sum_{t=1}^{T_{2}}\sum_{j\neq
k}\left(F_{j}(\boldsymbol{w}^{\prime}_{-k}[t-1])-F_{j}(\boldsymbol{w}^{\prime}_{-k}[t])\right)$
$\displaystyle\overset{(a)}{\leq}\sum_{t=1}^{T_{2}}\sum_{j\neq k}\nabla
F_{j}(\boldsymbol{w}^{\prime}_{-k}[t-1])^{T}(\boldsymbol{w}^{\prime}_{-k}[t-1]-\boldsymbol{w}^{\prime}_{-k}[t])$
$\displaystyle=\mathcal{P}_{k}^{\prime},$ (104)

where $(a)$ is due to the convexity of $F_{j}(\boldsymbol{w})$ for all
$\boldsymbol{w}$ and $j\in\mathcal{K}$.

We are ready to focus on agent’s overall cost when it plays its faithful
action $s_{k}^{m}$. From $|\mathcal{P}_{k}[T_{2}]-\mathcal{P}_{k}^{\rm
VCG}|\leq\epsilon$ as indicated in Theorem 1, we have

$\displaystyle\mathbb{E}[J_{k}({s}_{k}^{m},\boldsymbol{s}_{-k}^{m})]$
$\displaystyle\leq\mathbb{E}\left[\sum_{j\in\mathcal{K}}F_{j}(\boldsymbol{w}^{*})-\sum_{j\neq
k}F_{j}(\boldsymbol{w}_{-k}^{*})+\epsilon\right].$ (105)

From Proposition 4, it follows that, with a probability of $1-\tilde{\delta}$,
the following inequality holds: for all possible $A_{k}$,

$\displaystyle~{}~{}~{}\mathbb{E}[J_{k}({s}_{k}^{m},\boldsymbol{s}_{-k}^{m})]$
$\displaystyle\leq
K\min_{\boldsymbol{w}}E(\boldsymbol{w})-\mathbb{E}\left[\sum_{j\neq
k}F_{j}(\boldsymbol{w}_{-k}^{*})\right]+\epsilon+K\Phi(\delta)$
$\displaystyle\overset{(b)}{\leq}KE(\boldsymbol{w}^{\prime})-\mathbb{E}\left[\sum_{j\neq
k}F_{j}(\boldsymbol{w}_{-k}^{\prime})\right]+2\epsilon+K\Phi(\delta)$
$\displaystyle\overset{(c)}{\leq}E_{k}(\boldsymbol{w}^{\prime})+\mathbb{E}[\mathcal{P}_{k}^{\prime}]+2\epsilon+K\Phi(\delta)$
$\displaystyle=\mathbb{E}[J_{k}(A_{k},\boldsymbol{s}_{-k}^{m})]+2\epsilon+K\Phi(\delta),$
(106)

where (b) is from (103), and (c) is from (104).

###  IX-I Proof of Proposition 7

From Assumption 3, we have that ${\rm RB}_{\\{\mathcal{K}\\}}\leq{\rm
RB}_{\mathcal{C}}$. If we select
$\mathcal{C}=\\{\\{k\\},\mathcal{K}\backslash\\{k\\}\\}$, the inequality ${\rm
RB}_{\\{\mathcal{K}\\}}\leq{\rm RB}_{\mathcal{C}}$ becomes:

$\displaystyle p_{k}\frac{L_{\ell}^{2}d\log(2d/\delta)}{4\mu
n_{k}}+\sum_{j\neq
k}\frac{p_{j}^{2}}{(1-p_{k})^{2}n_{k}}\frac{L_{\ell}^{2}d\log(2Kd/\delta)}{4\mu}$
$\displaystyle+\sum_{j\neq k}2p_{j}\left\lVert
P_{j}(\cdot)-\bar{P}_{\mathcal{K}\backslash\\{k\\}}(\cdot)\right\rVert$
$\displaystyle\geq$
$\displaystyle\sum_{j\in\mathcal{K}}\frac{p_{j}^{2}}{n_{j}}\frac{L_{\ell}^{2}d\log(2dK/\delta)}{4\mu}+2\sum_{k\in\mathcal{K}}p_{k}\left\lVert
P_{k}(\cdot)-\sum_{j\in\mathcal{K}}p_{j}P_{j}(\cdot)\right\rVert.$ (107)

In addition, from $|\mathcal{P}_{k}[T_{2}]-\mathcal{P}_{k}^{\rm
VCG}|\leq\epsilon$ as indicated in Theorem 1, it follows that

$\displaystyle\mathbb{E}[J_{k}({s}_{k}^{m},\boldsymbol{s}_{-k}^{m})]\leq\min_{\boldsymbol{w}}\sum_{j\in\mathcal{K}}\frac{p_{j}}{p_{k}}E_{j}(\boldsymbol{w})-\min_{\boldsymbol{w}}\sum_{j\neq
k}\frac{p_{j}}{p_{k}}E_{j}(\boldsymbol{w})+\epsilon,$ (108)

Therefore, combining (107) and (108), we prove Proposition 7.

###  IX-J Proof of Proposition 8

From (24a) and (24b), we have

$\displaystyle\mathcal{P}_{k}^{*}=\sum_{t=1}^{T_{2}}\frac{\eta_{2}}{p_{k}}\left\lVert\sum_{j\neq
k}p_{j}\nabla F_{j}(\boldsymbol{w}_{-k}[t])\right\rVert_{2}^{2}\geq
0,~{}\forall k\in\mathcal{K}.$ (109)

Hence, we have completed the proof of Proposition 8.

###  IX-K Proof of Theorem 2

Based on the proof of Lemma 2, the distance between $\boldsymbol{w}^{*}_{-k}$
and $\boldsymbol{w}^{*}_{m}$ is given by

$\displaystyle~{}~{}\left\lVert\boldsymbol{w}_{l}^{o}-\boldsymbol{w}^{o}_{-k}\right\rVert_{2}$
$\displaystyle=\left\lVert\int_{0}^{1}\frac{\partial\boldsymbol{w}^{o}(\boldsymbol{\lambda})}{\partial\lambda_{k}}d{\lambda_{k}}\right\rVert_{2}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\frac{\partial\boldsymbol{w}^{*}(\boldsymbol{\lambda})}{\partial\lambda_{k}}\right\rVert_{2}d{\lambda_{k}}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\left(\sum_{k\in\mathcal{K}}\nabla_{\boldsymbol{w}}^{2}F_{k}(\boldsymbol{w},\boldsymbol{\lambda})\right)^{-1}\nabla
F_{k}(\boldsymbol{w})\right\rVert_{2}d{\lambda_{k}}$
$\displaystyle\leq\int_{0}^{1}\left\lVert\left(\sum_{k\in\mathcal{K}}\nabla_{\boldsymbol{w}}^{2}F_{k}(\boldsymbol{w},\boldsymbol{\lambda})\right)^{-1}\right\rVert_{2}\sum_{j\in\mathcal{C}_{l}\backslash\\{k\\}}\left\lVert\nabla
F_{j}(\boldsymbol{w})\right\rVert_{2}d{\lambda_{j}}$
$\displaystyle\leq\int_{0}^{1}\frac{L_{f}(\lceil K/M\rceil-1)}{\mu
K}d{\lambda_{k}}\leq\frac{L_{f}}{\mu M}.$ (110)

Hence, we have

$\displaystyle|\mathcal{P}_{k}^{\rm S}-\mathcal{P}_{k}^{\rm VCG}|$
$\displaystyle=\left|\sum_{j\neq
k}\left(F_{j}(\boldsymbol{w}_{m}^{*})-F_{j}(\boldsymbol{w}^{*}_{-k})\right)\right|$
$\displaystyle\overset{(a)}{\leq}\frac{(K-1)L_{g}}{2}\left\lVert\boldsymbol{w}_{m}^{*}-\boldsymbol{w}^{*}_{-k}\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{(K-1)L_{f}^{2}L_{g}}{2\mu^{2}M^{2}},~{}\forall
k\in\mathcal{K},$ (111)

where (a) is by the $L_{g}$-smoothness of $F_{j}(\boldsymbol{w})$. Hence, if
we select

$\displaystyle
M\geq\min\left\\{K,\sqrt{\frac{L_{g}(K-1)}{2\epsilon}}\frac{L_{f}}{\mu}\right\\}=\mathcal{O}\left(\sqrt{\frac{K}{\epsilon}}\right).$
(112)

then we have $\left|\mathcal{P}_{k}^{\rm S}-\mathcal{P}_{k}^{\rm
VCG}\right|\leq\epsilon$.

###  IX-L Proof of Proposition 9

The main proof of Proposition 9 is based on [8]. We start with the following
intermediate notation of concentrated differential privacy [53]:

######  Definition 9.

A randomized mechanism $\mathcal{M}:\mathcal{D}^{n}\rightarrow\mathbb{R}^{d}$
is $\rho$-Zero-Concentrated Differential Privacy ($\rho$-zCDP) if for any two
adjacent datasets $\mathcal{X}$ and $\mathcal{X}^{\prime}\in\mathcal{D}^{n}$
differing in one sample, it holds for all $a\in(1,\infty)$ that

$\displaystyle\mathbb{E}\left[\exp\left((a-1)\log\frac{\mathbb{P}[\mathcal{M}(\mathcal{\mathcal{X}})=y]}{\mathbb{P}[\mathcal{M}(\mathcal{\mathcal{X}^{\prime}})=y]}\right)\right]\leq\exp((a-1)a\rho),$
(113)

for $y\in\mathbb{R}^{d}$.

Bun and Steinke in [53] provided the following lemmas to achieve zCDP with the
Gaussian mechanism. Lemmas 4-6 bound the amount of Gaussian noise to guarantee
zCDP, give the composition of multiple zCDP mechanisms, and specify the
mapping from different privacy metrics.

######  Lemma 4.

Given a function $q:\mathcal{D}\rightarrow\mathbb{R}^{n}$, the outcome
$\mathcal{M}=q(\mathcal{D})+\boldsymbol{u}$, where
$\boldsymbol{u}\in\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})$,
satisfies $\Delta_{2}(q)^{2}/(2\sigma^{2})$-zCDP.

######  Lemma 5.

For any two mechanisms $\mathcal{M}_{1}:\mathcal{D}\rightarrow\mathbb{R}^{d}$
and
$\mathcal{M}_{2}:\mathcal{D}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$.
$\mathcal{M}_{2}(D,\mathcal{M}_{1}(D))$ satisfies $(\rho_{1}+\rho_{2})$-zCDP.

######  Lemma 6.

If a randomized mechanism $\mathcal{M}$:
$\mathcal{D}^{n}\rightarrow\mathbb{R}^{d}$ satisfies $\rho$-zCDP, then it
satisfies $(\rho+2\sqrt{\rho\log(1/\delta)},\delta)$-DP for any $\delta$.

Define $F_{k}(\boldsymbol{w},\mathcal{D}_{k})$ as the empirical risk given the
local dataset $\mathcal{D}_{k}$:

$\displaystyle
F_{k}(\boldsymbol{w},\mathcal{D}_{k})=\frac{1}{K}\sum_{k=1}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\ell(\boldsymbol{w},\boldsymbol{x}_{i},y_{i}),$
(114)

Given a gradient computation in iteration $t$ in Algorithm 2, we define

$\displaystyle M_{k,t}\triangleq$ $\displaystyle\nabla
F_{k}(\boldsymbol{w},\mathcal{D}_{k})+\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d})$
$\displaystyle=$
$\displaystyle\frac{1}{K}\sum_{k=1}\frac{1}{n_{k}}\sum_{i=1}^{n_{k}}\nabla\ell(\boldsymbol{w}^{T}\boldsymbol{x}_{i},y_{i})+\mathcal{N}(\boldsymbol{0},\sigma^{2}\boldsymbol{I}_{d}).$
(115)

Supposing $\mathcal{D}_{k}$ and $\mathcal{D}_{k}^{\prime}$ only differ in one
sample, we have

$\displaystyle\left\lVert\nabla F(\boldsymbol{w},\mathcal{D}_{k})-\nabla
F(\boldsymbol{w},\mathcal{D}_{k}^{\prime})\right\rVert_{2}\leq\frac{2L_{f}}{Kn_{(1)}}.$
(116)

Thus, using Lemma 4, we have that $M_{k,t}$ is $\rho$-zCDP where
$\rho=\frac{2L_{f}^{2}}{K^{2}n_{(1)}^{2}\sigma^{2}}$. On the other hand, by
adopting the noise $\sigma^{2}_{P}$ in (53), we have that

$\displaystyle M^{\prime}_{k}$
$\displaystyle=\mathcal{P}_{k}^{S}(\mathcal{D})+\mathcal{N}({0},\sigma_{P}^{2}),\forall
k\in\mathcal{K},$ (117)

where $\mathcal{P}_{k}^{S}(\mathcal{D})\triangleq\sum_{j\neq
k}\left({F}_{j}(\boldsymbol{w}^{*},\mathcal{D}_{j})-{F}_{j}(\boldsymbol{w}_{l}^{*},\mathcal{D}_{j})\right).$
Suppose that $\mathcal{D}$ and $\mathcal{D}^{\prime}$ only differ in one
sample,

$\displaystyle\left\lVert\mathcal{P}_{k}^{S}(\mathcal{D})-\mathcal{P}_{k}^{S}(\mathcal{D^{\prime}})\right\rVert_{2}\leq\frac{2}{n_{(1)}},\forall
k\in\mathcal{K}.$ (118)

Using Lemma 4, we have that $M_{k}^{\prime}$ is $\rho_{P}$-zCDP where
$\rho_{P}=\frac{2}{n_{(1)}^{2}\sigma_{P}^{2}}$.

From Lemma 5, we have that $\boldsymbol{w}^{*}$ is $T_{1}\rho$-zCDP,
$\\{\boldsymbol{w}_{l}\\}^{*}$ are $KT_{2}\rho$-zCDP. From (116) and (118), to
make sure $\\{\mathcal{P}_{k}^{*}\\}_{k\in\mathcal{K}}$ are
$(T_{1}+KT_{2})\rho$-zCDP, i.e., $(T_{1}+KT_{2})\rho=K\rho_{P}$, it follows
that

$\displaystyle(T_{1}+KT_{2})\rho=\frac{2K}{n_{(1)}^{2}\sigma_{P}^{2}}$
$\displaystyle=\frac{2(T_{1}+KT_{2})L_{f}^{2}}{K^{2}n_{(1)}^{2}\sigma^{2}},$
$\displaystyle\longrightarrow~{}~{}~{}\sigma_{P}^{2}$
$\displaystyle=\frac{\sigma^{2}K^{3}}{(T_{1}+KT_{2})L_{f}^{2}},$ (119)

which leads to an overall $2(T_{1}+KT_{2})\rho$-zCDP for Algorithm 2,
according to Lemma 5.

Lemma 6 shows that Algorithm 2 is also
$(2(T_{1}+KT_{2})\rho+2\sqrt{2(T_{1}+KT_{2})\rho\log(1/\delta)},\delta)$-DP
for any $\delta\in(0,1)$. It follows from Lemma 6 that

$\displaystyle\rho$
$\displaystyle\approx\frac{\alpha^{2}}{8(T_{1}+T_{2}K)\log(1/\beta)},$
$\displaystyle\longrightarrow~{}~{}~{}\sigma^{2}$
$\displaystyle=\frac{16L_{f}^{2}(T_{1}+KT_{2})\log(1/\beta)}{K^{2}n_{(1)}^{2}\alpha^{2}},$
(120) $\displaystyle\sigma_{P}^{2}$
$\displaystyle=\frac{16K\log(1/\beta)}{n_{(1)}^{2}\alpha^{2}}.$ (121)

###  IX-M Proof of Proposition 10

From the $L_{g}$-smoothness assumption, it follows that

$\displaystyle~{}~{}\mathbb{E}\left[F(\boldsymbol{w}[t+1])-F(\boldsymbol{w}[t])\right]$
$\displaystyle\leq\mathbb{E}\left[\nabla
F(\boldsymbol{w}[t])^{T}\left(F(\boldsymbol{w}[t+1])-F(\boldsymbol{w}[t])\right)+\frac{1}{2L_{g}}\left\lVert\nabla
F(\boldsymbol{w}[t])+\boldsymbol{n}\right\rVert_{2}^{2}\right]$
$\displaystyle=-\frac{1}{2L_{g}}\left\lVert\nabla
F(\boldsymbol{w}[t])\right\rVert_{2}^{2}+\frac{1}{2L_{g}}\mathbb{E}\left\lVert\boldsymbol{n}\right\rVert_{2}^{2}$
$\displaystyle\leq-\frac{\mu}{L_{g}}(F(\boldsymbol{w}[t])-F(\boldsymbol{w}^{o}))+\frac{d\sigma^{2}}{2L_{g}}.$
(122)

The last inequality results from the $\mu$-strong convexity assumption. The
above equation can be written as:

$\displaystyle\mathbb{E}\left[F(\boldsymbol{w}[t+1])-F(\boldsymbol{w}^{o})\right]$
$\displaystyle\leq\left(1-\frac{\mu}{L_{g}}\right)^{T_{1}}(F(\boldsymbol{w}[0])-F(\boldsymbol{w}^{o}))$
$\displaystyle~{}~{}+\frac{d\sigma^{2}}{2\mu}.$ (123)

When
$T_{1}=\mathcal{O}\left(\log\left(\frac{K^{2}n_{(1)}^{2}\alpha^{2}}{dL_{f}^{2}\log(1/\beta)}\right)\right)$
and
$T_{2}=\mathcal{O}\left(\log\left(\frac{K^{2}n_{(1)}^{2}\alpha^{2}}{dL_{f}^{2}\log(1/\beta)}\right)\right)$,
it follows that

$\displaystyle\mathbb{E}\left[F(\boldsymbol{w}[T_{1}])\right]-F(\boldsymbol{w}^{o})$
$\displaystyle\leq
C_{1}\frac{L_{f}^{2}d\log(Kn_{(1)})\log(1/\beta)}{K^{2}n_{(1)}^{2}\alpha^{2}},$
(124)

for some constant $C_{1}>0$.

Finally, according to [46],

$\displaystyle
E(\boldsymbol{w}[T_{1}])-\min_{\boldsymbol{w}}E(\boldsymbol{w})\leq$
$\displaystyle 2\left[F(\boldsymbol{w}[T_{1}])-F(\boldsymbol{w}^{o})\right]$
$\displaystyle+\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{2\mu}.$
(125)

Therefore, we have the following holds with a probability of at least
$1-\delta$,

$\displaystyle
E(\boldsymbol{w}[T_{1}])-\min_{\boldsymbol{w}}E(\boldsymbol{w})\leq$
$\displaystyle~{}C_{1}\frac{L_{f}^{2}d\log^{2}(Kn_{(1)})\log(1/\delta)}{K^{2}n_{(1)}^{2}\epsilon^{2}}$
$\displaystyle+\sum_{k\in\mathcal{K}}\frac{p_{k}^{2}}{n_{k}}\frac{L_{\ell}^{2}d\log(2d/\delta)}{2\mu},$
(126)

for some constants $C_{1}>0$.

###  IX-N Proof of Proposition 11

We first define

$\displaystyle J_{-k}(\boldsymbol{w})\triangleq\sum_{j\neq
k}F_{j}(\boldsymbol{w}),\forall\boldsymbol{w}\in\mathbb{R}^{d}.$ (127)

From $L_{g}$-smoothness assumption, it follows that

$\displaystyle~{}~{}~{}\mathbb{E}[J_{-k}(\boldsymbol{w}[t+1])-J_{-k}(\boldsymbol{w}[t])]$
$\displaystyle\leq\mathbb{E}\left[\nabla
J_{-k}(\boldsymbol{w}[t])^{T}\Delta\boldsymbol{w}[t]+\frac{\eta_{2}}{2}\left\lVert\nabla
J_{-k}(\boldsymbol{w}[t])+\boldsymbol{z}\right\rVert_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[-\eta_{2}\nabla F(\boldsymbol{w}[t])^{T}(\nabla
J_{-k}(\boldsymbol{w}[t])+\boldsymbol{z})+\frac{\eta_{2}}{2}\left\lVert\nabla
J_{-k}(\boldsymbol{w}[t])+\boldsymbol{z}\right\rVert_{2}^{2}\right]$
$\displaystyle=-\frac{\eta_{2}}{2}\left\lVert\nabla