Generative Refinement for Low-Budget Black-Box Optimization

• URL: http://arxiv.org/abs/2607.00691v1
• Date: Wed, 01 Jul 2026 09:41:41 GMT
• Title: Generative Refinement for Low-Budget Black-Box Optimization
• Abstract summary: Black-box optimization is a fundamental science and engineering tool that makes it possible to optimize objectives without information.<n>Existing methods leveraging generative models to navigate subspaces are built to sample from reward-aligned distributions.<n>We propose SPARROW, an algorithm that completely decouples the generative prior from the reward signal.
• Score: 33.559218731885046
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Black-box optimization is a fundamental science and engineering tool that makes it possible to optimize objectives without gradient information. Unfortunately, as it often requires many function evaluations, it can be challenging when each one is costly. This is especially true when the evaluation function is noisy or failure-prone, and when high-performing solutions are confined to thin, curved, or disconnected regions of the search space. Existing methods leveraging generative models to navigate these subspaces are built to sample from reward-aligned distributions. As a result, they require a large number of evaluations to align their sampler effectively, making them impractical in low-budget settings. We propose SPARROW, an algorithm that completely decouples the generative prior from the reward signal. SPARROW can use any sampler with a known corruption process and trained on unevaluated data, as a fixed, structured proposal operator. Optimization proceeds by rank-based guidance over an archive of evaluated candidates. SPARROW can navigate complex geometries, handle unreliable reward signals, and perform effective optimization under very low evaluation budgets. We provide asymptotic convergence guarantees over the sampler support and demonstrate strong empirical performance on problems with unreliable rewards and geometrically complex landscapes.

Related papers

• Rethinking Learnability in Offline Data-driven Optimization [20.146021332129703]
  Black-Box Optimization (BBO) faces efficiency challenges as real-world problems grow increasingly complex.<n>Data-driven optimization has been the most popular paradigm to improve the efficiency of BBO, by learning from data.<n>Many offline optimization methods have been proposed, but a fundamental question remains unanswered: what learnability is sufficient for offline optimization?
  arXiv  Detail & Related papers  (2026-09-01T16:22:28Z)
• Gradient-Free Noise Optimization for Reward Alignment in Generative Models [52.42087778653147]
  ZeNO is a gradient-free framework that formulates noise optimization as a path-integral control problem.<n>It enables effective inference-time scaling and demonstrates strong performance across diverse generators and reward functions.
  arXiv  Detail & Related papers  (2026-05-12T00:05:36Z)
• Kernel Learning for Sample Constrained Black-Box Optimization [7.054093620465401]
  We propose a new method to learn the kernel of a Gaussian Process.<n>Our idea is to create a continuous kernel space in the latent space of a variational autoencoder, and run an auxiliary optimization to identify the best kernel.<n>Results hold not only across synthetic benchmark functions but also in real applications.
  arXiv  Detail & Related papers  (2025-07-28T05:32:11Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Indirect Query Bayesian Optimization with Integrated Feedback [17.66813850517961]
  We develop a new class of Bayesian optimization problems where integrated feedback is given via a conditional expectation of the unknown function $f$ to be optimized.<n>The goal is to find the global optimum of $f$ by adaptively querying and observing in the space transformed by the conditional distribution.<n>This is motivated by real-world applications where one cannot access direct feedback due to privacy, hardware or computational constraints.
  arXiv  Detail & Related papers  (2024-12-18T07:20:33Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms [4.0295993947651025]
  We introduce the "incenter" concept, a new notion akin to circumcenter recently proposed by Besbes et al. We propose a novel loss function called Augmented Suboptimality Loss (ASL), a relaxation of the incenter concept for problems with inconsistent data. This algorithm combines approximate subgradient evaluations, together with mirror descent update steps, which is provably efficient for the IO problems with discrete feasible sets with high cardinality.
  arXiv  Detail & Related papers  (2023-05-12T18:58:08Z)
• Robust expected improvement for Bayesian optimization [1.8130068086063336]
  We propose a surrogate modeling and active learning technique called robust expected improvement (REI) that ports adversarial methodology into the BO/GP framework. We illustrate and draw comparisons to several competitors on benchmark synthetic exercises and real problems of varying complexity.
  arXiv  Detail & Related papers  (2023-02-16T22:34:28Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts. Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures. We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
  arXiv  Detail & Related papers  (2020-10-07T08:19: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.