Hessian-Free Distributed Bilevel Optimization via Penalization With Time-Scale Separation

This article considers a class of distributed bilevel optimization (DBO) problems with a coupled inner-level subproblem. Existing approaches typically rely on hypergradient estimations involving computationally expensive Hessian evaluation. To address this, we approximate the DBO problem as a minimax problem by properly designing a penalty term that enforces both the constraint imposed by the inner-level subproblem and the consensus among the decision variables of agents. Moreover, we propose a loopless distributed algorithm, AHEAD, that employs multiple-timescale updates to solve the approximate problem asymptotically without requiring Hessian computation. Theoretically, we establish sharp convergence rates for the nonconvex-strongly convex settings and for distributed minimax problems as special cases. Our analysis reveals a clear dependence of convergence performance on node heterogeneity, penalty parameters, and network connectivity, with a weaker assumption on heterogeneity that only requires bounded gradients at the optimum. Numerical experiments corroborate our theoretical results.