Federated Learning with Reduced Information Leakage and Computation
Authors: Tongxin Yin
Xuwei Tan
Xueru Zhang
Mohammad Mahdi Khalili
Mingyan Liu
Venue: Accepted by TMLR ()

Abstract: Federated learning (FL) is a distributed learning paradigm that allows multiple decentralized clients to collaboratively learn a common model without sharing local data. Although local data is not exposed directly, privacy concerns nonetheless exist as clients' sensitive information can be inferred from intermediate computations. Moreover, such information leakage accumulates substantially over time as the same data is repeatedly used during the iterative learning process. As a result, it can be particularly difficult to balance the privacy-accuracy trade-off when designing privacy-preserving FL algorithms. This paper introduces Upcycled-FL, a simple yet effective strategy that applies first-order approximation at every even round of model update. Under this strategy, half of the FL updates incur no information leakage and require much less computational and transmission costs. We first conduct the theoretical analysis on the convergence (rate) of Upcycled-FL and then apply two perturbation mechanisms to preserve privacy. Extensive experiments on both synthetic and real-world data show that the Upcycled-FL strategy can be adapted to many existing FL frameworks and consistently improve the privacy-accuracy trade-off.

Published in Transactions on Machine Learning Research (07/2024)
Federated Learning with Reduced Information Leakage and Computation
Tongxin Yin
hyin&humich..ommm edu
Department of Electricol and Computer Engineering University of Michigan
Xuwei Tan"
tan, 1206 usu. edu
Deportment of Computer Science and Engineering The Ohio State University
Xueru Zhang
zhang, (aang.12870oeeee edu
Department of Computer Science and Enginecring The Ohio State University
Mohammad Mahdi Khalili
khokil,. 1 77oosu
Deportment of Computer Science and Engineering The Ohio Stote University
Mingyan Liu
mingyan@urichh.. edu
Department of Electrical and Computer Engincering University of Michigan
Reviewed on OpenReview: ht tpts:::no en ww. d- 3w DV
*These authors contributed equally to this work.
Abstract
Federated learning (FL) distributed learning paradigm that allows multiple decentralized clients collaboratively learn a common model without sharing local data. Although local data is not exposed directly, privacy concerns nonetheless exist clients' sensitive information be inferred from intermediate computations. Moreover, such information leakage accumulates substantially over time as the same data is repcatedly used during the ilerative learning process. As a result, it can be particularly difficult to balance the privacy-accuracy trade-off when designing privacy-preserving FI. algorithms. This paper introduces Upcycled-FL, simple yet effective strategy that applies first-order approximation at every even round of model update. Under this strategy, half of the FL updates incur no information leakage and require much less computational and transmission costs. We first conduct the theorctical analysis on the convergence (rate) of Upcycled-FL and then apply two perturbation mechanisms to preserve privacy. Extensive experiments both syuthetic and real-world data show that the Upcycled-FL strategy can be adapted to many existing FL. frameworks and consistently improve the privacy-accuracy tradc-ofi!!
1 Introduction
Federated learning (FL) has emerged as an important paradigm for learning models in distributed fashion, whereby data is distributed across different clients and the goal is jointly learn model from the distributed data. This is facilitated by central server and the model can be learned through iterative interactions
Code available butps:////tthii http:://gthhab.com//mmmmmm Fta.essrrmmm//peeeeFFF..

---

Published in Transactions on Machine Learning Research (07/2024)
between the central server and clients: at each iteration, each client performs certain computation using its local data; the updated local models are collected and aggregated by the server; the aggregated model is then sent back to clients for them to update local models; and so on till the learning task is deemed accomplished.
Although each client's data is not shared directly with the central server, there is a risk of information leakage that a third party may infer individual sensitive information from (intermediate) computational outcomes. Information leakage occurs whenever the client's local gradients are shared with third parties. Importantly, the information leakage (or privacy loss) accumulates data is repeatedly used during the iterative learning process: with more computational outcomes derived from individual data, third parties have more information to infer sensitive data and it poses higher privacy risks for individuals. An example is Huang et al. (2021). which shows that eavesdroppers can conduct gradient inversion attacks to recover clients" data from the gradients. In this paper, we use differential privacy (DP) proposed by Dwork (2006), a de facto standard for preserving individual data privacy in data analysis, ranging from simple tasks such as data collection and statistical analysis (Zhang et al. 2022b Ghosh & Roth 2011 Khalili & Vakilinia 2021 Amin ct al.) 2019
Liu el al. 2021 Khalili et al.] 2021e 2019) lo complex machine learning and optinization tasks ( (Cai et al.
2024 Khalili et al.; 2021b a Huang et al. 2020 Jagielski et al., 2019 Zhang et al.) 2019b:
2018a b 2019c
Compared to other privacy prescrvation techniques, it can (i) rigorously quantify the total privacy Icakage for complex algorithms such as FL; (ii) defend against attackers regardless of their background knowledge; (iii) provide heterogeneous privacy guarantees for different clients. To achieve a certain DP guarantee, we need to perturb FL algorithms (e.g,, adding noise to the output, objective, or gradient of local clients) and the perturbation needed for achieving the privacy requirement of each client grows as the total information leakage increases. Because the added perturbation inevitably reduces algorithm accuracy, it can be difficult. to balance the privacy and accuracy trade-off in FL.
This paper proposes a novel strategy for FL called Upeycled Federated Learning (Upcycled-FL in which clients' information leakage can be reduced such that it only occurs during half of the updates. This is attained by modifying the even itcrations of a bascline FL algorithm with first-order approximation, which allows us to update the model using existing model parameters from previous iterations without using the operations on
client's data. Moreover, the updates in even iterations only involve addition/subtrace existing model parameters at the central server. Because Upcycled-FL. docsn't require local training and transmission in half of iterations, the transmission costs and the training time can be reduced significantly. It turns out that Upcycled-FL, by reducing the total information leakage requires less perturbation to attain a certain level of privacy and can enhance the privacy-accuracy trade-off significantly.
We emphasize that the idea of "upcycling information" " is orthogonal to both the baseline FL algorithm and the DP perturbation method. It can be applied to any FT, algorithms that involve local optimization at the clients. In this paper, we apply Upcycled-FL strategy multiple existing FL algorithms and evaluate them on both synthetic and real-world datasets. For DP perturbation methods, we consider both output and objective perturbation examples to quantify the privacy loss, while other DP methods can also be used.
It is worth noting that although diffcrentially private fedcrated learning has been extensively studied in the
literal ure, e.g., (Asoodeh et al.) 2021 Chuanxin el al. 2020: Zhang et al. 2022a Zheng el al.] 2021 Wang
et al. 2020b Kim et al.] 2021; Zhang et al..
2019a Baek et al. 2021 Wu et al.
2022
Girgis et al. 2021
Truex et al. 2020; Hu et al., 2020 Scif ct al.
2020 Zhao ct al., 2020 Wei et al.
2020 Triastcyn & Faltings
2019), all these algorithms need client's 's local data to update the model and the information leakage inevitably
occurs at every iteration. This is fundamentally different from this work, where we propose a novel strategy that effectively reduces information leakage in FL.
In addition to private federated learning, several approaches were proposed in the DP literature to improve
the privacy-accuracy trade-off, e.g., privacy amplification by sampling (Balle et al. 2018 Beimel et al. 2014
Hu et al. 2021 Wang et al.] 2019 Kasiviswanat han et al. 2011 Wang et al. 2015 Abadi et al. 2016
levenaging non- non-private public data (Avent et al.) 2017 Papernot et al. 2016 shuffting (Ulfrr Erlingsson et al,
2019), using weaker privacy notion (Bun & Steinke, 2016), using lighter privacy composition analysis tool
Abaai et al. 2016). However, none of these strategics affect the algorithmic propertics of learning algorithms.
By contrast, our method improves the privacy-accuracy trade-off by modilying the property of FL algorithm
The word "upcycle" refers to reusing material so as create higher-quality things than the original.
2

---

Published in Transactions on Machine Learning Research (07/2024)
(i.e,, reducing the total information leakage); this improvement the algorithmic property is independent of the privacy oodion/mechaninl or the analysis method.
Our main contributions are summarized as follows.
We propose Upcycled-FL (Algorithm D a novel stralegy with reduced information leakage and computation
that is broadly applicable many existing FL algorithms.
As an example, we apply our strategy to FedProx (Li et al., 2020) and conduct convergence (rate) analysis
(Section 5 Theorem 5.6 where we identify sufficient condition for the convergence of Upcycled-FL.
As example, we apply two differential privacy mechanisms (i.e., output perturbation and objective perturbation) to Upcycled-FL and conduct privacy analysis (Section 6 Theorem 6.2
We evaluate the effectiveness of Upcycled-FL on both synthetic and real data (Section Extensive experiments show that Upcycled-FL can be adapted to many existing federated algorithms to achieve beller performance; it effectively improves the accuracy-privacy trade-off by reducing information leakage.
2
Related Work
Differential privacy in federated learning. Differential privacy has been widely used in federated
learning to provide privacy guarantees
[Asoodeh et al. 2021
Chuanxin et al. 2020 Zhang et al. 2022a
Zheng ct al.
2021
Wang et al. 2020b
Kim et al. 2021 Zhang ct al.]
2019a
Back ct al. 2021 Wu al.
2022 Girgis et al.
2021 Truex et al.
2020 Hu el al.) 2020 Seil et al.
2020
Zhao et al. 2020
Wei al.
2020
Triastcyn & Faltings
2019 For example, Zhang et al. (2022a) uses the Gaussian mechanism for
federated learning problem and propose incentive mechanism to encourage users to share their data and participate in the training process. Zheng et al. (2021) introduces f-differential privacy, a generalized version of Gaussian differential privacy, and propose a federated learning algorithm satisfying this new notion. Wang et al. 2020bb proposes a new mechanism called Random Response with Priori (RRP) to achieve local differential privacy and apply this mechanism to the text data by training a Latent Dirichlet Allocation (LDA) model using federated learning algorithm. [Triasteyn & Faltings (2019) adapts the Bayesian privacy accounting method to the federated setting and propose joint accounting method for estimating client-level and instance-level privacy simultaneously and securely. WWii et al. (2020) presents private scheme that adds noise to parameters at the random selected devices before aggregating and provides a convergence bound. Kim et al. (2021) combines the Gaussian mechanism with gradient clipping in federated learning to improve the privacy-accuracy tradcoff. Asoodch et al. (2021) considers a different setting where only the last update is publicly released and the central server and other devices are assumed to be trustworthy. However, all these algorithms need client's local data update the model and the information leakage inevitably occurs at every iteration. This is fundamentally different from Upcycled-FL, which reuses existing results to update half of iterations and significantly reduces information leakage and computation.
Tackling heterogeneity in federated learning. It's worth mentioning that, Upcycled-FL also empirically outperforms existing baseline algorithms under device and statistical heterogeneity. In real-world scenarios, local data are often non con-identically distributed across different devices; different devices are also often equipped with different specifications and computation capabilities. Such heterogeneity often causes instability in the model performance and leads to divergence. Many approaches have been proposed tackle this issue in FL. For example, FedAvg (McMahan et al.) 2017 uses random selection of devices at each iteration to reduce the negative impact of statistical heterogeneity; however, it may fail to converge when heterogeneity increases. Other methods include FedProx (Li et al. 2020), generalization and re-parameterization of FedAvg that adds a proximal term to the objective function to penalize deviations in the local model from the previous aggregation, and FedNova (Wang et al.) 2020a) that re-normalizes local updates before updating to eliminate objective inconsistency. turns out that Upcycled-FL exhibits superior performance the presence of heterogeneity because gradients encapsulate information on data heterogeneity, the reusing of which leads boost in performance.
3

---

Published in Transactions on Machine Learning Research (07 (07/2024)
3 Problem Formulation
Consider an FL system consisting of a central server and set I of clients. Each client i has its local dataset D; and these datasets be non-i.i.d across the clients. The goal of FL is to learn model Rd from data DiezD; by solving the following optimization:
min f(w)= = (iEIPF((W:)))= = B[[[[[;;
(1)
where P: Ejez [Pyl is the size of client i's data as a fraction of the total data samples, R[] defined as the expectation over clients, Fi(w; D;) is the local loss function associated with client i and depends on local dataset D,. In this work, we allow (w; D:) to be possibly non-convex.
[D:]
FL Algorithm. Let w/ be client i's local model paramcter at time t. In FL, the model is learned through an iterative process: at each time step I, 1) local compulations: each active client updates its local model wf using its local data D;; 2) local models broadcasts: local models (or gradients) are then uploaded to the central server; 3) model aggregation: the central server aggregates results received from clients to update the global model parameter W6 = =xez Pawf; 4) model updating: the aggregated model is sent back to clients and is used for updating local models at ( 1.
During the learning process, each client's local computation is exposed to third parties at every iteration: its models /gradients need to be uploaded to the central server, and the global models calculated based on them are shared with all clients. It is thus critical to ensure the FL is crivacy-preserving In this work, we consider differential privacy as the notion of privacy.
Differential Privacy (Dwork, 2006). Differential privacy (DP) centers around the idea that the out of certain computational procedure should be statistically similar given singular changes the input, thereby preventing mcaningful inference from observing the output.
In FL. the information exposed by each client i includes all intermediate computations (wf]T Consider randomized FL algorithm A(-) that generates a sequence of private local models (0f) we say it satisfics (e, 8)diiforccnt privacy for client over T itcrations if the following holds for any possible output O E Rdd x .... x Rd, and for any two neighboring local datasets D,, D':
Pr E O(D;) S ex) Pr( E O + 6
where e [0, o0) bounds the privacy loss, and 8 E [0,1] 1] loosely corresponds to the probability that algorithm fails to bound the privacy loss by Two datascts are neighboring datasets if they are different in at most one data point.
4 Proposed Method: Upcycled-FL
Main idea. Fundamentally, the accumulation of information leakage over iterations stems from the fact that the client's data D; is used in every update. If the updates can be made without directly using this original data, but only from computational results that already exist, then the information leakage originating from these updates will be zero, and meanwhile, the computational cost may be reducod significantly. Basod on this idea, we propose Upcycled-FL, which considers reusing the earlier compulations in a new update and significantly reduces total information leakage and computational cost. Note that Upcycled-FL not a specific algorithm but effective strategy that can be used for any existing FL algorithms.
Upcycling model update. Next, we present Upcycled-FL and illustrate how the client's total information leakage is reduced under this method.
For an FL system with the objective shown Eqn. 1 the client i's local objective function is given by (w; D.). Under Upcycled-FL, we apply first-order approzimation to (w; D:) at even iterations during federated training (while odd updates remain fixed). Specifically, at 2m-th iteration, expand F;(w;; D,) at.
4

---

Published in Transactions on Machine Learning Research (07/2024)
w w/--! (local model in the previous iteration). Based on the Taylor series expansion, we have:
D;) Fi(wfm=1: (u:f"=1:::) D,) (u :D) (w w. - O w| - (w-w,
Fi(l, 2m D.) D.) + V (W 2m ; D:)" (w - w 2m- + Am ||
w 2m 112
(2)
2
for some constant Am 2 0 which may differ for different iteration 2m. Then for an FL algorithm, its model with its approximation Equ. 2 while the updates at odd iterations remain the same. We illustrate this using the following two examples.
update at 2m-th iteration under Upcycled-FL strategy can be attained by replacing
Example 4.1 (FedAvg (McMahan et al. 2017] under Upcycled-FL strategy). In FedAvg, client at each iteration updates the local model by optimizing its local objective function, i.e., w/ arg min Fi(w; Di), Vt. Under Upcycled-FL strategy, the client i's updates become:
w arg min VR "D;) w + Agn ||0
2m 11 if t= 2m
arg min Pi(w; D:),
if 1 = 2m -
Example 4.2 (FedProx (Li et al. 2020 under Upcycled-FL strategy). In FedProz, prozimal term is added to the local objective function to stabilize the algorithm under heterogeneous clients (Algorithm 2 i.e., client i at each iteration updates the local model w = arg min Fi(w; D.) + Ellw - 11? Vt. Under Upcycled-FF strategy, the client i 's updates become:
largmin, VFi(u?m-1 : : + Am 1|w w. 1m1- f|l 113 if t= 2m
w
(3)
arg min Pi(w; D:) + #1l - -am- 2112, if t= 2mm1
Next, we demonstrate how the information is upeycled under the above idea. As an illustrating example, we focus FedProx given in Example 4.2
Note that in the even update of Eqn. the only lerm that depends dataset D. is (W D;), which can be derived directly from the previous odd iteration. Specifically, according to the first-order condition, the following holds at odd itcrations:
wp 2m-1 1 = arg min (((w; + I I| 2mm imply
F. (=? + ullu? 2m-1 22t
2) 2 0.
(4)
Plug VF(u@m-11 D:) into even update of 3 we have the estimated update from the odd update:
w 2m arg min 2m- -wf 1
Am
w wi
111
M 2 I|w 2m 1112
(5)
2
where the approximately equals sign "s=" is due the approximation in Eqn. even update (5) can be reduced Lo:
2 By first-order condition,
7 w 2m-1
2m-1 2m
P + Am
It turns out that with first-order approximation, dataset D; is not used in the even updates. Because these updates do not require access to the client's data, these updates can be conducted at the central server directly. That is, the central server updates the global model by aggregating:
2m
Σ pruf SEI
2m-1
1a # Am
(w2m-1 2mm-? 2)
2m-1
/ # Am
(w)2- 2mm-2
iEI
Therefore, under Upcycled-FL strategy, even updates only involve existing global models from previous iterations (i.e., -2m-1, 2m=2) without the need for a local training epoch: both the computational cost and transmission cost are reduced significantly. Note that the first-order
operations on the
5

---

Published in Transactions on Machine Learning Research (07 (07/2024)
approximation is only applied to even iterations, while the odd iterations should remain as the origin to ensure Eqn. (4) holds. The entire updating procedure of Upcycled-FL is summarized in Algorithm 1
Because Dj is only used in odd iterations, information leakage only happens during odd updates. Intuitively, the reduced information leakage would require less perturbation to attain a certain level of privacy guarantee, which further results higher accuracy and improved privacy-accuracy trade-off. In the following sections, we first analyze the convergence property of Upcycled-FL and then apply privacy mechanisms to satisfy differential privacy.
Client
FL
FL
Giobal Aggregation
pust
Server
Cient
Upcycled-FL
Opcycled-FF
Aua
Piul
Aggregation
Server
(a) Upcycled-FL. reuses the intermediate updates
(b) Upcycled-FL. uses different, aggregation rule
Figure 1: Upcycled-FL be considered from two perspectives: (i) it can be regarded as reusing the intermediate updates of local models to reduce the total information leakage; or (ii) it can be regarded as a global aggregation method with larger global update, which accelerates the learning process with the same information leakage under the same training iterations.
Discussion. Indeed, we view two consecutive steps (odd 2m followed by even 2m) of Upcycled-FL single itcration t, then Upcycled-FedProx and FedProx will incur the same information leakage but will differ al the phase of global model aggregation, shown in Figure [(b) Specifically, instead of simply aggregating the global model by averaging over local updates (i.e., ΣiEr prws), Upcycled-FL not only takes the average of local updates but also pushes the aggregation moving more toward the updating dircction (i.c., EiEr p - 1) We present the difference between Upcycled-FL update strategy and regular aggregation strategy from these two perspectives in Figure [ As Upcycled-FL only accesses client data at even iterations, it halves the communication cost compared standard FL methods with the same number of iterations.
Algorithm Proposed aggregation strategy: Upcycled-FL
Input: Am μ 0, {D,)ee, " 2: for m = to M do
The central server sends the global model parameters 2mm-2 all the clients.
4: A subset of clients selected to be active and each active client updates its local model by finding (approximate) minimizer of local objective function:
w 2m-1 +- arg min (i(w;; D.)
or other local objective functions
5: Clients send local models to the central server.
6:
The central server updates the global model by aggregating all local models:
2m-1
Σiez
pm-
2m-1
2m
52m
3m-1
Am (--m)
2 2mm-2
2
end for
6

---

Published in Transactions on Machine Learning Research (07 (2742)
5 Convergence Analysis
In this section, we analyze the convergence of Upcycled-FL. For illustrating purposes, we focus on analyzing the convergence of Upeycxed-Peedrox. Note that we do not require local functions P.(-) to be convex. Moreover, we consider practical settings where data are non-i..d across different clients. Similar to Li et al. (2020), we introduce a mcasure below to quantify the dissimilarity between clients the federated network. Definition 5.1 (B-Disimillartty (Li et al. )020)). The local loss function F; is B-dissimilar if Vw, we have [[]VI [=
where [[]] denotes the expectation over clients (see Eqn. 11) Parameter B 2 1 captures the statistical heterogeneity across different clients: when all clients homogeneous with ii.d. data, have B = 1 for all local functions; the larger value of B, the more dissimilarity among clients.
Assumption 5.2. Local loss functions F; are B-dissimilar and L-Lipschitz smooth.
Note that B-dissimilarity can be satisfied if the divergence between the gradient of the local loss function and that of the aggregated global function bounded, as stated below.
Lemma 5.3. Vi, there erists such that F; B-dissimilar if [IVF(()) Vf(w)l Ki, Ve for some Re. Assumption 5.4. Vi, hy(w;=") = Pi(w; D.) + &ll - w01 are p-strongly convex.
The above assumptions are fairly standard. They first appeared in Li et al. (020 and are adopted in subsequent works such as T Dinh al. (2020); Khaled et al. (2020); Pathak & Wainwright (2020). Note that strongly convex assumption is not local objective [:::; D:), but the regularized function Filw;; D.) + $1 2112 i.e,, the assumption can be satisfied by selecting a sufficiently large μ >> 0. Indeed, as shown in Section 7 our algorithm still converges even when Assumption 5.2 and 5.4 do not hold (e.g.,
DNN). Next, we conduct the theoretical analysis on the convergence rate.
Lemma 5.5. Let Sm be a set of K randomly selected clients which got updated (i.e., active clients) at iterations 2m and 2m, and Es be the expectation with respect to the choice of clients. Then under Assumption and 5.4 we have
Es. 2m
1
- (
2m 2m1 + C2 1/ C3 h2
where
h
||V 2m
|| 11
h2
2112112
The delails of term C1, C2, C3 (erpressed as functions of L, B, p
D ) are in Appendia C Equ.
11
13
Lemma 5.5 characterizes the relation of the values of global objective function over two consecutive odd iterations. is easy to verify C2 C3 2 By rearranging and telescoping, we get. the following convergence rate of Upcyeled-FedProx.
Theorem 5.6 (Convergence rate of Upcycled-FedProxxs Under Assumption 5.2 and 5-4 if i&C 0, we have
M 2m
min E [|| mE[M]
E |||
M
f(
f(
C2
EM Czh
MC²
MC
MC²
where T and wn denote the inilial and the optimal global model parameters, respeclively. Both terms C2 and C3 are decreasing in Am. P
Theorem 5.6 implics that tunable μ and Am are key
that control the convergence (rate) and robustness of #pcycled-FedProx. Recall that μ penalizes the deviation of local model w from global aggregated model بي 2mm11, while An penalizes the update of local model wmt from its previous update w -
7

---

Published in Transactions on Machine Learning Research (07/2024)
Because C = Ci L, C= Fi, the condition C > 0 in Theorem 5.6 can hold for any Am. However, Am could affect the convergence rate via terms C2 = C2 L. B, p' K u+dm and C3 == Cs L, n² 1
does not depend on Am (by Equ.
[1p). for proper I and local functions
K a+>m Specifically, as the ratio Am increases, both C2 and C3 decrease (by Eqn. 12 13 which results in lighter convergence rale bound.
R
We empirically examine the impacts of μ and Am in Section 7
It is worth noting that the convergence rate also depends on data heterogencity, captured by dissimilarity B. According to Eqn. [1], C1 > 0 must hold when B = 0 (i.i.d. clients). Although Cı may become negative as B increases, the experiments in Section 7 show that Upcycled-Fedee FedProxx can still converge when data is highly heterogencous.
Assumption 5.7. | 2 h, Vm and [[V s d, Yw.
Assumption 5.7 is standard and has been used when proving the convergence of FI. algorithms (Li et al. 2019: Yang et al. 2022;: it requires that the difference of aggregated weights between two consecutive iterations and the gradient [V()]]] are bounded. Under this assumption, we have the following corollary.
Corollary 5.8 (Convergence to the stationary point). Under Assumption 5.2 5.4 and 5.7 for fixed p. K, if
then the convergence rule of Pecycled-FedPPeee reduces O Am laken such that -= 0 (
VM
Corollary 5.8 provides guidance on selecting the value of Am properly to guarantee the convergence of Upcycled-FedProx, i.c., by taking an increasing sequence of {Am 1. 1m=1- Intuitively, increasing Am during the training helps stabilize the algorithm, because the deviation local models from the previous updale gets penalized more under a larger Am
6 Private Upcycled-FL
In this section, present privacy-preserving version of Upcycled-FL. Many perturbation mechanisms can be adopted to achieve differential privacy such objective perturbation (Chaudhuri et al. 2011 Kifer
ee al. 2012), oulpul perturbation [Chaudhuri et al. 2011 Zhang et al. 2017), gradient perturbation (Bassily
let al. 2014 Wang et al. 2017), etc. In this section, we use output and objective perturbation as examples to illustrate that FL algorithms combined with Upcycled-FL strategy, by reducing the total information leakage, can attain better privacy-accurany trade-off. Note that both output and objective perturbation methods are used to generate private updates at odd iterations, which can be used directly for even updates.
Output perturbation: the private odd updates Wi'=1 are generated by first clipping the local models w,?--1 and then adding a noise random vector n.t to the clipped model:
W. 2m-11
Clip odd update:
E(w ((o2m-l)= max
11, Ilu Plla
Perturb with noise:
@?2-11 (mm + n2!
where parameter 7 > 0 is the clipping threshold; the clipping ensures that if ||w 11, 111 S T, then update remains the same, otherwise it is scaled to be of norm
Objective perturbation: random linear term (ni", w) is added to the objective function in odd (2m + 1)-th iteration, and the private local model 0mm-1 is found by solving a perturbed optimization.
Taking Upcycled-FedProx as the example, have:
w 2m++1 arg min Flww; D.)
2 F + (n." w),
Given noisy 57 generated by either method, the private even updates 6fm can be computed directly at the central server using the noisy aggregation Σier p,0,"
Privacy Analysis. Next, we conduct privacy analysis and theoretically quantify the total privacy loss of private Upcycled-FL. Because even updates computed directly using already private intermediate results
8

---

Published in Transactions on Machine Learning Research (07/2024)
without using dataset Di, no privacy leakage occurs at even iterations. This can be formally stated as the following lemma.
Lemma 6.1. For any m = 1,2,..., , if the tolal privacy loss up to 2m - can be bounded by Sm, then the total privacy loss up to the 2m-thh iteration can also be bounded by Em
Lemma 6.1 is straightforward: it can be derived directly by leveraging property of differential privacy called immanity to post-processing (Dwork et al. 2014), i.c., differentially private output followed by any data-independent computation remains satislying dillerential privacy.
Based on Lemma 6.1
we can quantify the total privacy loss of private Upcycled-FL. We shall adopt moments accountant method baadi et al. 2016) for output perturbation, and the analysis method in CCaudhuri
et al. 2011 Zhang
Zhu
2016
Zhang et al. 2018b) for objective perturbation.
Here, we focus on settings where local loss function Fj(,,, D,) := D. EdeD, [i d) for some f, and the
guarantee of privacy presented in Theorem 6.2 (output perturbation) and 6.3 (objective perturbation
below. The total privacy loss in the following theorem is composed using moments accountant method (Abadi
et al. 2016).
Theorem 6.2. Consider the private Upcycled-FL over 2M iterations under output perturbation with noise the algorithm is (E, for agent for
Mr² n2" (0,00 I) then for any 2 20
8 = exp (-
M7²
( 100 2 2 1 )
cxp
20 Mr²
Equivalently, for any 8 E [0, 1], the algorithm is (e,8)-DP for agent i for
Mr²
M7²
= 2 20 D
log( 8
20 D
Theorem 6.3. Consider the private Upcycled-FL over 2M iterations under objective perturbation with noise n ~ exp( (-a," ( [1n)) Suppose P. is generalized linear model (Iyengar et al, 2019: Bassily et al,
2014 that satisfies ||V [i; (I)] < un, |P u2- Let feature veclors be normalized such that ils norm is greater than 1, and suppose U2 I O.5/D./p holds. Then the algorithm satisfies O)DP) for agent where
EM m==
.M 20,"", "a.""uttt u.
D.1
The assumptions F, are again fairly standard in the literature, c.g., Chandhuuii et al. 2011 Zhang & Zhu 2016 Zhang et al. 2018b). Theorem 6.2 and 6.3 show that the total privacy loss experienced by each agent accumulates over iterations and privacy loss only comes from odd iterations. In contrast, if consider differentially private FedProx, accumulated privacy loss would come from all iterations. Therefore, to achieve the same privacy guarantee, private Upcycled-FI requires much less perturbation per iteration than private FedProx. a result, accuracy can be improved significantly. Experiments Section 7 shoo that Upcycled-FL significantly improves privacy-accuracy trade-off compared to other methods.
7 Experiments
In this section, empirically evaluate the performance of Upcycled-FL by combining it with several popular FL. methods. We first consider non-private algorithms to examine the convergence (rate) and robustness of Upcycled-FL, against statistical/deva device heterogeneity. Then, we adopt both output and objective perturbation to evaluate the private Upcycled-FL.
7.1 Datasets and Networks
We conduct experiments on both synthetic and real data, as detailed below. More details of cach datasct are given Appendix F.I
In supervised learning, sample (z, y) corresponds to the feature and label pair. Function (i generalized linear model it be written function of of a and y-

---

Published in Transactions on Machine Learning Research (07/2024)
Synthetic data. Using the method in Li et al. (202)) 4 we generate Syn(iid), Syn(0.0), Syn(0.5.005), (yn(1.1); four synthetic datasets with increasing statistical heterogeneity. We use logistic regression for synthetic data.
Real data. We adopt two real datasets: 1) FEMNIST, a federated version of EMNIST (Cohen et al. 2017
Here, A multilayer perceptron (MLP) consisting of two linear layers with a hidden dimension of 14x14, interconnected by ReLU activation functions, used to learn from FEMNIST; 2) Sentiment140 (Sent140), a text sentiment analysis task on tweets (Go et al. 2009). In this context, a bidirectional LSTM with 256 hidden dimensions and 300 embedding dimensions is used to train on Sent140 dataset.
7.2 Experimental setup
All experiments are conducted on a server equipped with multiple NVIDIA A5000 GPUs, two AMD EPYC 7313 CPUs, and 256GB memory. The code is implemented with Python 3.8 and PyTorch 1.13.0 Ubuntu 20.04. We employ SGD as the local optimizer, with momentum of 0.5, and set the number of local update epochs E to 10 at each ileration Note that without privacy concerns, any classifier and loss function can be plugged into Upcycled-FL. However, if we adopt objective perturbation as privacy protection, the loss function should also satisfy assumptions in Theorem 6.3
We take the cross-entropy loss as our loss function
throughout all experiments.
To simulate device heterogeneity, we randomly select a fraction of devices to train each round, and assume there are stragglers that cannot train for full rounds; both devices and stragglers selected by random seed to ensure they are the same for all algorithms.
Baselines. To evaluate the effectiveness of our strategy, we apply our Upcycled-FL method to seven representative methods in federated learning. We use the grid search to find the optimal hyperparameters for all methods to make a fair comparison. These methods include:
FodAvg (McMahan et al. 2017: FodAvg learns the global model by averaging the client's local model.
FedAvgM (Hsu et al.
2019 : FedAvgM introduces momentum while averaging local models to improve
convergence rates and model performance, especially in non-i.id. settings.
FedProx (Li et al. 2020): FedProx adds a proximal term to the local objective function, which enables more robust convergence when data is non-i.i.d. across different clients.
Scaffold (Karimireddy et al.] 2020 Scaffold uses control variates to correct the local updates, which helps in dealing with non-i.idd. data and accelorates convergence.
FedDyn (Acar et al.
2021 : FedDyn considers a dynamic regularization term to align the local model
updates more closely with the global model.
2020): PFedMe a personalization method to handle client heterogeneity. We set the hyperparamcter l in PFddMe as to accelerate the training.
PFedMe [T Dinh et al.
Yegi (Reddi et al. 2021;: Yeg considers the adaptive optimization for the global model aggregation.
Unless explicitly stated, the results we report are averaged outcomes over all devices. More details of experimental setup are in Appendix F.T.
7.3 Results
Convergence and Heterogeneity. Because even iterations of Upcycled-FL only involve addi- tion/subtraction operations with no transmission overhead and almost no computational cost, we train the Upcycled version of FL algorithms with double iterations compared to baselines in approximately same training time in this experiment. We evaluate the convergence rate and accuracy of Upcycled-FL under different datasct and heterogeneity settings. In each iteration, 30% of devices are selected with 90% stragglers. Table [ compares the average accuracy of different algorithms when the device heterogeneity is high (90% stragglers). The results show that all baselines can be enhanced by our methods. Notably, while FedAvg achieves good performance on Syn(iid), it not robust on hetcrogencous data, e.g. Syn(0,0), Syn(0.5.0.5), and Syn(1,1). Nonetheless, Upcycled-FedAyg makes it comparable with the regular FedProx algorithm, which shows that our strategy can also mitigate performance deterioration induced by data heterogeneity. When
10

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Table Average accuracy and standard deviation with 90% straggler on the testing dataset in the non-private sctting over four runs: models are trained over synthetic data (Syn) for 80 itcrations (160 for upcycled version), trained over Femnist for 150 iterations (300 for upcycled version), and trained over Sent140 for 80 iterations (160 for upcycled version). We use the grid search to find the optimal results for all methods.
Dataset
Method
Syn(ii))
Syn(0,0)
Syn(0.5,0.5)
Syn(1,1)
FEMNIST
Sent140
FedAvg
98.06
79. 79.28
81.58_u.43
80.40
81.3843.54
76.11
Upcycled-FedAAg
98.83
81.4620048
82.89
$1.4940.55
82.10
76.3210.46
FedAvgM
98.4320.07
80.2920.83
82.60
80.59
80.15+3.72
75.720.85
Upeycled-FedAvvVV
98.7210.44
81.74
$3.13
81.37 10.82
81.30
74.8812.29
FedProx
96.522t.07
80. 80.7220.77
81.99_0.68
81.1920.10
79.35
73.9440.15
Upcycled-FedProx
97.62#4.32
80.88
83.10 20.83
81.94
80.33
74.25
Scaffold
90.51
80.26=1.54
82.44 1.68
74.91
76.83
76.34
Upeycled-Scaffold
98.6840.12
81.10
82.64
76.14
77.88
77.34
FedDyn
97.00
81.62
80.64 0.81
77.27 #2.95
81.76+60.98
75.97
Updycled-FedDyn
98.32220.0
82.41 1.00
82.89
80.03 +3.02
83.33
76.03
pFedme
96.30.0.14
89.15.0.24
89. $9.43_0.61
93.06
71.73
72.81
Upcycled-pFedme
96.77.10.12
89.08
89.55 20.62
93.1210.25
76.66
74107 10.74
Yod
99.30
81.20
79.49 1.33
78.95
73.53
77.02+0.07
(ipeycled-FedYon
99.41100s2
81.65=2.44
80.84
80.17
10.84
75.64
77.5910.26
data is i..dd, FedProx with the proximal term -|| w' may hurt the performance compared with FedAvg. However, the proximal term can help stabilize the algorithm and significantly improve the performance in practical settings when data is heterogeneous; these observations are consistent with (Li et al.) 2020 Importantly, Upcycled-FL strategy further makes it more robust statistical heterogeneity than regular FedProx as it could attain consistent improvements for all settings.
0.70
23
22
0.55
3
0.40
03
64
10
training time
training time
training time
troccadPediig
Ubre
Uncrled4eckog
Mpocidd
of
Tedkop
Teckig
Uso
stedir
(eocis//adiigg
Pelly:
(a) Sin(iid)
(b) (y.(0.5.0.5
(c) FEMNIST
Comparison on average loss and standard deviation between Upcycled-FL. methods and original FL algorithms in the non-private setting under the approximate same training time. The training time refers to the time needed for given number of iterations. Upcycled-FL does not require update in the even iterations, allowing Upcycled-FL to train with doubled iterations.
Figure 2:
Figure [(a) 2 and [ compare the convergence property on Syn(iid), Syn(0.5.0.5) and FEMNIST. Note
that, by using the aggregation rule Figure [(b] the training time of Upcycled-FL. is almost the same the baselines without introducing extra cost. We observe that under the same training time (the number
11

---

Published in Transactions on Machine Learning Research (07 (224))
of iterations for baselines), Upcycled-FL strategy brings benefits (achieving lower loss along training) for baselines in most cases. And this improvement is significant when the dataset is i.i.d. The loss trends are consistent with results in Table [
We provide more results on the other three datasets in Appendix F.3
0.05
0.7
l055
0.50
0.6
0.45
0.35
0.4
20
60
30
Iteration
Iperation
Uf
Upcycled--eee
Upsye
Ubryc Feottug
Ficyeles-Feeiigg
Upoye ed-iiedhhgg
Fod4ugM
Upcyded FodDyn
Festrogi
FoskogM
Upcy FodDyn
Fodhoogi
Upeyc wdtrox
TweDyn
Uptyclet- withrox
Feddyn
(a) Syn(iid)
(b) Syn(0.0)
1.0
0.0
1055
0.6
0.6
0.5
0.4
20
30
50
90
70
50
10
20
30
40
50
60
70
80
iteration
iteration FeoFrox
Upcydies
FooProx
Upcycted #FodMs
Upcycled Fostug
Upcycled FFoMM
Feotig
Upcycled Scattold
pteotts
resPug
Upsye wa ao-scallod
phestte
Scafted
Uncycled- FestAug
Scarfo a
FooAugM
Upcyclod FoaDyn
FosVogi
FosArgH
Upcyc FodDyn
Festogg
Uscyciod FodProx
FeaDryn
Uecycled FooPrrx
FedDyn
(c) 5ym(0.5,0.5)
(d) Sym(1,1)
Figure 3: Comparison on average loss and standard deviation of private Upcycled-FL. and private FL methods using output perturbation. The noise parameter or 1.0 for all baselines, while a of the Upeycled version is set 0.8. Taking the iid dataset as an example, = 1.40 for the Upcycled version, which ensures stronger privacy than the original method with 1.59.
Privacy-Accuracy Trade-off. We next inspect the accuracy-privacy trade-off of private Upcycled-FL and compare it with private baselines. Although we adopt both objective and output perturbation to achiove differential privacy, other techniques can also be used. For each parameter setting, we still conduct a grid search and perform independent runs of experiments. To precisely quantify privacy, no straggler is considered this experiment. We reported the results using output perturbation and objective perturbation. Figure and demonstrate the performance of private Upcylced-FL. and private baselines on synthetic data using two types of perturbation respectively. We also report the results on real data in Appendix F
Here we carefully set the perturbation strength of cach algorithm such that the privacy loss for private Upcycled-FL. is strictly less than the original methods. As expected, private Upcycled-FL is more stable than baselines and attains a lower loss value under smaller e. This is because the private Upcycled-FL with less information Icakage requires much less perturbation to attain the same privacy guarantce as FL methods under privacy constraints. We also observe that general Upcycled-FL can be used augment all baseline methods with without client. local heterogeneity.
12

---

Published in Transactions on Machine Learning Research (07 (07/202) /022)
0.9
1.0
11
0.7-
0.5
10
30
40
60
70
10
30
40
60
70
iteration
iteration
Upcycled-Fedleg
Festfrxx
Upcycled- oFedMe
Upcyded-Feede
FedProx
Upryceed Feeeee
Foddigg
Upcycled Scaffo
pPadMe
Fedkig
SpcyciedSScaffa
precttt
ineye eetought
Sceffoul
Uppyycled--edfogg
Scaiftsts
Uprye wotto
Fodfrugh
Upcycted FesDyn
Fedhfog)
Fesluggh
Upcycled FexDyn
Fedtoggl
Upcycles-sahhhe Pad
PedDDy
Paxtyyn
(a) Syn(iid)
(b) Syn(0.0)
0.9
0.7
0.5
0.6
0.5
10
20
30
40
50
60
70
80
10
20
40
50
60
70
80
iteration
iteration
Feolep
Upcycled MFedMe
Upcycled- FestAug
OpryctediPFeMMe
Scatteld
Festun
Uprye ed-Scattod
pFedMte
Uscydes
FooYogi
Upcycled
Scoffs
Upoydled
upsycled-rwdDyn
Optye
Fectrogi
Upcydes
Upcycled
FedDyn
(c) 5yn(0.5.0.5)
(d) Sym(1,1)
Figure 4: Comparison average loss and standard deviation of private Upcycled-FL and private FL. methods using objective perturbation. Under objective perturbation, noise parameter a is 10 for all baselines, while of the Upeycled version is set to 20 to ensure stronger privacy than the original versions. Taking the iid dataset as an example, ē associated with these noise parameters is 7.36 for FedProx and 7.25 for Upcycled-FedProx (when = 0.5).
8 Conclusion
This paper proposes Upcycled-FL, novel plug-in federated learning strategy under which information Icakage and computation costs can be reduced significantly. We theoretically examined the convergence (rate) of Upcycled-FedProx, a special case when Upcycled-FL strategy is applied to a well-known FL algorithm named FedProx. Extensive experiments on synthetic and read data further show that Upcycled-FL can combined with common FL algorithms and enhance their robustness on heterogencous data while attaining much better privacy-aceuracy trade-off under common differential privacy mechanisms.
Acknowledgments
This material is based upon work supported by the U.S. National Science Foundation under awards ITS-2040800, UIS-2112471, LIS-2202699, IIS-230159,, and CMM1-2301601, by grants from the Ohio State University's Translational Data Analytics Institute and College of Engineering Strategic Rescarch Initiative.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer
13

---

Published in Transactions on Machine Learning Research (07/2024)
and communications security, pp. 308-318, 2016.
Durmus Alp Emre Acar, Yuc Zhao, Ramon Matas Navarro, Matthow Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization, arXiv preprint arXiv:2111.04263 2021.
Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. Differentially private covariance estimation. Advances in Neural Information Processing Systems, 32, 2019.
Shahab Asoodeh, Wei-Ning Chen, Flavio P Calmon, and Ayfer Özgür. Differentially private federated learning: An information-theorett perspective. In 2021 IEEE International Symposium on Information Theory (TSTT). pp. 344-349. IEFE, 2021.
Brendan Avent, Aleksandra Korolova, David Zeber, Torgeir Hovden, and Benjamin Livshits. (BLENDER) Enabling local search with a hybrid differential privacy model. In 26th (USENIX) Security Symposium ([USENIX) Security 17), pp. 747 764, 2017.
Chunghum Back, Sungwook Kim, Dongkyun Nam, and Jihoon Park. Enhancing differential privacy for lederated learning at scale. IEEE Access, 9:148090-148103, 2021.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: tight analyses via couplings and divergences. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 6280 6290, 2018.
Racf Bassily, Adam Smith, and Abhradecp Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEFE, 2014.
Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine learning, 94(3):401-437, 2014.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 335-658. Springer, 2016.
Zhongteng Cai, Xueru Zhang, and Mohammad Mahdi Khalili. Privacy-aware randomized quantization
via linear programming. In The 40th Conference Uncertainty in Artificial Intelligence, 2024. URL httpps://operrevie: wett/foorum http:://ggaaaaeeeeeeeeeeeeeeeees
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Rescarch, 12(3), 2011.
Zhou Chuanxin, Sun Yi, and Wang Degang. Federated learning with gaussian differential privacy. In Proccedings of the 2020 2nd International Conference on Robotics, Intelligent Control and Artificial Intelligence, pp. 296-30 306-301-420 2020.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist handwritten letters. In 2017 international joint conference neural networks (IJCNN), pp. 2921-2926.
IEEE, 2017.
Cynthia Dwork. Difforential privacy. In International Colloquium on Automata, Languages, and Programming, pp. 1- Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., ((344)2111-403 2014.
Arpita Ghosh and Aaron Roth. Selling privacy at auction. In Proceedings of the 12th ACM Conference on Electronic Commerce, EC '11, pp. 199-208, New York, NY, USA, 2011. Association for Computing Machinery, ISBN 9781450302616. doi: 10.1145 1993365. URL lttpp:://et //doi. org/10. 1145/1993
574. 1993605
14

---

Published in Transactions on Machine Learning Research (07/2024)
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffidd model of differential privacy in federated learning. In International Conference Artificial Intelligence and Statistics, pp. 2521 2529. PMLR, 2021.
Alec Go, Richa. Bhayani, and Lei Huang. Twitter sentiment classification using distant supervision. CS224N project report, Stanford, 1112):2009, 2009.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Mcasuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335, 2019.
Jingchen Hu, Joerg Drechsler, and Hang Kim. Accuracy gains from privacy amplification through sampling for differential privacy. arXiv preprint arXiv:2103.09705, 2021.
Rui Hu, Yuanxiong Guo, Hongning Li, Qingqi Pei, and Yanmin Gong. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7(10):9530 9539, 2020.
Chunan Huang, Xueru Zhang, Rasoul Salehi, Tulga Ersal, and Anna G. Stelanopoulou. A robust energy and emissions conscious cruise controller for connected vehicles with privacy considerations. In 2020 American Control Conference (ACC), pp. 4881-44444 4886, 2020. doi: 10.23919/ AC045564.202009144446
Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, and Sanjeev Arora. Evaluating gradient inversion at tacks and defenses in federated learning. Advances in Neural Information Processing Systems, 34:7232 7241, 2021.
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium Security and Privacy (SP), pp. 299-316. TREE, 2019.
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi- Maiiiiii,iajjrrdi, and Jonathan Ullman Differentially private fair learning. In International Conference Machine Learning, pp. 3000 3008. PMLR, 2019.
Sai Pranceth Karimiroddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Scbastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference machine learning, pp. 5143. PMLR, 2020.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793 886,,8266660 2011.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4529. PMLR, 2020.
Mohammad Mahdi Khalili and Iman Vakilinia. Trading privacy through randomized response. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1-6, IEEE, 2021.
Mohammad Mahdi Khalili, Xueru Zhang, and Mingyan Liu. Contract design for purchasing private data using a biased differentially private algorithm. In Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation, pp. 1-6, 2019.
Mohammad Mahdi Khalili, Xueru Zhang, and Mahed Abroshan. Fair sequential selection using supervised learning models. Advances in Neural Information Processing Systems, 34:28144-28155, 2021a.
Mohammad Mahdi Khalili, Xueru Zhang, Mahed Abroshan, and Somayeh Sojoudi. Improving fairness and privacy in selection problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8092-88100 8100, 2021b.
Mohammad Mahdi Khalili, Xueru Zhang, and Mingyan Liu. Designing contracts for trading private and heterogeneous data using biased differentially private algorithm. IEEF Access,
2021c.
15

---

Published in Transactions on Machine Learning Research (07/2024)
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high- dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings, 2012.
Muah Kim, Onur Günlü, and Rafael F Schaefer. Federated learning with local differential privacy: Trade-offs between privacy, utility, and communication. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2650 2654. IEEE, 2021.
Tian Li, Anit Kumar Sahu, Manzil Zahoer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. In International Conference on Learning Representations, 2019.
Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Advances in neural information processing systems, 34:3887 7901, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaisc Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLRR 2017.
Nicolas Papernot, Martin Abadi, Ulfar Erlingsson,, Ian Goodfellow, and Kunal Talwar. Semi-supervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:161000555,, 2016.
Reese Pathak and Martin J Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. Advances in Neural Information Processing Systems, 33:7057-7066, 2020.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2021. URL
2020 IEEE International Symposium Information Theory (ISIT), pp. 2604-2609. IEEE, 2020. Mohamed Seif, Ravi Tandon, and Ming Li. Wireless federated learning with local differential privacy. In
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:21394-21405, 2020.
Alcksci Triastcyn and Boi Faltings. Foderated learning with bayesian differential privacy. In 2019 IEEE International Conference on Big Data (Big Data), pp. 2587 2596. IEEE, 2019.
Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: Federated learning with local differential privacy. In Proccedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, pp- 61 66, 2020.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Fastor and more general. Advances in Neural Information Processing Systems, 30, 2017.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33: 7611-7623, 2020a.
Yansheng Wang, Yongxin Tong, and Dingyuan Shi. Federated latent dirichlet allocation: local differential privacy based framework. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1883, 2020b.
Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Postcrior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pp. 2493 2502. PMLR, 2015.
Yu-Xiang Wang, Borja Balle, and Shiva. Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2019.
16

---

Published in Transactions on Machine Learning Research (07 (2742)
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IREF Transactions on Information Forensics and Security, 15:3454 3469, 2020.
Xiang Wu, Yongting Zhang, Minyu Shi, Pei Li, Ruirui Ti, and Neal N Xiong- An adaptive federated learning scheme with differential privacy preserving. Future Generation Computer Systems, 127:362-372 2022.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pp. 25331-25363. PMLR, 2022.
Jiale Zhang, Junyu Wang, Yanchao Zhao, and Bing Chen. An efficient federated learning scheme with differential privacy in mobile edge computing. In International Conference on Machine Learning and Intelligent Communccations, pp. 538-550 Springer, 2019a.
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 3922-3928, 2017.
Lefeng Zhang, Tianqing Zhu, Ping Xiong, Wanlei Zhou, and Philip Yu. A robust game-theoretical federated learning framework with joint diffcrential privacy. IEEE Transactions on Knowledge and Data Enginccring, 2022a.
Tao Zhang and Quanyan Zhu. Dynamic differential privacy for admm--asee distributed classification learning. IEEE Transactions on Information Forensics and Security, 12(1):172-113) 187, 2016.
Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Improving the privacy and accuracy of admi- based distributed algorithms. In International Conference on Machine Learning, pp. 3796-5803 PMLR, 2018a.
Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Recycled admm: Improve privacy and ac- curacy with less computation in distributed algorithms. In 2018 56th Annual Allerton Conference on Commmicattion Control, and Computing (Allerton), pp.
IEEE, 2018b.
Xueru Zhang, Chunan Huang, Mingyan Liu, Anna Stefanopoulon, and Tulga Ersal. Predictive cruise control with private vehicle-to-vehiille communication for improving fuel consumption and emissions. TREE Communications Magazine, 57(10):91 97, 2019b.
Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Recyeled admm: Improving the privacy and accuracy of distributed algorithms. IEEE Transactions on Information Forensics and Security, 15: 1723 1734, 2019c.
Xucru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Differentially private real-time release of sequential data. ACM Transactions on Privacy and Security, 26(1):1-22 29, 2022b.
Yang Zhao, Jun Zhao, Mengmeng Yang, Teng Wang, Ning Wang, Lingjuan Lyu, Dusit Niyato, and Kwok- Yan Lam. Local differential privacy-based federated learning for internet of things. JEEE Internet of Things Journal, 8(11): (111)88836-855) 2020.
Qinqing Zheng, Shuxiao Chen, Qi Long, and Weijie Su. Federated f-differential privacy. In International Conference on Artificial Intelligence and Statistics, pp. 2251 2259. PMLR, 2021.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local central differential privacy via anonymity. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019. URL http:::/t////aee orgg/bs//811..
2469
17

---

Published in Transactions on Machine Learning Research (07 (07/2024)
A Notation Table
I set of agents
D dataset of agent
Pa size of agent i's data as fraction of total data samples
wf
agent i's local model parameter al time / aggregated model central server differentially private version of w local objective function of agent overall objective function
w
F
n
random noise added to agent i at time
hyper-parameter for proximal term in FedProx and Upcycled FedProx
Am
hyper-parameter for first-order approximation at iteration 2m in Upcycled-FI the clipping threshold for output perturbation
B
Lemmas
Lemma B.1. Define Wr Ex(w)). Suppose conditions Theorem 5.6 hold, then the following holds Vm:
f((r2+1)) < f(w-2m-1) C L, B, u
1
2m 11
+C2 L, B, p² u Am
2m -
||w02m-1
w
2m-2
+0s L, B,
1m2=-1 3 2m 2m
1 p μ + Am
where coefficients satisfy
1 - 1 t B,
LB LB2
12p 2/
Oz
I, B
1
P
112p +
L2
L L+
+
L(L + p)B BL
P
11 p
+
Am
112
0²
1e + Am
Cs L, B,
1
1
I[L+ p)2
112
2p²
( (
Lemma B.2. Let Sm be the set of K randomly selected local devices got updated at iterations 2m and 2m, and Es,., [i] be the expectation with respect to the choice of devices. Then we have
Es., (f s f(arm
1 + + (B,L, K'
IVF 1111
+C B, L,
1 P
|Vf I|| | 32m-2
K' p
+Cs B, T, K' p
1 P
1
21-
1 Am
where coefficients satisfy
ō (B,L,
K' )
1 1
2B2
2LB + P
2 B K P
Kp
P
C B, L, K + Xm
ALB
2LB P
I.
+ 2L
L+D
2
P
K2
P
K P
K
+ Am
Co B, L, 1 1
2 L
L +
2 L
+ 2T.
K' 1
p Am
K p2
P
K p
11 Am
18

---

Published in Transactions on Machine Learning Research (07 (07/2024)
C
Proofs
Proof of Lemma B.1
Proof. Since local functions Fj are L-Lipschitz smooth, at iteration 2m 1, we have
f((2mt1)
$ f(
(V ( 2m g2m+1 22m +
112
2
/ 2m- 1) - + (amtl)
2 1mttt 2mm-11
11
S f(
( 2m 1012 + - ( -| || +
| 1
w 2m
2mm111
112
where
2m++1
v f( + 5amt1 2m Eg ( + tw wpm+ w2m-1
(7)
By first-order condition, the following holds at (2m + 1)-th iteration:
w 2m+1
2mm-1
(w) 2m+1) + 2m -mmm1
Plug into Eqn.
we have
1 V 111))-F(44 (u(mmtt))) + 2m 2m-1
2m++
E.
By L-Lipschitz smoothness and Jensen's 's inequality, we have
2m+
||
<
E,
V FF
2m - VFil (wp
(mm++)1] |||
+ 11
2m-11
(8)
E,
2m-1
w.
2m+ ||
+
2m w 2mm-111
E,
2m+1
2m
+
| 22m-111
1
Since h; p-strongly convex, F; is L-Lipschitz smooth, and w
2m+1
arg min h; (w: am) we have
||m? 1m2
22m
(um (m 100 (F((2.2)))
m - -2m-11||+ 1 [[FF((022-11)
(9)
Plug Equ.
8
2m+1jl
E V 2m-1 ||| + (12 +
1?
L+ 11 ||ا
2m-111
μp
pp
Consider the following term
|| 2m+
2mm
|| (wffmm+
w 2m
< |.lllw?m++1 - 2mm-1
(10)
Ef || 2mm+1
2m
||اي
-2m
L +
1R,
2m
2m
+
p
p
19

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Because F; is B-dissimilar, have
E, [VF s BIV
Therefore,
1(12m+1)
1 f(52m-1)
( 112 ( -11001=m++1111111111111 + | 2m+1 - 2mm-111
{ LB
LB²
( ||(
122p
20
L.2
++ 11
LL + p) B)B
+
( 11w2m 2m
pPp
112
L(L
2)²
|a52m
2m-1111 112
2p²
After applying first-order approximation in even iterations, we have
2m
2m
2m
2m
Am
Therefore,
LB
LB
1( 1 (
| ( )11
12pp
20
L
+
L+
+
LLL + D)B
11
[ (1) 2m 2m-1) |||
-
2m
112p
112
1²
14 Am
[[ + p)2
112
21
2p²
(μ + Am))
)m
The Lemma B.1 is proved.
Proof of Lemma B.2
Proof. Because local function F; is L-Lipschitz smooth, f is local Lipschitz continuous.
1 & f((2m+1) + Lo 2m 2mm-1
where To is the local Lipschitz continuouty constant. Moreover, have
Lo S [[ 2m- |)]| 1)|
2m 2mm-11 -11 + m|l 2m+1 2mmm1 11]
Therefore,
Es.. If [m)) (m0mm++
+ Es...
(1V5((52mm)) + L[I 2m+1 @am-11 1|| + || 2m+1 - w2m- ||
1 - 33m+111
= = + (|Vf( ||| 2m w2m-111 Es., 11| 3m
+ LBs...
||ا| - ||| ا (2m+11|
<1(12m+1) + (|Vf(T2m-)) ||| 2L 2mm+1 x2m-11)) 11) IEs m 22m+1
LEs...
-
20

---

Published in Transactions on Machine Learning Research (07 2024)
When K devices are randomly selected, by Equ.
9
we have
3 Es..
2m+1
E4
|
30 |13]
2
E,
|10 [ -52mm 11
K
K
2
L
1
2m 1| 1 + 2L
1
2m
2mm-111 112 +
V
Fi
(w
2
2-m-111
||
( 25
K
p²
g²
p²
2 L²
2
1|1 + ALB
2m
112 +
3
2m
||
K /²
K p
kp²
2
-
B
2m 2m -1 |1
V
f(
K
p
By Jensen's inequality,
Esn
[m2++1 [22++1]] S
Es
| - @2m+1
2m 2m + -
v (w 1)]l
=
K p
By Eqn. 110
T I P Plaa w---111
2LB +
(w 2m-11) 1)11
2T. 15 2m++1
s 2T.
V 2m 2m-1))
P
Re-organize, we have
2 2
21 2B²
Ess, 2m) Ss (
+
K 0²
2m
Kp
||
4LB
2m
2mm1111
||
| f(x 2m 2m-) ||
Kp
L
+
2LB + A | w 2m 1111) V
2 T.
2L
2m
2m-1
2 22m-111
P
K p
2L
L P
W
2m
2LB + P
V
V (TT22m1111 2)11
K
=
+
2 L
+ 21
L+P
2 L K p)
1
|| 2m
w 2m 2m-12
K Pz
11 Am
ALB
2LB +
2 T.
+2L
T P
B
11 ||
2m 2
V (w (mm2m
Kp2
P
P
P
p
u + Am
2B2
2LB +p
2 B
| ( 311
Kpp
K
Lemma 3.2 is proved.
Proof of Lemma 5.5
21

---

Published in Transactions on Machine Learning Research (07/2024)
Proof. Lemma 5.5
can be proved by combing Lemmas B.1 and B.2 where
C = C1 L,
1 1
-
(1, L, B.
pP - č
11
L, B,
K' k
1
-
K
1
LB
LB²
2B
2LB +p
2 B K p
(11)
p PPp
2p
Kp²
P
C2
C₂
L,
1 1
1 X
P
=O,(L,
1 1
1
1 p
)
11 p K
Ji
Am
K'
p
u Am
L'
+ L+N +
L(L + B)B
ALB
(AL'B
pLL(1 + +2B)
2
+
(12)
p2p
112
P
K
K
1 Am
Cs
C2 L,
1 1
-))=
P
L, =
1 11 1
)
P.
+ +Os(L,
1
p p² K' u
# Am
p
H Am
= ( p)2 p)2
2 L2
L P
2 -
( (-
2
+
+ 2L
)
(13)
2p²
K p
K p
(1 1 Am
D Proof of Theorem 5.6
This can be proved directed using Lemma 5.5 by averaging over all M odd iterations.
E Proof of Theorem 6.2
WLOG, consider the case when local device got updated in every iteration and the algorithm runs over 2M iterations in total. We will use the uppercase letters X and lowercase letters to denote random variables and the corresponding realizations, and use (x(() to denote its probability distribution. To simplify the notations, we will drop the index i as we are only concerned with one agent.
According to Abadi et al. (2016). for a mechanism M outputs o, with inputs and d, let random variable c(o; M, d, d) = loog Pr denote the privacy loss at and Pr( (o)
a (A) = max log Eo,. (exp) d))
d.d
For two neighboring datasets D and D' of agent i, by Lemma 6.1 the total privacy loss is only contributed by odd iterations. Thus, for any sequence of private (clipped) models @ generated by mechanisms {. M Im= over 2M iterations, there is:
Procam (30:2M (D)
c(20:2M, (AMM MMM "
D,D')
log
Prizu (20:2M DD)
P Pmama (302m+1 DD 0:22m)
Pa (w (D)
log
log Po (w50) DD)
m1 (w2m++1 |D', 00:2m]
M
Σ
c 2m Am 0:2m D, D')
m=0
22

---

Published in Transactions on Machine Learning Research (07/2024)
where @hxt = 10=)== and S2 is random variable whose realization is Wt. Since @ is randomly generated, which is independent of dataset, we have ao (00 = Po (D"))) Moreover, the following holds for any X:
log R 2a (exp(Ac((0:22))) 1. " m==1 D. D'))
log
E ar fexp A
c (m Mt 20:2m D, D')}
M
log E aam+ (exp(Ac((2mt)) (2+ A 0::2m D. D.D')}
(14)
Therefore, a a1.4ppm mm
(A) S Em am (A) also holds. First bound each individual a. (A).
Consider two neighboring datasets D and D'. Private (clipped) model @2m+1 is generated by mechanism 1. MI)DD) 2(w + TDi EdED 7dd) ((d)+t) +N with function ||n(-)lla S 7 and Gaussian noise ~~(00,0" Without loss of generality, let [dn) f(d,) Σrei and EEED 17(d) O. Then nn A' and A("(D) are distributed identically except for the first coordinate and the problem can reduced to mie-dimenioonal problem.
log Pamm 12 (022+t11D @0:2m))
c1 1m, 0:2m ,
Pr (@2m+ (D' (0:2m)
(x(
log P' (n -
2/ (2/m) + +))
where n + Toy EeED n(d) = 2m++1 Therefore,
am)()) log EN
(2N + +7)}
2|D
log
exp(-
1
(n
X >1D) b
)2) exp(
2DD (22 + A))
72
V2TO
202
-o
7'X(A+ 11)
202
M
Mr +
(A)
Σ
om
2|D
m=1
Use the tail bound [Theorem 2, Abadi et al. 2016)] for any & 2 202 the algorithm is (c, Jddiffernnnl
M+²
private for
Mr A(2 11
8 = min h(A)
min exp X:20
A:
2
To find X* argmin h(A), take derivative of h(X) and assign 0 gives the solution x =ID/30² X:A20
1 2 0, and
Mr2
(²( > 0, implies X = À. Plug into 15 gives:
6 = exp (4ppro 5) (
Mr²
DF 2)
Mr² 2
(15)
Similarly, for any 8 E [0, 1], the algorithm is (c, Jdiffferrnnt private for
= min 1z min Mr²(A+1) 1
Mr²
log 1 +
Mr²
log 8 2/
2A20 A:20
202
2|
8
2D
23

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Proof of Theorem 6.3
Proof. WLOG, consider the case when local device got updated in every iteration and the algorithm runs over 2M iteration in total.
We will use the uppercase letters X and lowercase letters x denote random variables and the corresponding realizations, and use (.) to denote its probability distribution. To simplify the notations, will drop the index i as are only concerned with one agent, and use w' to denote private output W
For two neighboring datasets D and DD' of agent i, by Lemma 6.1 the total privacy loss is only contributed by odd iterations. Thus, the ratio of joint probabilities (privacy loss) is given by:
Prenr (w0:2M
(wo(w01D)
M II m=0
Poam- (w lau 0:2m DD
(16)
Piraa (w0:2M Pao (1 (D))
Pr 2m 1:::2mm Di)
where Oit = fw= and Ω denotes random variable of wt. Since w is randomly generated, which is independent dataset. We have (wo(w"(D) = (w)
Consider the (2m 1) iteration, by first-order condition, we have:
n ( D) - plw ) = am
Given 0:2m, n and 2 will be bijective and the relation is captured by one-to-one mapping g Rd + Rd defined above. By Jacobian transformation we have
Pram+s (w (w 0:2m D) Pwm (g(w (m+1: (Ig(( :D))
Thercfore,
Paam+s (w2m+1 0:2m
(w2m+1/ww00mm D) Pn (g(w2m+1 D))
(J ( 2m D)))
Porm (w2m+1 1...2mm D') Pa ( D'))
ddet [ (g D()))
Let n²t == gmw22+11111 D), ne' mmw2m+11 D') be noise vectors that result in output w2m+1 under neighboring datasots DD and D' respoctively. WLOG, let di E D and d' E D' be the data pints two datasets that are different, and D \ D' dz. Because noise vector N exp(-o"" [In"))) have,
Pr (g(w2m+11:)) :)) P (g( ((22m+11, (()) S exp(a""|\n" m []) = exp((" VF, (w) 2m+1 - 2m
exp | IIVE dd) - di)ll) S exp (202)) u1
(17)
Jacobian matrix
J J(g( 2m = 22 Fi 2m+ D) - :ul. :=
(18)
Further define matrix
A = Jig 2mth ('i)) - -A 1 ( d - V2 (2 (w)2m+1 di))
D
Then
[det ( :D)))]
[dc)(A)
1
(1e(()(g(22m)) D())
dee((AA + A)]
|det(/ / + A AAA)
- (1 + (e(A-
24

---

Published in Transactions on Machine Learning Research (07 (274))
where A (A) denotes the k-th largest eigenvalue of matrix A Under generalized linear models, Aa has rank at most 2. Because PD/a I >e (A) S
[Di and μ4, u2, [D] satisly pDl s 0.5, we have,
(g( 2m D))) (g D())
exp( exp(-2In(1 u2 )) exp (2Suu |DIp
(19)
u2 Dlu
1D|p
where the last inequality holds because 1n(1 x) 1.4x,, Vo [0,0.5).
Combine Eqn.
16
19
and
17 have
Pre:aM 0.2M (D)
2a U1
2.8u2
II exp
Pr0 (w22 (D')
$
|D]
exp
|D|p
m=0
M
2a Th U1 + 2.8u2
=
exp
m=0
Theorem 6.2 is proved.
F Experiments
F.1 Details of Datasets
Table 2: Details of datasets. Numbers in parentheses represent the amount of test data. All of the numbers
round to integer.
Datasct
Samples # of device
Samples per device
mean
stdev
iid
6726(683)
30
224
166
0,0
13791
30
460
841
Syn
0.5,0.5
8036(818)
30
268
410
1,1
10493(1063
30
350
586
FEMNIST
16421(192))
50
328
273
Sent 40
#2299(8484)
52
621
105
Synthetic. The synthotic data is generated using the same method in Li ct al. 2020). We briefly descríbe the generating steps here. For each device k, y/s is computed from a softmax function y/s = (ggumaxsoffmaxxWW33 bx)). We and by are drawn from the same Gaussian distribution with mean ug and variance 1, where ug E (0; 3). Ig N(w;; E). us is drawn from Gaussian distribution with mean B& NN(,,)) and variance 1. Σ is diagonal with Σj.j= j-1.2 In such setting, 8 controls how many local models differ from cach other and controls how much local data at each device differs from that of other devices.
In our experiment, we take k = 30, E R20 W E 200200 b E R10 We generate datasets in total. They 're Syn(iid) Syn(0.0) with 3 3=0 and + = 0, Syn(0.5.0.5) with = 0.5 and y= 0.5 and Syn(1,1) with 8 = 1 and y = 1. In the output perturbation experiments, we set a 1.0 for the baseline methods and to for the Upcycled basclines, ensuring that the privacy budget for the basclines always greater than that for the Upcycled baselines (e.g., the baseline 0.773 and the Upcycled baseline 0.683 for Syn(id))). In the objective perturbation experiments, we set to 10 for the baselines and 20 for the Upcycled baselines to achieve similar levels of information leakago, while still maintaining that for the Upcycled basclines is less than for the others. This constraint: is maintained across all experiments.
FEMNIST: Similar with Li et al. 2020). we subsample 10 lower case characters ('a''j") from EMNIST Cohen ct al. (2017) and distribute classes to each device. There are 50 devices in total. The input 28x28 image. In the privacy experiments, o is set to 0.27 for the basclines and 0.2 for the Upeycled basclines, and a is set to 100 for the baselines and 200 for the Upcycled baselines, respectively.
25

---

Published in Transactions on Machine Learning Research (07/2024)
Sent140: A text sentiment analysis task tweets Go et al. (2009). The imput is sequence of length 25 and the output is the probabilities of 2 classes. Here, is set. to 0.27 for the baselines and 0.2 for the Upcycled baselines, and is set to 15 and 30 respectively.
A brief summary of dataset can be found in Table
F.2 Details of Algorithm FedProx
Here we present the detailed algorithm of FedProx:
Algorithm 2 FedProx (Li et al. 2020
1: Input: > 0, {Di)ez, w
2: for t= to do
3: The central server sends the current global model parameter w to all the clients.
A subset of clients get active and cach active client updates its local model by finding (approximate)
minimizer of local loss function:
++ arg min Fi(w; + " W112.
w
Each client sends its local model to server.
The central server updates the global model by aggregating all local models:
att #t Pie
end for
26

---

Published in Transactions on Machine Learning Research (07 (07/2024)
F.3 Convergence all datasets
Here present the convergence and accuracy of the lesting dataset in the final iteralion for all datasets under 90% straggler and 30% straggler scenarios.
F.3.1
90% Straggler
0.70
0.70
0.55
0
0.60
0.55
0.45
0.40
0.45
40
50
training time
training time
Upoycied UpoyciedFodky FodAug
FidProx
Upcycled eeette plecitt
Upcycled FodAvng
FedProx
Upcyded pFodMte
Feddug
Upcycis/Srwllll
redfing
Upsye Si-Scalllad
phedhte
Uscyced PesAlugM
Scaffols
Up
Scaffoid
FedMogl
Festugg
RudDyn
Fadhogi
FidAright
Upaye le FudDyn
Fedrogi
Usrye FeddPrs
FedDyn
Ureye ledefedProx
Featyn
(a) Syn(iid)
(b) Syn(0.0)
0.8
0.7
155
0.6
0.5
0.5
training time
training time
Uscycled Fodting
FedProx
Upcycles #FedMe predite
Upcycled Fodding
ResProx
Usoycics Footte
reeffig
ail-Scallold
heddvg
UpcycledSccuffod
phestle
Uneyc Feg
Scarfold
Uprycled-TedluggM
Scaffold
MedyciesFedrogg
Foddright
FodDyn
FodDyn
Festrogi
Useyo
FeelDyn
Upaycleds
Fedibyn
(c) (yn50.5)).5
(d) Syn(1.1)
2.2
0.70
10
2.0
50
0.65
1.9
0.50
1.8
1.6
60
80
100
120
140
10
20
30
40
50
60
70
80
training time
training time
Upayc
Upcycledpphatte
Ubeye eddFeuug
Upryc FodYog!
Utery wn-Feerugg Foddrught
FodAright
Upcyced FodDyn
Upcyc FodDyn
Fodrogg
Upoyc add"tddrrxx
hedbyn
Upeyc Jncycleddredtree Predtro
Pealiyn
(c) FEMNIST
(I) Sent140
Figure 5: Convergence of Upcycled-FL and regular FL methods with the approximate same training time under 90% Straggler.
27

---

Published in Transactions on Machine Learning Research (07 (07/202) /204)
F.3.2 30% Straggler
We also conduct an experiment with 30% straggler scenario to examine the convergence of our method.
Table 3 demonstrates that our conclusions remain valid even when the straggler rate is relatively low.
Table Average accuracy with 30% straggler on the testing dataset over four runs, the experimental setting
is
Table
Dataset
Method
Syn(iid)
Syn(0,0)
(0..0.5,)
Syn(1,1)
FEMNIST
Sent140
FedAvg
98.50
80.30
82.60+0.72
78.81
83.06+1.30
74.29
Fecycled-FedAvg
99.30
80.77 #1.09
83.0940.14
80.7442.71
84.41
75.18
FedAvgM
98.50 10.07
81.08 2233
82.89
80.64
81.60
74.61
Upcycled-FedAvgee
99.12
82.20
82.6840.16
80.43
82.31
74.16+2.84
FedProx
97.22
80.88
82.31
80.1312.76
81.57.11.46
74.23
Upcycled-FedProxx
98.24
81.5220.82
83.05
81.73
82.85
74.83
Scaffold
98.28
79.95
79.5440.72
72.27
76.85
75.76
Upcycled-Scaffold
99.52
79.46=1.62
81.83
73.3441.18
77.6942.39
77.01
FedDyn
98.17
82.06
80.97+1.01
78.6543.83
84.3940.95
75.88
Updycled-FedDyn
98.57 20.22
82.08
82.80+1.42
81.11
85.34422.7
75.90
pFedme
96.45
91.05
89.64
92.88 L0.67
76. 1.1.008
72.87
Ueeycled-pFedme
96.89
91.06
89.40+1..3
92.64+0.90
77.3643.59
73.48
Fed
99.38
81.06
80.65+1.32
79.14+1.00
79.98
77. 77.63
Uedycled-Fed ogi
99.60
81.77 22.06
81.72+1.02
80.32
81.96+44.28
77.78
28

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
F.3.3 30% Straggler
0.65
0.35
0.50
0.45
0.40
0.5
20
30
40
50
60
70
80
10
20
30
40
50
60
70
80
training time
training time
Uscyciesphiettt
Upcycled FodAugM
Scoffold
Upoyced FodYogl
Upcycled FodAuggM
Scaffold
Uscycled FodMogi
Upsyclesse wdbyn
Pedrogi
FedAugg
Upeyc wyy
FedDyn
Upcycied-FedProx
FedDyn
(a) (in(iid)
(b) Syn(0.0)
0.80
0.75
0.70
0.60
0.55
0.6
0.5
0.45
0.4
20
30
40
50
60
70
80
10
20
40
60
70
training time
training time
Uncycledd-wssagg
Upcydes
Fosting
Upcyced
Scaffold
Upcycled-rasAuuk
Scellold
upcychee-rrattp
FedAAug
UpryclessF edd
Fedrogl
FedAvgg
Upeyc endFeddyy
Fectlogl
Upcycied FooProx
RodDyn
Upcyclzd FooProx
FodDyn
(c) 5yn(0.5.0.5)
(d) Syn(1.1)
2.3
0.75
2.1
0.70
0.65
1.9
1.7
20
40
60
800
1000
120
140
1.0
20
30
40
50
60
70
B0
training time
training time
Uscycled FodAvg
ed shealiee
Upcycled Feddug
Upcycled FeaMte sheattle
FadAug
FedAug
SpcrciedSccuflld
Sraffoie
Uneye eddifeoogg
Abcycleo-Twethogk
Uncycieddeeete
RsgAugM
Usoyced FodDyn
Podtogi
PodAugM
Upoycied FodDyn
FodMogl
Upcycled FooProx
FodDyn
Upcycled FodProx
FodDyn
FEMNIST
(f) Sent140
Figure 6: Convergence of Upcycled-FF and regular methods with the approximate same training time under 30% Straggler.
29

---

Published in Transactions on Machine Learning Research (07 (07/2024)
F.4 Additional Privacy Experiments
In addition privacy experiments on synthetic datasets, also report the output perturbation and objective perturbation real-world datasets: FEMNIST and Sent140 in Figure and M Due to limited computational resources, conduct these experiments using subset of the previously established baselines.
23
2.3
2.0
18-
1.9
20
40
60
80
1000
120
140
10
20
30
40
50
60
70
80
iteration
iteration
Upcycled
Upcycled
Upcrdedd
FodProx
Scaffild FedDys
FedAig
Fed
Upcrdddd FedDyn
Fesyted-FessuggM FodAugM
Fedlught
Figure 7: Comparison of private Upcycled-FL and private FL methods using output perturbation (left) and objective perturbation (right) on FEMNIST.
0.70
0.70
0.88
0.68
0.56
0.80
0.64
0.62
0.00
0.56
0.50
0.54
20
30
40
60
70
80
10
20
30
50
60
70
iteration
iteration
Upsycledewethgg
Scallid Upcycled
Upcycled- Fweshog Fedivg
Scafloid
Feddwrg
FedFrox
UpcycledFeddryy
Scaffo
Scaffold
Figure 8: Comparison of private Upcycled-FL and private FL methods using output perturbation (left) and objective perturbation (right) on 140t
F.5
Experiments full-scale lowercase letter of FEMNIST
We conduct convergence experiment with full-scale lowercase letters (26 classes) from the FEMNIST datasot, as shown Table We also conduct privacy experiments comparing our method with FedProx, as shown
Figure g
30

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Table Average accuracy on the large-scale FEMNIST dataset
(loeras letters)
Method
30% straggler
90% straggler
FedAvg
90.90 + 4.55
88.50 + 5.07
Secycled-FedAAee
91.26 + 4.06
88.69 + 4.94
FedAvgM
91.02 + 4.47
89.13 + 4.35
Speycled-FedAvghy
91.05 + 4.36
89.28 + 4.05
FedProx
91.91 + 0.38
89.02 + 4.53
Upcycled-FedProx
92.08 + 0.72
89.44 + 4.30
Scaffold
89.69 + 3.92
89.11 + 3.74
Upcycled-Scaffold
89.77 + 4.01
89.72 + 3.90
FedDyn
92.88 + 0.30
91.42 + 0.24
Upcycled-FedDyn
93.56 + 0.30
92.64 + 0.37
pFedme
81.36 + 4.63
80.72 + 1.47
Upcycled-pFedme
85.62 + 1.43
85.14 + 0.93
FodYogi
87.64 + 1.05
85.61 + 0.56
Uedycled-FedYYol
88.89 + 1.84
86.48 + 1.30
Table 5: Training time for output perturbation experiments Syn(iid).
Time/s
FedAvg
FedAvgM
FedProx
Scaffold
FedDyn
pFedme
FedYogi
Baseline
147.50 + 6.69
147.47 + 7.49
139.91
10.81
153.88 + 12.70
181.49
17.60
467.42
12.87
153.53 13.72
Upeyeled
86.11 + 9.23
81.95 3.39
80.59 = 3.29
95.09 13.89
99.82 = 3.32
259.54 18.27
92.82
UpePcled-FedProx
2.3
Upeyded-FedProx FedProx
FedProx
2.2
2.1
Incs
2.0
2.0
1.8-
17
20
50
100
120
140
20
40
50
100
120
140
iteration
iter on
Figure 9: Comparison private Upcycled-FedPret and private FedProx using output perturbation (lcft) and objective perturbation (right).
F.6
Training Time
We report the average training time to compare the communication cost in Table
31


Reviews:
[{"review_id": "LW9h16tzco", "reviewer": "Reviewer_2WzD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The paper is easy to follow and the proposed method is simple.\n2. The experimental results show the proposed method is effective.\n\nCons:\n1. The proposed updates is unclear to me in the cases that if the client is selected in even round but won't be selected in odd round. Will the model be updated if the client is not selected? \n2.  I am not an expert on the differential privacy field. However, I believe the information leakage won't be reduced by simply half if only half of the updates need communication. If the assumption is true, the best strategy would be use at least as possible synchronization and the proposed method could be quickly adapted into using only 1/3, 1/4, ....  \n3.  The experiments results in Figure 2,3,4 seems weird. I could get the proposed method would be better in terms of training-time however  it could achieve a better rate in terms of iterations. The proposed method uses a less information but achieve a better convergence rate which does not make sense to me.\n4. The experiments on the heterogeneous data distribution is not enough. The paper only uses synthetic data to simulate the heterogenous data distribution case. However, it would be more convincing if it could be done in the real-world data and it is also adopted by a lot of other federated learning methods to show their effectiveness. Partitioning the data with the dirichlet distribution would be a good way and the hyperparameter in the dirichlet distribution could be utilized to control the level of heterogeneity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new federated training method to reduce the communication cost and information leakage. Specifically, the paper proposes to only transfer the updates and merge on the odd iterations and uses the local model to do the update on the even iterations. The paper uses FedProx as an example to derive the upcycled version. The theoretical analysis are conduct to show the convergence rate of the proposed method and also briefly cover the privacy guarantee if differential private updates are utilized. The experimental results show the proposed upcycled FL could achieve a better convergence in both synthetic data and real-world data.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Have a more thorough and formal discussion about the information leakage problem.\n2. Explain why the half information is the sweet point for the update but not with fewer synchronization iteration.\n3. Experiments on real-world data with dirichlet distribution.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Tc2LiWpaVH", "reviewer": "Reviewer_QNCJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. the paper proposes a simple method that seems to work well, with clear motivation and explanation.\n2. The algorithm is supported with convergence guarantees and privacy analysis.\n3. The method is compared with a lot of baseline FL algorithms. \n\nWeaknesses:\n1. Only two examples are provided in Section 4 (FedAvg and FedProx). The authors should add a general modification description of FL methods. \n2. The method could be more general. Instead of only even/odd alternation, can we think about more general update rules? For example, we can change the frequency to 3 or more (i.e., communicate every 3 updates).\n3. Line 6 of Algorithm 1 seems like a momentum mechanism or extrapolation. The authors may want to explain the connection to existing optimization theory on this.\n4. Assumptions 5.2, 5.4 are standard but may not be practical. Could the authors explain how they are satisfied in your experiments?\n5. In addition to the convergence and privacy analysis, I think communication cost is another important factor. There should be some analysis on the communication.\n6. The main privacy results are in Appendix B, which I think are important and should be discussed in the main text.\n7. The main experiment datasets are either synthetic or small. The authors should try larger scale datasets for federated learning.\n8. The improvement after adding Upcycle seems a bit minor. This shows that Upcycle-FL may not be very effective.\n9. Missing baseline for FedYogi (https://arxiv.org/abs/2003.00295).\n10. Missing a table comparing the communication cost although partially reflected in Table 1.\n11. Privacy experiments are only done on synthetic datasets. What about standard datasets like FEMNIST and Sent140?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes Upcycled-FL, a simple yet effective method to save the communication cost and information leakage. The main idea is to reduce the communication rounds by updating the even rounds with previous updates from first-order expansion. The main method is provided with convergence analysis, privacy guarantees and comparison with multiple baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "I don't have broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "N7m0GiHPLU", "reviewer": "Reviewer_4RHt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The improvement is achieved with a simple technique and can be applied to general FL algorithms.\n\nWeakness: There is a lack of experiments on various dataset and the improvement achieved by the proposed technique is not significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a Federated Learning (FL) strategy to minimize information leakage. It achieves this by accessing data only in odd rounds, while for even rounds, it updates the model by applying a first-order approximation based on the previous rounds’ model.\nThe proposed technique looks simple but effective.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are a few comments.\n\n1. Predicting the next update by ‘upcycling information’ may be less accurate as the data held by each client is non-iid. However, the experimental results seem to show that, on the contrary, there is further improvement. Could you explain me the reason why that is? \n\n2. 30% of devices are selected in each iteration. Does the proposed technique still show better results even when fewer devices are selected? \n\n3. Why upcycle only in even iteration? Isn't it possible to do it at different intervals, like 3 times or 4 times? How would accuracy or convergence change in that case?\n\n4. Figures are too difficult to recognize. Please think about ways to presenst the experiment results more clearly.\n\n5. \"More rlated work is discussed in Appendix 2\" in page 2, but thre is no Appendix 2.", "broader_impact_concerns": "There is no concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the paper, I noticed some minor points of improvement I will list below:
- typo: "datatsets"
- I wonder if the $\approx$ in eq. (5) should be $=$? Or if it truly is an approximation, it should be made clear where it comes from.
- "selected clients got updated", I guess missing "which"?
- "we apply our Upcycled-FL method to six" I guess it's "seven" now
- "Femnist" >> "FEMNIST", caption of table 1
- Privacy guarantees need to be clearly communicated in Fig. 4. I would also suggest mentioning that the training is non-private in Table 1 and Fig. 2
- Report, what is the $\pm$ reported in Table 1. Similarly what are the errorbars depicting in Figs. 2, 3 and 4.
Decision: Accept (poster)