Rethinking Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy

Risheng Liu, Zhu Liu, Wei Yao, Shangzhi Zeng, Jin ZhangOpenReview 2024 · Submission to ICLR 2024 · Rejected · OpenReview

Abstract

Bi-Level Optimization (BLO) has found diverse applications in machine learning due to its ability to model nested structures. Addressing large-scale BLO problems for complex learning tasks presents two significant challenges: ensuring computational efficiency and providing theoretical guarantees. Recent advancements in scalable BLO algorithms has predominantly relied on lower-level convexity simplification. In this context, our work takes on the challenge of large-scale BLO problems involving nonconvexity in both the upper and lower levels. We address both computational and theoretical challenges simultaneously. Specifically, by utilizing the Moreau envelope-based reformulation, we introduce an innovative single-loop gradient-based algorithm with non-asymptotic convergence analysis for general nonconvex BLO problems. Notably, this algorithm relies solely on first-order gradient information, making it exceedingly practical and efficient, particularly for large-scale BLO learning tasks. We validate the effectiveness of our approach on a series of different synthetic problems, two typicial hyper-parameter learning tasks and the real-world neural architecture search application. These experiments collectively substantiate the superior performance of our method.
BibTeX
@misc{liu2024rethinking,
  author = {Risheng Liu and Zhu Liu and Wei Yao and Shangzhi Zeng and Jin Zhang},
  title = {{Rethinking Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy}},
  year = {2024},
  url = {https://openreview.net/forum?id=i6EtCiIK4a},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2024},
}
Figure