22 June 2022 at 16.00

Organised in collaboration with the School of Mathematics, University of Bristol, UK

Black-box Optimization in Theory and in Practice

Tara Javidi, University of California, San Diego, USA

In this talk, we will consider the problem of maximizing a black-box function via noisy and costly queries from a theoretical perspective (a lot of it) as well as applications (an exciting bit). We motivate the problem by considering a wide variety of engineering design applications from the heuristic optimization of wireless networks to hardware acceleration to neural network architecture search.

We consider the problem in two settings where the blackbox function belongs to (1) the sample paths of a Gaussian Process or (2) a reproducing kernel Hilbert space (RKHS) with bounded norm. These settings, despite their seeming differences, rely on a Gaussian Process Bandit (GP-Bandit) interpretation of the problem. As a result, in much of prior work  query point selection rule involves a bandit search over a sufficiently fine sequence of uniform discretization of the input space. In contrast, and inspired by a geometric (hypothesis testing) interpretation of optimization of continuous functions, we propose and analyze a new family of algorithms which adaptively discretize and zoom in the optimality region, resulting in  a lower computational complexity, particularly when the domain is a subset of a high dimensional Euclidean space. In addition to the computational gains, sufficient conditions are identified under which the regret bounds of the new algorithm either improve upon the known results or asymptotically match the lower bound. 

We end the talk by considering two important natural questions to which we provide partial answers.  In particular, we quantify a lower bound on the gains obtained from a first-order oracle who in addition to zero-order oracle has access to (noisy) gradient information. Last not least, we discuss the extension of the framework to account for an instance-dependent regret analysis. 

This is joint work with my former PhD student Shekhar Shubhanshu.  

---

For more information please email the Heilbronn events team at  heilbronn-coordinator@bristol.ac.uk

Information on past and future colloquia is available here

Join the Heilbronn Event mailing list to keep up to date with our upcoming event