An Implicit Gradient Method for Constrained Bilevel Problems Using Barrier Approximation

Abstract

In this work, we propose algorithms for solving a class of Bilevel Optimization (BLO) problems, with applications in areas such as signal processing, networking and machine learning. Specifically, we develop a novel barrier-based gradient approximation algorithm that transforms the constrained BLO problem to a problem with only linear equality constraints in the LL task. For the reformulated problem, we compute the implicit gradient and develop a gradient-based scheme, involving only a single gradient descent step and the (approximate) solution of the linearly constrained strongly convex LL task at each iteration. We establish, under certain assumptions, the non-asymptotic convergence guarantees of the proposed method to stationary points. Finally, we perform a number of experiments that show the potential of the proposed algorithm.