Complexity Guarantees for Heterogeneous Federated Bilevel Optimization with Lower-Level Constraints

Federated bilevel optimization (FBO) provides a framework for bilevel learning with decentralized data, yet existing methods largely focus on unconstrained lower-level problems and often rely on hypergradient computation. Lower-level constraints often induce nonsmoothness in the solution mapping, posing substantial challenges for standard implicit differentiation and hypergradient approaches. We propose an inexact zeroth-order framework for FBO that accommodates lower-level constraints and nonsmooth, nonconvex implicit upper-level objectives. To the best of our knowledge, this is the first zeroth-order method for constrained FBO that provides convergence and communication-complexity guarantees while accommodating client drift in both levels. Our contributions are threefold. (i) We design a SCAFFOLD-based zeroth-order scheme that uses control variates to correct client drift under heterogeneous data and partial client participation. To reduce repeated lower-level communication, we compute only two inexact lower-level solutions per outer round and reuse them across multiple local upper-level updates, while explicitly characterizing and controlling the resulting delay, bias, and lower-level inexactness. (ii) We propose Adaptive Penalty SCAFFOLD for constrained federated lower-level problems, using an increasing penalty parameter and round dependent local stepsizes, and establish convergence guarantees for the resulting inexact solutions. (iii) We extend the framework to constrained personalized FBO with client-specific lower-level problems and a general bilevel structure, allowing distinct upper- and lower-level objectives and client-specific constraints. Our numerical experiments on hyperparameter optimization and personalized federated learning demonstrate the performance of the proposed methods.