Similarity-based Portfolio Construction for Black-box Optimization

• URL: http://arxiv.org/abs/2604.18196v1
• Date: Mon, 20 Apr 2026 12:48:28 GMT
• Title: Similarity-based Portfolio Construction for Black-box Optimization
• Abstract summary: A natural remedy is to split the evaluation budget across multiple runs of potentially different algorithms.<n>We show that a naive portfolio constructed over the full training set already outperforms the strongest traditional baseline.<n>We then propose a simple yet effective k-nearest-neighbor-based finetuning approach to construct portfolios tailored to unseen instances.
• Score: 0.13764085113103217
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In black-box optimization, a central question is which algorithm to use to solve a given, previously unseen, problem. Selecting a single algorithm, however, entails inherent risks: inaccuracies in the selector may lead to poor choices, and even well-performing algorithms with high variance can yield unsatisfactory results in a single run. A natural remedy is to split the evaluation budget across multiple runs of potentially different algorithms. Such sequential algorithm portfolios benefit from variance reduction and complementarities between algorithms, often outperforming approaches that allocate the entire budget to a single solver. While effective portfolios can be constructed post-hoc, transferring this idea to the algorithm selection setting is non-trivial. We show that a naive portfolio constructed over the full training set already outperforms the strongest traditional baseline, the virtual best solver. We then propose a simple yet effective k-nearest-neighbor-based finetuning approach to construct portfolios tailored to unseen instances, yielding further improvements and highlighting the effectiveness of portfolio selection in fixed-budget black-box optimization.

Related papers

• How Sequential Algorithm Portfolios can benefit Black Box Optimization [0.13764085113103217]
  We show that splitting the budget across several algorithms yield significantly better results.<n>This approach benefits from both algorithm complementarity across diverse problems and variance reduction within individual functions.
  arXiv  Detail & Related papers  (2026-01-23T17:02:22Z)
• Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems [0.0]
  We present a scheduling approach that iteratively selects the algorithm performing best on the distribution of unsolved training problems at time of selection, resulting in a problem-independent solver schedule.<n>We demonstrate our approach using well-knowns from numerical black-box optimization on the BBOB testbed, bridging much of the gap between single and virtual best solver from the original portfolio across various evaluation protocols.
  arXiv  Detail & Related papers  (2025-04-15T17:54:21Z)
• On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting [0.0]
  This paper argues the importance of considering the number of function evaluations used in the sampling phase when constructing algorithm portfolios. The results show that algorithm portfolios constructed by our approach perform significantly better than those by the previous approach.
  arXiv  Detail & Related papers  (2024-05-13T03:31:13Z)
• PS-AAS: Portfolio Selection for Automated Algorithm Selection in Black-Box Optimization [4.842307002343618]
  The performance of automated algorithm selection depends on the portfolio of algorithms to choose from. In practice, probably the most common way to choose the algorithms for the portfolio is a greedy selection of the algorithms that perform well in some reference tasks of interest. Our proposed method creates algorithm behavior meta-representations, constructs a graph from a set of algorithms based on their meta-representation similarity, and applies a graph algorithm to select a final portfolio of diverse, representative, and non-redundant algorithms.
  arXiv  Detail & Related papers  (2023-10-14T12:13:41Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization [0.0]
  Feature-based algorithm selection aims to automatically find the best one from a portfolio of optimization algorithms on an unseen problem. This paper analyzes algorithm selection systems on the 24 noiseless black-box optimization benchmarking functions. We show that the performance of algorithm selection systems can be significantly improved by using sequential least squares programming as a pre-solver.
  arXiv  Detail & Related papers  (2021-09-17T07:17:40Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  Batch policy optimization considers leveraging existing data for policy construction before interacting with an environment. We show that any confidence-adjusted index algorithm is minimax optimal, whether it be optimistic, pessimistic or neutral. We introduce a new weighted-minimax criterion that considers the inherent difficulty of optimal value prediction.
  arXiv  Detail & Related papers  (2021-04-06T05:23:20Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)

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.