Bilevel Optimization

Follow this topic Ask about this topic

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

88 papers12 papers in the last four weeks, up 20% on the four weeks before. 0.1% of all new papers.

May 8, 2026

Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

We study a class of bilevel optimization problems in which both the upper- and lower-level problems have minimax structures. This setting captures a broad range of emerging applications. Despite the extensive literature on bilevel optimization and minimax optimization separately, existing methods mainly focus on bilevel optimization with lower-level minimization problems, often under strong convexity assumptions, and are not directly applicable to the minimax lower-level setting considered here. To address this gap, we develop penalty-based first-order methods for bilevel minimax optimization without requiring strong convexity of the lower-level problem. In the deterministic setting, we establish that the proposed method finds an

ε

-KKT point with

\tilde{O}(ε^{-4})

oracle complexity. We further show that bilevel problems with convex constrained lower-level minimization can be reformulated as special cases of our framework via Lagrangian duality, leading to an

\tilde{O}(ε^{-4})

complexity bound that improves upon the existing

\tilde{O}(ε^{-7})

result. Finally, we extend our approach to the stochastic setting, where only stochastic gradient oracles are available, and prove that the proposed stochastic method finds a nearly

ε

-KKT point with

\tilde{O}(ε^{-9})

oracle complexity.

Yiyang Shen, Yutian He, Weiran Wang +1

University of Iowa

Min-Max Optimization Bilevel Optimization Constrained Optimization

May 8, 2026

When Losses Align: Gradient-Based Composite Loss Weighting for Efficient Pretraining

Modern deep models are often pretrained on large-scale data with missing labels using composite objectives, where the relative weights of multiple loss terms act as hyperparameters. Tuning these weights with random search or Bayesian optimization is computationally expensive, as it requires many independent training runs. To address this, we propose a gradient-based bilevel method that learns pretraining loss weights online by aligning the composite pretraining gradient with a downstream objective. By exploiting the structure of the loss, the method avoids the multiple backward passes typically required by truncated backpropagation through the full model, reducing the overhead of hyperparameter tuning to approximately 30% above a single training run. We evaluate the approach on event-sequence modeling and self-supervised computer vision, where it matches or improves upon carefully tuned baselines while substantially reducing the cost of hyperparameter tuning compared to random or Bayesian search.

Ivan Karpukhin, Andrey Savchenko

Sber AI Lab · HSE University ISP RAS Research Center for Trusted Artificial Intelligence

Self-Supervised Pre-Training Adaptive Loss Weighting Bilevel Optimization Hyperparameter Optimization

May 8, 2026

Differentially Private Auditing Under Strategic Response

Regulatory audits of AI systems increasingly rely on differential privacy (DP) to protect training data and model internals. We study audit design when the audited developer can strategically respond to the privacy-constrained audit interface. We formalize privacy-constrained auditing as a bilevel Stackelberg game, in which an auditor commits to a query policy and DP budget allocation across harm dimensions, and a strategic developer reallocates mitigation efforts in response. We introduce the welfare-weighted under-detection gap

B_w

, the welfare-weighted true residual harm the audit fails to detect at the developer's strategic best response, and prove that naive DP auditing (uniform or harm-proportional allocation) induces a strictly larger

B_w

than any non-strategic mitigation baseline whenever effective detectability is heterogeneous, the welfare weights are not comonotone with detectability, and the developer's optimum is interior. We characterize the optimal auditor allocation as a four-factor balance of welfare weight, audit miss-probability, detectability elasticity, and mitigation-cost curvature, and provide a single-level reformulation of the bilevel problem via the developer's KKT system. We propose Strategic Private Audit Design (SPAD), a projected-gradient algorithm with hypergradients computed through the developer's best response.

Florian A. D. Burnat

University of Bath

Privacy Auditing Algorithmic Auditing Bilevel Optimization Differential Privacy

May 8, 2026

Bilevel Graph Structure Learning, Revisited: Inner-Channel Origins of the Reported Gain

Bilevel graph structure learning is widely understood to improve graph neural networks by jointly optimizing model parameters and a learned graph structure, with the resulting performance gain attributed to the rewired adjacency. We find that this attribution may be overstated: training-dynamics effects in the inner loop, rather than the rewiring itself, capture a substantial share of the gain. To establish this, we introduce frozen-

φ

, a control that freezes the graph while retaining the inner-loop training schedule. This decomposes the bilevel gain into an inner channel of

T

-step training dynamics with implicit gradient regularization and a graph channel of the graph rewiring itself. On spatio-temporal flow forecasting the inner channel matches or exceeds the full bilevel pipeline, accounting for 78-101% of the gain; on node classification it accounts for 37-44% under a Bernoulli edge-level parameterization. We also verify that classical spectral diagnostics can dissociate from task gain. We propose frozen-

φ

as a standardized diagnostic for bilevel graph structure learning, with graph distillation as a method-agnostic complement. A three-precondition framework further predicts the sign of the bilevel gain on all six benchmarks.

Minkyoung Kim, Beakcheol Jang

Graduate School of Information, Yonsei University

Graph Structure Learning Graph Neural Networks Bilevel Optimization Neural Network Training Dynamics

May 7, 2026

Constrained Triple-Head Price Optimization (C3PO) Network for Discrete-Choice Models

We propose a Constrained Triple-Head Price Optimization (C3PO) network for real-time bi-level decision making in discrete-choice environments. In these settings, a seller selects product or service offerings to achieve business objectives, while heterogeneous users make personalized acceptance or rejection decisions based on their preferences, ultimately determining seller outcomes. Existing approaches that fine-tune pre-trained tabular foundation models on synthetic data are limited by their imitation-learning paradigm and inability to enforce common pricing rules, including cross-product and global constraints. C3PO addresses these limitations through a novel transformer-based architecture that jointly integrates price imitation learning, multi-task revenue prediction, and in-context elasticity learning to generate robust pricing recommendations across domains without retraining. A lightweight differentiable constraint layer enables generated prices to satisfy business constraints while optimizing the revenue objective. We demonstrate strong out-of-distribution performance on simulated, synthetic, and real-world datasets. Across simulated benchmarks where the calibrated MNL model is misspecified relative to the ground-truth choice model, C3PO improves expected revenue by 1.4 to 7.9 percentage points over a calibrated MNL baseline. The constraint layer reduces average absolute constraint violations by more than 50%. We further deploy the model in real-world applications, including healthcare tender pricing and airline ancillary pricing, where C3PO improves directional pricing effectiveness, measured by price-increase and price-decrease recall, by 18--34 percentage points depending on the baselines considered, including calibrated MNL, classical optimization, and off-the-shelf tabular foundation-models.

Shivaram Subramanian, Zhengliang Xue, Markus Ettl +2

IBM T.J. Watson Research Center Yorktown Heights, New York, 10598, U.S.A.

Large Language Model-Guided Optimization Discrete Choice Modeling Bilevel Optimization Dynamic Pricing

May 7, 2026

One Algorithm, Two Goals: Dual Scoring for Parameter and Data Selection in LLM Fine-Tuning

In Large Language Model (LLM) fine-tuning, parameter and data selection are common strategies for reducing fine-tuning cost, yet they are typically driven by separate scoring mechanisms. When a parameter mask and data subset jointly determine restricted fine-tuning, this separation incurs redundant overhead and makes coordinated selection difficult. We cast parameter and data selection as two bilevel selection problems under a common validation objective and derive a shared local response-surrogate scoring rule. Under first- and second-order validation-improvement approximations, parameter importance and data utility emerge as column-wise and row-wise aggregations of a single gradient interaction matrix, yielding a closed-form row-column correspondence for co-extracting both signals. Building on this structure, we propose DualSFT (Dual-Selection Fine-Tuning), a one-shot dual-scoring algorithm that produces a parameter mask and data subset from shared gradient statistics. On 3B-9B LLMs, single-axis DualSFT variants strengthen target-task performance and stability-plasticity trade-offs within their comparison groups, while full DualSFT yields a more favorable joint-constrained trade-off than sequential hybrid baselines under matched budgets.

Xinrui Chen, Liu Yang, Ou Wu

Hangzhou Institute for Advanced Study, University of Chinese Academy of Sciences · College of Intelligence and Computing, Tianjin University

Supervised Fine-Tuning LLM Fine-Tuning Bilevel Optimization Selective Fine-Tuning Data Selection for Language Model Fine-Tuning Parameter-Efficient Fine-Tuning

Apr 24, 2026

Adversarial Co-Evolution of Malware and Detection Models: A Bilevel Optimization Perspective

Machine learning-based malware detectors are increasingly vulnerable to adversarial examples. Traditional defenses, such as one-shot adversarial training, often fail against adaptive attackers who use reinforcement learning to bypass detection. This paper proposes a robust defense framework based on bilevel optimization, explicitly modeling the strategic interaction between a defender and an attacker as an adversarial co-evolutionary process. We evaluate our approach using the MAB-malware framework against three distinct malware families: Mokes, Strab, and DCRat. Our experimental results demonstrate that while standard classifiers and basic adversarial retraining often remain vulnerable, showing evasion rates as high as 90 %, the proposed bilevel optimization approach consistently achieves near-total immunity, reducing evasion rates to 0 - 1.89 %. Furthermore, the iterative framework significantly increases the attacker's query complexity, raising the average cost of successful evasion by up to two orders of magnitude. These findings suggest that modeling the iterative cycle of attack and defense through bilevel optimization is essential for developing resilient malware detection systems capable of withstanding evolving adversarial threats.

Olha Jurečková, Martin Jureček, Matouš Kozák +1

Faculty of Information Technology, Czech Technical University in Prague, Th´akurova 9, Prague, 16000, Czech Republic

Adversarial Attacks Adversarial Robustness Bilevel Optimization Malware Analysis Malware Detection

Apr 22, 2026

On the Stability and Generalization of First-order Bilevel Minimax Optimization

Bilevel optimization and bilevel minimax optimization have recently emerged as unifying frameworks for a range of machine-learning tasks, including hyperparameter optimization and reinforcement learning. The existing literature focuses on empirical efficiency and convergence guarantees, leaving a critical theoretical gap in understanding how well these algorithms generalize. To bridge this gap, we provide the first systematic generalization analysis for first-order gradient-based bilevel minimax solvers with lower-level minimax problems. Specifically, by leveraging algorithmic stability arguments, we derive fine-grained generalization bounds for three representative algorithms, including single-timescale stochastic gradient descent-ascent, and two variants of two-timescale stochastic gradient descent-ascent. Our results reveal a precise trade-off among algorithmic stability, generalization gaps, and practical settings. Furthermore, extensive empirical evaluations corroborate our theoretical insights on realistic optimization tasks with bilevel minimax structures.

Xuelin Zhang, Peipei Yuan

College of Informatics, Huazhong Agricultural University, Wuhan, 430070, China · School of Artificial Intelligence, Jianghan University, Wuhan, 430056, China

Min-Max Optimization Bilevel Optimization Stochastic Gradient Descent Generalization Bounds Stochastic Bilevel Optimization Algorithmic Generalization

Apr 17, 2026

Bilevel Optimization of Agent Skills via Monte Carlo Tree Search

Agent skills are structured collections of instructions, tools, and supporting resources that help large language model (LLM) agents perform particular classes of tasks. Empirical evidence shows that the design of skills can materially affect agent task performance, yet systematically optimizing skills remains challenging. Since a skill comprises instructions, tools, and supporting resources in a structured way, optimizing it requires jointly determining both the structure of these components and the content each component contains. This gives rise to a complex decision space with strong interdependence across structure and components. We therefore represent these two coupled decisions as skill structure and component content, and formulate skill optimization as a bilevel optimization problem. We propose a bilevel optimization framework in which an outer loop employs Monte Carlo Tree Search to determine the skill structure, while an inner loop refines the component content within the structure selected by the outer loop. In both loops, we employ LLMs to assist the optimization procedure. We evaluate the proposed framework on an open-source Operations Research Question Answering dataset, and the experimental results suggest that the bilevel optimization framework improves the performance of the agents with the optimized skill.

Chenyi Huang, Haoting Zhang, Jingxu Xu +2

Department of Mathematics National University of Singapore Singapore · Department of Industrial Engineering and Operations Research University of California at Berkeley CA, USA · Department of Decision, Operation and Technology The Chinese University of Hong Kong CHINA

Large Language Model-Guided Optimization LLM Agent Skill Learning Bilevel Optimization

Apr 14, 2026

Bilevel Late Acceptance Hill Climbing for the Electric Capacitated Vehicle Routing Problem

This paper tackles the Electric Capacitated Vehicle Routing Problem (E-CVRP) through a bilevel optimization framework that handles routing and charging decisions separately or jointly depending on the search stage. By analyzing their interaction, we introduce a surrogate objective at the upper level to guide the search and accelerate convergence. A bilevel Late Acceptance Hill Climbing algorithm (b-LAHC) is introduced that operates through three phases: greedy descent, neighborhood exploration, and final solution refinement. b-LAHC operates with fixed parameters, eliminating the need for complex adaptation while remaining lightweight and effective. Extensive experiments on the IEEE WCCI-2020 benchmark show that b-LAHC achieves superior or competitive performance against eight state-of-the-art algorithms. Under a fixed evaluation budget, it attains near-optimal solutions on small-scale instances and sets 9/10 new best-known results on large-scale benchmarks, improving existing records by an average of 1.07%. Moreover, the strong correlation (though not universal) observed between the surrogate objective and the complete cost justifies the use of the surrogate objective while still necessitating a joint solution of both levels, thereby validating the effectiveness of the proposed bilevel framework and highlighting its potential for efficiently solving large-scale routing problems with a hierarchical structure.

Yinghao Qin, Mosab Bazargani, Edmund K. Burke +3

Centre for Intelligent Transport, QMUL, London, U.K. · School of Computer Science and Engineering, Bangor University, Bangor, U.K. · Department of Computer Science, Evolutionary Computation Group, CINVESTAV-IPN, Mexico City, Mexico. +2

Vehicle Routing Bilevel Optimization Electric Vehicle Charging

Apr 14, 2026

BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design

Large Language Model-based Hyper Heuristic (LHH) has recently emerged as an efficient way for automatic heuristic design. However, most existing LHHs just perform well in optimizing a single function within a pre-defined solver. Their single-layer evolution makes them not effective enough to write a competent complete solver. While some variants incorporate hyperparameter tuning or attempt to generate complex code through iterative local modifications, they still lack a high-level algorithmic modeling, leading to limited exploration efficiency. To address this, we reformulate heuristic design as a Bi-level Optimization problem and propose BEAM (Bi-level Memory-adaptive Algorithmic Evolution). BEAM's exterior layer evolves high-level algorithmic structures with function placeholders through genetic algorithm (GA), while the interior layer realizes these placeholders via Monte Carlo Tree Search (MCTS). We further introduce an Adaptive Memory module to facilitate complex code generation. To support the evaluation for complex code generation, we point out the limitations of starting LHHs from scratch or from code templates and introduce a Knowledge Augmentation (KA) Pipeline. Experimental results on several optimization problems demonstrate that BEAM significantly outperforms existing LHHs, notably reducing the optimality gap by 37.84% on aggregate in CVRP hybrid algorithm design. BEAM also designs a heuristic that outperforms SOTA Maximum Independent Set (MIS) solver KaMIS.

Chuyang Xiang, Yichen Wei, Jiale Ma +2

Automated Heuristic Design Large Language Model-Guided Optimization Bilevel Optimization

Apr 8, 2026

Differentiable Environment-Trajectory Co-Optimization for Safe Multi-Agent Navigation

The environment plays a critical role in multi-agent navigation by imposing spatial constraints, rules, and limitations that agents must navigate around. Traditional approaches treat the environment as fixed, without exploring its impact on agents' performance. This work considers environment configurations as decision variables, alongside agent actions, to jointly achieve safe navigation. We formulate a bi-level problem, where the lower-level sub-problem optimizes agent trajectories that minimize navigation cost and the upper-level sub-problem optimizes environment configurations that maximize navigation safety. We develop a differentiable optimization method that iteratively solves the lower-level sub-problem with interior point methods and the upper-level sub-problem with gradient ascent. A key challenge lies in analytically coupling these two levels. We address this by leveraging KKT conditions and the Implicit Function Theorem to compute gradients of agent trajectories w.r.t. environment parameters, enabling differentiation throughout the bi-level structure. Moreover, we propose a novel metric that quantifies navigation safety as a criterion for the upper-level environment optimization, and prove its validity through measure theory. Our experiments validate the effectiveness of the proposed framework in a variety of safety-critical navigation scenarios, inspired from warehouse logistics to urban transportation. The results demonstrate that optimized environments provide navigation guidance, improving both agents' safety and efficiency.

Zhan Gao, Gabriele Fadini, Stelian Coros +1

Department of Computer Science and Technology, University of Cambridge, UK · Zurich University of Applied Sciences, ZHAW, Winterthur, Swizerland · Computational Robotics Lab, Department of Computer Science, ETH Zurich, Switzerland

Robot Navigation Safe Robot Navigation Multi-Robot Motion Planning Trajectory Optimization Bilevel Optimization

Apr 5, 2026

Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization

Stochastic bilevel optimization (SBO) has been integrated into many machine learning paradigms recently, including hyperparameter optimization, meta learning, and reinforcement learning. Along with the wide range of applications, there have been numerous studies on the computational behavior of SBO. However, the generalization guarantees of SBO methods are far less understood from the lens of statistical learning theory. In this paper, we provide a systematic generalization analysis of the first-order gradient-based bilevel optimization methods. Firstly, we establish the quantitative connections between the on-average argument stability and the generalization gap of SBO methods. Then, we derive the upper bounds of on-average argument stability for single-timescale stochastic gradient descent (SGD) and two-timescale SGD, where three settings (nonconvex-nonconvex (NC-NC), convex-convex (C-C), and strongly-convex-strongly-convex (SC-SC)) are considered respectively. Experimental analysis validates our theoretical findings. Compared with the previous algorithmic stability analysis, our results do not require reinitializing the inner-level parameters at each iteration and are applicable to more general objective functions.

Xuelin Zhang, Hong Chen, Bin Gu +2

College of Informatics, Huazhong Agricultural University, Wuhan 430070, China · Engineering Research Center of Intelligent Technology for Agriculture, Ministry of Education, Wuhan 430070, China · School of Artificial Intelligence, Jilin University, Jilin 130012, China +2

Stochastic Bilevel Optimization Bilevel Optimization Generalization Bounds Algorithmic Stability Stochastic Gradient Descent

Apr 3, 2026

Accelerating Black-Box Bilevel Optimization with Rank-Based Upper-Level Value Function Approximation

Bilevel optimization is a field of significant theoretical and practical interest, yet solving such optimization problems remains challenging. Evolutionary methods have been employed to address these problems in the black-box setting; however, they incur high computational cost due to the nested nature of bilevel optimization. Although previous methods have attempted to reduce this cost through various heuristic techniques, such approaches limit versatility on challenging optimization landscapes, such as those with multimodality and significant interaction between upper- and lower-level decision variables. In this study, we propose an efficient framework that exploits the invariance of rank-based evolutionary algorithms to monotonic transformations, thereby reducing the computational burden of the lower-level optimization loop. Specifically, our method directly approximates the rankings of the upper-level value function, bypassing the need to run the lower-level optimizer until convergence for each upper-level iteration. We apply this framework to the setting where both levels are continuous, adopting CMA-ES as the optimizer. We demonstrate that our method achieves competitive performance on standard bilevel optimization benchmarks and can solve problems that are intractable with previously proposed methods, particularly those with multimodality and strong inter-variable interactions.

Marc Ong, Youhei Akimoto

University of Tsukuba Tsukuba, Ibaraki, JAPAN · University of Tsukuba & RIKEN AIP Tsukuba, Ibaraki, JAPAN

Bilevel Optimization Black-Box Optimization Evolutionary Optimization Surrogate-Assisted Optimization

Mar 31, 2026

Efficient Bilevel Optimization with KFAC-Based Hypergradients

Bilevel optimization (BO) is widely applicable to many machine learning problems. Scaling BO, however, requires repeatedly computing hypergradients, which involves solving inverse Hessian-vector products (IHVPs). In practice, these operations are often approximated using crude surrogates such as one-step gradient unrolling or identity/short Neumann expansions, which discard curvature information. We build on implicit function theorem-based algorithms and propose to incorporate Kronecker-factored approximate curvature (KFAC), yielding curvature-aware hypergradients with a better performance efficiency trade-off than Conjugate Gradient (CG) or Neumann methods and consistently outperforming unrolling. We evaluate this approach across diverse tasks, including meta-learning and AI safety problems. On models up to BERT, we show that curvature information is valuable at scale, and KFAC can provide it with only modest memory and runtime overhead. Our implementation is available at https://github.com/liaodisen/NeuralBo.

Disen Liao, Felix Dangel, Yaoliang Yu

University of Waterloo · Vector Institute

Kronecker-Factored Approximation Bilevel Optimization Hypergradient Optimization Differentiable Optimization Curvature-Aware Optimization Second-Order Optimization

Mar 24, 2026

Bilevel Autoresearch: Meta-Autoresearching Itself

If autoresearch is itself a form of research, then autoresearch can be applied to research itself. We present Bilevel Autoresearch, a bilevel framework in which an outer autoresearch loop improves an inner autoresearch loop by reading its code and traces, identifying bottlenecks, and generating injectable Python search mechanisms at runtime. The inner loop optimizes task performance; the outer loop optimizes how the inner loop searches. Both loops use the same LLM, so improvements come from the bilevel architecture rather than a stronger meta-level model, although the outer loop consumes additional inference and wall-clock budget. On Karpathy's GPT pretraining benchmark, the meta-autoresearch outer loop achieves a 5x improvement over the standard inner loop alone (-0.045 vs. -0.009 val_bpb), while parameter-level adjustment without mechanism change yields no reliable gain. The outer loop instantiates mechanisms from adjacent search domains, including combinatorial optimization, multi-armed bandits, and design of experiments, without human specification of the final mechanism design. Trace analysis suggests that these mechanisms break deterministic search patterns and force exploration of directions the LLM's priors avoid. The experiments demonstrate, on this benchmark, a first bilevel step: an outer loop improves the search behavior of an inner loop. Code is the mechanism carrier in this implementation, but skills, prompts, workflows, evaluators, domain principles, world-model assumptions, and memory schemas can also encode mechanisms that shape future agent behavior. This suggests a path toward recursive bootstrapping, where mechanisms discovered for the inner loop can be fed back to improve the meta-level loop itself.

Yaonan Qu, Meng Lu

Independent Researcher

Self-Improving Agents Autonomous Research Agents Large Language Model-Guided Optimization Automated Algorithm Discovery Bilevel Optimization

Mar 23, 2026

Strategic Infrastructure Design via Multi-Agent Congestion Games with Joint Placement and Pricing

Real-world infrastructure planning increasingly involves strategic interactions among autonomous agents competing over congestible, limited resources. Applications such as Electric Vehicle (EV) charging, emergency response, and intelligent transportation require coordinated resource placement and pricing decisions, while anticipating the adaptive behaviour of decentralised, self-interested agents. We propose a novel multi-agent framework for joint placement and pricing under such interactions, formalised as a bi-level optimisation model. The upper level represents a central planner, while the lower level captures agent responses via coupled non-atomic congestion games. Motivated by the EV charging domain, we study a setting where a central planner provisions chargers and road capacity under budget and profitability constraints. The agent population includes both EV drivers and non-charging drivers (NCDs), who respond to congestion, delays, and costs. To solve the resulting NP-hard problem, we introduce ABO-MPN, a double-layer approximation framework that decouples agent types, applies integer adjustment and rounding, and targets high-impact placement and pricing decisions. Experiments on benchmark networks show that our model reduces social cost by up to 40% compared to placement- or pricing-only baselines, and generalises to other MAS-relevant domains.

Niloofar Aminikalibar, Farzaneh Farhadi, Maria Chli

Aston University, Birmingham, UK, B4 7ET

Congestion Games Multi-Agent System Optimization Game Theory Bilevel Optimization

Mar 16, 2026

Efficient Morphology-Control Co-Design via Stackelberg Proximal Policy Optimization

Morphology-control co-design concerns the coupled optimization of an agent's body structure and control policy. This problem exhibits a bi-level structure, where the control dynamically adapts to the morphology to maximize performance. Existing methods typically neglect the control's adaptation dynamics by adopting a single-level formulation that treats the control policy as fixed when optimizing morphology. This can lead to inefficient optimization, as morphology updates may be misaligned with control adaptation. In this paper, we revisit the co-design problem from a game-theoretic perspective, modeling the intrinsic coupling between morphology and control as a novel variant of a Stackelberg game. We propose Stackelberg Proximal Policy Optimization (Stackelberg PPO), which explicitly incorporates the control's adaptation dynamics into morphology optimization. By modeling this intrinsic coupling, our method aligns morphology updates with control adaptation, thereby stabilizing training and improving learning efficiency. Experiments across diverse co-design tasks demonstrate that Stackelberg PPO outperforms standard PPO in both stability and final performance, opening the way for dramatically more efficient robotics designs.

Yanning Dai, Yuhui Wang, Dylan R. Ashley +1

Center of Excellence for Generative AI, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia. · Dalle Molle Institute for Artificial Intelligence Research (IDSIA), Lugano, Switzerland. · Università della Svizzera italiana (USI), Lugano, Switzerland. +1

Robot Morphology-Control Co-Design Bilevel Optimization Proximal Policy Optimization

Mar 8, 2026

Feed m Birds with One Scone: Accelerating Multi-task Gradient Balancing via Bi-level Optimization

In machine learning, the goal of multi-task learning (MTL) is to optimize multiple objectives together. Recent works, for example, Multiple Gradient Descent Algorithm (MGDA) and its variants, show promising results with dynamically adjusted weights for different tasks to mitigate conflicts that may potentially degrade the performance on certain tasks. Despite the empirical success of MGDA-type methods, one major limitation of such methods is their computational inefficiency, as they require access to all task gradients. In this paper we introduce MARIGOLD, a unified algorithmic framework for efficiently solving MTL problems. Our method reveals that multi-task gradient balancing methods have a hierarchical structure, in which the model training and the gradient balancing are coupled during the whole optimization process and can be viewed as a bi-level optimization problem. Moreover, we showcase that the bi-level problem can be solved efficiently by leveraging zeroth-order method. Extensive experiments on both public datasets and industrial-scale datasets demonstrate the efficiency and superiority of our method.

Xuxing Chen, Yun He, Jiayi Xu +9

Meta

Multi-Task Learning Bilevel Optimization

Feb 27, 2026

Bi-level RL-Heuristic Optimization for Real-world Winter Road Maintenance

Winter road maintenance is critical for ensuring public safety and reducing environmental impacts, yet existing methods struggle to manage large-scale routing problems effectively and mostly reply on human decision. This study presents a novel, scalable bi-level optimization framework, validated on real operational data on UK strategic road networks (M25, M6, A1), including interconnected local road networks in surrounding areas for vehicle traversing, as part of the highway operator's efforts to solve existing planning challenges. At the upper level, a reinforcement learning (RL) agent strategically partitions the road network into manageable clusters and optimally allocates resources from multiple depots. At the lower level, a multi-objective vehicle routing problem (VRP) is solved within each cluster, minimizing the maximum vehicle travel time and total carbon emissions. Unlike existing approaches, our method handles large-scale, real-world networks efficiently, explicitly incorporating vehicle-specific constraints, depot capacities, and road segment requirements. Results demonstrate significant improvements, including balanced workloads, reduced maximum travel times below the targeted two-hour threshold, lower emissions, and substantial cost savings. This study illustrates how advanced AI-driven bi-level optimization can directly enhance operational decision-making in real-world transportation and logistics.

Yue Xie, Zizhen Xu, William Beazley +1

School of Science, Loughborough University, UK · Department of Engineering, University of Cambridge, UK · National Highways, 199 Wharfside St, Birmingham B1 1RN, UK

Vehicle Routing Bilevel Optimization RL for Combinatorial Optimization

Feb 27, 2026

On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation

Stochastic Bilevel Optimization has emerged as a fundamental framework for meta-learning and hyperparameter optimization. Despite the practical prevalence of single-loop algorithms, their theoretical understanding in the stochastic regime remains less developed than that of multi-loop methods. In this paper, we provide a refined convergence analysis of the Single-loop Stochastic Approximate Implicit Differentiation (SSAID) algorithm. Under the squared-gradient stationarity criterion

\|\nablaΦ(x)\|^2\leε

, the corrected proof establishes an oracle complexity of

\mathcal{O}(κ^{14}ε^{-2})

, equivalently an averaged stationarity rate of

\mathcal{O}(κ^7K^{-1/2})

. The result preserves the canonical

\mathcal{O}(ε^{-2})

dependence on the target accuracy while giving an explicit characterization of the condition-number dependence for stochastic AID-based single-loop methods.

Yubo Zhou, Luo Luo, Guang Dai +1

Xi’an Jiaotong University · Fudan University · SGIT AI Lab

Stochastic Bilevel Optimization Implicit Differentiation Bilevel Optimization Stochastic Optimization Convergence

Feb 23, 2026

Less is More: Convergence Benefits of Fewer Data Weight Updates over Longer Horizon

Data mixing--the strategic reweighting of training domains--is a critical component in training robust machine learning models. This problem is naturally formulated as a bilevel optimization task, where the outer loop optimizes domain weights to minimize validation loss, and the inner loop optimizes model parameters to minimize the weighted training loss. Classical bilevel optimization relies on hypergradients, which theoretically require the inner optimization to reach convergence. However, due to computational constraints, state-of-the-art methods use a finite, often small, number of inner update steps before updating the weights. The theoretical implications of this approximation are not well understood. In this work, we rigorously analyze the convergence behavior of data mixing with a finite number of inner steps

T

. We prove that the "greedy" practical approach of using

T=1

can fail even in a simple quadratic example. Under a fixed parameter update budget

N

and assuming the per-domain losses are strongly convex, we show that the optimal

T

scales as

Θ(\log N)

(resp.,

Θ({(N \log N)}^{1/2})

) for the data mixing problem with access to full (resp., stochastic) gradients. We complement our theoretical results with proof-of-concept experiments.

Rudrajit Das, Neel Patel, Meisam Razaviyayn +1

Google Research · EPFL · University of Southern California

Data Mixture Optimization Bilevel Optimization Stochastic Optimization

Feb 20, 2026

Understanding the Generalization of Bilevel Programming in Hyperparameter Optimization: A Tale of Bias-Variance Decomposition

Gradient-based hyperparameter optimization (HPO) have emerged recently, leveraging bilevel programming techniques to optimize hyperparameter by estimating hypergradient w.r.t. validation loss. Nevertheless, previous theoretical works mainly focus on reducing the gap between the estimation and ground-truth (i.e., the bias), while ignoring the error due to data distribution (i.e., the variance), which degrades performance. To address this issue, we conduct a bias-variance decomposition for hypergradient estimation error and provide a supplemental detailed analysis of the variance term ignored by previous works. We also present a comprehensive analysis of the error bounds for hypergradient estimation. This facilitates an easy explanation of some phenomena commonly observed in practice, like overfitting to the validation set. Inspired by the derived theories, we propose an ensemble hypergradient strategy to reduce the variance in HPO algorithms effectively. Experimental results on tasks including regularization hyperparameter learning, data hyper-cleaning, and few-shot learning demonstrate that our variance reduction strategy improves hypergradient estimation. To explain the improved performance, we establish a connection between excess error and hypergradient estimation, offering some understanding of empirical observations.

Yubo Zhou, Jun Shu, Junmin Liu +1

School of Mathematics and Statistics and Ministry of Education Key Lab of Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an, 100190, Shaan’xi Province, P. R. China. · Pazhou Lab (Huangpu), Street, Guangzhou, Guangdong Province, P. R. China.

Hypergradient Optimization Hyperparameter Optimization Bilevel Optimization Variance Reduction Differentiable Optimization

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.

Jason Bohne, Ieva Petrulionyte, Michael Arbel +2

Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY, USA · Inria, CNRS, Grenoble INP, LJK, Université Grenoble Alpes

Bilevel Optimization Hyperparameter Optimization Stochastic Bilevel Optimization

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

\tilde{\mathcal{O}}(\bar κ_y^4 ε^{-2})

upper bound that is near-optimal in

ε

, which can be reduced to

\tilde{\mathcal{O}}(\bar κ_y^{7/2} ε^{-2})

by a naive application of Nesterov acceleration in the inner loop, where

\bar κ_y

is the global condition number. However, the optimal dependency on the condition number is unknown. In this work, we establish a new

Ω(κ_y^{5/2} ε^{-2})

lower bound, where

κ_y < \bar κ_y

is the lower-level condition number that is of the same order as

\bar κ_y

when the smoothness constants are

\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

Ω({κ_y^{31/14}} ε^{-12/7})

and

Ω(κ_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 /\sqrtε)

to

Ω(κ_y^{3/2} / \sqrtε)

. (3) For smooth stochastic problems, we also show a lower bound of

Ω(κ_y^4 ε^{-4})

.

Lesi Chen, Jingzhao Zhang

IIIS, Tsinghua University

Oracle Complexity Nonconvex Optimization Bilevel Optimization

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.

Quan Xiao, Yutong Xuan, Gaowen Liu +2

Cornell University · Cisco Research

Supervised Fine-Tuning LLM Self-Refinement LLM Fine-Tuning Bilevel Optimization Data Selection for Language Model Fine-Tuning

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.

Sadia Asif, Mohammad Mohammadi Amiri

Rensselaer Polytechnic Institute

Bilevel Optimization Machine Unlearning Multi-Objective Optimization LLM Unlearning

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.

Tianshu Chu, Dachuan Xu, Wei Yao +2

Institute of Operations Research and Information Engineering, Beijing University of Technology · National Center for Applied Mathematics Shenzhen · National Center for Applied Mathematics Shenzhen, and Department of Mathematics, Southern University of Science and Technology +2

Stochastic Bilevel Optimization Bilevel Optimization Stochastic Optimization Convergence