Two basic problems in finite stochastic optimization

Speaker  Sebastien Bubeck

Host  Yuval Peres

Affiliation  Princeton University

Duration  01:02:44

Date recorded  20 November 2013

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.

©2013 Microsoft Corporation. All rights reserved.
> Two basic problems in finite stochastic optimization