FedBiC: Federated Bilevel Constrained Optimization

Bilevel optimization has emerged as a fundamental framework for hierarchical machine learning problems, such as hyperparameter optimization, meta-learning, adversarial training, and neural architecture search. Extending this framework to federated settings allows collaborative training between distributed clients without sharing raw data. However, existing federated bilevel methods assume unconstrained lower-level problems, excluding applications with fairness constraints, resource budgets, or safety requirements. We propose FedBiC, the first federated bilevel algorithm that is capable of handling a convex lower-level objective together with general client-specific convex inequality constraints, using a gap function reformulation. FedBiC is single-loop and Hessian-free, supports partial client participation, and requires no bound on client heterogeneity. We establish an $O(1/\sqrt{pK})$ convergence rate to a stationary point of the penalized objective under a fixed penalty and partial participation, where $K$ denotes the number of communication rounds. With an increasing penalty parameter and full participation, FedBiC attains an $O(1/K^{(1-2\rho )/2})$ stationarity rate for the penalized objective, together with an $O(K^{-\rho })$ rate on the clientwise lower-level gap violation. Experiments on federated constrained LASSO, fair few-shot meta-learning, and federated steering under label noise are conducted to validate our approach.