Technical Summary: NeurGO – Learning to Generate Elite Candidates for Meta-Black-Box Optimization

1. Problem Definition

The paper addresses Expensive Black-Box Optimization (EBBO), a class of global optimization problems where the objective function $f: \Omega \to \mathbb{R}$ is accessible only through evaluations, gradients are unavailable, and the evaluation budget ($B_{max}$) is strictly limited. Such scenarios are common in hyperparameter tuning and engineering design.

The central challenge is to approach the global optimum with as few function evaluations as possible. Existing paradigms face specific limitations:

• Bayesian Optimization (BO) and Surrogate-Assisted Evolutionary Algorithms (SAEAs): These rely on constructing surrogate models (e.g., Gaussian Processes) to approximate the fitness landscape. However, under tight budgets, limited data often leads to inaccurate surrogates (the "cold-start" problem) and model bias, which can trap the search in local optima. Furthermore, training surrogates from scratch for each new task limits cross-task generalization.
• Traditional Meta-Black-Box Optimization (MetaBBO): While these methods learn transferable search strategies, many still treat Evolutionary Algorithms (EAs) as the underlying optimizer. Consequently, they waste a significant portion of the budget generating and evaluating large offspring pools, many of which are inferior.

2. Methodology: NeurGO

The authors propose NeurGO, a generative MetaBBO framework designed to directly synthesize a small set of high-quality ("elite") candidates from historical population states, bypassing the need for large offspring pools or online surrogate fitting. The framework consists of three main stages:

2.1 Architecture Overview

NeurGO is built on a Transformer backbone and comprises two core modules:

1. Population Context Encoder (PCE): Encodes the current population state into a high-dimensional representation capturing evolutionary trends.
2. Elite Synthesis Decoder (ESD): Maps the encoded representation to a small batch of $k$ candidate solutions ($k \ll N$, where $N$ is the population size) for expensive evaluation.

2.2 Population Context Encoder (PCE)

The PCE processes the population as a sequence to capture global interactions.

• Population Sorting: The population is sorted by fitness in ascending order. This acts as an implicit relative positional encoding, prioritizing high-performing individuals without relying on specific fitness scales.
• Rank-Fitness Dual-Aware Attention: Instead of standard learned projections, the attention mechanism is constructed using:
  • Fitness Branch: Normalized fitness values ($\tilde{F}_t$) are projected to create fitness-aware queries and keys, aggregating the sorted population based on fitness relations.
  • Rank Branch: A trainable matrix ($A_{rank}$) captures ordering information.
  • These branches are fused via learnable weights ($\lambda_{rank}, \lambda_{fit}$).
• Residual Fusion with Perturbation: To prevent premature convergence and encourage exploration, a Feed-Forward Network (FFN) introduces a learnable nonlinear perturbation to the attention output. The final refined representation ($X^{ref}_t$) is a residual fusion of the original sorted population, the attention-aggregated features, and the FFN-perturbed features.

2.3 Elite Synthesis Decoder (ESD)

The ESD generates $k$ elite candidates directly from the refined population representation.

• Multi-Source Feature Concatenation: The decoder concatenates three sources: the sorted raw population ($X^{sort}_t$), normalized fitness ($\tilde{F}_t$), and the refined representation ($X^{ref}_t$).
• Weighted Aggregation: An MLP ($g_\phi$) computes a score matrix quantifying each individual's contribution to each of the $k$ candidates. Softmax normalization yields contribution weights ($P_t$). The final candidates ($X^{cand}_t$) are synthesized by aggregating the refined population representation using these weights: $X^{cand}_t = P_t^\top X^{ref}_t$. This ensures candidates remain anchored to the current population distribution, avoiding out-of-distribution proposals.

2.4 Training Objective: Quality-Diversity (QD) Loss

NeurGO is meta-trained using a composite loss function to balance solution quality and search diversity:

• Quality Loss ($L_{qual}$): Measures the improvement of the best candidate in the synthesized set over the best individual in the parent population. Fitness values are z-score normalized to handle scale differences across tasks.
• Diversity Loss ($L_{div}$): Encourages candidates to spread out in the decision space by maximizing the mean pairwise Euclidean distance among the synthesized candidates, normalized by the search space bounds.
• Total Objective: $L_{QD} = L_{qual} + \lambda L_{div}$, where $\lambda$ is linearly decayed during training to shift focus from exploration to convergence.

3. Key Contributions

1. Generative MetaBBO Framework: NeurGO introduces a paradigm that directly synthesizes elite candidates from population states, eliminating the inefficiency of generating large offspring pools in expensive optimization settings.
2. End-to-End Architecture with QD Objective: The paper presents a unified generative model that learns a mapping from population states to solutions while explicitly balancing convergence speed (quality) and search diversity through a custom loss function.
3. Empirical Validation: Extensive benchmarking demonstrates that NeurGO achieves faster convergence and superior final performance compared to classical EAs, SAEAs, BO, and other MetaBBO baselines under strict evaluation budgets.

4. Experimental Results

The authors evaluated NeurGO on the CEC 2008 and COCO BBOB test suites with a dimensionality of $D=10$ and a strict budget of $MaxFE = 300$.

• Comparison with EAs: NeurGO outperformed classical evolutionary algorithms (DE, GA, SHADE, CMA-ES) on the majority of test functions. The authors attribute this to NeurGO's ability to avoid wasting evaluations on low-quality individuals by generating targeted elite candidates.
• Comparison with SAEAs and BO: NeurGO demonstrated greater stability and performance than surrogate-based methods (EGO, SACOSO, TurBO, HEBO). While BO methods can be competitive on specific complex functions, NeurGO showed more consistent advantages, particularly because it avoids the noise and bias associated with online surrogate fitting under limited data.
• Comparison with MetaBBO: NeurGO achieved better final performance and stability than other learning-based optimizers (B2Opt, LGA, LES). It exhibited stronger cross-function generalization, particularly on the CEC meta-test functions.
• Convergence Analysis: Convergence plots showed NeurGO achieving sharp fitness drops early in the optimization process (around 100 evaluations), suggesting the meta-learned prior effectively localizes promising regions.
• Ablation Study: Removing the PCE module or its internal components (attention, FFN, residual connections) significantly degraded performance, confirming the necessity of learning a rich population context representation rather than relying on simple recombination.

5. Significance and Claims

The paper claims that NeurGO offers a robust alternative to traditional expensive optimization paradigms by shifting the focus from modeling the objective function (surrogates) to modeling the search process (generative priors).

• Efficiency: By synthesizing only a few high-value candidates per iteration, NeurGO maximizes the utility of every expensive evaluation.
• Generalization: The framework leverages cross-task training to learn transferable search priors, reducing reliance on task-specific hyperparameter tuning or accurate online surrogates.
• Robustness: The method is less sensitive to the "cold-start" problem and model bias that plague surrogate-assisted methods in low-budget regimes.

The authors conclude that NeurGO effectively addresses the efficiency bottleneck in expensive black-box optimization, providing a stable and high-performing solution where traditional methods struggle with budget constraints.