Generative Refinement for Low-Budget Black-Box Optimization
2026-07-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors address the challenge of optimizing functions when it's expensive or difficult to get reliable results from each test. They introduce SPARROW, a method that separates the way solutions are generated from how good they are, allowing it to work well even with very few tests and noisy feedback. Instead of directly learning from the results, SPARROW ranks tested solutions to guide improvement, making it effective in tricky problem spaces. Their method is proven to converge over time and performs well when rewards are unreliable or the solutions cluster in complex shapes.
Black-box optimizationGenerative modelsNoisy evaluationFunction evaluation budgetRank-based guidanceOptimization under uncertaintySampling methodsConvergence guaranteesSearch space geometryCorruption process
Authors
Edouard R. Dufour, Pascal Fua
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.