SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning
Authors: Yifan Yang
Peiyao Xiao
Kaiyi Ji
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Federated bilevel optimization
federated hypergradient
communication efficiency
system-level heterogeneity
linear speedup

Abstract: Federated bilevel optimization (FBO) has shown great potential recently in machine learning and edge computing due to the emerging nested optimization structure in meta-learning, fine-tuning, hyperparameter tuning, etc. However, existing FBO algorithms often involve complicated computations and require multiple sub-loops per iteration, each of which contains a number of communication rounds. In this paper, we propose a simple and flexible FBO framework named SimFBO, which is easy to implement without sub-loops, and includes a generalized server-side aggregation and update for improving communication efficiency. We further propose System-level heterogeneity robust FBO (ShroFBO) as a variant of SimFBO with stronger resilience to heterogeneous local computation. We show that SimFBO and ShroFBO provably achieve a linear convergence speedup with partial client participation and client sampling without replacement, as well as improved sample and communication complexities. Experiments demonstrate the effectiveness of the proposed methods over existing FBO algorithms.

SimFBO: Towards Simple, Flexible and Communication-effiieee Federated Bilevel Learning
Yifan Yang, Peiyao Xiao and Kaiyi Ji
Department of Computer Science and Engineering University at Buffalo
Buffalo, NY 14260
(yyang99, peiyaoxi, (bb.iji)buufall...om edu
Abstract
Federated bilevel optimization (FBO) has shown great potential recently in machine learning and edge computing due the emerging nested optimization structure in meta-learning, fine-tuning, hyperparameter tuning, etc. However, existing FBO algorithms often involve complicated computations and require multiple sub-loops per iteration, each of which contains number of communication rounds. In this paper. we propose a simple and flexible FBO framework named SimFBO, which is easy to implement without sub-loops, and includes a generalized server- side aggregation and update for improving communication efficiency. We further propose System-leve heterogeneity robust FBO (ShroFBO) as variant of SimFBO with stronger resilience to heterogeneous local computation. We show that SimFBO and ShroFBO provably achieve a linear convergence speedup with partial client participation and client sampling without replacement, as well as improved sample and communication complexities. Experiments demonstrate the effectiveness of the proposed methods over existing FBO algorithms.
Introduction
Recent years have witnessed significant progress in a variety of emerging areas including meta- learning and fine-tuning (11]2), automated hyperparameter optimization [0] reinforcement learning (31 21), fair batch selection in machine learning [54), adversarial learning 766 40), AI- communication networks (27), fairness-aware federated learning (75). etc. These problems share common nested optimization structure, and have inspired intensive study on the theory and algorithmic development of bilevel optimization. Prior efforts have been taken mainly on the single-machine scenario. However, in modern machine learning applications, data privacy has emerged as critical concern in centralized training, and the data often exhibit an inherently distributed nature [70]. This highlights the importance of recent research and attention on federated bilevel optimization, and has inspired many emerging applications including but not limited to federated meta- weeannee (9. hyperparameter tuning for federated learning [25], resource allocation over communication networks (27] and graph-aided federated learning 771, adversarial robustness on edge computing [46), etc. In general, the federated bilevel optimization problem takes the following mathematical formulation.
min ((x) = =((z) = Σ ( (x)() RERY
Σ p. (I,
1=1
s.l. 1f (x) = arg min G(z, y) = Σ p.g. (x,
Σ p. (1, y:
(I)
yER
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

AID IID-based FHE
ITD-based FHE
SimFBO
Locally Update on and Aggregate
Locally Update on x and Aggregate
Generalized
Update
Calculate Hypergradient Estimate
Calculate Hypergradient Estimate
Communication
2V Communication
Rounds
One Communication
Round
FEDIHOP:
Compute Hessian-vactor products
At each rounds
Update on
Simultaneoualy Update on y, V,
local rounda
( rounds
2N Communication Rounds
FEDINN:
Updata on
Compute Hessian-vector products
Figure I: Comparison of AID-based federated hypergradient estimation (FHE) in FedNest 65 (left),
ITD-based FHE in AggITD [69 (middle) and our proposed SimFBO (right) at each iteration.
where is the total number of clients, the outer- and inner-functions fa(r,, y) and gi (x( y) for each client / take the expectation forms w.r.t. the random variables & and Ç., and are jointly continuously differentiable. However, efficiently solving the federated problem in eq. ① suffers from several main challenges posed by the federated hypergradient (i.e., (x)x)) computation that contains the second-order global Hessian-inverss matrix, the lower- and upper-level data and system-level heterogeneity, and the nested optimization structure. To address these issues, [25] 665 24 [22] proposed approximate implicit differentiation (AID)-based federated bilevel algorithms, which applied the idea of non -ederrtdd AID-based estimate in [5] to the federated setting, and involve two sub-loops for estimating the global lower-level solution y (a) and the [69] then proposed AggITD by leveraging the idea of iterative differentiation, which improved the communication efficiency AID-based approaches by synthesizing the lower-level optimization and the hypergradient computation into the same communication sub-loop. However, some limitations still remain in these approaches.
inverse- vector product, respectively.
First, the sub-loops, each with a large number of communication rounds, often compute products a series of matrix-vector products, and hence can complicate the implementation and increase the communication cost.
Second, the practical client sampling without replacement has not been studied in these methods due to challenges posed by the nested structure of AID- and (TD-based federated hypergradient estimators.
Third, as observed in the single-level federated learning 667 in the presence of heterogeneous system capabilities such diverse computing power and storage, clients take a variable number of local updates or use different local optimizers, which may make these FBO algorithms converge to the stationary point of different objective.
1.1 Our Contributions
In this paper, propose communication-effiiies federated bilevel method named SimFBO, which simple to implement without sub-loops, flexible with generalized server-side update, and resilient to sestem-level heterogeneity. Our specific contributions are summarized below.
simple and flexible implementation. As illustrated in Figure I differently from AID- and ITD-based approaches that contain multiple sub-loops of communication rounds at each iteration, our proposed SimFBO is simpler with a single communication round per iteration, in which three updated simultancously for optimizing the lower- and upper-level problems, and approximating the Hessian-ine dessian-invvrse-vve iere--nnveeeeeetooto vector product. SimFBO also includes a generalized server- side update on 2, y, which accommodates the client sampling without replacement, and allows for a flexible aggregation to improve the communication efficiency.
variables y, and
Resilient server-side updates to system-level heterogeneity. In the presence of heterogeneous local computation, we show that the naive server-side aggregation can lead to the convergence to stationary point of different objective. To this end, we propose System-level heterogeneity robust FBO (ShroFBO) building on normalized version of the generalized server-side update with correction, which provably converges to stationary point of the original objective.

---

System-level heterugencity
Partial participation
Without replacement
Linear speedup
Samples complexity
Communication complexity
Algorithm
FedNest [65]
X
x
x
O(e
O(e-))
FBO-AgglITD
x
x
x
O
FedBiO [6
x
x
/
Ole O(c-2nn=)
O
FedMBO
X
/
x
/
0p(-2p11)
Olc
SimFBO (this paper)
X
/
/
O(--p-1)
O(e7))
ShroFBO (this paper)
/
O(c-Pp-1)
O(e-1)
Table I: Comparison of different federated bilevel algorithms in the setting with heterogeneous data. We do not include the methods with momentum-bast acceleration for a fair comparison. P S n is the number of sampled clients in each communication round.
Convergence analysis and improved complexity. As shown Table our SimFBO and ShroFBO both achieve sample complexity (i.e., the number of samples needed reach an e-accurate stationary point) of (0--2p1) which matches the best result obtained by FedMBO (2 but under a more practical client sampling without replacement. Morcover, SimFBO and ShroFBO both achieve the best communication complexity (i.c., the number of communication rounds to reach an e-accurate stationary point) of (c--)), which improves those of other methods by an order of 1-22 Technically, we develop novel analysis in characterizing the client drifts by the three variables, bounding the per-iteration progress in the global y and o updates, and proving the smoothness and bounded variance in local updates via induction, which may be of independent interest.
Superior performance in practice. In the experiments, the proposed SimFBO method significantly improves over existing strong federated bilevel baselines such as AggITD, FedNest and LeedNest in both the i..dd and non-i.i.d settings. We also validate the better performance of ShroFBO in the presence of heterogeneous local computation due to the resilient server-side updates.
2
SimFBO: A Simple and Flexible Framework
2.1 Preliminary: Federated Hypergradient Computation
The biggest challenge in FBO is to compute the federated hypergradient ( due to the implicit and complex dependence of y (z) on æ. Under suitable assumptions and using the implicit function theorem in [8] it has been shown that the (x) takes the form of
(Φ))) Σ p. V.f((,))) v2 Vay ((x,y")[v G(r,v')] Σ (oVo(((,
which poses several computational challenges in the federated setting. First, the second term at the right-hand side contains three global components nonlinear manner, and hence the direct aggregation of local hypergradients given by
Σ pa P. V2 (z "V V,fi(z,)"))
is a biased estimation of (x) due to the client drift. Second, it is infeasible to compute, store and communicate the second-order Hessian-inverse and Jacobian matrices due to the limited computing and communication resource. Although various AID- and ITTD-based approaches have been proposed address these challenges. they still suffer from several limitations (as we point out the introduc- tion) such as complicated implementation, high communication cost, lack of client sampling without replacement, and vulnerability to the system-level heterogeneity. To this end, we propose a simple, flexible and communication-cfiee eefiiiienni FBO framework named SimFBO in this section.
2.2 Federated Hypergradient Surrogate
To estimate the federated hypergradient efficiently, use the surrogate FF(x,, = v.F(z,))-
2 G(z, v) where Rdy is an auxiliary vector. Then, it suffices to find y and efficient
3

---

estimates of the solutions to the global lower-level problem and the global linear system (LS)
v. Go VrF(r, y) that is equivalent solving following quadratic programming.
min R(I,y,0) = u V G(z, v)u vf (x,
Σ Pi V ( ot V
(2)
(x
where R. y, v) can be regarded as the loss function of client for solving this global LS problem. Based this surrogate, we describe the proposed SimFBO framework.
2.3 Simple Local and Server-side Aggregations and Updates
Simple local update. Differently from FedNest [65] and AggITD [69] that perform the lower-level optimization, the federated hypergradient estimation and the upper-level update alternatively in different communication sub-loops, our SimFBO conducts the simple updates on all these three procedures simultaneously in each communication round. In specific, each communication round t first selects a subset
(()) of participating clients without replacement. Then, each active client at ht local iteration simultaneously as
i (C)) updates three variables
Vi (1+++)))
(2.k)
:i :5 c(())) no V. Ra (1 (t.)) (t.K) (168) willd)
Ty Vugi (z) (1.K) (t.A),
Vi
& ((*+T)
(t
aj
(c,A)
(3)
(1,
v fa (L.)) (e.k) (e.b), cl
(t,K) is a client-specific coefficient to increase the where Ty. The correspond to the local stepsizes, a;
flexibility of the framework, <(f.))) 15 ((,,k) are independent samples, and local hypergradient estimate takes the form of fz, v, E) (2, y: E) V 9i (z, y; E)u, The variables y, v and eq. (3). which optimize the lower-level problem, the L. problem and the upper-level problem,
are updated with totally 7:t) local steps. Note that the updates in eq. (3) also allow for parallel computation on z, and y locally.
Local and server-side aggregation. After completing all local updates, the next step is to aggregate such local information both the client and server sides. As shown in eq. 4 each participating
client E (+)) aggregates all the local gradients, and then communicate the aggregations zy I..
and (t)
2z to the server. Then, on the server side, such local information is further aggregated to be
By go and qo which will be used for a subsequent generalized server-side update.
(2)
Σ
(0) P.y. =
Σ
(1.k) V 99
(1.k) (1.K), (I
P
iECIS
iEC()
(t)
Σ
(t.k) V. R. (z) (z(1 (1,00 . (1 (i (...
de
P.d.t
P
iEC!C
iEC())
P.9
11)
Σ
P
(t.k) f. (z (1.)) (1,4) ((
(4)
(
iEC())
k=0
Server aggregation
Local aggregation
[C0 P: is the effective weight of client E C among all participating clients such that i(E p.) 1. Note that in eq. (4), the local aggregation ( (similarly for and x:) can be regarded as a linear combination of all Tocal stochastic gradients, and hence covers a variety of local optimizers such as stochastic gradient descent, comeentum-based gradient, variance reduction by choosing different coefficients a: for E CO), This substantially enhances the flexibility of the proposed framework.
where P. =
N

---

Algorithm SimFBO and ShroFBO
1: Input: initialization y ( ,,'"), number of communication rounds 7', learning rates: client {y Ne: nue 3
server: {790 T/o, 7n local update rounds: {-,")
2: fo 0,1, 2, ..., do
3: for E (+) in parallel do
4:
Vi (t.0) = yyy, 1/
(1.0)
x(0) 24
k = 0, 1,
do
Locally update y
( (6.) and (1*)) simultancously via eq. x.
7:
end for
8:
Client i locally aggregates gradients compute 43 Lu Ix.t via eq. (4)
(2) (1) (0)
9:
Client locally aggregates gradients compute (+)) h(t) ( defined in eq.
10:
end for
11:
Client i (
communicate
(4) (2) (gy,: 4o 95,5)
[ h h
to the server
12:
Server aggregates local estimators compute (1 ( g8d) g using eq. (4
13:
Server aggregates local estimators compute (la 1 ) using eq.
14:
Server updates using eq. S
15:
Server updates using eq. 8
16:
end for
Server-side updates. Based the aggregated gradients qy g and d then perform server- level gradient-based updates on variables x, v and simultaneously as
g(++1) y 70g (++ (u()) - rog!"), ((++1) 21)) 7:0g
(5)
where Yv. and 7/2 are server-side updating stepsizes for v, x and (v) == min { Til J
simple projection on a bounded ball with radius of r. There are a few remarks about the updates eq. (5). First, in contrast to existing FBO algorithms such as [65] 69]. our introduced server-side leveras updates leverage not only the client-side stepsizes Ty V/o Fa. but also the server-side stepsizes Tv Yu and 72. This generalized two-learning-rat paradigm can provide more algorithmic and theoretical flexibility, and provides improved communication efficiency in practice and in theory. Second, the projection Pr(-.) serves as important step to ensure the boundedness of variable (1()) and hence guarantee the smoothness of the global LS problem and the boundedness of the estimation variance in and æ updates, both of which are crucial and necessary in the final convergence analysis. Note that
we do not impose such projection on the local of (t.A) variables because we can prove via induction that they are bounded given the boundedness ()))) (see Proposition
2.4 Resilient Server-side Updates against System-level Heterogeneity
Limitations under system-level heterogeneity. When clients have heterogeneous computing and storing capabilities (e.g., computer server v.s. phone edge computing), an unequal number of local updates often performed such that the global solution be biased toward those of the clients with much more local steps or stronger optimizers. As observed in [67], this heterogeneity can deviate the iterates to minimize different objective function. To explain this mismatch phenomenon, inspired by [57) we rewrite the server-side update on x (similarly for v and y) in eq. as
L
Pad
(1.k)
a 111)
Pilla
(6)
T2 -= py 1lay
1a
1=1
1=1
p(t)
Wi
where a(") (a(
(1, 11
collects all local coefficients of client i, and A
normalizes
the aggregated gradient Zz by 1/lla such that [|b does not grow with the increasing of 7,")
5

---

Although such normalization can help to mitigate the system-level heterogeneity, the effective weight w; can deviate from the true weight p: of the original objective in eq. ① and the iterates converge to the stationary point of different objective that replaces all pt by in eq. (see Theorem I
System-level heterogeneity robust FBO (ShroFBO), To address this convergence issue, we then propose a new method named ShroFBO with stronger resilience to such heterogeneity. Motivated by the normalized reformulation in eq. (6). ShroFBO adopts different server-side aggregation as
h = Σ
Pih (0)
Σ
(0) Pake
N = Σ
(9)
P 2,5
(ECS)
iECU)
SEC
where pú: == [emp Ps and ny (1) ( Accordingly, the server-side updates become
2. are the normalized local aggregations defined in eq. (6).
y(++))= pl vuh"", (++1) (v( rhh!)) ((++)) = pt)
(8)
Differently from eq. (6, select the client weights to be ps enforce the correct convergence to the stationary point of the original objective in eq. ④ as shown in Theorem 2 later.
3 Main Result
3.1 Assumptions and Definitions
We make the following standard definitions and assumptions for the outer- and inner-level objective functions, as also adopted in stochastic bilevel optimization 26
30) and in federated bilevel
optimization 665 69 24].
Definition 1. A mapping F is L-Lipschitz continuous for V2, 2' [F()) - F(=') = L|| 2/|1-
Since the overall objective (xx) is nonconvex, the goal is expected to find e-accurate stationary point defined as follows.
Definition 2. We say z is an e-accurate stationary point of the objective function Φ(x) if B]]V S where a is the oulput of an algorithm.
Assumption 1. For any Rd=, y E Rdd and i E n1, Silrr, v) and g(xx, y) are twice continuously differentiable, and gi(x, y) is (gg-Sronglly convex w.rll y.
The following assumption imposes the Lipschitz continuity conditions the upper- and lower-level objective functions and their derivatives.
Assumption 2. Function fa( 3) is -iipscchit continuous; the gradients ff(x,, y) and (z y) are Tnplipsciitz continuous; the second-order derivatives 2 (x. y) and V2 g y) are To-- Lipschitz continuous; and the third-order derivatives 93 v) is Tip-Lipschitz continuous for some constants Li, L1, L2, L3 > 0.
The Lipschitz continuity of the third-orde derivative is necessary here to ensure the smoothness of 8" (x), which guarantees the descent the iterations of LS function (see Lemma 10), under our more challenging simultaneous and single-loop updating structure. Next, we assume the bounded variance conditions on the gradients and second-order derivatives.
Assumption 3. There exist constants o² oy o' such that [[[VI V1 < oz
g[ y) Vgi(z, y: [|] S og and TE [V v) - V gr, y: 2] S og
Assumption 4. For any x Rd= y Rdd,, there exist constants Byr 2 and ahh such that
Σ we 1 w)1l < B
Σ We W.V o
We have Bgh- 1, and gh when all gi 's are identical.
This assumption of global heterogeneity uses 3yh and ag to measure the dissimilarity of V (x, for all i.

---

3.2 Convergence and Complexity Analysis
can be seen from eq. (2) that the boundedness of necessary to guarantee the smoothness (w.r.t I, v) and bounded variance in solving the local and global LS problems. Projecting the global 2/()) vector and the local u. o((.A), k 2 vectors onto a bounded set can be a feasible solution, but in (t) this case, the local aggregation f.. is no longer a linear combination of local gradients. This can complicate the implementation and analysis, and degrade the flexibility of the framework. Fortunately, we show via induction that the projection of the server-side vector ((f) on a bounded set suffices to guarantee the boundedness of local vectors u.
Proposition 1 (Boundedness of Local v). Under Assumptions i, and local iteration k .,.777 (t) we have r, = [10[(.0)
[ for each iteration t. client
[t.1)
Omin T, where the radius
Li and mmin: mmax are chosen such that O'min S a kt) I mmax.
Ag
Next, we show an important proposition in characterizing the per-iteration progress of the global (4) updates in approximating the solution of a reweighted global LS problem. Let (+) Ell(((
J" (21 denote the approximation error, where T* be the minimizer of Ei=1 w. (x, V.)
Proposition 2. Under the Assumption andd 3
the iterates v(t) solving the global LS problem
generated by Algorithm [ satisfy
B|| (I|o( - -0 (x((++)))) Ell((() - (a(0))11
5(68 7 - 01p² 7op गه (11 (1+ 70) |210|
Σ
10 w
iEC10
+ (1 + (1)p((1)
Yv
4L E (1)
(1))) 2
L2 122
Loe
w
W
4
iECO
4L n
kt)
+ +1++ 8))0
Pa
Wii
||a:
(1) 1/1
E
||a((1)
- x 122 + |10(()
y 11
+ +11000 of [] + (2)))
2hg
E
Σ
wihh
(t)
8/11
- for all 1 E 10,1, 13, &o E 10,1, (0)
l} and i E (1.,,.....)) n), where Wy
Teto we.
Similarly, we can provide a per-iteration process of (()) in approximating the solution T of the reweighted lower-level global function Σ wagi (agi(ar)) Note that such characterizations do not exist in previous studies in single-level or minimax federated optimization with a single objective (e.g.. (57)) because our analysis needs to handle three different lower-level, LS and upper-level objectives. As shown in Proposition 2 the bound involves the client drift term El(((()) (f,b) I (similarly for y, x), the next step is to characterize this important quantity.
Proposition 3. Under Assumption
and 2
the local iterates client drift of of is bounded
Σ
(1, Elll (t.R) u 11 < n0To
1a
1m1
1=1
for all t E {0, 1,.,, T - 1}, E {0, 1,.... :q 1} and i E (1,2, n). We define F = -E Te/n ? (g) + amax (L3 + r 47).
and 0i := 2 (0²
+
+
It can be seen from Proposition 3 that the bound on the client drift of the local updates on v is proportional to 7h and ||a.") [11- Since Omin S <a(t.)) O'maxx ||a (1) || is proportional to the number
(1) of local steps. Thus, this client drift is controllable by choosing 7/ and the local stepsizes 1) properly. Then, combining the results in the above Proposition I 2 and under a proper Lyapunov function, we obtain the following theorem. Let P [c(t]] be the number of sampled clients.
7

---

Theorem 1. Define
F(x, Vy) as the objective function by replacing Pi in with wi- and Hare satisfied. The iterates by SimFBO in Algorithm satisfy
Suppose Assumptions
2
min R
V
(z
o
Mi (n P)
T PT
O O(M2
M3 FT
n
PFT
partial participation
fidl synchromization error
local updates evror
where Yas Thp Ya Thy are set in eq. (38) and MI, M2, M3 are defined by eq. 400 in appendix.
For the full client participation (i... P Tt), the sample complexity is FT = On 2), and the number of communication rounds T = ). For partial client participation, the sample complexity is FT = DPP-1c2) and the number of communication rounds is O(P-1(3)
First, when set F (1), Theorem I shows that SimFBO converges to a stationary point of an objective function & (xx) with a rate of O /PT + 7). which, to the best our knowledge, is the first linear speedup result under partial client participation without replacement. Note that without system- p.lle."
level heterogeneity, i.c., ||a]"|
||an") I|. we Σラ= Ps [
Ps, and hence SimFBO
converges to the stationary point of the original objective in eq. ① However, in the presence of system-level heterogeneity, SimFBO may converge to the stationary point of different objective. Second, when nearly full clients participate, the partial participation error approximately zero. Then we can see that setting local update round 7 to its upper-bound results in the best performance.
Theorem 2. Define ((x) = F(x, y²) eq. (1. Suppose Assumptions iterates generated by ShroFBO Algorithm satisfy
and 3 are satisfied. The
min E (ola (0 =0(
P
Mi Mi(n
V PT + (My
M3
(10)
n
PFT
by setting the same server-side and local stepsizes and M1. M2 and M3 as in Theorem 7 For full client participation, the sample complexity is FT O(n-1c22) and the number of communication rounds is T = Oc--)). For partial client participation, the sample complexity is FT = O and the number of communication rounds is T O(P-1e
In Theorem
we show that even under the system-leve heterogeneity, ShroFBO can converge to the original objective function with the same convergence rate as SimFBO. This justifies the design principle of robust server-side updates.
Related Work
Bilevel optimization. Bilevel optimization, first introduced by [3] has been studied for decades.
A class of constraint-basee bilevel methods was then proposed [20 16 [59 61]. whose idea is to replace the lower-level problem by the optimality conditions. Gradient-based bilevel algorithms have attracted considerable attention due to the effectiveness in machine learning. Among them,
AID-based approaches 8 51 38 leveraged the implicit derivation of the hypergradient, which
was then approximated via solving a linear system. ITD -ased approaches [45] 12 56 [7]
approximated the hypergradient based on automatic differentiation via the forward or backward mode. A group of stochastic bilevel approaches has been developed and analyzed recently based on Neumann series (5) 26 M, recursive momentum 72, 23 19 and variance reduction [72] 7 etc. For the lower- level problem with multiple solutions, several approaches were proposed based on the upper- and lower-level gradient aggregation [55] 43 34], barrier types of regularization A1 39], penalty- based
formulations (58), primal-dual technique 62 and dynamic system-based methods (4).
Federated (bilevel) learning. Federated Learning was proposed to enable collaborative model train- ing across multiple clients without compromising the confidentiality of individual data 32 60 49
As one of the earliest methods of federated learning [47. FedAvg has inspired an increasing number of approaches to deal with different limitations such as slower convergence, high communication cost and undesired client drift by leveraging the techniques including proximal regularization (37), periodic variance reduction the convergence of FedAvg and its variants has been analyzed in various settings with the homo-
48 28
proximal splitting [50]. adaptive gradients [53]] Theoretically,
gencous [63] 68, 64 heterogeneous datasets [37] 66 48 29
[67] analyzed the impact of the
8

---

system-level heterogeneity such as heterogeneous local computing on the convergence. extended the analysis and the methods to the minimax problem setting.
57 further
Federated bilevel optimization has not been explored well except for a few attempts recently. For example, [4 [5 proposed momentum-based bilevel algorithms, and analyzed their convergence in the setting with homogeneous datasets. In the setting with non-i.i.d. datasets, [65] and (24] proposed
FedNest and FedMBO via AID-based federated hypergradient estimation, and (69 proposed an
ITD-based aggregated approach named Agg-ITD. Momentum-basee techniques have been also used
by [22 36) to improve the sample complexity. Moreover, there are some studies that focus on other distributed scenarios, including decentralized bilevel optimization 6 73 44), asynchronous bilevel optimization over directed network [74], and distributed bilevel network utility maximization (2
MNSSTUUUP un Ltd
CPAR-S CAN on
Than accuracy 5
LFedkest
LFediest
1/4
TD
Apo
ADOITO
SmmtUU
Simt
ml
600
600
2.00 180
100
Figure 2: Comparison among our SimFBO, FBO-AggITD 669, FedNest 65 and LFedNest 65 The left and middle ones plot the training accuracy v.s. # of communication rounds on i.i.d. MNIST datasets with MLP networks, and the right one plots the training accuracy v.s. # of rounds on i..dd. 10 datasets with 7-layer CNN.
Tes:
Tes:
LFedilest Rechiest
LFekiiest Feckest
2
FRO Agg
FRD 3TFFD
FRO-AgHHTD
SimFBQ
SmF30
SmmFBO
608 Communication
1280
Commun
Figure Comparison of different methods: the test accuracy v.s. of communication rounds.
5 Experiments
In this section, we perform two hyper-represenntaion experiments to compare the performance of our proposed SimFBO algorithm with FBO-AgeITD [69]. FedNest (69), and LFedNest [65], and validate the better performance of ShroFBO in the presence of heterogeneous local computation. We test the performance on MNIST and CIFAR datasets with MLP and CNN backbones. We follow the same experimental setup and problem formulation as in 65 69 specifications can be found in Appendix A.I
The details of all experimental
Comparison to existing methods. The comparison results are presented in Figure and Figure It can be seen that across different datasets and backbones, our proposed SimFBO consistently converges much faster than other comparison methods, while achieving much higher training and test accuracy. We do not plot the curves of FedNest and L.edNestt on CIFAR and CNN, because they are hard to converge under various hyperparameter configurations using their source codes.
Performance under heterogeneous local computation. We now test the performance in the setting where a total of 10 clients perform variable number of local steps. This is to simulate the scenario where clients have heterogeneous computing capabilities and hence can perform an uneven number of local updates.
this experiment, we choose the number 7; of the client i's local steps from the set {1.... 10) uniform at random. As shown in Figure the proposed ShroFBO method performs the best due to the better resilience to such client heterogeneity. We also compare the convergence rate of our proposed SimFBO, FedNest and FBO-AggITD w.r.t. running time. The results are provided in F All the settings for different algorithms are the same as in Appendix A.22] It can be seen that the proposed SimFBO still converges fastest with higher test accuracy in terms of running time.
9

---

Try exmple on ronil rata
Tr exmple on rovlld tata
LFedNest
Ag0-Agg
Test accuraiyy
SimF80
LFedNest
FedNest
AgalTD
SimFa0
SoroFBO
Communication
300
Commun rounds
Figure 4: Comparison among different algorithms in the presence of heterogeneous local computation.
MWST-MPP
UNISTALP comparison non-lvd.
Tost accuracy
Test accuracy
FedNest
FodNest FBO-AgglTD
F30-AggITD
SimFB0
SimFB0
Time (s]
Time [s]
Figure 5: Time Comparison among different algorithms.
6
Conclusion
In this paper, we propose a simple and communication-efiie federated bilevel algorithm named SimFBO and its variant ShroFBO with better resilience to the system-level heterogeneity. We show that both SimFBO and ShroFBO allow for more practical client sampling without replacement, and achieve better sample and communication complexities. Experiments demonstrate the great promise of the proposed methods. We anticipate that the proposed algorithms and the developed analysis can be applied to other distributed settings such decentralized or asynchronous bilevel optimization, and the algorithms may be useful in applications such as hyperparameter tuning or fine-tuning in federated learning or Al-aware edge computing.
Acknowledgement
The work is supported in part by NSF under grants 2326592 and 231 1274.
References
[1] M. Arbel and Mairal. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprini arXiv:2 2021.
[2] D. Basu, D. Data, C. Karakus, and S. Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019.
[3] J. Bracken and J. T. McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44, 1973.
[4] T. Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34:25294-25307. 2021.
[5] Т. Chen, Y. Sun, and W. Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2 2021.
[6] X. Chen, Huang, and S. Ma. Decentralized bilevel optimization. NeXiv:206.005600 2022.
arXiv preprint
10

---

[7] M. Dagréou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint arXiv:2201.13409, 2022.
[8] Domke. Generic methods for optimization- modeling. In Artificial Intelligence and Statistics, pages 318-326 PMLR, 2012.
[9] A. Fallah, A. Mokhtari, and A. Ozdaglar. Personalized federated learning: A meta-learning approach. arXiv preprint arXiv:2002.07949 2020.
[10] M. Feurer and F. Hutter. Hyperparameter optimizatinn..... Automated machine learning: Methods, systems, challenges, pages 3-33, 2019.
[11] C. Finn, P. Abbeel, and S. Levine. Model-agnoste meta-leaming for fast adaptation of deep networks. In International conference on machine learning, pages 1126-1135 1135. PMLR, 2017.
[12] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pages 1165- 1173. PMLR, 2017.
[13] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[14] H. Gao. On the convergence of momentum based algorithms for federated stochastic bilevel optimization problems. arXiv preprint arXiv:2204. 13299, 2022.
[15] S. Ghadimi and M. Wang. Approximation methods for bilevel programming, arXiv preprint arXiv: 02200.00246,..... 2018.
[16] S. Gould, B. Fernando, A. Cherian, P. Anderson, R. S. Cruz, and E. Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint arXiv: 160vv:1607.05447 2016.
[17] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning, pages 3748-3758. PMLR, 2020.
[18] A. Griewank and A. Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008.
[19] Z. Guo, Q. Hu, L. Zhang, and T. Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXin:2105.022666 2021.
[20] Hansen, B. Jaumard, and Savard. New branch-and-bound rules for linear bilevel program- ming. SIAM Journal scientific and Statistical Computing, 194-)111941221,,, 1992.
[21] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05//0, 2020.
[22] Huang. Fast adaptive federated bilevel optimization. arXiv preprint arXiv:2211.01122 2022.
[23] F. Huang and H. Huang. Biadam: Fast adaptive bilevel optimization methods. arXiv preprint arXiv:2106.1 11396, 2021.
[24] M. Huang, D. Zhang, and K. Ji. Achieving linear speedup non-iid federated bilevel learning. arXiv preprint arXiv:2302.05412, 2023.
[25] Y. Huang, Q. Lin, N. Street, and S. Back. Federated learning on adaptively weighted nodes by bilevel optimization. arXiv preprint arXiv:2207.1073: 2022.
[26] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference machine learning, pages 4882-4892, PMLR, 2021.

---

[27] K. Ji and L. Ying. Network utility maximization with unknown utility functions: A distributed, data-driven bilevel optimization approach. arXiv preprint arXiv:2301.0180/ 2023.
[28] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[29] A. Khaled, K. Mishchenko, and Richtárik, First analysis of local gd on heterogeneous data. arXiv preprint 1tXih::109.04715, 2019.
[30] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang. and Z. Yang. A near-optimal algorithm for stochastic bilevel optimization via nouble-momentum. Advances in neural information processing systems, 34:30271-30283 2021.
[31] V. Konda and J. Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
[32] J. Konečný, B. McMahan, and D. Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint / 2015.
[33] Y. LeCun, I.. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(11):2278-222) 1998.
[34] Li, B. Gu, and H. Huang. Improved bilevel model: Fast and optimal algorithm with theoretical guarantee. arXiv preprint arXiv:2009 000X::0009.00690,,, 2020.
[35] J. Li, F. Huang, and H. Huang. Local stochastic bilevel optimization with momentum-based variance reduction. arXiv preprint arXiv:2205.0/608, 2022.
[36] Li, F. Huang, and H. Huang. Communication--fficieenn federated bilevel optimization with local and global lower level problems. arXiv preprint arXiv:2302.0670) 2023.
[37] Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429 450, 2020.
[38] R. Liao, Y. Xiong, E. Fetaya, L. Zhang, K. Yoon, X. Pitkow, R. Urtasun, and R. Zemel. Reviving and improving recurrent propaaappa,,,.nn In International Conference on Machine Learning, pages 3082-3091. PMLR, 2018
[39] B. Liu, M. Ye, S. Wright, P. Stone, and Q. Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 01117228-77666 2022.
[40] R. Liu, J. Gao, J. Zhang, D. Meng, and Z. Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. JEEE Transactions Pattern Analysis and Machine Intelligence, 44(12): 10045-00667 2021.
[41] R. Liu, X. Liu, X. Yuan, S. Zeng, and Zhang. A falue-function-based interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning, pages 6882-6892. PMLR, 2021.
[42] R. Liu, Y. Liu, S. Zeng, and J. Zhang. Towards gradient-based bilevel optimization with non- convex followers and beyond. Advances in Neural Information Processing Systems, 34:8662- 8675, 2021.
[43] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generic first-order algorithmic framework for bi-le programming beyond lower-level singleton. In International Conference on Machine Learning, pages 6305-6315. PMLR, 2020.
[44] S. Lu, X. Cui, M. S. Squillante, B. Kingsbury, and L. Horesh. Decentralized bilevel optimization for personalized client learning. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5543-5547. IEEE, 2022.
12

---

[45] D. Maclaurin, D. Duvenaud, and R. Adams. Gradient- Grasee hyperparameter optimization through reversible learning. International conference on machine learning. pages 2113-2122. PMLR, 2015.
[46] Manoharan, R. Walia, C. Iwendi, T. A. Ahanger, S. Suganthi, M. Kamruzzaman, S. Bourouis, W. Alhakami, and M. Hamdi. Svm-based generative adverserial networks for federated learning and edge computing attack model and outpoising. Expert Systems, page e c13072, 2022.
[47] B. McMahan, E. Moore, D. Ramage, S. Hampson. and B. A. y Arcas. Communication-cfficin learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273 1282. PMLR, 2017.
[48] A. Mitra, R. Jaafar, G. J. Pappas, and H. Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34:14606-14619 2021.
[49] M. Mohri, Sivek, and A. T. Suresh. Agmostic federated learning. In International Conference on Machine Learming, pages 4615-4625. PMLR, 2019.
[50] R. Pathak and M. J. Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. Advances in neural information processing systems, 33:7057-7066, 2020.
[51] Pedregosa. Hyperparameter optimization with approximate gradient. In International conference machine learning, pages 737-746. PMLR, 2016.
[52] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
[53] S. Reddi, Z. Charles, M. Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
[54] Y. Roh, K. Lee, S. E. Whang, and C. Suh. Fairbatch: Batch selection for model fairness. In International Conference on Learning Representations, 2021.
[55] S. Sabach and S. Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 2702):440-600, 2017.
[56] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated back pookprropagttion for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 1732. PMLR, 2019.
[57] Sharma, R. Panda, and G. Joshi. Federated minimax optimization with client heterogeneity. arXiv preprini arXiv:2302.04224, 2022.
[58] H. Shen and T. Chen. On penalty-based bilevel gradient descent method. arXiv preprint arXiv:2302.05185 2023.
[59] C. Shi, J. Lu, and G. Zhang. An extended kuhn tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(():51-63, 2005.
[60] R. Shokri and V. Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310-1321, 2015.
[61] A. Sinha, P. Malo, and K. Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-295, 2017.
[62] D. Sow, K. Ji, 7. Guan, and Y. Liang. constrained optimization approach to bilevel optimiza- tion with multiple inner minima. arXiv preprint arXiv:2203.01 2022.
[63] U. Stich. Local sgd converges fast and communicates little, arXiv preprint arXiv: 180.x:8800007666 2018.
13

---

[64] S. U. Stich and S. P. Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. The Journal of Machine Learning Research, 2111:9613-964) 2020.
[65] D. A. Tarzanagh, M. Li, C. Thrampoulidis, and S. Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. International Conference on Machine Learning, pages 21146-21 21179. PMLR. 2022.
[66] J. Wang and G. Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. The Journal of Machine Learning Research, 22(1):9709-9758, 2021.
[67] Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:7611-7622 2020.
[68] Z. Wang, K. Balasubramanian, S. Ma, and M. Razaviyayn. Zeroth-order algorithms for nonconvex minimax problems with improved complexities. arXiv preprint arXiv:2001.074 00.099999 2020.
[69] Xiao and K. Ji. Communication-eficie federated hypergradient computation via aggregated iterative differentiation. arXiv preprint arXiv:2302.044900 04969, 2023.
[70] E. P. Xing, Q. Ho, P. Xie, and D. Wei. Strategies and principles of distributed machine learning on big data. Engineering, 2(2):179-19)) 2016.
[71] P. Xing, S. Lu, L. Wu, and H. Yu. Big-fed: Bilevel optimization enhanced graph-aided federated learning. IEEE Transactions on Big Data, 2022.
[72] Yang. K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 14:1367--3362, 2021.
[73] S. Yang, X. Zhang, and M. Wang. Decentralized based stochastic bilevel optimization over communication networks. arXiv preprint arXiv:2206. 10870, 2022.
[74] Yousefian. Bilevel distributed optimization in directed networks. In 202/ American Control Conference (ACC), pages 2230-2235. IEEE, 2021.
[75] Y. Zeng. H. Chen, and Lee. Improving fairness via federated learning. arXiv preprint 2021.
[76] Y. Zhang, G. Zhang. P. Khanduri, M. Hong, S. Chang, and S. Liu. Revisiting and advancing fast adversarial training through the lens bi-level optimization. International Conference on Machine Learning, pages 26693-26712. PMLR, 2022.
14


Reviews:
[{"review_id": "Oq8xyUm4ud", "reviewer": "Reviewer_8pmc", "summary": "The paper addresses the bilevel optimization problem in the federated learning context. The authors propose a novel gradient-based algorithm that effectively updates the arguments in both the inner and outer optimization problems simultaneously. Additionally, the paper extends this algorithm to handle data heterogeneity, making it more relevant for real-world scenarios. The theoretical analysis on the convergence rate of the proposed approach is also provided. While the content itself is interesting, the manuscript requires substantial proofreading and improvements before it is ready for peer review.", "questions": "See the questions in the above section.\n", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The paper demonstrates a comprehensive treatment of the bilevel optimization problem in federated learning. Notably, the proposed method addresses data heterogeneity, contributing to the algorithm's practical applicability.\n\n- The inclusion of a comparison with existing methods in Table 1 is valuable. ", "weaknesses": "- There are still rooms to improve the presentation of the paper.\n\n    - The paper suffers from unclear or inconsistent mathematical notations. E.g.\n\n        - In defining the objective functions, a bracket should be used otherwise the meaning is not correct. Eg. in (1), \n        $$\\min \\{\\Phi(x) = F(x.y^*(x))\\}$$\n        The objective functions defined elsewhere in the manuscript has the same issue.\n\n        - In (3), the notations $\\zeta_i$ and $\\xi_i$ are not defined. Similarly in (4). It is important to highlight they corresponds to local mini-batch dataset, as they make a difference in the proof of Lemmas in the appendix.\n        \n        - In assumption 1, it is better to use $\\mu_g$ for the $\\mu$-strongly convex constant as it is used elsewhere.\n                \n        - The notation $\\delta_t'$ in Propostiation 2 is not defined. Though the reviewer find the definition in the appendix, the notation should be defined when it is firstly used. Similarly for other notations such as $\\bar\\tau$ in Theorem 1.\n\n        - In Appendix $C$, Lemma $2$ is w.r.t. the function $G$ not $g$.\n\n        \n    - There are numerous typos and missing details in the appendix. E.g.\n\n        - In Proof of Lemma 3, the statement \"step 6 of algorithm (1)\" does not match the algorithm description.\n\n        - The proof of Lemma 4 missed some key steps and hence is not clear.\n        \n        - In the proof of Lemma 8 in L569. The first equality should have expectation on the LHS and the second equality should be $\\leq$.\n        \n    - Presentation\n\n        - The paper could benefit from providing concrete examples of bilevel optimization after (1) to underscore the problem's importance.\n\n        - The main text should reference where readers can find proofs for propositions.\n\n        - The description of the experimental setting is vague; a clearer explanation of why the studied problem is a bilevel optimization problem is needed.\n\n\n- The novelty in the proposed method is limited.\n    - The key method in Section 2.3 is a distributed version of the centralized gradient-based bilevel optimization method.\n\n    - The method for hetergoeneity is a simple generalization of FedNova.\n\n- Since the reviewer thinks the proposed method is a simple extension of existing algorithms under federated learning setting, the convergence rate analysis of the proposed algorithm is therefore a key contribution of the paper. There are several issues in technical details.\n    \n    - In Lemma 5, what is the definition of $\\nabla R_i(x,y,v)$? Is it only the partial derivative w.r.t. $v$? Otherwise the gradient is not well defined since $g_i$ and $f_i$ are only assumed to be twice differentiable.\n    \n    - Due to the unclear definition of the notations and many tiny typos in the manuscript, the proof is not very easy to follow. For example, Lemma 10 is a key lemma for the proof of theorem 1, but it is not clear why the first step (24) holds since $\\delta_t$ is not defined. Therefore, it is hard for the reviewer to check whether the proof is correct or not. \n\n    - In the proof of the theorem 1, it is not clear to the reviewer how the projection of $v$ is reflected in the proof of the theorem.\n     \n    \n    - The proof of Theorem 2, it does not make sense to the reviewer that \"taking $w_i=p_i$\" in L662.\n\n\n- It would greatly improve the quality of the paper if the summary of the results in Table 1 can be empirically demonstrated in the experiment.\n\n\nReference:\n\n[1] Gradient-based Bi-level Optimization for Deep Learning: A Survey", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer 8pmc for the time and valuable feedback! \n\n**Q1: Unclear notations, typos, missing details and other presentation issues.**\n\n**A:** Sorry about the confusion and missed details. Also thanks for pointing them out for us! We will definitely follow your suggestions to improve the presentation, double-check the typos and make the notations consistent.\n\n**Q2: The novelty of the proposed method is limited. The key method in Section 2.3 is a distributed version of the centralized gradient-based bilevel optimization method.**\n\n**A:** We respectfully disagree with this point. Our distributed method in Section 2.3 contains substantial new components that do not exist in the distributed version of the centralized gradient-based bilevel method. First, we include a generalized server-side aggregation and update to guarantee convergence, improve efficiency, and deal with the harder system-level heterogeneity. Second, we include a server-side projection on $v$ updates to ensure the local $v$ boundedness (via induction) and the convergence under the client drift. These key features also facilitate the design and analysis of ShroFBO under the system-level heterogeneity. \nNote that all previous federated bilevel methods do not have these new features.\n\n**Q3: What is the definition of** $\\nabla R_i(x,y,v)$ **? Is it only the partial derivative w.r.t.** $v$ **?**\n\n**A:** Yes, it is the partial derivative w.r.t. $v$. We will revise the notation to $\\nabla_v R_i(x,y,v)$. \n\n**Q4: Lemma 10 is a key lemma for the proof of theorem 1, but it is not clear why the first step (24) holds since is not defined.**\n\n**A:** $\\delta_t$  is a positive tunable parameter that is decided later in the final convergence rate analysis, as can be seen in (30). We will clarify this in the revision. \n\n**Q5: In the proof of theorem 1, it is not clear to the reviewer how the projection of** $\\delta_t$ **is reflected in the proof of the theorem.**\n\n**A:** The projection of $\\delta_t$ is reflected in two places of the proof. First, we use this server-side projection to guarantee the boundedness of $v^{(t)}$ for all $t$ such that we can show via induction that the local iterates $v_i^{(t,k)}$ are bounded. Second, the projection appears in characterizing the per-iteration estimation gap $\\mathbb{E}\\\\|v^{(t+1)} - v^*(x^{(t)})\\\\|^2$ in $v$ updates via the following inequality:\n$\\mathbb{E}\\\\|v^{(t+1)} - v^*(x^{(t)})\\\\|^2 = \\mathbb{E} \\\\| \\mathcal{P_r}(v^{(t)} - \\rho^{(t)} \\gamma_v \\sum_{i \\in C^{(t)}} \\widetilde{w_i} h_{v,i}^{(t)}) - v^*(x^{(t)}) \\\\|^2 \\leq \\mathbb{E}||v^{(t)} - v^*(x^{(t)}) - \\rho^{(t)}\\gamma_v\\sum_{i \\in C^{(t)}}\\widetilde{w_i} h_{v,i}^{(t)}||^2.$\nHere, the inequality uses the non-expansive property of projection on a convex set and $v^*(x^{(t)})=\\mathcal{P}_r(v^*(x^{(t)}))$ due to the boundedness of $v^*(x^{(t)})$. We will clarify this in the revision.  \n\n**Q6: In the proof of Theorem 2, it does not make sense to the reviewer that \"taking** $w_i = p_i$**\" in L662.**\n\n**A:** Sorry for the confusion. Note that the server-side aggregations in (7) for ShroFBO replace the weights $w_i,i=1,...,n$ of the aggregations in (6) for SimFBO by $p_i,i=1,...,n$. It is equivalent to setting $w_i$ to be $p_i$ in the analysis of Theorem 1 for SimFBO. We will clarify this and directly use $p_i$ in the proof of the Theorem in the revision. \n\n"}, {"review_id": "b9a4H0mwPL", "reviewer": "Reviewer_MEss", "summary": "This work studies the federated bilevel optimization, where the lower- and upper-level objectives are defined over all clients. Since the lower-level solution is the minimizer of the average of all client objectives (i.e., in a global manner), the main computational challenge is to compute the global hypergradient with second-order derivatives. This work provides a simple and effective approach named SimFBO to this problem. It contains simultaneous updates on all three variables at each client, a generalized server-level update. It has no subloops. A variant of SimFBO called as ShroFBO is also proposed to deal with the heterogeneous client computation. \nTheoretical convergence is provided for these two approaches.  Experiments seem to show the proposed methods are much better than other baselines.\n", "questions": "1. Does the $1/\\epsilon$ communication complexity hold for both partial and full client participation? Per my reading, it only holds for the full participation case, right? I think the authors should make this clearer. \n\n2. From the experiments, it is not clear to me how many local steps are used for the proposed methods? Also it would be great to investigate the impact of number of local steps on the final convergence rate and test accuracy. \n\n3. Is it possible to incorporate the variance reduction or momentum-based estimators to improve the sample complexity to $O(\\epsilon^{-3/2})$ under the current simple framework? It would be great to include some discussions on this. ", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The work is well motivated and easy to follow. Finding a simple but effective solution to a complicated problem in federated setting is a interesting and important topic. \n\n2. The algorithm design is new, i.e., simultaneous local updates, aggregation, and generalized server-side operation. The simple structure will be useful in practice. But such simple structure seems to be not easy to prove in the federated setting. Specifically, it is usually challenging to guarantee the boundedness of $v$ variable. The authors show this via induction that as long as the server-side $v$ is bounded, the local $v$ is bounded as well. This seems to be new.\n\n3. Nonasymptotic convergence is provided and seems to be significant. It allows for client sampling without replacement, linear speedup, achieves the $1/\\epsilon$ communication complexity. In contrast, existing studies require clients to be selected with replacement due to the complex hypergradient construction. This work achieves the linear speedup without replacement, and as well as optimal communication complexity. These are new results in federated/distributed optimization. ", "weaknesses": "For the experimental part, can the authors explain why FedNest and AggITD perform poorly over CNNs? Is it due to a non-proper hyperparameter tuning or something else? More details should be provided. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer MEss for the time and valuable feedback! \n\n**Q1: Why FedNest and AggITD perform poorly over CNNs?**\n\n**A:** As we illustrate in Figure 1, FedNest and AggITD both contain one or more sub-loops of communication rounds in each outer iteration, which leads to a high per-iteration computational cost as well as a much slower convergence rate. In addition, we show that the generalized server-side aggregations and updates are helpful to improve communication efficiency. However, FedNest and AggITD do not have such features. We will clarify this in the revision. \n\n**Q2: Does the **$1/\\epsilon$** communication complexity hold for both partial and full client participation?**\n\n**A:** Great question! The $1/\\epsilon$ communication complexity holds for full client participation. We will clarify this in the revision. \n\n**Q3: From the experiments, it is not clear to me how many local steps are used for the proposed methods. Also, it would be great to investigate the impact of the number of local steps on the final convergence rate and test accuracy.**\n\n**A:** For the experiments shown in Figure 2 and 3, we set all numbers of local steps of our SimFBO method to one because we found that more local steps only improved the performance and convergence rate marginally. In particular, we found that the performance and efficiency of SimFBO were improved only slightly when increasing the number of local steps from 1 to 5, whereas further increasing the number of steps degraded the performance due to the larger client drift. We will include such a figure in the revision. \n\n**Q4: Is it possible to incorporate the variance reduction or momentum-based estimators to improve the sample complexity under the current simple framework?**\n\n**A:** Great point! As we explained in line 120, our flexible coefficients $a_i^{(t,k)}$ of local aggregations in (4) cover the optimizers such as variance-reduced and momentum-based methods, and hence it is possible to further improve the sample complexity with these two techniques. We would like to leave this interesting work for the future. \n"}, {"review_id": "Xgmme4sKYZ", "reviewer": "Reviewer_TKNN", "summary": "This work consider the federated bilevel optimization problem. Compared to existing methods, the authors develop a new and simple method named SimFBO without subloops and requiring much fewer communication rounds at each iteration. In the setting with system-level heterogeneity like diverse local steps, they further propose a more robust version named ShroFBO that is shown with a correct convergence under such heterogeneity. Convergence analysis is developed for both methods. Empirical results have shown the great performance of the proposed methods. ", "questions": "Another question is: In the right plot of Fig. 2, is the legend correct? It missed SimFBO. \n\nOverall, this is a strong work with a promising solution to federated bilevel optimization, so I suggest the acceptance. \n", "limitations": "A limitation of their work is the requirement of the lower-level strong convexity in Assumption 1. It would be interesting to explore if this condition can be relaxed or eliminated, taking into account recent advancements in the field, such as those presented in [1, 2].\n\n[1] B. Liu et al. “Bome! bilevel optimization made easy: A simple first-order approach.” NeurIPS 2022.\n\n[2] R. Liu et al. “Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity.” ICML 2023.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Federated bilevel optimization is a relatively new but challenging problem even when the lower-level objective is strongly convex. This work provides a reasonable and quite effective framework to this problem. \n\n2. The proposed algorithms are novel, easy to understand and theoretically grounded. Providing a simple solution with strong empirical and theoretical performance is strong. \n\n3. Technical derivations seem to be nontrivial. For example, it is interesting to deal with the challenges by client drift, boundness of local iterates etc. It seems to fill the gap of communication complexity of $1/\\epsilon$ in federated bilevel problems. This is good. ", "weaknesses": "The proposed methods require second-order derivatives, which may cause some scalability issue. Is it possible to develop fully first-order methods given the current SimFBO framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " We thank the reviewer TKNN for the time and valuable feedback! \n\n**Q1: Is it possible to develop fully first-order methods given the current SimFBO framework?**\n\n**A:** Good point! One possible idea is to approximate the Hessian- and Jacobian-vector products using the finite-difference tricks, i.e., $[\\nabla_y g(x, y+\\delta v)-\\nabla_y g(x, y-\\delta v)]/(2\\delta)\\approx \\nabla^2_{yy} g(x, y)v$. Since this approximation error is controllable, it is possible to provide a convergence rate guarantee similar to that of SimFBO. We would like to leave it for our future study. \n\n**Q2: Another question is: In the right plot of Fig. 2, is the legend correct? It missed SimFBO.**\n\n**A:** Thanks! We will fix the legend in the revision. \n\n**Q3: A limitation of their work is the requirement of the lower-level strong convexity in Assumption 1. It would be interesting to explore if this condition can be relaxed or eliminated, taking into account recent advancements in the field, such as those presented in [1, 2].**\n\n**A:** Great suggestion! In this setting, it is critical but challenging to find the correct convergence criterion from the KKT perspective, develop feasible distributed constrained optimization-based methods, and provide the convergence analysis. We will leave this interesting exploration for future study. \n\n"}, {"review_id": "6Eaj7HfOEt", "reviewer": "Reviewer_DZHN", "summary": "This paper focuses on bilevel optimization in a federated learning environment. Bilevel optimization has various applications in federated learning (FL) and few recent works proposed versions of bilevel optimization schemes for FL. A challenging step in bilevel optimization is the computation of the \"hypergradient\", and the existing schemes are able to obtain an estimate of the hypergradient, albeit a biased estimate, with a substantial communication overhead (multiple rounds of communication per server-side update). The paper reformulates the hypergradient computation as a least squares problem that can provide an unbiased estimate of the hypergradient, while requiring only a single round of communication for every server-side update. Based on this estimate, the paper presents a federated bilevel optimization algorithm, SimFBO, and a variant robust to system-level heterogeneity, ShroFBO. The theoretical analyses demonstrate that the proposed algorithms can converge with a sample complexity comparable to that of existing federated bilevel schemes, while demonstrating a significant improvement in the communication overhead. Preliminary empirical results highlight the significant communication efficiency of the proposed schemes compared to the existing baselines.", "questions": "- In lines 87-88, it seems that $\\tilde{v}^*(t)$ in the definition of $\\Delta_v^{(t)}$ depends on the iteration $t$. However, line 88 claims that $\\tilde{v}^*$ is the minimizer of $\\sum_{i=1}^n w_i R_i(x, y^*, \\cdot)$, which implies that $\\tilde{v}^*(t)$ is not dependent on $t$. Can this be clarified? Usually in the bilevel analysis, we are tracking quantities such as $|| y^*(x^{(t)}) - y^{(t+1)} ||$ for dependent variables, such as $y$ and $v$. So $\\tilde{v}^*(t)$ can also be the minimizer of $\\sum_{i=1}^n w_i R_i(x^{(t)}, y^*(x^{(t)}), \\cdot)$ or even $\\sum_{i=1}^n w_i R_i(x^{(t)}, y^{(t+1)}, \\cdot)$.\n\n- What is $\\bar{\\tau}$ in Theorem 1? It seems to be introduced in the theorem statement, but I am not unable to find (in the main paper) what this $\\bar{\\tau}$ is supposed to signify. Is it some aggregate of the $\\{ \\tau_i^{(t)} \\}$ across all $i \\in [n]$ and $t \\in [T]$?\n\nMinor:\n- The legend in Figure 2 (right) seems off since it has no SimFBO.", "limitations": "I did not find any discussion on limitations in the main paper. However, I do not anticipate any potential negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Well-motivated intuitive presentation.**\nThe authors do an excellent job in presenting this paper. The main problem and the challenges with the existing solutions are clearly discussed, and it is easy to see why the existing schemes are not very practical. The main idea of the use of the global least-squares reformulation, while obvious in hindsight, is very well presented and motivated, making it easy for the reader to follow along and realize how the existing challenges are mitigated. The theoretical results are clearly and intuitively presented with proper discussion highlighting the main parts of the analysis, and the main steps (with appropriate pointers to the supplement).\n\n\n**Critical reformulation removing both bias and communication overhead.**\nA key strength of this paper is a simple (yet of significant practical impact) reformulation of the hypergradient estimation using a standard quadratic program. A key property that the authors leverage is the fact that the global quadratic objective can be decomposed into per-client quadratic objectives, which is not true of the global hypergradient (which cannot be decomposed into per-client hypergradients). This simple yet powerful insight is then utilized to obtain an estimate which, upon proper solution of the global least-squares problem, is unbiased, and can be efficiently updated along side the upper and lower level variables in the bilevel problem. While this global least-squares reformulation does facilitate an intuitive communication-efficient algorithm, the paper also performs a thorough theoretical analysis, demonstrating how the inaccuracy in the hypergradient estimate plays into the convergence. The overall algorithm makes the solution of federated bilevel problems significantly more practical.\n\n\n**Generality of the proposed algorithmic framework.**\nThe authors do a great job at highlighting the generality of the algorithm framework. First, the general client and server aggregation (in equation (4)) allows us to cover various different client side optimizers, and the analysis is able to provide a convergence guarantee with such generalized aggregations. Second, the proposed framework incorporates system-level heterogeneity, allowing for different clients to perform different levels of client-side updates, and making the server-side aggregation robust to such heterogeneity. This robustness is demonstrated empirically, and the robust version of the algorithm is analysed theoretically.\n", "weaknesses": "**Increased hyperparameter space.**\nThe proposed framework utilizes various hyperparameters:\n- The client-side learning rates $\\eta_{y/v/x}$ and iterations $\\tau_i^{(t)}$ (for each server side update $t \\in [T]$ and each client $i \\in [n]$)\n- The server-side learning rates $\\gamma_{y/v/x}$\n- Potentially the choice of the client-side coefficients $a_i^{(t)} = \\left[a_i^{(t,0)}, \\ldots, a_i^{\\left(t, \\tau_i^{(t)}-1 \\right)} \\right]^\\top$ (for each client $i \\in [n]$), which might be potentially tied to $\\alpha_\\min, \\alpha_\\max$.\n- The hypergradient projection radius $r$\n\nAs per the theoretical analyses, it can be seen that the best convergence rate of any execution will critically depend on an appropriate setting of these problem-dependent hyperparameters. Since these hyperparameters often depend on quantities that cannot be efficiently estimated (such as Lipschitz constant), the practical bilevel implementations usually utilize some form of hyperparameter search. Hyperparameter optimization is known to be a hard unsolved problem in FL because of the overall communication overhead. This makes it hard to see how the proposed federated bilevel framework can live up to its practical potential -- one can view this proposed federated bilevel framework as having shifted the communication overhead from the model training stage to the hyperparameter optimization stage, without reducing the overall communication necessary for good training convergence (which involves trying various hyperparameters and training with them).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer DZHN for the time and valuable feedback! \n\n**Q1: Hyperparameter optimization is known to be a hard unsolved problem in FL because of the overall communication overhead. This makes it hard to see how the proposed federated bilevel framework can live up to its practical potential -- one can view this proposed federated bilevel framework as having shifted the communication overhead from the model training stage to the hyperparameter optimization stage, without reducing the overall communication necessary for good training convergence (which involves trying various hyperparameters and training with them).** \n\n**A:** Thanks for pointing this out to us! In our practical implementation, we set the client-side learning rates to be the same as $\\eta$ for the updates on $y,v,x$ (similarly we set the server-side learning rates to $\\gamma$). In addition, we set the iterations $\\tau_i^{(t)}$ to be the same as $\\tau$ for all clients $i\\in [n]$ and all $t\\in [T]$. The coefficients $a_i^{(t)}$ are only used to show the flexibility of our framework to cover various local optimizers, and hence we simply set all $a_i^{(t,k)} = 1$ in the experiments. The purpose of radius $r$ is only to guarantee the boundedness of $v$ updates, and hence any sufficiently large constant suffices. In summary, our implementation involves only three critical hyperparameters $\\eta$, $\\gamma$ and $\\tau$, and hence is still quite efficient in practice. \n\n\n**Q2: In line 187-188,** $v^*$ **is defined unclearly.**\n\n**A:** We guess you refer to lines 187-188. Sorry about the confusion. To make this clearer, we revise this sentence as follows:\nLet $\\Delta_v^{(t)} := \\mathbb{E}\\\\|v^{(t)} - \\widetilde{v}^*(t)\\\\|^2$, \n$\\widetilde{v}^*(t) = \\arg\\min_v \\sum_{i=1}^nw_iR_i(x^{(t)}, y^*(x^{(t)}), v)$ denote the approximation error, where $\\widetilde{v}^*(x^{(t)})$ is the minimizer of $\\sum_{i=1}^nw_iR_i(x^{(t)}, y^*(x^{(t)}), \\cdot)$. \nThen, it can be seen that $\\widetilde{v}^*(t)$ is dependent on $t$. Please let us know if we do not understand your question correctly. \n\n**Q3: What is **$\\bar{\\tau}$** in Theorem 1?  Is it some aggregate of the** $\\tau_i^{(t)}$ **across all** $i\\in[n]$ **and** $t\\in [T]$**?**\n\n**A:** Yes, you are right. In the analysis, we set all $\\tau_i^{(t)}$ to be $\\tau_i$  independent of time $t$. Then, $\\bar{\\tau}$ is defined as $\\bar{\\tau} = \\sum_i^n w_i \\tau_i$, as given in line 614. We will clarify it in the revision. \n\n"}]

Author rebuttal:

Meta-review: All the reviewers are consistently positive about this paper and agree that this paper is worthwhile to be accepted. Most of the concerns seem to be clarified during the rebuttal, and I would recommend accepting this paper.
Decision: Accept (spotlight)