Overview

Bilevel optimization models decisions in two levels: an outer problem evaluates choices using the solution of an inner problem, as in hyperparameter tuning, data selection, meta-learning, and neural architecture search. Common approaches differentiate through inner optimization using unrolling or implicit hypergradients, while single-loop stochastic, penalty-based, and derivative-free methods aim to reduce computation and handle larger or black-box problems. Applications also use the framework for decision-focused learning, reinforcement learning, and strategic settings where one agent responds to another. A central challenge is making these methods efficient and reliable when the inner problem is nonconvex or has multiple solutions, while establishing useful convergence and generalization guarantees without restrictive assumptions.

Latest papers

96 papers10 papers in the last four weeks, down 23% on the four weeks before. 0.1% of all new papers.

Jan 21, 2026

Non-Stationary Functional Bilevel Optimization

Functional bilevel optimization (FBO) provides a powerful framework for hierarchical learning in function spaces, yet current methods are limited to static offline settings and perform suboptimally in online, non-stationary scenarios. We propose SmoothFBO, the first algorithm for non-stationary FBO with both theoretical guarantees and practical scalability. SmoothFBO introduces a time-smoothed stochastic hypergradient estimator that reduces variance through a window parameter, enabling stable outer-loop updates with sublinear regret. Importantly, the classical parametric bilevel case is a special reduction of our framework, making SmoothFBO a natural extension to online, non-stationary settings. Empirically, SmoothFBO consistently outperforms existing FBO methods in non-stationary hyperparameter optimization and model-based reinforcement learning, demonstrating its practical effectiveness. Together, these results establish SmoothFBO as a general, theoretically grounded, and practically viable foundation for bilevel optimization in online, non-stationary scenarios.
Nov 27, 2025

On the Condition Number Dependency in Bilevel Optimization

Bilevel optimization minimizes an objective function, defined by an upper-level problem whose feasible region is the solution of a lower-level problem. We study the oracle complexity of finding an εε-stationary point with first-order methods when the upper-level problem is nonconvex, and the lower-level problem is strongly convex. Recent works (Ji et al., ICML 2021; Arbel and Mairal, ICLR 2022; Chen et al., JMLR 2025) achieve a O~(κˉy4ε−2)\tilde{\mathcal{O}}(\bar κ_y^4 ε^{-2}) upper bound that is near-optimal in εε, which can be reduced to O~(κˉy7/2ε−2)\tilde{\mathcal{O}}(\bar κ_y^{7/2} ε^{-2}) by a naive application of Nesterov acceleration in the inner loop, where κˉy\bar κ_y is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new Ω(κy5/2ε−2)Ω(κ_y^{5/2} ε^{-2}) lower bound, where κy<κˉyκ_y < \bar κ_y is the lower-level condition number that is of the same order as κˉy\bar κ_y when the smoothness constants are O(1)\mathcal{O}(1). Our lower bound establishes the first provable gap in terms of condition number dependency between bilevel problems and minimax problems in this setup. Our lower bounds can be extended to various settings, including high-order smooth functions, stochastic oracles, and convex hyper-objectives: (1) For second-order and arbitrarily smooth problems, we show lower bounds of Ω(κy31/14ε−12/7)Ω({κ_y^{31/14}} ε^{-12/7}) and Ω(κy21/10ε−8/5)Ω(κ_y^{21/10} ε^{-8/5}), respectively. (2) For convex-strongly-convex problems, we improve the previously best lower bound (Ji and Liang, JMLR 2022) from Ω(κy/ε)Ω(κ_y /\sqrtε) to Ω(κy3/2/ε)Ω(κ_y^{3/2} / \sqrtε). (3) For smooth stochastic problems, we also show a lower bound of Ω(κy4ε−4)Ω(κ_y^4 ε^{-4}).
Nov 26, 2025

Bilevel Data Curation for LLM Fine-tuning: Offline Selection and Online Self-Refining Generation

Supervised fine-tuning (SFT) datasets are critical to the downstream performance of large language models, yet they often contain low-quality or harmful question-response pairs. To improve SFT data quality, we develop a unified bilevel framework that combines offline data selection with the online self-refining generation. In the offline setting, bilevel data selection (BDS) selects question-response pairs from the offline SFT dataset to maximize the validation performance. We theoretically show that the optimal model given by BDS outperforms direct data mixing approach in useful data coverage. Moreover, we provide a global convergence analysis for gradient-based BDS approach for one-layer Transformer, showing that the epsilon-global optimum of offline BDS is achievable in finite time. Although efficient, offline BDS discards potentially harmful questions together with responses, thereby reducing question diversity. We address this limitation by refining the responses to selected questions using online self-refining generation framework. However, BDS is inefficient to update the response weights when responses are regenerated online. To address this issue, we introduce bilevel multi-objective optimization (BMO) for response-level weighting. We show that BMO recovers the same validation-aligned solution as BDS, but admits a closed-form importance-ratio weight that adapts to regenerated responses. Experiments on LLM quality enhancement and safety-aware fine-tuning demonstrate that the proposed framework consistently improves both data quality and downstream fine-tuning performance.
Sep 26, 2025

OFMU: Optimization-Driven Framework for Machine Unlearning

Large language models deployed in sensitive applications increasingly require the ability to unlearn specific knowledge, such as user requests, copyrighted materials, or outdated information, without retraining from scratch to ensure regulatory compliance, user privacy, and safety. This task, known as machine unlearning, aims to remove the influence of targeted data (forgetting) while maintaining performance on the remaining data (retention). A common approach is to formulate this as a multi-objective problem and reduce it to a single-objective problem via scalarization, where forgetting and retention losses are combined using a weighted sum. However, this often results in unstable training dynamics and degraded model utility due to conflicting gradient directions. To address these challenges, we propose OFMU, a penalty-based bi-level optimization framework that explicitly prioritizes forgetting while preserving retention through a hierarchical structure. Our method enforces forgetting via an inner maximization step that incorporates a similarity-aware penalty to decorrelate the gradients of the forget and retention objectives, and restores utility through an outer minimization step. To ensure scalability, we develop a two-loop algorithm with provable convergence guarantees under both convex and non-convex regimes. We further provide a rigorous theoretical analysis of convergence rates and show that our approach achieves better trade-offs between forgetting efficacy and model utility compared to prior methods. Extensive experiments across vision and language benchmarks demonstrate that OFMU consistently outperforms existing unlearning methods in both forgetting efficacy and retained utility.
May 2, 2025

A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization

Bilevel optimization has recently attracted significant attention in machine learning due to its wide range of applications and advanced hierarchical optimization capabilities. In this paper, we propose a plug-and-play framework, named PnPBO, for developing and analyzing stochastic bilevel optimization methods. This framework integrates both modern unbiased and biased stochastic estimators into the single-loop bilevel optimization framework introduced in [9], with several improvements. In the implementation of PnPBO, all stochastic estimators for different variables can be independently incorporated, and an additional moving average technique is applied when using an unbiased estimator for the upper-level variable. In the theoretical analysis, we provide a unified convergence and complexity analysis for PnPBO, demonstrating that the adaptation of various stochastic estimators (including PAGE, ZeroSARAH, and mixed strategies) within the PnPBO framework achieves optimal sample complexity, comparable to that of single-level optimization. This resolves the open question of whether the optimal complexity bounds for solving bilevel optimization are identical to those for single-level optimization. Finally, we empirically validate our framework, demonstrating its effectiveness on several benchmark problems and confirming our theoretical findings.
Feb 5, 2025

Bilevel ZOFO: Efficient LLM Fine-Tuning and Meta-Training

Fine-tuning pre-trained Large Language Models (LLMs) for downstream tasks using First-Order (FO) optimizers presents significant computational challenges. Parameter-Efficient Fine-Tuning (PEFT) methods address these by freezing most model parameters and training only a small subset. However, PEFT often underperforms compared to full fine-tuning when high task-specific accuracy is required. Zeroth-Order (ZO) methods fine-tune the entire pre-trained model without back-propagation, estimating gradients through forward passes only. While memory-efficient, ZO methods suffer from slow convergence and high sensitivity to prompt selection. We bridge these two worlds with Bilevel-ZOFO, a bilevel optimization method that couples fast, local FO-PEFT adaptation at the inner level with stable, memory-efficient ZO updates of the full backbone at the outer level. The FO-PEFT inner loop performs fast, low-memory local adaptation that reduces the variance of ZO estimates and stabilizes the search, guiding the outer ZO updates of the full backbone and reducing prompt sensitivity. In the mean time, the outer ZO provides better generalization ability for PEFT. We provide theoretical convergence guarantees and empirically demonstrate that Bilevel-ZOFO significantly outperforms existing ZO and FO-PEFT methods, achieving 2-4 times faster training while maintaining similar memory efficiency. Additionally, we show by updating the backbone with ZO and adapting only a tiny FO-PEFT block per task, Bilevel-ZOFO combines full-model capacity with few-shot efficiency, making it a very efficient meta-learning algorithm that quickly adapts to new tasks.