Task-free Adaptive Meta Black-box Optimization

AI summary

Overview

• Research area: Meta black-box optimization (MetaBBO), evolutionary computation, and neural attention-based optimizer design (cs.NE).
• Technical level: Advanced. The paper combines differentiable attention modules, evolutionary operators, and a convergence analysis, and it assumes familiarity with meta-learning and derivative-free optimization.
• Scope: The paper introduces ABOM (Adaptive meta Black-box Optimization Model), a meta-optimizer whose evolutionary operators are learnable and update online using only data generated on the target task, with no predefined training task distribution.

What This Paper Is About

Most MetaBBO methods learn meta-strategies by training on handcrafted distributions of optimization tasks, then hope those strategies transfer to a new target task. When the target task is unique or data-scarce, no such training distribution exists, so these methods cannot be applied cleanly. The paper's goal is to remove that dependency entirely: ABOM parameterizes selection, crossover, and mutation as differentiable functions and continuously refines their parameters during the search itself, using only the populations and fitness values it generates on the target task.

Key Contributions

1. A task-free MetaBBO formulation. The paper reformulates meta-optimization from the triplet (A, R, F) — algorithm search space, performance metric, training task distribution — to an adaptive version (A, R, f_T) that operates directly on the target task f_T, then further reduces this to a single differentiable optimizer π_θ updated only from cumulative optimization knowledge M^(t) = (X^(t), Y^(t)).
2. Differentiable evolutionary operators via attention. Selection is an N×N attention matrix combining a solution-space term and a fitness-driven term; crossover applies an MLP to the attention-weighted recombination pool with dropout rate p_C; mutation applies a per-individual d×d gene-interaction matrix and an MLP with dropout rate p_M.
3. Closed-loop adaptive parameter learning. Instead of offline meta-training, θ is updated by minimizing the squared distance between the offspring population and the elite archive, ‖P̂^(t) − E^(t)‖², using a gradient-based optimizer such as AdamW.
4. Theory and interpretability. The paper proves global convergence under stated assumptions and shows that the learned selection and mutation matrices expose structured, readable search patterns (illustrated on BBOB functions f_4, f_11, and f_24 at d = 30).

Main Findings

• Competitive results with no training tasks. On the BBOB suite at d = 30/100/500, the paper reports that ABOM "matches or outperforms all baselines," with mean and standard deviation over 30 independent runs and Wilcoxon rank-sum tests at 95% confidence. For example, at d = 500 on f_4, ABOM reaches 1.215e+4 ± 5.389e+2 versus CMAES at 1.447e+4 ± 7.83e+2, and on f_14 ABOM reaches 1.487e+1 ± 2.291e+0 versus CMAES at 2.494e+1 ± 3.554e+0.
• Strong UAV path planning performance. On the UAV benchmark, ABOM converges fastest under limited evaluations (a 2,500-evaluation budget) and achieves the lowest normalized cost, while GPU-accelerated evolution gives it significantly faster runtime than most baselines.
• Selection and mutation learn structure. The selection matrix develops row similarity, meaning offspring are generated from a small subset of individuals, resembling the difference-vector mechanism in DE. Higher-fitness individuals are preferentially selected, but the single best individual is not always chosen, which the authors suggest preserves diversity. The mutation matrix evolves from random initialization into an ordered structure.
• All components matter. In the ablation at d = 30, disabling crossover, mutation, or parameter adaptation each degrades performance. For f_4, ABOM reaches 5.45e+02 ± 2.95e+02 while the no-crossover variant gives 4.23e+03 ± 3.02e+03, no mutation gives 1.01e+03 ± 5.44e+02, and no parameter adaptation gives 2.58e+04 ± 1.67e+04.
• Modest hyperparameters suffice. A population size of 20 is sufficient for robust performance across most functions within 20,000 evaluations, and a hidden dimension d_M smaller than d (for example d_M = 16) often achieves competitive results. Dropout rates p_C and p_M perform best at 0.95; setting either to 1 removes beneficial randomness and degrades performance. Learning-rate analysis is placed in Appendix I.
• Complexity is dimension-dominated. Total per-step complexity is O(N d d_A + N² d_A + N d_A d_M + N d_M d + d² d_A + d d_A d_M). Assuming d_A = d_M = d reduces this to O(Nd² + N²d + d³), and in the typical high-dimensional regime N ≪ d the leading term is O(d³).
• Global convergence is proven. Under Assumption 1 (compact search space, continuous objective with an interior global minimizer, tanh-activated MLPs with 0 < p_C, p_M < 1 during inference), Corollary 1 gives an exploration guarantee, Corollary 2 gives a positive expected-improvement (progress) guarantee, and Theorem 3.1 states that f_t* converges to f* almost surely as t → ∞.

Methodology in Plain English

ABOM treats an evolutionary algorithm as a neural network. A population of N candidate solutions P^(t) and their black-box fitness values F^(t) are fed into three modules. Selection uses attention over both the solutions and their fitness values, producing a matrix that decides which individuals contribute to each offspring — blending "who is nearby in search space" with "who is fit." Crossover mixes those selected parents through a small multilayer perceptron and adds the result back onto the current population. Mutation applies a second attention matrix over the dimensions of each individual, capturing gene-to-gene interactions, then perturbs through another MLP. Dropout is kept active at inference so the operators stay stochastic and exploration does not collapse.

The optimization loop is: initialize with Latin hypercube sampling, reproduce offspring, evaluate them on the black-box objective, keep the top N individuals from the union of parents and offspring as an elite archive, then update all parameters. The update signal is simple — pull the generated offspring toward the elite archive by minimizing the squared distance between them, and take a gradient step with AdamW. Because the elite archive is produced on the fly by the target task itself, no training tasks, no pretraining, and no hand-designed algorithm search space are needed. The authors evaluate on the MetaBox Benchmark, which bundles the 24-function BBOB suite (search space [−100,100]^d, d = 30/100/500, 20,000 evaluations) and 56 UAV terrain-based path-planning instances (2,500 evaluations), on a Linux machine with an NVIDIA RTX 2080 Ti GPU (12 GB memory, CUDA 11.3). MetaBBO baselines were trained on the same problem distribution as RLDEAFL, with 8 of 24 BBOB instances used for training and 16 for testing, and the 56 UAV instances split 50%/50%.

Why This Matters

Impact on research. The paper attacks the hidden assumption underneath most MetaBBO work: that a representative training task distribution can be assembled in advance. By folding parameter learning into the evolutionary loop, it reframes meta-optimization as online adaptation rather than offline meta-training, and it backs the reframing with a convergence proof plus interpretable attention visualizations. That combination gives the field both a new baseline to beat and a diagnostic tool — the learned matrices can be read as evidence of selection pressure and gene dependency.

Real-world applications:

• Unmanned aerial vehicle path planning through terrain with cylindrical threats, minimizing total flight length while staying collision-free, as tested on 56 terrain-based instances.
• Hyperparameter tuning, where the objective is evaluated only through expensive training runs and no gradients are available.
• Neural architecture search, where candidate architectures are compared by black-box validation performance.
• Prompt engineering, where objective quality is measured only through evaluations of generated outputs.

The paper's introduction also cites neuroevolution as a motivating BBO application.

Industry relevance. MetaBBO systems that require curated training task suites are costly to deploy and re-engineer for every new domain. ABOM's task-free framing plus out-of-the-box GPU acceleration means a practitioner can point one optimizer at a new problem without a task-design phase, no discrete algorithm search space, and no expert feature engineering — lowering the barrier for teams without optimization specialists. The runtime advantage over MetaBBO baselines on the UAV benchmark is directly relevant where search happens under tight evaluation budgets.

Future Directions

• Reduce the cubic bottleneck. The authors propose sparse or low-rank attention mechanisms to cut the O(d³) cost that dominates when N ≪ d.
• Adapt population size and model capacity online. Rather than fixing N, d_A, and d_M, let the optimizer resize itself during the search.
• Analyze the convergence rate. The current result establishes almost-sure convergence, but not how fast; the authors call for a rate analysis grounded in the theory of adaptive parameter learning.
• Explore hybrid training. Combine pretraining on prior knowledge with online adaptation to improve efficiency and bridge task-agnostic adaptation and cross-task generalization.

Target Audience

Researchers and graduate students in evolutionary computation, meta-learning, and derivative-free optimization who want an alternative to distribution-dependent MetaBBO; practitioners solving expensive black-box problems such as UAV path planning, hyperparameter tuning, or architecture search who need a method that works without a curated training suite; and readers interested in interpretability of learned search operators through attention visualization.

Authors’ abstract

Handcrafted optimizers become prohibitively inefficient for complex black-box optimization (BBO) tasks. MetaBBO addresses this challenge by meta-learning to automatically configure optimizers for low-level BBO tasks, thereby eliminating heuristic dependencies. However, existing methods typically require extensive handcrafted training tasks to learn meta-strategies that generalize to target tasks, which poses a critical limitation for realistic applications with unknown task distributions. To overcome the issue, we propose the Adaptive meta Black-box Optimization Model (ABOM), which performs online parameter adaptation using solely optimization data from the target task, obviating the need for predefined task distributions. Unlike conventional metaBBO frameworks that decouple meta-training and optimization phases, ABOM introduces a closed-loop adaptive parameter learning mechanism, where parameterized evolutionary operators continuously self-update by leveraging generated populations during optimization. This paradigm shift enables zero-shot optimization: ABOM achieves competitive performance on synthetic BBO benchmarks and realistic unmanned aerial vehicle path planning problems without any handcrafted training tasks. Visualization studies reveal that parameterized evolutionary operators exhibit statistically significant search patterns, including natural selection and genetic recombination.