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

• URL: http://arxiv.org/abs/2604.02888v1
• Date: Fri, 03 Apr 2026 08:55:23 GMT
• Title: Accelerating Black-Box Bilevel Optimization with Rank-Based Upper-Level Value Function Approximation
• Abstract summary: We propose an efficient framework that exploits rank-based evolutionary algorithms to monotonic iteration.<n>We demonstrate that our method achieves competitive performance on standard bilevel optimization benchmarks.
• Score: 4.026354668375411
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Mixed-Categorical Black-Box Optimization via Information-Geometric Bilevel Decomposition [4.50009116058958]
  Mixed categorical-continuous optimization arises in many practical domains, yet remains challenging.<n>We propose a bilevel optimization framework that explicitly captures such interactions by optimizing over categorical variables in an outer loop, and over continuous variables conditioned on each categorical configuration in an inner loop.<n> Experimental results on binary-continuous domain demonstrate that the proposed method outperforms existing state-of-the-art approaches in interaction-handling capability while also being more efficient across benchmarks encompassing both previously reported and newly proposed types of interaction.
  arXiv  Detail & Related papers  (2026-06-11T04:27:22Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  We propose a smooth variant of the min-max problem based on the augmented Lagrangian.<n>The proposed algorithm scales better with the number of objectives than subgradient-based strategies.
  arXiv  Detail & Related papers  (2025-03-16T11:05:51Z)
• Bayesian Optimization of Bilevel Problems [0.0]
  This paper focuses on bilevel optimization where both upper-level and lower-level functions are black boxes and expensive to evaluate.<n>We propose a Bayesian Optimization framework that models the upper and lower-level functions as Gaussian processes over the combined space of upper and lower-level decisions.<n>Our experimental results demonstrate that the proposed algorithm is highly sample-efficient and outperforms existing methods in finding high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-24T15:55:30Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
  This paper introduces a novel gradient-based approach for multilevel optimization. Our method significantly reduces computational complexity while improving both solution accuracy and convergence speed. To the best of our knowledge, this is one of the first algorithms to provide a general version of implicit differentiation.
  arXiv  Detail & Related papers  (2024-10-15T06:17:59Z)
• Pareto Set Prediction Assisted Bilevel Multi-objective Optimization [2.3293561091456283]
  We address problems with multiple objectives (BLMOP) at both levels. The proposed approach is competitive across a range of problems, including both deceptive and non-deceptive.
  arXiv  Detail & Related papers  (2024-09-05T08:04:11Z)
• Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
  We propose a new method for two-time-scale optimization that achieves significantly faster convergence than the prior arts.<n>We show how the proposed algorithm specializes to novel online sample-based methods that surpass or match the performance of the existing state of the art.
  arXiv  Detail & Related papers  (2024-05-15T19:03:08Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  We introduce contextual bilevel optimization (CSBO) -- a bilevel optimization framework with the lower-level problem minimizing an expectation on some contextual information and the upper-level variable. It is important for applications such as meta-learning, personalized learning, end-to-end learning, and Wasserstein distributionally robustly optimization with side information (WDRO-SI)
  arXiv  Detail & Related papers  (2023-10-27T23:24:37Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  We propose a bilevel optimization method based on Bregman Bregman functions. We also propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique.
  arXiv  Detail & Related papers  (2021-07-26T16:18:43Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.