Regularization-Based Constrained Distributed Bilevel Optimization Over Unbalanced Graphs

This paper focuses on solving a class of constrained distributed bilevel optimization problems over unbalanced graphs, where all agents are equipped with convex inner objective functions and strongly convex outer ones. The goal of solving the considered bilevel optimization problem is to minimize the global objective functions at both levels. In this paper, we propose a regularization-based distributed projected algorithm with row stochastic matrices and a time-varying regularization parameter θt. Furthermore, with the aid of the strong convexity of outer objective functions and the smoothness of two level objective functions, we establish that the proposed algorithm converges to the optimal solution with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−<i>a</i>+<i>b</i></sup>) (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</i> ∈ (0.5, 1) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</i> ∈ (0, 0.5)) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−<i>b</i></sup>) convergence rates from the perspectives of the outer and inner objective functions, respectively. Finally, we illustrate the effectiveness of the proposed algorithm by numerical simulations.