Learning Confidence Sets

I will discuss the problem of finding confidence sets for arbitrary distributions.  This is a fundamental statistical task with connections to many problems, like support estimation, robust estimation, and conformal prediction.  Given samples from a distribution D, the goal is to find a small set that contains at least a target 1 - α probability mass of D. We study this in a setup similar to PAC learning, where, for a fixed family of sets F, our goal is to find a set that achieves coverage on D, and has volume comparable to the smallest set in F that achieves coverage on D.  

 

In the first part of the talk, I will discuss some work in the high-dimensional setting, where D is supported on \mathbb{R}^d. We give an efficient algorithm that learns a confidence ellipsoid that has volume approximately that of the smallest-volume confidence ellipsoid of bounded condition number.

 

In the second part of the talk, I will discuss an online formulation of the confidence set problem. We show that the problem of learning confidence sets looks quite different from the standard online learning problem. This talk is based on joint work with Chao Gao, Liren Shan, and Aravindan Vijayaraghavan.