Budgeted Optimization with Constrained Experiments.

Javad Azimi, Xiaoli Z. Fern, Alan FernJAIR 2016 · OpenReview

TL;DR

This paper introduces a new framework for "budgeted optimization with constrained experiments," where instead of specifying exact experimental parameters, we define ranges (constraints) that incur variable costs. They propose novel algorithms for both batch and sequential selection of these constrained experiments, demonstrating their effectiveness in optimizing functions where precise experimentation is impractical.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly in scientific and engineering domains, involve expensive experiments where precisely controlling all input parameters is difficult or impossible. For instance, optimizing the design of nano-enhanced microbial fuel cells involves parameters like nano-wire density and length, which are hard to set exactly. Instead, researchers can specify ranges for these parameters. However, tighter constraints (more precise parameters) lead to higher costs, while looser constraints reduce cost but increase uncertainty about the actual experimental outcome. Traditional Bayesian optimization methods, which assume precise experimental inputs, are not directly applicable here. This paper addresses the challenge of efficiently selecting a sequence of these "constrained experiments" within a limited budget to maximize the chances of finding the optimal function value.

Methods

The authors tackle this problem in two settings:

  • Non-sequential (Batch) Setting: They formulate an objective function that measures the expected maximum output from a batch of selected constrained experiments. This objective is shown to be a non-decreasing submodular function. They then propose a greedy algorithm that iteratively selects the experiment offering the best cost-normalized improvement, along with an accelerated version for efficiency. This approach is guaranteed to achieve a certain approximation factor.
  • Sequential Setting: They extend existing myopic Bayesian optimization heuristics (like Maximum Expected Improvement - MEI) to handle constrained experiments. Crucially, they introduce two cost-sensitive policy frameworks:
  • Cost Normalized (CN): Selects experiments that maximize the heuristic value per unit cost.
  • Constrained Minimum Cost (CMC): Selects experiments that balance heuristic value with cost, ensuring the expected improvement is at least as good as a random policy for the same budget. They specifically highlight CMC-MEI as a robust, parameter-free method.

Datasets

The authors evaluate their methods on:

  • Synthetic Functions: Five 2-dimensional functions (Cosines, Rosenbrock, Discontinuous, Hydrogen, Fuel Cell) are used.
  • Real-World Data:
    • Data from a study on biosolar hydrogen production (66 samples) is used to simulate a true function by fitting a Gaussian Process (GP) model.
  • Data from microbial fuel cell experiments (16 samples) is used to simulate a true function via polynomial Bayesian regression.

Key Insights and Ideas

  • The Cost-Uncertainty Trade-off is Central: The core challenge is managing the inherent trade-off between the cost of an experiment and the uncertainty it introduces about the actual experimental outcome. Looser constraints mean lower cost but higher uncertainty.
  • Constrained Experiments as a Practical Necessity: For many real-world problems, specifying ranges (constraints) is more practical and informative than attempting to hit exact points.
  • Submodularity is Key for Batch Optimization: Demonstrating that the objective function is submodular allows for the application of efficient greedy algorithms with theoretical guarantees in the non-sequential setting.
  • Cost-Sensitive Policies are Crucial for Sequential Optimization: Simply applying standard heuristics to constrained experiments can lead to selecting overly expensive options. The CN and CMC policies provide principled ways to incorporate cost into the selection process.
  • CMC-MEI Emerges as a Strong Contender: The Constrained Minimum Cost policy combined with the Maximum Expected Improvement heuristic (CMC-MEI) consistently performs well across various functions and cost structures, and importantly, is parameter-free.

Key Results

  • Non-sequential Greedy Algorithm: Consistently outperforms a random policy, especially when cost slopes are smaller, indicating its ability to leverage tighter constraints effectively.
  • Sequential Policies: Generally outperform non-sequential methods, as expected, due to their ability to update the model with each experiment.
  • CMC-MEI Performance: Demonstrates robust performance across all tested functions and cost models, often outperforming other model-based and model-free sequential policies. It generally achieves significantly lower normalized regrets compared to random policies. For example, on the "Hydrogen" function with a slope of 0.1, CMC-MEI achieves a normalized regret of 0.129 (±0.04), compared to 0.879 (±0.06) for RR/BRR.
  • Comparison with Precise Experiments: CMC-MEI (using constrained experiments) performs comparably to MEI (using precise experiments), suggesting that the proposed approach can achieve similar performance without the need for exact parameter control.

Limitations and Future Work

  • Low-Dimensional Focus: The current work focuses on low-dimensional problems (2D). Extending these methods to higher dimensions would require optimizing selection criteria over continuous input spaces, which is a natural direction for future work.
  • Cost Model Simplification: The cost function is defined as a simple formula. Real-world cost structures might be more complex.
  • Enriching Cost and Action Models: Future work could involve developing more sophisticated cost and action models that more closely align with real-world applications, potentially requiring tighter integration of planning and scheduling techniques.
  • Parameter-Free Recommendation: The authors recommend CMC-MEI due to its consistent performance and lack of parameter tuning, but acknowledge that other CMC variants (like CMC-MPI) can be competitive in specific scenarios.

Summary updated

Abstract

Motivated by a real-world problem, we study a novel budgeted optimization problem where the goal is to optimize an unknown function f(.) given a budget by requesting a sequence of samples from the function. In our setting, however, evaluating the function at precisely specified points is not practically possible due to prohibitive costs. Instead, we can only request constrained experiments. A constrained experiment, denoted by Q, specifies a subset of the input space for the experimenter to sample the function from. The outcome of Q includes a sampled experiment x, and its function output f(x). Importantly, as the constraints of Q become looser, the cost of fulfilling the request decreases, but the uncertainty about the location x increases. Our goal is to manage this trade-off by selecting a set of constrained experiments that best optimize f(.) within the budget. We study this problem in two different settings, the non-sequential (or batch) setting where a set of constrained experiments is selected at once, and the sequential setting where experiments are selected one at a time. We evaluate our proposed methods for both settings using synthetic and real functions. The experimental results demonstrate the efficacy of the proposed methods.
BibTeX
@article{azimi2016budgeted,
  author = {Javad Azimi and Xiaoli Z. Fern and Alan Fern},
  title = {{Budgeted Optimization with Constrained Experiments.}},
  journal = {J. Artif. Intell. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=lO9-2Vf0vnbT},
}
Figure