Byzantine-Robust and Hessian-Free Federated Bilevel Optimization
Authors: Shruti P Maralappanavar
Bharath B N
Venue: Accepted by TMLR ()

Abstract: In the last few years, Byzantine robust algorithms to solve a minimization problem in the Federated setup have received significant attention. Most of the existing works consider the problem of byzantine-robustness for single-level optimization or consider the federated bilevel optimization without Byzantine nodes. However, problem formulation such as federated bilevel optimization in the presence of byzantine nodes is unexplored. Recognizing the gap, for the first time, we propose a computationally efficient and robust algorithm for solving Federated Bilevel Optimization with Byzantine (FedBOB) nodes that: \One Work under the assumption that the data across nodes are heterogeneous (non-iid), \2 Consider the lower-level objective is non-convex and satisfies the Polyak-\L ojasiewicz (PL)-inequality, and  \3 Is fully first-order and does not rely on second order information. We achieve this by reformulating the federated bilevel problem into a single penalty problem. We provide the theoretical performance of the proposed algorithm and experimentally corroborate our theoretical findings.

Published in Transactions on Machine Learning Research (09/2025)
Byzantine-Robust and Hessian-Free Federated Bilevel Opti- mization
Shruti Maralappanavar
mshruti32@gmail.co com
Deportment of Electrical, Electronics and Communication Engineering Indian Institute of Technology Dharwad Dharwad, India
B. N. Bharath
Shorathbr&diitdh oc.
Department of Electrical, Electronics and Communication Engineering Indian Instttute of Technology Dharwad
Dharwad, India
Reviewed on OpenReview: https: // optpevveee.r.......mmmm net/ pdf9 id= 5trmyutkeo
Abstract
In the last few years, Byzantine robust algorithms to solve a minimization problem in the Federated setup have received significant attention. Most of the existing works consider the problem of byzantine-robustness for single-level optimization consider the federated bilevel optimization without Byzantine nodes. However, problem formulation such as federated bilevel optimization in the presence byzantine nodes is unexplored. Recognizing the gap, for the first time, we propose a computationally efficient and robust algorithm for solving Federated Bilevel Optimization with Byzantine (FedBOB) nodes that: ① Work under the assumption that the data across nodes are heterogeneous (non-iid), @ Consider the lower- level objective is non-convex and satisfies the Polyak-Lojjssieviez (PL)-inequality, and @ Is fully first-order and does not rely on second order information. We achieve this by reformulating the federated bilevel problem into a single penalty problem. We provide the theoretical performance of the proposed algorithm and experimentally corroborate our theoretical findings.
1 Introduction
Deep Learning thrives on large datasets that are often distributed across multiple owners (Verbraeken et al. 2020). The challenge of training the model on distributed data sets was addressed using paradigm called
Federated Learning (FL), which enables clients (agents) to train models locally private data while central server (aggregator) combines them into unified model (McMahan et. al.
2017 Smith et al. 2017) Although FL offers several benefits, it comes with certain risks. Since it is a collaborative mechanism, it opens the possibility of security threats (Karimireddy et al. 2020 Gorbunov et al. 2022). In particular, a few nodes in the FL setting can potentially be malicious, also known as Byzantine nodes, and send corrupt information which renders the updates at the central server useless. Recently, the question of byzantine robustness has received significant attention making relatively well studied both in theory and practice for single-level minimization problems in the FL setting (Yin et al. 2018 [Blachard et al. 2017b Chen
let al., 2017 Karimireddy et al. 2021 2020 Rammal et al. 2024). There are many real-world applications
that cannot be modeled as single level mininization problems, c.g. robust lcarning Zhhag et al. (2022)
Khanduri et al. (2023), meta-learning Rajeswaran et al. (2019). hyperparameter optimization Franceschi
et al. (2018) neural architecture search Xue et al. (2021), resource management Sun et al. (2021). and image
denoising Crockett al. (2022) and other problems encountered machine learning and signal processing
tasks Zhang al. (2024). name a few. Such problems follow a nested structure that goes beyond the
scope of standard single-level minimization structure, in Karimireddy al. (021 2020); Rammal et al.

---

Published in Transactions on Machine Learning Research (09/2025)
2024p. Towards solving such nested problems, bilevel optimization in non-FL as well the FL setting has received great attention in the recent past GGhadimi & Wang (2018); Hong et al. (2023); Khanduri et al.] (2021]; ;s Tarzanagh et al. (2022); Huang et al. (2023); Yang et al. (002bb). But these works cannot handle the presence of Byzantine clients. Recently, the authors in Abbas et al. (2024) proposed a byzantine-resilenn bilevel federated optimization algorithm. However, they use second order information to update its model parameters making it computationally expensive, and make restrictive assumption such as strongly-convex lower level function.
A typical approach to solving the bilevel problems is to compute the gradient of the upper-level function (called hypergradient). To find the hypergradient there is need to compute the socond-order information of the lower-level function that makes the algorithm compulationally complex (Ghadimi & Wang 2018 Chen
le al.
2021). This issue was resolved by using the first order method involving penalty formulation (Liu
2022a Kwon et al., 2023b Shen & Chen 2023 Chen et al.) 2023) of the bilevel problem; albeit in the non-FL FL setting. However, none of the existing work considers a computationally efficient robust algorithm
jtt al.
to solve bilevel optimization problem in the FL setting leading to the following question.
Q: Is it possible to design a Robust and Low Complexity algorithm for solving a bilevel optimization
problem in the FL setting in the presence of Byzantine nodes?
In this paper, we answer the above question by considering federated version of the bilevel optimization problem in the presence of Byzantine nodes. We assune that there are N nodes denoted by N 9 U B, where G is the set of good or legitimate nodes, and B is the set of Byzantine or bad nodes. Let [g] = G and B = B. The problem of Federated Bilevel Optimization with Byzantine (FedBOB Problem) involves solving the following:
1 Σ fo yx, G
min f(x) = f (x)) = xEX
KED
subject to
y" (x)x E arg min g(x, = 1 - EO yERdz
(1)
G
kEg
where fa Rdh x Rd + R and 9k : Rdh x Rd + R, k E G are upper and lower level objective func- tions, respectively. The standard approach to solving the above problem involves computing second-order information such as Hessian, which is computationally expensive. In this paper, we take the first order approach by minimizing a penalty function defined as minx.y {hx (x,y)
= f(x) + xp(x.y)], where X > 0
and p(x, y) = g(x,y) y)- -min,/ 9 yx. (Shen & Chen 2023 Liu et al. 2022a. Kwon ct al. 2023b a). Next.
wC present challenges that WC need to address in comparison with the existing work
(Kariireedy et al.
2020 Shen & Chen 2023 Blanchard et al. 2017a Pillutla et al. 2022a).
The penalty based method in the non-FL setting is very well studied (Shen & Chen 2023 This work relics on the equivalence between a local solution to the penalty formulation (i.c., the point at which the gradient is zero) and a solution to the original problem. Unfortunately, the FL setting with heterogeneous and Byzantine nodes forces the solution to have non-zero gradients (see lower bounds in (Karimireddy al., 2020)) ) and hence the equivalence in (Shen & Chen 2023) cannot be directly used. We take a different approach where we analyze (i) convergence of the gradient, as in (Shen & Chen 2023) and (b) a new notion called constraint violation that measures the average violation of the constraint in the lower-level problem, which is new. Keeping track of the average constraint violation is particularly important. in scttings such as adversarial learning (Khanduri et al. 2023). The average constraint violation gives information on how frequently the constraint is violated rather than capturing it implicitly in the convergence rate, as in (Shen) & Chen 2023). In addition, minimizing the penalty function involves computing miny 9 (x, in FL lashion in the presence of Byzantine. To make matters more challenging, the resulting lower-level optimum drifts away from (x) due to heterogeneity in the data and is further alleviated due to the presence of Byzantine nodes, which makes the analysis difficult.
Challenges:
Contribution: In this paper, we address the above challenges and make the following contribution. D We consider the FedBOB problem in equation 1. and propose robust and fully first-order federated al-
2

---

Published in Transactions on Machine Learning Research (09/2025)
gorithm by reformulating the federated bilevel problem into a single-level penalty-based optimization prob- lem that makes it computationally efficient. Unlike the existing work on lederated bilevel optimization (Tarzanagh et al. 2022 Huang et al. 2023; Yang et al. 2024b) where the lower level is strongly convex, we consider a class of non-convex functions satisfying the PL inoquality, thus widoning the scope of applicability.
@ The proposed algorithm (Rob-FedBOB) is shown to converge at a rate of O a/4 + +a( x())) where R is the mumber of communication rounds, Sf and Sg are the inter-client heterogencity terms correspond- ing to the upper and lower level objective functions, respectively, and a E [0, 0.5) is the fraction of the Byzantine nodes. Additionally, the algorithm results in an average constraint violation that scales as o 0 + =oc?)) Our results demonstrate the trade-off wetween the convergence and the constraint violation that is captured through A. Higher À results in better constraint violation properties, but at the expense of lower convergence rate and vice versa. Furthermore, our bounds reveal that Byzantine nodes and heterogeneity act as bottleneck in achieving good performance, as expected. We study the trade-off between convergence and the constraint violation, and provide insight on the choice of A.
3 Finally, we present experimental results for data hyperclearning application for various attacks and cor- roborate our theoretical findings. In particular, we consider the following attacks (i) Bit Flipping (BF), (ii) Label Flipping (LF), (iii) Inner Product Manipulation (IPM), and (iv) A Little is Enough (ALIE), and show that both gradient and constraint violation go down and converge to constant with increasing number of communication rounds. The constants to which the gradient and the average violation converge governed by the number of Byzantine nodes, and the inter-client heterogeneity of the good nodes.
1.1 Related Work
Robust Federated Learning: Over the recent years there has been a significant amount of work on byzantine robustness in case of single level optimization problems (Karimireddy et al. 2020; Gorbunov et al. 2022). Byzantine robustness is very well studied when the nodes have iid data distributions. One approach to obtaining robustness is to use robust aggregation strategics such as Coordinate wise median
(Chen et 2017 KRUM (Blanchard et al., 2017at, geometric median (Pillutla et al. 2022a), use variance roduction techniques (W et al., 2020), filter byzantine nodes. Recently, there have been many works which consider byzantine robustness for non-iid data distributions such as: outlier based-robust clustering (Sattler et al. 2020), spectral methods for robust optimization (Data & Diggavi 2021). Other interesting approaches include use of (a) a formal definition of robust aggregation with client momentum (Karimireddy et al.) 2020). (b) random checks of computations (Rammal et al. 2024). (c) normalized gradient (Zuo et al. 2024). and (d) normalized momentum (Yang et al. 2024a). These works are limited to solving single level federated learning problem in the presence of Byzantine nodes.
Federated Bilevel Optimization (FBO): Recently some works have considered Federated Bilevel opti- mization as many machine learning applications can be formulated as nested bilevel problem. The authors in (Tazaanagh et al. 2022) proposed a federated alternating stochastic gradient method that requires a fed- erated hypergradient computation. They use variance reduction to handle lower-level heterogeneity. The results on the complexity of the sample were improved using momentum-baen based federated bilevel algorithms with a reduction in variance in (Li al., (022). Later, the work in (Huang et al. 2023) achieved lincar speedup in the presence of non-iid data by using a novel client sampling scheme. Along similar lines, the authors in (Yang et al. 2024b) propose communication efficient federated bilevel optimization algorithm. However, most of these works require the second-order information to perform the gradient update. Further, these works limit the lower-level objective function to strongly convex. Thus, the challenging problem of finding a computationally efficient algorithm that is robust to byzantine attacks in a federated bilevel set ting is still an open problem. In this work, we have closed this gap. Concurrent to our work, the authors in (Abbas et al. 2024)) proposod a byzaitine-resilient bilevel federated optimization algorithm. They use the second order information such as the Jaccbiian making it computationally expensive. In addition, we have included more experimental results compared to (Abbas et al. 2024
3

---

Published in Transactions on Machine Learning Research (09/2025)
2 Problem Statement
We consider federated version of the bilevel optimization problem in the presence of Byzantine nodes as in equation [ The problem in equation 1 cannot be solved directly in the presence of Byzantine nodes. This is due to the fact that the Byzanine nodes can share corrupt information with the central server, which can make the updates potentially useless. The problem of Byzantine robust distributed optimization in various scttings have been studied carlier (Blanchard et al.) 2017a; Pilluutla et al.) 2022a Wu et al., 2020 He et all, 2020). Clearly, explained in the previous section, the problem of federated bilevel optimization with Byzantine is not at all addressed in the literature as it posses several challenges: @ The typical solution for the bilevel problem without Byzantine involves using second order methods thus making it computationally expensive (Ghadimi & Wang, 2018 Chen et al.] 2021). @ Most these works assume that the lower level function Ie (x,)) for all l E is strongly convex making more restrictive. @ The lower level optimum drifts away from y"(x) due to hetcrogeneity in the data, and is further aggravated due the presence of Byzantine nodes. We handle the above challenges by ① proposing fully first order method of solving FedBOB Problem, and @ using robust aggregation strategies that is resilient to the Byzantine attacks. Our method is motivated by reformulating the FedBOB Problem into approximate equivalent form as follows:
Approx-FedB0B Problem: min I' (x.
such that p(x,y) == g (x,y) ux) s.
(2)
where v(x) == miny g yx) and e >>> O. Letting = 0 in the above problem makes it equivalent to that of the FedBOB Problem. Writing the Lagrangian function of the above problem results in
G
hy (x, = G
Σ hx (x.y) == (xx,) + (x.
(3)
for all x E Rdi y E Rd,, In the above, X 0 and p yx is the penalty term. Now, the dual problem is to solve the following in the presence of Byzantine nodes
FedBOB Penalty Problem: min hx (x,
(4)
It turns out that solving the above problem is approximately equivalent to solving the original problem (see (Shen& & Chen 2023) for more details). Note that this boils down to a single level federated learning problem in the presence of Byzantine. Although single level federated optimization in the presence of Byzantine (see
(Krrmireddy et al.) 2020 Gorbunov et al.) 2022 Pillutla et al. 2022a Wu et al., 2020)) has been studied in the literature, our framework is completely different in the following sense D the impact of the Byzantine nodes and À on the performance need to be studied, and does not follow directly from the existing literature. @ The solution obtained by our proposed algorithm should not only result in a good stationary point of | but also should exhibit good constraint violation properties this additional requirement is not explicit in the single level formulation. Proposing a low complexity robust algorithm and analyzing its performance is completely new
equation
2.1 Preliminaries
In this subsection, we discuss the assumptions and definitions required in the analysis of the proposed Robust Federated Bilevel Optimization with Byzantine (Rob-FedBOB) algorithm.
Assumption 1. (Smoothness): The upper-level objective function fu (x.y) is assumed to be L smooth for all good nodes k 9, i.e.,
V (x,y) - f (x)) S LyN lly - Y'1l2
for all x E RRd, y.y's E Rdd. Further, we also assume that fo (x is a 1f Lipschit, i.e.,
I fx (x,y) - fa (x,y)) I5 f Ily -V'l2
for all x E Rd, y.y's d and le 9. In addition, gk (x, x) is a Ly.k- and 1g.6 lipschitt function for all l E 9.
4

---

Published in Transactions on Machine Learning Research (09/2025)
Assumption 2. (PL inequaliyy: The lower-level objective function 96 (x.y) for all k E G satisfies the PL
inequality, i.e., g/ (x, x)) 2 My (gu (x,y) vn (x)) for some Mg > 0 and for all x E R", ,Y,.22 2 Rd, Here (x) miny 9k (x. y). In addition, we consider the aterage lower level objective g (x.y) satisfies the PL inequality, i.e., [Vg (x, y)1l 2 Py (g (x. (13y)--fi v(x)) for some My > for all E (Rdd,, E TRd
Assumption 3. (Inter-client heterogencitt): The upper-level objective function fa (x,y) for all E g is said to salisfy inter-client helerogeneily, i.e., Beeg V/ (x. - VV,.) xx, S for some St > 0 and for all E Rd , Rdb In addition, 9k (x, also satisfies inter-client heterogeneity for some bg > 0, i.e., EEeG [V (x,y) (x,
Most of the assumptions above such as smoothness, inter-client heterogencity are standard (Shen & Chen 2023 Karimireddy et al., 2020: Rammal et al. 2024p. The PL inequality is satisfied by most of the over- parameterized neural networks (Liu et al. 2022b; Shen & Chen 2023p. The inter-client heterogeneity (Karim- ireddy et al. 2020; Gorbunov et al. 2022 Yu et al. 2018) restricts the data heterogeneity of good nodes. In fact, the lower bound in (Karimiredyy
al.) 2020) shows that the heterogeneity condition is inevitable. Note that Ç, and Co = 0 case imply that the data homogeneous across all nodes.
3 Algorithm Design
It is well known that the aggregator plays an important role in the performance of any algorithm with Byzantines. Hence, we first define the class of aggregators, which is adapted from Karimireddy et al. 2020
Definition 1. ((a, coobbut Aggregator):
Let us assume that we are given inputs {x1, ....... NN3 such that
there crists subsel G S [N] of size 9 1- G > (1 a) N for S 0.5 such that E [||x xj 82 for all j.j E 9 and some 2 0. Then we say that x satisfies (a, c) -oouut Aggregator (RAgg) if
E E| - x||² S cao?
(5)
where x Et Xg. Here the expectation is taken with respect to possible randomness of good nodes {x1, X2..,X...,,
Note that (a, e)- Robust Aggregator property satisfied by many aggregators such as KRUM, Coordinate- wise median (CM), Geometric median (RFA). We provide more details in Appendix H
3.1 Rob-FedBOB Algorithm
Given that the penalty reformulation is single level problem, an obvious approach is to use the following gradient updates: X,-1 = = xxxh (x). and yr+1 = - 3V h, (x,,y,). However, this computation involves finding Vp (x), which requires Vu (x,).
). In general, u (x) need not to smooth always. Further, Vxe(x) + Vxg (x. y") at y". From assumptions 2 and 1 using Lemma A.5 Nouiehed et al. (2019), we can see that Vv(x) Vxg (x)) In addition this, the gradient update requires yx(x), which is a solution to the lower level problem with respect to y, and is unknown. More specifically, computing y" (x) requires access to y(x,y) (scc equation [ which is not available cach node. One way to handle this is that cach node k runs T number of GD steps on the lower level function gh (xr.)) for a given x, as follows (see line 9 of Algorithm
yr.+1 = yr. - 7 yag (x,))
where yr.0 = -y-11 and = 0, 1,......7 T Here,
V Vygag (x,, = RAgg (yykk yr), [N]).
(6)
where RAgg uses bucketing followed by geometric median aggregation (see (Karimireddy al.] (0200) for more details). Now, can YET as proxy for (x,) to get the following updates (see line 13 of
5

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm !
yr+1 = Yr Vy (x), and
(7)
X,+1 X, 3V VVx (x,,
(8)
where the gradients are defined as
Vyhx,ag (Xr. = RAgg (Vyhx. Vr), , [NT),
Vxhx, (xr. = RAgg V Vx) E [M]
In the above,
(x.. = (X.. +
(Vxg (x,, Vx9t Vr,2l)
(9)
and Vyy (x, = Vx (x) yVyg (x,, for all E G. In order access whether the output of the algorithm satisfies the constraint not, we propose the following notion of violation:
Violn = Σ p(x..
(10)
where x, and y, are the output of the algorithm in round r. Note that when Violn/ R converges to a small constant, it means that p(x,,y,) for sufficiently large r close to the constant, and hence captures the violation performance of the algorithm.
Note: The robust strategy involving binning followed by geometric median is known to satisfy the (a, robustness (scc (Karimireddy et al. 2020 property. However, in case, the gradient of the penalty function is aggregated at the central server. This function depends on À and the proxy for y"(x),, which is obtained by using lines 5 to 11 in Algorithm [ This makes it necessary for us to prove that the (a, c) robustness is still achieved for the penalty function, as shown in the following lemmas.
Lemma 1. For the robust eggregator RARgg, we have for some 0
V (x,, hy (x)l $ cap²
where p² = 867 + 8X2C2
Proof: See Sec. in Appendix.
The above lemma shows that the robustness depends on À and the heterogeneity terms, In the following, prove the robustness of V Vxhx (x,, yr) _/2 Eg Vxhnaa (x) with 82 8A2
244
"5
2
82 ma 2 + GC7 12, where Iig.mar maxkeg by and lym maxkeg 4.
Lemma The robust aggregator ARgg satisfies
V (oelxxee(xxx10 - V Vahna Xxrix(x. v.)l < cad2.
Proof: See Sec. C in Appendix.
The above lemma shows that the robustness depends on how close the proxy yrr the actual optimal y" (xx,) captured through the first term in 52. Tt. also reveals that this can be reduced by increasing T.

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm Rob-FedBOB Algorithu
Initialize Xg E IR::, Yo Rd for r 0, 0...2.....
do Send Yr to cach node
Set. 2,,0 =
5: for t =
do
6: for k E N in parallel do
7:
Send Vyg (X.. Vra), N end for
yr.++ = Yr. 7 Vyyaag (X,, Vra)
10: Send yr.41 to all nodes
11:
end for
12:
Set Yr.r -r,
13:
Server updates X,41 and yr-1 using equation S and equation 7 respectively.
14:
end for
Output: xR and yR
3.2
Convergence Analysis
In the following, we provide the first main result for the Rob-FedBOB algorithm.
Theorem 1. Suppose assumptions hold, then for the aggregator RAgg, Algorithm 1 following bound
achieves the
Vhi (x,, y.) < 50
X²
+ as} xx())
R
R
for constant learning rates 1) S t,,, B L. and T
log
88 8
max
7p
Proof: See Sec. in Appendix.
The above result reveals the effect of X, the fraction of the Byzantine nodes a, and the heterogeneity terms S and on the convergence rate. Note that when = 0, i.c., when there are no byzantine nodes, we get a convergence rate of hand, in the presence of Byzantine, ie., a + O, we have
Thus, a smaller gradient can be achieved by choosing larger R. On the other
Vh x=)l= 2))
(11)
R
This cannot be made very small unless the heterogeneity terms C} and 23 are zeros. A similar observation was made in Karimireddy et al. (2020) in the context of single level setting. They also showed a lower bound demonstrating that the result they obtain cannot be improved further. Since single level is a special case of the bilevel problem that we are considering, we believe that the bound in Theorem Next, we present bound on the average violation that relates the gradient of the penalty function.
D cannot improved.
Lemma 3. Suppose Assumptions and hold, and II Vhx (x, for some vp then the average violation in equalion 10 is bounded as follows
2 211 + 1/2 2/2
Violg
(12)
R
22
Proof: See Sec. 1 in Appendix.

---

Published in Transactions on Machine Learning Research (09/2025)
Note that the above shows that by choosing large À or if &o is small results in good constraint qualification properties. In order to prove violation bound on the proposed algorithm, we use bound on V/ (xr:l))l for each r obtained in the proof of Theorem
Theorem 2. Algorithm 7 satisfies the following average constraint violation provide the conditions in Theorem 7 are salisfied
( (1 + ca(7) (1+)
Violn R
+ eacs)
X2
Proof: See Sec.
G in Appendix.
We observe from the above theorem that larger values of À result in a better violation qualification properties as expected. In particular, as A + oo, average violation converges to cac, revealing the bottleneck due to the Byzantine nodes and the heterogeneity the lower level function, it is expected that the heterogencity in the upper level function impacts mildly the average violation. However, larger À results in bad gradient bound leading to trade-off bet convergence (gradient bound) and violation.
the lower level function. Since the violation with respect
Convergence versus Violation tradc-off: To better understand the trade-off, consider a = 0 condition,
i.e., no Byzantine nodes. In this case, choosing = o ( results in an average violation of O (e) and
the average gradient converges at the rate of O (#) recovering the results of (Huang et al. 2023 Tarzanagh
ct al. 2022) when the variance zero. The presence of the Byzantine nodes (i.c., a o 0) changes the
scenario completely. Choosing as above, and - oo results an average violation of O (coC?) and the convergence rate of the average gradient decreases to
R Σ IV (x., (x.. =0
(6) )
lim R-
G ce+
(13)
R
This also reveals the impact of heterogeneity in the presence of Byzantine nodes.
Note that the ((a, ((a,e)-Roee Robuss Aggregator, initially proposed by Karimireddy et al. (2021 2020) plays an important role in our algorithm. Most of the existing works that use this robust aggregator Karimireddy el al. 2020 Rammal et al.) 2024 Yang el al.] 2024a) with single-level optimization problem. However, we consider a bilevel problem, which requires us to carefully combine the upper and lower level objective functions. Moreover, we need to obtain the optimal solution yx(x) to the lower level problem, which adds complexity to our analysis. Also, our problem formulation requires proving convergence of the gradient and bound on the average constraint violation, which is completely new. In addition, À plays important role in studying the trade-off between convergence of the gradient and the constraint violation guarantee; this makes the problem more challenging compared to existing work (Karimireddy et al. 2020:
Remark:
Shen & Chen )023).
The total number of communication rounds for bilevel foderated learning probloms (with or without Byzantine) is O(R) (Huang el al. 2023). Our communication complexity is O O(Rlog R), and order- wise matches with other existing algorithms except for log R factor; this is done to ensure a good proxy for y" (x,) (see lines 5 to 11 of Algorithm 1. In contrast to the existing algorithms in the federated bilevel learning problem (Tarzanagh et al.] 2022 Huang el al. 2023 we require only first-order information, and as consequence, the run time at each node is very low as demonstrated in our experimental results.
Complexity:
3.3 Proof Sketch of Theorem
In order to prove our main results, first need the smoothness of the penalty problem.
8

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma Suppose assumption hold, then the function h(x, y) Ln smooth i.e.,
Vhx(x, Vhx(x,y))l I La lly - y'll.
where Lu = Ly + ALe.
Proof: See Sec.
in Appendix.
R-- [ (x, y)ll
60
20
0.2
0.2
15
0.2
20
0.2
0.4
a
0.4
0.4
0.4
40
10
(a)
(b)
(c)
10
(d)
5
20
0
0
0
500
1,000
0
500
1,000
500
1,000
0
500
1,000
R
R
R
R
Figure 1: Effect of the convergence of Rob-FedBOB under BF (see (a)). LF (see (b)), IPM (see (c))
and ALIE (see (d)) attacks on the data hypercleaning application.
10a
10
110
10a
log (
102
10a
102
b
10
(c)
10a
(d)
10
100
0.2
0.4
100
0.2
0.4
109
a
0.2
100
a
a 0.4
0.2
500
1,000
500
1,000
0
500
1,000
500
1,000
R
R
R
Figure 2: Effect of on the violation under BF (see (a)), LF (see (b)), 1PM (see (c)) and ALIE (see (d))
attacks the data hyperclcaning application.
Note that unlike vanilla FL problems, the bilevel problems, we need extra rounds of communication (see lines 5 to 11 of the algorithm) obtain good proxy for the lower level problem, which is stated in the next lemma.
Lemma Under assumptions and choosing 1j bounded as
S nyy" the approzimation error Algorithm is
212
2c
S(x,) (xrT) _ g.max TT +
11
Pg
where 7 (1 THe
Proof: See Sec. in Appendix.
Note that by choosing T as in Theorem ensures that & (s),,, (y,,) S O 2ca5 Pg
indicating that the presence of Byzantines effect the proxy for the lower level problem as well. Since the gradients VY (x,,y,) and Vxh,, yr) are sent to the central server, and aggregated using bucketing followed by geometric median, we first need to relate these gradients to the true average gradients of the good nodes. This is done using Lemmas and Once these results established, we prove bound on // (x y) which is

---

Published in Transactions on Machine Learning Research (09/2025)
summed r= 0, 1...., R to get bound the total gradient as in Theorem 1 We establish result that connects violation to the bound on V/ (x, x)ll as in Lemma Using this Lemma, we establish the rates for the average violation as in Lemma 2
m [ y)))
6 10
6 10-3
0.1
0.2
0.2
6-10-3
0.2
0.3
a 0.3
4. 10-3
4 10-3
4 10-3
(b)
2.10-3
2 10-3
10-3
0
500
1,000
500
1,000
500
1,000
R
R
R
Figure 3: Effect of a the convergence of Rob-FedBB13 under BF (see (a)), 1PM (see (b)) and ALIE (see
(c)) attacks on the learnable regularization application.
10
log(Violn)
10-2
10-2
10
(a)
(b)
(c)
10-3
10
10
0.1
0.2
0.2
0.2
0.3
0.3
10-1
10
10
500
1,000
500
1,000
500
1,000
R
R
R
Figure 4: Effect of on the violation under BF (see (a)), LF (see (b)), IPM (see (c)) and ALIE (see (d))
attacks on the learnable regularization application.
4 Experimental Results
In this section, we experimentally validate our theoretical findings of Rob-FedBol We evaluate the perfor- mance of Rob-FedBOB on two ML applications.
Data Hyper-cleaning: We consider the Data Hyper-cleaning lask experimentally validate our theory
Shabann et al. 2019 Kwon et al., 2023bb for the following attacks (i) BF, (ii) LF, (iii) TPM, and (iv) ALIE.
The goal of Data Hyper-cleaning to solve the following bilevel problem in federated manner:
min
Lu (y ((a)
Gm
subject to
G
(x) e mig min
oxx, (y; Dirain) + + +c|ll|1
(14)
Gn
k=
where, Dirain == {(āz.i hm is the noisy training data set and D = {a Hh denotes a clean validation data set. Here, (Xx.)) ) is the sigmoid function, 4 () is the cross entropy loss al each node k E N and c is the regularization constant. The lower level problem aims to find the optimal model parameters y that minimizes the weighted average of the loss function (with regularization) on the noisy datasct Dirain for fixed set of coefficients oxx,.), l E G. On the other hand, the upper-level optimization problem aims to find the coefficients a (xx,;) by minimizing the validation loss learned the clean dataset Dyal for k E G.
10

---

Published in Transactions on Machine Learning Research (09/2025)
Learnable Regularization: The goal of learnable regularization is to learn the optimal regularization
coefficients for newsgroup dataset (Chen et al. 2023 Liu et al. 2022a). The federated bilevel optimization problem for this task can be posed as:
min
La (x);
Gm
k= 1=1
subject to
yx) arg min ΣΣ k=li=1
y Gm la (y, Diraiu) + y/",,
where, Dirain = ((āg, b the training data set and Diai == {(ag, bz, denotes the validation data set. The lower level function minimizes the loss on the training dataset across the good nodes by finding the optimal model parameters for given regularization coefficient. The upper level objective finds the optimal regualrization coefficient by minimizing the validation dataset of good nodes.
We train a linear model on the MNIST dataset with N = 16 nodes. We divide the dataset into equal parts among G good nodes, and ensured that the data distribution is heterogeneous. Also, we consider Byzantine nodes which have access to the entire dataset, We have used the bucketing algorithm followed by geometric median aggregator. Next, we present the four different attacks that we consider:
Bit Flipping (BF): In this attack, the Byzantine nodes change the sign of the gradient of the penalty function computed using the entire data set, i.e., it sends - -x,x(x, (x. y) aiming to cancel the effect of the
gradients shared by all the good nodes. See (Karimireddy et al., 2020: Rammal et al. 2024) for more details. Label Flipping (LF): Byzantine nodes modify the label of the MNIST dataset to 9 9- Z, 2 10.1..... .9. Inner product Manipulation (IPM)) The byzantine nodes will send A ENEG (x,,, where decides the intensity of the attack (Xie et al.; (020)..
T
A Little is Enough (ALIE): The byzantine nodes send jlg - vag to the server, where jig and og are the mean and the standard deviations of the good nodes gradients, respectively. Here, v dictates the intensity of the attack (Baruch et al. 2019).
Next, we present the experimental results for Rob-FedBOB algorithm and corroborate our theoretical findings made in this paper for N = 16 nodes:
Figure and 3 show the convergence rate of the proposed algorithm versus the communication rounds under different attacks for the application of the data hypercleaning and learnable regularization, respectively. We have chosen B and B = 6 for a total of N 16 nodes which result in approximately a 0.2 and a = 0.4, respectively. It is clear from the figure that the gradients does not converge to zero due to the presence of Byzantine nodes, expected. The figures also demonstrate that the gradient converges to constant that scales with a. This corroborates with Theorem D where we it-1 have shown that R. Σ // (x), increases as a increases because of a(L + X²(2) term, provided A and the inter-client heterogeneily are fixed. Figures 2 and show the plot of the constraint. violation (in log scale) versus the number of communication rounds under different attacks for data hypercleaning and Iearnable rogularization applications, respectively. In particular, the figure shows that by inercasing a for a fixed À= results in a poor violation performance. This corroborates our theoretical findings (see Theorem 2. where we have proved that Viola increases as increases at the rate of al{ + X²(3).
Effect of a and heterogencity:
In this subsection, we use the same sctting explained in our experimental results scction (scc 4 Effeec of X: Figures 5(a) and (b) show the plot of convergence rate (in log scale) and the constraint violation (in log scale) versus R by varying À while fixing a = 0.2. The heterogeneity in the data causes the Rob-FedBOB to convergence to a non-zero gradient and violation, as expected. Note that Theorem [ shows that the average gradient ||Vhx (x))))) scales with À as larger À results in a better violation. This is in agreement with Theorem 2 where we have shown that ViolR decreases at the rate of 1. x²
X² On the contrary, Fig. () shows that
Effect of T: Figure G() and (b) show the effect of T on the convergence and constraint violation of Rob-FedBOB algorithm. We get O( +) rate when T > O(lo((R)) rounds.
11

---

Published in Transactions on Machine Learning Research (09/2025)
10c
300
10a
10
log (VVvol)))
aa)
(b)
102
10
--==n
100
100
300
0
200
400
600
800
1,000
0
200
400
600
800
1,000
R
R
Figure 5: Effect of À on the convergence of Rob-FedBOB (see (a)) and violation (see (b)) under BF atlack in the log scale for the data hyperclearning application.
15
T ==11
102
--- (x)
T
10
log (og(Vi)lR)
10
(a)
(b)
-r=n
5
10
T
200
400
600
800
1,000
200
400
600
800
1,000
R
Figure 6: Effect of T on the convergence of Rob-FedBOB (sce (a)) and violation (sec (b)) under LF attack in the log scale for the data hypercleaning application.
Performance Comparison: The Figure shows the performance comparison between our proposed method (Rob-FedBOB) and Hessian-based federated bilevel optimization algorithm (BILANTINE) for the data hyper cleaning application. We have considered the bit flipping attack in both the cases. In Kwon et al. (002bb), the authors have demonstrated the superiority of the penalty based method over the second order (Hessian) method in the absence of Byzantine nodes in the centralized case. We on the other hand show superior- ity of our penalty method compared to BILA- TINE (second order method) in the FL setting in the presence Byzantine nodes. As stated in Kwon et al.) (023b), the exact mathemati- cal reason of why the penalty methods work better than the second order methods is clear, and will be relagated to the future work.
Accuracy
(a)
10 10-0.5
Rob-FedBOB
Bilantine
50
100
150
R
Figure 7: Performance comparison of Rob-FedBOB with BILATINE.
12

---

Published in Transactions on Machine Learning Research (09/2025)
5 Conclusion
In this work, we considered the problem of bilevel optimization with Byzantine nodes where both upper and lower level objective functions non-convex. Typically, bilevel problems solved using estimate of the hypergradient which requires second-order information about the lower level objective making it computationally expensive. Further, the presence of Byzantine nodes require the algorithm to be robust against attacks. We propose Rob-FedBOB algorithm, a fully first order byzantine robust federated algorithm that (i) does not require second-order information making it computationally efficient, (ii) handles non- convex lower level objective function satisfying PI-inoquality and heterogencous data, and (iii) aggregates the information from all the nodes in a robust manner making it resilient to Byzantine allacks. We prove theoretical performance of the proposed algorithm, and show that the rate at which the gradient and the average violation scale depends heavily the fraction of the Byzantine nodes and the heterogeneity of the upper and lower level objective functions. In the absence of Byzantine nodes, we show that the gradient converges at the rate of 1/R, where R is the number of communication rounds while the violation can be made arbitrarily small. We have performed extensive experiments to corroborate our theoretical findings and demonstrate that the complexity of Rob-FedBOB is very low.
Acknowledgemmetts: This work is in part supported by MFITY, India AT Mission (2024-2026), SERB- CRG (grant number: CRG/2021/007500) and SERB-MATRICS (grant number: NTTR/2021/000573 The authors would like to thank the anonymous reviewers for their valuable comments.
References
Momin Abbas, Yi Zhou, Nathalie Baracaldo, Horst Samulowitz, Parikshit Ram, and Theodoros Salonidis. Byzantine-resileent bilevel fedcrated learning. In 2024 IEEE 13rd Sensor Array and Multichannel Signal Processing Workshop (SAM), pp. 1 5, 2024. doi: 10.1109/SAM600 200,02222.2244.1366999
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed lcarning. Advances in Neural Information Processing Systems, 32, 2019.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: byzantine tolerant gradient descent. In Proceedings of the 31st International Conference on Newral Information Processing Systems, NIPS'17, pp. 118-128, Red Hook, NY, USA, 2017a. Curran Associates Inc. ISBN 9781510860964.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adver- saries: Byzantine tolerant gradient descent. In 1. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017b. URL httpss://rroceeddngg htw.:r/cceennnnn...ii..... cheurips.cc/pappee http://ccccppppeeeeeeeee//eeeeee filesspaper/20111 F11e://400ec000sfffre000sssse6f
Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-optimal fully first-order algorithms for finding stationary points in bilevel optimization. arXiv preprint arXiv:2306.14 14853, 2023.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems. arXiv preprint arXiv:2106.1971 18781, 2021.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1(2):1-25, 2017.
Caroline Crockett, Jeffrey A Fessler, et al. Bilevel methods for image reconstruction. Foundations and Trends2 in Signal Processing, 15(2-3):121 289, 2022.
Deepesh Data and Suhas Diggavi. Beziittn sgd in high dimensions on heterogeneous data. In 2021 IEEE International Symposium on Information Theory (ISTT), pp. 2310-20 2315. IEFE, 2021.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Luca Franceschi, Paolo Frascomi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel pro- gramming for hyperparameter optimization and meta-learning. Tn International conference machine learning, pp. 1568 1577. PMLR, 2018.
Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. ar preprint arXiv:1802. 02246, 2018.
Eduard Gorbunov, Samuel Horv'ath, Peter Richt'arik, arik,, and Gauthier Gidel. Variance reduction is an antidote byzantines: Better rates, weaker assumptions and communication compression cherry the top. 2022.
Lic Hc, Sai Pranceth Karimireddy, and Martin Jaggi. Secure byzantine-robust machine learning. arXiv preprinl ar Xrv:20000. 04747, 2020.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm frame- work for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180 2023.
Minhui Huang, Dewei Zhang, and Kaiyi Ji. Achieving linear speedup in non-iid federated bilevel learning. In International Conference on Machine Learning, pp. 14039-14055 PMLR, 2023.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing, In International Conference on Learning Representations, 2020.
Sai Pranceth Karimiroddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimiza- tion. In International Conference on Machine Learning, pp. 5311 5319. PMLR, 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. near- optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural informa- tion processing systems, 34:30271 30283, 2021.
Prashant Khanduri, Ioannis Tsaknakis, Yihua Zhang, Jia Liu, Sijia Liu, Jiawei Zhang, and Mingyi Hong, Linearly constrained bilevel optimization: a smoothed implicit gradient approach. In Proceedings of the 40th International Conference on Machine Learning, TCML'23. JML..org, 2023.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint XXi::230900175: 2023a.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference Machine Learning, pp. 18103. PMLR, 2023b.
Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum-based variance reduction. arXiv preprint arXiv:2205.00 01668, 2022.
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: simple first-order approach. Advances in neural information processing systems, 35:17248 -12082,172222222 2022a.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non- linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85 116, 2022b.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiienn learning of deep networks from decentralized data. Tn Artificial intelligence and statistics, pp. 1282-1282. PMLR, 2017.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Mcisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. Advances Neural Information Processing Systems, 32, 2019.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. 1EEE Transactions on Signal Processing, 1111-1115444 2022a. doi: 10.1109/TS9:2222233333313
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IREE
Transactions on Signal Processing, 70:1142 1154, 2022b.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Ahmad Rammal, Kaja Gruntkowska, Nikita Fedin, Eduard Gorbunov, and Peter Richtárik. Communication compression for byzantine robust learning: New efficient algorithms and improved rates. In International Conference Artificial Intelligence and Stalistics, pp. 1207-1215. PMLR, 2024.
Felix Sattler, Hoburt Müller, Thomas Wiegand, and Wojciech Samek. On the byzantine robust of clustered federated learning. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech doi: 10.1109 /CA/II/AAA./77700000000000044400 and Signal Processing (ICASSP), pp. 8861 8865, 2020.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back-propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. PMLR, 2019.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In International Conference on Machine Learning, pp. 30992-33011 PMLR, 2023.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. In I. Guyon, U. Von Luxburg, S. Bengio, Н. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: https:///roceeednngs www.rdiinnnnnnnn....e.eemee cwtpripppcccpppprrrrreepeep ftlles//aperr/207/EEeee/
621 1211000888911166611446666000. Paper. pdf.
Haoran Sun, Wenqiang Pu, Minghe Zhu, Xiao Fu, Tsung-Hul Hui Chang, and Mingyi Hong. Learning con- tinuously optimize wireless resource in episodically dynamic environment. In ICASSP 2021-2021 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 4945 4949. IEEE, 2021.
Davoud Ataee Tarzanagh, Mingchen Li, Christos Thrampoulidis, and Samet Oymak. Fednest: Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, pp. 21146 21179. PMLR, 2022.
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Reller- meyer. A survey on distributed machine learning. Acm computing surveys (csur), 13(3):1-33, 2020.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583- 4596, 2020.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainly in Artificial Intelligence, pp. 261 270. PMLR, 2020.
Chao Xue, Xiaoxing Wang, Junchi Yan, Yonggang Hu, Xiaokang Yang, and Kewei Sun. Rethinking bi- level optimization in neural architecture search: A gibbs sampling perspective. In AAAI Conference on Artificial Intelligence, 2021. URL https://api. semanticscholar. wwwp::oppo/D..103533353055
Yi-Rui Yang, Chang Wei Shi, and Wu-Jun Li. On the effect of batch size in byzantine-robust distributed learning. In The Twelfth International Conference on Learning Representations, 2024a. URL https: //openreview www.:eee//teeeeee
Yifan Yang, Peiyao Xiao, and Kaiyi Ji. Simfbo: Towards simple, flexible and commmiiation.-ffiiiett federated bilevel learning. Advances in Neural Information Processing Systems, 36, 2024b.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International conference machine learning, pp. 3650-5658 Pmlr, 2018.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI Conference Artificial Intelligence, 2018. URL htttp::/app..mmmtticccchob
www.sti wtt.cccoo......ooooorraaaaa.... 53285773
Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference on Machine Learning, pp. (0093-26712. PMLR, 2022.
Yihua Zhang, Prashant Khanduri, Ioannis Tsaknakis, Yuguang Yao, Mingyi Hong, and Sijia Liu. An intro- duction to bilevel optimization: Foundations and applications signal processing and machinc learning. IEEE Signal Processing Mogazine, 41(1):38 59, 2024. doi: 10.1109/
Shiyuan Zuo, Xingrun Yan, Rongfei Fan, Li Shen, Puming Zhao, Jie Xu, and Han Hu. Byzantine-resilieut federated learning employing normalized gradients on non-iid datasets. arXiv preprint wxXi:22488005339 2024.
16

---

Published in Transactions on Machine Learning Research (09/2025)
A Appendix
A.1 Useful Lemma
In this subsection, we prove lemma that relates the gradient of the lower level functions with and without aggregation.
Lemma 6. Suppose the aggregator RAgg is (a, robust aggregator (see definition 1 then
yygag Xr, Vr.)) yg (x.)
4ca
It follows from the definition [ of (ax, c)-Robust. Aggregator that the above result can be shown provided we prove a bound on E V/VVyl (ra) yy (x.. where the expectation is with respect to uniformly randomly chosen i.j E g. Adding and subtracting the term Vyg (x,, and using the inoquality ||a + bl]² < 2||a|| + b|]b we get
Proof:
E yy (r.)
Vygs (r.)l1
$ 2B || | Vy9: (x,, Vyg (x,, xr,e)11
2E Vygg Nr) Vyg (x,, (x,, Fr,t) 1
4Bieg || Vygi (x) - Vxy (xr,
(15)
Using the inter-client heterogeneity in Assumption 3 the above bounded as
FRe V y (x,, Vyg (X.. yra)il
S C2.
(16)
Using this in equation
15
we get
E | y&t (x,, Vygj (x,, Yr,))l
4G2
From the definition 1 of (a, co-Rus Aggregator, it follows that
Vygag (r.) Vyg (x.) 1|
4cal.
This completes the proof.
B Proof of Lemma 1
In this section, we prove bound on || Vyhx.ag (x.. - V Vyhx (x)] to show robustness of the aggregator
with respect to the penalty function. From Definition D we know that robustness can be proved by proving a bound on E hh, (x,,yr) - Vxha, (r)ll, where expectation with respect i, uniformly sampled
from G. Adding and subtracting the term Vyha (xr, and using the inequality ||a + b1l² s 2 ||a|] + 2 [|b]] we get
E
- -yliss (xr,
S 2E, | y (X,, yr) - Vyhi (x,, + yr)11
2,, || Vyli, y.) Vyha (Xr, y=)
4E.co Vyli,, (X,, yr) Vyhe (xr, v+)1
(17)
Consider the above equation, Le., A = Eieg h/,, (x,,y,) - Vyhy (xr,, xr)11 Vyhis (x,, Vyfi (x,,yr) + AVys (x,,y,) for all E g and Vyha y,) Vy (x,, +
Substituting
AV A (x), we get
A
E Vy.l (Xr, AV y (x., Vy (xr, y.) XV 1
(a)
<
2 VVyff (x,,y.) V, y,) 2E X2 Vyg (x,. - (x,,))1)
<
2 2
(18)
17

---

Published in Transactions on Machine Learning Research (09/2025)
where (a) follows from the inequality, ||a + bll - 2 ||a|l2 + 2 [[6|] and the last incquality follows from the heterogeneity Assumption
3 Substituting the above in equation 17 get
E V hy, (x) Vyhys yr)ll
8C} + 8x2
From the definition Tof (a, c)-Robust Aggregator,it is clear that the output of robust aggregator satisfies
Vy (x,,,,)~ - yylaa (x)11 s ca (867 8X ()
This completes the proof.
C Proof of Lemma 2
In this section, we prove bound on V Axrag (x): Vaha (xr, vr)
Towards this, we need to first
prove a bound on (see Definition from G. Adding and subtracting the term Vxla Vr) to the above and using the inequality I|a + bl| < ||all + 2|bb we get
nn Vxhxa (x,; Nr) where i are uniformly chosen
E
V Vahi, (x)
Vxhas (x).
23,e0
V Vx (Xr; Vxha (x,, yr)
1
2g
Vzhxs (xr,
Vxha (x,, Nr.
12
= 4E,e9
Viyx, (r) Vxha (x Nr
(19)
The following lemma required to prove a bound on the above equation.
Lemma 7. Under Assumption 3 the following bound is satisfied
Bieg V (r) Vxhxs (x):
4X21.3 max (X 6C3 12x (20)
Proof:
Towards bounding the above equation, let add and subtract the term (xy,8r)
1 Exeg hxss (r) (see Lemma
Esg Vzhna (xr. Vxhaa (x,,
Breg V (x,, - Vañe (x..8r)
V Vuda (x,, Valea vr)
2 B,eg Vahix (x.. - Vahu (x (x.. +
= 2 Vehi (xr.yr) Vxhar (x).
(21)
=A2
where the above follows from the inequality ||a + b1l² 2 2|]l + |Bb12_ Consider
A = Eseg Vahaa (Xr, - Vulua (x.. v.)
18

---

Published in Transactions on Machine Learning Research (09/2025)
Substituting Vx (x) =
+ A (Vxi (x,, Vx9 (x,, from equation 9 and Vxhi (r) = Vx (xr: + X (Vx (Xr, Vx (x., in the above, we get
A
Bies lI Vx/i (x,, + V x9i (xr: VxDi (x,, Vx (x)
X(Vx (r) Vxg (x.:
3 VxJi Y.) - Vx (x, yr) )1 3 Vx9i (xr: Vxg (x,, y+)1 3g 2 ||Vg V,,)) Vxg (x,, vnT)il?
(22)
where (a) follows from the inequality, ||a + b + c| 2 I 3 ||ll + |b| + 3 [|c]]. Now, consider
A s 3E, VV (x, Vx x,, yr )1 + 3, VV (x,, Vxg (x)
+ E. Vxg. (xr, Vr.)) Vxg (x., yr,)
< 30} + 2 '.
(23)
where the last inequality
follows from the inter-client heterogeneity Assumption 3 i.e.,
Ereg f[V (x. - Vf (x.
S s? and Exeg V[ (x.y) - Vg yx,,)) I Sg. Let us consider the
term Ag from equation 21
A2 = V\Vxis (x,,87) (x))))))) - (x.((xr. v.>|
Substituting V Vx (x) "xf(xx;8) A A(Vx (xr, V VxO (x,,) and Vxh( Vxf (x,, A (Vxg (x): VxU (x,)) in the above, we get
A I (x, A (Vxg(xx.)) Vxg - A (x,, Vxu (x,)) 11?
Simplifying further, we get
A S - (x..
Using Jensen's 's incquality, we get
2 G
A
5
Vxut (xx) - Vxga (xr, Vr.r)
G
k=1
X
1 d2
((x.) (V+:T)
IAG
X2L2 m.max ((x,) (yr,r),
ds
(24)
where (a) follows from the Assumption and 2 g,max maxkeg L2 Substituting equation 23 equation 24 in equation 21 we get
Eieg
V Vxha,
-v) (x). <
22 m.max (x) + +67 + 12X2
(25)
Using the results from equation 25 in equation Lemma.
19
we get the desired result. This completes the proof of the
To complete the proof of Lemma
2 we substitute the result from Lemma in equation 20 get
Eggg V (x)+ - Vahxas (x),
8x2 1.2
9 g.max g.max
12
744 T + (1 (1-
)²
16X T.2
9
max C2
2
Mg
+ +6C3 + 12X2
19

---

Published in Transactions on Machine Learning Research (09/2025)
Using the definition | of (a, c)-rousst aggregator, the output of the robust aggregator satisfies the following
Vxhx,ag (x)1)))) Vxhe (x,.
8X
g. g. g.max
(1
16A g.mxx COC,
S ca
2
+ +667 + 12)
(26)
This completes the proof.
D Proof of Lemma 3
Suppose Yr) is an approximate stationary point of FedBOB Penalty Problem, i.e.,
[V.h 1 yx) + y (x, yr)ll S thr
(27)
where b. > the approximation error. Then, for some v, such that ||v, S Vry the above can be written as
Vy (x) = -XVyg (x,, Vr. Rearranging the above, taking norms on both sides and applying triangle's incquality, get
V - |/yy (.). + vr.
Squaring on both the sides, we get
vx,,
2
(IVyf (x.. y+)1 +x?)
X2
WVB
2
1
Vy (x): +
X²
G
(
2
13
+ +
(28)
X²
where (a) follows from the inoquality ||a b1l s 2 ||||
||b|] (b) uses the Jensen's inequality, and (c)
follows from Assumption i.e., V yxl $ 13 for all E g. From Assumption we know that
1
Y.) gr (xr, y' (x,)) <
VV (x.,
(29)
1gg
Substituting equation 28 in equation 29
get
21
20
(x) = (x,,y,) - (xr,," (xx))
+
2g
Summing from == 0 to R 1, and dividing by R, get
ViolR R
R-1 p(x..).)
213 2g
R-1
Σ
+
(30)
R
Mg
R
Note that the result. in Lemma 3 can be obtained by choosing (x,, = (x for all r satisfying ,x,,,x(x, y)ll < th. This completes the proof.
E Proof of Lemma 4 and Lemma
In this section, we prove smoothness of the penalty function in Lemma 4 and bound on (s (y+,T)
Lemma E.0.2 Recall that yrr is the output of the Algorithm in step 12 which is used as proxy for arg miny y(x,,)) First, we state the proof of Lemma
20

---

Published in Transactions on Machine Learning Research (09/2025)
E.0.1
Proof of Lemma 4
Recall from equation 3 that the penalty function hx (x. = f + (x, Consider the following
/V V (xxxx,)') |Vyf (x.y) + XV y - Vyf(x,y') - AV yp (x,y')l
< Vy (x.y) Vy/ (x, y')l + V (x,y) Vyp (x,
The above incquality follows from the triangle's incquality i.c., ||a + bll Σ |||| + ||b]|- From equation 2 wc know that p (x, - (x, - g (x, y"), where y" E arg tilt (xx y). Using the fact that Vyg (x, y =0 in the above, we get
(x))) V'x( = 1x,/(x,,)) VyJ
(x.y) (x,
y (x.)) - Vyfa
+t
Σ
(V (x, - Vyga (x,
G
k=
6o (20 IN
Σ
G
A l y'1l
Σ
Lgg by yyl
G
k=1
(Ls.max + ALg.max) 11 - ylll
La - y'll,
where (a) follows from the triangle's inequality and Assumption 1 and (b) uses the fact that I.f.max == maxkeg Lyf and Lgmax = maxkeg Lg and (c) results from La L.max + Alegmmax. This completes the proof.
E.0.2 Proof of Lemma 5
First, note that in Lemma we have used Yr.r = yr,r- Using smoothness property from the Assumption we have
(Xr, Vræ+1) < g (r,t + (Vr,+11 Yrat Vyg (Xr, vra)) + Lg Ilyat1 -eall
2
Substituting the update in 6 i.c., Vr.41 = -y,t 1 y Vr.e) in the above, we have
L2Lg
g Nra+1) s 9 Vra) - 7( (Vyaag Nra). Vyg (x.. vr.)) +
V (x Frae)l
2
Using the identity (a, b) = _|aa|1² + =11bb122 - ||1aa - bll we gel
g (x.4.1))1 S g (ra) 2 V Vag (re) 11 1 V Nr.) 11?
L.g
+ 11 V
V (X,, vr.e) v 112
|| | (x, Nr.))?
(31)
2
Choosing 7 by in the above, and ignoring the negative term, we get
g (x.,)r
g (x.. 2 V Vr.e) 112 +
2 y y& (x.) Vyg (x.)
(32)
Using the result of Lemma the third term in the above is bounded as
V yag (x,, Vr.)) Vyg Vr.)) 12 4caC3.
(33)
Using the PT-inequality in Assumption
i.e., | (x.,. vr.))l 2 1y (g (Xr, Vr.) v(x,) and substituting
equation 33 in equation 32
we get
22 (g (x.) v(x,) + 2yya
g (r.41)) S ggg (x.)
2
21

---

Published in Transactions on Machine Learning Research (09/2025)
Adding and subtracting the term (x,),, have
g (r.+) v (x,) _ (1- 2 (g (xa) 27eac
Applying recursion, we have
(1- 2 (g (xx v(x))
1 7/12 $ y 2yya5
- 1 (xx) (x.1
(=0
Ti important to note that the Pl-ineeuallity implies quadratic growth condition, i.e., I Vr.T) - (x,) Mu 2 (xxx)) (Vr,T) for some By > Since g() satisfies the PL-inequality, invoking the quadratic growth condi- tion, we get
-
Lss,,) (YrT)
(1
214 T 2
(x - o (x+))
T-1
Σ t=0
11
N 2
27caC2
1gg
Next, we can further bound the above using the fact that the lower level function satisfies the Pl-inequality (see Assumption 2
d (xxx) (xr2))
2
(1
11Vg N.)1
+
Σ
(1
2 2rouCz.
(34)
f1y
2
2
t=
Using Assumption 1 i.e., [V yr)1
$ 12 have VVg (Xr,
S EE Vgg (x,, S 12 max
Using this in the above results in
& (ix.) (yr.T)
212 g.max
(1
7P4
T-1
Σ
1
7144/
1
2yca
(35)
2
1=0
The above is further bounded using geometric series as
212 g.max
4ca
d (x
(1-
i14gg
(36)
123
Fg
This completes the proof.
F Proof of Theorem 1
First, we state and prove the following Lemma, which is also useful while proving the violation bound.
Lemma 8. Suppose assumptions i 3 hold, then for the aggregator RAgg, Algorithm 1 achieves the following bound
B |1 (x)1
min 2
< (ʃ (x,,)r)) - f (x (x441)8++1)) + A (g 8x) (x (++1))
(u (xx+1) (xx))) + 3oor2 L caL
77 2 "opp²
23 9.maxx g.max (1 (1-214g
12
744g T
212
2
(37)
Pg
for B < L/Ln and 17 L,,,, and for any T 2 1.
22

---

Published in Transactions on Machine Learning Research (09/2025)
Proof: Using the smoothness result from Lemma we can write
hx Ve41)) ha (r) + (Xx+1 Xy, Vxha (x,, Vr)) + (yr+1 -r, Vylu (x,, Ln + 2
+
||x++11 - xrl1? + llyr+1 - yr1l?)
(38)
Substituting for the update x,+1 Xr -BV vhiss (x) and yr+1 -r y (x): from
equation 8 and equation 7
we get
hy (x++1,8++1)
S
ha (x), - B (ixii.0 (r), Vxha (x.. V (Vyyuxagg Vx), Vyl,, (x):
8 Ln V2his. (x vv) 112 L
Vyrea (x)
2
Using the identity (a. j1lal12 + 1/16122 - - - bll,, and adding and subtracting the term Vzhs (x),)r);
we have
1
Vx Vxlerae (x (xx.. 1||
B 2
hx (x+11,
h1 (x,, (,)
V (x.,,.)]'
2
3
V Vxhx.ng (+) - valua (xr,, Yr) + Vañu (x), - Valia (xr, No> ||
2
7
Vy Vylex (x.. 11
!
Vy,x (x,,, y. )| + 2 Vytii (Xr. - Vy 11
2
2
82
Tan Vixhss (xp, k7)
Tp
Tu
Vyhaag (x.. yr)
2
Combining the common terms, choosing 7 S 2 2||a]] + 21bbb we get
1 and B S +. and applying the inequality ||a+ bll s
9 hx (87+118011 S ha (x) - 2 V1Vx (x., y= + + Vxlix.no yr) - Vxhr 15) /|
+ V Vxhu (x) Vxha (x yr) ||
2 yyte (X5r. (x)1
"
V Vylis. (x) Vyht (x, yr)
(39)
2
Using Sx = Vxfi (X.. + (VV9 (x) Vxgi (x,)) in the fourth term above, we
get
G
Sx Vxlaa
(eeh( < (x, +1 (x. 1
Tx9 (x., (...)))))
V
G
k=1
(x).)))))) - -
(vng(x...)))
1
Σ
UxUR (xx) 112
G
Simplifying the above results in
1 G
1 G Vxtie (x+) (x))
2
Vahaa (x,. - Vxhr (x..
|
s x²
Σ
Σ
Vx9k (x (r.r)
G
G
k=1
1=
Using Jensen's inequality, the above is further bounded as
G
Vada (X). -Vxh (1))
V (x,) - -xar (X,, Nr.))
G k=1
G
12
((xx) ((x)))
G
222
1 Bix (Vr:T);
23

---

Published in Transactions on Machine Learning Research (09/2025)
where (a) follows from the Assumption 1 and (b) uses the fact that L g. result from Lemma in equation 40 we get
maXkeg Li Now using the
V (x) vx v,
2
g.max g.max
(1-
T
+
4
g.max cac
(40)
2
Mg
From Lemma 2. the third term in equation
39 can be bounded as
V wxda (xr.
Vxha (Xr:
(x.: yy) | 5 cad2
(41)
12 12
16A 20
where 82
p.max
2
+ 6C3 + -2 Similarly, from Lemma
the last
term in equation 39 is bounded as
Vy (x) - Vyhi (x..
1 cap².
(42)
where x ca (823 8A.
Substituting equation 40
equation
41 and equation 42 in equation 39 we
get
h1 (x++))8+41))
S hx (x,
VV
? [Vyl, (x,, (+)1 + Boad² 2
capp
-2
2,32 g.max g.max
12
(1-
7/4
T
2,922
cOC
2 +
H2
Mg
Rearranging and using the fact that hx [ + (g)xx.)) - - (x)); the above becomes
B
2 || xx (x., v.)1 " Vy (x,,
S (x),, >g (x,. - v (x,))
(r41) - -A (X++1,y++]) 1 (x++1))
+Bo088 + 1 caxp² +
2, m. 12
g.max (1
7Hg
T
11
2
2 max cat
(43)
Hg
8 n Using the fact that, min 2: 2 results in the bound of Lemma This completes the proof of the lemma.
|/
y.)] < || Vxhx (x,, y+)l +)1 y (xr, and rearranging
Completing the Proof of Theorem 1 Now, summing both sides of the the bound of Lemma g in
results
13 R
min
Vhx (x)1
S (f (X). - (x). + X (Xo. (xR.YR)
2 r=0
X (u (xx)) - (xo)) + 3Read²
+ Reap" +
7
2
23RX²
L max g.max (1-
12
71
T
+
23 L
max caC
(44)
22
2
Pg
Since we need n, S 1/L,, we assume that both 1) and B are of the same order. This results in
R-1
(Xo. yo) - (xR.
+ (gg (o) g (XR. VR))
|h, (x)1
<
2R
π
X (( v (Xoo)
22
12 m. g.max (I
7/4g T
+ cas²
+ _appp² +
nR
2
#
2
2x g.m C
(45)
Pg
24

---

Published in Transactions on Machine Learning Research (09/2025)
We wish the second last term on the right hand side in the above equation to satisfy
2A L m.max g.max
(1- 7M4
(46)
R
The above condition is achieved by choosing T 2 2 log
2/1
max
this makes the communication
7Pg
M
complexity slighter higher than the conventional second order methods
This will be relaxed in the next
result that we state. Substituting equation 16 in equation 45
we get
(xo, yo) f (xR. VR))
+ (g (xo, yo) - 9 (XR, yR))
Vhy (x):
<
2R
nR
nR
A (v (xR)) - U (xo))
1
22
g. max C0C
+ ca0²
_capp
+
+
1
2
R
ng
Now, substituting for 8 and p², we get
1
Σ
Vhx (x)1
(o) - I (x):
+
A (x), (xn: (x vxxo))
2R
n
nR
7R
8X2 I2
9. g.max g.max
12
(1- 744
822L2
g.max g...aaaaci
c
+ +GC7 + 1-122
M9
1 +
2X L2
g.max COC
+ ca (8C} + +222(2
+
2
R
Pg
88X L2 max 12
Suppose, we choose T 2
2 log 7ag
the above is further bounded as
1 R-1
(f (o) (x))
( (x0: yo)
g (R):
/h> (x)1
2R
n.
nR
A (xo)) - v (xR))
co
822 g.max
a
+ 6cacs + 12cax2
nR
R
Hg
2x
+4ca(3 4ca +
+
g.max
R
Hg
Rearranging the above, multiplying by 2 both sides, and using only those terms that depend on À and R, we get the desired order result of the theorem. This completes the proof.
G Proof of Theorem 2
In order to prove the Theorem, we need a bound on the stationary point of the penalty function (see Lemma
More specifically, we need a result of the form ||Vhx vx)|? < wh? Towards this, consider equation 37
of Lemma
S
B ? 2
min
|hx (x)) s (f (xr.)r) - -f (x++1. + X (g (x,, (x++1)
X (u (x++1) - (x.))) + Boad² + 11
capp +
2
2 g. g.max g.max (1 (1- 714
233
max coC2
(47)
42
pg
25

---

Published in Transactions on Machine Learning Research (09/2025)
Dividing by X? and using the fact that min { a 1
y + max. and further rearranging, we
1
2 2hn
get
21 f.ax (S (x) - / (X-+1:-r+1)) +
2 2l.gamax (S (Xr:8r) - S (x-+1,)r+1)) + x
As || Vhi yx)l
X2
m.ax (g (Xr, Yr) - 9 (Xx+11)r++)) + 22ggmmxx (9 (xr: - 9 (x,+1,8++1))) A
f.ax (v (Xx+1) - U (x+))) X
-2 y.ax (xx++1) - (x,,)) + 2ca02
2x g.max g. g.max
(1-
T +
22 g. casa
tcop22 +
1211
2
2214g
22 max 12 p.max
Choosing
2 log T>
we gel
1/3
1 xK
2L max (f (x) - f (x++1,))+11) g.g.max (f (Xr, f (xx++ A
//h (x.1
x2
mmx (g (Xr, - 99 (xx++1)8+11)) + +. (g (Xr. - 9 (xx+11,
2 f.mx (v (Xy+1) -2 -x(x)))
g. (u (Xr+1)) - 1 (x+)) + 200082
1
22
g.max Ca
+cap² 2 +
X2R
X²pg
Summing from = 0 to R - 1 and simplifying, we get
R
R-1 1 2L (f (xx.yr) - ff ((+1)) R- 1 2L (f (x). - f (x++1,
Vhy (x,, 82)1 A
X
A2
A
m (g Nr) - (x++1)
R-1
+ 22 max
Σ
(xr: 2 (x++1;)041))
r=0
m (o (xx+1) 1 (x+)))
22 m.a.
Σ
(w (x++1) 1 (x+)))
+
R-1
20082
+
R-1
cap2
+
R-1
Σ
1
R-1 2x
g.max cars
(48)
X
X2
X2R
X211,
r=0
r=0
Using the telescopic sum, we
get ΣR (f (xr, Yr) f (X,+1,
f (xp, (()x
R-1 (g (x) - g (x+1) = g (Xo, yo) - (xR. yR) and Σm=o
R-1 (u (Xx+1) - u (x,)) = v (xx) - 2 (Xx).
Using these results in equation 48
we get
R-1 Σ X2 /h (x,1
22 m max
2 mmx
S
+
(f (Xo. - f (x yn)) +
X²
A
22 f
+ +.
(g (x). - ((xR.YR))
f.
2L
2Rca02
Reap?
+ 2L g. g.max
(u (xxo) - e (xR)) +
+
+
A
X2
X2
1
2RX2 L2
g. g.mnax cOC
(49)
X
X2 Pg
From Lemma 3
we know that
2RI2
R-1
ViolR
<
+
Σ
(50)
A² X2
0=0
26

---

Published in Transactions on Machine Learning Research (09/2025)
Substituting equation in equation 50
49
get
2R12
f2L
2L.g.mux
ViolR
+
(f (x). - (xR:YA) +
Hy
1
A
2
2
f.mxmaxx
+ 22
(g (x). (xn: +
Pg
X
2
f.mxx
+ 22 22Lg.
(x(x)) - (x(RR) +
Mg
A
4Rca82
2Reap²
2RA
g. m,axx ca
(51)
2g
Ug
1
X2
Now substituting for 8² and p², we get
2R1
2
2 2.g.aux
ViolR
(f (X). - (x)) +
1g 22
Mg
X2
A
2
y
+ +2Lg,max
(g (X) - (xR.) +
19
A
2
2 f
+ +2Lg.max
(o (xx) - v (xRR) +
Pg
A
4Rco
82
1...g.gma.. g.max g.max
12
(1 TH4 T +
82 g.max C
+ 6C7 + 12X2(2
2g
Pg
2Rex
2RX² g.max COC
(827 + 2
+ X2
2g
221g fgg
1882 12
n.max 12 mg
Now, choosing T>
2 log mps
m.max
we get
2RI
f2
2Lg.max
ViolR
+
(f (x) - (foo)--(xx3:3 (xR: +
Pg
X2
Hi
X²
2
2L f.mxx
+ +2I.
(xo: g (xR.YRR) +
Pg
X
2
22
+
+. g.ax
(v(xo) - -x(xn)) +
Pg
A
4 4eca
1
8221,2 1.2 max C0C2
+ +62 + 12X2
+
2g
R.
fgg
2Rcx
2RX² L2 g.max caç?
(823 + 8X
+
(52)
2g
2²p1
Dividing on both sides of the above equation by R results in the following average violation
ViolR
21;
2
(2Lx,max
2I mgg.max
+
+
(f (xx. (xn. +
R
Ug
22
Rig
X²
2
f.
21 2I. max
(g (x(x - (x): +
Ritgy
2
22T
2L y.axx
(v (xo) v vxxx) +
R1g
4ecc
32L²
g.max
20262
24ca5
+ 48ca8(
+
Rjig2
23
2g
My
16caC
16ca?
212 gmax ca5?
(53)
2g
Mg
RX2
Mg
27

---

Published in Transactions on Machine Learning Research (09/2025)
Now, retaining terms that depend on X, R and a, get the order result stated in the Theorem. This completes the proof.
H Examples of ca,c)-Robust Robust Aggregators
Though many robust aggregators have been proposed in the literature (Chen et al. 2017 Pillutla et al, 2022b), they do not satisfy the dcfinition Also there are many new attacks where the methods using these aggregators fail to converge.
In this section, we present the aggregators which when used with the bucketing algorithm, introduced Karimireddy et al. (2021 2020) satisfy ca.cb-robust aggregator definition
Geometric Median: Also known Robust Federated Averaging (RFA) (Chen al. 2017
Pillutla et al.
2022b) where aggregation is performed using geometric median:
X2, ... XN)
arg min Σ
x xi|l
Coordinato-wise Median: CM is an aggregator which performs co-ordinate wise median:
[CM(x), x,, xn)]; Median((xi]j, (x2]j:.... [xwli);
where [xly the jth component of vector x.
Krum: Krum finds vector x₃ which is closest to the mean of the input vectors when |B] - vectors are excluded
Krum(x; (x,, X,,
xn) = arg min
Σ JESz
|x,
x,
x (x,,..,,,)
28


Reviews:
[{"review_id": "AjUb6g6UP9", "reviewer": "Reviewer_eVJZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n[S1] The paper discusses an important and difficult problem of bilevel optimization in the presence of Byzantine nodes.\n\n[S2] The paper is well written and easy to follow.\n\n[S3] The algorithm is 'second-order free', and hence, computationally efficient.\n\n## Weaknesses\n\nI mainly have concerns with the experimental results section.\n\n[W1] While the authors mention that they ensured the data distribution is heterogeneous, there is no mention of how this was ensured and what level of heterogeneity is exists in the client datasets.\n\n[W2] This is more of a question: I do not understand how the figures 1-4 show the effect of heterogeneity. The text is also not explicit about this.\n\n[W3] The experimental results only show the convergence rates and the policy violations. It would make the paper stronger if the authors also present the actual convergence curves of the task given their method. It would also be nice to how close the results get to the optimal convergence. In this case, comparing against the concurrent Hessian-based federated bilevel optimization solution (Abbas et al., 2024) would also make the results more convincing. Of course, the convergence results do not have to be better than the Hessian-based solution because it is much more computationally expensive. But, having and discussing them would add to the completeness.\n\n[W4] The paper mentions that the approximate problem \"boils down to a single level federated learning problem in the presence of Byzantines\". I am not convinced why we shouldn't do this. Adding to [W3] above, would it be better or worse experimentally?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an approximate solution to the Federated Bilevel Optimization problem in the presence of Byzantine nodes. The approximate solution utilizes a penalty function to convert the problem into single-level optimization. The authors study the convergence rate in the presence of data heterogeneity and the policy violations. The experimental results study the convergence rate on MNIST for varying number of communication rounds R in the presence of 20% and 40% Byzantine nodes out of 16 total nodes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In general and as a high priority, I would request the authors to address the weaknesses above.\n\nAdditionally, I have some nitpicky concerns which the authors may choose to act on or ignore. This will NOT positively or negatively affect my stand on the paper.\n\n[N1] Split Algorithm 1 into the algorithm for the server and the algorithm for the client. It would make it easier to understand.\n\n[N2] Add attack names to the figures instead of just having them in the captions (Figures 1-4).\n\n[N3] Providing code for the experimental results would be really helpful to the community. Any code is better than no code.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WKdG2nOznN", "reviewer": "Reviewer_fCue", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is solid. However, I am an outsider of this field and found it hard to understand several points. The writing has room to improve.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work aims to solve federated optimization problem with byzantine nodes. A computationally efficient and robust algorithm using only first order information is proposed. Theoretical guarantees and experiments are provided to validate the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most issues are related to definition and concept discussion, including\n\n1. The problem of Federated Bilevel Optimization with Byzantine (1) involves upper and lower level objective functions. It would be clearer if the authors can explain what are the upper and lower level objective functions, especially with concrete examples such as in the experiment section. This problem only involves good nodes. I always have the question how Byzantine nodes are involved and impact the optimization?\n\n2. The first paragraph of Problem Statement, 'We consider a federated ... resilient to the Byzantine attacks.' is largely duplicated with the introduction.\n\n3. Can you elaborate how the dual problem in (4) is obtained? Also, more discussion on \"solving the above problem is approximately equivalent to solving the original problem\" will help readers understand this formulation. Moreover, why (4) is a single level federated learning problem, how do you define a 'single level' optimization problem?\n\n4. About assumptions:  (1) in assumption 2 PL inequality, I was wondering if the first part assumption on each good node implies the second part assumption; (2) the expectation in assumption 3 is taken with respect to what?\n\n5. Can you explain why access to $g(x,y)$ is not available at each node? Is the objective function still well-defined?\n\n6. 'where RAgg uses bucketing followed by geometric median aggregation (see (Karimireddy et al., 2020) for more details).' Same as before, discussion is encouraged for clarity and completeness. \n\n7. At the top of page 6, $k\\in[N]$ and $k\\in \\mathcal{G}$ are not consistent.\n\n8. Can you elaborate why does Lemma 2 shows 'the robustness depends on how close the proxy yr,T is to the actual optimal y∗(xr) captured through the first term in δ2\". How does $\\delta$ reflect the closeness?\n\n9. The convergence rate is $O(\\lambda/R)$ or $O(\\lambda^2/R)$? Why the order in (11) does not involve $\\lambda$?\n\n10. In lemma 3, the condition $\\Vert \\nabla h_\\lambda(x,y)\\Vert \\leq \\psi$ should hold for any x,y? How strong is this assumption? Moreover, the bounds in Lemma 3 and Theorem 2 do not related to $R$. This means that violation is of constant order and cannot be reduced along the update. Can you provide any insight on this? Why is this result interesting?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "m5JU4DXm53", "reviewer": "Reviewer_cDCn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThis problem is interesting. Solving a bilevel optimization problem in the FL setup with non-iid data and PL condition is interesting. This problem is new, although a little artificial. \n\nThe paper is well-written and easy to follow. \n\nThe authors provided a complete and nice solution to this problem, where the key idea is to leverage inner iterative GD update to approximate the optimal point of the inner optimization problem, at the cost of additional $O(log R)$ communication complexity compared with existing FL methods. \n\n### Weaknesses\nThe arguments of $O(R\\log R)$ communication complexity are a little trick. The authors should also explain when $O(R)$ communication complexity is fixed, this paper can only achieve a near-optimal $O(\\log R / R)$-type convergence rate.\n\nAs for assumptions, this paper requires $f_k$ and $g_k$ to be Lipschitz and smooth. However, it not only requires $g_k$ to satisfy the PL condition, but also requires the averaged $g$ to satisfy the PL condition. My question is: Is such a requirement on the averaged function also needed in previous works? Some necessary discussions of the assumptions compared with previous works are needed here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the novel and challenging problem of Federated Bilevel Optimization in the presence of Byzantine nodes (FedBOB). The authors note that this problem is largely unexplored, as existing works typically focus on either single-level robust optimization or non-robust federated bilevel optimization.\n\nTo overcome the computational complexity of traditional second-order methods and the security risks from malicious nodes, the authors propose Rob-FedBOB, a computationally efficient and robust algorithm. The key innovation is to reformulate the federated bilevel problem into a single-level penalty-based optimization problem, which makes the proposed algorithm fully first-order and Hessian-free. The algorithm is designed to work under more practical and relaxed assumptions, including heterogeneous (non-iid) data across clients and a non-convex lower-level objective that satisfies the Polyak-Łojasiewicz (PL) inequality.\n\nThe main contributions of the paper include:\n\n1. Theoretical Performance Analysis: The paper provides a convergence analysis for Rob-FedBOB, showing that the convergence rate depends on the number of communication rounds, the fraction of Byzantine nodes ($\\alpha$), and the data heterogeneity. In the absence of Byzantine nodes, the algorithm achieves a convergence rate of $1/R$, where $R$ is the number of communication rounds.\n\n2. New Performance Metric: It introduces and analyzes a new notion of average constraint violation, providing a bound that highlights the trade-off between convergence and constraint satisfaction, managed by the penalty parameter $\\lambda$.\n\n3. Experimental Validation: The theoretical findings are empirically corroborated through experiments on applications like data hyper-cleaning and learnable regularization under various Byzantine attacks (e.g., Bit Flipping, Label Flipping).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some minor suggestions:\n1. On the top of Page 3, when introducing the results of this paper, the meaning of $\\lambda$ is not explained at all, which may confuse readers. The authors are encouraged to add an explanation like \"$\\lambda$ is a punishment parameter in the algorithm xxx\".\n\n2. In the third line of Assumption 2, should it be $v_k$ but not $y_k^*$?\n\n3. On Page 7, it should be $O(\\lambda^2/R)$ but not $O(\\lambda/R)$.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)