Wednesday 22nd June 2022: 16.00 – 17.00
University of Bristol
We are delighted to welcome Professor Tara Javidi, University of California, San Diego, to the University of Bristol to deliver a Heilbronn colloquium.
Title: Black-box Optimization in Theory and in Practice
Abstract: 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.
The colloquium with take place in Lecture theatre LG.02, Fry Building at 16:00 – 17:00 followed by a wine reception in the Fry Common Room.
The talks will be held in-person only. Spaces are limited in the room, so we ask that you please register via this form if you are intending to come in person. Once capacity is reached, we will close registration and any current remaining spaces will be allocated on a first come basis.
Join the Heilbronn Event mailing list to keep up to date with our upcoming events.