2024/01/29 by Wei Yao, Chengming Yu, Yao, Wei +5 · 6 citations
Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Advanced Numerical Methods in Computational Mathematics #FOS: Computer and information sciences #FOS: Mathematics #Gas Dynamics and Kinetic Theory #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2401.16164
openalex publication_date 2024/01/29 · openalex created_date 2024/01/31 · openalex updated_date 2026/07/28
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.