SLBRD: A Single-Loop and Byzantine-Resilient Decentralized Bilevel Algorithm

Decentralized bilevel optimization has emerged as a powerful paradigm for large-scale machine learning over distributed data. However, these systems are inherently vulnerable to Byzantine agents that transmit arbitrary or adversarial updates. While extensive progress has been made on Byzantine resilience in single-level optimization, extending these robustness guarantees to the bilevel setting remains an open problem. To bridge this gap, we propose SLBRD, the first Byzantine-resilient decentralized bilevel algorithm. By adopting a fully single-loop and Hessian-inversion-free architecture, SLBRD improves communication efficiency and limits the attack surface available to adversaries. We establish its sample and transient iteration complexities, explicitly characterizing the joint effects of network topology, data heterogeneity, and Byzantine influence. We further develop the Polyak-momentum variant SLBRD-M, which removes stochastic variance from the persistent Byzantine error and improves the topology-dependent transient complexity. Experiments on hyperparameter optimization and hyper-representation tasks validate the effectiveness of the proposed methods.