Overview

Black-box optimization studies how to choose inputs that maximize or minimize an objective when its internal workings or gradients are unavailable, often because each evaluation is costly. Common approaches include Gaussian-process Bayesian optimization, evolutionary strategies such as CMA-ES and differential evolution, and bandit or partitioning methods that balance exploration with refinement. Surrogate models, multi-fidelity evaluations, and learned or generative proposals extend these methods to noisy, constrained, discrete, and high-dimensional tasks, including scientific design and system tuning. Benchmarks such as COCO/BBOB and CEC help compare methods, but performance often depends on the problem and evaluation budget, leaving robust transfer and fair comparisons across settings as central challenges.

Latest papers

193 papers16 papers in the last four weeks, down 48% on the four weeks before. 0.1% of all new papers.

Jan 13, 2026

Amortized Acquisition Optimization for Bayesian Optimization with Variational Mutual Information

Bayesian optimization (BO) of expensive black-box functions is traditionally addressed with Gaussian processes (GPs), which scale cubically with observations, or Bayesian neural networks (BNNs), which incur costly posterior sampling and inner-loop acquisition optimization. We propose VBO-MI (Variational Bayesian Optimization with Mutual Information), a fully gradient-based BO framework that requires no explicit GP prior or fixed parametric posterior family over objective function and treats it as a strict black box. An actor-critic architecture pairs an action-net with a variational critic that estimates information gain, eliminating the acquisition optimization bottleneck and achieving up to 102×10^{2}\times fewer FLOPs than BNN-BO baselines. A lightweight surrogate network further reduces real function queries to one batch per iteration. We establish consistency guarantees and evaluate VBO-MI on synthetic benchmarks (Ackley, Levy, Griewank) and real-world tasks (Rover Trajectory, Lunar Lander, Pest Control), demonstrating competitive or superior performance over the baselines.
Jan 12, 2026

Surrogate-based Optimization via Clustering for Box-Constrained Problems

Global optimization of large-scale, complex systems such as multi-physics black-box simulations and real-world industrial systems is important but challenging. This work presents a novel Surrogate-Based Optimization framework based on Clustering, SBOC for global optimization of such systems, which can be used with any surrogate modeling technique. At each iteration, it uses a single surrogate model for the entire domain, employs k-means clustering to identify unexplored domain, and exploits a local region around the surrogate optimum to potentially add three new sample points in the domain. SBOC has been tested against sixteen promising benchmarking algorithms using 52 analytical test functions of varying input dimensionalities and shape profiles. It successfully identified a global minimum for most test functions with substantially lower computational effort than other algorithms. It worked especially well on test functions with four or more input variables. It was also among the top six algorithms in approaching a global minimum closely. Overall, SBOC is a robust, reliable, and efficient algorithm for global optimization of box-constrained systems.
Nov 11, 2025

Hyperellipsoid Density Sampling: Exploitative Sequences to Accelerate High-Dimensional Numerical Optimization

The curse of dimensionality remains a persistent challenge in modern optimization problems. Expanding the search space into higher dimensions exponentiates the difficulty of finding optimal solutions, rendering traditional algorithms inefficient. An efficient sampling strategy is presented to accelerate high-dimensional optimization as an alternative to uniform quasi-Monte Carlo (QMC) methods. This method, referred to as Hyperellipsoid Density Sampling (HDS), generates sequences by defining multiple hyperellipsoids throughout the search space. HDS utilizes three types of unsupervised learning algorithms to bypass high-dimensional geometric calculations, producing a non-uniform sample sequence that exploits statistically promising regions of the parameter space. The ability to influence its distribution towards regions of interest makes HDS versatile for applications beyond global optimization, where models benefit from samples focused in specific regions. HDS was evaluated against Sobol, a highly uniform QMC sampling method, using differential evolution (DE) on the challenging set of 29 CEC2017 benchmark test functions. The results show statistically significant improvements in final solution geometric mean error (p<0.05), with average performance gains ranging from 37% in 10D to 11% in 100D. This paper demonstrates the efficacy of HDS as a robust alternative to uniform QMC sampling in high-dimensional optimization.
Oct 2, 2025

Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning

We introduce an order-invariant reinforcement learning framework for black-box combinatorial optimization. Classical estimation-of-distribution algorithms (EDAs) often rely on learning explicit variable dependency graphs, which can be costly and fail to capture complex interactions efficiently. In contrast, we parameterize a multivariate autoregressive generative model trained without a fixed variable ordering. By sampling random generation orders during training, a form of information-preserving dropout, the model is encouraged to be invariant to variable order, promoting search-space diversity, and shaping the model to focus on the most relevant variable dependencies, improving sample efficiency. We adapt Group Relative Policy Optimization (GRPO) to this setting, providing stable policy-gradient updates from scale-invariant advantages. Across a wide range of benchmark algorithms and problem instances of varying sizes, our method frequently achieves the best performance and consistently avoids catastrophic failures.
Sep 29, 2025

Machine Learning Algorithms for Improving Black Box Optimization Solvers

Black-box optimization (BBO) addresses problems where objectives are accessible only through costly queries without gradients or explicit structure. Classical derivative-free methods---line search, direct search, and model-based solvers such as Bayesian optimization---form the backbone of BBO, yet often struggle in high-dimensional, noisy, or mixed-integer settings. Recent advances use machine learning (ML) and reinforcement learning (RL) to enhance BBO: ML provides expressive surrogates, adaptive updates, meta-learning-based algorithm selection, and generative models, while the RL--BBO interface includes dynamic operator configuration, robust policy search, and meta-optimization across tasks. This paper surveys these developments, covering representative algorithms such as the modular model-based optimization framework (mlrMBO), zeroth-order adaptive momentum methods (ZO-AdaMM), automated BBO (ABBO), distributed block-wise optimization (DiBB), partition-based Bayesian optimization (SPBOpt), the transformer-based optimizer (B2Opt), diffusion-model-based BBO, surrogate-assisted RL for differential evolution (Surr-RLDE), robust BBO (RBO), coordinate-ascent MORE with step size adaptation (CAS-MORE), log-barrier stochastic gradient descent (LB-SGD), policy improvement with black-box (PIBB), and offline Q-learning with Mamba backbones (Q-Mamba). We further review benchmark efforts such as the NeurIPS 2020 BBO Challenge and the MetaBox framework. A controlled numerical study further confirms that ML-based candidate screening can improve the evaluation-budget performance of direct search and differential evolution, while the benefit remains solver-dependent.
Jul 16, 2025

Cost-aware Stopping for Bayesian Optimization

In automated machine learning, scientific discovery, and other applications of Bayesian optimization, deciding when to stop evaluating expensive black-box functions in a cost-aware manner is an important but underexplored practical consideration. A natural performance metric for this purpose is the cost-adjusted simple regret, which explicitly captures the trade-off between solution quality and cumulative evaluation cost. Existing stopping rules for Bayesian optimization are either heuristic, or are theoretically grounded but designed to optimize simple regret without accounting for evaluation costs; as a result, they provide no guarantees against unnecessary evaluations when costs are high. We propose a principled cost-aware stopping rule for Bayesian optimization that adapts to varying evaluation costs without heuristic tuning. Our rule is grounded in a theoretical connection to state-of-the-art cost-aware acquisition functions, namely the Pandora's Box Gittins Index (PBGI) and log expected improvement per cost (LogEIPC). When paired with either acquisition function, we prove that the resulting policy satisfies a theoretical guarantee bounding the expected cost-adjusted simple regret. Across synthetic tasks and empirical benchmarks including hyperparameter optimization and neural architecture size search, pairing our stopping rule with PBGI or LogEIPC usually matches or outperforms other acquisition-function--stopping-rule pairs in terms of cost-adjusted simple regret.
Jul 2, 2025

Tuning without Peeking: Provable Generalization Bounds and Robust LLM Post-Training

Gradient-based optimization is the workhorse of deep learning, offering efficient and scalable training via backpropagation. However, exposing gradients during training can leak sensitive information about the underlying data, raising privacy and security concerns such as susceptibility to data poisoning attacks. In contrast, black-box optimization methods, which treat the model as an opaque function, relying solely on function evaluations to guide optimization, offer a promising alternative in scenarios where data access is restricted, adversarial risks are high, or overfitting is a concern. This paper introduces BBoxER, an evolutionary black-box method for LLM post-training that induces an information bottleneck via implicit compression of the training data. Leveraging the tractability of information flow, we provide non-vacuous generalization bounds and strong theoretical guarantees for robustness to data poisoning attacks and extraction attacks, while ensuring privacy by design. In experiments with LLMs, we demonstrate empirically that black-box optimization methods-despite the scalability and computational challenges inherent to black-box approaches-are able to learn, showing how a few iterations of BBoxER improve performance, generalize well on a benchmark of reasoning datasets, and are robust to membership inference attacks. This positions BBoxER as an attractive add-on on top of gradient-based optimization, offering suitability for deployment in restricted environments while also providing non-vacuous generalization guarantees.
May 20, 2025

LLINBO: Trustworthy LLM-in-the-Loop Bayesian Optimization

Bayesian optimization (BO) is a sequential decision-making tool widely used for optimizing expensive black-box functions. Recently, Large Language Models (LLMs) have shown remarkable adaptability in low-data regimes, making them promising tools for black-box optimization by leveraging contextual knowledge to propose high-quality query points. However, LLMs lack explicit surrogate modeling and calibrated uncertainty, and their internal mechanisms remain opaque. This structural opacity can result in unnecessary experiments, which are costly in BO and may prevent the search from approaching the optimum. To address this, we propose LLINBO: LLM-in-the-Loop BO, a general framework that wraps existing LLM-based BO approaches, deciding when and how to act on their suggestions and when to revert to classical BO. We introduce three mechanisms for this interaction, each accompanied by a no-harm theoretical guarantee that ensures sublinear cumulative regret for common kernels while requiring no performance assumptions on the LLM. Beyond these theoretical guarantees, we show through simulation studies that LLINBO makes existing LLM-based BO more reliable while still exploiting the LLM's few-shot learning ability to outperform classical BO. We further demonstrate its practical use on a real-world, expensive 3D printing experiment. Code is available at https://github.com/UMDataScienceLab/LLM-in-the-Loop-BO.
Jun 9, 2024

Probabilistic Approach to Black-Box Binary Optimization with Budget Constraints: Application to Sensor Placement

This paper presents a fully probabilistic approach for solving optimal experimental design problems under budget constraints. The experimental design is viewed as a random variable and is associated with a parametric conditional distribution that inherently models the budget constraints. The original optimization problem is replaced with an optimization over the expected value of the original objective, which is then optimized over the distribution parameters. The resulting optimal parameter (policy) is used to sample the feasible region of binary space to produce estimates of the optimal solution(s) of the original optimization problem. In this work we extend the family of conditional Bernoulli models to model the random variable conditioned by the total number of nonzero entries, that is, the budget constraint. This approach (a) is generally applicable to binary optimization problems with nonstochastic black-box objective functions and budget constraints; (b) employs conditional probabilities to model and sample only the feasible region and thus considerably reduces the computational cost compared with employing soft constraints; and (c) does not employ soft constraints and thus does not require tuning of a regularization parameter, for example to promote sparsity, which is generally challenging. The proposed approach is verified numerically using an optimal sensor placement experiment based on an advection-diffusion forward model in a parameter identification setup.
Jun 6, 2024

Simulating, Fast and Slow: Learning Policies for Black-Box Optimization

Simulators are vital in science and engineering, as they faithfully model the influence of design parameters on real-world observations. Optimizing design parameters to minimize a desired objective function is notoriously challenging since simulators are often non-differentiable black boxes. Moreover, each simulation incurs significant compute time, thus doing such optimizations naively may be prohibitively expensive. Furthermore, in experiment design settings, practitioners are typically required to solve the same optimization problem for various input distributions before proceeding to real-world experiments. Starting these related optimizations from scratch each time can be inefficient if the forward simulation model is expensive to evaluate. To address these challenges, this paper introduces a novel method for solving black-box optimization problems on various input distributions by learning a policy that guides the training of a differentiable surrogate. The surrogate's gradients are then used to optimize the simulation parameters with SGD. After training the policy, the cost for downstream optimization of problems involving black-box simulators is amortized, and we require up to 10×10\times fewer expensive simulator calls compared to baselines such as previous local surrogate-based approaches, numerical optimization, and Bayesian optimization.
Jun 5, 2024

BEACON: A Bayesian Optimization Inspired Strategy for Efficient Novelty Search

Novelty search (NS) aims to uncover diverse system behaviors through simulation or experiment without requiring a pre-specified scalar objective. This capability is especially relevant to modern discovery problems in chemistry, materials science, and molecular design, where researchers often seek broad coverage of attainable property space rather than a single optimum and where each evaluation may require a costly computation or experiment. For such expensive black-box settings, we propose BEACON, a sample-efficient NS strategy inspired by Bayesian optimization principles. BEACON models the input-to-outcome mapping using multi-output Gaussian processes and selects new inputs by scoring how far plausible posterior outcomes lie from a denoised archive of previously observed outcomes. This gives a distance-based novelty acquisition that accounts for predictive uncertainty and observational noise while operating directly in continuous outcome space, rather than requiring direct optimization over a discretized partition of behaviors. By leveraging efficient posterior sampling together with scalable high-dimensional Gaussian process models, the proposed framework can be extended to settings with large data sets and high-dimensional design variables. We demonstrate BEACON on established benchmark problems together with real-world case studies in materials and molecular discovery. Across these settings, BEACON consistently discovers broader sets of distinct behaviors than several competing baselines under limited evaluation budgets.
May 29, 2024

MEGO: Learning Mixture-of-Experts for General-Purpose Binary Optimization

Discrete optimization is ubiquitous in science and engineering. The vast array of existing discrete optimization problems, coupled with the continuous emergence of new ones, necessitates off-the-shelf optimizers capable of generating high-quality solutions for a large variety of optimization problems. This article introduces MEGO, a novel general-purpose neural optimizer for binary optimization under the black-box setting, intended for broad applicability across diverse binary optimization problem classes with minimal problem-specific customization. MEGO comprises a mixture-of-experts trained without domain knowledge. When presented with a new problem instance to solve, it employs a routing policy to dynamically activate the most relevant expert models to generate high-quality solutions. The strong generalization capability of MEGO is demonstrated on six problem classes from different disciplines, including classic problems and real-world applications. Trained solely on classic problems, MEGO effectively generalizes to unseen and complex real-world problem classes, significantly outperforming widely-used general-purpose optimizers in both solution quality and efficiency. Furthermore, MEGO provides a computational approach for quantifying similarity between optimization problems and classifying them, which is fundamentally different from the conventional analysis-based problem classification.
May 19, 2024

Gradient Testing and Estimation by Comparisons

We study gradient testing and gradient estimation of smooth functions using only a comparison oracle that, given two points, indicates which one has the larger function value. For any smooth f ⁣:Rn→Rf\colon\mathbb R^n\to\mathbb R, x∈Rn\mathbf{x}\in\mathbb R^n, and ε>0\varepsilon>0, we design a gradient testing algorithm that determines whether the normalized gradient ∇f(x)/∥∇f(x)∥\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\| is ε\varepsilon-close or 2ε2\varepsilon-far from a given unit vector v\mathbf{v} using O(1)O(1) queries, as well as a gradient estimation algorithm that outputs an ε\varepsilon-estimate of ∇f(x)/∥∇f(x)∥\nabla f(\mathbf{x})/\|\nabla f(\mathbf{x})\| using O(nlog⁡(1/ε))O(n\log(1/\varepsilon)) queries which we prove to be optimal. Furthermore, we study gradient estimation in the quantum comparison oracle model where queries can be made in superpositions, and develop a quantum algorithm using O(log⁡(n/ε))O(\log (n/\varepsilon)) queries.