Unlocking Global Optimality in Bilevel Optimization: A Pilot Study
This work addresses the open problem of global optimality in bilevel optimization, which is important for high-stakes engineering applications, though it appears incremental as it builds on existing convergence theories.
The paper tackled the challenge of achieving global optimality in bilevel optimization, which is crucial for reliable AI applications, by presenting sufficient conditions for global convergence and demonstrating convergence to the global minimum in representation learning and data hypercleaning experiments.
Bilevel optimization has witnessed a resurgence of interest, driven by its critical role in trustworthy and efficient AI applications. While many recent works have established convergence to stationary points or local minima, obtaining the global optimum of bilevel optimization remains an important yet open problem. The difficulty lies in the fact that, unlike many prior non-convex single-level problems, bilevel problems often do not admit a benign landscape, and may indeed have multiple spurious local solutions. Nevertheless, attaining global optimality is indispensable for ensuring reliability, safety, and cost-effectiveness, particularly in high-stakes engineering applications that rely on bilevel optimization. In this paper, we first explore the challenges of establishing a global convergence theory for bilevel optimization, and present two sufficient conditions for global convergence. We provide algorithm-dependent proofs to rigorously substantiate these sufficient conditions on two specific bilevel learning scenarios: representation learning and data hypercleaning (a.k.a. reweighting). Experiments corroborate the theoretical findings, demonstrating convergence to the global minimum in both cases.