Constrained Bi-Level Optimization: Proximal Lagrangian Value function
  Approach and Hessian-free Algorithm
Wei Yao Chengming Yu Shangzhi Zeng Jin Zhang
This paper presents a new approach and algorithm for solving a class of
constrained Bi-Level Optimization (BLO) problems in which the lower-level
problem involves constraints coupling both upper-level and lower-level
variables. Such problems have recently gained significant attention due to
their broad applicability in machine learning. However, conventional
gradient-based methods unavoidably rely on computationally intensive
calculations related to the Hessian matrix. To address this challenge, we begin
by devising a smooth proximal Lagrangian value function to handle the
constrained lower-level problem. Utilizing this construct, we introduce a
single-level reformulation for constrained BLOs that transforms the original
BLO problem into an equivalent optimization problem with smooth constraints.
Enabled by this reformulation, we develop a Hessian-free gradient-based
algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level
Algorithm (LV-HBA)-that is straightforward to implement in a single loop
manner. Consequently, LV-HBA is especially well-suited for machine learning
applications. Furthermore, we offer non-asymptotic convergence analysis for
LV-HBA, eliminating the need for traditional strong convexity assumptions for
the lower-level problem while also being capable of accommodating non-singleton
scenarios. Empirical results substantiate the algorithm's superior practical
performance.