Constrained Two-step Look-Ahead Bayesian Optimization

Duke Zhang, Xiangyu Zhang, Peter I. FrazierNeurIPS 2021 · OpenReview

TL;DR

This paper introduces 2-OPT-C, a novel Bayesian Optimization (BO) algorithm designed for problems with inequality constraints. It significantly improves query efficiency and computational speed compared to existing methods by employing a "two-step lookahead" strategy and a new likelihood-ratio-based gradient estimator that overcomes challenges posed by constraint discontinuities.

What Problem Does This Paper Address?

Bayesian Optimization (BO) is a powerful technique for optimizing expensive-to-evaluate black-box functions. However, many real-world problems involve constraints (e.g., ensuring a machine learning model is accurate and fast, or a chemical process is effective and safe). Existing methods for constrained BO (CBO) are often "myopic," meaning they only consider the immediate improvement from an evaluation. This can be inefficient, especially when the optimal solution lies near the boundary of the feasible region. While non-myopic BO has shown promise for unconstrained problems, extending it to constrained settings is challenging. Existing non-myopic CBO methods are computationally expensive, often relying on brute-force optimization or techniques that fail when constraints introduce discontinuities in the optimization landscape. This paper addresses the need for an efficient, non-myopic CBO method that can effectively navigate these constrained, discontinuous spaces.

Methods

The core contribution is the 2-OPT-C acquisition function. Unlike myopic methods that look one step ahead, 2-OPT-C looks two steps ahead, considering the potential improvement after evaluating two points. This "two-step lookahead" allows the algorithm to better balance immediate gains with future information gathering, particularly around constraint boundaries.

A key technical challenge in optimizing non-myopic acquisition functions is estimating their gradients. Standard methods like Sample Average Approximation (SAA) and Infinitesimal Perturbation Analysis (IPA) rely on the reparameterization trick, which breaks down when constraints create discontinuities in the acquisition function's surface. To overcome this, the authors develop a novel approach using the likelihood ratio method. This method provides an unbiased estimator of the gradient without requiring the reparameterization trick, making it robust to these discontinuities. This gradient estimator is then used within a multistart stochastic gradient ascent procedure to efficiently optimize the 2-OPT-C acquisition function. The method is designed to support both sequential and batch evaluations.

Datasets

The paper evaluates its method on:

  • Three synthetic problems (P1, P2, P3): These are standard benchmarks used in prior CBO research, allowing for direct comparison.
  • Two real-world problems:
    • Portfolio optimization: Maximizing annualized return subject to constraints.
  • Robot pushing: A task likely involving physical constraints.

The authors note that detailed descriptions of these problems are available in the supplement.

Key Insights and Ideas

  • Non-myopia is more important in constrained BO: The fear of violating constraints pushes myopic methods away from the critical boundary region. Non-myopic methods, by looking ahead, can strategically explore this boundary, which is crucial for finding solutions with tight constraints.
  • Constraint discontinuities are a major hurdle: Standard gradient-based optimization techniques for non-myopic BO fail because constraints can make the acquisition function surface discontinuous.
  • Likelihood ratio method as a solution: This technique offers a principled way to estimate gradients in the presence of discontinuities, enabling efficient optimization of complex acquisition functions.
  • Two-step lookahead offers a sweet spot: While longer lookaheads are possible, the paper argues that a two-step approach provides a good balance between computational cost and performance improvement.

Key Results

  • Significant query efficiency gains: 2-OPT-C consistently outperforms myopic CBO methods, achieving utility gaps that are often 2x better and sometimes 10x better. For example, on problem P1, 2-OPT-C reaches a utility gap of $10^{-5}$ in 27 evaluations, while the best myopic method (EIC) is at $10^{-3}$ with the same number of evaluations.
  • Competitive with or better than existing non-myopic methods: Compared to the rollout algorithm from [1], 2-OPT-C provides comparable or better solution quality, often by a factor of 2, especially with tight evaluation budgets.
  • Computational efficiency: Despite its non-myopic nature, 2-OPT-C is computationally more efficient than the existing non-myopic CBO method [1], which relies on expensive brute-force optimization. For instance, optimizing a batch of 5 points takes 25-30 minutes.
  • Robustness to discontinuities: The likelihood ratio method allows 2-OPT-C to effectively optimize acquisition functions even when discontinuities are present, unlike methods relying on the reparameterization trick.

Limitations and Future Work

  • Computational cost: While more efficient than prior non-myopic CBO, further reductions in computational cost are still desirable.
  • Theoretical investigation: The authors suggest further theoretical work to understand why their method provides such significant improvements.
  • Societal impact: The paper briefly touches upon the broader implications of faster optimization for engineering and AI, suggesting that understanding the societal effects of improved optimization capabilities is an important area for future research.
  • Parameter $\delta$: The theoretical analysis uses a parameter $\delta > 0$ to ensure differentiability, but in practice, $\delta=0$ is used. Further exploration of the role and practical implications of $\delta$ could be beneficial.

Summary updated

Abstract

Recent advances in computationally efficient non-myopic Bayesian optimization offer improved query efficiency over traditional myopic methods like expected improvement, with only a modest increase in computational cost. These advances have been largely limited to unconstrained BO methods with only a few exceptions which require heavy computation. For instance, one existing multi-step lookahead constrained BO method (Lam & Willcox, 2017) relies on computationally expensive unreliable brute force derivative-free optimization of a Monte Carlo rollout acquisition function. Methods that use the reparameterization trick for more efficient derivative-based optimization of non-myopic acquisition functions in the unconstrained setting, like sample average approximation and infinitesimal perturbation analysis, do not extend: constraints introduce discontinuities in the sampled acquisition function surface. Moreover, we argue here that being non-myopic is even more important in constrained problems because fear of violating constraints pushes myopic methods away from sampling the boundary between feasible and infeasible regions, slowing the discovery of optimal solutions with tight constraints. In this paper, we propose a computationally efficient two-step lookahead constrained Bayesian optimization acquisition function (2-OPT-C) supporting both sequential and batch settings. To enable fast acquisition function optimization, we develop a novel likelihood ratio-based unbiased estimator of the gradient of the two-step optimal acquisition function that does not use the reparameterization trick. In numerical experiments, 2-OPT-C typically improves query efficiency by 2x or more over previous methods, and in some cases by 10x or more.
BibTeX
@inproceedings{zhang2021constrained,
  author = {Duke Zhang and Xiangyu Zhang and Peter I. Frazier},
  title = {{Constrained Two-step Look-Ahead Bayesian Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=oVEGzC7ieOB},
}
Figure