Technical Summary: SPARROW for Low-Budget Black-Box Optimization

Problem Statement

Black-box optimization (BBO) is essential for fields like materials design, drug discovery, and engineering simulation, where gradient information is unavailable. However, existing methods struggle in low-budget settings where function evaluations are costly, noisy, or prone to failure. The challenge is exacerbated when high-performing solutions reside in thin, curved, or disconnected regions of the search space (e.g., a low-dimensional manifold within a high-dimensional ambient space).

Classical approaches face specific limitations in these regimes:

• Bayesian Optimization (BO): Methods like Gaussian Processes (GP) often fail when feedback is unreliable or when the search space is high-dimensional, as they waste evaluations on infeasible regions.
• Evolutionary Strategies (ES): While robust to noise, methods like CMA-ES typically require more evaluations to converge and struggle to capture complex geometries without wasting budget.
• Generative Model-Based Methods: Recent approaches leveraging diffusion or flow matching models often rely on reward-aligned distributions. These methods require either labeled training data or a large number of evaluations during sampling to shape the sampler toward the objective. This "distribution-learning" paradigm is structurally incompatible with low-budget optimization, where the goal is to find a single best solution with very few evaluations.

Methodology: SPARROW

The authors propose SPARROW (Sequential Proposal via Archival Rank-based Refinement for Optimization under Weak feedback), an algorithm that completely decouples the generative prior from the reward signal.

Core Architecture

SPARROW treats a fixed, unconditional generative sampler (e.g., a diffusion model or flow matching model) as a structured proposal operator. It does not retrain or adapt this model based on objective evaluations. Instead, optimization is driven entirely by rank-based guidance over an archive of evaluated candidates.

Algorithmic Steps

At each iteration $k$, SPARROW performs the following:

1. Ranking: All candidates in the archive $A_k$ are assigned normalized ranks $r_k(x_i)$ based on their objective values.
2. Parent Selection: A parent $x_k$ is sampled from the archive with probability proportional to $\exp(-\beta r_k(\cdot))$, where $\beta$ controls selection pressure.
3. Corruption Level Computation: A noise level $t_k$ is computed based on the parent's rank: $t_k = 1 - r_k(x_k)^\gamma$.
   • High-ranked (good) candidates receive low corruption ($t_k \approx 0$), leading to local refinement.
   • Low-ranked (poor) candidates receive high corruption ($t_k \approx 1$), leading to global resampling from the prior.
4. Rank-Guided Directional Step: Two random archive members $x_a, x_b$ are selected. A mutation direction is formed by the difference $(x_a - x_b)$, sign-corrected to point from the worse to the better candidate. The parent is displaced along this direction:
   $$x_{guided} = x_k + \lambda (1 - t_k) \text{sign}(r_k(x_b) - r_k(x_a))(x_a - x_b)$$
5. Noise-Refine Mutation: The guided candidate is corrupted to noise level $t_k$ and then refined back to the data manifold using the fixed generative sampler's reverse process ($S_{t_k \to 1}$). This produces a new proposal $x'_{k+1}$.
6. Evaluation & Archive Update: The new candidate is evaluated, and the archive is updated.

Key Design Principles

• Decoupling: The generative model provides structural priors (feasible regions) but is never updated with reward signals. The reward signal only influences the selection and corruption level of candidates.
• Rank-Based Invariance: By relying on ranks rather than raw objective values, SPARROW is invariant to monotone transformations and robust to scaling, misspecification, and outcome-dependent noise.
• Adaptive Exploration: The corruption level $t_k$ acts as an adaptive step size. Poor candidates are "reset" globally (high $t$), while good candidates undergo local refinement (low $t$).
• Full Archive Retention: Unlike methods that discard candidates, SPARROW maintains a growing archive, allowing for progressively finer-grained rank estimates without discarding potentially promising regions due to noisy evaluations.

Key Contributions

1. Algorithmic Innovation: Introduction of SPARROW, which separates generative modeling from optimization, enabling the use of pre-trained samplers in low-budget regimes without expensive reward-aligned training.
2. Theoretical Guarantees: The authors provide asymptotic convergence guarantees showing that, under noiseless conditions, the best sample observed converges almost surely to the global optimum over the support of the generative sampler.
3. Robustness: The method is explicitly designed to handle unreliable feedback (noise and solver failures) through rank-based selection, avoiding the brittleness of value-based methods in such environments.
4. Empirical Performance: Demonstrated effectiveness on problems with complex geometries (thin tubes, disconnected regions) and unreliable objectives where classical methods fail.

Experimental Results

The authors evaluated SPARROW on three tasks with a strict budget of $B=100$ evaluations (except for a scaling test on the tube task):

1. Synthetic Thin Tube (64D):

   • Setup: Optimal solutions lie on a thin, curved 1D manifold in 64D space.
   • Result: Ambient-space methods (CMA-ES, GP, TuRBO) failed entirely or stagnated because their search distributions could not concentrate on the low-volume tube. SPARROW substantially outperformed all baselines, including Random Diffusion Sampling (RDS), with the performance gap widening as dimensionality increased.

2. HopperController (5126D):

   • Setup: A continuous control task with highly disconnected high-performing regions.
   • Result: CMA-ES collapsed. GP and TuRBO plateaued near initialization quality. SPARROW significantly outperformed all baselines, successfully navigating the disconnected feasible regions.

3. Airfoil Aerodynamic Optimization:

   • Setup: Maximizing lift-to-drag ratio ($C_l/C_d$) using XFOIL, a solver prone to failures (invalid geometries).
   • Result: SPARROW achieved the highest median $C_l/C_d$ with a notably tight interquartile range compared to baselines. The fixed generative prior reduced the rate of solver failures by steering proposals toward geometrically valid shapes, while rank-based guidance handled the noisy feedback.

Significance and Claims

The paper claims that SPARROW addresses a critical gap in black-box optimization: optimizing complex, geometrically constrained problems under severe evaluation budgets with unreliable feedback.

• Practicality: It offers a practical solution for engineering design (e.g., aerodynamics) where simulations are expensive and prone to failure, and where good solutions are rare and structurally complex.
• Efficiency: By avoiding the cost of learning reward-aligned distributions, SPARROW makes generative priors accessible for low-budget scenarios.
• Limitations: The authors modestly acknowledge that performance is bounded by the quality of the generative prior (solutions outside the support are unreachable) and that the convergence guarantees are asymptotic and restricted to noiseless evaluations over the sampler support. The method is specifically positioned for low-budget, complex-geometry settings, not for simple, high-budget, or reliable-feedback scenarios where established methods may still be superior.

In summary, SPARROW demonstrates that decoupling the structural prior from the optimization signal allows for robust, efficient navigation of complex search spaces where traditional gradient-free and generative approaches fail.