Georgia Institute of Technology College of Sciences

The Prophet Inequality and Pandora's Box problems are fundamental stochastic problems. A usual assumption for both problems is that the probability distributions of the n underlying random variables are given as input to the algorithm. In this talk, we assume the distributions are unknown, and study them in the Multi-Armed Bandits model: We interact with the unknown distributions over T rounds. In each round we play a policy and receive only bandit feedback. The goal is to minimize the regret, which is the difference in the total value of the optimal algorithm that knows the distributions vs. the total value of our algorithm that learns the distributions from the bandit feedback. Our main results give near-optimal  O(poly(n)sqrt{T}) total regret algorithms for both Prophet Inequality and Pandora's Box.

In this talk, we will look into the two most widely studied settings of the stochastic multi-armed bandit problems - regret minimization and pure exploration. The algorithm is presented with a finite set of unknown distributions from which it can generate samples. In the regret-minimization setting, its aim is to sample sequentially so as to maximize the total average reward accumulated. In the pure exploration setting, we are interested in algorithms that identify the arm with the maximum mean in a small number of samples on an average while keeping the probability of false selection to at most a pre-specified and small value. Both of these problems are well studied in literature and tight lower bounds and optimal algorithms exist when the arm distributions are known to belong to simple classes of distributions such as single-parameter exponential family, distributions that have bounded support, etc. However, in practice, the distributions may not satisfy these assumptions and may even be heavy-tailed. In this talk, we will look at techniques and algorithms for optimally solving these two problems with minimal assumptions on the arm distributions. These ideas can be extended to a more general objective of identifying the distribution with the minimum linear combination of risk and reward, which captures the risk-reward trade-off that is popular in many practical settings, including in finance.

Given an n-by-d matrix A and a vector of size n, the p-norm problem asks for a vector x that minimizes the following

\sum_{i=1}^n (a_i^T x - b_i)^p,

where a_i is the i’th row of A. The study of p=2 and p=1 cases dates back to Legendre, Gauss, and Laplace. Other cases of p have also been used in statistics and machine learning as robust estimators for decades. In this talk, we present the following improvements in the running time of solving p-norm regression problems.

For the case of 1

For 1

The talk is based on a joint work with Richard Peng and Santosh Vempala.

The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regression to recent trends such as adversarially robust and private learning, it’s surprising we still lack a unifying theory explaining these results. 

In this talk, we'll introduce exactly such a framework: a simple, model-independent blackbox reduction between agnostic and realizable learnability that explains their equivalence across a wide host of classical models. We’ll discuss how this reduction extends our understanding to traditionally difficult settings such as learning with arbitrary distributional assumptions and general loss, and look at some applications beyond agnostic learning as well (e.g. to privacy). Finally, we'll end by surveying a few nice open problems in the area.

Based on joint work with Daniel Kane, Shachar Lovett, and Gaurav Mahajan.