Single-Loop Byzantine-Resilient Federated Bilevel Optimization
Authors: Yangnan Li
Shenghui Song
Xuanyu Cao
Venue: ICLR 2026 Poster (2026)
Keywords: Bilevel optimization
Federated learning
Byzantine robustness
Primary area: optimization
TL;DR: This work aims to bridge the gap between bilevel optimization and Byzantine-resilient federated learning.

Abstract: Federated bilevel optimization plays a crucial role in solving complex problems with nested optimization structures. However, its distributed nature makes it highly susceptible to faulty or Byzantine behaviors. Existing Byzantine-resilient approaches are either restricted to simple single-level optimization problems or rely on sub-loop updates that introduce significant computational and communication overhead. To address these limitations, we propose a family of Byzantine-resilient federated bilevel algorithms, which (i) operate within a single-loop structure, (ii) achieve optimal Byzantine resilience, and (iii) ensure computational and communication efficiency. The core of the proposed method, BR-FedBi, leverages an auxiliary variable that facilitates efficient hypergradient estimation while simultaneously solving the lower- and upper-level problems. Building on BR-FedBi, we further integrate the algorithm with Polyak’s momentum and the probabilistic gradient estimator (PAGE) (Li et al., 2021), resulting in provable optimal Byzantine resilience and optimal sample complexity. Both theoretical analysis and empirical results demonstrate the superior performance of the proposed algorithms.

Published as a conference paper at ICLR 2026
SINGLE-LOOP BYZANTINE-RESILIEN FEDERATED BILEVEL OPTIMIZATION
Yangnan Li', Shenghui Song Xuanyu Cao²
The Hong Kong University of Science and Technology 2 Washington State University (yl (ylity)e @connect. .k, (eeshsong) @ust.hk, xuaanyu, cao) @wsu.
ABSTRACT
Federated bilevel optimization plays a crucial role in solving complex problems with nested optimization structures. However, its distributed nature makes it highly susceptible to faulty or Byzantine behaviors. Existing Byzantine-resil ressilent ap- proaches are either restricted to simple single-level optimization problems rely on sub-loop updates that introduce significant computational and communication overhead. To address these limitations,
propose family of Byzantine-resilient federated bilevel algorithms, which (i) operate within a single-loop structure, (ii) achieve optimal Byzantine resilience, and (iii) ensure computational and commu- nication efficiency. The core of the proposed method, BR-FedBi, leverages an auxiliary variable that facilitates efficient hypergradient estimation while simulta- neously solving the lower- and upper-level problems. Building on BR-FedBi, we further integrate the algorithm with Polyak', 's momentum and the probabilistic gradi- ent estimator (PAGE) (Li et al., 2021b), resulting in provable optimal Byzantine resilience and optimal sample complexity. Both theoretical analysis and empirical results demonstrate the superior performance of the proposed algorithms.
INTRODUCTION
Federated Bilevel Optimization (FBO) (Tarzanagh al., 2022; Xiao & 2023) has recently emerged as a powerful framework for tackling machine learning problems with hierarchical structures in distributed settings. By distributing the computational workload across multiple clients, preserves local datasets' privacy and mitigates the computation burden central server (Haddadpour et al., 2019; Li et al., 2020). Practical applications range from federated meta-learning (Finn et al., 2017; Hu al., 2021) and hyperparameter optimization (Franceschi et al., 2018; Akiba et al., 2019) to imitation learning and federated reinforcement learning (Husscin et al., 2017; Li, 2017), demonstrating the versatility of bilevel formulations. The general formulation of the federated bilevel optimization problem is expressed as:
Σ lxxxxx())) 1
min ((x)
ES
XER
(I)
subject to yx))) = arg min
Σ 9. (x,,)
1 Σ E.p. [G
yER
where x E IR denotes the upper-level variable, y R represents the lower-level variable, and denotes the number of clients. Each client i possesses a local upper-level loss function fi( and lower-level loss function gi (x, y) We consider objective functions expressed expectation form, where di and sp; represent random local data samples of client i which usually follow unknown and heterogeneous distributions across different clients.
Despite its effectiveness, federated bilevel learning also faces critical challenges, including increased communication costs (Cao et al., 2023; He et al., 2024), privacy concerns (Wei et al., 2020), and vulnerability to attacks (Baruch et al., 2019; Xie et al., 2020). In this paper, focus crucial aspect of federated bilevel learning: Byzantine resilience the capability of distributed systems to maintain reliability in the presence of Byzantine attackers (Karimireddy et al., 2020a; Allouah

---

Published as a conference paper at ICLR 2026
et al., 2024). Specifically, during the training process, some anomalous participants (i.e. Byzantine attackers) may submit corrupted or malicious information to the central server, thereby compromising result from hardware or software
the accuracy of the global model. These abnormal behaviors malfunctions (Armstrong, 2003), data poisoning (Zhang et al., 2020; Yerlikaya & Bahtiyar, 2022), or adversarial entities controlling parts of the system (Baruch et al., 2019).
Numerous prior works have focused on defending against Byzantine attackers, leading to the de- velopment of robust algorithms in both theoretical and practical contexts (Blanchard et al., 2017; Karimireddy et al., 2021; Gorbunov et al., 2022). However, most of the works primarily focused on single-level optimization, while advanced tasks in bilevel optimization involve inherently nested formulations, which extend beyond the capabilities of singlc-level approaches. Solving bilevel optimization problems in the presence of Byzantine attackers challenging. In federated bilevel optimization, the computation of global hypergradient is not a straightforward aggregation of local hypergradients. Additionally, data heterogeneity unavoidably prevents any aggregation algorithm from reaching the optimal point with 6-proportion of Byzantine attackers (Karimireddy et al., 2020a; Allouah et al., 2023). Due to the hierarchical structure of FBO, the asymptotic error becomes further amplified as the heterogeneity level increases in both the lower- and upper-level objectives.
In this paper, we aim to bridge the gap between federated bilevel optimization and Byzantine resilience by addressing the following research questions: (i) What is the lower bound of the asymptotic error caused by Byzantine attackers in bilevel optimization? (ii Can any bilevel algorithm achieve this lower bound and atlain optimal Byzantine resilience? To answer these questions, we propose family of single-loop Byzantine-resilien bilevel algorithms that facilitate efficient hypergradient estimation while ensuring high efficiency in both communication and computation. Our key contributions are summarized as follows:
Lower bound for asymptotic error. We derive an algorithm-independedd lower bound on the asymptotic error induced by Byzantine attackers in bilevel optimization. This result highlights the fundamental limitations imposed by heterogeneity and Byzantine attackers, extending existing lower bounds from single-level optimization to the more complex bilevel setting.
Achievable optimal Byzantine resilience. We propose single-loop Byzantine-resilient bilevel algorithm, BR-FedBi, that eliminates the need for frequent gradient exchanges, significantly improving both efficiency and robustness. Building upon the framework of BR-FedBi, we further incorporate Polyak's 's momentum (Polyak, 1964) to match the established lower bound, achieving optimal Byzantine resilience and demonstrating the tightness of the theoretical lower bound.
Communication and computational efficiency. BR-FedBi achieves a communication com- plexity of (c-")) and demonstrates linear speedup with respect to the number of honest clients. Furthermore, by incorporating PAGE variance reduction techniques (Li et al., 2021b), the algo- rithm attains a sample complexity of O(E-1.5) under the mean-squared smoothness assumption, matching the optimal sample complexity in general expectation setting.
Experiment evaluation. Experimental results the hyper-representation task demonstrate that the proposed methods significantly outperform existing approaches under various Byzantine attack scenarios, in both homogeneous and heterogeneous settings.
1.1 RELATED WORK
Asymptotic error for Byzantine-resilient distributed learning. The convergence behavior of Byzantine-resilient distributed learning has been extensively studied over the years (Karimireddy al., 2021; Farhadkhani al., 2023; Allouah et al., 2024). More recently, research has focused on analyzing the convergence behavior in heterogeneous settings (Karimireddy et al., 2020a; Allouah et al., 2023; Liu al., 2023: Murata et al., 2024). In this line of work, Karimireddy al. (2020a) was the first to establish the lower bound on the asymptotic error, given by 52 (ōς²). Building on this foundation, Allouah et al. (2023) proposed Nearest-Neighbor Mixing (NNM) algorithm, showing that most robust aggregation methods, when combined with NNM, are able to achieve an asymptotic error of O (6c²). Furthermore, Murata et al. (2024) introduced the Momentum Screening method and demonstrated that, under the assumption of maximum gradient heterogeneity Smax, this method achieves a smaller asymptotic error of 0882 when the condition 5 < (m/Gmax)² is satisfied. Despite these advancements, research bilevel optimization remains limited.
Federated bilevel optimization. Unlike single-level optimization, bilevel optimization involves a nested structure, making hypergradient computation particularly challenging. Various techniques
2

---

Published as a conference paper at ICLR 2026
have been developed to estimate the hypergradient, including approximate implicit differentiation (Domke, 2012; Grazzi et al., 2020), iterative differentiation (Maclaurin et al., 2015; Franceschi et al., 2018), and Neumann series expansion (Chen et al., 2023; Hong al., 2023). Recent efforts have focused on designing efficient bilevel optimization algorithms for federated learning and decentralized learning. For instance, Tarzanagh et al. (2022) introduced FedNest, federated bilevel algorithm based on approximate implicit differentiation (AID), while Xiao & Ji (2023) proposed an iterative differentiation (ITD) based approach that reduces communication costs. Dagréou et al. (2022) introduced SOBA, novel single-loop framework for solving bilevel optimization problems, and Yang al. (2024) extended their work to federated learning. Recent studies have incorporated communication compression (He et al., 2024) and differential privacy (Chen & Wang, 2024) into federated bilevel optimization. However, research on Byzantine-resilien federated bilevel learning remains scarce.
The most related work is (Abbas et al., 2024), which proposed a Byzantine-resilient federated bilevel optimization algorithm leveraging AID-based method. However, this approach involves sub-loop computations hypergradients and requires multiple communication rounds per iteration, leading to high communication costs and increased vulnerability to attackers. In contrast, study introduces a single-loop algorithm with reduced communication and computational overhead, along with a theoretical guarantee for achieving optimal Byzantine resilience.
PRELIMINARIES
2.1 PROBLEM STATEMENT
We consider distributed system with n clients, [n]] {I...., n). where most 8 < 1/2 proportion of them are Byzantine attackers. Such attackers have the ability to access honest gradients and may send well-crafted malicious updates minimize global honest loss of the bilevel optimization problem, defined as yx( (x)), where JH xx yx)) [.. EiER (x, yx))) and H S [n] represents the set of honest clients. Typically, we consider a Byzantine- resillent version of the problem (1):
the server. The objective of the honest clients to
min (x)
Σ yxxx,x(x)))
XER
H
iEH
subject y y"(x) = arg min IH (x,y), yER=
where (). := TH Σ EiER (x. and $ f- yx))x The goal of Byzantine-reste resilient algorithms is to minimize honest global loss and achieve an e-stationary point, even when d- proportion of the workers are Byzantine attackers. We formalize this concept Definition which introduces the notion of (6, B---yyaiinne--silllee
fx
Definition (ō, eiyyzantine-rsillennti A bilevel algorithm is considered to be (8, Byzzaniine resilient if, despite the presence of 8 5-proportion of Byzantine attackers, outputs parameter such that
E
[+ se
where (x = [P4] EIEN (x(x) denotes the global loss.
The key to achieving Byzantine resilience lies employing robust aggregators (Blanchard al., 2017: Pillutla et al., 2022; Murata et al., 2024), which are designed to maintain comparable performance even when a fraction of the workers are Byzantine attackers. To evaluate the effectiveness these adopt the (6, robbustenss criterion, proposed by Allouah al. (2023).
robust aggregators,
Definition 2 (ő, robuustsss)))) Let ā < 1 and k 2 0. A robust aggregation rule AGG(.) pdxx gd is said to be (8, robruussss if, for any vectors DI...., D,, IRd and any set S [n] of size (1 8ym, the following holds:
|AGG(DD,....D... D..) - DDs < K
ΣID, -Dsl'
S
iES
where D3 15 Dies D,. The term x referred to as the robustness coefficient.
3

---

Published as a conference paper at ICLR 2026
This criterion provides tight convergence guarantee and is satisfied by most robust aggregation methods. Notably, K has a theoretical lower bound given by x > I-25 which implies that no robust aggregator can achieve arbitrarily close proximity the average output of the honest workers.
2.2 ASSUMPTIONS
The following assumptions are used throughout this paper. They are standard assumptions made in the literature on bilevel optimization (Chu et al., 2024; He et al., 2024) and federated learning (Allouah et al., 2023).
Assumption (Lipschitz Continuity). For any honest worker i E H. the upper-level loss function Ji is Cy-Lipschitz continuous w.r.f. y. The gradients and Hessian matrices V., Vg,, &yy Vyy.9 are Lipschitz continuous with constants L,, Leg, Lug Lug, respectively.
Assumption 2 (Strong Convexity), For any honest worker E H. the lower-level loss gi is Pa strongly convex w.E. y.
Assumption 3 (Bounded Variance). For any honest worker i H. there exists o 2 O, such that the stochastic gradients and Hessians (x y: Vy, V (x pp;) and V G y: (p:) unbiased with bounded variance o².
Assumption 4 ((-gradient/Hessinn dissimilarity). The local gradient/Hessian A; of the honest worker H is said to satisfy S-gradien//Hessian dissimilarity if
1
A;
1
Σ SE
A
<
HH
H
SEN
The gradients (x(() and (x, of honest workers satisfy the Sy-gradient dissimilarity assumption.
The gradient/Hessians yy (x, y), V & y) and Vyy9: (x, of honest workers satisfy the Su grgadien//HHesiann dissimilarity assumption.
3 LOWER BOUND FOR ASYMPTOTIC ERROR
In Byzantine-resilient distributed learning, it is inherently impossible to fully eliminate the asymptotic error due to data heterogeneity. this section, we derive the lower bound on the asymptotic error induced by Byzantine attackers in bilevel optimization, illustrating that both lower- and upper-level data heterogeneity contribute to the asymptotic error.
The analysis of the lower bound is performed with slightly more general setting. Specifically, re- place Assumption with a more general heterogeneity condition, namely the (C, gradeiene/eiet dissimilarity assumption (Assumption 8 in Appendix E). When B O, Assumption 8 degenerates to Assumption 4, thus recovering the original setting as a special case.
Theorem 1. For arbitrary federated bilevel algorithm, there always exists a federated bilevel optimization problem satisfying Assumptions 1-3 and 8, such that:
(c7 +
( Ω
+ B3}
where 5 < min { 2++ 2 }
} is the proportion of attackers and x is the output of the algorithm.
Remark 1. The above lower bound generalizes the results previously established for single-level optimization problems. Specifically, by removing the term related to Eg. obtain the bound
sc?
Ω (3)(2+B3) which matches the lower bound for single-level optimization (Allouah al.,
2024). Moreover, under the (c, -grggdiient dissimilarity assumption, the breakdown point for the proportional of attackers is given by 8 < min 2+87 2+ }. indicating that is not fixed threshold of 2 but depends on the heterogeneity coefficients at both the lower- and upper-levels. Corollary 1. For an arbitrary federated bilevel algorithm, there always exists a federated bilevel optimization problem satisfying Assumptions 1 144, such that:
(x))))) 2 2 (C} + +(2) (7)
(4)
4

---

Published as a conference paper at ICLR 2026
where 8 < 1/2 is the proportion of attackers and & is the output of the algorithm.
Remark 2. Corollary can be viewed as special case of Theorem 1 by setting B, Bg 0. Notably, Karimireddy et al. (2020a) established lower bound of (2(6c²) for single-level optimization. Corollary extends this result to the bilevel optimization setting, highlighting that the inherent diffi- culty introduced by heterogeneity and Byzantine clients persists even in more complex hierarchical optimization problems.
4 SINGLE-LOOP BYZANTINE- - RESILIENT FEDERATED BILEVEL ALGORITHM
In this section, we propose the first Single-Loop resiiinn Federated Bilevel Algorithm (BR-FedBi), which extends the SOBA framework (Dagréou et al., 2022). The algorithm employs an auxiliary variable to enable efficient hypergradient estimation while preserving the robustness of the distributed system against potential Byzantine attackers.
4.1 DESCRIPTION OF BR-FEDBI
commonly employed strategy for bilevel optimization problems makes use of implicit differentiation (Griewank & Walther, 2008). In Syzaattinerrssllien federated bilevel optimization (BR-FBO), the expression of the hypergradient (x. y"(x)) can be written as:
Vxfi (x, (x)) - V2 2y yx,) (x)) [V yx,
1
Σ EE
Vyfi (x,
[
[H|
iEW
where the global Hessian matrices can be written as:
V Ky (x, y" (x))
1 y" (x)),
V VyysH (x.y (x))
V2 (x.
H
H
iEH
iEH
Hypergradient estimation. We extend the SOBA framework (Dagréou et al., 2022) to develop a single-loop solution for BR-FBO, which introduces auxiliary variable x (x) approximate the Hessian-inverse-vecte product:
1 Vyli [
z (x) == (1,
IEW
VyytH(X, y" Vy.xxxx 0. Although computing the exact z" is infeasible in practice, approximation be obtained by minimizing the following objective:
where z" can be seen as the solution of the global linear system:
1
Z (x) + ( Vyf((xx)))
H
12
The auxiliary variable enables the estimation of the global hypergradient using the expression: I. TR] Eien Vxf((x,y) + (2) where y represents the approximate solution to the lower- level problem.
As result, hypergradient estimation can be decomposed into three steps: (i) solving the upper-level optimization problem, (ii) solving the lower-level optimization problem, and (iii) estimating the auxiliary variable of Hessian-inverse-vectoo product z. Next, we provide the detailed procedure.
Algorithm procedure. The full procedure of BR- RR-FedBi is summarized in Algorithm 1 in Appendix C. the k-th communication round, the server distributes the global parameter (x*,y* 2² to the clients. Each honest client i E H computes the gradients using their locally sampled data, of Dr and " ~ gi and transmits them to the server:
D V Gi(xt yh of + Fx y (!))
(5a)
k y.j V,G, y (
(5b)
D Gi(" pl)e Fx (.))
(5c)
On the other hand, each Byzantine attacker may send an arbitrary value to the server. Upon receiving the gradients from all the clients (including honest clients and attackers), the server employs a robust aggregation rule AGG(-) dxx_ + dd and updates the global parameters o E {x* y zt with
learning rate Tee By, Tz > 0:
5

---

Published as a conference paper at ICLR 2026
AGG (D 0.1. 6++ -
.............
Do.))
(6)
I Before broadcasting z =11 to the local clients, projection operation is applied to ensure z lies within an balbal of radius p. which is defined as:
Pp (z min (1, |1 =
This projection ensures smoothness of the linear system and maintains the boundedness of the gradient updates for the variables x and both of which are essential for convergence analysis.
4.2 CONVERGENCE ANALYSIS
To establish convergence of BR-FedBi in Algorithm 1, the following additional assumptions are required. All proofs are relegated to Appendix G.
Assumption (Boundedness of gradient terms), There exists a constant Hx 2 such that, for any (x* 2*) produced during the iterations in Algorithm the following inequality holds:
V Yy TH (x* y x Vx/H (x* y > H
Note that this assumption milder than the Lipschitz continuity of fu. w.r.t. x in previous works (Lu al., 2022) and is similar to the one in (He al., 2024).
Assumption 6. Hessian matrices 2y Viyy are -mooth,,h, and F is Ly-Lisschitz continuous.
Theorem 2. Let 1/2. Suppose Assumptions 1-4 and 5-6 hold, and AGG(-) satisfies the (6, k))-
robustness criterion. Set the learning rates Tix min 01
A.
Mly Cy Tl C2
where Ag Au of K, Then, BR-FedBi converges as:
/²/((1 o
8)m) and Au, a1, Cy. Cz. A& are some positive constants independent
o² E |V [1V0 =o (VT-J) 6-jK
=o(vv=v
A K
+ +0
+0
K. (c3
+ +
(7)
where the expectation is over the algorithm's 's randomness.
Sample Complexity. BR-FedBi achieves a linear speedup with respect to the number honest clients (1 8).. The dominant term, (LI/vnK), demonstrates that increasing the number of participating honest workers improves the convergence rate. This leads sample complexity of O(e 2n 1). which aligns with the standard convergence rate of distributed stochastic gradient descent (D-SGD) for non-convex loss functions (Karimireddy et al., 2020b).
Asymptotic error. Theorem 2 shows non non-vanishing asymptotic error of (1x (2 for
BR-FBO, indicating that both lower-level and upper-level heterogeneity contribute to the aggregation error. Moreover, the error is influenced by variance-related term, O (Ro²), where o² is the noise variance of the stochastic gradients and Hessian matrices for both the upper-level and lower-level loss functions. This variance-related dependency limits the algorithm's 's ability to achieve optimal Byzantine resilience.
We further instantiate Theorem 2 by selecting the minimal robustness parameter O (8), which yields an explicit bound on the optimization error c, as shown in Corollary 2.
Corollary 2. Suppose AGG(-) satisfies the (ō, robuusttss criterion with it. O (8). Then, BR- FedBi is (8, B--BBaaninn-reslllee with: = o (v / . The asymptotic error of BR-FedBi has a term proportional to da². Compared to the lower bound in Corollary I, this additional term indicates that the algorithum achieves suboptimal Byzantine resilience.
n. +
ACHIEVING OPTIMAL BYZANTINE RESILIENCE
In this section, we extend BR-FedBi by incorporating the Polyak's momentum (Polyak, 1964), a.k a.k.a. heavy-ball momentum, resulting variant named BR-FedBiM. This improvement enables the algorithm to achieve optimal Byzantine resilience, i.e., achieving the lower bound in Corollary I, while simultaneously relaxing the bounded gradient assumption (Assumption

---

Published as a conference paper at ICLR 2026
5.1 INCORPORATING POLYAK'S MOMENTUM
The full procedure of BR-FedBiM is summarized in Algorithm in Appendix C. At each iteration k E [K] instead of directly transmitting the stochastic gradients, each honest client E H updates and sends local momentums of the parameters {x*, y 2t to the server,
m 3. + (1 -B) D
(8)
where 3x, Sy. E (0, 1) are the momentum coefficients shared by all honest clients. After receiving the local momentum updates of all the clients (including honest clients and attackers), the server applies robust aggregation methods AGG(-) and updates the global parameter.
For an aggregation method (GG(-) that satisfies the (6, robusttesss criterion, the aggregation error is uniformly bounded by times the drift between local gradients and the honest global gradients. The incorporation of momentum effectively mitigates this drift and eliminates the variance-related term in the asymptotic error. Specifically, for yx y, 2), the of momentum replaces the
drift term with E mm. - -= where m H. Eien m .. It can be demonstrated that the application of momentum reduces the variance-related error O (K (1 (%)) o²). Consequently, by setting the momentum coefficient Bo + 1, the variance-related error can be eliminated.
5.2 CONVERGENCE ANALYSIS
In this subsection, we establish the convergence guarantee for BR-FedBiM. Theorem 3. Let 8 < 1/2. Suppose Assumptions 1-4 hold, and the robust aggregation rule AGG() satisfies the (6, robbusinnss criterion. Set the learning rates as follows, Ax v L,g Tx,
By /I Lg, Tre B2 11--L8 txx thx minn a1
Tly Cy Tha Calbx, where
T.K K
A, Ago² /(1 8)n+ kAy0² Lon Loy, LB Cy, Cz a1, A3, Ag are some positive constants independent of K, Then, BR-FedBiM converges as
E [[Vvn(())]] =0
AAAi K
0 + O
+0
+
A (c} (6}+
(9)
K
where the expectation is over the algorithm's 's randomness.
We instantiate Theorem using a specific choice of x = O (6). Corollary shows that BR-FedBiM achieves the optimal Byzantine resilience under heterogeneity.
Corollary Suppose AGG(-) satisfies the (6, robuustesss criterion with K = O (6). Then, BR-FedBiM is (6, c)) with: e = == (V (2 + ( 2) BR-FedBiM
achieves optimal Byzantine resilience, as the upper bound of the asymptotic enror matches the lower bound in Corollary 1.
Eliminating variance-related error. there exists no Byzantine attackers, i.e. 8 = O, the conver- gence rate in Corollary 3 matches that of conventional FBO (Yang et al., 2024). However, if à > 0, the dominating term of convergence rate, O (V ( ())) is affected by Byzantine attackers. While BR-FedBiM cannot achieve linear speedup as BR-FedBi the presence of Byzantine attackers, it eliminates the variance-related error tenm O (nO²). Consequently, it is able to achieve optimal Byzantine resilience. Moreover, in the homogeneous setting, the BR-FedBiM algorithm is able to converge to stationary point at a rate of (1/1// K), even with a 8-proportion of Byzantine attackers.
3)).
FEDERATED PROBABILISTIC BILEVEL ALGORITHM
In this section, we propose BR-FedBiP, a Byzantine-resilien and variance-reduced algorithm for federated bilevel optimization. In particular, we make Probabilistic Gradient Estimator (PAGE) (Li et al., 2021b), which is a variance-reduced method, applicable to the context of Byzantine-resilient bilevel federated learning to reduce the variance among honest workers. This enhancement allows BR- BR-FedBiP to achieve optimal sample complexity, aligning with the results established in prior works (Chu et al., 2024).
7

---

Published as a conference paper at ICLR 2026
6.1 PROBABILISTIC GRADIENT ESTIMATOR
The full procedure of BR- BR-FedBiP is summarized in Algorithm 1 in Appendix C. At each iteration k E [K] the server samples Cj Be(p) from the Berouuli distribution with probability p and sends it to the clients. Then, each honest client E H employs the probabilistic gradient estimator to reduce the gradient variance:
x,1 T V22 Giz; up! (.)) + Th (xxxViii of o. 6
(10a)
yi (V Gi spt (.))
(10b)
2., TV Giz; sp: (p TT Py ,
(10c)
where u² (x y 2²). We define the operation Te as:
(b Tx = T + (u (u if Cj = O,
c/ =
(11)
where vp represents one of the following quantities: {Vx VyFi VyGi, V Gzz V Gz). which is selected based on the specific context within πh
In each iteration k; the gradient computation follows two cases: (i) if ca = 1, PAGE uses vanilla mini-batch SGD with larger batch size of b', with of' Dy; and uo DD 9: and (ii) if cg = 0. it reuses previous global updates with a small adjustment based on a smaller batch size 6, with of ~ Dy, and o Dg,- After collecting gradients from all clients, the server applies robust aggregation method and updates the global parameters.
6.2 CONVERGENCE ANALYSIS
In this subsection, we establish a convergence guarantee for BR-FedBiP and show that BR-FedBiP achieves the optimal sample complexity. To establish this, we assume that the stochastic gradients satisfy the mean-squared smoothness property, as commonly assumed in existing works (Yang et al., 2021; Chu et al., 2024). All proofs are provided in Appendix I.
Assumption 7 (Mean- sqquae- smoothness). For any honest client i E H. the stochastic gradients and Hessians (x y: Φ.), VX, y: pi), V Gxx. sp.) and V (x, 4P:) are L Lg. L and Lg Lipschitz continuous, respectively.
Theorem 4. Let 8 < 1/2. Suppose Assumptions 1-4 and hold, and the robust aggregation rule A-G(.) satisfies the (ő, robbussssss criterion. Choose mini-batch size < VB and the probability
p E (0, 1). Set the learning rates as follows: 1x S min On1
1+ Bl = cyJb:: Ta = C2ulx
where a1, C, Cy, Cu are some positive constants independent of K. Then, the algorithm BR-FedBiP (1) converges as:
(
[1 K
E [[Ive(<3)]] -O
+0 +0
02
K (
(
where the expectation over the algorithm's randomness.
Remark 3. To achieve (6, c)-Bynantine resilience, take B' = min f M where N and M represent the numbers data points for the upper-level and lower-level objectives held by each client, respectively. If + M is sufficiently large, we have = (c-l). Assuming < v and choosing p- 8 the sample complexity of BR-FedBiP reduces to the optimal sample complexity in the general expectation setting (Li et al., 2021b).
à
which matches
7 EXPERIMENTS
In this section, evaluate the performance of the proposed algorithms on hyper-representttion tasks. We compare these algorithms with BILANTINE (Abbas et al., 2024), a sub-loop Byzantine-resilien bilevel optimization algorithm under four different Byzantine attacks on MNIST (LeCun, 1998) and CIFAR-10 (Krizhevsky et al., 2009) datasets. Please refer to Appendix D for details of the implementation and experiment results.
8

---

Published as a conference paper at ICLR 2026
Table 1: Hyper- reperrrepresentation on MNIST with heterogeneous data. "Worst" shows the worst test
accuracy among all attacks.
AGG
Algorithm
ALIE
BF
IPM
RN
Worst
AGG
Algorithm
ALIE
BF
IPM
RN
Worst
BILANTINE
73.74
46.02
49.85
63.12
46.02
BILANTINE
66.96
32.02
19.96
67,68
19.96
Median
BR-FedBi
83.11
82.00
81.28
82.65
81.28
RFA
BR-FedBi
70.83
79.41
80,70
82.49
70.83
BR-FedBiP
83.24
82.24
81.36
82.73
81.36
BR-FedBiP
70.80
79.26
80.69
82.62
70.80
BR-FodBiM
79.53
82.51
82.60
82.59
79.53
BR-FedBIM
72.76
81.95
81.87
82, 60
72.76
BILANTINE
41.84
46.05
64.19
41.84
BILANTINE
56.88
51.02
58.4
63.32
51.02
TM
BR-FedBi
83:27
82.61
82.54
82.66
82.54
CWMed
BR-FedBi
58.25
79:70
81.51
82.76
58.25
BR-FedBiP
83.29
82.58
82.58
82.61
82.58
BR-FedBiP
58.25
79.70
81.62
82.76
58.25
BR- BR-FeeBIM
82.44
82.69
82.61
82.44
82.44
BR-FedBIM
69.37
82.23
82.30
82, 66
69.37
Table 2: Hyper- eyper-representttion on CIFAR-10 with homogeneous data. "Worst" shows the worst test
accuracy among all attacks.
AGG
Algorithm
ALIE
BF
IPM
RN
Worst
||
AGG
Algorithm
ALIE
BF
IPM
RN
Worst
BR-FedBi
60.61
59.36
63.22
43.70
43.70
BR-FedBi
51.91
57.52
63.13
43.02
43.02
Median
BR-FedBiP
63.39
62.04
59.36
62.86
59.36
RFA
BR-FedBiP
49.36
52.67
51.52
62.91
49,36
BR-FedBiM
63.12
62.68
63.40
62.67
62.67
BR-FedBiM
54,83
62,83
62.47
63.09
$4.83
BR-FedBi
62.92
42.45
BR-FedRi
54.83
63.14
42.01
TM
BR-FedBiP
63.22
62.09
62,92
63.22
62.09
CWTM
BR-FedBiP
37,70
48.84
54.83
61.40
37.70
RR-FodBiM
63.64
63.34
63.18
63.74
63.18
BR-FodBiM
51.92
62.21
60.37
62.92
51,92
BR-FedBi
63.49
63.16
63.06
43.60
43.60
BR-FedBi
54.45
$7.38
63.70
43.31
43.31
Krum
BR. BR-TedI
63,72
63.49
63.16
63.17
63.16
CWMed
BR-TediiP
47.26
54.45
57.38
63.51
47.26
BR-FedBiM
63.19
62.80
63.09
63.21
62,80
BR BRRFFeBBM
47.90
$2.70
58.77
63.08
47.90
Distributed system. We consider distributed system with = 25 workers, among which f f= 7 are Byzantine attackers. In the experiment, we test four representative attacks, which are A Little is Enough (ALIE) (Baruch et al., 2019), Inner Product Manipulation (IPM) (Xie et al., 2020), Bit Flipping (BF) (Allen-Zhu et al., 2020) and Random Noise (RN). To preserve Byzantine resilience, we implement six widely used robust aggregators, which are Krum (Blanchard et al., 2017), Median, Trimmed Mean, Coordinate- Wise Median (CWMed) (Yin et al., 2018), Coordinate- Wise Trimmed Mean (CWTM) (Yin et al., 2018), and RFA (Pillutla et al., 2022).
Empirical results on MNIST. Table compares the performance of BR-FedBi, BR-FedBiM, and BR- RR-FedBiP against BILANTINE on the heterogeneous MNIST dataset under four different Byzantine attacks. For each block (i.c. cach robust aggregator), we highlight in bold the algorithm with the highest accuracy under each attack. It is observed that BR-FedBiP and BR-FedBiM achieve better performance on worst-case accuracy, and all the proposed single-loop bilevel algorithms significantly outperform the baseline BILANTINE. Additional experiments under homogeneous settings on MNIST dataset are presented in Appendix D.3.2.
Empirical results on CIFAR-10. Table 2 compares the performance of BR-FedBi, BR-FedBiM, and BR-FedBiP on CIFAR- 10 dataset. The results for BILANTINE on CIFAR- 10 dataset are not presented, as our extensive hyperparameter search revealed that BILANTINE failed to converge on CIFAR-10 10 dataset. The experimental results show that BR-FedBiM achieves better performance on CIFAR-10 dataset and attains higher worst-case accuracy when combined with multiple robust aggregation methods.
Experiments on different numbers of attackers. We further evaluate the efficacy of the proposed methods under different numbers of attackers / {3, 5, 7, 10) with = 25 (see Appendix D.3.2 for details) on MNIST dataset. The results demonstrate that the proposed methods achieve better performance than the baseline BILANTINE algorithm with different numbers of attackers.
8 CONCLUSION
This work bridges the gap between federated bilevel optimization and Byzantine-resilient federated learning. We proposed BR FedBi and its variants, which are family of single-loop Byzantine- resilient bilevel algorithms that ensure both efficiency and robustness. We provided the first tight analysis of asymptotic error under Byzantine attacks in bilevel optimization. Experimental results demonstrate that the proposed methods significantly outperform existing approaches under various Byzantine attack scenarios. However, the convergence analysis relies on the (-dissimilarity hetero- geneity assumption (Assumption 4). Whether similar theoretical guarantees can be established under the milder (ç, B) -iisiiiilaryy assumption (Assumption 8) remains an open question. We aim to address these limitations in future work.

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported in part by a grant from the NSFC/RGC Joint Research Scheme sponsored by the Research Grants Council of the Hong Kong Special Administrative Region, China and National Natural Science Foundation of China (Project No. N N_HKUST656/22),
REFERENCES
Momin Abbas, Yi Zhou, Nathalie Baracaldo, Horst Samulowitz, Parikshit Ram, and Theodoros Salonidis. Byzantine-resilent bilevel federated learning. In 2024 IEEE 13rd Sensor Array and Multichannee Signal Processing Workshop (SAM), pp. 1-5, IEEE, 2024.
Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topeu. Robust training high dimensions via block coordinate geometric median descent. In International Conference on Artificial Intelligence and Statistics, pp. 11145-11166 PMLR, 2022.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2623-26222222 2019.
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex stochastic gradient descent. arXiv preprint arXiv:2012. 143368 2020.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 1232-1300, PMLR, 2023.
Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and Geovani Rizk. Robust distributed learning: tight error bounds and breakdown point under data heterogeneity. Advances in Neural Information Processing Systems, 36, 2024.
Joe Armstrong. Making reliable distributed systems in the presence of software errors. PhD thesis, 2003.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. little enough: Cireumventing defenses for distributed learning, 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. Advances in neural information processing systems, 30, 2017.
Xuanyu Cao, Tamer Başar, Suhas Diggavi, Yonina C Eldar, Khaled B Letaief. H Vincent Poor, and Junshan Zhang. Communication-efficin efficient distributed learning: An overview. IEEE journal on selected areas in communications, 41 41(4):851-77, 2023.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294-25307, 2021.
Xuxing Chen, Minhui Huang, Shiqian Ma, and Krishna Balasubramanian. Decentralized stochastic bilevel optimization with improved per-iteration complexity. In International Conference on Machine Learning, pp. 4641 16711. PMLR, 2023.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 15(15 2024.
Xuxing Chen, Minhui Huang, and Shiqian Ma. Decentralized bilevel optimization: X. chen et al. Optimization Letters, 19(7):1249-133 2025.
Ziqin Chen and Yongqiang Wang. Locally differentially private decentralized stochastic bilevel optimization with guaranteed convergence accuracy. In Forty-frrst International Conference on Machine Learning, 2024.
10

---

Published as a conference paper at ICLR 2026
Tianshu Chu, Dachuan Xu, Wei Yao, and Jin Zhang. Spaba: A single-loop and probabilistii stochastic bilevel algorithm achieving optimal sample complexity. arXiv preprint arXin:2405.18777, 2024.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances Neural Information Processing Systems, 35:26698-266 -070998--61,,,, 2022.
Justin Domke. Generic methods for optimization-basee modeling. In Artificial Intelligence and Statistics, pp. 318-326. PMLR, 2012.
Youran Dong, Shiqian Ma, Junfeng Yang, and Chao Yin. A single-loop algorithm for decentralized bilevel optimization. Mathematics of Operations Research, 2025.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Lê-Nguyên Hoang, Rafael Pinot, and John Stephan. Robust collaborative learning with linear gradient overhead. In International Conference on Machine Learning, pp. 9761-9813 13. PMLR, 2023.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learming. pp. 1126-1135 PMLR, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pp. 1568-1577. PMLR, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246, 2018.
Eduard Gorbunov, Samuel Horváth, Peter Richtárik, and Gauthier Gidel. Variance reduction is an antidote to byzantines: Better rates, weaker assumptions and communication compression cherry on the top. arXiv preprint arXiv:2206.00529, 2022.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application bi-level optimization. arXiv preprint
05447, 2016.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp- 3748 3758. PMLR, 2020.
Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding distributed sgd for non-convex optimization. In International Conference on Machine Learning, pp. 1344-2555 PMLR, 2019.
Yutong He, Jie Hu, Xinmeng Huang, Songtao Lu, Bin Wang, and Kun Yuan. Distributed bilevel optimization with communication compression. arXiv preprint arXiv:2405. 18858, 2024.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05170. 2020.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1): 2023.
Ye Hu, Mingzhe Chen, Walid Saad, H Vincent Poor, and Shuguang Cui. Distributed multi-agent meta learning for trajectory design in wireless drone networks. IEEE Journal on Selected Areas in Communications, 39(10):11773112. 2021.
Ahmed Hussein, Mohamed Medhat Gaber, Eyad Elyan, and Chrisina Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR), 1-3 2017.
11

---

Published as a conference paper at ICLR 2026
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pp. 4882 4892. PMLR, 2021.
Sai Pranceth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogencous datasets via bucketing. arXiv preprint arXiv:2006.00 09366,09965.. 2020a.
Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference machine learning, pp- 1132-5143, PMLR, 2020b.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. 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. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems, 34:30271-30283, 2021.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameterization. Advances in Neural Information Processing Systems, 144118990-1999 2021.
Boao Kong, Shuchen Zhu, Songtao Lu, Xinmeng Huang, and Kun Yuan. Decentralized bilevel optimization over graphs: Loopless algorithmic update and transient iteration complexity. arXiv e-prints, pp. arXiv-2402, 2024.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Li Li, Yuxi Fan, Mike Tse, and Kuo-Y Lin. A review of applications in federated learning. Computers & Industrial Engineering, 149:106854, 2020.
Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, and Samet Oymak. Autobalance: Optimized loss functions for imbalanced data. Advances in Neural Information Processing Systems, 34:3163-3177 2021a.
Yuxi Li. Deep reinforcement learning: An overview. arXiv preprint
2017.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. International conference on machine learning, pp. 6286-6295, PMLR, 2021b.
Yuchen Liu, Chen Chen, Lingjuan Lyu, Fangzhao Wu, Sai Wu, and Gang Chen. Byzantine-robust learning on heterogeneous data via gradient splitting. International Conference on Machine Learning, pp. 1444004-422555 PMLR, 2023.
Songtao Lu, Siliang Zeng, Xiaodong Cui, Mark Squillante, Lior Horesh, Brian Kingsbury, Jia Liu, and Mingyi Hong. stochastic linearized augmented lagrangian method for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 35:30638-30663 2022.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-bard -baeed hyperparameter optimization through reversible learning. In International conference on machine learning, pp. 2112-2122 PMLR, 2015.
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Aguera Arcas. Communication--fficieen learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273 1273-1282. PMLR, 2017.
Tomoya Murata, Kenta Niwa, Takumi Fukami, and Lifan Tyou. Simple minimax optimal byzantine robust algorithm for nonconvex objectives with uniform gradient heterogeneity. In The Twelfth International Conference Learning Representations, 2024.
Youcheng Niu, Jinming Xu, Ying Sun, Yan Huang, and Li Chai. Distributed stochastic bilevel optimization: Improved complexity and heterogeneity analysis. Journal of Machine Learning Research, 26(76)11-58, 2025.
12

---

Published as a conference paper at ICLR 2026
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. In International conference on machine learning. pp. 737-746. PMLR, 2016.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions Signal Processing, 70:1 70:1142-1154, 2022.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Virat Shejwalkar and Amir Houmansadr. Manipulating the byzantine: Optimizing model poisoning attacks and defenses for federated learning. In NDSS, 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. 21 2144-1216 179. PMLR, 2022.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE transactions on infor information forensics and security, 15:3454-3469, 2020.
Peiyao Xiao and Kaiyi Ji. Communication-fffiieee federated hypergradient computation via aggre- gated iterative differentiation. In International Conference on Machine Learning, pp. PMLR, 2023.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty Artificial Intelligence, pp. 261-270. PMLR, 2020.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34: 34:13670-13682, 2021.
Yifan Yang, Peiyao Xiao, and Kaiyi Ji. Simfbo: Towards simple, flexible and communication--eficcnn federated bilevel learning. Advances in Neural Information Processing Systems, 36, 2024.
Fahri And Yerlikaya and Şerif Bahtiyar. Data poisoning attacks against machine learning algorithms. Expert Systems with Applications, 208: 118101, 2022.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robus distributed learning: Towards optimal statistical rates. In International conference on machine learning, pp. 5650-5659. Pmlr, 2018.
Xuezhou Zhang, Xiaojin Zhu, and Laurent Lessard. Online data poisoning attacks. In Learning for Dynamics and Control, pp. 201-210. PMLR, 2020.
Shuchen Zhu, Boao Kong, Songtao Lu, Xinmeng Huang, and Kun Yuan. Sparkle: unified single- loop primal-dual framework for decentralized bilevel optimization. Advances in Neural Information Processing Systems, 37:62912-629887, 2024.
13

---

Published as a conference paper at ICLR 2026
ORGANIZATION
Appendix A contains LLM usage statement.
Appendix B presents the additional related works.
Appendix C presents the full version of the algorithms.
Appendix D contains additional experimental results.
Appendix E provides the proof of the lower bound stated in Theorem 1.
Appendix provides general lemmas used for the convergence analysis.
Appendix G provides the proof of convergence analysis for BR-FedBi as stated in Theorem 2. Appendix H provides the proof of convergence analysis for BR-FedBiM stated in Theorem 3.
Appendix provides the proof of convergence analysis for BR-FedBiP as stated in Theorem
Appendix provides the proofs of supporting lemmas used in the convergence analysis.
A LLM USAGE STATEMENT
In this work, used large language model (LLM) solely for writing assistance (e.g. proofreading. rephrasing, stylistic polishing). We did not rely on for scientific content generation, experiment design, idea generation, or analysis. All core research components- cumponenss-cooccppuuaiiiii conceptualization, modeling. experiments, theoretical derivations, and interpretation- were weee performed by the authors. We take full responsibility for all content in the manuscript, including any modifications influenced by the LLM.
B MORE RELATED WORKS
Distributed bilevel optimization. Distributed optimization has emerged key paradigm for solving large-scale learning problems in which data are distributed across multiple agents. A major milestone in bilevel optimization non-asymptotic analysis of bilevel stochastic approximation methods, thereby motivating extensive research on more efficient bilevel optimization algorithms. This growing line of work includes AlD-based methods (Domke, 2012; Pedregosa, 2016; Gould et al., 2016; Ghadimi & Wang, 2018; Grazzi et al., 2020; Ji et al., 2021), ITD-based approaches (Domke, 2012: Maclaurin et al., 2015; Franceschi et al., 2018 8; Grazzi et al., 2020; Ji et al., 2021), and Seummnn--eeree-baaseee (Chen et al., 2021; Hong et al., 2020; et al., 2021). Building on these foundations, Tarzanagh et al. (2022) proposed FedNest, a federated bilevel optimization algorithm based approximate implicit differentiation, while Xiao & Ji (2023) introduced an iterative differentiation (bsD) method designed to reduce communication overhead in federated settings. More recently, Dagréou et al. (2022) developed SOBA, a single-loop framework for bilevel optimization, and Yang et al. (2024) extended this framework to the federated learning setting. Despite these advances, research Byzantine-robust distributed bilevel learning remains limited.
achieved by Ghadimi & Wang (2018), who provided the first
techniques
Decentralized bilevel optimization. In contrast distributed algorithms, decentralized approaches operate without a central server, offering increased robustness to communication network contin- gencies. However, the lack of a central coordinator necessitates peer-to-peer communication, which introduces additional challenges for seavergenceeespcciallle in the presence of significant data heterogeneity. Kong et al. (2024) proposed single-loop algorithm based on decentralized SOBA. To improve robustness against data heterogeneity, recent works have incorporated Gradient Tracking (GT) into both lower- and leper-level optimization procedures. While existing results such as (Dong et al., 2025; Chen et al., 2025) have primarily focused on deterministic settings, Niu et al. (2025) investigated personalized lower-level problems that relax the requirement for global consensus. No- tably, approaches such as Chen et al. (2025; 2023) have relied on computationally intensive inner-loop GT updates. Furthermore, Zhu et al. (2024) presented a unified convergence analysis for GT-based methods and demonstrated that integrating GT achieves smaller transient iteration complexity compared to D-SOBA for decentralized stochastic bilevel optimization. Despite these advances, research Byzantine-robus decentralized bilevel learning remains limited.
Byzantine- distributed learning. The goal of Byzantine Byziitine-resilient learning is to protect the learning process from malicious attackers (Blanchard et al., 2017; Yin al., 2018; Pillutla et al.,
14

---

Published as a conference paper at ICLR 2026
2022). Most existing defenses replace the simple averaging step used in conventional FL frameworks (McMahan et al., 2017) with robust aggregation rules designed to compute a global update that is resistant adversarial manipulation. Some robust aggregation rules aim to incorporate all honest gradients into the aggregation (Blanchard et al., 2017; Shejwalkar & Houmansadr, 2021), whereas others (Yin al., 2018; Blanchard al., 2017) purposely aggregate only subset of gradients to ensure that adversarial updates are excluded. However, data heterogeneity makes Byzantine robustness substantially more challenging (Karimireddy al., 2020a; Allouah al., 2023). To mitigate this issue, Karimireddy et al. (2020a) proposed a pre-aggregation method, bucketing, which adapts existing robust aggregation rules to heterogeneous data distributions. Building on this direction, Allouah et al. (2023) developed the Nearest-Neighbor Mixing (NNM) algorithm, which strengthens standard robust distributed gradient descent methods and achieves optimal Byzantine resilience under heterogeneous settings. Despite these advancements, research on bilevel optimization remains limited.
C FULL ALGORITHM DESCRIPTION
In this section, we provide the full version of the proposed algorithm, which complements the abbreviated description given in the main paper.
commonly employed strategy for bilevel optimization problems makes use of implicit differentiation (Griewank & Walther, 2008). In centralized bilevel optimization, under appropriate hypotheses, the function & is differentiable, and the chain rule and implicit function theorem give for any
( Vx yx, 9xx, y" (x)) [Vyyo(x,
yxx(xx,""x)),,
By leveraging the results for centralized stochastic bilevel optimization, in Byzantine-resilien federated bilevel optimization (BR-FBO), the expression of the hypergradient V y (x)) can be written as:
1 (x,, [H
Vxli (x,, V2y (x,y"(x))
( (x,
H
iEW
EE
where the global Hessian matrices can be written as:
Vey (x,y' y" (x))
Σ
V2 ( y (x)), V2 Vyy SH (x,y'x)))
Σ iEH
v2 (x,
[70
[7
iEH
We extend the SOBA framework (Dagréou et al., 2022) to develop a single-loop solution for BR-FBO, which introduces an auxiliary variable 2" (x) to approximate the Hessian-inverse-vector product:
z" (x) == - (x,
Vy (x,
(12)
H
iCH
Thus, the hypergradient (x) can be written
(x)
Σ
Vxfi + v2 9y (x,y*(x)) .z =x))..
(13)
H.
iE
Approximating x" (x) in (12) amounts to letting each agent solve for the following equation:
2' =
Σ H
b;
or
Σ H
x
Σ ba
(14)
IEH
IEH
IEH
NE
where H, 2 y
and b, V, f y" (x)). Equality (14) is essentially the optimality condition of the following optimization problem:
(x)) yx,
1 V.= = -T
min
V.
11, + b,.z. 2
(15)
H
In the light of (12), (13) and (15), it turns out that the derivation of the gradient of 4x each iteration cumbersome because it involves two subproblems: the resolution of the inner problem to find an approximation of y (x) and the resolution of linear system to find approximation of 2(x).
15

---

Published as a conference paper at ICLR 2026
The auxiliary variable enables the estimation of the global hypergradient using the expression: 1 ZieH (xfi(x,,' y) + (x y)z, where y represents the approximate solution to the lower- [H]
level problem. Thus, the solution of the inner problem, the solution of the linear system (15), and the outer variable all evolve at the same time. Algorithm outlines the unified framework for the proposed BR-FedBi, BR-Fen BR-FedBiM,, and BR-FedBil algorithms. For clarity, gradient computation and aggregation steps are marked with different colors corresponding to the respective variants.
Algorithm 1 BR-FedBi, BR-FedBiM and BR-FedBiP
Initialization: each honest worker E H initializes x², y² (122) S p) R learning rates 72 Ty 122 IR+ and robust aggregation method A Raxd Rd. for 0, ....
do Server: Broadcast x² .y z² to all workers;
Get probability indicator: C₁ Be(p):
for Each honest worker E H, in parallel: do
Locally compute gradients D Db: y D defined in eq-(5);
Locally compute gradients m m is m defined in eq.(8);
Locally compute gradients " y, n, defined in eq.(10);
end for
Server: Received the gradients from all clients; for E yx 2 do
Server aggregates local estimators:
D = AGG (D Do
// Similar statergy for the m and t
Server update global parameter:
ok+1 = ot DoD
end for Clip the norm of z k+1; ++1 min http/l/++11// 112] kt,
end for
return Sample x uniformly at random from {x" ,.., x
x -1-
D EXPERIMENTS
In this section, we evaluate the performance of the proposed methods on hyper-representation task. Specifically, we compare the proposed Byzantine-resilien single-loop bilevel optimization algorithms with BILANTINE (Abbas et al., 2024), a sub-loop- based Byzantine-resilicn bilevel optimization algorithm.
D.1 ATTACKS AND ROBUST AGGREGATORS.
D.1.1 ENVIRONMENTS
All methods were implemented using the PyTorch framework (Paszke al., 2019) and executed on NVIDIA A100 GPUs with 40GB of memory. Notably, all experiments can be conducted with as little as 2GB of memory.
D.1.2 ATTACKS.
In experiments, the Byzantine workers execute four state-of-the-att gradient attacks, namely A Little Enough (ALIE) (Baruch et al., 2019), Fall of Empires (Xie et al., 2020), Bit-flipping (BF) (Allen-Zhu al., 2020), and Random noise. Let a denote the attack direction at iteration k and let
16

---

Published as a conference paper at ICLR 2026
7 0 be fixed scalar. At each step k, every Byzantine worker sends to the server manipulated vector B zh + naa where s is an estimate the true gradient (or momentum). In our gradient descent (GD) experiments, compute this estimate z* म Eien o where of is the gradient computed by honest worker w; iteration k.
ALIE: The adversarial direction is chosen as a* o² where o² is the coordinate- wise standard deviation of s*
1PM: The adversary sets a* = - In this case, each Byzantine worker sends (1 17)8* to the server.
BF; This attack also uses a = - but fixes 17 = 2. Thus, Byzantine workers send B = a
-gh at every step.
RN: In this attack, the adversarial direction a² is sampled from random Gaussian distribution. Formally, a (u, o²), , so each Byzantine worker injects random Gaussian noise into its reported vector.
D.1.3 ROBUST AGGREGATOR.
In our experiment, we use six widely adopted robust aggregators: Krum (Blanchard et al., 2017), Median (Acharya al., 2022), Trimmed Mean, Coordinate- -ise Median (CWMed)), Coordinate- Wise Trimmed Mean (CWTM) (Yin et al., 2018), and RFA (Pillutla et al., 2022). The following outlines how each method operates:
Given input vectors Ti...... Tn. Krum selects one of them based on its proximity to its closest neighbors while ignoring the farthest vectors. For each i [n]] let 81..... fn be the indices of the other vectors sorted by distance from IG, and define the set of its n - f
Krum.
nearest neighbors C. {úr, ; fn-f-1. Krum then chooses the vector whose neighbors
are collectively the closest:
Krum(
Fi, E arg min iE(n]
Σ |1: 1.
JEC.
Median. Given vectors 21....; En E Rd the multivariate median is defined as the point Med(#)..... xx) == arg mingged Σx | - x://2. This estimator minimizes the sum of Eu-
clidean distances to all input vectors. Although robust, it is computationally expensive in
high-dimensional settings.
Trimmed Mean. Given 21,..., Rd and trimming parameter f. let 2(1)...... ... (n)
denote the vectors sorted by their distance the mean, = - Te [|= - 5 f|2 S S ||=())) 2||2. The trimmed mean removes the f farthest and closest vectors and averages the remaining:
TM Fn) = n 2f
TG) j=
CWTM. Given vectors Ti, 2n Rdd let Tue be the permutation that sorts their k-th coor- dinates in non-dccreasing order: [Tr,(1)le S ... < [m)kk For trimming parameter f. the CwTM is defined coordinate-wise removing the largest and smallest f values and averaging the rest:
CWTM(EL.......)
Σ (Tr,))k j=f+1
k E [d].
2f
CWMed: For vector E Rdd let [τ]] denote its k-th coordinate. Instead of computing the full multivariate median, which is difficult in high dimensions we take the median in- dependently on each coordinate. Given input vectors .I....,77 Zno the coordinate-v CwMed((r),.... ) is the vector whose k-th coordinate is
median
Cw A.)a k = Median ([æıkk,... [xx,k))
k E [d].
RFA: Given vectors 3T, . Zm I and weights a; 0, RFA computes a robust center via iterative smoothed Weiszfeld update. Starting from (0() for 0,...,
.,. R 1 sets
0i and 2 (r+1) Σm 3(0) Tj
B
VV (2() -
xz|l
m 3(r))
17

---

Published as a conference paper at ICLR 2026
D.2 LOSs FUNCTION TUNING ON IMBALANCED DATASET
Loss Function Tuning on Imbalanced Datasets. We use bilevel optimization to tune loss function for learning on an imbalanced MNIST dataset, aiming to maximize the bass-bbllanced validation accuracy to better serve minority (tail) classes. Following the formulation in (Li et al., 2021a), we tune the VS-loss (Kini et al., 2021) in federated setting, where each client has a local training set Di and validation set D The bilevel problem is given by
n 12
min (a)
Σ (a.9)ED;
Laa (y, x; f(00 (a)))
s.t. (a(a)= = arg min
1
Σ
Bvs (V,
Dr
(2.0)
where lvs is the parametric VS-loss with hyperparameters (class-dependent weights and logit adjustments), and faal is class-balancee, validation loss. To create long-tailed imbalance, we exponentially decrease the number of MNIST samples per class (Tarzanagh et al., 2022). For example, class O has 6000 samples, class I has 3597 samples, and class 9 has only 60 samples.
D.2.1 IMPLEMENT DETAILS
In our experiments, we use a 2-layer multilayer perceptron (MLP) with 200 hidden units. We the number of communication rounds be 1000 and ensure that all algorithms are run for sufficient number of iterations to reach convergence. The batch size each client is set to b = 64 for all algorithms, and b' 256 for the BR-FedBiP algorithm. The learning rates are chosen as fly: 12, Ba E (0.1, 0.02, 0.01). and the momentum coefficient is set to 3 = 0.8 for all parameters (x, M, 2). The coefficient for BR-FedBiP set to p = 0.2, which matches the theoretical value p 845 Details of the model architectures and implementations are summarized Table
Table 3: Implementation details.
Details
MNIST
Model type
2-layer MLP Input: 784, Hidden; 200, Output: 10
Model architecture
Optimizer
SGD
Learning rate (1))
Eny Ro. n, E 0.01, 0.01)
Batch size (6)
Momentun (9)
8 0.8
Probabilistic coefficient (p)
0,2
Server-side update (iteration)
Number of Byzantine workers
/= 7
Number of honest workers
f = 18
D.2.2 EXPERIMENT RESULTS.
Table 4 reports the test accuracy of BR-FedBi, BR-FedBiM, and BR-FedBiP compared with BILAN- TINE on the heterogeneous MNIST dataset under four types of Byzantine attacks. For each block corresponding a robust aggregator, we mark in bold the method that attains the highest accuracy for given attack. Overall, BR-FedBiP and BR-FedBin consistently yield higher worst-case accuracy, and all three proposed single-loop bilevel methods substantially outperform the baseline BILANTINE.
More results about wall-clock running time. We also report the wall-clock running time of different algorithms for the MNIST datasets for 300 epochs, which shows that the single-loop algorithms less time for training epoch. In terms of communication cost, the sub-loop algorithm requires 8 rounds per epoch, whereas the single-loop algorithm requires only 3 rounds per epoch. To further support the conclusion, we also present the wall-clock running time that different methods require to reach 50%, 60%, 75% and 85% of the top-1 test accuracy in Table 5.
18

---

Published as a conference paper at ICLR 2026
Table 4: Imbalanced- Data Loss Tuning on MNIST with heterogeneous data. "Worst" shows the worst test accuracy among all attacks.
AGG
Algurithm
ALIE
BF
IPM
RN
Wonst
AGG'
Algorithm
ALIB
BF
IPM
RN
Worst
BILANTINE
67.49
61,03
51.9
66.36
51,9
BILANTINE
30.29
30.52
27.46
50.63
27.46
Median
BR-FedBi
75.81
68.38
72.84
75.98
68,38
RFA
BR-FedBi
78.25
68.61
65.7
76.16
65.7
BR-FedBiP
76.02
68.37
73.15
76.18
68.37
BR-FedBiP
78.05
68.88
76.41
68.88
BR-FodBiM
76.27
69.97
71.17
76.03
69.97
BR-FedBIM
78.26
67.35
65.19
76.01
65.19
BILANTINE
57.14
52.78
52.38
62.47
52.38
BILANTINE
69.5
55.29
54,09
62.31
54,09
BR-FedBi
75.86
73.68
74, 79
75.33
73.68
BR-FedBi
78.38
67.12
60.69
75.7
60.69
TM
BR.FedBiP
76.08
73.76
74.97
76.02
73.76
CWMed
BR-FedBiP
78.52
67.38
60.99
75.75
60.99
BR- BR-FedBiM
76.39
71.06
72.48
75.79
71.06
BR-FedBiM
78.35
65,49
61.67
75.1
61.67
BILANTINE
61.35
58.83
61.61
62.92
58.83
BILANTINE
42.39
46.31
40,18
68.8
40.18
Krum
BR Re-deeBBiP
BR-FedRi
76.06
75.88
73.35
72.91
74.08
73.96
75.96
76.21
73.35
72.91
CWTM
BR TedBiP
BR-FedBi
78.51
78.23
67.04
60.58
60.52
76.03
75.86
60.58
60,52
BR-FedBIM
72.01
72.71
72.01
BR-FedBIM
78.17
61.07
Table 5: Wall-clock running time (s) for different methods over 300 epochs. "X% of top-1 test acc." denotes the time required to reach X% of the final top-1 test accuracy.
Clock-time
Algorithm
Krum
TM
Median
RFA
CWTM
CWMed
BR FedBi
5951.92
5890.92
5897.21
5929.72
5860.15
5837.08
Total time
BILANTINE
7041.4429
6459.92
6516.94
7116.44
6523.39
6589.95
BR FR-FedHi
123.49
70,60
68.39
96.38
106.78
75.80
50% of top-1 acc
BILANTINE
166.60
371.64
199.62
259.10
13.28
326.59
60% of lop-1 test ace
BR-FedBi
310.76
146.78
132.27
142.50
146.23
BILANTINE
286.25
566.82
281,24
674.35
189.49
404.07
BR-FedBi
457.30
557.70
325.63
544.96
550.09
552.83
75% of top-1
BILANTINE
731.12
1301.09
359.70
1566.27
557.48
660.45
BR-FedBi
566.09
1825.56
584.79
1724.10
1591.81
1602.61
85% of top-1 test acc
BILANTINE
1315.46
1650.53
448.32
1856.44
766.82
876.82
D.3 HYPER-REPRESEENTTTIN
Reppeseeprrsnntiionnn Following the formulation presented in (Franceschi et al., 2018), the hyper- representation problem can be described as:
min L(A)
1
Σ
((0
n1
D
ØED:
s.t. (*( arg min
Σ ((0,);))
D
PED:
where DÍ and D are training and validation datasets of each client respectively. The last fully connected layer serves as the lower-level objective, and the remaining parameters serve as the upper- level objective. We conduct experiments on MNIST using a 2-layer multilayer perceptron and on CIFAR- 10 using CNN, where the last fully connected layer serves the lower-level objective and the remaining parameters as the upper-level objective.
D.3.1 IMPLEMENT DETAILS
In our experiments, we test two datasets: MNIST (LeCun, 1998) and CIFAR-10 (Krizhevsky et al., 2009). For MNIST, we use a 2-layer multilayer perceptron (MLP) with 200 hidden units. For CIFAR- 10, we employ a convolutional neural network (CNN) with two convolutional layers, followed by two fully connected layers. In both models, we designate the fully connected layer as the lover- objective, while the remaining parameters are treated as the upper-level objective. Details of the model architectures and datasets are summarized in Table 6.
Wall-Clock Running Time Results. We also present the wall-clock running time of the evaluated algorithms on the MNIST dataset over 200 training epochs. The results demonstrate that the single- loop algorithms have lower per-epoch training time. Regarding the communication workload. the sub-loop algorithm requires communication operations per epoch, whereas the single-loop algorithm requires only 3, corresponding to its three variable updates. To further substantiate these observations,
19

---

Published as a conference paper at ICLR 2026
Table 6: Implement details.
Details
MNIST
CIFAR-10
Model type
2-layer MLP Input: 784, Hidken: 200, Output:
CNN
Model architecture
ConvI:
Conv2: 6 16 P. 84
Optimizer
SGD
SGD
Learning rate (1)
Edy Tee No (0.1, 0.02, 0.01)
(lly flo #x ) (0.1,0.05, 0.03)
Batch size
6 61
b
Momentum (99
(0.5, U.S, 0.5)
8 E (0.5,0.3 0.5.0.3)
Probabilistic coefficient (p)
p = 0.5
p
Server-side update (iteration)
200
1000
Number of Byzantine workers
f f = 18
Number of honest workers
n 18
we report the wall-clock time required for each method to reach 50%, 60%, 75%, and 85% of the top-1 test accuracy in Table 7, Table 8, Table 9, and Table 10, respectively. As evidenced by the results, BR-FEDBI generally reaches the target accuracy in less time than BILANTINE.
Table 7: The wall clock running time (s) for differrnnt methods with 200 epochs MNIST dataset.
Algorithm
Krum
TM
Median
RFA
CWMed
CWTM
BILANTINE
7701.42
7202.51
7229.27
7458.81
6590.10
6523.29
BR-FedBi
3138.29
3139.92
3102.36
3132.67
3138.48
3126.39
BR FedBiM
3200.38
3148.26
3136.17
3173.29
3169.27
3153.02
BR RR-FedBiP
3158.74
3166.83
3165.91
3207.01
3238.28
3203.91
Table The wall clock running time (s) for different methods to reach 50% top-1 test accuracy on MNIST dataset under ALIE attack on MNIST dataset.
Algorithm
Krum
TM
Median
RFA
CWMed
CWTM
BILANTINE
871.26
1073.19
888.60
472.37
326.59
189.20
BR-FedBi
78.29
78.26
77.48
78.94
119.39
116.83
BR-FedBiM
129.36
126.37
126.22
140.37
140.38
BR- Re-BRdBiPP
46.94
109.28
109.29
110.20
115.37
115.20
Table The wall clock running time (s) for different methods to reach 60% top-1 I test accuracy on MNIST dataset under ALIE attack on MNIST dataset.
Algorithm
Krum
TM
Median
RFA
CWMed
CWTT
BII BNITANN
1176.96
1215.51
1104.37
545.89
404.07
$57.89
BR-FedBi
110.28
109.93
108.73
109.93
146.93
112.39
BR-FedBiM
128.38
129.36
126.37
126.22
140.37
148.30
BR-FedBBP
109.92
109.28
139.95
110.20
147.48
115.20
Table 10: The wall clock rumning time (s) for different methods to reach 75% top-1 test accuracy on MNIST dataset under ALIE attack MNIST dataset.
Algorithm
Krum
TM
Median
RFA
CWMed
CWTM
BILANTINE
1407.85
1466.47
1392.71
728.29
660.92
557.63
FedBi
187.56
186.82
187.29
BR-FedBiM
255.37
254.17
254.73
253.22
276.39
279.40
BR-FedBiP
155.91
170.92
170.02
173.84
179.62
179.20
Table 11: The wall clock running time (s) for different methods to reach 85% top-1 test accuracy on MNIST dataset under ALIE attack MNIST dataset.
Algorithm
Krum
TM
Median
RFA
CWMed
CWTM
BILANTINE
1791.57
1574.27
1500.40
838.84
726.38
641.68
BR-FedBi
234.27
264.73
232.82
264.29
332.27
336.23
BR FedBiM
652.36
379.27
376.39
380.36
360.29
357.29
BR-FodBiP
310.28
309.62
309.29
299.64
322.39
302,29
20

---

Published as a conference paper at ICLR 2026
D.3.2 ADDITIONAL EXPERIMENT RESULTS
In this subsection, empirically compare the performance of the proposed Single-loop Byzantine- resilient Bilevel algorithms with BILANTINE (Abbas et al., 2024) on MNIST dataset. We compare the performance the methods under different fractions of attackers on MNIST dataset. We choose the number of attackers, f = f3, 5, 7, 10), out of 25. Under different numbers of clients, our proposed algorithms achieve better performance than the baseline method, which shows that our methods are more robust to the changing number of attackers.
Table 12: Comparison of top-1 test aceuracy (%) for hyper-representation task MNIST with heterogeneous Data, under BF attack for different numbers of attackers.
Algorithm
RFA
Algorithm
CWMed
BILANTINE
37.84%
35.29%
32.02%
27.86%
BILANTINE
69.20%
53.48%
51.02%%
15.72%
BR-FedB:
82.84%
82.08%
79.41
49.75%
BR-FedBi
82.8%%
82.40%
79.71%
55,23%
BR-FedBIM
82.69%
82.49%
81.96%
78.46%
BR-FedBIM
82.68%
82.50%
82.24%
80.98%
BR-FodBiP
82.83%
82. 10%
79.26%
49.77%
BR-FedBiP
82.84%
82.37%
79.71%
55.31%
Algorithmn
f=3
Median
Algorithm
f=3
Krum
BILANTINE
66.85%
61 82%
46.02%
47.17%
BILANTINE
57.57%
53. 74.%%
52.36%
40.83%
83.02%
BR-FedBIM
82.91%
82 55%
82.51
82.15%
BR-FedBIM BR-FedBiP
82.82%
82.8.3
82.92%
82, 70%
BR-FedBiP
82.86%
82.
82.25%
77.93%
82.90%
82.92%
82.84%
70%
Algorithm
3-3
CWTM
5
f
f - 10
Algorithm
f-3
f 5
f 10
BILANTINE
10.20%
45
10.90%
21.11%
BILANTINE
63.23%
55.43%
11.84%
13.34%
BR-FeddR
82.19%
60.02%
50. 14%
32.33%
BR-FedBi
82.98%
82. 89%
82.61%
82.53%
BR-FodBIM
82.51%
81 65%
78.649
20.69%
BR-FedBIM
82.74%
82.67%
82. 69%
81.46%
BR-FodBiP
82.16%
59.96%
50.95%
34.71%
BR-FedBiP
83.03%
82.87%
Table 13: Comparison of top-1 accuracy (%) for hyper-repressentaion task on MNIST with heterogeneous Data, under IPM attack for different numbers of attackers.
Algorithm
RFA
Algorithm
CWMed
F=3
DILANTINE
23,08%
18.74%
19.9755
17.54%
BILANTINE
67.12%
60.25%
58.15%
48.75%
BR-FedBi
82.78%
82.20%
80. 80.70%
51.68%
BR-FedBi
82.84%
82.28%
81.51%
68.18%
BR- FedBiM
82.65%
82.44%
$1.88%
65.32%
BR Red-eedBiM
8263%
82.52%
82.31%
79.67%
BR RedBeP
82,80%
82.21%
80.699
51.78%
BedFedBiP
8288%
82,29%
81.62%
63.75%
Algorithm
Median
Algorithm
Krum
=
J
J=3
J = 10
BILANTINE
67.33%
55.85%
49.33%
48.64%
BILANTINE
63.3%%
62.05%
61.11%
60.16%
BR-FedRi
RR.FedBi
83.025
82.91%
92.825%
BR FedDiM
82.70%
82.76%
82.609
81.71%
BR FedBiM
82.825
82.83%
82, 32.92%
82.67%
BR-FedBiP
BR-FedBiP
Algurithm
CWTM
Algorithm
7=3
10
T=3
=5
=
36.09%
11.35%
BILANTINE
55.46%
34.68%
BR-FedB:
82.59%
80.16%
61.23%
18.67%
BR-FedBi
82.99%
82.80%
82.54%
82.34%
BR. TedDiM
82.52%
81 81.22%
72.68%
26.21%
BedBiM
82.79%
82.67%
82.61%
80.98%
BR-FedBiP
82.60%
80.14%
61.40%
18.67%
BR-FodBiP
82.97%
82.85%
82.58%
80.98%
Table 14: Comparison of top-1 test accuracy (%) for hyper-representation task on MNIST with heterogeneous Data, under ALIE attack for different numbers of attackers.
CWMed
Algarithm
Algorithm ==3
==3
10
5
/
BILANTINE
81.36%
76.78%
62.95%
BILANTINE
70.45%
45.54%
BR-FedBi
82.39%
79.26%
70.83%
53.67%
BR-FedBi
81.92%
71.93%
58.25%
54.39 %
BR-TedMiM
82.46%
25%
72.76%
53.71%
DR FedBiM
82.329
74.03%
69.38%
54.31 4
BR-FedBiP
82.40%
79.25%
70.80%
53.68%
BR-FedBiP
81.998
71.94%
58.25%
54.39 %
Algurithm
Median
Algorithm
Krum
/=3
=
BILANTINE
63.69%
74.73%
73.74%
72.44%
BILANTINE
54.32%
53.67%
53.54%
52.97 %%
BR-FedBi
84.02%
83.56%
83.11%
82.98%
BR-FedBi
83.06%
83.02%
82.92%
82.82 96
BR-FedBIM
83.37%
16%
79.53%
82.99%
BR-FedBIM
82.79%
82.83%
82.92%
82.72 %
BR. BR-FedBiP
84.02%
83.58%
83.24%
82.98%
BR- FedBiP
83.01%
82.92%
82.90%
82.72 %
Algurithm
CWTM
Algorithm
TM
1
BILANTINE
76.63%
72 22.
56.88%
50.30%
BILANTINE
75.80%
69.800%
73.961%
22.54 %
BR-FedBi
82.13%
56.71%
58.25%
31.09%
BR-FedBi
83.31%
83.35%
83.27%
82.90
BR-FedBIM
82.19%
65. 06%
59.52%
11.95%
BR-FedBiM
83.73%
83.07%
83.07%
83.01 %
BR-FddBiP
82.15%
56.71%
58.25%
32.06%
BR-FodBiP
83.31%
83.35%
83.27%
82.90 %
21

---

Published as a conference paper at ICLR 2026
Table 15: Comparison of top-1 test accuracy (%) for hyper-ropresenntaion task on MNIST with heterogeneous Data, under RN attack for different numbers of attackers
Algorithm
RFA
Algorithm
CWMed
BILANTINE
71.12%
69.95%
67.68%
9.215
BILANTINE
68.19%
64.06%
6.3.22
58,41%
BR-FedBi
82.61%
82
BR-FedBi
82.77%
BR- FedBiM
82.61%
82.53%
82.609%
81.24%
BR- BR--eedBiM
82.66%
82.65%
82.57%
82.28%
BR Re-BBP
82,836
82.608
82.62%
80.35%
BR BRdFed
82.89%
82.76%
82.61%
81,42%
Algorichm
Modian
Algorithm
Krom
T=3
10
T=3
==5
= 10
BILANTINE
66.87%
66.47%
63.122%
60.66%
BILANTINE
57.57%
57.25%
45.62%
44.64%
BR-FedBi
82.85%
82. 62.66%%
65%
80.788
BR-FedBi
82.8%%
82.57%
82.78%
82.45%
BR. T'ddiM
82.77%
82.54%%
82. 609%
82, 12.42%%
BR FedBBiM
82.70%
82.50%
82.50%
82.51
BR-FedBiP
82 84%
BR-FedBiP
82.57%
Algorithm
CWTM
Algorithm
TM
10
5
10
BILANTINE
12.27%
BILANTINE
71.36%
65.33%
15.36%
BR-FedB:
82.69%
82 28%
81.65%
75.29%
BR-FedBi
82.82%
82,50%
82. 62.666%
82.11%
BR-FedBiM
82.76%
82.23%
82. 11%
64.20%
BR-FedBiM
82.46%
82 82.28%
82,44%
34%
BR-FedBiP
82.68%
82.28%
81.13%
73.26%
BR-FedBiP
82.78%
82.52%
82.61%
82.34%
Impact of number of clients We evaluate the performance of the methods under different numbers of clients, where set {10, 25, 50} and select the corresponding numbers of attackers as f = {3, 7, 14). The top-1 test accuracy under these settings is presented in Figure 1. Across all configurations, the proposed algorithms consistently outperform the baseline methods. These empirical results demonstrate that the proposed methods maintain strong robustness even as the number of clients varies.
Methods
Fed
BR. BR-FedBIM
FecBiP
BILANTINE+
Text Accurssy tSa
se- 22
26-
28-
20-
20
Toxt Accuracy IN
CWTM
100
BP|
100
CWTM
320
1:0
Random Moise CWTM
2z-
30-
R0-
40
60
40
40
22-
20-
20-
Test Accurscy (ha Totk Acorary 190
k.00
ALIE|
Krum
BF Knum
IPM |Krum
320
Minic | Krum
150
Random Noise| Krum
ce-
ae-
10
10
25
25
ALIE Median
BF Medi
100
IPM Median
120-
Mi mic Medilan
Random Moise| Medilnn
an-
50
60
20-
5o
1e
28
28
10
25
50
10
25
50
16
25
10
25
10
Text Accussyy BM
ALIC RFA
IPM RFA
Mimic RPA
Random Nolan RFA.
20
50
50
e0
20
se.
50
20
20
20-
20
10
32
50
10
20
100
20
Test Accuracy (N)
1:0
40-
60
30-
10-
x
46-
70
20
20-
26-
Number Clients
Number
Clients
Numbor of Clients
Number of Clients
Number of Clients
Figure 1: Impact of the number of participating clients the top-1 I test accuracy for the MNIST data nyper-representation task. The figure compares the performance different aggregation methods as the number of clients varies.
22

---

Published as a conference paper at ICLR 2026
Performance under IID Setting. We evaluate the methods on a homogeneous MNIST dataset with f Byzantine attackers among n = 25 workers. As shown in Table 16, the proposed approaches consistently outperform the bascline method (BILANTINE) under the IID setting. In particular, BR-FedBiM achieves the strongest worst-case performance across most aggregation rules, attaining 95.82% accuracy under Krum and 92.68% under CWTM during BF attacks. These results highlight the robustness and adaptability of the proposed methods in both IID and non-llD scenarios.
Table 16: Hyper-repressntattonn on MNIST with iid data. For each block, the algorithm with the highest test accuracy (%) under each attack is highlighted in bold. "Worst" shows the worst test accuracy among all attacks.
AGG
Algorithm
ALIE
BF
TPM
RN
Worst
AGG
Algorithm ALTE
BF
IPM
RN
Worst
BILANNINE
84.52
BILANTINE
84.63
Krum
BR-FedBiM
BR-Fedli
95.76
95.76
95.82
95.76
95.68
95.68
TM
BR-FedBBiM
BR-FedBi
95.88
95.24
95.25
95.92
95.71
95.65
95.24
BR-FedBiP
95.75
95.75
95.76
95.70
95.70
BR-FedBiP
95.89
95.25
95.24
95.74
95.24
BILANTINE
54.60
BILANTINE
82.49
84.18
80.33
RPA
BR-FedBi
95.69
94.88
94.87
95.67
94.81
CWMed
BR-FedBi
95.36
94.82
94,97
95.78
94,82
BR-FedBIM
95.87
94.35
95.93
BR-FedBIM
95.79
95.44
95.89
95.44
BR RR-FodBiP
95.69
94.80
94.87
95.68
94.80
BR- BR-FedBiP
95.36
94.82
94.97
95.77
94.82
BIT ANTINE
84.92
80.57
81 18.58
84,
80.57
BILANTINE
60.82
15.00
16.66
51.96
15.00
Median
BR. FedBi
95.93
94.98
94.90
95.73
94,90
CWTM
BedBiiii
90.88
81.34
91.12
95,40
81.34
BR FedBiM
95.92
95.52
95.49
95.86
95.49
BR BR-FedBiM
94.95
92.68
92.34
95.70
92.34
BR-FedBiP
95.93
94.99
94.90
95.75
94.90
BR-FedBiP
90.91
82.74
91.13
95.46
82.74
Experiments with different seeds. We evaluate the robustness and consistency of our methods under different random seeds by running each experiment with different seeds. Table 17 shows the performance on MNIST with heterogeneous data, while Table 18 reports results on CIFAR-I0 with homogeneous data. Each block groups algorithms using the same aggregation rule, and we report the mean and standard deviation of the test accuracy under various Byzantine attacks. The "Worst" column highlights the lowest test accuracy across all attack types for each method. Our proposed BR-FedBiP and BR-FedBiM consistently outperform BR-FedBi and the baseline BILANTINE in most cases, showing both strong robustness and stability.
Table 17: rlyper-representation MNIST with heterogeneous data. "Worst" shows the worst test. accuracy among all attacks. Each block groups algorithms under the same aggregation rule.
AGG
Algorithm
ALIE
BF
IPM
RN
Worst
BILANTINE
73.74=1.46
46.02-42..36
49.85 1.83
63.12
46.02+42.36
BR-FedBi
83.11=1.64 82.00:11.98
81.28:11.93
82.65+1.911
81.28:11.93
Median
BR BR-FedBiP
83.24-2.28 8..24
81.36-1.83
82.73:11.49
81.36:1883
BR-FedBiM
7..53=1.28
8..51:
82.60 1.81
82.59++2.44
1..53
BILANTINE
66.96=1.73
32.02+22.75
19.96:1.557
67.68+1.81
19.96=
BR-FedBi
70.83=3.26
1..41
3..70:3.22
1.84
70.83:13.26
RFA
BR-FedBiP
70.80=2.19
79.26:1:2.26
80.6912.57
82.62:11.97
70.80:12..19
BR Fe-Bee
72.76-1.73
81.95
81.87:1
82.60:12.11
72.76:11.73
BILANTINE
73.96=2.80
17
46.05 1.95
19.19.12.19
41.84.12.17
BRdFedBi
83.27=1.89
82.61 12.11
82.541 1.76
82.66:12.00
1.754
BR-FedBiP
83,29-2.28
82.58+11.77
82.58+ 1.83
82.61+1.59
1285
BR-FedBiM
82,44=3.44
82.69+1..77
82.61 1.81
82,44+22444
82.44+13.44
BILANTINE
56.88-1.81
51.02:11.33
58.40-1.78
63.32-11.87
11.02.11.33
BR-FedBi
58.25-1.28
79.70+2.67
81.51+ 1.83
82.76+2.10
58.25+
CWded
BR-FedBiP
58.25- 1.92
79.70+1.35
81.62+1.88
82,76+2..2
58.25+1.99
BR-FedBiM
69.37-1.63
82.2311.62
1..30-1102
82.66-12.10
69.37-1163
23

---

Published as a conference paper at ICLR 2026
Table 18: Hyper-representation on CIFAR-I0 10 with homogeneous data. "Worst" shows the worst test accuracy among all attacks. Each block groups algorithms under the same aggregation rule.
AGG
Algorithm
ALIE
BF
IPM
RN
Worst
BR-FedBi
60.61
1.03
63.22:t1.32
13.70+1.11
1.120=1.12
Median
BR-FedBiP
63.39:11.55
62,04 1.44
59,3611.07
6.38
59.36=1.07
BR-FedBiM
63.12:11.52
6..68
63.40
62.67:10.98
62.67=0.98
BR-FedBi
1..59::1.09
57.52
63.13:1113
43,02:+1.62
43.02==1.62
RFA
BR-FedBiP
19.36:::1.4
52.67=1.004
1..52+1.56
49.36=1.45 1,39
BR-FedBiM
54.83-+1.38
6.18
62,47=11225
63.09:1..48
54.83=
BR-FedBi
61.31=00.39
62.92:10.34
63.11
1..45+1130
42,45=1.30
TM
BR-FedBiP
6..22:+:.00
1..09
62.92-10.26
63.22:+0.51
1.12
BR-FedBiM
63.64:11.83
63.3411.996
63.18
63.74-10.51
63.18-1.711
BR-FedBi
63.49:+0.58
63.16+0.23
63.06++1.22
43.60+#1.27
43.60=1.27
Krum
BR-FedBiP
63.72-10.38
03,49-10.22
63.16:00.55
63.17-00.46
63,16=0075
BR-FedBiM
63.19:1.113
62.80+0.92
63.09
63.21+3.880
62.80=0.92
BR-FedBi
48.84-1:0.64
54.83-10.82
63.14:0..55
42.01++1001
1..01=1.01
CWTM
BR-F BR-FedBiP
37.70:11.60
48.8440.67
54.83+00.1
61.40:0.51
37.70=1.60
BR-FedBiM
51.92:10.57
62.21
60.37+0063
62.92-10.33
51592=0.57
BR-FedBi
54.45-10.50
0.76
63.70-11009
43.31+1.68
43.31
CWMed
BR-FedBiP
47.26::1.21
54.45+1.47
$7.38+1.02
63.51
47.26=1.21
BR-FedBiM
47.90:11.80
52.70
58.7740.71
63.08
47.90-1.800
24

---

Published as a conference paper at ICLR 2026
E LOWER BOUND FOR ASYMPTOTIC ERROR (THEOREM 1)
In this section, we establish the lower bound on the asymptotic error introduced by é-fraction of Byzantine attackers in distributed bilevel optimization. We assume that the gradients of the lower- level and upper-level loss functions satisfy the (Sg. Bg)-grndient dissimilarity assumption and the (Cy, -rradieet dissimilarity assumption, respectively, as specified Assumption 8.
Assumption ((C. gg-ggadient/Hessian dissimilarity), The local gradient/Hessian A, of the honest worker E H. is said to satisfy (s, B) (ir.B))grrdnn/HHeeee gradien//Hessian dissimilarity if
1 776
Σ iE
|A Axll = B² |x
1 where Ax = [H]] EiEHAN As.
The local gradients V (fi(x.y) of the honest worker H satisfy the (Cr, By)- gradient dissimilarity assumption.
The local gradien//Hessian (x,i(x, V yx,) 2 y) of honest worker i E H
satisfy the (Sg: Bg) -gradienettt// Hessian dissimilarity assumption.
Our proof is inspired by the work of Allouah et al. (2024) and extends their work to bilevel optimiza- tion. Now, we restate Theorem
Theorem 1. For an arbitrary distributed bilevel algorithm, there always exists a federated bilevel optimization problem satisfying Assumptions 1-4, such that:
(
v+x(()11 2
(16)
1- + B3)
where 5 < min {2-B7- 24 is the proportion of attackers among clients and & is the output of the algorithm.
Sketch of proof. In the proof, we construct a set of quadratic bilevel loss functions for clients, denoted by (x)..).... ( (.)). We consider two quadratic FBO problems with attackers. In the first problem, the functions of the honest workers are denoted by 2H, ,, (x) { (x), (1) (x)) while the remaining (- 4 (x)} are the functions of attackers. In the second scenario, the functions of honest workers are TH (x) (
(x)], and the remaining functions of the attackers. The messages sent from the clients (including honest ones and attackers) to the server the same for both problem settings. Regardless of the aggregation rule, the server, being unaware of the identity of the attackers, will produce the same output & for the two FBO problems. However, the two problems have different optimal points and this single cannot be close both points, which leads to our lower bound.
the
We consider a distributed system consisting of n clients, among which d-fraction of them are Byzantine attackers. For the proof, we construct set of quadratic bilevel loss functions for the n clients, denoted as (xx)x)..... (x)), each composed of a lower-level objective and an upper-level objective.
Lower-level objective. We consider the following lower-level objective for n clients, where Y1. 72 are positive constants, and Cx, Cy Rdd are given positive vectors. For i E [n]. the lower-level objective is defined as:
(x Cx)² + (y C2)²,
for E for E {ôn + 1, ...., (1-8)m}, for E {(1 8)n + I,.... n).
yx
x2 y2)
(17)
21 x2 y2)
Upper-level objective. We consider the following upper-level objective for n clients, where di a2 positive constants, and Cx Cy E Rd are vectors. For i [m]) the upper-level objective is defined
25

---

Published as a conference paper at ICLR 2026
a1
x - Cx) 2 + 2 (y y Cy)= d (and + 02(1 - 26)) x yy for i E [1,...,8n}} xx y2)
2
71
((xx)))
22
01 (a,ō + 02 (211-2)) y for E (ôn + I...., (1 8-m),
7:
a:
x2
+ y2)
ai (a1ō + 02(11 26) y for E ((1 5)n + n,...,n),
2
(18)
where (x) = fi(x. y")x (x)). To prove the theorem, we consider two scenarios, each corresponding
to different subset of honest workers and attackers in problem (18). In each scenario, (1 8)n clients are honest, while the remaining òn clients are Byzantine attackers.
The first scenario. In the first scenario, we assume that honest workers have indices H4 f1..... (1 d)m}, while the remaining are Byzantine attackers B1 {(1 8)n 1....,... ....
The corresponding problem can be formulated as
min PH (x) fx, (x.xx()) XER
Σ fi)x)
Hil
iE
(19)
subject to yi(x) arg min yERv
gxx,y)).
H4
iE
As defined in (17), the solution to the lower-level problem in (19) given by
mi0y
xi()
(20)
71d + +2 25)
As result, the corresponding upper-level loss function in (19) for the i-th client is given by
αn (x- - Cx) 2 an (xi(x) - cy)² a1oC,x, for i {1,...,ön, 5n), az [x2 + (yi(x))) - a100,x,
f (x,(((()))
for i E {8n + 1..... (1
8)m}.
(21)
The second scenario. the second setting, we assume that honest workers have indices H2 {ôn + l,..., nt,, while the remaining are Byzantine attackers B2 {1...., ,n]. The corresponding problem is formulated as follows:
min (x) = (x,, XERP
1
Σ xxxx))
172
iEH2
(22)
subject to y²(x) = arg min
gx(
yER*
HHl
iE
As defined in (17), the solution to the lower-level problem in (22) is given by
y²(x) =
(23)
As result, the corresponding upper-level loss function in (22) for the honest clients is given by:
{ 0/2 [x" (x)))), for i {ōn ...... : 8)m), for i ((1 5)n I,....n.. n).
f (xxxz((x))
(24)
a (x)))),
Although these two sets of problems have different global optima, the server, unaware of the identity of the attackers, will produce the same result x for the two FBO problems. However, the two problems have different optimal points, and this single & cannot be close to both points, leading to our lower bound. This indicates that no aggregation algorithm can achieve an accurate model under Byzantine attacks.
E. LOWER BOUND
In the following Lemma, establish the minimal aggregation error.
26

---

Published as a conference paper at ICLR 2026
Lemma 1. Consider the two sets of bilevel optimization problems described above and assume that Assumption 4 holds. The asymplotic error is at least:
a²
(C2 + C3 +
max (x) --H (x3) (H2 (E(122
8(1 ( + az2(1 - 26))
Proof. The first scenario. In the first setting, we assume that the indices of the honest workers H1 {l,..., (1 5) Recalling from (19), for any honest client H1. the first set of lower-level loss functions is defined as:
(x Cx) (y Cy) y²)
for i (1,..,õn)) Ön), for i {ôn l,..., (1 8)m}.
(x,)) =
(25)
The solution of the lower level objective given by yi(x) = 116+12l1-287 Recall from (19), for any honest client E M1, we consider the first set of the upper-level loss functions to be:
8n
2 (x Cx) (xi(x) Cy) and0yx
for i E 8n}, for i {òn 1, .... n). (26)
(x) = f. (x,x(()))
an xx2 tT a1²C,x
2
In the first setting, the global optima of the first set of loss functions (19) is given by
Oy (i 7id + 72(1 26)'
8α Cy + Cx
(27)
an a2 25)
The second scenario. In the second setting, we assume that the indices of the honest worker He = {ōn + 1,..., n. Recall from (22), for any honest client i E H2, we consider the second set of the lower-level loss functions to be:
xx y2) o (x.)) 1 x2 +2
for E {8n + 1, ...., (1 - 5)m). for E {(1 8)n + 1.... n).
(28)
The solution of the lower-level loss function is (x) 0. Recall from (22), for any honest client i H2, we consider the second set of upper-level loss functions of the honest clients to be
022 (x2 xx)))
for i {ōn + 1, .... (1 8)m}. for i {(1 5)n 1,.... n².
Φ (x. (3())
(29)
an [x2 +5(())
In the second setting, the global optima of the second set of loss functions (22) is given by
x²(x) = O. x = 0.
(30)
Although these two sets of problems have different global optima, the server, unaware of the identity of the attackers, will produce the same result for the two FBO problems. Then, we analyze the minimal emror follows. For the first scenario, we obtain that:
8
1 28
PH (x) TH (x+)
2
1-8
01
1-8 02
| x+ll= -8a Cy xi)
(31)
1
8
1- 28
|| x 111
2
8
01
1 1-8 02
where the inequality uses the output loss functions, we can obtain:
x; <
x
<
xi, and x is a positive vector. For the second set of
1
8
28
DH, (x) PH (x;)
01 +
02
|x||
(32)
2
1
8
1- 8
1
By using max (a. b} > atb 2 we have:
1
8
28
max TH, (x) - TH (x7) (1.2)
> 4
01 +
1 - 5" 012
(1x112 + -x1111?)
(33)
1
1- 5"
27

---

Published as a conference paper at ICLR 2026
By Jensen's inequality, the following relationship holds:
1
| 2 + || xi
|xi|]
(34)
Substituting this inequality in (34) into the expression (33), we obtain:
5
28
max 2H (8) - H (xx) SE(1,2)
1- an 1-8 002
|xi|| 11
(35)
8a (C+ + +z
8(1 - 8) + az 26))
Hence, the proof is complete.
E.2 SATISFACTION OF (S. B)-GADIENNT HETEROGENEITY
We then establish the constraints for the constants and vectors {71,72 72, 01 02. Cx Cy in the bilevel loss function (17) and (18). These conditions ensure the gradients of the lower-level and upper- level loss functions satisfy the (Cg. By)-gradient dissimilarity assumption and the (Cy, By) -gradient dissimilarity assumption (Assumption 8), respectively.
Lemma 2 (Satisfaction of (S, B)ggrdieent heterogeneityy). Let us consider the two sets of bilevel optimization problems in Lemma 1. The condition for satisfying Assumption 4 is equivalent to the condition for the following inequalities to hold:
Ay,1 S 0, Ay.3 S 0 and ||Ay.21 12 - -y,,1 S O,
where
Ay, = 8(1 -6)
1 26 2
(1 (1-8)2 (n - 722)² -B²
11 1--
+ 72
8
1 8-6 8
5
Ay.2 (1-25)(11 72) (220 -22(1 -26)))
(1 8)2 7/2 Cy.
8(1- -21 28)
8
Ay.3 (1 8)2
71 C2
B² 1 22 Cg.
Similarly, we have:
Ax,1 SO,
Ax
and A2,2 S Ax,
where
1 - 20 2
6(1-20)
6
Ax.1
(a) 2²2² - 2-) B3 a1
+ 02 1- 5
(1 - 8)2
1-8
8
1- 28
8
1- 28
(Cx + (c))
8
Ax.2
1 1- 0
(a1 Ox - -By
02
1 1- 8
1-0
a1
8(1 28)
8
Ax,3
Cf - B7(
2 Paf + 02)2 - G7.
(1 8)22
Proof. The first scenario. As defined in (19), in the first setting, we assume the indices of honest workers are H, = (1,..... (1 8)m}. For any honest client Hi, we define the first set of the lower-level loss functions as:
2 (x Cx) 2 z (y 02
for i E {1, ōn), for i (ōn 1...., (1 8)m}.
of (x, =
(36)
x +2²)
The gradient of the global lower-level loss function in (36) is computed as follows: 25)) y 8n
VYHN, (x (715 72(1 1
(37)
28

---

Published as a conference paper at ICLR 2026
Similarly, the gradient of the local lower-level loss function in (36) is computed
V Vyg = My 12y
?1 Cy
for E {1,..., (1....,nn]. for i E {ōn + 1,... (1 - 8)m}.
(38)
Combining (37) and (38), the gradient dissimilarity of the lower-level objectives can be bounded as:
6
( 72) 1 26
1 28
1 1- 5 7C )
EB (x.)) - Vygn, (x,
y)1"
1-8 y
8
(39)
1 28
+
)² ((72 n)y + +,,yy²
1 1-8
And the norm of the global gradient in (37) can be written as:
[IV (x, x>|| - 1 12 1-
1-2 y - 1 - 8 nnc)) ?
1 28
(40)
In order to satisfy (c. -ggrddientt heterogeneity in Assumption 4, we have:
V y (x. y) VygH, (x, y) |9| < B3E
[[ || (x.
(x, x>11 +
(41)
Combining equations (39) and (40) with (41), we have:
E V Vygl (x,y) Vygti (x,y)
11
|| V Vy9Ht xx) 53
8(1 - 26)
1 1 28
(>1 - -22) B²
||y112
8)2
71
1
8
12 1 1 8
1y.1
2 1 25
(n1 72) - B3 m
5
12
1 1-8
- 28
2 )
1 1-8 1
8
(42)
8
8
Ay.2
6(1 - 25)
8
+
70 B
23 0.
(1 8)2
Ay.3
To ensure the validity of the above inequality, the following condition must be satisfied:
Ay, S O,
Ay.3 S and || Ay. Ay. S O.
(43)
Recall from (21), for any honest worker e Hi. we define the first set of the upper-level loss functions as:
(x,x(((x)) = [x 2 2 (xi(x) Cy)² 01
for i E (1,...,81)) 8n}, for i E {ōn 1, n.... (44)
The gradient of the global upper-level objective in (44) is obtained as follows:
V (x)) = (anδ + a2 - 26)) x
San dō.. Ox
(45)
1-8
Similarly, the gradient of the local upper-level loss function in (44) is computed as:
[1xx on Cx
son Cy
for i {1, 5n), for i E {8n 1,... (1 8)m}.
vx((xxx(()))
az 8a Cy
(46)
29

---

Published as a conference paper at ICLR 2026
Combining (45) and (46), the gradient dissimilarity of the upper-level objectives be bounded as:
8(1 26)²
E
V (x)
Vnn, (x)]]
((a) 02) x 0z xx)²
(1 8)3
(47)
(1 26)82
+
((a2 a1)x +ax C1
(1 6)3
And the norm the global gradient (45) can be written as:
E [IVVSN (x)1
((<:) ((1
1-8 02
8
1 - 26
1 1-
1-0
a Cy 1 a
5
- Cx 2
(48)
To satisfy the (s, -3garadieent heterogeneity condition specified in Assumption 4, the following must hold:
[x) V/H, (x) (x)) = B& [IV +
(49)
By combining equations (48) and (47), we obtain:
E [|| [ - Vy (x))1²] B&E | fH, (x)1?² -C7
5(1- 1 26)
1
(an (x2)² - B2
+
02
||x|
(50)
(1- 8)2
8
1 -
Ax.1
28
6
1- 26
5
2
(an -02)xx - B7(an
(Cx + Cy)
1 8
1-
1 1-8
1-5
Ax.2
8(1 28)
8 az Cx)² - 5.
B3{
8)
(1 8)2
Ax.3
To ensure the validity of the above inequality, the following condition must be satisfied:
Ax, S O,
5 and A S Ax,3
(51)
Hence, the proof is complete.
E.3 PROOF OF THE LOWER BOUND IN THEOREM 1
To satisfy the (G, -)ggrddient heterogeneity assumption, the constants and vectors (71:72, 01, 0r2, Cx, Cy) in (17) and (18) have satisfy the constraints in Lemma 2. Once these constants and vectors are chosen to meet the specified conditions, we derive the lower bound for the asymptotic error, which is influenced by the heterogeneity in both the lower-level and upper-level objectives.
Lemma 3. Consider the two sets of bilevel optimization problems in Lemma and Assumptions 1- 4 hold. the constants and vectors ar 02 Cx and Cy satisfy the constraints in Lemma 2, the asymptotic error at least:
8 (G + + +2(/5/)
V (x)]1
max (E(1.2
4(1 8(2 + BB))
Proof. Building on the analysis above, we select the constants a1 a2 and the vectors Cy. Cx to satisfy the incquality specified in Lemma 2:
5
a1 -1 B7), ag = =1 1-25 28 B3).
(52)
30

---

Published as a conference paper at ICLR 2026
The vectors Cy and Cx set as follows:
(1- (1-6)
(1- 53-
C%
(53)
8(1 - (1 + B3 00)00022
5(1 26)(1 + B3)o102
Combined with equation (35) and the above parameter, we obtain that:
8 ( + 2cr
max DH (x) TH. (x²) (E(12)
(54)
8yr (1 8(2 + 13)))
We demonstrate that the selected coefficients ensure the upper-level loss function satisfies ja strongg convexity and Ly smoothhess
- 28
max (1.2)
= L,- uy 1-8 02 2 p..
(55)
Given that the upper-level objective satisfies the pyy-trong convexity assumption, the following inequality holds:
[> 2 2 (+(x) + (x*)).
(56)
By combining the results from (54) with (56), derive the following lower bound:
8 ( 2 + +
VVH, (x)]|²
(57)
max (E(1
4(1 8(2 + BJ))
Hence, the proof is complete.
F GENERAL LEMMAS FOR CONVERGENCE ANALYSIS
In this section, we provide general lemmas that frequently used throughout the proof. Lemma 4 ((Chen et al., 2024), Lemma B.2). Under Assumptions 1, 2, there exist positive con-
stants L Ly, Lz,, such that ( y" (x), z² (x) are Lv Lyy Leg- Lipsschizz continuous, respectively. Moreover, we have [x)]l S. CL for all x E RRdx Ps
Lemma 5 ((Dagréou al., 2022), Lemma C.1 and C.2). Under Assumptions 2, there exist positive constants Lyx and Lux, such that y (x) and z (x) are Lyx and Lzx- smooth, respectively.
Lemma 6 (CChen et al., 2024), B.I). Under Assumptions 2, if < Lotpo the following inequality holds:
2
VV - yfll S (1 3pgg -
-
Lemma 7 ((He et al., 2024), Lemma B.3). Under Assumption 3, we have the following variance bounds in distributed learning:
Var
D
Fkl
2
Var
S <02/((1 8)m). S oof/((1 - -8)m). Var D
D
Fk
Var
D
Fk
of.
Var
D
Fk
Var
D
Fkk
S of/((1 -8)n), Fkj
where of A o² p*+
Lemma 8 ((Khanduri al., 2021), Lemma C.2). If à is St-stnongly convex and my -moothh, then
(Vo(x) Voly), x y) 2 Txyly
||x
y112 +
Vo(x) Vo(y))1
7x fly
Th + mly
G CONVERGENCE ANALYSIS FOR BR- (THEOREM 2)
G. PROOF OUTLINE
In this section, we prove the convergence results stated in Theorem 2. Our analysis of BR-FedBi in Algorithm 1, which follows the framework of (He al., 2024), consists of four key elements:
31

---

Published as a conference paper at ICLR 2026
(I) Aggregation error (Lemma 9),
(2) Lower-level convergence (Lemma 10),
(3) Gradient Update Bias (Lemma 11),
(4) Descent Lemma (Lemma 12).
By combining these elements, we derive the final convergence result presented in Theorem 2.
Notation. For convenience, we have the following notations used throughout the proof:
+3+ 13= 11=17/ 12 p² 2 Xg = Ngggg Mg + Lg
of = =1 p²)
In the k-th communication round, the server distributes the global parameter {x* yx z²1 to the clients. Each honest client H computes the gradients using their locally sampled data, of Dj. and of Dg and transmits them to the server:
D v G(x y )z) vxF(x* y of)).
D - G (h) FyP o!
(58)
yu
D A V G(X
where x and yh the upper- and lower-level parameters, respectively. Here, spt and of denote datasets sampled from the distribution available to each honest client.
Upon receiving the gradients from all the clients (including honest clients and attackers), the server employs Byzantine-resilient robust aggregation rule AGG(.) Rdxx - Rd to aggregate the updates. The aggregated gradients computed as follows:
D AG
D x)
D = AGG(D y.1. D D
(59)
D AGG(D 2 2.1..... D* D
Finally, the server updates the global parameters {x* yh: 2²) using the aggregated gradients and the learning rates Th. fly > 0. The updates are performed as follows:
x k+1 =x 7/x D
b+1 = =x 17y D
(60)
x+l = =²² D
G.2
AGGREGATION ERROR
We define the aggregation enror the deviation between the robustly aggregated gradients and the average gradients of honest clients. Specifically, the aggregation error is expressed as:
* = D x
D x1
<h D
D D 2
*# = D
where D
1 Eiex D& D
1 Eien D y.i and D
ΣIEN D
[
We then establish the following bounds for the aggregation enror. The detailed proof is provided in Appendix 1.1.1.
32

---

Published as a conference paper at ICLR 2026
Lemma 9. Suppose Assumptions 1-4 hold, and the robust aggregation rule AGG() satisfies the (8, ---rousstnsss criterion. The aggregation errors in the BR-FedBi algorithm (Algorithm I) satisfy the following inequalities:
(1)
E
||
S nCy + KO² (1+
1
(1+ + 8)m
(2)
[||=1|]]
- 2k (p + (f) + 2no7
1+ (1 + 8)n
(3) E ||*
- 2x (p 2 + (t) + 2no
1+ (1+ 5)n
where of = (1 + 0²) and Ct.
G.3 LOWER-LEVEL CONVERGENCE
We then analyze the convergence behavior of the lower-level variables in our bilevel algorithm. The detailed proof of this lemma is provided in Appendix J.1.2.
Lemma 10. Under Assumptions 1-4, and 5-6, the following inequalities hold for variables y and z:
(1) E ||y
-y2+111
s (1 TyHa + +2n L2)1 [1y* -
->+11 (3ng
+ Th Pg
) || !1
61 7x
4
1zy
(E [|E(D>))]] TH [IE+|]"])
T/ylug
0² (1
of
37/
8)n
(1 - 8)y²
(2)
E
1| ++1
2 ++1 [111 [1]]
iallig
+ 6n 1-g
|| 2011²] + Anna + on
[|>* - x111
2
Fgg
4n 1z ) (E ||E +E [1=211]]
4L2 1hx + +L +
Taal
3/12
21122
E |||$||
+ (2m² + 4L2.12 + 4L 4L
of
(I-
Ug
where y = y (x*) and z = (xtt).
G.4 GRADIENT UPDATE BIAS
Next, we then analyze the gradient update bias of BR-FedBi in Algorithm 1. The gradient update bias measures the distance between the hypergradient V (x*) and the expectation of the update gradient E {)) where the expectation is over randomness.
Lemma 11 ((He et al., 2024), Lemma B.4), Suppose Assumption 1, 2 and 3 hold, if 2 Cf/Hg
we have:
E || (D+ V (xx [x] < 3L33 ||x*
y11 + +3L3E 1 25 [3]
where L3 = 13 D.pp?
33

---

Published as a conference paper at ICLR 2026
G.5 DESCENT LEMMA
Finally, we analyze the progression the upper-Ievel loss function in BR-FedBi, as described in Algorithm 1. During each iteration, the updates for x y and x+11 are given by:
x k+1 x AAG (D
x,1 D xn) x
1/x Dx x 1/ Dx 1/5xx:
y k+1 = -y nyAGG (D y,1
D y.n) = y Dr =y Dy - Gy:
zt1 z" TZAG (D 2....... D z The D z" -DaD 5
The detailed proof of Lemma 12 is provided Appendix J.1.3.
Lemma 12. Suppose that assumptions 1-4 hold true. Recall in Lemma 4 that the upper-level loss function is L 254-300 ao--smothhh all k E [K], we can obtain
E 2H [x]
s E PH (x*)]
Tx E
(x*)
12] + 2
|
Ba
E [( - EDD |1
4
of oi
Toon
7xx
E
|| )
[|]
(4 + (vo E ||$$1|
2
(1 8)
where of (1 + 0²)
G.6 PROOF OF THEOREM 2
Theorem 5. Suppose that Assumptions 1-4 and 5-6 hold, and that the robust aggregation rule AGG(.) satisfies the (6, ko-robussnesss criterion. There exist positive constants c, Cy, and Oz such that
Tly Cy.
Tk C2Tbx
and the step size The satisfies
A K.A
7x min
a1
Here, we have
Ao 0² a =
A = (1 8)m
4 (I.v + 6T2y + 2.2. + 4T.zap)
and Ao is a positive constant independent of n and K. Then, for K 2 1, the algorithm converges as:
Σ E
(x+)
0
A K
A Ag
(0 (G
+
(61)
K
where & (x + of the algorithm.
- + 1| 212 and the expectation is taken over the randomness
Proof. In order to obtain the final convergence result, we combine the above Lemmas. To obtain the convergence result we define the Lyapunov function be
L1 = (x*)) + [|xx
y
+
1
z
(62)
34

---

Published as a conference paper at ICLR 2026
Consider the Lyapunov function in (62). By combining Lemmas 10, 11, and 12, we obtain:
Lk+1 - Lik:
1x
|/ (x
(x*)][²
4
31 122
Myylg
215 +
4n + L3
E -x
4
19
T1
30 L2
9
Mally
+
6n 13
E || -|"11= 2711²]
2
2
T2
+
1x
+
LV 2 x
+ -64.
47 Ly + 4L 122 + 44 +
4 Li
E [|
2
Blylg
T/allg
Ts
0f + 2nl (1 8)n
a²
+ (2112 + 6L2..1 12 + +112.11 1 + +44 4b + Lvo)
(1 (1- 8)m
L
4 Ly
+ 41 L2g + +64 2 + ALL n/ + 46 pTk
41xx +
13 ||
2
Mg
Tallgg
+
3
+
21/z
E
||
ck 12
+
3rl
+
Fly
E
|
Ug
pgg
(63)
Under the assumptions that
1
1
Pg T.
1xx S Pa
fly
S
2/1g
1/2
S
2p
Tx S
{Lvo + +61, + AL2. + 4Lzap)
7xx S
32
(64)
and invoking Lemma 9.we can implies
Cx+1
Cs
11x
E
/ (xx)
[x]
2
31
123
flylg
2nÿ 1.3 +
4 T
+ on
E [1se - -
4
Mg
Ti
3//p 12
natt
61/2 T
E. ||2--11111 2111²²]
2
2
+
1x
+
L + 6L
6L2.
1xx
2
40 Byllg
L2 + AL2. 1/2 + +4 +
41 L3 Tallaa
E [| 1|]
2
Ts
of (1-6)n
a²
+ (2m2 + +6L2. R2 + +4L2 12 + 44 2x + Lvo)
+ 22n (1 - 8)n
(( (8ne + 101xx
3ry kO?) (1+ (1+8)m
1
.ko +
M4g
Mg
+
811x
+ 10Tx
x2 + 27) +
B1ly
n
Mg
Ng
(65)
We now analyze each term on the R.H.S. to further bound them.
Analysis of the coefficient for E
||y* y!!
35

---

Published as a conference paper at ICLR 2026
Under the assumptions that
Mg 1672 g
fl -
Tle $
(66)
6/1g
we can implies
2n 13 S
Typy
61 L2 S
7/ L
(67)
8
pg
Then, bound the term T3 in the following manner:
37x L
MyPg
512
12
30 12
Tyllg
Ti S 2
+
S 0,
(68)
Mg
2
16
where the first inequality follows from (66). The last two incqualities uses 122 Analysis of the coefficient for E
P. 801
and 1/x
241.5
||E* zł| 1]]
Under the assumptions that
Mg Th S
Pa 61. g
Txx S
(69)
2412"
Then, can bound the term T3 in the following manner:
T2 3
Mall
on s
3
< 0.
(70)
2
2
4
Analysis of the coefficient for E
Given the assumption that
Txx S
(71)
4 (L + +6L4. + 412. + +4zzzp)
we can deduce
I + 6L. 1z + 1 + 4T 4T
19x S 0.
(72)
Then, using the assumptions that
MgJly 32L
7x S Hglha
S
(73)
32L
and inequality (72), we can bound the term T3 in the following manner:
4m 1 +
4 L2
7x
T3 <
< 0.
(74)
Tyyg
Talig
4
Combining the above inequality (68), (70) and (74), we then drive the convergence result. For simplicity, we define:
Ao = (202 GL9 + 4L- + Abbup + Loo) (1 + p²) + 26
(75)
A := ((
8Cz + 10 (1+ (1+ + 30y
(1
1mm
1
(76)
Mg
Fgg
(1 + 5)m
and
8cz
Ag = 8czp²
3cy
A2 =
+ 10,
+ 2p²
(77)
Pg
Pg
Hgg
Thus, substituting the above inequality into (65), re-arranging the R.H.S. (65), and combining the term Ao, A1, A2, A3 from (75), (76) and (77), we obtain
1xx E
V (x* + 7xx (1 8)n
A
1xx + xA1o² + RA2 + nAstE)
Lx+1 - Lx S
4
(78)
36

---

Published as a conference paper at ICLR 2026
For simplicity, define:
Ao o²
Ag (1 8ym. Rearranging the terms in (78), we obtain
(79)
1x E v (x*)1"² - La Lx+1 + Thx (AoTic + KAI + + #KA2
+ k
(80)
As the above inequality (80) is true for an arbitrary &o E [K]. by taking summation on both sides from k = 0 to k = K 1, we can obtain
( Lk
(fu-
E
Vo (xt) s
+ AoTx KA K + KA23K + KAgS2K)
1xx
(81)
Dividing both sides of (81) by K, we can obtain
1 K-
Σ E
P (x*) (x*) < (
[oo-Lx -L
Co
Lx
AoToK + RA + KA22) nASS?)
(82)
K
7xx
k=0
Analyzing Co- LK. Recall the definition of Lyapunov function in (62), we can obtain
Lo - Lk S (xxxxxx) |1y - yy + 1|z" 11
(83)
For simplicity, define Ag = (x*) + 11 y + 1|z" =2
Invoking (83) into (82), we can obtain
ΣE
V (x*) ||]
A 1xK
+ Ao + xA1 + nAAC? + nASG?)
(84)
K
Recall that the step size l)x satisfies:
A KAa
min
a1
(85)
where
Ao
Q1 =
Ag =
o²
(86)
4 (Lvo + 6L2. + 4L2. 4Lzxp)
(1 - 8)n
Thus, have
1
KA,
1
KAg
max
A
+
A
(87)
T/x
Therefore, substituting the value of in (87) into (84), we obtain
7x
A
A, A
Σ E
v< <4
2
+ 4x
A1o2 + A2 + Ashs)
(88)
K
aik
K
k=
which simplifies to:
D [TDN((() =
0 K
A₂ A g
+ K n 2g (2 (g+
(89)
K
As (0) 41 { x
(2)
x (6)
k }
combing with (89), we finally get:
E
[ (x)1 0
A
A. A
+o
( + (0022
(90)
K
K
Hence, the proof is complete.
37

---

Published as a conference paper at ICLR 2026
H CONVERGENCE ANALYSIS FOR BR-FEDBIM (THEOREM 3)
In this section, we drive the convergence analysis of BR-FedBiM, which shows that incorporating momentum helps mitigate the impact of local variance asymptotic error by reducing the drift between local and global parameters.
H.1 PROOF OUTLINE
Our convergence analysis for BR-FedBiM in Algorithm 1, consists of five elements:
(1) Aggregation error for momentum (Lemma 13),
(2) Lower-level convergence (Lemma 14),
(3) Gradient Update Bias (Lemma 15),
(4) Momentum Deviation Lemma (Lemma 16),
(5) Descent lemma (Lemma 17).
Notation. Recall that, at each iteration k. Byzantine clients send carefully crafted malicious gradients the server with the intention of degrading the global model's performance. Meanwhile, each honest client i computes the momentum term as:
m mx k-1 (1 (3x D x,1
my; By k-1 + (1 (1-By) D y;
(91)
m Bem k-1 (1 [₂) D
2,
After receiving the gradients, the server aggregates the gradients using robust aggregation rules AGG(-), ensuring robustness by satisfying the (ō, x) criteria in Definition 2. The aggregated momen- tum terms for x, y, and z are computed as follows:
m (GG
m x
1
m y
AGG y.1 my my,n);
(92)
m AGG(m 2.11... . )
H.2
AGGREGATION ERROR
By using the (f, robussness criteria Definition and the bounded heterogeneity Assumption
4, we define the error for BR-FedBing to be the distance between aggregated momentum and True update:
<x = m
m x
<t = my
m
(93)
c² m
m
where m
P. Eien
m
m
[ EiEn
m
m
Eien m
TH
We get the following aggregation error bound, the detailed proof can be found in Appendix J.2.1
38

---

Published as a conference paper at ICLR 2026
Lemma 13. Suppose Assumptions 1-4 and the robust aggregation rule AGG() satisfies the (ô, robbussssss criterion. The aggregation errors in the BR-FedBiM algorithm (Algorithm I) satisfy the following inequalities:
(1)
27 ||5y
S 3x
By
1
0² + 3tC
1 1 By
(1 8)n
8x
(2)
- 6x
+
o + 6r (r + +7),
1 Bz
(1 - (1-
(3) E ||<
- 6x
8x
of + 6x (0 + (7)
+ Bx
(1 8)n
where of (1 + p²) o² and C
H.3 LOWER-LEVEL CONVERGENCE
In this subsection, we analyze the lower-level convergence behavior of our bilevel algorithm. The detailed proof of this lemma is provided in J.2.2.
Lemma 14. Under Assumptions 1, 2, 3, and 4, and assuming Tly S min N>0 #o } and
T22 I min { (2g. n.t J. the following holds:
(1)
E
- x 1 11]
112 21
1 1 pq Ly
E
v²11²] -11
Tly E ||B(D))) [|a]
2 (Mg + Lg)
Mg
+ 12 (1n + Lgg)
||
B(D ||]] + RE [||*t]]]
1g
2 (1r + [.g) I.z. n
|1
+
Mi Loggy
(2)
E
E1|z/11- -
- 2 1|]
<
Mgggyiaa
E
-
7 E ||E ||d]
2 (1gg + Lgg)
Mg
+ 12 (1ig + I.ng) 1/2e
E3
|
1E(D
+ EE || (l)
Mg
+ 2 (My + Lg) L2g 1
|
E
Mg MgLg
H.4 GRADIENT UPDATE BIAS
Next, we analyze the gradient update bias of BR-FedBiM in Algorithm 1. The proof details of this lemma can be found in J.2.3
Lemma 15. Suppose Assumption 1, and 3 hold, if p 2 C5/Hgp we have:
E V (x*)= - m [²] s GT ||y y [2]
+ GT [|2-~ -2:11
+ 2E
| - E (D
where -3= L2 L.pp?
39

---

Published as a conference paper at ICLR 2026
H.S MOMENTUM DEVIATION
We now analyze the momentum deviation, which is defined as the distance between the average momentum and the true gradient. The proof of this lemma be found in Appendix J.2.4. Lemma 16. Suppose Assumptions 1-4 hold. Considering Algorithm BR-FedBiM in 1, for each k E [K], the following bounds hold for my m k++1, and m :
k+1
(1)
E my h+1 ---1-EE E (D*
S 88 (1 + Tnghty) (1 + 3ry (.g) TE || E (D$) |"]
1222033 1 + My Lgg
B. ||
+ 3,38
(I ThLb))
1
(
11s+ - y" (xx (xxt + ト [1 (1] + (1 - By)²
o2
(1 8)n²
(2) E2 m k++ E (D bD [1*]
$ 8 (1 + Toggba) E
| - E (D k [1]] + +
+
1
1 [|]=t|1]]
L
+ 12
+ 1221
B E
|m - E (D$) 19|
+ +128
+ Taalg
L || E (D* ||"]
+ 1288
+ Tha Lgg
(L9 + 333)33)) IE y (
+ +36,2
+ MaLg
Lg || z (1
+ 128
+
+ 1200 LE ||<$*|
[+
1 -111
LinEE
||[$ 21
+ (1 - 3x)²
of
1/e Lig
(1 8)n
(3) E m
1++
E (D" + [1(]]
$ 12 (1 + Th) (1 + 12 E | E (D*)) 122]
+ + 1+
1
L 1 |
Matg
+ +2
+ Ilat g
B R ||
E (D$
+ 1282
+ Lg g
(L3 + +3322312 E |1av - y" yx*xxx))x) [1]
+ +3682
+ TaLy
E 12 z [x*)
+ 1282
1+ 1/
1
[||$]1]] + 1232 (1 [+
mallin ),mn) L3 1. [|c* 27
1
+ +
B0)² (1-)))²
of
(1- (1-8)m
H.6 DESCENT LEMMA
In this section, we amalyze the progression of the upper-level loss function in BR-FedBiM as described in Algorithm 1. At each iteration, we have the following updates:
x k+1 = x AGG (m (1.11
m
x
x²
in = x - mx - 1/x ck
y ++1 y+= AGG (my.,...
m my,n) =x By xx my 1y55
z k+1 z² AGG (m ...... m n,n) = z²
mi = z² 1 T2
40

---

Published as a conference paper at ICLR 2026
where AGG(.) denotes the aggregation operator, EE() represents the expected value randomness, and 5x: ck and &x denote the aggregation error terms.
The detailed proof of Lemma 17 can be found in Appendix J.2.5.
Lemma 17. Assuming that the upper-level loss function Px(-) is L we have:
E DH (x []]]
- E de (x*) B
| (x*)
1x
LV
)
| |?]
2
2
+ 1/x / (x*) m + 1
||5
H.7 PROOF OF THEOREM: 3
Theorem 6. Suppose that Assumptions 1-4 hold, and that the robust aggregation rule AGG()) satisfies the (6, roobusttsssss criterion. There exist positive constants Cy, and O2 such that
Mly Cy:
1/2 = C2
and step size The satisfies,
A
Tx min
a1
K A
where
A/ o² kA30² (1
01
Ag
8L
8)n
and Agg and Ag are positive constants independent of n and K. Then, for K 2 1, the algorithm converges as:
E [
0
4 Ag K
+
+0 K (<) + + +2
(94)
K
where A3 = (x(x))
+ Pk I1y
y0
+
Qx ||
-21
+ A BED
B&
Ck |BD and Pr, Qk, BR, Cs are positive constants. The expectation is over the random- ness of the algorithm.
Proof. To obtain the final convergence result, we build upon the above lemma. To obtain the convergence result we define the Lyapunov function be
L. 1x
P.EEE Ily+
v=1
Q&
|z
2 [1]
(95)
+ A&EE
E(D
B&E I|m
E(D$)11)
+ C.E [[m E(DD)
The coefficients are chosen to be
812 L, Xg
21 Q
8L4
Lg 36I
Lg
Pk
+
A
B
C
(96)
L7>,
36L
36L
By invoking Lemmas 14, 15, 16 and 17 into (95), we can obtain:
Lk+1
L*
1x F
|
2
AgAby P
12 (+ naLg) ) (1312 + +31
+
2
Ti(1)
41

---

Published as a conference paper at ICLR 2026
+3BBB&
(1
1
m + 120x
1+ natig)
n.) (IR + 3322332)
E |lve (xx+))]
Myy Myy
T1(2)
61xLi +
Ag
Qx + 36A
1+ TaLio
Light + 36Ck
(1+ )ott)) Linh
nakly/
||z z (xx (x*))]
2
T2
21x + Av (82 + Lotia) -1)
1) 11 E [|lm B(D
TB
+
Bx (3g + My (1 + 3 - 1) + 12
1+
Ling
Maaling
To(1)
12My Pe
+12Cx02
1+ Maeleg
Li +
E m 31D
>g
T4(2)
12na Qk
Ck (32(1 Lg )1 12 1) 12AM
1
lig +
E
|
B(D
)1
T Matin
Xg
T6
L 2
2T2. vx
21z 1x
+
lxx
+
Qk +
Pk + 4A
(1 Mattg
1.111
(97)
2
2
Ag
dg
Té(1)
+
BBgBy
(+
13g1 + +4Cx82
1+
1
1 12
E |||
my
(2(2)
of
o²
of (1 8)n
A4
3x)²
Bx -3y)
+ +Cx(1 -32)
(1 8)n
(1 - 8)n
||
|| [2] A2nxE
52 27
E
A
For simplicity, we define:
3Cz
96L2L2
241
A
Gy:
(98)
Acy
X211 112
X2
and
3L2 9
91L4 9
A₂ =
Cz.
(99)
4L7
22
We now analyze each term on the R.H.S. to further bound them.
Analysis of the Coefficient for EE ||yx y (x*)) By assuming
Fy 5
na S
(100)
18L
18I.
42

---

Published as a conference paper at ICLR 2026
incorporating Pa = م2 Li
+
242 = C₁
As
L. 3012
and Bs
1
as in (96), we can bound the
Ag
364,
term Ti:
AL
L2
2 12
2
Ti 61x Fly
L1
L3
3L
[2
122
1/2
(101)
By assuming
4 L1 fly 1
I/2
L2
,yy
1xx S
9
fly
(102)
3 L2
9T.2
we further bound the term Ti in the following manner:
[I2 L2
L3
2
Ti S L2 fly
T1
+ 12
3
Li
+ +L
T.7
1/
+
12
1/2
(103)
s 61xL2
1i S O.
Analysis of the Coefficient for EE Under the assumptions that,
Zzz z" (x*)
L3
1/x S
6T,1 lla
(104)
and incorporating A = Ck following manner
Lg 361.
and Qk
8L
as in (96), we further bound the term Tg in the
T
4L1
2L
2L
L L 1/ S 0.
T2 = 617 I22
L
1)2
L
12
2
+
L
S 61 I.3
(105)
Analysis of the Coefficient for
||
E ED
We analyze T3 by rewriting it in form that separates the contributions from the momentum parameter Ox and the step size ys:
T3 -mx A (32 + LgTi)) 1) - -1- + Th (2 BgCg
(106)
Using the fact that 82 < 1, and incorporating A₁ = 362,
Lg
as in (96), we bound the term Ty:
Lg
((1 12
72L?
Lg(z) )) = 0.
T3 - -1- (1- + nx (2 82 LL <
+ 17x
36L
Lg
(107)
where the equality uses
72
1 - 32 = T/x
1ha l.g.
(108)
Lg
Analysis of the Coefficient for E
|| - E(D
We analyze T4 by rewriting in a form that separates the contributions from the momentum parameter By and the step size Ty:
12
Ta = -1- (1-57) Bx + ny
(7g
Pk 4Bx + +3B
(109)
12 (1+
1
I2ply + 120
1
natzg 1,118)
+ +1y
Toalg
43

---

Published as a conference paper at ICLR 2026
Using the facts & P2 I 1, ?y: can bound the term T4:
S
1
Ak Ck
Lg 362;
and BB
1
in (96),
184,""
361,
T4 L
1
-
D + fly
432Lg )g
Pe. + 61.g 241.9 Sx
))= 0.
(110)
Cz
Here, the last equality follows from
432I.g B(D
1 By "/y
Ps. +6Lg) + 24
(111)
Ag
Analysis of the Coefficient for E
||
We analyze T3 by rewriting it in form that separates the contributions from the momentum parameter 3e and the step size f/2-
12 Qx A
T3 -1 - 1--2)
(2) Ck + 1/2
13Cx + 12C + A + 12
(112)
Using the facts B2 < 1, 1/2 S
and A =
as in (96), can further bound the 3627
Ly
187.."
term Ts:
Lg T3 S 36L2
(-(1- (2) + 122
43213
Qx + 14Lg 121.(x) 0,
(113)
where the last equality uses
432T2
82 1/2
Qk 26Lg)
(114)
\ggLg
Analysis of the Coefficient for EE Under the assumption that
[3]
1
1/2
Tx I
fly I
S
5
1xx S
8L
18L'
18Lg"
16Q L
32
16P L.
Ag
Ag
g
(115)
and incorporating A = C₂ manner:
Lg
and B₁
1
we can bound the term Ta in the following
361,
361,''
1x
1x
Tx
212
22
1
4
Te
Q
+ Pk
0.
(116)
36
AgT2
AgTy
187y
977
Next, we analyze the variance-related aggregation error in Lemma 13, using the chosen momentum coefficients in (108), (111),and (114). We start by analyzing the relationship between the momentum coefficient and 7x-
(1 82)2
14413
2
(1 3x)
I (1- (1- <
+ +c2Lg
1/2 = Li3 nh
(1+ 8x)²
Lg
(1 - Rg)3
I (1- BB) ((
433 (/gg Iig)
2 cy 24czL1/
(1 3
Pt + 6Lgg)
11x L3 nb.
(1 + By)²
Hg
[1 82)2
432 (Mg Lg) L3
(1 8,)²
< (1 8203 <
Qi + 26L,
2 L3 Txx
(1 + 82)2
Mg
(117)
44

---

Published as a conference paper at ICLR 2026
Based the above analysis, we proceed to examine the terms in Lemma 13. Observing that 1- g I+3 [I+3)² X - 8², combined with (117), we can derive an upper bound for the aggregation emror associated with the parameters x, y, and z as follows.
For parameter y, have:
B
|| S 3 the (1+
1 (1 8)m
0² +3xC3.
(118)
For parameter we derive:
E [|s* S GxL88 the (1+ 11+ (1 -)m
0² + GnLG 0² + GGxC7
(119)
Similarly, for parameter z, we have:
E
c
I 6KLg, Txx
1 (1 5)m
0² + GRLzp²
2 + GnC7.
(120)
These bounds highlight the influence of the momentum coefficients Bx. By. and B2 on the variance- related error terms. By appropriately selecting 3 + 1, the impact of the variance terms o² on the aggregation errors can be mitigated.
Combining the above inequality (103). (105), (100), (112) and (116), we then drive the convergence result. For simplicity, define:
Ao = Lg
12
12
L
(1 +
(p²)
+
(121)
36L
36L
3cx
96L2L2
24L
A
+
+
Cy+
(122)
4cy
XZL1
X2
313
96L
A2 =
4L3
+
XgL3
C21
(123)
As (6(1 + + + +1A211 + p3) +3A1
(1+ (1 8)n
1
(124)
A = 34, + (6.4, + +bpp²
(125)
and
As 6A2
(126)
Thus, substituting the above inequality into (97) and combining the term Ao. A1. Ag, As,As, Ar As. we can obtain
+ A (1 8)n
Cx41-Le 11i1-655 L
Tx E
V (x]
+ n2nAgo² (A1s) Ast7) nxx-
2
(127)
Rearranging the term in (127), we can obtain
1x E V ||] s Lxx Lx+1 + Ago nx 2
+ xx (A1C, + Ad The
(1 5)n
(128)
Analyzing Co - Lx. Recall the definition Lyapunov function in (96), we can obtain
Lo Lx 5 (x)) Ph. I|y -y01 Qu ||z| - - 2
(129)
AA m E(D {
||
B& |mmm E(DY 111 C Ilmm E(D
45

---

Published as a conference paper at ICLR 2026
Using the definition of momentum in (91) and set the initial momentum my 0, obtain
m ( = [| - V" - E(DD)) |
(130)
Under Assumption 3, we have
[|V,G(x,, = B(D)), E v -
N s02/(1 - (1-
Thus, we can obtain
o²
my y
E(DS) [|] = = - By)²
+ 2 Vyg(x) y0)1
(131)
(1 -1- 6)n
using inequality (117) and 18 < 1, we can obtain
E m E(D ) - L3, nh (1- -)n
+ //gggxx),") x2)
(132)
We can obtain similar results for x, z.
of
|| - E(D
$ L33 ux
||E
(133)
(1 8)m
and
E | EDD |||
< L3,12 1x
of
+
|(DD))
(134)
(1 8)n
Combining the above inequalities, we can obtain
Co Lx S 4 + 2x (1-8)m 8)m (11 (1 +CL())) - B,,
(135)
For simplicity, we define
A = (x (xx) + Ps 115 y21 + Qx |z - 2
(136)
+ A B(D || + B& |[D C |E
As the above inequality (128) is true for an arbitrary & E [K] by taking summation on both sides
K - 1, and defining A, (AAe +CxL B 0² + KASO
from A 0 to k
(1-8)n
can obtain
K
A (2 + AonaK) + 2 2 + kmA((K))
Σ E
[
(x*) [1] <
(137)
17x
k=
Dividing both sides by K, we can obtain
1
Σ (xx) 1|]
A
Aotle + 2 mAA57))
(138)
K
7xK
Final step. Recall that the step size 7/x satisfies:
A
1/x min
01,
KA
where
1
A/ = Ao + (1 (1+/) ++))( + +C2
+ BaL
A.
+ 2 ai
8L
(139)
46

---

Published as a conference paper at ICLR 2026
This implies that
1 max
KAa A
KAg
S 8lv0 +
(140)
V
A
7x
Consequently, using this upper bound for in (140). we can obtain
1/x
8L
4,41
Σ E
2
+21
K
(141)
+ 2x (Ar
+ Asc7))
This simplifies to:
K Σ 0 |
=0
A K
+
4
+0
k(C7 + (
K
(142)
Finally, x(() u1xx0 (1)
(1)
K-11, combing with (142), we have
A
A A
+ + (.0))
E (x))
= 0
+
+0
n²{{
(143)
K
K
Hence, the proof is complete.
47

---

Published as a conference paper at ICLR 2026
1 CONVERGENCE ANALYSIS FOR BR-FEDBIP (THEOREM 4)
I.1 PROOF OUTLINE
Our convergence analysis for BR-FedBiP in Algorithm 1 similar to BR-FedBiM and BR-FedBi, the only additional lemma that we have to prove is the deviation of PAGE (Lemma 21).
Notation. Recall that for each iteration k, each malicious client send well-craft malicious gradient, and each honest client computes:
x, = (V Gizi op. :4.) T of Φ.),
y. TV G upt :p)), y. TV<VV Giz; spf (pf) (V oi Φ.).
where u² = (x", , ) and we define the operation Te
(zb: = s (u*: 1) TT-- + +b (u*;b) + (ut;b), if c 0.
if Cx 1,
The server receives the gradient from the clients and performs robust aggregation methods (.G
AGG(v x,n)
= AGG(V yy r.a),
= AGG(V 1.... ).
1.2 AGGREGATION ERROR
We define the aggregation error as the deviation between the robustly aggregated gradients and the average gradients of honest clients. Specifically, the aggregation error is expressed as:
2x = k
y
<² v
1 where vx = [7 EIEN
v 2,0
vy
1 गM
EiEN v and v
1 [म
EiEx v...
The detailed proof follows a similar approach as that provided in Appendix J.3.1.
Lemma 18. Suppose Assumptions 3 and 4 hold, and the robust aggregation rule AGG(.) satisfies the (8, -)rrouustsssss criterion. The aggregation errors in the BR-FedBi algorithm (Algorithm satisfy the following inequalities:
(1)
|| 11 < 4nl2 + 4k
11
(1 -
8)n
(2)
[||
< 8k (p25) + (7) + 8x 1+
o7,
(1 8)m
(3) ||]
< 8x (p² 22 + ( + 8k
1
0
(1 8)m
where of = (1 + 0² and Ct
I.3 LOWER-LEVEL CONVERGENCE
In this subsection, analyze the lower-level convergence behavior of our bilevel algorithm. Specifi- cally, we examine the distances between " and yh, as well as yh and z The proof this lemma is similar to Lemma 14.
48

---

Published as a conference paper at ICLR 2026
Lemma 19. Under Assumptions 1, 2, 3, and 4, and assuming my S min sg noth, } and
1
Th min Ngo m }. the following holds:
(1) [[y yx
-122-1++111 11] =
1 1g 1gllg
E [|1x* 1oyn-y- -y+19²
Fy E
( [1]
2 (1g + Lg)
NgLo
12 (1gg Lig) Vly
E ||v - + + |||$* ["]]
MyLg
2 (1gg + [ng) Tz 18x
+
E
|
Mggig
(2) B B11 2+
11] v
1
Hg
E
|||2
T E ||E(D!))
2 (1g + Leg)
1 و
12 (1g Lg) 1/2
E [1lv2 B
+ E ||E*11] 1))
Mg L
2 (Mg + Lgg Li 15x
| ||
+
M4 40
1.4 GRADIENT UPDATE BIAS
Next, we analyze the gradient update bias of BR-FedBiP in Algorithm The proof details of this Lemma are similar to J.2.3.
Lemma 20.
Suppose Assumption 1, 2 and 3 hold, if 2 Cf/Mg we have:
E |QH (x*)
v²1 6T.2
||y* y1
+ 6T. B
21E || E (D
where -3 L7 + Lzp2
1.5 PAGE DEVIATION
Next, we study the deviation, which is the distance between the average PAGE gradient and the true gradient. Proof of this Lemma can be found in J.3.2.
Lemma 21. Suppose Assumption 2, 3 and 7 hold. Considering Algorithm BR-FedBiP in Algorithmm 1, we have
(1)
E |
k-1
EDD
E
+
$ |||
σ²
+ (1 - p)
|/ ||*
8(1 6)n
(1 - p) 1.2
1
EE ||
+ 3
[| E (D.) [1)) If')
(1 p) L3
||x*
+ 33 [|5st 2))
b
49

---

Published as a conference paper at ICLR 2026
(2) E [[ k+1 E (Dx []a]
of
+ (1 PP) [[] x - 11 + (1 (1-1)) E [1
P ((1 8)n
b
+ 12 (1 (1-P)
1, [B [|K$]] [1] + E [|v] - E (D |1 + L3 [lly* - -
6
12(1 - p) 12 (T
[1st1]]] E [| - e (D 1r])
b
12(1 - p)
12 (31 [1|2* - 2 + +32E [|lx* - -
b
(3)
[[|v2 k+1
EE (D*+
of
||| - B(D 12| + (1- p)
12 [|0211]]
$ P (11 8)m
+ (1
p)
b
+ 12 (1 - p)
1
E
[|S$
2
+ E [ E (Dz))
[1²] |1
+ 1. [|ly - -yt1191
b
+ 12(1 - p)
22
[
[|<tt]]]
+ E
11v2 E (D+) 11]
+ +3L |||2* 221171)
b
12(1 p)
+ b
L n2 (3LIE [1y** -x
1.6 DESCENT LEMMA
In this section, we analyze the progression of the upper-level loss function in BR-FedBiP as described in Algorithm 1. The proof this Lemma is similar to Lemma 17.
Lemma 22. Assuming that the upper-level loss function 2x((-) is Lva For each step k E [K]. we have:
E De (x*+2)
S E [
(x*)]
Txx EE
| (x*)
[x]
4x
)E
2
2
2
| (x*) v²11"]
||55
+ BBB
+ 7/ E
1.7 PROOF OF THEOREM 4
Theorem 7. Suppose that Assumptions 1-4 and 7 hold, and that the robust aggregation rule AGG(.)
satisfies the (6, ro)-ruuustssss criterion. There exist positive constants c, Cy, and C2 such that if
Mly Cy
1/2 C2Nxx
and step size The satisfies,
1
7x < min
8LV
1 v
1-2
bp
the algorithm converges as
1
1-p
o
[[Vxx())]] =
pb
+
K
Kpl/
V 8)m
(144)
+ (K (cg + 2yp²
+ 2 + o2)),
where the expectation over the randomness of the algorithm.
50

---

Published as a conference paper at ICLR 2026
Proof. We consider the Lyapunov function
L (x() + E
||y - yfll
11
+ E ||
2
11]
+
Tx E
||
E(D
||]]
P
(145)
1x E || E(D ||]
Tx
||
E(D
Using above equation (145), and Lemmas 19, 20, 21 and 22, we can obtain that
L
Lx
T1x E2
4 (x [x*)
4
+
3121xx
AgTly
+
3(1 p) pg
24(1 p) 7x
72(1 p)
E -x+1
2
bp
bp
bp
T
+
31
Ag 2
72(1 p) nx
|| - 2²11²)
bp
T2
E ||v [1D
1xx
+ 17x
12my
3(1 - p) 1)
24(1 - p) 12 Txx
E 11v B(D})) >1 |2]
17x +
+
Ag
bp
bp
Ta
127zz
24(1 p) 12 T/x
E 11v2 11
1/x
+
+
Ag
bp
1x
2
212. 11x
212-112 12x
(1 23
8(1 - p) Li
[| | 21
+
+
+
+
4
4
Ag
7g71a
bp
bp
Ts
120y +
3(1 p)1
24(1
p)
Li
|
+ 1x
17 +
fre
Ag
bp
bp
+ 7xx
12cz
12(1 - p) 12.22
n
E
ck
7x E
||E$*
[*]
Ag
6p
2
g2
of 21/x 8( 8)m
+ 1/x
V((1 - 5)m
(146)
Under the assumptions that
4bp
bp
S (1 (13 + 817)
S
(147)
[1 L2
and invoking Lemma 18 into 146 we can implies
Ck+1
Lb
1/x
| (x*) [x*)
E
4
+
3L311x
Ag +
3(1 - (1-p))Lan)
24(1 D) Tx
72(1 - P)L
E -
2
bp
bp
bp
51

---

Published as a conference paper at ICLR 2026
AgTl
72(1 - 1)
||2| - =+11²²
+
2
bp
1/2
||v [[D
7/x
+ 1/x
E
12ny
3(1 - p) 13
24(1 - p)) P) 1/
|| B(D))) [
1/x +
E
Ag
bp
bp
1a
127
24(1 p)
23 T/x
E ||I22 E(D
+
- +
+
Ag
bp
T4
1xx
L
2
2L2.
1
213
(1
D)Lg3
8(1 2
[| [|]]
+
+
+
+
+
4
4
Aggly
7g
6p
bp
Ts
960y +
192cz
(192c= +
+4 p²)
C3 NITLL +
2g
Xg
Agg
1920z
96cy
1
+
(1
p²)
+
|+
0² 0²
Xg
(1 - 5)n
0²
o7
+ 7x (1
27x 61(1
(148)
8)n
We now analyze each term on the R.H.S. to further bound them.
Analysis of the Coefficient for EE [|y** yt]l"]]
Due to the assumption that
22 Xg 4A7
1/x
12L3
A A}= = (31g/2 + 24T2 + 12gy + T21.g
(149)
we can bound the term Ti in the following manner
Agnyy +
3(1 n Tx
24(1 - 13 72(1 - L3
Ti < 3L2Txx
bp
bp
bp
Ag
(1 p)
< 33221x
+
nx (3L + +2AL3 + L3 + T22
(150)
bp
Xg
AgTly
< 33
0.
4
Analysis of the Coefficient for IE |1 - -111
Due to the assumption that
An
Xg 288L3Ca
1x <
o² S
(151)
12L
we can bound the term T3 in the following manner
Aglle
72(1
L3
AuT1e
AgT2
T/ = 3L
2 +
$ 3L
+
< 0.
(152)
bp
2
4
Analysis of the Coefficient for E [Ive - E(D
52

---

Published as a conference paper at ICLR 2026
Due to the assumption that
Ml S Mg 1g
c² Σ 2 (312gg + 24L2(²)
(153)
24( + Lg)
we can bound the term T3 in the following manner
T3 1/x 12my
24(1 p) 3(1 -p)
bp
bp
(154)
12tly
(1 (1- p)
lxx (3L3g +24L7G) 5 O.
1/x Ag
bp
[1v2 11
Analysis of the Coefficient for TE
Due to the assumption that we can bound the term T4 in the following manner
AgTle
1/2 I
c²
(155)
24
24 g
12
12(1
p) 12
Ta +
1xx
+
S 0.
(156)
Ag
bp
Analysis of the Coefficient for IE
[111
Due to the assumption that
7x
à² <
1
(157)
L-P
16 (T2 + 8T,7)
hp
we can bound the term T3 in the following manner
Txx
L
2L2. n²
212 2
(1 (1-P) p) (L 8L,)
TB =
+
+
+
4
4
Ag
Ag
bp
(158)
?xx
L
2 2
2L2 2L2
Txx
+
+
4
4
Aayyy
Ag12a
16'
Due to the assumption that
Ag fly
Xg 1/2
1/x
1/x S
Gx S
(159)
8T
32T
321,
we further bound the term T2 in the following manner
1x
L
n
2T 2
1/x < 0.
To
(160)
4
Ag
AgTla
16
Combining the above inequality (150), (152), (154), (156), (158) and (160), we then drive the convergence result. For simplify, define
Ag = 1 + 2(1+
(161)
((100 (192c= +4 4
(1+ (1+p?) p²) 96cy ) (1 (1- 8)n )
A1 =
(162)
Ag
X
96c,
1192c
A2
+ +4) p².
(163)
Ag
Ag
and
192c:
A3
(164)
Ag
53

---

Published as a conference paper at ICLR 2026
Thus, substituting the above inequality into (97) and combining the term A2, As, As, obtain
Lx+1
Lx S 1xx
E
(x*) [19]
4 +
o²
(165)
Ao 61 8)n 1 + RAAI + K.A2bbg + RASSsbs.
Rearranging the term in (165), we can obtain
Lk -
Lk+1
0²
E V (x*) ||] <4
Ao
8)m + =AA + KA2S + KASS))
(166)
b4 As the above inequality (166) is true for an arbitrary k E [K], by taking summation on both sides
1
from t k K and Dividing both sides by K we can obtain
P (x [x)])] 34
Co
LK
o²
+ KAjo² + KA222 + nASS?)
E
Ao
1x
6(1 8)n
K=
(167)
Analyzing Lo LK. Recall the definition of Lyapunov function in (145), obtain
4(xx)
Ox
Co LK S 2
|1y0
y
+
E ||
2011
+ pb - 8)n
(168)
Final step. Recall that the step size satisfies:
Tx min
Bly
Cylh:
1/2 Callx-
(169)
1-p
SLV0
Combing (168) and (167), the iterates satisfy
1
k
| (x ||]] 00
(x+)
pb
o²
E
+
+
K
K
Kpb
8( 8)m
(170)
k=
+0 (N (Sa + Cgp
+ 6 + 0²))
Finally, as x( ~ u1xx6 (1)
,..,,
x 1 we have
1-2 pb
o²
[[ =0
+
K
Kpl/
V 8)n
(171)
+ (K (Cg + 22p² + 2 37+ + o²)).
Hence, the proof is complete.
Corollary (Analysis for sample complexity). general expectation cases, choose b' min! { o² N M where N and M the number of data points of upper and lower-level problem. If + M is very large, then b' O(c In each iteration, it uses pb' + p)b samples on expectation. Let p _ b' O (5-1) and b S vV. Then the number of iterations performed by BR-FedBiP sufficient for finding c-approximate solution in the general non-convex case can be bounded by
Vb +
8 +bb
))
K K-O
c-
1+
(172)
bb
Thus, the total sample complexity is
K (pb' + (1 - (p-}
b' bb
2bbb
0
-1
1
b
bb
(173)
=0 (VDc-) 0 (c.1.)).
54

---

Published as a conference paper at ICLR 2026
J PROOF OF SUPPORTING LEMMAS
J.1 PROOF OF SUPPORTING LEMMAS FOR BR-FEDBI
J.1.1 PROOF LEMMA
Lemma 9, Suppose Assumptions 3 and 4 hold,and the robust aggregation rule AGG() satisfes the (6, k) robuustesss criterion. The aggregation errors in the BR-FedBi algorithm (Algorithu 1) satisfy the following inequalities:
(1)
E |||
S NG KO²
[+ (1+ (1 -1-00 8yn
1 )
(2) E |||+||
s 2x (p + (7) 2no2
11
1
(174)
(1 6)n
(3) E ||
$ 2x (p2c² + (7) 2no
1+ (1 6)m
1
Proof. Now we analyze the aggregation error of and under Assumption 4.
Analysis for IE
ck Sy
Recall that
$ DJ -D.
For an arbitrary step l > 1, we obtain that
D
y
Σ
E
D y, - D 12]]
(1 8)
iNN
k
E
9 (x+ v*) - Vyg(x", w²) + Dÿ, 1x(x"" + V. Vxo(x* .x D311
8)m
EE
yy (x* yt) Vyg(x" (x((x">"')1" -+)1|]] + to² (1+ (1-8)) 8)n -mm))
E
(1 8)m
icH
K
2 + o²
1+ (1-6))
1
8)m
iEH
< nnG + NO?
(1+ (1-
(175)
The first incquality holds due to the (8, robuusttssssss of AGG(.) defined in Definition 2. The third inequality is obtained using Assumptions 3, 4, and Lemma 7.
| Recall that
Analysis for E
$ = -
For an arbitrary step > 1, using the Definition 2, we obtain that
E
D
D
K
Σ E
||
(1 - 8'm
iEH
k
[[I (x* 2t VxJi (x* (x*. -2y ) 2t
(x
(1 8)n iEM
+ tof
1
(176)
(1 - 88y
55

---

Published as a conference paper at ICLR 2026
Using the Cauchy-Schwand inequality, we then obtain that
2
E
D
x
2k
Σ
E
V2 Xy (x²,
22y0 (x* (x*,)")]] |||]] || 112
(1 8) m
EH
2x
[1V (x*, ,²)) Vx yK) x+))))+)))1 ||
of (1 I+ (1 ---0m)
(1 8)m
iEH
1
K
Σ
2p Sg + 26 + 20? (1 (1 - 8)n
1
(1 8)m
EEH
SK K (2p + 2(7) + 2kO (1 (1
1
(1 8ym
(177)
where inequality is derived using Assumptions 4, and Lemma 7. Analysis for E
[ Recall that
D -
For arbitrary step l: > 1, follows Definition 2, we obtain that
E
D D
E
D
D |
(1 - 8'm
iEH
K
[ by (x" x²") 2" + Vy (x*, (x",y*) Virg (x+ (x²) z== -Vy Fxf(x" 1111
E
8)n
EN
+ of
(1 8)m
(178)
Using the the Cauchy-Schward Schwwrz inequality, we obtain that
E
D k
D
2k
2 by (xe x²) - Viyo (x" .x ||3 ||2212
(1 8)m
icH
2k
V Fy fi (x*xx*) Vyf(x*,, + of (+ (1- (1-8)m)
+ (1 8 n)n
(179)
icH
20 26 + 20ी (1+ (1 5)n
(1 8)m
ieH
1 1+ (1-11))0 8)n )
S (2p 22 + 2(7) + 2
where the inequality is derived using Assumptions 3, 4, and Lemma 7.
J.1.2 PROOF OF LEMMA 10
We now restate the Lemma 10 and present its proof.
56

---

Published as a conference paper at ICLR 2026
Lemma 10. Under Assumptions 1, 2, 3, 4, and 5, the following inequalities hold for y and z:
(1)
I3 | x+1 - -y-+-1111 y1+
I (1
"lylkg
+ +21 1B ||x - yt [|] + (3ng +
My )E 2e
|| 1 |
4
+ (6L 2/x +
4n2 ) E [ +
19] + E [||S 11 ")
Tyy
0²
of
+ 211 2
+ 3lyy 11x (1 8)m
(1 - 8)m
(180)
(2) 16
2 ++1 +
++++11" 11(]]
1 Tafta
+ 61 1/)
E || - z-11²] + (ATLL + on
E I1yy - yx |?]
2
Mg
4.g
rix + 4 4l2z211
+
4 1/2
EE
B(D x |9] + E [1|$211]
Pall'g
+
30/ +
21/2
E
|||5%]
27
+ (2n + 4T2 2/x + 4L:z2p1))
of
(1-8)) 8)n
Mgg
where yh (xx",, and zt = z² (x*))
Proof. Inequality for y.
We first separate the E ||y - --2+111 y1+ into five parts. Due to iteratively updating y k+1 we have
E
||y
x+1
y 11
E
k+z y |1]] 1
+ E
1 k+1 y 111
2E [(yht2 y y xkt1 - y
x+1 - yx ||]]
||y k+1 - y11
2E [(y* - -hi,htt xt1 - y + 21yy IE ( (D (D
yxt1 ( y1
E
+ EE
E
||y k+1 - -xall ||?]
+ EE
||5 ++ - y ||]
- 2E [(y+ - -y Vyy* (x*) (x+t1 - -x1x) x())]]
2E Ky* y yt yh Vy (x*) ++1 }}} + 2ny (DD y H+1 - yt)]
(181)
where the existence of Vy (x*) is guaranteed by Lemma 4.
For the first part in the R.H.S. of (181), by the Assumption 3. Dÿ is the unbiased estimation of B(D)), then have
++1 11]
l Tyy D - y
[(x y. - ny vyge) - "Ty (D) Vro+) )19
E
= EE
|ly : - 11y Vy. $ |2]]
fyy DD - Vyg²) 11] 21yyE ((r* - y - my Vyg", Db. Vxgg)) }
E
+E
||y k 3 - my vyg* |1]]
n/ (DS. - vyg*)
17] 27 K-x-- - y
myy v Vyg" Dτ -D&)
< E
+
< (1 H,, 2
||>*
||]
+
E E
(D) Vxgg
[|]]
2 ((s - Fy v g k D D }
(182)
The first equality follows the unbiased estimation of D in Assumption 3, and the second inequality is derived using Lemma 6.
57

---

Published as a conference paper at ICLR 2026
Then, using Young's 's inequality 2(a, b) - ca² + bb,,, we have
21yy F. Ky*
y
fy Vxg" D D$}
- MyHlg |1x**
2
Ty (1 - By Mn) b
||E$]
y fyy V Vyg
+
(183)
nybgg
Pg
- My
MyHyy] )
||y*
x=1
fy (1 my E
|||
Fgg
where the last inequality is derived using Lemma Combining (183) into (182), and use the Cauchy-Schree -Shhwaz inequality, we have
E
| - v41l"
S (1 nyHgg) 2 ||y* -1 -+1l + +n
(DB Vzge )19
(184)
+ my Mo (1- My )E ||1x* - y² 1²]
My (1 My ||L$ |
Hi
2n5
s (1 - ny 1|y+ - 111 fly
||
+ (1 5)n
Fy
For the second part in the R.H.S. of (181), using Lemma 4, we can imply that
E ||y +
y=1 S Lg. m
D
(185)
For the third part in the R.H.S. of (181), using the fact that D is the unbiased estimation of (D))) we have
2E [(x+ yx, Vy* (xt) (x*+1-x**) x+))]
21 EE [(y y Vy (x*) (D& + {
2 IE (yy* yh, Vy (B(D** )
(186)
s 2
P ||1x* y 4n
r F
|| |2]
4 Izy. E ||
TyHig
My
where the inequality uses Young's inequality that 2ab S a + cb and Lemma 4. For the fourth part in the R.H.S. of (181), using the
inequality, we have
2E (y* yt y k+1 yt Vy* (x*) (x*+1 - x*) - 2E ||y vill ||y yh Vy" (x*) (x+++1 - x*)
Then, using Taylor's expansion, and Lemma 5, we have
2E [||y - - !|y yt - Vy* (xt) (x - -x+)
s LyxlE |||y yه ||x - x*11
(187)
Further, applies Young's inequality 2ab < La + cb? we have
T F.
[1xx
||* k+1 x [|a]
1
F.
[|1x*
- - ||
- x ||a]
+ T22. EE. [|xA+]_x*11
- x*11"
412.
12x211
yt1l || E + 27
[||y*
+ T 2
D
(188)
4T.7..
58

---

Published as a conference paper at ICLR 2026
Then, using the following inequality
D 2
x + + ||
D 6 x
= =
- 2E
| D 21
11
+ + ||
[ 21
| -Dx D 22
s 21
+ 2B
0²
$ 2H + 2F
||< 27
+
I 2H
(189)
(1 8)n
where the third inequality uses Assumption 5 and we define H2 follows
H = H + 2n(C2 + (7) + 2not (1 1+
(1+ 8)m) + o²
1
(1 5)m
Polg. Bly 21 HgT we can bound the fourth term in the R.H.S
Finally, choosing the learning rate that 1/x S of (181) as follows
2T [(y
y
y++ - y Vy" (xx) (xtt1 x())]
(190)
He ||yy yx 12] + Lz. 121 | [3]
(191)
For the fifth part in the R.H.S. of (181), by Young's inequality and Lemma 4, we have
B (DI. y y4) s E
|
||
12
|
27
(192)
By substituting the above inequality into (181) and use Cauchy-Schwer inequality and Lemma 24, we have
E
||y
y 11
+B 4n 12y. ([ [[E[D +B [IsE(())) (193)
$ (1
17ylg ) ||1y+
-11 + 6IZ. +
Ty
of
+
T3
[1
+
ny
+
| |
3 17 (1 - 8)n
Pg
By substituting Lemmas 24 into equation (193), we obtain
E
k+ - - 11] S (1
TlyHg
+ 21 1
[|xx
- -/-11²]
+ (3ny
+ Ty ) Bgg
[|s$||]]
2
+
61 6I2 12
1z
E ||E
+ E [T
(194)
TyHlg
d²
of
+ 2ny
+ + 3L
2
8)n
(1 8)
Thus, the proof is finished.
59

---

Published as a conference paper at ICLR 2026
Inequality for z. Similarly, We separate E
|||-
2x ++ [+]] into five parts. Due to iteratively
updating 2++1_ wwe have
++ x +
E
E
k+1 1|
+ E
k+1 211²]
2E [ (+1 2 x+1 - 211
|| k+1 2=(1²]
| x+1 =1] 2E (<" z z,:t - 2 + 21/2 ( (D 2, - -2ti
E
+ E
E
|| + <t'1[]] IF
| 2=]]]]
2F [(2 2 Vx" (x*) (x+++1 x*) |]
2F [(zt zt, + 2 2 (xt) (x*t1 x )}} + 27 E
(D 2 - -2t) 2t)}
(195)
where the existence of Vz (x*) is guaranteed by Lemma 4.
For the first part in the R.H.S. of (195), we separate each term and analysis, and we have
E 1 k+
z 21
1ta 1/ (D 2 + (E (D= - D
E
E
(zz zt: 12 2 Voy (z* zt) ztt)
7/ (V gf + Vyft* + (I (D 19
[1(2* z² 1/2 V2 Viyg (z+ -2+) |0] + T || D 10] +1 |1 Vzygrzz + [²]
[1]
E
K(2** -2t) 1/2 V g (2 2,,, E(D - -DA)
(VVyggzz + Vy B(D+) - -D²)
((V x Vy (z+ z. - 1/2 V (x* z)))|----
(196)
Then, we start to analyze the last three terms the H.S.S. of (196).
For the first term, using Young's 's inequality 2(a, b) S ca + 1²² and || T 1/2 V we have
V3
S
Bn ((( - -2))= 1/2 V2 Vorg" (z* 2,),E(D) k) - -D
B [|(eet -xt)== 1/ V2 Vzyg" (zr - 2t D D
S 2(1 1/allg)
Mally
E.
[||(2* 2 - 1/2 Vry (z" - -z") [|] +
2/7z2 (1
121 1 )
|| 1 2
(197)
Mally Taaklo
E |||2* - _ [1]]
27/2 (1 - 72b )E |||c$| 11 ||]
2
Ug
where the two inequality uses Young's inequality, || 1/ gygg *1| S Mally and Lemma 4. For the second term, using the Assumption 1 and Cauchy-Schwarz inequality, we have
E vy
V2 o + ( )1" 22 + Lipp²) E [1xx y6 2
1-1 (198)
Then, using (198) and define L3 == I + I p2p², we obtain that
- ( ( : + Vy D D:
(199)
< 2n 13 ||y y || 27
where the inequality uses V2n + Vyst
0 and unbiased estimation of D
60

---

Published as a conference paper at ICLR 2026
For the third term, using Young's inequality 2(a,b) S ca² + 2² and || The V vy $1 11 7zllg we have
2 (KV (f f4) (z =²t) 1/2 Viy (z* -zt))]
Pally
[11(** =z,)== - 1/2 Vz (z" -z+)| 11
2112 (1 - 1aHkg) || " + V. 1011
E
2(1 ((llgg
Maayl(1 (1
|| z=11" + 11 (1 Matly ) |||x** - yz v211"].
E
M4
(200)
where the two inequality uses Young's inequality, ||+ - n2 V v S Mally and (198).
Substituting the above inequalities in to (196), we obtain that
|| k+1 - 2+1 ==]
E I1ae - -2, 11e V "y (z+ 21)1
+ 1
[V by 22 + |1]
+ +
B (D+) 1
+ (1 Tally) (all |||2 -22.1 21]
+ (2
7/2
n E
|x 2
+ (2
The
n 2L
||yx y 12)
14g
Mg
$ (1 1F | [1]]
+
4 L3
||1y*
- y. 1²]
+
1/2
21/2
E
||<t 27
Mg
1g
(201)
where the second inequality uses (198) and
1/2 V yyg gM S 1 -
Talg
For the second part in the R.H.S of (195), using Lemma 4, we have
E
k+1
2t. 11]]
< L2 1
D
27
(202)
For the third part in the R.H.S of (195), using Young's inequality and Lemma 4, we have
2E (x2 zh, Vz" (x*) ) (x - x()>
2E [(zz 2 Vz (xx) (D <
(203)
- 2
Wallg E
|z =11 + 4nk L E
[|B(D*)
+
4n
L2
[|]
Tap
Tall
where the last inequality uses 2ab S La² + ct² and Assumption 3. For the fourth part in the R.H.S of (195), we have
2E (z* 2 2 k+1
- -iz (xx) (x++1 - xb)>
s 2E [||e* - 2 ||2 - 2 Vz" (xt) (xtt1 - x+) []
< Lux E |||2* z || - -x!11 [|]
(204)
|| < 2
|
The first inequality is derived using Cauchy's inequality. The second inequality is derived using Taylor's expansion, and Lemma the third inequality uses the boundness of z, ||z]|| S p.
For the fifth part in the R.H.S of (195), by Young's 's inequality and Lemma 4, we have
2n F
(D k+1
2
E
D
2
+
E
D 27
(205)
61

---

Published as a conference paper at ICLR 2026
Combining the above inequalities and using the Cauchy- Schwarz inequality and Lemma 24, we have
|| ++
x + 2
I (1
T IE
|| 1
2111²] +
4r
13
E
||y* -
- x11 + c +
2//x
E
ck $2
21
2
My
Mg
+ (4L2) 1/x
2 +
4n 1xx))
[E
[(D )11
+B [||=||0]
|
E
[|12*-
2+11?]
+
AneLi
6n L3
E ||y* x31
[||2*
2
Mg
AT.2. 11x + 4l.20
4 T.g.
[F
|
[1]
+ E [|s$1]]] +
/31/
21
TP
|
1g
09
+ (2n + 4L2. R2 + 4lgz)11))
(1 8)n'
(206)
where the second inequality uses Lemma 24.
J.1.3 PROOF OF LEMMA 12
We now restate the lemma 12 and present its proof.
Lemma 12. Recall that the upper-level loss function is L smooth,, we have
E P (x*+))] s E PH (x*)]-
1xx
(x*)
||
T2 E [Qxx(x))
- E(D ||]]
+
4
2
+ -
1xx 2
E
E ||ECD IP] + (41x L
|| []
+ LV4
(1 - 8)n
(077)
where of = (1 + 0²) 0².
Proof. By using L smoothness of upper-level loss function DD, we obtain
E Dee (x++))] S E DH (x*) } + E [(V (x*) x*1 x* +
Lv IE
||x
[xxtt _ x* x²]
(208)
b+1 x -1 D T and Assumption 3, we obtain that Using
L
E DH (x*+t)]
< EE D (x*) | B (e (x*)
D
E
D
2
TE p (x+)) 1/x E
(V (x*)
|
L E
D
22
S E. T (x+) F ( (x*)
(ED }
E ( 4 (x*) | +
2
|
27
2
(209)
where the first inequality uses the Assumption 3 that D is the unbiased estimation of E (D+). Using uses (a, b)
[a² + 62 - (a + b) we obtain that
1x KV (x*) |>
The
E || (xx R (D || E [|V - -[IIE()))]])
(210)
2
Using the fact that 2ab= < La² + cb2 we obtain that
RE [V (xx) , S 7
E
(x*) || ||5
(211)
<
7x
E
V W
(xx) [x²)
+ 4 ||
4
62

---

Published as a conference paper at ICLR 2026
Substituting from (211), (210) in (209), we obtain that
E pxx (x
x
E
(x*)]
7x E
[19]
+
Dn E [
E 1|
2
1x E 2
| x 11 11
+ L
| /
22
|| 19]
E
+ +
I E
TH (x*)]
1xE E
(x |1
+
170 E xx** E ED
4
2
7xx Lvon
E
[[((D*)
2
(4nx L E
|| 2
+ 8)n (212)
2
where the last inequality uses Assumption 3 and Cauchy-Schwarz inequality.
J.1.4
OTHER USEFUL LEMMAS
Lemma 23. Under Assumptions 3, the following inequality holds for BR-FedBi:
E(D - DD |"] S
[[|tt|]]
(213)
((1 d)m)
E (D)) D
SE 1E 21
1
((1 - 8)m) of
(214)
|| - D
27
Proof. Analysis for E
We decompose the term into two components: the error
due to the approximation Dÿ and the variance of Dý. Specifically, we rewrite the term as follows:
D 13
D D$) - (D$ - -E( -
E
=
DJ D$| ||/ + D - E(D))
E
E
||
21
(1 8)m
where the first inequality uses the fact that D - E(D = 0, ensuring the cross-term vanishes. The second inequality applies Lemma 7 to bound the variance term
Analysis for E E [(D)) - =
Similarly, we have
[(D*) - D& | = E E
[ D* + (D² - -E(D)) [|]
| D 1|] + E | - E(D
E
$ E
|||*
27
(1 (1-5) 8)n
where the first inequality uses D
EE(D*)) )]
0 and the second inequality uses Lemma 7.
63

---

Published as a conference paper at ICLR 2026
Analysis for (BD)) D
Similarly, we have
E D.
B(D
E
D D
+ (D B(D /(DD))| /
E8
D
D
+
D - B(D |
[=]]]
(1 - 8)n ot
where the first inequality uses D - E(D = 0 and the second inequality uses Lemma 7.
Lemma 24 (Bounded Second Moment). Suppose Assumption 1, 2 and 3 hold, if 2 Cs/Mg. For each step & E [K]. we have:
27
$ 21
||
(D
|1
21E
|
+
of
x
(1 - 8)yi
|
S 21
||y** - v=11²]]
+ 2F
[| 27
+ 2 o²
(215)
5)n*
E
I 6L3E
||y* - - 6LGE
|| - 211 + 21
|| 27
+
of
(1 8)n'
where of (1 p²)
Proof. Analysis for E
We decompose the second moment into two components: the true
gradient term D and the error term & = D - -D Using the decomposition, we can write:
D + D D ||]
E
D x
=
E
< 2E
|
+ 2E ||
(216)
< 2E
| (D
19]
2E
|| 27
+
[1 of
8)m
where the first inequality follows from the Cauchy-Schwarz inequality.
27
Analysis for EE
We decompose the second moment into two components: the true
gradient term D and the error term zý
D Dý_ Using the decomposition, write:
E
D
||]
E | D + D$ |7]
a²
21 [IE (D$)) 1191 + 2E [| + +2 (1- -)n
(217)
21 |11*~ 2E || 2
o²
+ 2 8)n²
where the first inequality uses the
inequality, and the second inequality uses
E
E [D}
= ||V
Vyot < LEE ||y
y.111²]
(218)
64

---

Published as a conference paper at ICLR 2026
Analysis for D
We decompose the second moment into two components: the true gradient
term D and the error term & = D D Using the decomposition, we can write:
E
D
E
| D + D
of
s 2 [||E (D²) 1| + 2E ||5** 22 + 2 (1 - -6)n
(219)
s 6L3B ||yx - y 1'] + 6L23
|||| - 11
2E
||5
2
+ 2 (1 d)n²
of
where the first inequality uses the Cauchy-Schie Schwarz inequality, and the second incquality uses the following inequality,
E
E [D =B [ly (irg( z" + V (z*
z + (Vyf*
3 (T, + 122p2) |||x** -11x*~>x011 --"1'"] - 31.2 ||a zt11 2111"]]
(220)
where the equality in (220) uses gyg + Vy = O.
J.2 PROOF OF SUPPORTING LEMMAS FOR BR-FEDBIM
J.2.1 PROOF OF LEMMA 13
Lemma 13. Suppose Assumptions 1-4 hold,and the robust aggregation rule AGG(-) satisfies the (8, -t)rrobusteess criterion. The aggregation errors in the BR-FedBiM algorithm (Algorithm 1) satisfy the following inequalities:
(1)
||
27
< 3x
By
1+
0² + 3KC2
1 + By
(1
8)n
(2) || "]
S 6x
1 8x
1 (1- 8)n
of + 6R (0²C)) + +(),
I+
1- 8z
(3) E ||
< 6x
1 +
of + 6x (P + (7)
1 Bx
(1 8)m
where of (1 + p²) 2² and p Cf/Pg.
Proof.
Using Lemma 25 and Definition 2, we can finish the proof.
Lemma 25 (bounded aggregation drift). Suppose Assumptions 1-4 hold. For each step k [K], we
have:
By
)
(1
1
E
m
m11
3
1+
02 -²+30 +323
H
y.a
+ By
(1-8)m 8)m
E
m
m!
K
3x
1+
1
o + (p2 +7)
[H||
1 + 3x
(1 - 8)m
3n
E
m|
<
1 |
of +6 6 (0 + +
H
3
(1 8)m
EN
Proof. Analysis the inequality for y.
Expanding the sum in momentum, we can obtain
k
my. = - + (1 - D v.i = (1
(1- - (1-By) Σg
26 D
y.
65

---

Published as a conference paper at ICLR 2026
Therefore, applying Jensen's inequality, write
E
m -0mmmmmml =(1 By)
m
Σ
(D
D2))
71
iCH
iE
S -3
D yi
TE (D
171
1= H
t=1
A
3(1 R
Σ
gh
(D
E
(D;)))
[HL
y
A$
h
+ 3(1- - B
Σ YE
gk y
E
(D y.i)
- E (D
[H4]
(221)
For the first term R.H.S., we have
Af
E
8 (D' - E (D(
E
g (D) - (Dz..)
D y, E (D ()
Σ
3 (D (D$.))
- EE
113
+E [|I
E3 (D (D)) 11]
By recursion, we have
k-2
A < 8 22(k-1) 1)
A
Σ
181
Iml
As | E [ID - (D. (D)
< 2² we can obtain that
M <
22
1 18
1=0
For the second term of the R.H.S in (221). denote
A E
Σ 3 (D) -E())))
Similarly, we obtain that
a²
A <
82) ((1 8)n)
For the third term of the R.H.S. in (221), denote.
A
Σ
2 gh (E(D -E 1|2
H
iEH
66

---

Published as a conference paper at ICLR 2026
By applying Jensen's inequality, we have.
A
E
8 y
| (D (Dz
H
gk-t
E
E
D .) - (D')) 11?
H
1=1
tEH
C
ak-
(22)
(1
By)
Combining the above results, we get
mtl?
EF
iE
1
3(1
)²
(Af + A + -1)
171 SEH
1
0²
0²
C (1 Byy )2
3(1
32)
17|
1
By
(1 - (83) ((1 8)n)
By
$ 1+ By
1 (1 - 8)m
0² + 32
Similarly, we can prove the inequality for x and z following the same proof of Lemma 9.
J.2.2 PROOF OF LEMMA 14
We now restate the lemma 14 and present its proof.
Lemma 14. Suppose Assumptions 1-4 hold, and assuming My S min { م2g) motie } 1/ S
min Ag Hot
-. }. we have
(1) - 122 27
-1ly
Ag
[|y/* - -111"]] Mg + Lg
My EF.
[IB(D))
2
1 12rly
[
[|
IE(D ||
+ [II+)]"]
X
2 2 y
1
||
+
E
(222)
(2) E 111 x+ 2 11 <
E
||
17
EE
2
+ Lg
+
121/2
IF
||
E(D
11
+
||ss)
Agg
2L
1/2
[|I
+
where X, = MoLa
Proof. Inequality for
By utilizing the Young's inequality and the T -Liscchiz continuity of yxx) (Lemma 4), we have
67

---

Published as a conference paper at ICLR 2026
E ||y Iyy y (xx++)) [1]]
E ||y y (xx) + yx (xx) y* (x
< + vxn TE ||x y² (x*) [=)
+ uk
1 EF
Ily* (xt) - y* (xx+t))) [|]
(223)
s (1 B
y (x+) +
[1+
1
Liy m [110
Vik
For the first term, once again employing Young's inequality, we have
||y4tt2 y* (x*
E
Ily* y (x*) m [']
E ||s5 y* (xx) "yy Vyg* "y (mn. - -Vyg") )1o
- (1 +
M/
E ||s* my g - y (xt)) + (1+ ne E || my - 1
2
2
Utilizing Lemma 8, we can thus establish the following inequality
E yy my Vyga y" (x*)
E |ly* y (x+)) [|²] + E [1ons V 7 11]] -2R [ny (V Vyy* y yy (xx))]
(1- - 21 A₂) ) E ||yy* - y (x+ + n/ 2ny 14g + Tig
E /|
Plugging it into (223) and taking the total expectation, we have
E [|yAtt] - y ++1 [2] s (1 + m))
(1+
4/2
- 11 E [||y* -y" (xx* [1²]
2
+ (1 + vk)
(1+
1/k
n - 2ny Mg Lg
WE ||
2
+ (1 +1+))
1+
2
n E [|| | - +
1/k
+ 1+
1
Li
|
21
1/
We choose the parameter vn and the step size By to satisfy
A Mgg + Lg }
uk Ag
my S min
Then, we can obtain
||y* - x1]
A0
||1x* -x
[| V
Vygg [13)
< 1
1g + L. By
2
6MTy JE' [l|inn
vygA11 91+ + 213-12 12 IE'
L k:
+
Xg
2
Xy
E
||y**
y (x**) ||
1 12 E
[
E(D [2]
2
Ag
+
12ny
c
216 12
| [[]
Ag
Similarly, we can get the result for z.
68

---

Published as a conference paper at ICLR 2026
J.2.3 PROOF OF LEMMA 15
We now restate the lemma 15 and present its proof.
Lemma 15. Suppose Assumption 1, 2 and 3 hold, if 2 C1/Mg. we have:
E [ (x*)
m ||]
6L
||y* y11 + +L, [| -2
(224)
m E (D |1
2
where =3= =1 L2g2².
13
Proof. We begin by analyzing the expected squared norm of the difference between the gradient of the Hamiltonian and the estimate m Starting with the decomposition:
V (xt) -m&ll
[1 | (x*)
E (D*) + (D*) m |
(225)
4 (x*) (D [1 - 21E || (D*) - m ml [²]
S 21
where the first inequality follows from the Cauchy-Scheee inequality. By applying Lemma 11, we obtain:
E
| (x*)
m
[|]
1
v² + 6L || zt11"] + 2E E (D m
(226)
Thus, the lemma is proven.
J.2.4 PROOF OF LEMMA 16
We now restate the lemma 16 and present its proof.
Lemma 16. Suppose Assumption 2 and 3 hold, consider Algorithm BR-FedBi in For each step
1 E [K], we have
my k+1 - (D ||²]
(1) E
< 89 (1 LgMy)) ) (1 + 3ny Lg) ) E I
E (D+) ||] 1. [1
Tyyoo _11 E
||
+
+388 (1+ (nmn (n2Lig1
(x+)) 2 1
[1]
(1 Byy
o²
(1 - -)mm
(2) E
m k++ - E (D (D+ |1a
< 82 (1
Tgglte) E
||
E (D
+
1
1
1. ||
1/ In
1282
1
Li
m E (D ||]
Ln
1283
1 1/2 T
12
[| E [F
12
(I,T2 + 33.31222) IF [||x* - y" (xx)
+368
+ T.g
L 2 ||2 (1]
+ 12
11 The I.g.
E ||c*
27
+ 12:33
1+ Ial.g
[15
27
+ (1
3x)²
of
(1 8 8)
69

---

Published as a conference paper at ICLR 2026
(3) E [ A+1 - E (D )|
[1*}
S 0/ (1 + Tig (1 + 12 R3 || - IE (D²) [|]]
+ +482 (1+
1
1. [|
Matig
+ 1
1282
1/ ( 1
128%
1+
(L + 3L E ||1x* y (xx))]
1/2 g 1
36,92
+
T. E. | zt (x+))1[]
12,8
1+
LingE
||= + 12,3%
[+
Maclig Lg [|EE
+ +(1 Bx)²
of
ThL
[1 - 8)
Proof. Analysis for
|| 1+ k+1
E
(D
The update of the momentum term m is defined as:
m my k-1 + (1- - By Dr.
To analyze the variance of +1 relative to E (D 1)) we consider arbitrary step k > 1. The squared expectation of the deviation is given by:
E
| ++
E (D& [D*+1) ["]
E
||8y (1 - -3
(D (D (Dz) [2]
E
[|ly (m E (D²)) + (1- +1 ED -D()) By (D, (D*
S TT || (Dz) ||] + (1 - 3 - 1
+ E ||
- - (D")))" 28 (m - E (D$) E (D. + E (D+)),
(227)
where the inequality uses unbiased estimation of D For the fourth term, the inner product can be bounded using the Cauchy- Schwarz inequality:
- 288 (m E (D$) E (D k+1 E (D$))
2 m #
E (D$) || | D ++1
E (D$) ||
< 2,83 mm - E (D$)
Mly
m
12 + 2 jm
| 1|
239 1n
E (D$)) ||
1
$ Lg
E [|m - E (D+)
+
E
2
+ cz
E
|
where the second inequality uses the lipschitz continuous V
:
yd+1) - VyG((* s111
13 (Ixr+1 - 112 + ||x*+I x²) and last inequality uses 2ab < + b².
Combining (227) and (228), we have
E |||m k+1 E (D*++>>1 y
s 86 (1+ Lygny) E || m EE (D)
(1
||D 1DD++1-E(D$)
(D ||?
(228)
+ Ly (1 + Lo)
E
|| | k |||
1
[[
70

---

Published as a conference paper at ICLR 2026
Combining (228) with Lemma and Lemma 26, we have
E [[ 1-nk-1 (D*+1)11*
o²
< gg (1 + Lggly) ) (1 + 3fly lig) E |lmgg. E (D$) 11]]
+ +1-33y)
(1 8)m
+ Byyly bu (1 + my bng 34 11y -y (x*) 3E [1s$>11])
8 bu (1 + My Lوg)
|
+ oy fly
Analysis for
| k+1
E (D* [|]] 12]
The update of the momentum term m k++ is defined as:
m = x k-1 + (1 3x)
To analyze the variance of m relative E 1D)+)), we consider arbitrary step k: > 1, The squared expectation of the deviation is given by:
E
k++ m
E [1]
|| + (1- Dx ++1 - 3x1E (D*) - -E (D & (D
E
E
| (m E )Dx)) 3x) (D -E (D + (D (D (D (229)
E
||
E (D()
2 ||]
+ -1- 3x || E
+
LE
LE (D*
[ 2m (D E (D +)) - (D#)
where the inequality uses unbiased estimation of D For the fourth term, the inner product can be bounded using the Sauchy-Schward inequality:
- (m E (D+) (D 1
E (D*))
< 2/3 | - E (D E
-E
M++1 x
E (D*) II
1
< 2 m (D
|E
- ED 1|2
(230)
S La
[1lm (D+) ||']
+ L3
(D + - (D+)
where last inequality uses 2ab < a² 62.
Then we use following inequality
E
E (D&
[1]
213
12
| 2
+ n
|| (1] + 4LLD² (12E ||
+ nラ ||,m
(231)
+ 1LA
[| ||
< 1
[|
+ 1L [|m
+ "E ||m+|1
71

---

Published as a conference paper at ICLR 2026
Combining above inequality and Lemma 26, we have
E || +1 - - (D*+
8 (1 gT) E
m - E (D*) 2 + (1 -x)²
of
+ 43
1 1
L Li
| |]
(1-8)m
Thel
125
1+ MaL1
B || E (D+) ) 19] + 12
1 Mellg
I nig
[|
E [D+
12
+ 1/2 L.g
(17 3321133) E
||y** y" (xx) 12]
+ +3688
1+ Ia
Lg || - xz (x*)|²
1265
1+ MaLg
LRnzE [II$t1"] + 1202
1+
1 1
Li ||Et l*]
Similarly, for we have
E m s+1 - E 1D=+!)11?
(232)
+ (1 B2)² of
S 82 (1 Me) (1 + g2 E || E [D
(1 5)n
+ 4,6
1
1
Li
| [|]
+ 12,3
1+
1 LinEB E
m
E (D$) [|]
Tzalig
7zaLin
12
1 1
(1911211 + +3T2I2n2) E
|||x*
y* (xxi) [1²]
1/e L
+ 36692
1+ MaLg
L |||2 z" (x*))1?
+ 12,92
1 The L
E [|SSt]"] + 12:32
1
1
1. T.
||c 27
(233)
The
Thus, the lemma is proven.
Lemma 26 (Bounded second moment for momentum). Suppose Assumptions 1-4 hold. For each step E [K]. we have
(1)
E
m
k
[|]
<
2E
m
+
2E
||
(2)
E
2
3E
||$$
|2]
3I
E
(D+) [|]
+3L3E ||y* - y111
(234)
(3)
E
m k
x
< 3E
||
27
3E
m
E
(D* [2]
9 || - -2+1²²
+ 9..E
[|yx*
-
-
Proof. Bounded second moment for x. |ااا - m m 27
E 1
E
< 2E
||=
2E
27
(235)
Bounded second moment for y. Decomposing m. into three components, we have
| =
||
m
+ m - E (D + E [D
3E
[||+*|]] 27
+ +3
3E
|
E [
+ 3E [| [D (D:) ||]
(236)
3E
[|**1]]
+ 3E
||
E
+ +3LEE [|xx* -xil
72

---

Published as a conference paper at ICLR 2026
where the first inequality uses Cauchy- Secch---chwatzztt inequality and the second inequality uses Assumption
Bounded second moment for Decomposing n into three components, have
E
B
mm
m
m
E (Dx) + E (D:) []]
s 3E
||
+3E
|m
EE (D 3E
E (D 11
S 3E
3E
|
E (D
9
11
+ 9L3B
||x**
y. [1]
(237)
where the first inequality uses
inequality and the second inequality uses Assumption
1.
J.2.5 PROOF OF LEMMA 17
We now restate the lemma 17 and present its proof.
Lemma 17. Recall that the upper-level loss function is L we have
PH (x+ S E @ (x*)]
11x E
|| (x*)
11]
( 1xx
L yE
[|
2
(238)
V (x*) mEll"] + Bx |||5|||
27
+ 1x
Proof. By using smoothhess of upper-leved loss function 4, we obtain
E 1 (x++1)]
< E 4x (x*)
+ E
(v (x*)
x* 1
Lvo
E
||
x*
x1( 11²]
2
E p (x*)
17x E
( 2 (x*) m
T
|
k
21
E pxx (x*)
1xx
E
v (x*)
||3| )|
Txx
IE
||
2
2
1x E | (x*) - mxll" + T E
||
(239)
where the last equality uses (a, b) (a² + b² - (a + b)
Du [x]
< E 1 (x*))
1xx
|| ve (x*) ||]] - %x
Loon
)E
[|
2
2
(240)
+ 7 E
(x*)
m&ll" + B ||s$|| 27
where the last inequality uses the Cauchy- Schwarz inequality.
73

---

Published as a conference paper at ICLR 2026
J.3 PROOF OF SUPPORTING LEMMAS FOR BR- BR-FEDBIP
J.3.1 PROOF OF LEMMA 18
We now restate the lemma 18 and present its proof.
Lemma 18. Suppose Assumptions and hold,and the robust aggregation rule AGG(.) satisfies the (6, k) rob-ustbsss criterion. The aggregation errors in the BR-FedBi algorithm (Algorithm 1) satisfy the following inequalities:
(1) E ||
< 4k6g + 4x
[1+
1
0²
(1 8)m1
(2) E |||+||]]
$ 8K (0 + (g) 8k
1+
o
(1 8)n
(3) E ||
|]
s 8k (0 + {7) 8k
1
01
(1 8)m
where of -1 + p²)o² and
Proof. Analysis for || Recall that
Ey - y.. b
For an arbitrary step l: > 1, we obtain that
E 1
v+ll")
K
Σ
pE
Gi VyG(x*, x1117]]
8)n
iEM
+ (1
VVy (x+,x*)
VyG, (x* (x* y (V,G
(241)
where the inequality uses the expectation over and the inequality holds due to the (5, k)) robuustesss of (GG as defined in definition 2.
Using the the Cauchy-Schwaal inequality, we obtain that
v+1"
E
V yt) Vx(((*t
2F
[1 5)
E
G2 k-1 xk1 ,
VyG(x* , -
+ 2E
(242)
4n2z + 4k 1 ((1 ((1-5)m) 0²
(1 8)m BE7
)m)) 0²,
< 4x63 + 4x
(1+ ((1 8)m)
(1+(1-8m)
where the second inequality uses Assumptions 3 and 4.
Similarly, the inequality for x and z can be established by following the same proof as in Lemma 9,
J.3.2 PROOF OF LEMMA 21
We now restate the lemma 21 and present its proof.
74

---

Published as a conference paper at ICLR 2026
Lemma 21. Suppose Assumptions 2 and 3 hold, consider Algorithm BR-FedBiP in 1. For each E [K], we have
(1)
E v k+1 - E (D++t))
0²
+ (1 - p)L || B(D
P (n
(1 2
B [11211]] + 33 | - E [I) |1²))
+
b
(1 2
(LL ||5 - -+1l + 3 [|st|] ().
+
b
(2) E [[v - (D*+1) [|
of
+ (1 - p) [|l - >1 + (1 p)
Li L ||
$ P 6' - f)
+ +12 (1 - p) 13,1 (R) [II$t []] E ||v e (D))) [1"] + F. [|ly* y((11)))
+ 12(1 p) 22
DE [|<>|]]] + E 1| - E (D (D
b
12(1 p)
+
La (3 [||2* - |-] + 3L3E [|yy* - y
b
(3) E [|[v k+1 - E (D (D=+1)) |1
of
||| 2 >(D []] + (1 p) L E ||
P 6'(n f)
+ (1
D)
+ 12 (1 p)
1 B
[||$t
["]
+ E [|v - e (D,) (D/) [1]] B. [[ly* -111131)
b
12(1 p) 1,
[
[||=t|]]] + E ||v2- B ||] + 33,E [||e* 20:111]
b
+ 12(1 p)
12 (3LEE [||y* - y1
b
Proof. Analysis for E [[ E (D++1) [1:]. Recall that
VG. vv- VG, (u (p) VG, (ut)) w.p. 1 1- p.
[ sp!
w.p. P.
To analyze the variance of v relative to E (D++1), we consider an arbitrary step k > 1. The squared expectation of the deviation is given by:
|| k+1 E
(D*+)) ["]
S
IE
y G(xx(x (( E (D )1*] + (1 - p)) [|v + D - - EE (D [D*
2²
E) || - (D ||] + (1 1) ||D DØ E (D + E (DŞ) |2]
V(n + (1
(243)
where the first inequality uses the expectation over ck2 the second inequality uses unbiased estimation in Assumption 3.
Using E
||X]| p < KEA [ we can imply that
E
|| k + +D 1+1 DD. - (DD <
D k+1 - D+11
(244)
75

---

Published as a conference paper at ICLR 2026
Plugging (244) into (243), we obtain that
E
++1 -
E
(D++1)
(D,
p V(n f)
(1 p)
|| - B [D
+ (1 (1- || x+
D
S 8(n f)
o²
+ (1 p)
|| E (D |1
1 ||>
+ nラ || [1]
b
0²
(1 - 2
V(n P(n -f) + (1 p)
|| E (D$) |1]]
| ||
+ अف
||
E (D ||]
b
L |||s* - y [|] + 3 [|+)
(245)
where the second inequality uses Assumption 7, and last inequality uses Lemma 27. Analysis for
[| k+ E (D*+1) [!?]
To analyze the variance of v relative to E (D*+1), we consider an arbitrary step k > 1. The squared expectation of the deviation is given by:
++1 -E
E (Dx
(D&+1) ||]]
P Vn f)
o
+ (1 p)lE
|| + D k+1
D - E (D |??
of
$ V(n f) + (1 - E)
|| - E (D*)
[|] + +1 - p)
|| k+1 D -E (D + E (D 11) |1
(246)
where the first inequality uses the expectation over ck. the second inequality uses unbiased estimation in Assumption 3.
Using E||x X
|[X]| < E [ we can imply that
E || + D D - (D [
D SE
-D&I'
k-1
(247)
Plugging (247) into (246), we obtain that
E k+1 EE (D k+1 ||]]
(Dx+))
of
(1 p)l
|| E (D*)
[]]
2
+ (1 (1-1) p)) || 1* 2
p(nn f)
of
(1 p)l || E (D+) ||]
+ t p) Li [100119]
p(n f)
(1 p)
LinE ||
4(1 - p)
13 [|\>~11]]
b
S PP - f)
of
+ (1 D)
|| - E (D |?]
+ (1- p) 1
||
[n
12 (1 (1-p) p)
L3 (E [||* [|]]
+ E || E (D+) 11"]
+ 1E |||** - y (111))
b
12(1 p)
n2 (I [|<=||]]]]]]
||v E (D + +355 |||2 2 |2]
+ 3L3E
||y* - y (1))
1|y+-
(248)
where the second inequality uses Assumption 7, and last inequality uses Lemma 27.
Analysis for E [[|v++] E (D
76

---

Published as a conference paper at ICLR 2026
To analyze the variance of v²+1 relative to E (D&+1), consider arbitrary step k > 1. The squared expectation of the deviation is given by:
E l|ve+* - E (D=+)) [[]]
of
P Vn f) (1 p)
V + D
D
EE (D2+1) "1
of
p Vnn - (1 p) || EE (D=)ll)
+
|| h+ D E (D 10
(D
(249)
where the first inequality uses the expectation over Ck= the second inequality uses unbiased estimation in Assumption 3. Using [B| X - E[X]| - E [x]] we can imply that
| h + D
k++ - D E (DE ((=+))"' | S E
D k+1
- D 21
(250)
Plugging (250) into (249), we obtain that
(D
k++)
x
P ((
o
+ (1 p)
| - EE (D [|]
+ (1 D)B || k+ - 11
p (n -
of
+ (1 p)
|| - EE (D [|]]
+ (1 p)
Li [1121]]]
+ 4 (1 p) Li ||***1
+ 4(1 - p) LE ||
b
of
+ (1 p) [1 ||~2 EE (1) [|] (1 P)
Lin IE [|
p V( f)
p)
12 E || 12]
E ||v - B (D$) ||]]
+ 13 11y*-x*1 y²)(())
12
b
12(1 - p)
13
[E
[|<=)]]]]]
+ E
[|vE E ||
+ 332 [||2* 2 |2]
+ 3L
[||y -y*->211 x2ll"))
(251)
where the second inequality uses Assumption 7, and last inequality uses Lemma 27.
Lemma 27 (Bounded second moment). Suppose Assumptions 1-4 hold. For each step [K], we
have
(1)
k
< 2E
+ 2
(2)
|| y
< 3E [|5$) ||]
+ 3E
[| E (D&)
+ + [|y* y y-11
(252)
(3) ||02||]]
S 3E ||stt |2]
+ 3IE
[|v* ||
+ +9L3E || -
-2201 2111?
+ 9LLE
[|xx*
- -x-11 1-1
Proof. Bounded second moment for E
||
v
v ||
S 2E ||~=||
+
2E
||5* 27
(253)
Bounded second moment for y. Decomposing vy into three components, we have
E
[|
E
||
v
+ + -E (D + (D
||| 27
|| E (D + 3E E | |3]
$ 3E
+ 3E
(254)
s 3E
[|<)|]]]
+ 3E
[| - E (D
+ 3L3E [|y - x [1]
77

---

Published as a conference paper at ICLR 2026
where the first inequality uses Cauchy-Schward inequality and the second inequality uses Assumption 1 and (218).
Bounded second moment for Decomposing v into three components, we have
E
k
E
v
(D,) E [1]
[|]]
||<
|| E (D (D ||
3E || B (D [D
s 3E
3EE
S 3E
||<|||
3E
|| E (D ||]
9
||
+
+9L3E
[|,x*
y:
(255)
where the first inequality uses I and (220).
inequality and the second inequality uses Assumption
78


Reviews:
[{"review_id": "uD8TkK3Fv3", "reviewer": "Reviewer_aw31", "summary": "this paper studies the vulnerability of federated bilevel optimization against Byzantine attacks and the inefficiency of existing sub-loop-based defenses by proposing a family of single-loop Byzantine-resilient algorithms (FBO). The proposed algorithms leverage auxiliary variables, Polyak’s momentum, and variance reduction to balance robustness, computational and communication efficiencies.  The experiments on a set of hyper-representation tasks show the algorithms outperform existing tasks under four attacks and six robust aggregators. Authors also give theoretic analysis regarding algorithm-independent lower bound for FBO under Byzantine attacks.", "questions": "Can authors elaborate the potential applications of the proposed method in real-world scenarios ?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies two important problems in federated bilevel optimization including Byzantine vulnerability and computational inefficiency of sub-loop defenses.   It also provides first-of-its-kind theoretical guarantees for Byzantine-resilient federated bilevel optimization.  Experimental results have shown consistently that the proposed method outperform the existing methods in the literature.", "weaknesses": "Experiments use fixed attacker ratios and static attack types, but real-world Byzantine attacks often involve dynamic attacker counts e.g., sudden spikes in faulty clients or adaptive attack strategies. The paper does not test how algorithms adapt to such changes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q6grdjQag7", "reviewer": "Reviewer_jwjE", "summary": "This paper proposes BR-FedBi, a single-loop Byzantine-resilient federated bilevel optimization framework. By introducing an auxiliary variable and integrating Polyak’s momentum with the probabilistic gradient estimator (PAGE), the method achieves efficient hypergradient estimation, optimal Byzantine resilience, and sample complexity. Both theoretical analysis and experiments show strong empirical performance under adversarial settings.", "questions": "see weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses an important and challenging problem, Byzantine-resilient bilevel optimization in federated settings, which is timely and underexplored.\n\n2. The proposed single-loop design is elegant and significantly reduces computation and communication overhead compared to two-loop approaches.\n\n3. Theoretical analysis is comprehensive, providing convergence guarantees with optimal sample complexity, supported by consistent empirical results.", "weaknesses": "1. The paper’s presentation could be clearer, especially in explaining how the auxiliary variable interacts with upper and lower levels in the single-loop update.\n\n2. Experimental evaluation is somewhat limited; it would be more convincing to include larger-scale or more diverse federated settings.\n\n3. The robustness analysis mainly relies on existing aggregation rules; more ablation on the aggregation mechanism itself would strengthen the contribution.\n\n4. While the proposed single-loop design is interesting, the experimental section lacks direct comparison with other single-loop bilevel approaches, which would help isolate the benefit of the proposed structure itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "crEhFfet46", "reviewer": "Reviewer_h9q3", "summary": "The paper studies federated bilevel optimization (FBO) under Byzantine clients. It first presents an algorithm‑independent asymptotic lower bound. Algorithmically, the paper proposes a single‑loop Byzantine‑robust FBO framework BR‑FedBi, plus a Polyak‑momentum version (BR‑FedBiM) and a PAGE variance‑reduced version (BR‑FedBiP). With momentum, the method is shown to match the lower bound up to constants, claiming “optimal Byzantine robustness.” Experiments also validate the advantages of the proposed algorithm.", "questions": "See Weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. First Byzantine lower bound for FBO. Extends single‑level robust learning lower bounds to bilevel settings, clarifying that both upper‑ and lower‑level heterogeneity amplify error and that the breakdown depends on $B_f,B_g$. \n2. Theory–algorithm closure. After giving the lower bound, BR‑FedBiM attains it (up to constants), which is convincing.\n3. Robust empirical gains across diverse attacks/aggregators with sizeable margins.", "weaknesses": "1. External validity / representativeness. Experiments focus on hyper‑representation with small models and datasets. Add a more realistic, higher‑dimensional FBO (e.g., hyperparameter optimization of weight decay/augmentation, or meta‑learning / personalized FL) and report end‑to‑end communication volume, latency, and speedups to support the single‑loop efficiency claim.\n2. Lacked related works. The related works section lacks coverage of distributed stochastic bilevel optimization, particularly decentralized bilevel optimization, which has gained an increasing focus recently. Therefore, the author should include a review of relevant works on decentralized bilevel optimization in this section.\n3. Near‑critical $\\delta$ behavior & aggregator choice. Theory constrains $\\kappa$ vs. $\\delta$, but the paper lacks a systematic study when $\\delta$ approaches the breakdown. Provide $\\delta$ sweeps and compare $\\kappa$ across aggregators to probe the near‑bound regime.\n4. Assumption strength & measurability. Mean‑square smoothness and $(\\zeta,B)$‑heterogeneity are standard but not easily measurable in practice. Offer empirical estimates (from client gradient statistics) for $\\zeta_f,\\zeta_g,B_f,B_g$ to connect constants to practice.\n5. Baseline tuning fairness. Has BILANTINE been tuned fairly for communication rounds, stepsizes, batch sizes? Include ablations under equal communication budget or equal wall‑clock, and disclose full tuning tables.\n6. Engineering clarifications. Clarify PAGE trigger probability $p$, mini‑batch sizes $b$, momentum/stepsize coupling (theory ranges vs. actual values). Address practical FL issues (asynchrony, partial participation, client dropouts) experimentally if possible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)