A Loopless Distributed Algorithm for Personalized Bilevel Optimization

Abstract: This paper studies a class of personalized distributed bilevel optimization problems over networks, where nodes aim at jointly optimizing the sum of outer-level objectives that depend on the solution of inner-level optimization problems. The existing algorithms for distributed bilevel optimization problems usually require extra computation loops for estimating hypergradients. To facilitate computational efficiency, we develop a loopless distributed algorithm that employs certain steps to approximate the optimal solution of inner level optimization problems, and track Hessian-inverse-vector products in a recursive manner. We prove that for stochastic nonconvex-strongly-convex problems, the proposed algorithm achieves the state-of-the-art $\mathcal{O} \left( \epsilon ^{-2} \right) $ communication cost, while improving the computational cost by $\mathcal{O} \left( \log \left( 1/\epsilon \right) \right) $. Numerical experiments validate our theoretical findings.