FAB: A First-Order AB-based Gradient Algorithm for Distributed Bilevel Optimization over Time-Varying Directed Graphs

Distributed optimization over time-varying directed graphs has shown promising performance in addressing challenges posed by complex communication constraints in real-world scenarios. In many practical settings, however, the direct application of distributed optimization algorithms encounters additional difficulties, most notably hyperparameter tuning, which our empirical observations suggest can be effectively mitigated by integrating bilevel optimization. Motivated by these findings, we study distributed bilevel optimization over time-varying directed networks, a problem that remains largely unexplored due to the compounded challenges arising from consensus bias in dynamic unbalanced communication and the nested optimization structure. In this work, we propose a fully first-order distributed gradient-based algorithm that integrates the Push–Pull (also known as AB) communication strategy with a value function-based penalty method and establish its non-asymptotic convergence properties. Notably, a simplified variant of our analysis framework for nonconvex single-level distributed optimization establishes a convergence rate for the Push–Pull algorithm, thereby resolving an open question concerning its convergence over time-varying directed graphs. Experiments across hyperparameter tuning, data hyper-cleaning, and reinforcement learning validate FAB's effectiveness and efficiency.

Modern machine learning often runs across many devices or agents, such as distributed servers or connected devices, whose communication links can change over time. This paper studies how these agents can cooperate to solve learning problems that also require tuning important choices such as hyperparameters. We propose FAB, a distributed method that lets agents communicate over changing directed networks while avoiding expensive second-order computations. We prove that the method converges under standard assumptions and show in experiments on hyperparameter tuning, data cleaning, and reinforcement learning that it performs effectively in practical distributed learning settings.