CS Theory Seminar: Computing Small Volume Confidence Set for Arbitrary Distributions (Liren Shan, TTIC)

We study the problem of learning a high-density region of an arbitrary distribution. Given a target coverage level, and sample access to an arbitrary distribution D, we want to output a confidence set S such that S achieves the desired coverage and the volume of S is as small as possible. We show that this problem is statistically intractable in the most general setting. Then, we restrict our attention to competing with sets from a set family C with bounded VC dimension and provide approximation algorithms to compute a small volume set with desired coverage. Finally, we demonstrate the application of our results to conformal prediction.