Source-linked AI summary
Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration
Emile Contal, David Buffoni, Alexandre Robicquet, Nicolas Vayatis
TL;DR
The paper studies costly noisy maximization with parallel batches and unknown horizons. It introduces GP-UCB-PE, combining UCB with Pure Exploration, and derives regret bounds showing order-√K improvement over sequential methods while confirming empirical effectiveness.
Problem
The paper addresses how to maximize an unknown function from costly noisy evaluations acquired in parallel batches, while minimizing cumulative regret.
Method
GP-UCB-PE combines a Gaussian Process UCB query with Pure Exploration queries within each batch of K evaluations.
Results
Theoretical regret bounds improve over sequential GP optimization by a ratio of √K, and experiments confirm effectiveness against GP-BUCB and SM-UCB.
Takeaways & Limitations
Parallelization can improve regret bounds while GP-UCB-PE remains empirically effective on real and synthetic problems.
Takeaways & Limitations
The paper conjectures that a more exploitative greedy strategy has unbounded regret for general GPs and lacks formally specified assumptions for guarantees.
Abstract
from arXiv · showhide
In this paper, we consider the challenge of maximizing an unknown function f for which evaluations are noisy and are acquired with high cost. An iterative procedure uses the previous measures to actively select the next estimation of f which is predicted to be the most useful. We focus on the case where the function can be evaluated in parallel with batches of fixed size and analyze the benefit compared to the purely sequential procedure in terms of cumulative regret. We introduce the Gaussian Process Upper Confidence Bound and Pure Exploration algorithm (GP-UCB-PE) which combines the UCB strategy and Pure Exploration in the same batch of evaluations along the parallel iterations. We prove theoretical upper bounds on the regret with batches of size K for this procedure which show the improvement of the order of sqrt{K} for fixed iteration cost over purely sequential versions. Moreover, the multiplicative constants involved have the property of being dimension-free. We also confirm empirically the efficiency of GP-UCB-PE on real and synthetic problems compared to state-of-the-art competitors.
1 Introduction
The paper addresses noisy, costly maximization of non-convex functions, especially when evaluations occur in parallel batches. It introduces GP-UCB-PE, combining UCB and Pure Exploration to improve parallel optimization efficiency.
- Motivation: Noisy sequential maximization of non-convex functions is important in applications with expensive evaluations and high-dimensional inputs.Examples include industrial sensor placement and optimization of heavy numerical codes.
- Objective: Cumulative regret measures the sum of gaps between queried function values and the true optimum.
- Parallel setting: Parallel batches of K evaluations can incur no additional batch cost when K sensors or computing cores are available.
- Contribution: GP-UCB-PE combines UCB and Pure Exploration within each batch to reduce uncertainty and support locating the maximum.
- Contribution: Compared with GP-BUCB, GP-UCB-PE removes the need for an initialization phase.
2 Problem Statement and Background
The problem is batch optimization of an unknown function under noisy observations and an unknown horizon. Gaussian Processes provide a posterior mean and variance for guiding queries and confidence-based analysis.
- Problem formulation: The objective is to find the maximum of an unknown function f over X ⊂ R^d using batches of K noisy evaluations.
- Objective: The horizon T is unknown, so the strategy must perform well at every iteration.
- Objective: Batch cumulative regret sums the losses associated with the queried points, under a fixed cost for each evaluation batch.
- Theoretical analysis: The analysis provides upper bounds for batch regret and full cumulative regret, including bounds on the gap between the best point found and the true maximum.
- Gaussian Processes: A Gaussian Process models nearby function values as correlated through a mean function and covariance kernel.
- Gaussian Processes: Conditioning a known-kernel, zero-mean GP on observations yields a posterior GP with location-specific mean and variance.
- Gaussian Processes: The posterior is computed from noisy observations, their covariance vector, and a kernel matrix augmented by the noise variance.
- Gaussian Processes: Common kernels include polynomial, radial basis function, and Matérn-family constructions.
3 Parallel Optimization Procedure
GP-UCB-PE uses confidence bounds to identify promising regions, then combines one UCB query with information-seeking Pure Exploration queries in each batch. The exploration points are selected greedily to reduce posterior uncertainty.
- Confidence bounds: The GP posterior defines upper and lower confidence bounds containing f with high probability when β_t grows as O(log t).
- Relevant region: The relevant region contains the likely maximizer and discards locations where the optimum is unlikely to occur.
- Relevant region: The modified relevant region also contains the maximizer of the upper confidence bound, preserving influence on subsequent query choices.
- GP-UCB-PE: GP-UCB-PE selects the first point in a batch using the GP-UCB rule and the remaining K − 1 points using Pure Exploration.
- GP-UCB-PE: The UCB criterion balances exploration of high posterior variance against exploitation of high posterior mean.
- Pure Exploration: Pure Exploration maximizes information gain within the relevant region, defined as entropy reduction from observing candidate locations.
- Pure Exploration: Because information gain is submodular, the NP-complete batch selection problem can be efficiently approximated greedily without backtracking.
- Pure Exploration: The greedy exploration points use updated posterior variances, which do not depend on the observed noisy values.
4 Regret Bounds
The paper derives high-probability regret bounds for GP-UCB-PE in terms of maximum information gain, under finite or compact convex input domains. For K much smaller than T, the simple-regret bound improves over sequential GP-UCB by an order involving K, while full batch cumulative regret is equivalent.
- Main Result: The regret bounds are expressed through γ_TK, the maximum information gain from a sequential sequence of TK queries.For common kernels, the resulting growth rates depend on the kernel and input dimension through γ_TK.
- Main Result: Theorem 1 bounds GP-UCB-PE batch cumulative regret with high probability for Gaussian-process functions of bounded variance.The calibration of β_t ensures the confidence region contains f with probability at least 1 − δ.
- Discussion: When K ≪ T, the bound for R^K_T improves over sequential GP-UCB by an order of √K, while R_TK is equivalent when all batch queries matter.Compared with prior parallel strategies, GP-UCB-PE also removes the need for an initialization phase.
- Discussion: With RBF kernels, the information-gain discussion reports that the improvement can be doubly exponential in the dimension d.The paper also states that GP-UCB-PE avoids multiplying the uncertainty parameter by an initialization-dependent information-gain factor.
- Proof Strategy: The proof combines UCB regret control with Pure Exploration queries that gather information and accelerate uncertainty reduction.Intermediate lemmas relate UCB deviations to preceding Pure Exploration deviations and bound aggregate variances through γ_TK.
- Main Result: For compact convex domains, the cumulative bound has the form C1β_Tγ_TK + C2, with C1 and C2 specified in the theorem analysis.For finite domains, the analysis gives a corresponding C1β_Tγ_TK form.
5 Experiments
The experiments evaluate GP-UCB-PE against GP-BUCB and SM-UCB on three real applications and two synthetic problems. Using batches of 10 and averages over 64 runs, the comparisons show algorithm-dependent performance across task types.
- Protocol: The evaluation compares GP-UCB-PE with GP-BUCB and SM-UCB on three real applications and two synthetic problems.Figure 4 reports the evolution of batch regret across these tasks.
- Protocol: All experiments use batch size K = 10, random initialization with 20 observations, and averages with confidence intervals over 64 experiments.Kernel-prior parameters, including the RBF bandwidth, are selected by marginal-likelihood maximization.
- Data Sets: The synthetic benchmarks include Generated GP, Gaussian Mixture, Himmelblau, and Mackey-Glass functions with varied dimensionality, noise, and optimization difficulty.The Gaussian Mixture has a thin highest peak, while Himmelblau tests exploration–exploitation tradeoffs and Mackey-Glass is chaotic.
- Results: SM-UCB performs similarly to GP-UCB-PE on synthetic functions, better on the noiseless chaotic task, and worse on real noisy data.The comparison is reported for Figures 4(a)–4(f).
- Results: GP-BUCB performs well on difficult real tasks but loses time during initialization on synthetic Gaussian or polynomial tasks.The Abalone task’s dimensionality is already described as a limitation for GP-BUCB with the RBF kernel.
6 Conclusion
GP-UCB-PE combines Pure Exploration with UCB in parallel batches, yielding theoretically improved regret bounds and empirical effectiveness. The paper also identifies a trade-off: more exploitative strategies can reduce regret faster in practice but lack general guarantees.
- GP-UCB-PE combines UCB and Pure Exploration within batches of K noisy evaluations.
- Parallelization improves GP-UCB-PE's cumulative-regret bounds over sequential GP optimization by a ratio of K.
- GP-UCB-PE has strictly better regret bounds than GP-BUCB, a concurrent parallel GP-optimization algorithm.
- Experiments against GP-BUCB and SM-UCB confirmed GP-UCB-PE's effectiveness across several applications.
- Combining Pure Exploration queries within a batch may extend to other methods and to regret proofs based on uncertainty reduction.
- More exploitative strategies can decrease regret faster in practice, but the K-times GP-UCB strategy may have unbounded regret for general Gaussian Processes.