Breaking the Sequential Bottleneck in Black-Box Optimization

403 concepts346 papers4 proposals

Modern computing hardware is fundamentally parallel. Whether utilizing multi-core CPU clusters, massive GPU grids, or automated robotic laboratories, we have the capacity to run dozens, hundreds, or thousands of evaluations simultaneously. Yet, classical optimization frameworks—most notably Bayesian Optimization (BO)—were born in a sequential era.

In a standard sequential pipeline, an algorithm queries a single point, waits for the evaluation to finish, updates its internal model, and uses that updated model to select the next point. This creates a severe sequential optimization bottleneck: expensive parallel hardware sits idle while a single thread computes the next optimal query. Overcoming this bottleneck requires a fundamental shift from sequential decision-making to batch and parallel architectures.

The Core Challenge: The Cost of Joint Selection

Why not just pick the top $q$ points from a standard acquisition function?

If you naively evaluate a sequential acquisition function (like Expected Improvement) and select the $q$ highest-scoring points, they will almost always cluster tightly around the same local optimum. This redundancy wastes parallel resources.

To avoid this, we must optimize a joint batch acquisition function that balances exploration and diversity across the entire set. However, as Hutter et al. point out, maximizing a joint acquisition function over a batch of $q$ points simultaneously transforms a low-dimensional problem into a high-dimensional, non-convex optimization challenge. The complexity scales exponentially with the batch size, forcing a trade-off between mathematical rigor and computational tractability.

Differentiable and Information-Theoretic Batch Selection

To make batch selection practical, researchers have developed methods to efficiently compute and optimize joint acquisition criteria.

One approach is to derive exact analytical gradients for batch metrics. For instance, Marmin et al. derived a closed-form analytical gradient for multipoint Expected Improvement ($q$-EI). By providing exact gradients, the authors enabled standard gradient-based optimization algorithms to quickly navigate the high-dimensional batch landscape, making parallel black-box design practical.

Alternatively, decision-theoretic and information-theoretic frameworks look at how a whole batch reduces overall uncertainty. Wu et al. introduced the Parallel Knowledge Gradient ($q$-KG), which uses a gradient estimation technique to evaluate how a simultaneous batch of noisy evaluations will change the global optimum. Similarly, Shah et al. proposed Parallel Predictive Entropy Search (PPES), which optimizes an entire batch at once to maximize the information gained about the location of the global maximum.

Enforcing Diversity via Penalization and Geometry

Instead of solving a massive joint optimization problem, another strategy is to pick points sequentially within a batch loop but dynamically alter the landscape to enforce diversity.

González et al. introduced this via local penalization. When a point is selected for the batch, the algorithm estimates the local Lipschitz constant of the function and applies a penalization "dent" around that point in the acquisition landscape. This prevents subsequent points in the same batch from clustering together without requiring a massive joint optimization step.

A more geometric approach leverages Determinantal Point Processes (DPPs). As shown by Kathuria et al., one can define a DPP kernel directly from the Gaussian Process posterior covariance. Sampling from this DPP naturally balances quality (points with high expected value) and diversity (points that are far apart in the feature space), yielding strong theoretical regret bounds while maintaining high parallel throughput.

Asynchronous Execution and Thompson Sampling

Synchronous batch optimization still suffers from a practical flaw: the "straggler" problem. If one evaluation in a batch takes longer than the others, the entire system waits.

To bypass this, researchers leverage Thompson Sampling (TS). In a single-worker setting, Thompson Sampling draws a random function from the posterior distribution and maximizes it. Andreas Krause demonstrated that this exploration-exploitation trade-off can be parallelized effectively. Building on this, Kandasamy et al. showed that Thompson Sampling is uniquely suited for asynchronous parallelization. Because each worker can independently sample a new hallucinated function from the current posterior and immediately evaluate its optimum, workers can submit queries and receive new tasks continuously without ever waiting for a full batch to synchronize.

Eliminating Sequential Algebraic Operations

The sequential bottleneck is not unique to Bayesian Optimization; it also plagues classical and manifold-constrained optimization.

Traditional optimization on manifolds (such as keeping a matrix orthogonal) relies on "retractions"—complex operations like Singular Value Decomposition (SVD) or matrix inversions to project iterates back onto the manifold surface. As Peyré et al. observe, these matrix decompositions are inherently sequential and map poorly to the parallel processing strengths of modern GPUs.

To fix this, Peyré et al. and Vary et al. proposed "landing" algorithms. Instead of strictly enforcing constraints at every step via sequential factorizations, they introduce a dynamical system where iterates are allowed to leave the manifold temporarily but are pulled back via simple matrix multiplications. Because matrix multiplication is highly parallelizable, this approach replaces the scalar and sequential bottlenecks with high-throughput operations, accelerating manifold optimization by orders of magnitude on modern hardware.

Similarly, in classical machine learning optimization, Laue et al. redesigned the L-BFGS-B algorithm for GPUs. They replaced the traditional, highly sequential line search—which relies on heavy scalar processing and complex interpolation—with a parallelizable "working set" approach, unlocking massive speedups by aligning the optimization logic with many-core architectures.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_optimization_bottleneck_11ed1260,
  title = {sequential optimization bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-optimization-bottleneck/rdr_11ed12608b554e04a663b53c37121b77},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_optimization_bottleneck_11ed1260_v1,
  title = {sequential optimization bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-optimization-bottleneck/rdr_11ed12608b554e04a663b53c37121b77/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake