Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations

By Nando de Freitas, Alex Smola, Masrour Zoghi. 2012

116 citations recorded by the source corpus.

This paper analyzes the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, (Srinivas et al., 2010) proved that the regret vanishes at the approximate rate of O(1/√t), where t is the number of observations. To complement their result, we attack the deterministic case and attain a much faster exponential convergence rate. Under some regularity assumptions, we show that the regret decreases asymptotically according to O(e-τt/(ln t)d/4) with high probability. Here, d is the dimension of the search space and τ is a constant that depends on the behaviour of the objective function near its global maximum.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Freeze-Thaw Bayesian Optimization (2014, background): “Recent work has developed compelling theoretical convergence guarantees [6, 7, 8], more rigorous methodologies [9, 10] and methods tailored to speciﬁc applications such as hyperparameter optimization [11, 4, 3] and sensor set selection [12].”
Bayesian Optimization in a Billion Dimensions via Random Embeddings (2013, methodology): “We also experimented with the UCB acquisition function (Srinivas et al., 2010; de Freitas et al., 2012) and found it to yield similar results.”
On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning (2014, background): “In the realm of optimizing deterministic functions, a few works have proven exponential rates of convergence for simple regret [de Freitas et al., 2012, Munos, 2011]. A stochastic variant of the work of Munos has been recently proposed by Valko et al. [2013]; this approach takes a tree-based”
Bayesian Optimization with Unknown Constraints (2014, background): “Strong theoretical results have also been developed (Srinivas et al., 2010; Bull, 2011; de Freitas et al., 2012).”
Relative confidence sampling for efficient on-line ranker evaluation (2014, methodology): “…remedy for dealing with this diﬃculty is to use correlation information between rankers and make use of continuous armed bandits algorithms [3, 10, 25, 30, 33], although both the algorithm and the theoretical analysis would be considerably more intricate in this setting, since the goal is not…”
High Dimensional Bayesian Optimisation and Bandits via Additive Models (2015, background): “It was first proposed and analysed in the noisy setting by Srinivas et al. (2010) and extended to the noiseless case by de Freitas et al. (2012).”
Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem (2013, unknown): “First, building off extensions of UCB to the continuous bandit setting (Srinivas et al., 2010; Bubeck et al., 2011; Munos, 2011; de Freitas et al., 2012; Valko et al., 2013), we aim to extend RUCB to the continuous dueling bandit setting, without a convexity assumption as in (Yue & Joachims, 2009;…”
An Entropy Search Portfolio for Bayesian Optimization (2014, methodology): “More recently a wide variety of more advanced techniques have been proposed which include Bayesian upper conﬁdence bounds [28, 8, 33] and information-theoretic approaches [31, 11].”
Gaussian Process Optimization with Mutual Information (2013, background): “The theoretical analysis of such optimization procedures requires some prior assumptions on the underlying function f .”
Copeland Dueling Bandits (2015, methodology): “Given that both our algorithms utilize confidence bounds to make their choices, we anticipate that continuous-armed UCB-style algorithms like those proposed in [24, 25, 26, 27, 28, 29, 30] can be combined with our ideas to produce a solution to the continuous-armed Copeland bandit problem that does ”
Derivative-Free Optimization via Classification (2016, methodology): “…only except the recent development of the optimistic optimization method (Munos 2011; 2014), Bayesian optimization methods (Bull 2011; de Freitas, Smola, and Zoghi 2012), and ∗This research was supported by the NSFC (61375061, 61272217, 61223003), Foundation for the Author of National…”
UvA-DARE (Digital Academic Repository) Bayesian Optimization in High Dimensions via Random Embeddings (2013, unknown): “Finally, when using the high-dimensional kernel, the regret bounds of [Srinivas et al., 2010; Bull, 2011; de Freitas et al., 2012] apply.”
Bayesian Multi-Scale Optimistic Optimization (2014, methodology): “de Freitas et al. (2012) proved that if we double the density of points in the lattice at each iteration, the feasible region shrinks very quickly.”