adaptive-acquisition-bbo - SKILL.md Agent Skill

name: adaptive-acquisition-bbo description: "Adaptive acquisition function selection for discrete black-box optimization (BOCS + GP-LCB hybrid). Based on arXiv:2605.10856 (Shikanai & Ohzeki, 2026). Use when optimizing QUBO, HUBO, or any discrete-variable black-box problem where BOCS stagnates. Combines parametric surrogate with Gaussian-process-based adaptive LCB selection for exploration-exploitation balance. Also applicable to quantum annealing sparse surrogate construction and combinatorial search. Activation: adaptive acquisition, BOCS stagnation, discrete Bayesian optimization, QUBO optimization, HUBO optimization, black-box optimization, quantum-inspired search, combinatorial optimization"

Adaptive Acquisition Black-Box Optimization

Overview

A hybrid search framework combining BOCS (Bayesian Optimization of Combinatorial Structures) as the primary parametric surrogate with a Gaussian Process + adaptive Lower Confidence Bound (LCB) component that activates only when stagnation is detected. Solves the fundamental problem of BOCS repeatedly proposing already-evaluated points as observations grow.

Based on: Shikanai & Ohzeki (2026), Improving search efficiency via adaptive acquisition function selection in discrete black-box optimization, arXiv:2605.10856.

When to Use

QUBO/HUBO problems with expensive evaluations
BOCS or similar parametric Bayesian optimization on discrete variables
Quantum annealing sparse surrogate construction
Any discrete black-box search showing stagnation (repeated proposals)

Core Algorithm

Step 1: Run BOCS as Primary Search

BOCS fits a parametric surrogate model (sparse regression) over binary variables and proposes candidates via its acquisition function. Works well for early-stage optimization with few observations.

Step 2: Detect Stagnation

Stagnation criteria: BOCS proposes a point that has already been evaluated (duplicate). This signals the parametric surrogate has exhausted its unique proposals.

Step 3: Activate GP-LCB Component (On Stagnation Only)

When stagnation is detected:

Train a Gaussian Process on all observed data using a Hamming-distance kernel:
```
k(x, x') = σ² · exp(-λ · d_H(x, x')/d)
```
where d_H is the Hamming distance, d is the problem dimension.
Compute multiple LCB acquisition functions with varying exploration parameters β:
```
LCB_β(x) = μ(x) - β · σ(x)
```
Use β ∈ {0.1, 0.5, 1.0, 2.0, 5.0} to span exploitation-to-exploration spectrum.
Adaptively select the best β based on recent search progress:
- Track improvement in objective over the last k iterations
- If recent progress > 0: favor smaller β (exploitation)
- If recent progress ≈ 0: favor larger β (exploration)
- Simple rule: select β that maximizes acquisition value at unevaluated points
Generate alternative unevaluated point by minimizing the selected LCB among unevaluated candidates. Use a short random restart or local search over the Hamming neighborhood.

Step 4: Evaluate and Update

Evaluate the proposed point on the true black-box function, add to observation set, and return to Step 1.

Key Design Principles

On-demand GP activation: GP component only runs when BOCS stalls, keeping computational cost low.
Hamming-neighborhood awareness: The effectiveness comes from selecting points that promote search progress within Hamming-distance neighborhoods, not from simply adding low-energy points near promising solutions.
Near-fully connected representational capacity: For quantum annealing sparse surrogate applications, retaining near-fully connected capacity in the surrogate model is important. Overly sparse models degrade search quality.
Adaptive β selection: Dynamically adjusts exploration-exploitation balance based on optimization trajectory, outperforming fixed-β or random-point addition strategies.

Application to QUBO

For Quadratic Unconstrained Binary Optimization:

# Pseudocode for the hybrid BOCS + GP-LCB method
observations = []  # list of (x, f(x)) pairs

for iteration in range(max_iterations):
    # Step 1: BOCS proposes
    candidate = bocs_propose(observations)
    
    # Step 2: Check for stagnation
    if candidate in [x for x, _ in observations]:
        # Step 3: Activate GP-LCB
        gp = train_gp(observations, kernel='hamming')
        beta = select_beta(recent_progress=observations[-k:])
        candidate = minimize_lcb(gp, beta, exclude=observations)
    
    # Step 4: Evaluate
    fx = evaluate(candidate)
    observations.append((candidate, fx))

Application to HUBO

For Higher-order Unconstrained Binary Optimization, the same framework applies. The BOCS surrogate should include higher-order interaction terms. The GP-LCB component handles higher-order interactions implicitly through the Hamming kernel.

Quantum Annealing Surrogate Construction

When building sparse surrogate models for quantum annealers:

Use BOCS to identify important interaction terms
Apply the adaptive GP-LCB method to explore the configuration space
Retain near-fully connected representational capacity — over-sparsification degrades performance
The sparse surrogate can then be embedded on the quantum annealer's topology

Performance Characteristics

Outperforms random-point addition on both QUBO and HUBO benchmarks
Effective with limited evaluation budget (typical for expensive black-box functions)
GP component computational cost is bounded by on-demand activation
Scales to moderate dimensions (d ~ 20-50) with Hamming-distance kernels

Activation Keywords

adaptive acquisition function selection
BOCS stagnation fix
discrete Bayesian optimization
QUBO optimizer
HUBO optimizer
quantum-inspired black-box optimization
combinatorial Bayesian optimization
adaptive LCB selection
Gaussian process combinatorial search