Bayesian Optimization with Directionally Constrained Search

Yang Li, Yaqiang Yao

Abstract

Bayesian optimization (BO) offers a flexible framework to optimize an objective function that is expensive to be evaluated. A Bayesian optimizer iteratively queries the function values on its carefully selected points. Subsequently, it makes a sensible recommendation about where the optimum locates based on its accumulated knowledge. This procedure usually demands a long execution time. In practice, however, there often exists a computational budget or an evaluation limitation allocated to an optimizer, due to the resource scarcity. This constraint demands an optimizer to be aware of its remaining budget and able to spend it wisely, in order to return as better a point as possible. In this paper, we propose a Bayesian optimization approach in this evaluation-limited scenario. Our approach is based on constraining searching directions so as to dedicate the model capability to the most promising area. It could be viewed as a combination of local and global searching policies, which aims at reducing inefficient exploration in the local searching areas, thus making a searching policy more efficient. Experimental studies are conducted on both synthetic and real-world applications. The results demonstrate the superior performance of our newly proposed approach in searching for the optimum within a prescribed evaluation budget.

Introduction: The Challenge of Limited Budgets in BO

Bayesian Optimization is the gold standard for optimizing "expensive" black-box functions—situations where every single trial costs significant time or money, such as tuning massive neural networks or running physical experiments. While effective, standard acquisition functions like Expected Improvement (EI) often suffer from "jiggling": the optimizer spends too many evaluations jumping around a promising area without actually converging, or it explores too aggressively even when the budget is nearly exhausted.

In a world of finite resources, we need an optimizer that knows how to "settle down" and follow a promising path as the clock ticks down. This paper introduces Directionally Constrained Bayesian Optimization (DCBO), a method that improves search efficiency by leveraging the history of successful steps as a "latent gradient" to guide the search more purposefully.

The authors propose a new acquisition framework that combines global exploration with a directional constraint ($H(x)$).

The Directional Constraint

Instead of just looking for high improvement, the algorithm prefers points that lie in a direction similar to the previous step. This ensures the search path maintains an acute angle between successive steps, mimicking the efficiency of gradient descent without actually needing access to gradients.

Figure 2: Geometry of the directional constraint, showing the relationship between the previous step $g_{t-1}$ and the target direction $g_t^*$.

Probabilistic Directional Modeling

To model these directional probabilities mathematically, the algorithm uses the Von Mises-Fisher (VMF) distribution—essentially a "Gaussian on a sphere." By using directional statistics, the authors provide a sound way to update the "belief" about which way the optimizer should be heading.

Figure 3: Probabilistic modeling of directions using the Von Mises-Fisher distribution on a unit circle.

Budget-Aware Balancing

They introduce a time-varying parameter, $\rho(t)$, which increases as the number of iterations grows. The final acquisition function is a weighted product: $H(x)^{\rho(t)} \cdot EI(x)^{1-\rho(t)}$.

  • Early on: $\rho(t)$ is small, so the algorithm behaves like standard BO (global exploration).
  • Later on: $\rho(t)$ grows, forcing the algorithm to focus on local, directionally-consistent refinement in the most promising regions.

Experimental Evaluation

The authors evaluated DCBO against several benchmarks, including synthetic multi-modal functions and real-world industrial datasets:

  • Industrial Milk Evaporator (milk): A 3-dimensional sequential dataset used to tune the parameters of a Linear Dynamical System (LDS).
  • Motion Capture (motion): A high-dimensional (10D subset used) dataset of sensor readings, also used for LDS parameter estimation.

Key Results

  • Faster Convergence: In synthetic tests, DCBO reached the global optimum significantly faster than standard constrained BO (cBO) and Probability of Improvement (PoI).
  • Reduced Jiggling: Qualitative traces show that while standard BO "jiggles" aimlessly near the end of a budget, DCBO exhibits a more "purposeful" local search behavior.
  • Real-World Performance: On the milk and motion datasets, DCBO consistently achieved lower negative log-likelihoods than popular methods like UCB and EI. Notably, it maintained a steady decreasing trend even when other methods stalled.

Conclusion and Future Work

DCBO’s directional consistency helps it "break through" plateaus by maintaining momentum toward the optimum. While the current $\rho(t)$ schedule is a simple linear function of time, future work could explore adaptive schedules that react to the ruggedness of the function being optimized. Additionally, automating the tuning of the balance between global and local search remains an open challenge for high-dimensional constraint manifolds.

Summary updated

Abstract

Bayesian optimization offers a flexible framework to optimize an objective function that is expensive to be evaluated. A Bayesian optimizer iteratively queries the function values on its carefully selected points. Subsequently, it makes a sensible recommendation about where the optimum locates based on its accumulated knowledge. This procedure usually demands a long execution time. In practice, however, there often exists a computational budget or an evaluation limitation allocated to an optimizer, due to the resource scarcity. This constraint demands an optimizer to be aware of its remaining budget and able to spend it wisely, in order to return as better a point as possible. In this paper, we propose a Bayesian optimization approach in this evaluation-limited scenario. Our approach is based on constraining searching directions so as to dedicate the model capability to the most promising area. It could be viewed as a combination of local and global searching policies, which aims at reducing inefficient exploration in the local searching areas, thus making a searching policy more efficient. Experimental studies are conducted on both synthetic and real-world applications. The results demonstrate the superior performance of our newly proposed approach in searching for the optimum within a prescribed evaluation budget.
BibTeX
@misc{li2019bayesian,
  author = {Yang Li and Yaqiang Yao},
  title = {{Bayesian Optimization with Directionally Constrained Search}},
  year = {2019},
  eprint = {1906.09459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.09459},
}
Figure