Fully First-Order Lagrangian Methods for Byzantine-Robust Federated Bilevel Learning

Federated bilevel optimization (FBO) plays a crucial role in solving hierarchical learning problems over distributed data. However, its distributed nature makes it highly susceptible to faulty or Byzantine clients. Existing Byzantine-robust FBO methods either rely on Hessian or Jacobian vector products or perform repeated robust updates within an inner loop, incurring additional differentiation or synchronization costs. To address these limitations, we propose FOBFBL, the first Byzantine-robust FBO method that is both fully first-order and single-loop. With a finite Lagrangian multiplier $\lambda$, it forms three coupled blocks of stochastic gradients that the server robustly aggregates at their natural scales in one round. For nonconvex upper-level and strongly convex lower-level objectives, we establish a nonasymptotic stationarity bound that separates the decaying optimization error, the Byzantine-induced floor, and the $\mathcal{O}(1/{\lambda }^2)$ Lagrangian bias, yielding $\mathcal{O}({\epsilon }^{-2})$ iterations above the residual floor. Under an additional upper-level PL condition, we obtain a last-iterate function-gap bound with $\tilde{\mathcal{O}}((n_{h}K{)}^{-1})$ finite-horizon dependence. We further develop the Polyak-momentum variant FOBFBL-M, which removes stochastic variance from the persistent Byzantine error and leaves a limiting neighborhood governed by honest heterogeneity and the Lagrangian bias. Experiments on federated hyperparameter optimization and hyper-representation learning validate both methods.