Two basic problems in finite stochastic optimization


November 20, 2013


Sebastien Bubeck


Princeton University


I will present a new theoretical perspective on two basic problems arising in stochastic optimization. The first one is arguably the most elementary problem in stochastic optimization: assume that one wants to find the maximum of function defined on a finite set, and that one is given a budget of n noisy evaluations. What is the best sequential allocation procedure for the evaluations? The second problem that I will discuss is inspired from the issue of security analysis of a power system. We formalize this problem as follows: Let X be a set, and A a subset of X of “interesting” elements in X. One can access X only through requests to a finite set of probabilistic experts. More precisely, when one makes a request to the ith expert, the latter draws independently at random a point from a fixed probability distribution Pi over X. One is interested in discovering rapidly as many elements of A as possible, by making sequential requests to the experts.


Sebastien Bubeck

Sebastien Bubeck is an Assistant Professor at Princeton University, Department of Operations Research and Financial Engineering, specializing in stochastic optimization and statistical learning theory. He received his PhD in 2010 and was a postdoctoral scholar in Barcelona.