Skip to main content

Black-box Optimization in Theory and in Practice

Tara Javidi

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 first 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.

In the second part of the talk, we consider the problem in a Bayesian framework with a Gaussian Process prior. In particular, a new algorithm for this problem is proposed, and high probability bounds on its simple and cumulative regret are established. The query point selection rule in most existing methods involves an exhaustive search over an increasingly fine sequence of uniform discretizations of the input space. The proposed algorithm, in contrast, adaptively refines the domain which leads to 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 improve upon the known results.

In the last part of the talk, we build on the intuition provided by our work in the Bayesian setting to consider the problem in a non-Bayesian setting where the objective function is assumed to have a kernel representation as well as be smooth. Most notably the proposed algorithm –augmenting the Gaussian Process based surrogate with local polynomial estimators— closes a significant gap to the (optimal) regret lower bound for a class of widely used and practically relevant Matern family of Kernels.

This is joint work with my PhD student Shekhar Shubhanshu.

Bio

Tara Javidi received her BS in electrical engineering at Sharif University of Technology, Tehran, Iran. She received her MS degrees in electrical engineering (systems) and in applied mathematics (stochastic analysis) from the University of Michigan, Ann Arbor as well as her Ph.D. in electrical engineering and computer science. From 2002 to 2004, Tara Javidi was an assistant professor at the Electrical Engineering Department, University of Washington, Seattle. In 2005, she joined the University of California, San Diego, where she is currently a professor of electrical and computer engineering and a founding co-director of the Center for Machine-Integrated Computing and Security (MICS).

Tara Javidi Headshot
Tara Javidi
UC San Diego
Virtual Zoom Lecture
28 Apr 2020, 10:30am until 11:30am