Towards Efficient Large-Scale Bi-level Optimization, Algorithms and Applications
COM3 Level 2
SR21, COM3 02-60
Abstract:
Bi-level optimization is a mathematical framework with a long history of research, dealing with hierarchical optimization problems where one problem is nested within the other. Recently, with the rise of machine learning, bi-level optimization has regained attention as a theoretical framework covering a wide range of machine learning problems, including hyperparameter optimization, neural architecture search, robust machine learning, meta-learning, and physics-informed machine learning. In recent years, as the scale of machine learning problems has grown rapidly, large-scale bi-level optimization has emerged as a critical area of study. These large-scale settings bring unique computational and algorithmic challenges, including memory constraints, scalability issues, and the complexity of high-order gradient computations.
This thesis focuses on analyzing the key challenges introduced by large-scale bi-level optimization and presents recent methodological advances aimed at addressing them. Beyond a survey of existing approaches, we propose principled algorithmic designs tailored to various problem scenarios, enabling the efficient resolution of large-scale bi-level optimization tasks in practical applications. These contributions aim to bridge the gap between theoretical developments and scalable deployment in real-world machine learning systems. This dissertation is organized into two main parts.
The first part focuses on large-scale bi-level optimization algorithms. We begin by introducing classical bi-level optimization algorithms, including gradient unrolling (GU)-based, implicit function (IF)-based, and value function (VF)-based approaches. We then provide a theoretical analysis of the computational and memory challenges these methods face when applied to large-scale problems. Following this, we discuss recent developments in large-scale bi-level optimization. We review state-of-the-art algorithms, assessing their respective strengths and limitations across diverse practical scenarios. In particular, we introduce Forward Gradient Unrolling with Forward Gradient ((FG)2U), which leverages forward-mode automatic differentiation (AD) to significantly reduce memory consumption compared to traditional GU-based methods. Furthermore, we explore key considerations for improving computational efficiency in large-scale settings, such as variance control, parallel computation, and iterative strategy refinement.
The second part is dedicated to real-world applications of large-scale bi-level optimization. We first investigate the problem of identifying confidence intervals in Partial Differential Equations (PDEs), framing it as a bi-level optimization problem and introducing Physics-informed Confidence Propagation (PICProp) as a solution. Next, we explore a vision-language model (VLM) pipeline called SilentBadDiffusion, designed to solve the bi-level formulation of a copyright backdoor attack in text-to-image (T2I) generation. Finally, we present Loss-based Reweighting Unlearning (LoReUn), a lightweight plugin for accelerating machine unlearning, inspired by classical data reweighting in bi-level optimization.