  Gradient-based Bi-Level Optimization (BLO) methods have been widely applied
to handle modern learning tasks. However, most existing strategies are
theoretically designed based on restrictive assumptions (e.g., convexity of the
lower-level sub-problem), and computationally not applicable for
high-dimensional tasks. Moreover, there are almost no gradient-based methods
able to solve BLO in those challenging scenarios, such as BLO with functional
constraints and pessimistic BLO. In this work, by reformulating BLO into
approximated single-level problems, we provide a new algorithm, named Bi-level
Value-Function-based Sequential Minimization (BVFSM), to address the above
issues. Specifically, BVFSM constructs a series of value-function-based
approximations, and thus avoids repeated calculations of recurrent gradient and
Hessian inverse required by existing approaches, time-consuming especially for
high-dimensional tasks. We also extend BVFSM to address BLO with additional
functional constraints. More importantly, BVFSM can be used for the challenging
pessimistic BLO, which has never been properly solved before. In theory, we
prove the asymptotic convergence of BVFSM on these types of BLO, in which the
restrictive lower-level convexity assumption is discarded. To our best
knowledge, this is the first gradient-based algorithm that can solve different
kinds of BLO (e.g., optimistic, pessimistic, and with constraints) with solid
convergence guarantees. Extensive experiments verify the theoretical
investigations and demonstrate our superiority on various real-world
applications.
