Adaptive Acquisition Bbo

---
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:

1. **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.

2. **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.

3. **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

4. **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

1. **On-demand GP activation**: GP component only runs when BOCS stalls, keeping computational cost low.

2. **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.

3. **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.

4. **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:

```python
# 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