Personalized Decentralized Bilevel Optimization over Stochastic and Directed Networks
Authors: Naoyuki Terashita
Satoshi Hara
Venue: Submitted to ICLR 2023 (2023)
Keywords: decentralized stochastic gradient descent: bilevel optimization: hyper-gradient: personalization: directed network: federated learning: distributed learning: fully-decentralized

Abstract: While personalization in distributed learning has been extensively studied, existing approaches employ dedicated algorithms to optimize their specific type of parameters (e.g., client clusters or model interpolation weights), making it difficult to simultaneously optimize different types of parameters to yield better performance.
Moreover, their algorithms require centralized or static undirected communication networks, which can be vulnerable to center-point failures or deadlocks.
This study proposes optimizing various types of parameters using a single algorithm that runs on more practical communication environments.
First, we propose a gradient-based bilevel optimization that reduces most personalization approaches to the optimization of client-wise hyperparameters.
Second, we propose a decentralized algorithm to estimate gradients with respect to the hyperparameters, which can run even on stochastic and directed communication networks.
Our empirical results demonstrated that the gradient-based bilevel optimization enabled combining existing personalization approaches which led to state-of-the-art performance, confirming it can perform on multiple simulated communication environments including a stochastic and directed network.

Under review as a conference paper at ICLR 2023
PERSONALIZED DECENTRALIZED BILEVEL OPTIMIZA- TION OVER STOCHASTIC AND DIRECTED NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
While personalization in distributed learning has been extensively studied, existing approaches employ dedicated algorithms to optimize their specific type of param- eters (c.g.. client clusters or model interpolation weights), making it difficult simultaneously optimize different types of parameters to yield better performance. Moreover, their algorithms require centralized or static undirected communication networks, which can be vulnerable to center-poin poiter-pointtee failures or deadlocks. This study proposes optimizing various types of parameters using a single algorithm that runs more practical communication environments. First, we propose gradient-based bilevel optimization that reduces most personalization approaches to the optimiza- tion of client- hyperparameters. Second, propose decentralized algorithm to estimate gradients with respect to the hyperparameters, which can run even on stochastic and directed communication networks. Our empirical results demon- strated that the gradient-bare personalization approaches which led state-of-the-art performance, confirming it can perform on multiple simulated communication environments including a stochastic and directed network.
bilevel optimization enabled combining existing
INTRODUCTION
In distributed learning, providing personally tuned models to clients, or personalization, has shown to be effective when the clients' data are heterogeneously distributed (Tan et al. 2022).
While various approaches have been proposed, they are dedicated optimizing specific types of parameters for personalization. A typical example is clustering- based personalization (Sattler et al.) 2020), which employs similarity-based clustering specifically for seeking client clusters. Another approach called model interpolation (Mansour et al., 2020 Deng et al., 2020) also specializes in optimizing interpolation weights between local and global models. These dedicated algorithms prevent developers from combining different personalization methods achieve better performance.
Another limitation of previous personalization algorithms is that they can run only on centralized or static undirected networks. Most approaches for federated learning (Smith et al. 2017 Sattler et al.) 2020; Diang et al. 2019) require centralized settings which a host server can communicate with any client. Although few studies (Lu al. 2022 Marfoq et al. (202I) consider fully-decentralizeed settings, they assume that the communication edge between any clients is static and undirected (i.e., synchronized). These commutation networks are known be vulnerable to practical issues, such as bottlenecks or central point failures on the host servers (Asrran et al. 2019), or failing nodes and deadlocks on the static undirected networks (Tsianos al.] 2012).
This study proposes optimizing various parameters for personalization using a single algorithm while allowing more practical communication environments. First, we propose gradient- Personalized Decentralized Bilevel Optimization (PDBO), which reduces many personalization approaches to the optimization of hyperparameters possessed by each client. Second, we propose Hyper-gradient Push (HGP) that allows any client to solve PDBO by estimating the gradient with (ooper-gradient) via stochastic and directed communications, that are
respect to its hyperparameters immune to the practical problems of centralized static undirected communications (Assran et al.) 2019). We also introduce a auriance-reduced HGP to avoid estimation variance, which is particularly effective when communications are stochastic, providing its theoretical error bound.

---

Under review as a conference paper at ICLR 2023
We empirically demonstrated that the generality of our gradient-based PDBO enabled combining existing personalization approaches which led to state-of-the of-the-rt performance a distributed classifi- cation task. We also demonstrated that the gradient-based PDBO succeeded in the personalization multiple simulated communication environments including a stochastic and directed network.
Our contributions are summarized follows:
We propose a gradient- based PDBO that can solve existing personalization problems and their combinations its special cases.
We propose a decentralized hyper-gradient estimation algorithm called HGP which can run even on stochastic and directed networks. We also propose variance-reduced HGP, which is particularly effective in stochastic communications, and provide its theoretical error bound.
We empirically validated the advantages of the gradient-based PDBO with HGP; it enabled solving a combination of different personalization problems which led to state-of-the performance, and it performed on different communication environments including a stochastic directed network.
Notation (A)s denotes the matrix at the i-th row and j-th column block of the matrix A, and (a); denotes the i-th block vector of the vector a. For a function f TRdd + Rdd, we denote its total and TR by dgf (a)) E RRdixdd and 0z. (a:) Rd. xd2, respectively. We denote the product of matrices by II. A (+) A (m)... ( and II. A
partial derivatives with respect to vector
PRELIMINARIES
We formulate distributed learning (Li et al. 2014), communication networks, and stochastic gradient push (Nedić & Olshevsky 2016 SGP) as a generalization of gradient-based distributed learning.
Distributed learning
Distributed learning with n clients is commonly formulated for all i E [n] as
x
arg min
Σ kE(m)
Esg [ff Aei Ex))
s.t. x; Zÿ. Vj [n].
π
where, the i-th client pursues the optimal parameter x. E TR that makes consensus (æ; = xy Vj [n]) over all the clients, while minimizing its cost fi RR x Rd + for the input & X sampled from its local data distribution. We allow fi to take the hyperparameters X E Rd as its argument. We further explain the examples of the choice of X; in Sections 3 and
Stochastic and directed communication network In distributed learning, clients solve Eq. by exchanging messages over physical communication network. The type of edge connections categorizes the communication network: static undirected (Lian et al., 2017). which represents syn- chronization over all clients; stochastic undirected (Lian et al. 2018), which represents asynchronicity between different client pairs; and stochastic directed (Nedić & Olshevsky 2016), which represents push communication where any message passing can be unidirectional.
This study considers distributed learning on stochastic and directed communication networks. Such a network has several desirable properties: robustness to failing clients and deadlocks (Tsianos eet al. 2012), immunity to central failures, and small communication overhead (Assran et al. 2019). We model stochastic directed networks by letting communication edges be randomly realized, as simulated in Assran et al. (2019) and Nedić & Olshevsky 2016). Let o!.) E {0, 1] be random variable where ((0) 1 denotes that there is communication channel from the i-th client to the j-th client the time step t. and ( 0 otherwise. We set 6542 1 for all i [n] and t E N allowing every client to send message to itself at any time step. Note that the edge model above can recover the other fully-decentralizedd settings as its special cases; the symmetric edges (5(5) s/0,, Vi,j E [n], Vt N) recover stochastic undirected networks, and the symmetric constant edges, which additionally require (!2) 5 ő.j, recover static and undirected networks.
Stochastic gradient push (SGP) SGP Nedic & Olshevsky 2016) is one of the most general solvers of Fq. (T). This section formulates SGP with further generalization for its variants.
2

---

Under review as a conference paper at ICLR 2023
The i-th client in SGP updates its weight Wi IR along with biased parameter 2; E Rd obtain its debiased parameter 2; zi/Wg. Let y: = [z] wi] E R' be a concatenated vector. At the t-th step, the i-th client samples its minibatch c and sending edges o( 18 6 runs runs local update 4b 14 + Rd and message generator Pi R& + Edd, and updates y, as )
(1+1) = Σ P)((o))))))
V 9 }j ()) + ab; vv X. ()
(0)
Vi
(2)
JEGN
8.L. ExE(n) (m.
and Pik (o 5: i. Pik (6! ) wk [m],
where, Pjt : {0, 13" + [0, 1] is a weight function that forms column stochastic matrix p(t) such that
P )) to ensure the convergence of a; to the consensus. Denoting the learning rate by a, E RR. the following formulations of ip; and 2/; recover the two SGP variants:
9. (y Ro, (i) [z] [.l ESEs, Om. f( xx: x
wi)
th (y: Ai Ct)
Oaz o]
(4a)
2,_ wT]. 4/s (a:; A. G) [c. Eeec. Ji E) 0]
(yi; >o Ci)
(4b)
where Eq. (4a) and Eq. (4b) run local gradient descent with a minibatch before (Assran et al. 2019)
and after (Nedić & Olshevsky 2016) communication, respectively.
We can recover other popular distributed learning schemes as special cases of SGP. By making
(o form doubly stochastic mixing matrix p(t), Eg. (a) and Eq. 4b recover the decentralized
stochastic gradient descent (DSGD) in Bianchi et al. (013)) and Lian et al. (0117) respectively.
We can also recover FedAVG (McMahan et al. 2017 by choosing fully-connected graph with
averaging over all clients, i.c., 6. = 1 and pij (6, 1/n for all i, E [n] and E N in Eq. (4a
PERSONALIZED DECENTRALIZED BILEVEL OPTIMIZATION (PDBO)
We then propose the formulation of PDBO as generalization of existing personalization problems. PDBO played by n clients is formulated as follows:
min
Σ Fx (AI....,,A,, A.) . A,), s.t. of satisfies Eq. Vi e [n].
(5)
=E(m
where the outer-problem (Eq. (Heft)) lets the i-th client find its optimal hyperparameter X; that minimizes the average of outer-cost F; Rd x Rda + R across all clients. Here, we write of (Ai..... An) ) to show its dependency to hyperparameters explicitly. The generality of Eq. (5) in personalization comes from the flexibility in the choice of fú, Fi, æ,, and X For example, suppose that f; is the cross-entropy loss of a DNN with a feature extractor and classifier parameterized by a;; and A; respectively. By letting F; be validation loss,
recover family of personalized layer scheme (Arivazhagan et al. 2019 Bui et al. 2019). See Section for further examples.
We then reformulate PDBO by replacing Eq. ① with the stationary point of an iteration as in Grazzi et al. (2020). Following the original works of SGP (Nedić & Olshevsky 2014) and the push-sum (Bénézit al. 2010), introduce additional assumptions:
Assumption 1. For every E [ni]. and for all X; E T& and & X, fa A,AA; G.) is strongly convex. Assumption 2. A graph with edge set {(1,) Es, [p.y (8.)] > 0, i,j E [n]} is strongly connected.
For every i E [n]. the expectation of iteration Eq. with Assumptions and 2 admits the following unique stationary point which gives the optimum of Eq. I (edic & Olshevsky 2014 Assran & Rabbat 2020
Let 8 = {ōi.... Jn). < (CI....,
y Es,c Σj=Ph (5,) sp (y Aj () + 1/: A)) [ wf]T s.t. at 2//wf, (6)
Replacing the inner-problem Eq. (5) by Eq. (6) reformulates PDBO as min (x" (y² (A)) A) s.t. Eq. (6) is satisfied for all E [n].
where, A A AT x= [ concatenated parameters, and (x, A) :
x TIT and y (A)
M T
yn TJT
are
Eeenn [1% (Ix Ax)] is the average outer-cost.
"This is a mathematical equivalence; FedAVG runs on a centralized network in practice.
3

---

and Under review as a conference paper at ICLR 2023
4
ESTIMATION OVER STOCHASTIC AND DIRECTED COMMUNICATION NETWORKS
To solve PDBO using gradient-based methods, this section introduces an empirical estimate of the hyper-gradient and its decentralized computation algorithm, which we named HGP.
4.1 EMPIRICAL ESTIMATE VIA APPROXIMATE IMPLICIT DIFFERENTIATION
Below, we derive the estimator of hyper-gradient following the recurrent backpropagation for approx- imate implicit differentiation (Grazzi et al., 2020: Lorraine et al. 2020). The hyper-gradient with
respect to À is written as Fx (æ" (y" (A)) X) under Assumption 3
F(
Assumption 3. For all E [n]] and Çi Pi (y:: X, G)) and th: (y:: X, (i) are differentiable with respect to y, and X, and F; (I:, 2;) is differentiable with respect to æ; and X
Estimator of hyper-gradient We introduce Jacobian matrices A (6, <) and (6, () whose (i i) blocks are the partial derivative of Eq. 2 with respect to yj and Xy for j, E [nt], respectively:
(A (6, (),; = Pji (6,) og si (u): (. + 1 2b (y): Aj. (y) RRdydd,
(8a)
(B (6, {)) P.i (6,) 0x, P, (Dj: () + + 1 by (y)i Aj. {i) Rddxdd
(8b)
where, 1;y denotes the Kronecker delta. We introduce their expectations by A == Es,cl |A (6. ())
B = -Es,c [ (6, c)] assuming the following:
Assumption 4. The largest singular value of A is strictly smaller than one.
Let cº = F (x* (y" (A)), A) and e OxF (x" (y" (A)) A). Using Assumption 4 Eq. (6) and
empirical estimates (A B(0) (A (0())(())) B (8tt) (())) we obtain the estimator
M-1
1
F2F (x" (y' (A)) A) = B
Σ m==
A ~ + c ~
Σ (2m)
II 8=0
A (2m+1) 1) cd + c² =: F.F. (9)
m==0
where, the first approximation is obtained from Grazzi et al. (2020) (Eq. (4), (5), (19)) and the
second approximation simply replaces the expected Jacobians with their estimates, as in Ghadimi & WWan 2018, 3.62, 3.66). We estimate Jacobians in the odd- and even-rounds introducing the
following assumption ensure unbiasedness: B M Am E MDM (2m)) I A (2m+1))
We include the complete derivation of the estimator in Appendix
Assumption 5. glt) and ((9) are independent across the time steps E N.
Recurrent backpropagation We compute Eq. (9) using the fact that finite number of recurrent
backpropagation around the stationary point approximates the hyper-gradient (Lorraine et al. 2020 4.2), which avoids the explicit computation of Jacobian matrices, A (m) and B(m), Let u mm)
Im À (2m+1)) cM and (mm) = -m>= =0=0 B(2m') (m())) + c². By initializing ( + c² and (0)) t-
and by the following iterations for m = O,...,M ...
(m++)) t- (2m) (m)) + x(m) (m+1) x- A (2m+1)
(10)
we obtain the hyper-gradient estimate as d + (M), Eq. 10) only requires Jacobian-vector products (2m) (m)) and Á (2m-1) (mn) leading O (ndæ + rıd)) and O (ndzz) in time, respectively.
Decentralizing backpropagation Decentralized computation of Eq. 100) requires consideration of the data locality and the communication stochasticity. From the locality of c!(T) clients need to communicate because only the i-th client can compute Jacobian-vector products of the i-th row block of A (m) and (m) from their definitions Eq. (8) Moreover, we need to design a decentralized algorithm so that any required communication can be performed stochastic and directed networks.
4

---

Under review as a conference paper at ICLR 2023
4.2
PUSH (HGP)
We propose HGP which enables any i-th client update their hyperparameter X; by estimating its hyper-gradient dx, F = (dxP), over stochastic directed networks. HGP runs an unbiased alternative of Eq. 10) based our observation that the exact computation of Eq. (TO) requires undirected edges.
Exact backpropagation requires undirected edges Suppose the i-th client is responsible for computing the i-th block of ((m+1) and w(m++1) denoted by u (m++)) E R and u o(m+1) R
respectively. From Eq. (10), we obtain the following recursive iteration performed by the i-th client:
(m++1) x Σ/=1 6/2gm)
B (B(2m)
(m)
(m))
vi
21
of
(11)
- -i 6:0g u
(m++1)
6(2m+1)
(2m+1)
(m)
u
where, we use the equivalencies (A (mm))s
6/mm) (m))
(A
kg and (
6,-5 (B(m)))s >ag, as they
(m))
are non-zeros only when 6/-7)) from Eq.
( and Eq. (3 To complete Eq. (11. the i-th client
needs to receive u (m) from all the j-th client with 6(m))
which possible only when there is
of 0/T)) 1). In other words, the exact computation of
the communication channel from j to (i.e., Eq. is available only when the communications are undirected (i.e., ((u?)) 5fm) Am E N).
Unbiased estimation via directed edges To relax the undirected communication constraint to stochastic directed communication, we propose HGP as simple yet effective alternative of Eq. (TT).
We first assumes that the i-th client knows the receiving frequency 8y.; = H3 [j.]] and expected sending weight Pij Es, Jpg (6.) for all j E [n]. In practice, we can estimate them through T rounds of SGP communication. We also adopt the following assumptions:
Assumption 6. If fgzz 0, then 8,.g and vice versa.
Assumption 7. The realization of o. are independent over different j and i for all m E N.
The key idea of HGP is to replace the sending edges ((m) in Eq. with the debiased receiving edges
6/m) /8,.. By initializing u!! + (c") a, F. (zf >,) and v < (c>); = 100, F, (z) A.). we obtain the estimate as dx, F - v. (M) after the following iterations for ..... M 1,
(m+1)
(mm) 8y.i
B B(2m)
u mm/))
+ v (m)
j=l
(12)
(m+1)
8 2m++1)
(22m+)) u (m)
u
==
83-1
where, (A(m)) and (B(m)) are defined by replacing Pij (6. in Eq. (8ap and Eq. (8b) with Poj. respectively. The iterations above are always computable even on stochastic directed networks because the i-th client needs to receive u.)" from the clients with ofm! 1, which is always possible. We also note that Assumption 6 ensures that (A(m)) and (B(m)) i unbiased: Es (6 /8, (A (A(m)) Bs(ofm))8 /8..) [Esc
Es
[n (A)as and the same for B(m).
HGP enjoys the same complexity as SGP in both communication and computation. HGP exchanges only u. having O (dy) in communication. In practical cases where dx < dy. the Jacobian-vector products (B u and
are computed in O (dy) time.
Variance reduction We now introduce the variance-reduced version of HGP, which we call VR- HGP. The naive HGP above suffers from large variance because of 65mh /5,.., which can take a value far larger than when 8y-; small. The multiplication of such values induces high variance.
5

---

Under review as a conference paper at ICLR 2023
The idea of VR-HGP is to combine HGP with its following variant, where wi (0)
(c9)
8 8(2m)
(m+1)
-ij=1
(
W
(m)
(13)
(m+1)
- 03.
(2m+++)
w (m) + (c*)
Here, w(m) corresponds to the estimator of Σ m0==0 Am c² Note that the weighted average of two different estimators results in an estimator with a smaller variance. By averaging Eq. (12) and Eq. (33
with weights a, B E (0, 1), we obtain VR-HGP the following iterations for m -,..., M
(m+1) vi
t
Ui + -,
(m)
g(mm)
((2m)
(m) "
)
+ (1 -a) (Σ:
fis 8y.1
((2m)
B
w w
83-
is
(m++1)
gl2m+1)
À
(2m+11)
(m)
u,
(m+1)
t 3
Σ
g(mm+)))
jq
(2m+1)
w (m)
+ (c2)):
+ (1 (8) (00)m))
(m)
+ u (m+
85.
(c ). and w (c"), having the estimate as dx F + v (M)) + (c>)):
with vi < Odz uz
The following theorem provides the estimation error of the hyper-gradien using VR-HGP. Assumption 8. 37A E (0. 1), 7B E oo) such that Vy, As. Ça and Vi.
max {100g 3b 21 | ( = 7/
1B
max (1,0), 11. pillet
(14)
2x'
2x'
where K.
Eis
Pai and ||-112 denotes spectral norm. b6,
| g hold true and </(mm)
Theorem (Estimation Error of VR-HGP). Suppose that Assumptions
14 (2m+1). 1)
= b for any i and m. Then, for a, (0, 1), with probability at least -,, we have
JR. F FxF (xx" 2) S HO,ST
Σ
P
+
4n b
log
nidy + dx) + e -000)
82
e
2,
where, ||||| denotes f2 norm, e O(M) denotes the exponentially diminishing term over M, and
Ha. V 8 1-a a
I+a 1+
1 a(1 3 Bma) 1 a(1 -3 + BBA) 1 - (1 B 3TA)2
32n
7 ||
T
x(1 7A)
One can see that the coefficient Pa,3 dominates the magnitude of the estimation error. Setting a, B E 10 that minimizes Ma,s can attain small error The proof is provided in Appendix C
5 RELATED WORK
Personalization in federated learning We compare our work to standard personalization methods by recovering them as special cases of PDBO and pointing their applicable communication networks.
Mansour et al. (2200) and Deng et al. 2020 propose model interpolation that provides personalized models as the optimal interpolation between local models and the global model, which is recovered by letting the inner- inner- problem train the global model and the outer antereproblem optimize the interpolation weight. Federated multi-tast learning (MTL.) (Marfoq et al., 202T) obtains personalized models by allowing clients to tune the ensemble weights of the global preeeprrdsssors. In Section 6 we demonstrated that PDBO can recover the federated MTL by letting the inner-problent optimize the base-predictos and the outer-problem learn ensemble weights. We see the clustering personaliza- tion (Sattler et al. 2020) as a sub-problem federated MTL from the empirical results (Marloq et al.
2 Althoough setting = 1 makes Ha.8 = 0. the remaining error is no longer -O(M) in that case. This observation implies that slightly smaller than is preferred. A similar analysis also shows that / slightly larger than 0 is preferred. Our empirical results show that (a, 9) = (0.9, 0.1) performs well (Appendix C.6).

---

Under review as a conference paper at ICLR 2023
2021 J.4) that demonstrated the personalized ensemble weights recover the client clusters. Data augmentation (Duan et al. 2019 Zhao et al. 2018) mitigates data heterogeneity by over- or under- sampling to train generalized global model. This can be recovered by optimizing pseudo-sampling rates as hyperparameters. Furthermore, the generality of PDBO allows us to optimize different types of parameters simultaneously, which current personalization algorithms cannot handle.
For communication networks, most personalization schemes require a centralized network (Sattler al. 2020; Jiang et al. 2019), which is vulnerable central point of failure (Assran al. 2019). A few fully-decentralized algorithms (Marfoq et al. 2021 Lu et al., 2022) assume static undirected networks which are vulnerable failing clients and deadlocks (Tsianos et al., 2012). While Vanhaesebrouck et al. (2017) and ZZnneddschi et al. (2020) consider stochastic undirected settings, their applicability are limited to linear models or a linear combination of pre-trained models. Gradient-basse PDBO can learn more complex models and run on stochastic directed networks, which are immune to practical problems in centralized and static undirected networks.
Distributed bilevel optimization Distributed bilevel optimizations proposed in concurrent works differ from PDBO in formulations. We categorize them into consensus distributed bilevel optimization
(CDBO) (Chen et al. 2022 Tarzanagh et al. 2022 Gao et al. 2022 Yang et al. 2022 and CDBO
with the local inner-problem (CDBO-Local) (Li et al. 2022
Liu et al. 2022 Lu et al. 2022).
CDBO requires clients to make consensus both on the outer- and inner- mror-epro Chen et al. (2022) ;
Tarzanagh et al.] (2022); Gao et al. (2022); Yang et al. (2022) applied CDBO to hyperparameter
optimization, such as L2 regularization rates, While PDBO and CDBO are different tasks, both require
estimation over communications. which we discuss in the next paragraph. CDBO-Local (Lu et al.
2022) requires consensus in the outer-problee as in CDBO, whereas its inner-problem is a local optimization. Clients in CDBO-Local thus cannot benefit from others in the inner-loop for better generalization. In our PDBO, both outer- and inner- mmer-prrbllms optimized using global information; the inner-parameters are trained for consensus, and the outer-parameters are optimized to improve the total performance across all clients.
We highlight that our gradient-based PDBO recovers CDBO by running SGP using the estimated hyper-gradien for the outer- proobep,, and recovers CDBO-Local by using SGP for the outer-problem and designing Pij to form the self-loop topology in the inner SGP.
Hyper-gradient estimation over communication Networks We compare our HGP with the other hyper-gradient estimation methods performed over communication networks.
Yang al. 2022) proposes hyper-gradient estimation algorithm in fully-decentralizeed settings. However, they assume static and undirected networks, and their algorithm is complex both in computation and communication as they involve computations and communications of full Jacobians and Hessians. Tarzanagh et al. (2022) considers the hyper-gradien estimation in centralized settings, which is typical in federated learning. While their approach is advantageous in complexity because clients only compute Jacobian-vector products and exchange O (d.z) vectors, its applicability is tied to the centralized host-clients setting. Other CDBO methods (Chen et al. [0022] Gao et al. 2022) estimate different types of hyper-gradient See Appendix P for further details.
Our HGP enjoys reasonable complexity in computation and communication, as stated in Section 4.2 and covers wide range of communication networks, including stochastic and directed networks.
Hyper-gradient estimation for single agent The hyper-gradien estimation approaches are cate- gorized into iterative differentiation (ITD), and approximate implicit differentiation with recurrent backpropagation (AID-RB) and conjugated gradient (AID-CG) (Grazzi et al. 2020). We found that applying ITD or AID-CG to the hyper-gradien estimation stochastic and directed communication networks is infeasible for the following reasons.
Applying the ITD variants, backward and forward mode (Franceschi et al. 2017). have limitations in communication; the backward mode requires static and undirected network, the forward mode requires all-to-all communication at the end of iteration and exchanging large O (dy x dx) sized matrices. A detailed discussion is provided in Appendix H To apply AID-CG (Pedregosa) 2016), need to solve min gv " I A)q ex 12. However, in setting where I A can be
7

---

Under review as a conference paper at ICLR 2023
asymmetrie, AID-CG is slower than AID-RB (Grazi al. 2020). AID-RB only requires the network to be undirected and our HGP relaxes this limitation by simple and effective modification.
EXPERIMENTS
To demonstrate the generality in personalization and applicability practical communication envi- ronments, we introduced three different personalization approaches as special cases of gradient-base PDBO and benchmarked them with baselines on four different communication networks.
6.1 SETTINGS
We followed the settings of EMNIST classification played by n = 100 clients in Marfoq et al. (0021)
unless otherwise mentioned. The detailed experimental settings are described in Appendix
Communication networks We simulated four communication networks: fully-connected (FC),
static undirected (FixU), stochastic undirected (StoU), and stochastic directed (StoD).
FC allows clients to communicate with all the others any time step, i.e. 6/4 for all i,j [n] and / E N. Fi FixU is static undirected network simulated by binomial Erdós-Rényí graph (Erdos Rényi] 1959) with parameter p = 0.4 adding the self-loop edges. Following the setting in Marfoq et al. [22T), we generated doubly stochastic mixing matrix using the fast-mixing Markov chain (Boyd et al. 2003) rule. StoU simulates stochastic undirected network by letting undirected (4)
edge j-4 (-j independently realize each step with the probability J5.; E [o, 1]. In StoD, every direction of edges 6fth is independently sampled at probability 5j... simulating a stochastic directed network. For all i E [n], òz-2 was sampled from the uniform distribution with [0.4, 0.8).
Proposed approaches We introduce and evaluated three different personalization methods as special cases of PDBO, that are, PDBO-DA, PDBO-MTL, and PDBO-MTL&DDA
PDBO-DA optimizes the pseudo-sampling rates to recover the duta-augmentttion based personaliza- tion (Duan et al. 2019 Zhao et al., 2018). PDBO-DA optimizes X, RC to obtain the label-wise weight vector CSoftmax (A,) E [0, CT In the inner- mnuer-problem, the losses of the instances labeled as c E [C] are multiplied by the e-th element of the weight vector. PDBO-MTL is obtained by formulating FedEM (Marfoq et al.) 2021) as PDBO. PDBO-MTL lets each client train ensemble classifier that outputs weighted average predictions across K = of CNNs. PDBO-MTL trains the CNN parameters the inner-problem and optimizes the hyperparameters A E R to obtain the ensemble weight vector Sof tmax (Ax) E [0, 1j* PDBO-MTI&DD combines PDBO-DA and PDBO-MTL by optimizing X, E RC+K to obtain both the label weight and ensemble weight vectors.
Baseline approaches We compared approaches with baselines on each communication setting. For FC and FixU settings, we compared several personalization approaches: a personalized model trained only the local dataset (Local), FedAvg with local tuning (FedAvg+) (Tang al. 2019). Clustered-FL. FL (Sattler et al.) 2020), PFedMe (T Dinh et al.) 2020). and centralized and decentralized versions of FedEM (Marfoq al. 202T). We also trained the global models using SGP (Nedić & Olshevsky 2016 Assran et al. 2019) and FedProx (Li et al.. 2020). As SGP recovers FedAvg and DSGD on FC FixU, respectively, we treat them as equivalent approaches. Among all approaches including ours, model architecture follows the setting in Marfoq et al. (2021).
Training procedure We allowed every client to generate its local dataset which has its unique label distribution, following Marfoq et al. (202T), and split into train, validation, and test datasets.
All baselines and PDBO inner-opiimizations ran the distributed learning following Dallowing/Marfog et al. (2021) on FC and F FixU, and ran SGP of Eq. (4b) on StoU and StoD using the train dataset. In PDBO. any i-th client estimates 5j-i, Pij for all j [n] through communications in the imner-optimization. and approximates S by y Appendix C.7 proves this approximation of y is reasonable when | (T)
(T') obtained from the steps of inner-optimizattonn Theorem in
y is sufficiently small.
8

---

Under review as a conference paper at ICLR 2023
Table 1: Test accuracy of personalized models on EMNIST (average clients 10% percentile).
Method
Communication network
FixU
BtoU
StoD
Global
FedPros
69.67
73.8
82.3/74.1 W/
79.7/
n/a
79.7/ W/b
63.7/63.9
74.7/630 n/a
73.7/63.8
T3.7/ 63.8
FedAvg+
83.0/75.1
n/a
R/a
ChisteredFFL
82.3/73.8
lifa
wia
WV
Personalized
gledMec
76.2/65.7
wa I/a
83.9/75.9
75.9
WV 72.9
PDBO-DA
24.9/74.8
83.0/ 75.5
73.2
80.8/
PDBO-MIL
83.9/780 76.6
S3.91
76.5
73.3
81.6/ 70.0
PDBO-ATI.CM
88.9/76.2
PDBO outer-optinee outer-optimizztions ran 20 outer-steps tracing the average validation accuracy, and we reported outer-step that showed the best validation accuracy. Outer-steps were
the average test accuracy performed by Adam (Kingma & Ba 2015) from the zeros initial hyperparameters Od To estimate the hyper-gradient for each outer-step, clients ran M 200 HGP iterations with Eq. (4b) using the average cross-entropy on the train dataset as Fú. We adopted HGP for FC and F FixU, and VR-HGP with (a, 9) (0.9, 0.1) for StoU and StoD. We also made a practical modification in HGP to sample (m) and B (m) together at the single m-th round, which leads to the same length of the Neumann series with the half sampling costs of the original HGP, while they are no longer unbiased.
6.2 RESULTS AND DISCUSSIONS
Personalization performance Table shows the average test accuracy with weights proportional to local test dataset sizes. We observed that the ensemble-based approaches, FedEM, PDBO-MTL, and PDBO-MTI&DD. performed the best on FC, and PDBO-MTI &A outperformed on all fully- decentralized settings, that are, F FixU, oU, and ot. Although PDBO-DA improved the average accuracy from SGP in all communication settings, it was especially effective when combined with PDBO-MTL. These results indicate that optimizing diffferent parameters simultaneously, which is newly enabled by our PDBO, is advantageous to the personalization performance.
We also investigated whether the accuracy gain was shared among all clients. Table shows the accuracy of the bottom 10% percentile of clients. All our approaches improved accuracy at the 10% percentile from global model approaches (SGP and FedProx) in all communication settings, confirming that the clients fairly benefited from our personalization.
Applicability to stochastic communication networks The communication network limits the available personalization methods, especially when the network is stochastic. Although FedEM is one of the few personalization methods feasible in fully-decentralized settings, it requires the doubly stochastic mixing matrix to be known, which is impractical 2012). As PDBO encompasses SGP and HGP can run on stochastic communication networks, our approaches succeeded in the personalization on StoU and StoD.
stochastic networks (Tsianos et al.)
Robustness to communication directionality Our HGP and VR-HGP estimate graddegr solely from the directed communication edges, rather than running the standard recurrent backpropa- gation which requires undirected edges. The improvement in our approaches on St demonstrated that VR-HGP estimated the hyper- pper-grrddent with sufficiently small errors to solve PDBO.
CONCLUSION
This study proposed a gradient-based PDBO, which reduces most personalization approaches the optimization of hyperparameters possessed by each client. We also proposed HGP that estimates the hyper-gradient through communications over stochastic and directed communication networks. In addition, we introduced variance-reduced HGP that mitigated the estimation variance caused by the stochasticity communication edges and provided its theoretical error bound. Our empirical results demonstrated that our gradient-bait based PDBO with HGP enabled combining different personalization approaches which led to oftte-of-the-art performance, and performed on different simulated communication environments including stochastic and directed network.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We provide the detailed experiment settings of Section in Appendix DesondxxDDiee Dincluding any modification
the benchmark conducted by Marloq al. (202T) and will be releasing their implementations after
the review process. Our theoretical contributions and required assumptions are stated in Section 4.2
The detailed derivations of our HGP and VR-HGP are provided in Appendix [A] and Appendix B
respectively. We also provide detailed proof of the estimation error bound of VR-HGP in Appendix C
The code for reproducing the results in Section 6 and Appendix GG are provided by a separated supplement.
REFERENCES
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Feder- ated learning with personalization layers. arXiv preprint arXiv:1912.00818, 2019.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, 2019.
Mahmoud S Assran and Michael G Rabbat. Asynchronous gradient push. IEEE Transactions Automatic Control, 66(1), 2020.
Florence Bénézit, Vincent Blondel, Patrick Thiran, John Tsitsiklis, and Martin Vetterli. Weighted gossip: Distributed averaging using non-doubly stochastic matrices. 2010 ieee international symposium on information theory. pp. 1753-1757. IEEE, 2010.
Pascal Bianchi, Gersende Fort, and Walid Hachem. Performance of distributed stochastic approxi- mation algorithm. IEEE Transactions on Information Theory, 59(11):7405-7418 2013.
Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on graph. SIAM REVIEW, 46:667-689, 2003.
Due Bui, Kshitiz Malik, Jack Goetz, Honglei Liu, Seungwhan Moon, Anuj Kumar, and Kang G Shin. Federated user representation learning. arXiv preprint arXiv: 12535, 2019.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01099; 2018.
Xuxing Chen, Minhui Huang, and Shiqian Ma. Decentralized bilevel optimization. arXiv preprint arXiv:2206.05667, 2022.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending MNIST
to handwritten letters. In International Joint Conference on Neural Networks, 2017.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003. 13461, 2020.
Moming Duan, Duo Liu, Xianzhang Chen, Yujuan Tan, Jinting Ren, Lei Qiao, and Liang Liang. Astraea: Self-balancing federated learning for improving classification accuracy of mobile deep learning applications. In IEEE 37th International Conference on Computer Design, 2019.
Paul Erdös and Alfréd Rényi. On random graphs. Publicationes Mathematicae, 6:290-297, 1959.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference Machine Learning, pp. 1163-1173. PMLR, 2017.
Hongchang Gao, Bin Gu, and My Thai. Stochastic bilevel distributed optimization over network. arXiv preprint arXiv:2206. 10020.5555... 2022.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: (002 02246, 2018.
10

---

Under review as a conference paper at ICLR 2023
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complex- ity of hypergradient computation. In International Conference on Machine Learning. 2020.
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv preprint (eXXiv:909912200 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
A Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Tront, 2009.
Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum-basee variance reduction. arXiv preprint arXiv:2205.0 0600,, 2022.
Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor- Yüing Su. Scaling distributed machine learning with the parameter server. In 11th USENIX Symposium on Operating Systems Design and Implementation. 2014.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In I. Dhillon, D. Papailiopoulos, and Sze (eds.), Proceedings of Machine Learning and Systems, 2020.
Wei Li and Andrew McCallum. Pachinko allocation: correlations. In Proceedings of the 23rd international conference on Machine learning, pp. 577-584, 2006.
Dag-structured mixture models of topic
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, 2018.
Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks. arXiv preprint arXiv:2207.13220 2022.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pp. 1540-1552. PMLR, 2020.
Songtao Lu, Xiaodong Cui, Mark S Squillante, Brian Kingsbury, and Lior Horesh. Decentral- ized bilevel optimization for personalized client learning. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2022.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint 10X1::2002.10679, 2020.
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Proceedings of the 18th ACM international conference on Multimedia, pp. 1485-1488, 2010.
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated multi-task learning under a mixture of distributions. In Advances in Neural Information Processing Systems, 2021.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficiie efficient learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, 2017.
Angelia Nedić and Alex Olshevsky. Distributed optimization over tine-varying directed graphs. IEEE Transactions Automatic Control, 60(3):601 -615, 2014.
11

---

Under review as a conference paper at ICLR 2023
Angelia Nedić and Alex Olshevsky. Stochastic gradient- push for strongly convex functions time-varying directed graphs. IEEE Transactions on Automatic Control, 61(12):3936 3947, 2016.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pp. 737-746. PMLR, 2016.
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 on Learning Representations, 2020.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chick Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4510-4520, 2018.
Felix Sattler, Cebus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model- agnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems, 32(8):3710-322 2020.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems, 2017.
Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. In Advances in Neural Information Processing Systems, 2020.
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning.
IEEE Transactions on Neural Networks and Learning Systems, 2022.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis. and Samet Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. arXiv preprint arXiv:2205.02211 2022.
Konstantinos I Tsianos, Sean Lawlor, and Michael G Rabbat. Consensus-based distributed optimiza- tion: Practical issues and applications in large-scale machine learning. 50th Annual Allerton Conference Communication, Control, and Computing, 2012.
Paul Vanhaesebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized collaborative learning of personalized models over networks. In Artificial Intelligence and Statistics, 2017.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Fed- erated learning with matched averaging. International Conference on Leurning Representations, 2019.
Shuoguang Yang, Xuezhou Zhang, and Mengdi Wang. Decentralized gossip- based stochastic bilevel optimization over communication networks. arXiv preprint arXiv:2206. /0870, 2022.
Valentina Zantedeschi, Aurélien Bellet, and Mare Tommasi. Fully decentralized joint learning of personalized models and collaboration graphs. In International Conference Artificial Intelligence and Statistics, 2020.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, arXiv preprint arXiv:1806.00 00582, 2018
12

---

Under review as a conference paper at ICLR 2023
A ESTIMATION OF HYPER-GRADIEN
Notation For a vector v E R², ||o|| = v Vii of is its la norm. For a matrix V E Rd4idd ||112
is its largest singular value.
A.1 STATIONARITY OF SGP
We consider the generalized version of SGP over n nodes follows:
11+1) = -E PP
)4, ( Xo ( + vi ( (.: ) - offP (6f9).....09)))
j=1
We set 6/0 for all and i, i.e., every client send message itself at any time step. Assumptions
and 2 ensures existence of the unique stationary point y²
yi Es.5
Σ Pipps (v): } (3 +b (0e: A, Gi
Pailee |sps Ay; + Be bobs (2) As.
where pj: = Es [p
A.2 HYPER-GRADIENT BY IMPLICIT DIFFERENTIATION
We adopt Assumption 3 so that y0, ub, and F to be differentiable. The differentiation of y by Xj is
da, vi
P&e (dx, y oy Be [4y (vj: A G)] + 8x Ec رمم (リ): Aj G)]
j=1
j (d2, yf ag. Bgg (bbs (y): A 4) 0х R5g ( (uf ; X1 G)
Let 3" [B/]] and A [At] be the concatenated parameters and hyperparameters. respectively. We can write the differentiation in the matrix form by
day" dxy À + B,
where
A
AAA + Af
ji E RRdd xndy
A = 0y Bc lsp:lyt: Ao, Gi)l E Rdodd
AS = Es (p)( Rd
B = By + : By) E Rndy
B = 0x F (4: Ai, Gi) E Rddxdy,
B. = Rh (,) E Rdxxd
Then, we have
day' = =B(I-A) A)-
In particular, we have
dx v. = (B) A)-
where (+)sk and (.) denotes the (j. k) and (ks, i)-th block of the matrix.
The hyper-gradient of the objective function F(x" >) E, Fx Ax) is then given dx, Fly" X) = Σ dx, Vi By F. Ar) Fx
Σ d U. cf + +c²
13

---

Under review as a conference paper at ICLR 2023
A.3 ESTIMATION OF HYPERGRADIENT
In the remainder, we consider th and f of the following forms:
(y: Ae, G)
Σ
Di (y )i,
SEC
s وy ンリ (i =
hy 2):
|sg1
SEC.
for some (:; {) Rd + R and (: }3. {) Rd - Rdd, which are true for SGP in Eq. 4a)
and Eq. (4b) Assumption ensures that 9j and hy are differentiable with respect both y and X.
A.3.1
ESTIMATION OF Á AND B
Because the matrices Á and B are defined as the expectation over the data minibatch Ço, S as well the realization of communication network ö, estimate them from the observation as follows.
|,
v + +PnA Rudyyxndy
AV-
By 9: A.,g) E Rduxds Ag-
Σ EEC;
oy (15: E Rdxxdd
15i EEC;
|6yl
B
B, + P.j By) Rnndxxnd,
B = Isi1
Σ
ax hx Ar,E) E Rdaxdy By- = |s,l
Σ
Rdxxd
SEC
EEG
A.3.2 APPROXIMATION BY NEUMANN SERIES
With Assumption have A Neumann series up to the M-th term as
1 We can thus approximate (I (I-A) -A) by the truncated
00
M
-
(I -I A) -1
Σ m=00
m
m==
The approximation of the hyper-gradient could be expressed as
M-1
dxF(xz A) Re Σ
A c + tcj.
m=
By replacing À and B with the estimators A and B, we have
M
FxF x A)
B (2m)
II ==0
(2++1)
2 + cA
m==
where 12++1) and (2m) denotes the estimators at the 2s + 1-th and the 2m-th step of the commu- nication round, respectively. this estimator, we estimate A the odd-numbered steps and estimate B in the even-numbered steps of the communication round, respectively.
A.4
PUSH (HGP)
We now present our proposed method, gradiett push (HGP), which is a modified version the recurrent backpropagation. HGP same order communication efficiency as SGP. In HGP, we adopt Assumptions and 7 and assume that {5j-; E& [5)..]}s. and (pzz J y known.
stochastic and directed networks while enjoying the
14

---

Under review as a conference paper at ICLR 2023
The idea of HGP is to use bi dg
Pet instead of Pji in A and B follows.
A
11 A
1 + dies
Psc
A
B
1 Br + 820s
Pis B
òi-s 5a
Under Assumption 5 where and are independent, these the unbiased estimators because
Es,5
A =
1 Eug
A
+ Ess.s
8i-j
Pjs
ESs,
A4
di.j
AA
A.
8..1 8i-s
PPs
1
= A + Apj:
Es.c
B
1 Es
B
+ Es..;
Pji
Be,
Bij
8z-j
=B.
8i.s 8,.5
Ajt =py
=By
1r + By
=B.
Recall that the hyper-gradien can be approximated
M-1
d2, F(x A) R
())sk Σ (A )ack + cj.
(15)
m==
By replacing the expectation with the above estimators À and B, we have
M-1
m
A) =
(2m)
Σ
II ==0
À (2++1)
of +
(16)
m=0
ki
Let u (m)
=, Im-
(2++1)
y We note that u
(m+1)
can be computed recursively as
(m+1)
Å (2m+1))
u (m)
k
kkl
By using this fact, we can rewrite the estimator as
M-1
2
dx ( =
A)
Σ
B
(2m)
Σ A
A 2mm (2m-11) 11)
II
Å (2++1)
o +c
lok'
m=
b
x=
ki
(m-1)
(2m))
A (2m (2m-11)
2 (m- 1)
jk
(m)
We then derive the proposed algorithm, hyper-gradient push, follows:
15

---

Under review as a conference paper at ICLR 2023
Gradiet Push (HGP)
f g f. t cg
(0)
(m)l) t {o) (m)
+ Ek
(B(2m)
(mm)
jk
(m+1)
- EEE A (2
(m1)
uk
U
Akk
for m 0, 1, 1,2..... .M-
dx, F(== A) (M)
In HGP, the estimator could be obtained after the 2M rounds communication. In each round the communication, the clients communicate ug (m) E Rdd which is O(dy) parameters only, the same as the standard communication for SGP update.
B VARIANCE REDUCTION
We now introduce the variance-reduced version of HGP. The naive HGP above suffers from the large variance because of &5Th) / this term can take value far larger than one when 85.; is small. The multiplication of such values induces high variance.
Recall that, in HGP, we aim at approximating the estimator
M-1
dx, Flx" A)
Σ m==
Σ (B) ((A") +Cy
With "0 + 0, u (0) + C HGP computes the first term of the right-hand-side by iterating
fm+1) c- D. +
(m))
Σ B (u
(m)
oj
(m+1) u
Σ
(A) um (m)
(m++) is equivalent to En (A (m bx. ) cK.. We can also consider another way of computing where u
the first term. With o + Odx w + Ck.
())
2
we can compute
(m+1)
Σ ( (m))
w
(m+1)
Σ
(A) (m)
+ +ct.
where w (m+1) is equivalent Em= k'
(Am')
A cy. = = Em= u
(m''
(m) (m++1)
uk
By combining the above two formulas, we can derive the general expression of HGP
(m+1) -
(5m)) +
> [(B)auu (m) + (1 (1-a) Σ B (mm
(m)
k
(m+1)
(A) F) (m)
u
w
(m+1)
t 3
(m) A'Ala
+
+ + - (113))10)))) + u (mmtt)))
where 3 [0, are the interpolation weights. By replacing A, B by the empirical estimates Á, B, we obtain the general expression of HGP as follows.
16

---

Under review as a conference paper at ICLR 2023
General HGP for Variance Reduction
Od
ujj
(0)
t
cy.
(0)
cy
0 1m+1)
Vj
(m)
Σx
B B((m))
(m)))
+ (1 -1--) Blam)) )
(m)
jk
jk
(m+1)
Ex (A(sm+2)
(m))
k
1 (m+1)
x- 3 Ex
(A(mm)1)
A
Wk + x/k + (1 1 (3) (8) (1r (m) + u )
(m))
for = 0, ..... ..,
dx F F(x", >) + 1) (Mf)
+ cz
We note that this general HGP is the weighted average of the two different estimation algorithms, which results in estimator with smaller variance. That is, by choosing a, B E [0, 1] appropriately. we can obtain an estimate of the hyper-gradient with a smaller variance. From the computational perspective, this general HGP has properties similar to the original HGP: it be computed even on stochastic and directed networks; the estimator could be obtained after the 2M rounds of communication; and the clients communicate (dy) parameters in each iteration.
C ESTIMATION ERROR OF HYPER-GRADIN
In the following, we assume that the derivatives of gi and hy are bounded. Assumption 9. 37U E (0, 7B E (0, oo) such that Vgg and Vi,j.
max
sup Vr.Ac.E
(10 A122) sup | hy Ay. 5)12
5
1A
2 End
Pss
max
sup
[10.9. A,,
hy sup ||a hy (3/ My. E>1l2 An
y/B
yi.A
2 Ei.
Pai 6;.g
Recall that Eis
Pii 2 n by the properties Ex= Pjs = 1, 1, E 10, 1]. Assumption implics
di.s
|| - Σ sup
A,, 1l2 + Σ Pyt sup ViAAi
| h (B/, A,, E)11
vi.Aing
S
Σ
Dji
πA
S TA
2 Ein
Psi
i
biet
||A||
Σ
110y. Ie (Yi AEs 1112 + Σ
Ps sup 110 1t,(,, Ar, 6)12
sup
Jens Ay
i.j
Pis
7
S
I nA,
Óie5
2Σ
2
Dic
b
1.
BBI2 W Σ
sup
||
(i Arr + >
Dis sup [0x,,,(Us A., 5012 yr.
u..Ar.E
Σ Pji
7B
< 7B.
2 2in
iij
Kt.j
Psi
B
Σ
sup
||02 9: (yi,
>o, E)12
Σ
de. AyA
Pji sup h (.: 5.12
gr.d.ng
i,j
Djs
nB
< nB.
Óinj
2 2Σ,
Pr 8
1.j
17

---

Under review as a conference paper at ICLR 2023
C.I PRELIMINARY LEMMAS
In this section, we present few preliminary lemmas we use in the proof of the theorems.
We recall that we can express the general HGP using the concatenated vectors and matrices as
(m-1)) 1) = a (m)) + B (2m))
(m)) (
+ (1 - a) (22m) w (m))
(17)
u (m- A (2m+1) (m)
(18)
w (m-1) = 3 A (2 20 (m) + c²)) (1 (1-13) (1o(m)) ul(tt))
(19)
with the initial conditions (0) t u (0) t c², and w ea
The following lemmas show explicit formula and w and their decomposition. Lemma (Explicit Formula of w).
M-1
(M
II
(1 3)I 3A (2m+t)) c²
m=0
M
M
II A mm )) o² (20)
1-1
II (1 (1- 3)I BA BA {
8I [II (1 - B)
where we define
Imme (.) so that
II 1m==()a O. I.
Proof. We prove the claim by induction. We first recall that
u (M)
II m=0
À 12m+1) c"
(21)
By setting m in 19
we have
(1) (2 + c²)) + (1 - 3) (wo())(()) v
(A dd +0
+ + - 3) (C) + A
- + A (
By setting M 1 in 20
we also have
w
(1 3)1 + 3A++ d² (3I+ (1- (3L+(()))) c² - dd + A0)
which confirms that 20 is valid when M 1.
Now, suppose that the statement is true for some M 2 Then, by (19.
w (M+1) = =A (1(2++1)) (M) (w))) + Cv))
+ (1 (1- B) (M)) re (N)+)
M
A (2m+1) 1) a + (11 3)I BA (((2)-1)) (M)
3 (1- (1)
II
18

---

Under review as a conference paper at ICLR 2023
M
= 3c + +11 (1-1)) 9)
πI L
A (2m+1)
c
M-11
+ (11-3))++ (A
π
(1 (1- (1-3)T (BA2mmtt))) c2
m==
+ +(1-8) BA (2M441
Σ
TM-1
II (1-
(1- 3)I
BA A (2mmti)
(3r+ |1 (1 ()
II 0
A (2m+1) c
M II L
(1 B)I + 3.A (
c²
M
+1x
31 + (1 (1-8)
II Lm=0
A (2m+1)
c²
(-1
II (1 (1--3)I + 3A (2atti)
3I + (1-1) B)
II m=0
A 2mm+1) cD
mi=i
II (1 +)I+33 +3
C"
M+1
M
(-1
II 3)1-3)+++00 (1- Li=i
(BX+
31 (8x+ (1- 3)
II m=0
A 22m+l) d²
where the last line follows from the fact that [1==+1100 =
Lemma (Decomposition of w).
w (M)
A c
M
i (i.M) (A (2i+1) R) + I ((. (2i+1))
(A(2))))))) - -A)A' c²
(22)
1=0
where
M-1
i (2
II mm=+t1
(11- B)J -.(2mm+1))
M-1
j-1
(.. (1 B)
(1 (1- 3)I BA (2m+t))
II A (2m+1)
j=i+1
m=j
R ((1 - ((11-3)+4 3A)* Σ (11-3)1+ 3) +)
1-1 (BI+(1-13)) +1-111144 -))
J=1
Proof. We first recall that, the corollary of Lemma
M
M
A' (1- "
(11
((1
+ 3A) 1-A) (9I + (1-11)1))) (1-3))A) c".
E=Ul
i=1
19

---

Under review as a conference paper at ICLR 2023
By using Lemma 2
expand the difference
M
wM
Σ
A'
i=0
M-1
II
(1 (1-3)
-Alemttt -(1-8)++ c²
M
M--1
II +
- (11-33+++00 3A) M-i
(3I+
(3I + (1 (1-))1))) c²
m==
M
MM-1
i-1
II (1-3)I + 3A 3. (112mmtt))
(1 (1-
II m==
A (2m+1) - -A' - c²
M-1
Σ
(1 (1-B) () +BA(mttt) B (Acott) a) (1-3)I + +BA)² c
M-IM-11
M-1
Σ
(1- /Alemttt) (Alert)) - A) ((1 - (11-))I + +3AA i-1
Lm=++1
X (GI + (1- 3)A²) cd
M
M-1
(1-3) 33 BA
(1- Σ II A (2m+1)
(ARrtt) -A) A'c
j=j
Li Lmmi++1
M-1
M-1
Σ
(1- B) + -.A
B (Ale4t)) - A) ((1 ((1-3) 3)x + 3A) c
m=1++
M-1
3)I (1- +1((mttt)
1 (ACCtt)) - -A)
Lm=i+1
((1 - B)I + 3A) 1-1 (BI + (1 3)))) ct
M
M-1
j-1
Σ
Σ
II (1-B8) 33) 3. ( (1 (1-33
II
A 2m++)
(A - -A) A'd
İ= 1=i+1
m=
Lm=i+1
M-1
M-1
Σ
3
(1 3)1 BA (
(A A)
I=ii+1
=L G.M
X
((1
-01--31-330 + Σ ((1-3) +) +BA))
1-3 (3I + (1-3))A)) C²
j=1
=R(0) (
M
M
M
j-1
Σ (1 9)
Σ
II
(a B)I + BÁ (2m+1))
II mn=++1
A 2m++1
(A2641) -A) A'cU.
1
mmj
20

---

Under review as a conference paper at ICLR 2023
Lemma 4 (Explicit Formula of v).
M
2 (M+1))
Σ ( + (1 a)
Σ
a
M
B (2))
w ($)
(23)
==0
Proof.
We prove the claim by induction. By setting m = - in 17
we have
e = a (v + /000 + (1-a) B w (
( c² + + B() = -0
By setting M = 0 in 23 we also have
e B CD (1 - B -B(00
which confirms that 23 is valid when M = 0.
Now, suppose that the statement is true for some M 2 Then, by 17
0 (M) + (22
+ (1 a) B (2
M-1
M
a (21) (1) + (1 - a)
M M B 20 (1)
a
a
1=0
+ a B (2M)
m (M) (1 a B (M w (M)
M-1
Σ
M i+ B ((2)) (
a (2 un (M)
M
(1 a)
Σ
a
B 21) ( + (2 w (M+1)
M
M
M-++
u ( + (1 - a)
Σ
M-i M (9.
a
==0
i=0
Lemma (Decomposition of v).
M
((M+1) B
Σ A'cv
km0
M Σ
M-1
(2))) - B)R
(.
c² + Σ
(A(M)(AA
(6,00
(((+1)) - AA)A' + +L. (..M))
(A (2141) - A)R c²,
1=0
1=0
(24)
where
R(i. = Mi+1 A' + (1 - aaaa
M-1
Σ A
==0
M
j-1
i M(
Σ j=it1
a M-+11 1(2))
12m+1)
m=i+1
M
A-1
- a11-a)(1
- -3)
Σ (2))
Σ
II (1- 13I + 3A A (
II
A (2m+1)
j=1+1
k=++1
Lm=k
j-1
(( - (1 Σ M-j (2))
II (a1 11-3))++ B. (12mmtt1))
Lm=i+1
21

---

Under review as a conference paper at ICLR 2023
Proof. We first recall that, the corollary of Lemma
M aa--+
i
B _
A'c
BA'C" (1 a) Ma Ba- B Σ A'
-
By using Lemma 4 and Lemma]
we can expand the difference as
x(M+1))
B A'cW
Σ
i=0
Σ
M-+++1
(
II A (2m+1)
BA'
c + + a) Σ M-j
B(20) (1) B >
A'c
i=0
Lm=00
j=0
M
M
a
M--++1
(B(20_
B
A'c Σ (NN1)+11(3)
II
A 22m+1)
A ( A c'co
M
M A'c (1 a Σ
+ (1
a)
M
(B(26) - B
Σ
M B (26)
w (1) Σ c
2=
j=0
1=1
j=0
By substituting (2
we have
(M++)) B A
>
i=0
M
M
1-1
Σ 1=0
M-i+1 (B(2i) - B) A'c + Σ
M- ((2))
Σ II
A (mm+1)
(A - A) A'c'
a
j=1
Lm=++1
+
②)
M-i (B(20) B Σ
c'c
/=0
+11 - a) Σ
M (21))
Σ
i (1:5) (2i+1))
A)R + (A(441) -A)A C
(A
1=0
M
i
(22)) B)
M-it1 A' + (1 - a)a
M-1 Σ A' c
1=0
R M.
M-1
M + + +11-a) a)
Σ M-
A (2m+1)
Σ
- ((,) (A (10H))-A1
-A) A) A'
j=it1
14-1
jmit1
-10.30
M 1
(1
Σ a M-j B(2 (0.)) (24+1) A)R("O
İ=U
j=i+1
By substituting L (id) L (id))
we obtain the claim.
To bound the estimation error of syperngradient, we need to bound each term of 24 The following lemma gives the bounds for each coefficient matrices in 24
22

---

Under review as a conference paper at ICLR 2023
Lemma 6. Under Assumption g
we have
5
1
1
a
M
1
+
1
M-1+1
11A
M -M-in i+1
(25)
2
7A
1 11A
1 7A
M-i
2
(1 B + BTA)
118
1/13
(1 3 -BA) ) M-
(26)
1
11A
1A a - (1 (1-3 3 + +B7A))
- (1
S B1B α
(a (a - (1-
- 33 + (11))
(2
2
(1 - B + (TA))
1 7/A i+1
R
(28)
2
7A
Proof. Recall that Assumption 9 ensures |A|| S 1/, |
s nn.
B S nn.
B 2
S ina-
Then, we have
S aa
M M-i11
|
2 + +1 (1:
Σ
A 11
2
5=0
S a
M- M-i+1
7A + (1 - a)a 2
(1-a)a
Σ 1/A
5=0
M-it1
7/ + (1 a)a M- 1 1
i+1
1 - 7
= a M-itl i
1 1-6 a
M-i
M
-i i1 i+
+ 7A a
M-++1
1/A
+
a
a
7
1/A
1 - 71l
1- 11A
1 1JA
1 -
M-f
1
M-+11
M
M M-
1/4
11A
77A
1 7
1 17A
M
j-1
i
(8.M))
< Σ
a M
M-+t
A 22m+1)
2
j=it1
m=i+1
k-1
+ - +(1a)((1 -1))) 3) Σ a
M-J B(2))
Σ II
(1- (1- B)1 + (2(2++1))
II
A (2m+1) 1)
j=i=1
k=i+1 m=
m==++
M
M
< B
a
M-++ j+1
M
1/A
j-i-1
+ 1B(1 - -a)(1 - -3)
Σ
a
Σ
(1 B + (BaA)* 1/ 8-1-1
j=1+1
j=1+1
k=i+1
M
a
(a M-i - 11A
M-1) + 1B
1 a a Σ
M-j (11 B (11-B+3aa)) - ,
= B
a
1 - 7A
j=i+1
a
(a M- - 1 M-1)
B
a 1TA
1-a a
(1- + 3AA) Mi (1 (1-P) BB B+ (TAA) M-i)
nA (a Ma - 1,. -i)
-17AA
+ 11
1 7A
a (1-
3 + (TAA)
a 11A
1
(a M-i
1 M-1) + 11B
1-a a 1 1-3 1B+BAA
(aM-i- - (1 - 33 + Mi
T]B
- -|A
7)Λ a - (1 - B + +BnA)
a M-1
M-i
1BB
1-a
(1 3-33- + (BAA)) M-++1
0 (1 11-53 13 + (AAA)
1 7A a (1 - 93 + (87A)
23

---

Under review as a conference paper at ICLR 2023
M
j-1
c M
s (1 [1
Σ a
M-j B(25)
II
[1 (1- 8)X + BA (2m++))
j=it1
m=++1
M
S <na(1 - a)B
M- - + +1AA)-i-
j=+1
(1 - 3+ + BMA)
=1 - a)B
a -1 - 3 + (M1A)
R
S 11(1 - B)T + 3A + Σ (111 - 3) + 3A 1-3
2
j=1
<11 8+ 3TA)" + 3 >> (1 - B
Σ (1 - 3 3TA)
j=1
j=1
1- (1 3 )
(1 3 BAA)' - n'A
= (1- - B + BAA)" +
+ 1A
TJA
1- 1JA
1 7 i+1
1 AJ
C.2 DECOMPOSITION OF Á, B
We can decompose the difference Å - Á and B - B as
bi.j As AA3) 13)1,
Á Á A
1ni(A A +Dj
8,,5
( 8inj
-1) })p)A/
+ [IR(AA - + 59
16
n
[ōioj Öinn
Σ
e,e,
8
-1) PjiAg
i==1
+ 11
e,e;
T 8
A²)+ Lsi Σ (BU. - +
Pjs (1,,)) 43) |Gi
|5il
EEG:
EEC,
(dies Byg- - BTy) BB:] }]
B - B =
1 B B,,h)) ) + +Dzi
Öioj
ji
(Bmg 11 1) BrrB3l + [1,".. - BB²) + Psi (By- - -B²)]
Oinj Óiej
Σ
eje,
T 8
-1
Pji -1)ps1B3
1,
+ Σ
e
1 ji
(8s.
B₂²)+ +
PJc Σ (0,,h)(0) B3)
Gcsl
iJ=1
SEC.
EEG,
where e,, e, are i-th and j-th canonical basis vectors.
24

---

Under review as a conference paper at ICLR 2023
By using these expressions, we rewrite Lemma 5
as
M
(MM+1) B A'c
M
n
M
M-1
M-1
(.9 Bu
c²
+
Σ
ΣE
Y(U
A,t c²
B
i= s,t=1
ÇEÇA 21)
1=0
5,t=1
1=0
SEc! ()
where
(i) Nnt
x
(0) B,st
=
eieg 8
8gmt
Pio BroB))
y = Σ
n
1
(Ie (VT Ac.E) + Pra (n 2c,5) - 1, - Dis B:) ng n!M.
B,t
Cies
88
(((2i)
1(2im1)
X (1)
= L (1.00)
Cat
Pio Ap(aatt)))) A'
e,eg 2
A,st
deet
8(2441
+ L
((.M)
C 20
Pts Pro Ap(2tt1))
R(().
Oant
a (( y
(Ioddn E) + Pro he ),, 1,,,, Des Ai) A
cee
B,t
1s (124412)
n
( + L
(1esdrr 2) (1,)) + Pts Bg, he )e, 11s - Pts At) R!O.
e
Ice
Here, we note that (.,M0 and i i (22+2)) (2M)) We therefore have
depend only on 22143) A 12 and
E 020t" (044))
(
(i)
A
(2443)
112M-1) ((2+2) ..... B(M = 0,
Asst
(29)
E B (2511)))) (2512)
(
(2(43)
12) B (21+2)
B(2M) 0,
by the independence of 5 (2(+1) and c (2++1) in Assumption 5
C.3 BOUND FOR a E 10 AND 3 E 1),
We now derive the error bound of VR-HGP for the case when a, B E (0, 1). The error bound follows from the next bounds on x((
B.st: B,: A and (t)
x(1 ((i)
A,
Lemma 7. Under Assumption when a. (0, 1) so that B + 3ra E (Ma 1), we have
X
(8)
B Dh a a
( + exp(-O(MM),
(30)
B
2
x²
82.t
X
(i)
1 Dig
77
(1 - a)
2
8+ (a--i- -1- B1a))-1) + exp(-O(MM)
A,
2
x²
82.
7/Λ a - (1 + (r1a)
(31)
(i,E)
5 x:2
4
1-a
2
2((M-1) + eexp(-O(MM)
(32)
x=21c(201 (2
1 17
(1.))
1,2
2
4n
17.1
(1 a)
)
2
(a--i- (1-
11-B B (nAA)) M-o) + exp(-O(M)),
-
x
12++ 2
1 - MA a - (1 - 3 + +BBAA))
(33)
25

---

Under review as a conference paper at ICLR 2023
where
K
Σ
Pts 854
(34)
8,7
Proof.
(
2
2)
B
2
(.)
2
1 +
-1
Pis
Bist
2
8e
2
3
$ 5-1
Pia
1B
2
a a
M-i
+ +exp(-O((M))
8
2k
7/A
2
Pie
a
a 2 + (O(M))
x2
x(1) (5)
A.st
1 +
8get
1
2
Pie
1: (|
(1000)
n/A + L
(1.M)
1 )
Pis
2
1/B
(1 (1-a)3
(a -1- (1-8-- -+ + 3M1) + exp(-O(Mr)) )² )
2k
1 - 77 a - (1- 3 + (nA)
1B Pie
1/A
2 11A a - -11 11-B++ + +BMA))))
(1 a))
(a--i-(11- -1 B1aaa~1) + cxp( (exp(-O(M))
x² g-1
(1.))
2
1
n
1x 2) + Pr de. - 1 Br Pts Bj
R
(1.M)
B,8
2
12
15t
2
2 1 1- a a M-i + exp(-O(ar)) )²
1
BBB
2 2+ 2
Pts
15!20)
2x
I n
s=1
4
1 1-a
a ((M-)) + eexp(-O(M)),
k22 |s(
(21)
12
111
(1.5)
2
n
1 1e Ar: + he E) 1,, ProAF
1 5
12
x
7'A
i
(1
R ( 2
(2)
2
MA
2+ 2
P18
15
12
2K
1BB
(1 - 3,3
(a (1-33 -3 M--) + =xpp(-o(ar))
x
7A
(1 - 3 3TA))
4n
17A
(1 a))
)
2 Ma--i (1 - B + M- + expp(-O(M))
x (2++1) 22
1 - M] a - (1 - -8 3+ (BB1)))
26

---

Under review as a conference paper at ICLR 2023
Theorem 8. Suppose Assumptions 1 with probability at least e, we have
hold true, and 16 for any and i. Then,
(((rt2) + Fly". 2>
Pis
4n
n(dy + dx)
S MTT
log
+ +exp(-O(M)),
82
b
1,,==
where
1 1-a a
1 1 a(1 + BMA)
32n2
7B TBB|c*
Ha.. =
8
1+
T=
I+a
1 a(1 3 + BBA) 1 1 (1 B + BAA)²
x(1 -1A)
Proof. We first have
|olle2)) + - - Fly" >> S (01M+1)) B Σ
A' c
+
B
Σ i=M+1
A'c²
i=
Here, we can bound the second term by
|B||2*|
B
A'c
S nBl
nalc"*
ca1l
n -
7A
M+1 = exp (-0(M))
7A
i= M+1
i=++1
The conditions (29 ensure that we can bound the first term by using Matrix Azuma's inequality; with probability at least 1 - E, we have
((M+1)) - B
M
A'c
S 1802 "ly + dx)
1=0
where
x²
M
n
X
(
2
M I
n
(i) 2
||aya
B,st
A,st 2
2
1=
8,t=1
1=0
8,1=1
n
(1.))) 2
ΣΣ
12
SEC(21)
1=0 (2(()
M
B Pts
2
1 1 a
2 82
1 17A
0= 8,1=1
M
1
Pis
71A
(1-x):
-1 + (Baa) Mi1²
R2 g-d
1- 1)
(1 - B (9A))
1=0
s,t=1
M
4n/
1-
2
2(M-))
x2
(200)
1 1 7
(2)
(2))
ΣΣ
4172
7A
(1 (1-a)) a)
Ma- -1-3+ 111-i-(1-13 811a)-ii
(
?A a (1 3 + Bqa))
(Ec(2++))
+ exp(-O(M))
27

---

Under review as a conference paper at ICLR 2023
7B
n
Pis
1 a
2
2(M+1)
x²
1- - 7AA
a²
, 8-8
1/4
(1-a). a
12
1 1] (1 - 3 + BBA))
2
a (M++)
(1 3 + 3TA))² - (1- - + 3
a(1 - 3 + 3TA)) - ar - - + 3
M+1
X
- -2-
a2
1- (1 3 + BmA)²
1 - a(1 B + B11a)
4
a
2
1 1-a0 (1))(M+1)
(2
1 1/A
1- a²
M
K
4
17
(1 - -))
R2
(
1A a (1- B (.BAA)
a²
(2(++
B + Bqa)² (1 - 3 + (qA)) ((M+))
-2 a( 3 + BTA)) a - + Snx)art1)
X
+
a-a²
1- (1 - 3 + ATA)²
1 a(1 - 3 37A))
+ e (M()
1/3
Pis
Σ
4
1 -
2 1
x²
1-8
St
(2)
1 17A 1-a² a²
Σ
1/4
(1-
2
+
R2
1=1 15t [
1- 1] a- (1- - 1 + BmA))
Net
a²
(1- 8 + Bna)2
al1 - 3 + BTIA)
X
2 1 a(1 - 3 + 3m1))
1- (1 - 3 + 31112
+ exp -(M))
n
P
4
1- a
2 1
x²
22)
1- 1
1-a²
L,,==
(=1
St
+
MB
Pie
+
Σ
7A
(1-a);
2
R2
Le,t=1
8+1
t=1 1st
(2(+1))
1 11
1A a (1 - B + 3TA))
(1 + a(1
B + Baa)) - (1 - 3 3na))2
X
-1-00 a2) (1 - + (11)))(1 - a(1
+ (TAA
+ exp( (M))
Pis
1- a 1 a
x²
get
t=1
(2)
A
P1s
4
1
2 $ -
+
82.
1st
(22tt))]
1- n
I+a
Le,t=1
t=1
1+ a(1 - 8 + (na)
13272
X 1- a(1 8 + BTA) 1- (1 - 3 B2A)2
+ exp(-O(M)
When (: (1)) = |2 ((+11) = b for any t and i, we further have
0² < R12 )
1/8 c00 |
n
Pix +
4n
b
1 g-t
x 1 1-a a
1 + a(1 - 33 BTA)
82
|
+ +exp(-O((M))
1 1+a
1
a(1 -B+ (T1) 1 (1 B + BTA)2)
28

---

Under review as a conference paper at ICLR 2023
C.4 BOUND FOR 1 AND 3 = 0
Setting
and B 0 recovers naive HGP. Here, we derive the error bound for naive HGP.
Lemma 9. Under Assumption g
when a 1 and so that 1 B + ANA 1, we have
2 Pis
X
(
B
24
(35)
B
82.t
x
(
B Pis
2
11A
AA exp (-O(M))
2
(36)
A,st
1o? 82.t
17A
2
A
77
(37)
2
1:21 Se
(2))
1/=
|--
4
Vi + exp (-O(M)).
(38)
n22
n=1lt
12
1 7A
Proof.
-1 1 1)²
2)
2
(., 2
x
B,st
+
8xst
Pes
B
R
Pis
1B8
(11a)
2k
Pie
T
x² g+1
1,
(
2
<
+
Jent
-2 2
2)
Pie
1: (1129000)
1/a +
-. ()
|
|3 2
2 (n'a nxx )
Pis
1/8
82
2k
- 7AA
2
1/B
Pis
VA + exp (-O(M)),
x²
dut
TAA
(1.0)
(1.5)
2
1
a
1
It (2) Ar, + (1 1, B3 1
R
(1.M) 2
B.8
2
15
12
2
1
MB
(1'A2
+ 2
Pts
1c!20)
2k
8=1
41/33
24
x
I5e (24)
12
(1,0)
1
2
-
Les Le der + he Ars - 11. - Pro
A.5
12
(11 ((.M))
R 1))²
7'A +
2
1122 15
1xx
T/4
2 2
Pes
11
(n'a v2a1)
1 17.1
2i + exp (MM)))
x31cc (2++1)
11A
29

---

Under review as a conference paper at ICLR 2023
Theorem 10. Suppose Assumptions 1
withaobbbbiliyy = 1 = 0, with probability at least
hold true, and 1 = 16t 16(2it1)/ for any and i. When
e, we have
- d2, -d,,
Fly. ./or.2/1- s 110T
Pia
4n
log
n(dy + dx)
+ (xx(())(M))
0
[<]
e,1=1
where
8 12 + (1 - n1
Mn c
M1.0 = V
1 nna
x(1 71))
Proof. We first have
x
-d, F(y" >> <
((N+11) B
_ A'c
+
B
Σ i=M+1
A'c
Here, we can bound the second term by
E
B
A'c
S 1Bl|c*1|
Σ
1/
MB
|
M+1 1/A
exp exp()O(M))
i=M+1
i=++1
We can bound the first term by using Matrix Azuma's inequality; with probability least 1 C, we have
$ 1802 + dx)
(((++1)
B
A'c
e
where σ²
M
2
M-1 n
2
Σ
x
||
B,st
2
A
2
1=0
1,1=1
1=0
8,f=1
1
M-1 Σ
(1.5
Σ
(1.))
12
(EC(2))
(Ec((2)1))
M
2
M-1
Σ
AA
n/A
1= 8,1=1
1=
s,1=1
g+t
1AA
M
Σ
m
+
M-1
4n (2(+1)
7A
2i
+
1=0 1=1
REC (2))
RZ
İ=U 1= SEC! (2++1)
k=1s((
12
1 1A
12
22
2(M+1)
VB
Pie
7
(2))
1 n'
8+!
1B
LS
4
7A
2
1
2M
+ exp(-O(M))
22
(2x+1))
7
2
[=1
1
1
Pie
1
R2
(28)
s+1
St
2
4
7A
2
1
+
+exp(-0(m))
x²
82 get
11-1)
L
m=l
When (1)0
|k| 1k( (2
b for any t and i, we further have
2 |c" 1
n
22
4n
0² < x² (1
(1
1 + (1 7A
+
+ +xp((-((M))
L,,(=1
30

---

Under review as a conference paper at ICLR 2023
C.5 COMPARISON OF Pa.8 AND Ma,1
The estimation errors of VR-HGP and naive HGP are dominated by their scaling factors.
1 a
(1 1 1- a- 8 BnA)
1 a 8 3mA)
3 1+a
+ B
UA + (1 1TA)2
11,0
1- 7'A
Figure 1 shows that Ma,s is few times smaller than 11,0 for any 7A E (0. 1) if we choose a close to one and close to zero. This result indicates that the error of VR-HGP can be few times smaller than the one of naive HGP for sufficiently large M where the diminishing term exp (-O(M)) is negligibly small.
7
1,
a= 0=9,8
a= 0.9, 0.2
4-
a= a= 0
a= 0.8,8
1
0.2
0.4
0.6
0.8
ΠA
Figure 1: Comparisons of Ma,s and (4100 for 7A E (0, 1).
C.6 COMPARISON OF & AND
We empirically evaluated the advantages VR-HGP in stochastic communications as well as found that (o. B) (0.9, 0.1) performed well in practice.
We compared the & norm between of the syper-gradient estimation (((m) at the m-th round of HGP
and the true hyper-gradient F (a*", >) which computed using the explicit (I A)-1, We made synthetic one-dimensional dataset with two classes by randomly selecting two digits from MNIST let n clients performed 500 iterations of Eq. (4b)
and averaging the inputs each sample. ensuring the convergence of SGP. For all E [n.. we used the binary cross-entropy loss for fi and F; computed on local training and validation datasets with 100 samples, respectively. We adopted StoU communication network presented in Section 6 In order to purely evaluate the effect of edge stochasticity sfth) /āy... which we pointed the source of the high variance in Section 4.2 excluded the randomness of minibatches Ç by adopting |c!" 100 for all time steps in SGP and HGP and by using the true Pij and oj.4 for all i E [n]. We computed F (a", A) from the explicit computation of B [I A) 6 c using expected values of Pij and ōy.. for all i, [n]. The HGP was conducted to obtain (m)) after the iterations of SGP using 500 and the alternative samplings, i.e., Á (2m+1) and (22m) for m = 0, ..., M 1.
Fig. 2 shows VR-HGP with (a, (3) (0.9,0.1) provided the smallest estimation error and the larger number of estimation rounds tends to have smaller error. However HGP, which is a special case of VR-HGP with parameters (a,, 3) (1.0, 0.0), failed to attain smaller error than the well-tuned VR-HGP with (a, 9) (0.9, 0.1). This larger estimation error was also observed in experiments with different random seeds. We also observed that HGP could not reduce the estimation error after around m 5 indicating the larger number of rounds does not always help the better estimation in HGP stochastic communication networks.
31

---

Under review as a conference paper at ICLR 2023
10
||vi dy AIl
Wi
a=1.0, 8-0.0
a-0.00 a-0.0,8-1.0 8-1.0
0=0.5, 8=0.5 B-0.5
8=0.1
0.1.1, 8=0.9
100
200
300
400
500
Figure 2: l norm between the estimation VR-HGP (m)) and the true hyper-gradient d, F (ax", A) at the m-th estimation round with different combinations of a and B.
C.7 RELAXATION OF CONVERGENCE TO THE STATIONARY POINT
While VR-HGP relies on the assumption that the unique stationary point y² is available, client
may only have (T) # y in practical case where the inner- mnner-rroblem is solved by finite T of SGP iterations. We show that this assumption can be relaxed by adopting an extra smoothness assumption below.
Assumption 10. There exist finite positive constants Ly, LA such that for any E [n]] and for any ys: V.
sup (0 A, {) - 0y A,, E) S Lullys - vlll.
A.
sup 10 y. hi (y:, Ai, { 8, 1: A, Ol1 < Lylly: vill.
A:-
sup 10x gi y/ A 8 0x g6 (3/ A, 1)12 - 7BLa|ly 1/ll.
A:A
sup 10x,h A, {) - h, >, E) $ n 111,111:111 vlll
A:E
Below, we show that the error between y, (T) and yÿ induces a bias to Theorem
Theorem 11. Let ((M+1) be the estimate of (M++1 obtained by VR-HGP using (T) instead of y². Suppose Assumptions 10 true, ( |g(2 (2i+ b for any and i, and a, B e (0, 1). Then, with probability at least we have
((M+)) + c dx, Fly", ;>
4n
nidy + dx)
n nalle*
$ $Ta,TT
+
log
(T.y + I2)G + +exp(-0(M))
b
(e,t=1
where
G
3 y (T)
i=1
32

---

Under review as a conference paper at ICLR 2023
Proof.
To compute ((M+1) using VR-HGP, A and B are estimated by
A 1 v + P3
Ruddyndy
j
A 1sel Σ O :2 Rduxdd
A3 = 1s,1 EECs
Σ
(T), ;,,, E Rdvxd, "o
SEC:
B
B. Pri Bi Rundxndy
B
Σ
Ox. ).. (2.E)) Rdadd By = lsy1 EEC,
Σ
; ;>,,E) E Rddadd,
1
EEC.
We can decompose the difference Ā Á and B - B as
Á A
Ā - A) + (A-4) A), B B B=
B B + (B -B-B) (B-B)
Here, by Assumption 10 we have
Ā A
S
Ly
yi
y: (T)
= LgG.
B B 12 S Mn Ln Σ 33 - y (T)
= 7n
By using these expressions, we can derive the expression similar to Lemma 5la as
M
F(M+1)
B
A
1=
Σ
x
(i.)) c Σ ΣΣ
c ΣΣ
((E))
(=0
(Ec!a
M
M-1
+
(B(2)) -
B)R
( e
+
i (L. (A 22+11)
A)A + L (L.M) (2i-1) (
A C²
A)R
1=0
(Bias)
where the last line corresponds to the bias induced by the use of y instead of y", and
I (6.M0
Σ
M M-5+1
((3))
II À 12m+1)
j=++1
mm=++1
M
J-1
K-1
+ (1 a) -3)
Σ
a
M M-J (2))
Σ
II (1- B)I SARm+1))
II -==++1
A (2m+1))
j=it1
k=++1
Lm=k
M
j-1
(.0M = (1 a)
Σ
a M-j (21)
II
(1- BBI (.(22-m1))
F=
Lm=++1
(2i+1)
(2i+1)
(1) Asst 1 ((
get dant
Pes Ar. (2(14t2))
A' A'+ ((C,M))
ereg
1 Pis A Ap(21t12) R!.
dent
(1) i (L
e T
(Ieodg. (.. + Pr. By (,,, 1 11. Brodt) A
1st (2i+1)
I (t.M)
(1e,0g. d., he Ae.)) - 1,, - mmaAt) R!o.
c
| [(2)+1)]
33

---

Under review as a conference paper at ICLR 2023
Then, bound the bias
[[Bias)]
M
B
B
R
|ca||
2
==
M 1
+ Σ
(1,M)
1
A 1/1 |||1
1g M)
2 -a1[ 1 11)
1=
1 1-
< L1
1 !)A 0m0
+ GL,
1
(1 (1-a)3 a)
M
(a (a-li (1-B 3+ (11) 16 + exp (xpp-000 (-O(M))
AJA 0 - (1 - + +1TA))
TJB (Ly LA]G + exp (MO(M))
D DETAILED EXPERIMENTAL SETTINGS
The experiments in Section Section followed the settings of EMNIST (Cohen al. 2017) classification in Marfoq et al. (202T), unless otherwise mentioned.
Communication networks We simulated four communication networks which the clients per- form the distributed learning: fully-connected (FC), static undirected (F i xU), stochastic undirected (StoU), and stochastic directed (StoD).
FC allows clients communicate with all the other clients all the time steps, i.e. 6/2 1 for all i.j E [n] and E N. FixU uses time-invarian and sparse undirected communication network simulated by binomial Erdós-Rényi graph (Erdös & Rényi 1959) with parameter
0.4 adding the self-loop edges. Following the setting in Marfoq et al. (2021), we generated a doubly stochastic mixing matrix using the Fast Mixing Markov Chain (Boyd et al. 2003) rule. StoU uses stochastic and undirected network in which any undirected edge 5(0) (() independently realizes at each
step with the probability J,.; E [0, 1]. In StoD each direction of edges 6/0² are independently sampled at probability 5,-5. forming stochastic and directed network. StoD forms the asymmetric expected mixing matrix given by the StoD network is asymmetric representing the communication bias between the clients; some clients may communicate more infrequently than others due to bottlenecks in physical network environments long computation times of local updates due to poor computational resources. We sampled 65.; from the uniform distribution with [0.4, 0.8] both in Stou and StoD
Proposed approaches We solved personalization of classification models using three different formulation: PDBO-MTI,, PDBO-DA, and PDBO-MTI&&DA
For PDBO-DA, we optimize the pseudo sampling rate to recover data augmentation- personal- ization Duan et al. 2019 Zhao al. 2018). PDBO-DA optimize XÇ E RC to learn the label-wise weight vector CSof tmax (A,) E [0, C.. In the inner-problem, the losses of instances labeled as c E [C] are multiplied by the c-th element of the weight vector.
PDBO-MTL is obtained by applying PDBO to FedEM Merfoo et al. (021). PDBO-MTL lets each client train ensemble classifier that outputs weighted average predictions across K 3 of CNNs.
We trained CNN parameters as the inner- inner-probled problem and optimized the hyperparameters X E R to
obtain ensemble weight vector Softmax (A:) 1]
PDBO-MTL&DD combines PDBO-DA and PDBO-MTL optimizing [ ACT e RC+K to obtain both the label-weight and model--wight
For all E [n] in the outer-problem, we ran 20 outer-steps of Adam (Kingma & Ba 2015) iterations with (81, (2) (0.9, 0.999) from the initial hyperparameters Oc, 0x. and Oc for PDBO-DA,
34

---

Under review as a conference paper at ICLR 2023
Table 2: Parameters for the outer-problems in Section 6
Network
Method
L2 reg. rate
Hyper-learning rate
PDBO-DA
0
0.1
FC and FixU
PDBO-MTL
0.01
1.0
0.01 for A
1.0 for A,
PDBO-MTL&DA
0.0005 for X
0.1 for X!
PDBO-DA
0
0.1
StoU and StoD
PDBO-MP MTB
0.01
0.1
0.01 for X
0.1 for X
IDBO-MTL&DA
0.0005 for X
0.1 for A!"
PDBO-MTL, and EDBO--MT&DDA respectively. For Adam optimizer, we adopted different learning rate shown in Table 2 (Hyyperlearning rate). We adopt HGP for FC and FixU setting, and VR-HGP with (a. 3) = (0.9, 0.1) for StoU and St settings. Both HGP and VR-HGP ran M = 200 estimation steps using iteration Eq 4bb) in all the settings. We also made a practical modification in HGP to sample Á (m)) and (mm) together at the single m-th round, which leads the same length of the Neumann series with the half sampling costs of the original HGP, although they are no more unbiased. For all the approaches the cases and for all E [m]. we used the average cross-entropy loss over the local train dataset of the i-th node and L2 regularization loss of X; for F; with the rates shown in Table 2 (L2 reg. rate). We reported the mean test accuracy of an intermediate step that had maximum validation accuracy (i.e., early stopping) which was sampled independently from the train dataset as described in Appendix D
Baseline approaches We compared our approaches with baselines for each communication setting.
For FC and FixU settings, compared with several personalization approaches: personalized model trained only on the local dataset (Local), FedAvg with local tuning (FedAvg+) (Jiang et al.) 2019), Clustered-FL (Sattler et al., 2020). pFedMe (T Dinh al. 2020), and centralized and decen- tralized version of FedEM adopted in Marfoq et al. (2021). We also trained global models using SGP (Nedić & Olshevsky 2016 Assran et al. 20199) and FedProx (Li et al. 2020). From the fact that SGP recovers FedAvg and DSGD on FC and F xU, respectively, we treat them as equivalent approaches. All the approaches on FC and FixU followed the training procedure with epoch- pise communication in Marfoq et al. (2021) while using Eq. (4b) for HGP computation. And any method ran on StoU and StoD adopted the SGP iteration (Eq. 4b)) with T 600 steps, batch size
Ki = 128, L2 regularization with 0.001 decay. For SGP StoU and StoD, we adopted the learning rate a = 0.05 for SGP, Local, and PDBO-DA, 0g = 0.25 for PDBO-MTL and PDBO-MTL&DD Those learning rates were scheduled be multiplied by 0.1 at t 500, 550. As we have baseline ensemble model approach (i.e. FedEM) to be compared to our PDBO-MTL. and PDBO-MTIL DA in StoU and StoD, we also examined our performance improvement from the initial hyperparame- ter. We confirmed PDBO-MTL and PDBO-MTL&DA improved their test accuracy from the initial hyperparameter both in StoU and StoD, confirming the performance gain of PDBO-MTL and PDBO-MTL&DA from SGP were not solely due to their differences in architectures and learning rates.
Dataset and model We adopted the procedure of generating a federated version of EMNIST in Marfoq et al. (202T) except for train and validation split. In our experiments, we consider 10%of the EMNIST dataset as in that were partitioned according to Dirichlet allocation of parameter a = 0.4 over 100 clients in Marfoq al. (2021). We randomly selected 20% of the obtained dataset to make a validation dataset. We use the validation dataset only for the early stopping in outer- optimization of PDBO-DA,
We trained the same CNN in |Mrroq et al. (202T) for all the baselines with a single model and PDBO-DA, and for base-predictor of FedEM, PDBO-MTI, and PDBO-MIL&DA.
MTL, and PDBO-MTL&DA
35

---

Under review as a conference paper at ICLR 2023
Table Comparison of the gradient-based PDBO, CDBO, and CDBO-Local.
Bilevel problem
Communication
No O (dz x dx) and O (dz x dz)
Study
Hyper-gradient
network
communication
in computation
Ours
PDBO
Stochastic directed
GlobalGrrud
Chen et al
2022
CDRO
Static undirected
ClieniGrad
CDBO
Static undirected
LocalGrad
Yang c
207
CDBO
Static undirected
GlobalGrad
Tarzanaph
CDBO
Centralized
GlobalGrad
Lr al
CDBO-Lecal
Centralized
LocalGrad
Lau et al.
20722
2072
CDBO-Local
Static undirected
LocalGrad
20222
CDBO-Loc
Static undirected
LocalGrad
E GRADIENT-BASEE BASED DISTRIBUTED BILEVEL OPTIMIZATION
We compare concurrent studies of distributed bilevel optimization (Chen al. 2022 Tarzanagh et al. 2022 Gao et al. 2022 Yang et al., 2022 Li et al. 2022 Liu et al., 2022] Lu et al. 2022) in terms of problem settings, applicability on communication networks, hyper-gradient value to estimate, and complexity in communication and computation.
Bilevel problem setting We categorize them into two problems (Bilevel problem in Table the consensus distributed bilevel optimization (CDBO) (Chen et al. 2022 Tarzanagh et al. 2022 Gao
al.
2022, Yang et al. 2022) and CDBO with the local inner-problen (CDBO-Local)
2022
Liu et al. 2022
Lu et al. 2022).
CDBO pursue consensus also outer-problem, which can be obtained by imposing A; = X for all j [n] on PDBO outer-problem (Eq. (efft)
1
min
F. (x) (A An) Ad), s.t. x arg min
Eg, [ffe (2 E.)],
(39)
2; 72
A Vj.
m, m.
i=1
Chen et al. (2022); Tarzanagh et al. 2022): Gao et al. )022); Yang et al. (022 applied CDBO to hyperparameter (e.g. L2 regularization coefficient) optimization.
While CDBO-Local also requires consensus in the outer-problem as in CDBO, its inner mmor-problem is a local optimization problem in which optimal parameters are independent of each other client, unlike PDBO and CDBO:
min
F. (x (X:),>)) s.t. x. arg min Egg [&a (z; A:
(40)
A5
Lu al. (2022) demonstrated the ability CDBO-Local problem to handle personalization tasks. However, no client in CDBO-Local can benefit from the others in the inner loop for better general- ization. We note that in our PDBO, both outer and inner problems are optimized from the global information; the manr--aarameter is trained for consensus among the clients and the outer parameter optimized to improve the total performance across all the clients.
Communication networks rected, static undirected, and centralized (Communication network in Table 33)
The communication networks be categorized into stochastic di-
Studies for CDBO (Chen et al. 2022
Gao et al. 2022 Yang et al.) 2022 and CDBO-Local (Liu
et al. 2022 Lu et al. 2022) suppose the communication networks are static and undirected. More
specifically, they assume the weighted mixing matrix (()) to double-stochastio matrix at all time
steps E N for the consensus of DSGD in the outer-problem. (Liu et al.) 2022] Lu ct al. 2022) (i.c.
T; = C ;. Vi, j E (n)), and both in the outer-problem and inner-problem (Chen et al. 2022
Gao et al.
2022 Yang al. 2022 (i.e. æ;, Fr A; Xj. Vi,j E [n]).
Tarzanagh et al. (2022); Liu et al. 2022 addresses the consensus in the outer titter-robblm by adopting
centralized communication settings so that the single global hyperparameter shared among the clients at every step.
Our HGP is the only method that even stochastic and directed communication networks.
36

---

Under review as a conference paper at ICLR 2023
In terms of the consensus, Chen et al. (2022); Gao et al. ) Yang et al. 2022); Liu et al. (2022): Lu et al. (2022) to the stochastic and directed networks by replacing DSGD with SGP for the inner-loop and outer-loop.
relax the assumption of the static undirected communication in
However, in terms the hyper-gradient estimation, we cannot naively replace the communication
networks setting discussed in Section 4.2
Hyper-gradient estimate Both PDBO and CDBO require apper-gradient estimation they involve the interaction of clients in the inner-po amerr-roblemm However, the estimated hyper-gradien varies among the studies, so we categorize them into GlobalGrad, ClientGrad, and LocalGrad (Hyper- gradient in Table R). Our HGP and Yang et al. [ Tarzanagh et al. (2022) aim at estimating the gradient the average outer-objective across the client with respect to the hyperparameter of the client (GlobalGrad), i.c. dx, (x* (A) A) E 1d
Chen et al. (2022) estimate slightly different hyper-gradient, that is, the gradient client outer- objective with respect to the hyperparameter of the client (ClientGrad), i.e. dx, F; (z: (A) A,). Unlike GlobalGrad, ClientGrad only lets the client know how the perturbation on the client's s hyperparameter changes its outer-objective. Thus the gradient step of the client hyperparameter using ClientGrad is not supposed to improve the performance of the others, which is not the case with GrabalGrad.
Gao et al. (2022) estimates the LocalGrad which is equivalent to the hyper-gradient estimation of SGD that estimates dx, Fi (at (A:) A.). LocalGrad differs from ClientGrad because LocalGrad needs no communication because the optimal inner-parameter o; is only parameterized by its hyperparameter
A,
Complexity in communication and computation For fair comparison, we compare the com- plexity of communication and computation between methods that intend to estimate the same hyper-gradient. Note that we only focus on the requirement computation or communication for the full Jacobian matrix as it is dominant in decentralized aeper-gradient estimation (rightmost two columns Table 3).
No approach for LocalGrad involves the full Jacobian computation and communication they can naively adopt efficient algorithms such as backward mode. For GlobalGrad, the algorithm proposed by Yang et al. 2022 is complex both in computation and communication they involve computations and communications of full Jacobian matrix (O (dy x dx)) and Hessian matrix (O (dy x dy)). Tarzanagh et (2022) and our HGP enjoys reasonable complexity because these methods avoid computation and communication of full Jacobian by using Jacobian-vector products.
F DETAILED ALGORITHMS
We provide algorithm Alg. which describes case of PDBO in which outer-problem is solved by local SGD. We also describe the complete algorithms of SGP (Alg. 2 formulated by Eq. (2). HGP (Alg. 4 formulated by Eq. (12). VR-HGP (Alg. 5). formulated in Section 4.2 (Variance reduc-
tion), and the exact recurrent backpropagation (Alg. 3) formulated by Eq. (II) All the algorithms above are expected run locally every i-th client, showing how all clients collaboratively solve the PDBO (Eq. (7) without any central orchestration.
For better understanding, we describe below special notes on several lines in the algorithms that characterize our approach.
Let X be a hyperparameter of the i-th client at the s-th outer-step. PDBO runs multiple outer-steps for 8 O, - from a given initial hyperparameter x Alg. supposes X( is updated locally by SGD step (Line 7 in Alg. 1). As the output of HGP can be seen as an unbiased estimate stochastic gradient, the convergence property of outer steps is simply given by the common convergence property of SGD whose noise is characterized by Theorem [ We can also use other optimizers such as Adam (Kingma & Ba 2015) for outer-steps, as we adopted in our experiments (Section ())
Outer-loop in PDBO
37

---

Under review as a conference paper at ICLR 2023
HGP vs. Exact recurrent backpropagation We explain the difference between HGP (Eq. and exact recurrent backpropagation (Eq. (TT) in algorithmic perspective.
As mentioned in Section 4.2 decentralization of exact recurrent backpropagation is impossible directed communication networks. In exact recurrent backpropagation Line 9 and Line ii Alg B
(m)) from clients such that require client to receive the intermediate backpropagation vector 3
b = 1, indicating the i-th client needs to receive the message from whom the i-th client sent messages. This is possible only when the communication network undirected or synchronized.
(mm) from clients such that In our HGP, Line 9 and Line 17 in Alg. let the i-th client to receive uj
-- g(m) 1, thus any client simply receives the information from all the client who is able to send to
The estimation bias incurred by this simple modification corrected according to the expected sending weight Pij = [ps (6:) and receiving frequency ój.; EE [j]+] estimated through inner
SGP iterations (L.nee and Line 12 Alg.
Note that both HGP and the exact recurrent backpropagation enjoys cheap time complexity since the computations related to Jacobians, 0x yy:: A, 5, (2mm) juj
(m) and 0x, thi (y:: A 5 (2mm) ii
(m)
can be locally computed by Jacobian-vector product.
Algorithm 1: PDBO with SGD ran by the i-th client
Input: y, () 3
(0) (0)
foreach $ = 0 O...., do
// Solve the inner-problem
y. op + Alg
A
// Hyper-gradient estimation
a then
dx F
Alg
y
(T)
(p dz.z) se(m)
HÚP
else
dx, F +- Alg.
y
(pis, 8y.r) sE(m) a.,
IIP
// Run a local SCD outer-step (++1) x( 3,dx, F
return X (5)
38

---

Under review as a conference paper at ICLR 2023
Algorithm 2: SGP ran by the i-th client
Input: y, A
(0)
// Initialize empirical estimates
Pay 400, 0, Vj [n]
85-1 + 0, E
foreach t. O,...,T--1 do
// Sample minibatch and communication edges
Sample ( and 0.00 10:9 6
foreach j s.t. Ri- do
(t)
Send (1) ) y ).,
to the j-th node
Pij + ())
y; ((+1) + 0a,
foreach j s.t. 0j do
(()
10
Receive Pf((O) )49 (1)
(0)
A
(1)
from the j-th node
yi (1+1) += p)((o) )49 Vj }; 5,,5
(t)
Eq.
11
8,.1 1
12
(1+1) += 1b (y: (1) A,, 2s. (10)
13
y;
// Normalize empirical estimates
Pay + Paj. Vj in]
15 8Rرر Toj-i E JE[m]
return y/ (T) (p.y }
39

---

Under review as a conference paper at ICLR 2023
Algorithm 3: (Maybe impossible) Exact recurrent backpropagation ran by the i-th client
Input: y X;
1/ Compute i-th block of 0yF (a"" A) denoted by (c"),
u + 0g Pi (at
// Compute i-th block of OxF (x", denoted by (c");
0 (0)
0 Pi (i)
foreach m 0, .....,,, - do
// Sample minibatch and communication edges
Sample <(2m) and of (22) (2m) 6,2m0)1
foreach j s.l. g(2m) do
L Send u, (m) to the j-th node
2 (m+ + 0ds
foreach j s.t. 5 ((2m) = 1 do
Receive unth (m) from the j-th node
Iteration of (m++)) in Eq. 11
0i (m+1) += P=p(
)xx (m(2m)
yt: A,, Si (2m) ) mm/
sp:
(m+1) 02,33 (v:: Ai (./2m) 0
ui + mmm)
(m)
Sample c: c(2m+l)) and of (2m+1)
10 i-1
(2m+1)
8 222+ DjT
ton
foreach j s.t. 5(2m+1) 1 do to the j-th node
13
(m) Send u;
14
(m++) -Od,
16
foreach j s.l. 0:-]
(22m+)) 1 do
Receive un (m) from the j-th node
17
Iteration of
(m+1)
u; (m+1) += Pij (0. (2 yy, 40 (v): dis Si s(aamt))) (m)
Eq.
(m++)) += By: 2/ (v:: ro ci c(2m+l)) u (m)
(m)
20
return U.
40

---

Under review as a conference paper at ICLR 2023
Algorithm 4: HGP ran by the i-th client
Input: y Ao { (Pij, و5.1) se(n]
1/ compute i-th block of 0gF (x",)) A) denoted by (c"),
u (0) 0g Fi (xt,
// Compute i-th block 0x ())))) denoted (c));
0 + 0 P. (,)
foreach m = 0....,,M
M do
// Sample minibatch and commun i cation edges
Sample 5! (m2m) and d(2m) (0(2m)
6/2m²)T
+-
foreach j 8.1. ((2m) do
L Send u, ((m) the j-th node
2: mm++)) Ods
foreach j s.t. 5(2m) do
Receive uj (m) from the j-th node
Iteration of
(m+1) += Pui 0g. Pi y Ao 5e (22m)
(m)
(m+1) in Eq. 12
10
u
85-1
i (m+ += 0x, ( Ai 5: (2)))
u + v (m)
(m)
11
Sample ;i (2m+1) and of ((2m+1)
10 (2m+1)
8 8zm DjT
12
13
foreach j 01.g
o(2m+1) 1 do to the j-th node
Send u; (m)
2d (m++1) +Od,
15
16
foreach j s.t. 0,-1
1 do
Receive u, fmm) from the j-th node
Iteration of (m++1) in Eq. 12 u
u; (m+1)
+= Bet 0y 4: y Ao cf (22+22) (mm)
18
8,.,
(m++1) 2
+= By: ti : As c. (22m+1)) (m)
19
return (m)
41

---

Under review as a conference paper at ICLR 2023
Algorithm 5: VR-HGP ran by the i-th client
Input: y Ao { (Pij, و5.1) Jeln] ,
1/ compute i-th block of 0g (x", denoted by (c"),
u (0) 0g Fi (xt,
// Compute i-th block 0 (æ*, denoted (c));
v + _x P. (æ),
(0)
c
+ u;
C v; (0)
foreach m = ..... M do
// Sample minibatch and communication edges
Sample < ( and of ((2m) = (0 (2m)
)(2r0))
foreach j s.t. 5(2m) = do
..j
L Send us (mm) w (m) to the j-th node
vi (m)+1) Odi
foreach j s.t. 8 g(2m) = 1 do
10
11
Receive u (m)
w
(m)
from the j-th node
w. (m+1) += a
Bi 0x pi
yē: A. c. mm))
(m))
12
+ (1
- a)
0x yr; di, Si (2m)
2 (m))
13
0/
(m)
+= 02 2b
y X1 5i (2ml)
(m)
2s
(m8)
+ (1 a)
(2x thi
yi: As Se
(2ml
w m))
Sample ci (2m+1) and 0f (2m+t)
10(2m (2m++1)
2m
14
foreach j s.t. b.. g(2m+1)
15
do
L Send u, (m)) un to the j-th node
16
u, (m++) +- Odl
17
un (m++) + Ody
18
19
foreach j s.t. (22+11
Receive u, (m) j-i
1 do
20
w (m)
from the j-th node
u (m+ += Pig 0y si (y:: A, c (2m+1)
(m)
21
u
w (m+1) 1) += B p
Psi 0g. 40: (y: Ass cfam 1)
u (m))
22
1m+ += oy si (i As ci cl2m+t)) mm))
23
(m++) += B (gy, bb (vt: As cf cf2m+1))) ww! mn! (m)
+ c²²) + +1 33) (wo + u (m
(m)
25
return vim)) + c²
42

---

Under review as a conference paper at ICLR 2023
Table
Test accuracy of personalized models on the simulated stochastic directed communication network (StoD) (average clients / 10% percentile).
Dataset
Method
CIFARIO
CIFARI00
Shakespeare
EMNIST
SGP
75.6/ 69.7
38.8/314
28.5 26.0
79.7
Global
SGP-MTL
T3.0/ 64.2
34.4/2.7
27.7 24.0
80.9/73.2
Local
62.5/41.1
33.1/25.1
25.3/17.5
73.7/ 63.8
Local-MTL
64.2//8.3
35.2/28.0
20.5
67.3/
Personalized
PDBO-DA
75.6 70.3
12.1/37.1
38.2/33.7
80.8 / 72.9
PDBO-MTL
73.6/ 65.2
11.4/35.1
38.0/34.9
81.6/ 75.0
PDBO-MTL&DA
77.2 / 73.0
43.3/36.7
37.7/
82.2 74.5
G ADDITIONAL EXPERIMENTS
We conducted personalization benchmarks on different tasks: image classification (CIFAR10 and CIFAR 100 (Krizhevsky] (009)), language modeling (Shakespeare (Caldas et al. 2018: McMahan al. 2017)), and handwritten character recognition (EMNIST (Cohen al. 2017 simulated stochastic directed communication network.
G.1 SETTINGS
We ran our approaches, PDBO-DA, PDBO-MTI, and PDBO-MTL&DA, and Local and SGP for baselines which are explained in Section 6 We adopted the stochastic directed network StoD for simulated communication network with the same setting as in Section For each approach, solve different tasks on corresponding datasets: CIFARIO, CIFAR100, Shakespeare, and EMNIST.
Tasks For image classification on CIFARIO, we distributed samples with the same labels across clients according to symmetric Dirichlet distribution with parameter 0.4, as in Marfoq al. (202T): Wang et al. (019)), to create a federated version. We used 40% the total data as the train and validation dataset
3:1 ratio and the rest as the test dataset. We also tested image classification using CIFAR 100 exploiting the availability of "coarse" and "fine" labels, using a two-stage Pachinko allocation method (Li & McCallum) (0066) as in Reddi al. (2020); Marfoo et al. (202T), distribute 900, 300, and 1800 sized train, validation, test datasets to each client, respectively. Pachinko allocation ran with the parameters adopted in Marfoq al. (2021). For both CIFARIO 10 and CIFARIO0, set n 20 and trained MobileNet-v2 (Sandler et al. 2018), implemented in Torch Vision(Marce) & Rodriguez, 2010 with an additional linear layer.
The Shakespeare dataset was naturally divided by assigning all lines from the same character to the same client as in Marlog al.) (202T); McMahan al. (2017). From 728 characters, we randomly selected n = 20 characters and assigned each of them to a client. We trained two stacked-LSSTV layers with 256 hidden units followed by densely-connen from sequence of 200 English characters as input. The model embeds 80 characters into learnable 8-dimensional embedding space. For each client, we used 80% lines as the train and validation dataset in 3:1 ratio and the rest the test dataset. The lines split from the beginning in the order train, validation, and test to simulate the practical time dependence between datasets.
layer, to predict the next character
The settings of handwritten character recognition EMNIST (Cohen et al. 2017) are described in Section and Appendix D
Approaches For PDBO-DA, PDBO-MTL, and PDBO-MTL&DA, we adopted the same strategies and parameters in Section 6 PDBO-DA optimizes weights vector of loss which elements correspond to labels (characters) of EMNIST, CIFAR1O, and CIFAR100 (Shakespeare). PDBO-MTL optimizes ensemble weights of predictions of models of each task. and PDBO-MTL&DA simultaneously outer-parameters parameters of PDBO-DA and PDBO-MTL. Except for reducing M to 20 rounds for efficiency, adopted the VR-HGP setting in Section
optimizes the outer
43

---

Under review as a conference paper at ICLR 2023
For baselines, due to the absence of personalization methods applicable to stochastic directed communication networks, Local and SGP were adopted. We also trained an ensemble model with uniform prediction weights for both baselines, Local-MTL and SGP-MTL to fairly compare the performance difference between the baselines and our approaches. This allows us to exclude architectural differences from the reasons for performance improvements.
Results and discussions Table shows the average test accuracy with weights proportional to local test dataset sizes. We observed that our approaches PDBO-DA, PDBO-MTL, and PDBO-MTL&D improved accuracy from baselines on all tasks with a few exceptions: PDBO-MTL. on CIFAR 10 and PDBO-DA on EMNIST. EOBO-MTL&DA, out performed on CIFARIO, CIFAR and EMNIST in average accuracy. confirming the simultaneous optimization of different parameters is effective on complex tasks. Even on the next character prediction task on time series data, all of our approaches improved the performance from baselines, indicating our gradient-based PDBO is effective in variety of tasks. Note that the performance improvements did not come from the architectural differences in the models (single model or ensemble model) since PDBO-MTL and PDBO-MTL&II SGP-MTL and Local-MTL. Accuracy at the 10% percentile are also improved from the baselines in all the tasks and approaches, which validated that clients fairly benefited from our personalization.
outperformed
H HYPER-GRADIENT ESTIMATION BY ITERATIVE DIFFERENTIATION
Iterative differentiation is categorized into forward (ITD-Forward) and backward (ITD- Backward) (Franceschi et al., 2017). ITD-Forward and ITD-Backward are advantageous to AID as they do not assume convexity on the loss. In this section, we show that ITD- IDD-Forward and ITD-Backward suffer from physical limitations and large complexity in communications.
ITD-Forward and ITD-Backward compute the hyper-gradient by recursively tracing back all inner- loops, which is performed to obtain the trained parameter, y without requiring y to be the stationary point. To apply IDD-Fowward and -D-BBakwarrd to our setting, we suppose y (T is obtained by T iterations of Eq. 2 Considering iterations for t 0,..., 1, concatenated hyper-gradient Forw-Fo and (TD-Backward can be given as
T-1
d LTD ((x (T)
A) = Σ
D
II s=t+1
A +
(41)
t=
ITD-Forward and ITD-Backward are differentiated by how they compute Eq.
41
Forward mode iterative differentiation (ITD-Forward) Let (+() == -
B IT A0.
To compute Eq. (41}. ITD-Forward updates the matrix ( Band xndy, After initializing by
U7(") Ondx xndy the following iterations for O,.... -1
U(++1) (*) A + (())
(42)
provides the hyper-gradient by d (( (T) A) (K) c. + e².
We then consider decentralized algorithm ran by the i-th client to obtain the i-th block of con- catenated hyper-gradient d.. F(TDFF(x' (x((T) ^) = af X)); Rd By letting the i-th client
update column block matrices bs == (U)) for all k E [n]. a decentralized algorithm of ITD-Forward can be written as follows.
Forward mode iterative differentiation (ITD-Forward)
(1()) Odxxd, Vk E [n]]
U(t-1)
Σ 002 ( (A / + 5(00 (B())
Vk [m] (43)
jE(m]
for 0, 2, ......... T T- -
ITD (T) (T) ()) + Σ U c +
(T)
(44)
jE|m]
44

---

Under review as a conference paper at ICLR 2023
The i-th node can compute the first term of the right hand of Eq. product U (A(t)); ji is always receivable from the j-th client even when edges are directed; when U (A())) Oax xd, otherwise. In the same manner, the second term can be computed receiving (B(t)) ki from the k-th node. Note that when choose to let the i-th client update row block matrices U/4 (U()),
43 because Jacobian
mncobian-matrix matrix
34 + Odxxi xdy the communication edge for receiving exists (of = 1) and U/) (A()) =
for all & E [n]] required to update U(! are not guaranteed on stochastic communication networks.
The difficulty of the forward mode is its communication cost. To update U the any j-th client needs to send U/) (A ) E agdxxd, to the i-th client. Because both dx and dy can be large for practical models such as deep neural networks, communicating Odd x dy) parameters is prohibitive in general.
The other problem is the last step of computing the sum Σje(n) U.j Cj in Eq. (4). This requires communicating with all the clients. The i-th client, therefore, needs to wait for several communication rounds until can receive the Jacobian-vector product ( cz Rdda from all E [n].
Backward mode iterative differentiation (ITD-Backward) the reverse time sequence of ITDD- i.e., ( - T 1,...,0. 0. resulting in having an iteration similar to Eq. (10). Let (*)) - (())a" and ()t)) Σズ=1 ( (s) + c². By initializing u (T) t c²' and e (T) +- c², and by the following iterations for t = T 1....,,,
BackBadwardd computes Eq. 41 in
(t)) (n + +(+11)
(0) t ((+),
we obtain the hyper-gradient estimate as FxF (0). Mathematically, the decentralized algorithm of ITD-Backward for the i-th client can be written as Backward mode iterative differentiation (IDD-Bakwarr)
u f-
(c
(T)
(c))2
v Σソ j== Dinj
(++1)
B((+1))
j
(++1)
+ +
(++1)
(1)
Σラ= ((+1)
(((+1))
(1+1)
u
for t = - 1,T 2, ......
x (()()) ())) x D (0)
In centralized bilevel optimization, iterations of T 1,...,.., are realized by storing the intermediate parameters and indices of every minibatch during the training (Franceschi et al.) 2017) to recover all iterations after T inner-grand geaeiegradeent descent steps. However, when we use SGP iterations for inner-steps, the stochastic network does not guarantee reproduce the communication edges which clients experienced during the training, making the computation the decentralized ---Backward infeasible.
Moreover, ITD-Backward also requires undirected edges similar to the exact recurrent backpropaga- tion pointed out in Section 4.2 (Exact backpropagation requires undirected edges).
We thus conclude that TTD-Backward requires the communication network to be restricted static and undirected in order to function.
45


Reviews:
[{"review_id": "rEryshqS7_", "reviewer": "Reviewer_Mrqc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a gradient-based bilevel optimization that reduces most personalization approaches to the optimization of client-wise hyperparameters. Then the authors propose a decentralized algorithm to estimate gradients with respect to the hyperparameters, which can run even on stochastic and directed communication networks. Empirical results demonstrated that the gradient-based bilevel optimization enabled combining existing personalization approaches which led to state-of-the-art performance, confirming it can perform on multiple simulated communication environments including a stochastic and directed network.", "summary_of_the_review": "This study proposed a gradient-based PDBO, which reduces most personalization approaches to the optimization of hyperparameters possessed by each client. The approach is not practical since the assumption is too strong, and the experiment using EMNIST classification is a bit too simple. ", "strength_and_weaknesses": "Strength: \n- This study proposed a gradient-based PDBO, which reduces most personalization approaches to the optimization of hyperparameters possessed by each client. \n\nWeaknesses: \n- Assumption 2 is a bit too strong to require $y_i^*=y_i^{(T)}$ make it unpractical. The authors should provide some bound estimation for it.\n- Empirical results using the settings of EMNIST classification is a bit too simple.  \n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "i_5vgGOQUD4", "reviewer": "Reviewer_3KYv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a general formulation for learning personalized models in a fully-decentralized context. The problem is formulated as a bi-level optimization problem, where the outer-objective updates the local hyper-parameters given the optimal local parameters of the inner objective. The algorithm for optimizing such problem in a decentralized way is then derived, supposing that the communication graph is fully connected but only a few directed communication edges are active at each iteration.", "summary_of_the_review": "The paper would require a major revision in order for the reader to appreciate its contributions. At this stage, the significance and potential impact of the work are limited because of the poor clarity of the paper and because of the lack of discussion or guarantees on the recovery of the true mixing matrix depending on the choice of random communciation model.", "strength_and_weaknesses": "The paper is very hard to read, and hence it is difficult to assess the contributions and correctness of the derivations.\n\nThese are some of the reasons that make the paper difficult to parse:\n1. Some notation and formulations are inexact, confusing or undefined:\n- In Problem 1 and Problem 5, the index $i$ is used for two different thing: first for indicating the client's parameters to be optimized and then for indexing the terms of the sum. Also the size of $\\xi_i$ is not provided and $p(\\xi_i)$ is not formally defined.\n- Right before Equation 2, it is said that \"The i-th client in SGP updates its weight $\\omega_i$\" but Equation 4 do not update this parameter.\n- Equation 4, the operation $[a \\quad b]$ is not defined. I assumed it was a vector concatenation. Also $p()$ denotes here the message distribution, while it was used before for the local data distribution.\n- (minor) In page 3, end of Section 2, $p_{ij}$ should be replaced by $p()$ ($p_{ij}$ cannot be a doubly stochastic matrix as it is defined as a scalar function).\n- In Assumption 2, the stationary point is denoted by $y^\\star$ while later one is referred to as $y^\\star(\\lambda)$.\n- Overall, the equations are very hard to read because the notation is heavy. The paper would benefit from a simplification. For instance, the update matrices that depend on $y$ (resp. $\\lambda$) should be called in a way that remind the reader of this dependence. The Jacobian is called $A$ and its estimate $u$.\n\n2. It is not clear which criteria are used for determining if a set of parameters should be optimized in the outer or inner loop of the bi-level problem. For instance, why is the label weight vector of PDBO-DA considered a hyper-parameter, hence to be optimized in the outer problem, and not the parameters of the neural network? In the end, all the parameters of the model are specialized to the agent. \n\n3. Little intuition or explanation are provided for supporting the various derivation choices. For instance, why are truncated Neumann series and recurrent back-propagation needed to compute the outer gradient?\n\nFinally, the interplay between agent similarity (usually referred to as mixing matrix) and model performance is never discussed in the paper. No assumptions are then made on the model for drawing directed communication edges, as the paper does not try (or guarantee) to recover the true mixing matrix. However, the performance of a personalized model depends on how often/well an agent communicates with similar agents. If existing works make more assumptions on the graph model, it is to guarantee a good estimation of the true mixing matrix, hence a good estimation of true local models.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "edVNI1HOT2K", "reviewer": "Reviewer_b9iT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of personalized bilevel optimization in a decentralized distributed learning system over stochastic and directed underlying communication networks. The major contribution of this paper is to propose an effective scheme termed HGP to compute the hyper-gradient, i.e., the gradient of hyperparameters in the outer-problem, in a decentralized way. Specifically, this paper first shows the failure of standard backpropagation in hyper-gradient computation on a directed network, then introduces a push-sum communication strategy to tackle the biasness of the hyper-gradient estimate. Moreover, the variance reduction technique is introduced to handle the large variance in the push-sum communication. This paper further derives an upper bound for the estimation error of the proposed method and evaluates it effectiveness empirically. ", "summary_of_the_review": "This paper contributes an effective scheme for hyper-gradient computation in PDBO over stochastic and directed networks, where the use of push-sum communication to make an unbiased estimate is interesting. However, the relevance to previous hyper-gradient computation methods and push-sum communication methods should be explained in more detail, and several assumptions in theoretical analysis need to be justified.", "strength_and_weaknesses": "**Strengths:**\n+ The discovery of the failure of standard backpropagation for hyper-gradient computation over directed networks is interesting, and the use of push-sum strategy sounds novel.\n+ This paper is well-written in general and easy to follow.\n+ The derivation of the estimation error bound is technically sound.\n\n**Weaknesses:**\n- Some assumptions in this paper need to be justified. \nI wonder if the assumption of knowing the receiving frequency in advance is reasonable. Although this paper said that it can be estimated by simulating several rounds, it will bring estimation error to the computation of hyper-gradients. Does the main theorem take such an error into consideration? \nIn addition, please justify Assumption 5, which said that the edges are “undirected” in expectation. I wonder if this assumption still holds for standard (deterministic) directed networks.\n- The relevance to some related work should be clarified.\nSince the proposed method relies on the previously proposed recurrent backpropagation method, HPG should be compared with Grazzi’s work in detail, especially from the theoretical aspect. Specifically, what is the difference between using the sending edges and the receiving edges in principle? Will it bring any difficulty in theoretical analysis? Besides the error bound for VR-HGP, can you provide a bound for the standard HGP and compare it with Grazzi’s? \nAnother related line of work is the push-sum method. It seems that the core innovation of HPG is to introduce such a method to the optimization of the outer-problem. Hence, I wonder what is the main difference from applying the method to the inner-problem as in previous works (perhaps more complex theoretical analysis)? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EqCG22g6mu", "reviewer": "Reviewer_TFeg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies Personalized Decentralized Bilevel Optimization (PDBO). Based on Stochastic Gradient Push (SGP) method, the authors propose Hyper-Gradient Push (HGP) method to estimate the hypergradient and analyze the estimation error of its variance-reduced version (VR-HGP). On top of the hypergradient estimation, they conduct experiments to solve PDBO problems and compare its performance to some existing algorithms.\n", "summary_of_the_review": "Overall, I feel that the proposed method has several benefits than previous ones, but there are quite a few limitations and questions left. I tend to reject this time, but am open to increase the evaluation based on the other reviewers' comments and the authors' response. ", "strength_and_weaknesses": "Pros:\n1. This paper considers the general setting in decentralized training, i.e., the network is stochastic and directed.\n\n 2. The formulation of PDBO is more general than previous papers, as discussed in Section E and Table 3 of the appendix.\n        \n3.  HGP method does not require computing exact Hessian or Jacobian, which is an improvement comparing to previous CDBO papers.\n\nCons:\n\n1. Reformulating Eq. (5) as Eq. (6) is reasonable in practice (and is true under Assumption 2). However, in theory technically speaking the condition $y_i^* = y_i^{(T)}$ in Assumption 2 is unusual. It would be good if the reformulation (Eq. (6)) of Eq. (5) can be theoretically justified (e.g., via some error estimation) without assuming $y_i^*=y_i^{(T)}$ in Assumption 2.\n\n2. (Assumption 2) The authors claim \"To apply implicit differentiation, we introduce the following assumption as in Grazzi et al. (2020)\", but is \"$y_i^* = y_i^{(T)}$\" assumed in Grazzi et al. (2020)? It seems that in Grazzi et al. (2020) they only require $y^*$ to be unique instead of accessibility in $T$ steps. \"$y_i^*=y_i^{(T)}$\" seems to be a strong assumption that is not included in papers about non-asymptotic convergence of bilevel optimization. Besides, carefully analyzing the error incurred by $\\|y_i^* -y_i^{(T)}\\|^2$ is not a trivial problem in bilevel optimization literature. For example, Chen et al. (2022) uses a novel way to deal with this error (see Lemma 3 therein and the order of $T$ in Theorem 1 and Proposition 2) and successfully reduce the sample complexity comparing previous works on bilevel optimization.\n\n3. (Theorem 1) This theorem characterizes the hypergradient estimation error. How can we apply this in real PDBO algorithms to solve (5)? Should we just use $v^{(\\lambda)} + c^{\\lambda}$ as the hypergradient and then use single-agent gradient descent, or should we still run some decentralized algorithms to solve (5)? It is unclear how we should use the estimation (i.e., $v^{(\\lambda)} + c^{\\lambda}$) mentioned in Theorem 1 to run PDBO. It would be better if there is another theorem characterizing the convergence results (e.g., sample complexity) of PDBO using this estimation.\n\n4. (Mini-batch) We need to use mini-batch method (i.e., setting $b$ in Theorem 1 to be large enough) for HGP. However, some of the previous CDBO papers (e.g., Yang et al. (2022)) do not require mini-batch method.\n\nQuestions: \n\n (\"Suppose the i-th client is responsible for computing the i-th block of $u^{(m+1)}$ and $v^{(m+1)}$, ...\", Section 4.2.) What happens after all the agents finish the computation of their own blocks? Is there a central node collecting all the blocks to obtain $v^{(M)}$?\n\nReferences:\n\n[Chen et al., 2022] T. Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient\nmethods for bilevel problems. Advances in Neural Information Processing Systems, 34, 2021.\\\\\n\n[Grazzi et al., 2020] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient\ncomputation. In International Conference on Machine Learning, pages 3748–3758. PMLR, 2020.\\\\\n\n[Yang et al., 2022]S. Yang, X. Zhang, and M. Wang. Decentralized gossip-based stochastic bilevel optimization over\ncommunication networks. arXiv preprint arXiv:2206.10870, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject