This paper introduces a novel approach and algorithm for solving constrained Bi-Level Optimization (BLO) problems, where the lower-level problem involves constraints that couple both upper-level and lower-level variables. These problems are widely used in machine learning, such as hyperparameter optimization, meta-learning, and neural architecture search. Traditional gradient-based methods often require computationally intensive calculations involving the Hessian matrix, which can be expensive. To address this, the authors propose a smooth proximal Lagrangian value function to handle the constrained lower-level problem. This function is defined as the value function of a strongly-convex-strongly-concave proximal min-max problem, which is continuously differentiable. By leveraging this function, the authors reformulate the original BLO problem into an equivalent single-level optimization problem with smooth constraints. Based on this reformulation, they develop a Hessian-free gradient-based algorithm called Proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA). LV-HBA is designed to be implemented in a single loop, making it particularly suitable for machine learning applications. The authors provide a non-asymptotic convergence analysis for LV-HBA, eliminating the need for strong convexity assumptions on the lower-level problem and accommodating non-singleton scenarios. Empirical results on synthetic problems, hyperparameter optimization for SVM, and federated bilevel learning demonstrate the superior practical performance of LV-HBA compared to existing methods.This paper introduces a novel approach and algorithm for solving constrained Bi-Level Optimization (BLO) problems, where the lower-level problem involves constraints that couple both upper-level and lower-level variables. These problems are widely used in machine learning, such as hyperparameter optimization, meta-learning, and neural architecture search. Traditional gradient-based methods often require computationally intensive calculations involving the Hessian matrix, which can be expensive. To address this, the authors propose a smooth proximal Lagrangian value function to handle the constrained lower-level problem. This function is defined as the value function of a strongly-convex-strongly-concave proximal min-max problem, which is continuously differentiable. By leveraging this function, the authors reformulate the original BLO problem into an equivalent single-level optimization problem with smooth constraints. Based on this reformulation, they develop a Hessian-free gradient-based algorithm called Proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA). LV-HBA is designed to be implemented in a single loop, making it particularly suitable for machine learning applications. The authors provide a non-asymptotic convergence analysis for LV-HBA, eliminating the need for strong convexity assumptions on the lower-level problem and accommodating non-singleton scenarios. Empirical results on synthetic problems, hyperparameter optimization for SVM, and federated bilevel learning demonstrate the superior practical performance of LV-HBA compared to existing methods.