PaperlayerView exact revision on arXiv

Source-linked AI summary

BINOCULARS for Efficient, Nonmyopic Sequential Experimental Design

Shali Jiang, Henry Chai, Javier Gonzalez, Roman Garnett

arXiv:1909.04568v3cs.LGstat.ML

TL;DR

Finite-horizon sequential experimental design has an intractable optimal policy, while common approximations can be myopic. BINOCULARS uses an optimal batch to guide a single sequential choice, and experiments across Bayesian optimization and Bayesian quadrature report advantages over myopic policies and efficiency over nonmyopic alternatives.

  • Problem

    Finite-horizon sequential experimental design requires an intractable dynamic-programming policy, while popular one-step policies can be myopic and over-exploit.

    Source: §1 · p. 1

  • Method

    BINOCULARS computes an optimal batch of experiments and selects one point from it for sequential evaluation.

    Source: §1 · p. 1

  • Results

    Across its applications, BINOCULARS significantly outperforms commonly used myopic policies while being much more efficient than popular nonmyopic alternatives.

    Source: §7 · p. 8

  • Takeaways & Limitations

    The framework is realized for Bayesian optimization and Bayesian quadrature, including the first nonmyopic policy proposed for Bayesian quadrature.

    Source: §1 · p. 2

    With an imperfect model, planning too far ahead can hurt empirical performance, and smaller lookahead horizons are more computationally efficient.

    Source: §4 · p. 4

Abstract

from arXiv · show

Finite-horizon sequential experimental design (SED) arises naturally in many contexts, including hyperparameter tuning in machine learning among more traditional settings. Computing the optimal policy for such problems requires solving Bellman equations, which are generally intractable. Most existing work resorts to severely myopic approximations by limiting the decision horizon to only a single time-step, which can underweight exploration in favor of exploitation. We present BINOCULARS: Batch-Informed NOnmyopic Choices, Using Long-horizons for Adaptive, Rapid SED, a general framework for deriving efficient, nonmyopic approximations to the optimal experimental policy. Our key idea is simple and surprisingly effective: we first compute a one-step optimal batch of experiments, then select a single point from this batch to evaluate. We realize BINOCULARS for Bayesian optimization and Bayesian quadrature -- two notable SED problems with radically different objectives -- and demonstrate that BINOCULARS significantly outperforms myopic alternatives in real-world scenarios.

1. Introduction

Finite-horizon sequential experimental design requires balancing exploration and exploitation, but its optimal dynamic-programming policy is generally intractable. BINOCULARS approximates that policy through batch design and is reported to outperform myopic baselines while remaining efficient.

1. Introduction

  • Finite-horizon SED seeks to maximize a data-dependent utility over a prespecified number of adaptive experiments, but its optimal policy is generally intractable.The policy is formulated as dynamic programming that balances exploration against exploitation.Source: §1 · p. 1
  • BINOCULARS computes an optimal batch of experiments, then selects one point from it for sequential evaluation.The optimal batch expected utility is a lower bound on optimal sequential expected utility and is tighter than the one-step policy’s implied expected utility.Source: §1 · p. 1
  • Popular one-step-optimal policies, including expected improvement for BO and uncertainty sampling for BQ, are computationally efficient but can be myopic and over-exploit.Recent nonmyopic BO alternatives have promising results but are typically costly to compute.Source: §1 · pp. 1–2
  • Experiments show BINOCULARS significantly outperforms myopic baselines and is competitive with or better than state-of-the-art nonmyopic alternatives while being much more efficient.The framework is realized for Bayesian optimization and Bayesian quadrature, and is the first nonmyopic policy proposed for Bayesian quadrature.Source: §1 · p. 2

2. BINOCULARS

BINOCULARS approximates finite-horizon sequential design by using an optimal non-adaptive batch to guide the next experiment. Its batch objective is a tractable lower bound on adaptive value, while the full adaptive policy is generally intractable.

2. BINOCULARS

  • For BO, the two-point batch-informed choices are described as nearly perfect relative to the expensive full two-step expected-improvement policy.The method first forms a two-point batch using 2-EI, then selects a point and uses EI conditioned on its observation for the next choice.Source: §2 · p. 2, Figure 1 · p. 3

2.1. The Optimal Adaptive Policy

  • The optimal adaptive policy uses a Bellman equation, but is intractable for moderately large horizons; limiting lookahead is efficient but myopic.Restricted lookahead can make suboptimal exploration–exploitation tradeoffs because it plans only a limited distance into the future.Source: §2.1 · p. 2

2.2. Nonmyopic Approximation via the Optimal Non-Adaptive Policy

  • The batch objective lower-bounds true adaptive expected utility because it exchanges the future expectation and maximization and uses a non-adaptive future utility.The batch and adaptive formulations coincide when remaining experiments are conditionally independent given observed data.Source: §2.2 · p. 3
  • Computing the optimal batch is the primary computational cost, and the paper reports gradient-based optimization for the BO and BQ examples.The batch policy is therefore used to guide a sequential design rather than to observe all batch outcomes at once.Source: §2.2 · p. 3
  • BINOCULARS repeatedly computes an optimal batch, chooses one experiment from it, observes its outcome, and continues sequentially.The batch is a subroutine; each iteration observes only one experiment’s outcome.Source: §2.2 · p. 3

3. BINOCULARS for Bayesian Optimization

For Bayesian optimization, the paper models the objective with a Gaussian process and seeks to maximize the best observed value within a fixed evaluation budget. It defines adaptive expected-improvement lookahead and applies BINOCULARS by optimizing a batch-EI objective before choosing one point.

3. BINOCULARS for Bayesian Optimization

  • Bayesian optimization selects T evaluations to maximize the best observed function value, with the objective modeled by a Gaussian process.The recommended maximizer is the point with the highest observed value after the evaluation budget is spent.Source: §3 · p. 3
  • EIk denotes the expected improvement from k adaptive decisions, with later decisions conditioned on each observation and the incumbent updated.The one-step EI policy is one-step optimal, while EI2 is analytically intractable because it requires numerical integration with a global optimization inside the integrand.Source: §3 · p. 4
  • For BO, BINOCULARS optimizes batch EI, also called q-EI, then selects one point from the resulting optimal batch.The framework can use other utility functions by replacing q-EI, including knowledge gradient, probability of improvement, and predictive entropy.Source: §3 · p. 4

4. BINOCULARS for Bayesian Quadrature

For Bayesian quadrature, BINOCULARS optimizes a batch using joint entropy and selects a point to evaluate; the choice of lookahead size trades computation against empirical performance.

4. BINOCULARS for Bayesian Quadrature

  • Bayesian quadrature estimates integrals such as likelihood-weighted prior integrals; with fixed GP hyperparameters, its optimal design can be precomputed.The posterior covariance then does not depend on observed function values, eliminating the need for sequential design in that setting.Source: §4 · p. 4
  • For non-negative integrands modeled through a transformation, the approximate GP posterior can depend on observed values, making adaptive sampling critical.Posterior covariance then depends on observed values.Source: §4 · p. 4
  • Uncertainty sampling is a computationally efficient surrogate that greedily reduces integrand entropy rather than the entropy of the integral.It selects the location with the largest variance.Source: §4 · p. 4
  • BINOCULARS maximizes joint differential entropy over q-point batches through DPP mode optimization, while one-point entropy maximization corresponds to uncertainty sampling.The batch objective can be optimized with gradient-based methods.Source: §4 · p. 4
  • “Best” and “proportional sampling” perform similarly when choosing a batch point, while “uniform sampling” performs worse.Source: §4 · p. 4
  • Planning to the full remaining budget is not necessarily best with an imperfect model, and smaller q values reduce computation.The authors empirically study the choice of q.Source: §4 · p. 4

5. Related Work

Prior nonmyopic work spans Bayesian optimization and active learning of Gaussian processes, with approaches differing in how they construct future decisions and computationally approximate them. The paper distinguishes its Bayesian quadrature setting from active learning focused on GP hyperparameters.

5. Related Work

  • Earlier Bayesian optimization work includes optimal lookahead policies, GLASSES, rollout, and branch-and-bound methods, with some approaches requiring expensive computation or specific assumptions.The cited branch-and-bound policy assumes Lipschitz-continuous rewards; two-step EI requires an expensive quadrature subroutine.Source: §5 · pp. 4–5
  • GLASSES constructs future batches heuristically, whereas BINOCULARS optimizes them with q-EI; rollout instead constructs future points adaptively from sampled outcomes.Both GLASSES and rollout are described as very expensive to compute.Source: §5 · p. 5
  • The authors report being unaware of prior nonmyopic Bayesian quadrature work, and distinguish their setting from GP active learning focused on hyperparameter learning.For non-negative integrands, transformation-based approximate posteriors can depend on observations even when GP hyperparameters are known.Source: §5 · p. 5
  • Prior active-GP-learning methods include separating exploration and exploitation, and ε-BAL, which approximates a Bellman solution using truncated sampling.Krause and Guestrin (2007) proposed the former; Hoang et al. (2014) developed ε-BAL and an anytime pruning-based version.Source: §5 · p. 5

6. Experiments

Across Bayesian optimization (BO) and Bayesian quadrature (BQ), BINOCULARS outperforms myopic baselines with modest additional computation and is at least as good as prior nonmyopic methods while running much faster. The experiments show nonmyopic behavior in both tasks.

6. Experiments

  • Experiments compare BINOCULARS with myopic and nonmyopic baselines for BO and BQ, with most results aggregated over 100 random initializations.Each run starts with 2d observations and performs 20d further iterations, where d is the function dimensionality.Source: §6 · pp. 5–6
  • BINOCULARS outperforms myopic baselines while running only slightly slower, and is at least as good as previously proposed nonmyopic methods while running orders of magnitude faster.The paper places it on the Pareto front of the running time–performance tradeoff in policy design.Source: §6 · p. 5

6.1. BO Results

  • On hard synthetic BO functions, all q.EI.s variants significantly outperform EI on average; 12.EI.s performs best, and performance generally improves with q up to 12.12.EI.s initially trails EI, catches up at about 20% of the budget, then outperforms it by a large margin; the plotted result averages GAP over nine functions.Source: §6.1 · pp. 6–7, Figure 2 · p. 6, Table 1 · p. 6
  • On real BO functions, all q.EI.s variants outperform EI; 6.EI.s is close to the strongest nonmyopic baseline, while the proposed methods are considerably faster at similar GAP performance.Table 2 averages 50 repeats, and Figure 3 compares mean GAP with per-iteration time over seven functions and 350 experiments.Source: §6.1 · p. 7, Table 2 · p. 7, Figure 3 · p. 7

6.2. BQ Results

  • Across 800 BQ experiments, 2.DPP.s significantly outperforms the tested methods, is considerably faster than rollout, and is only slightly slower than UNCT.Figure 4(c) plots median fractional error against average time per iteration; Table 3 reports terminal median fractional errors.Source: §6.2 · p. 8, Table 3 · p. 8, Figure 4 · p. 8
  • For BQ, q.DPP.s variants tend to outperform q.DPP.b variants, while increasing batch size q does not consistently improve performance.On synthetic BQ functions, 2.DPP.s initially lags UNCT before overtaking it, illustrating nonmyopic behavior.Source: §6.2 · p. 8

7. Conclusion and Future Work

BINOCULARS approximates finite-horizon sequential experimental design by computing an optimal batch and selecting one point, and the paper applies it to Bayesian optimization and quadrature. The authors report improved performance over myopic policies and greater efficiency than popular nonmyopic alternatives, while identifying theoretical questions for future work.

7. Conclusion and Future Work

  • BINOCULARS significantly outperforms commonly used myopic policies while being much more efficient than popular nonmyopic alternatives.The authors report this result across applications to Bayesian optimization and Bayesian quadrature.Source: §7 · p. 8
  • BINOCULARS is an efficient, nonmyopic approximation framework for finite-horizon sequential experimental design.The approach computes an optimal batch, then selects one point from it.Source: §7 · p. 8
  • The framework is applied to Bayesian optimization and Bayesian quadrature, two different sequential experimental design problems.Source: §7 · p. 8
  • Future work includes theory to guide lookahead horizon q and explicit adaptivity-gap bounds for a general class of problems.Source: §7 · p. 9

A. Full-Lookahead Expected Improvement as Bellman Equation

The appendix frames full-lookahead expected improvement as a Bellman recursion over sequential decisions. At one remaining evaluation it reduces to ordinary expected improvement, while two-step utility requires integrating over the next observation, location, and value.

A. Full-Lookahead Expected Improvement as Bellman Equation

B. Additional Bayesian Optimization Results

Additional Bayesian optimization results show that BINOCULARS variants outperform EI on average across synthetic functions, while rollout and GLASSES fare worse than EI on a selected five-function set. On real functions, sampling and best variants do not consistently outperform one another.

B. Additional Bayesian Optimization Results

Related papers

Loading 1909.04568v3…