Abstract: Learning-based predictive algorithms have tremendous potential to reduce costs and improve outcomes in a breadth of domains including business, healthcare, and government. Rigorous guarantees about the performance of such powerful algorithms are necessary in order to ensure their responsible use. I will describe current results in this area, focusing on the most recent work, which bounds the expected loss of a predictor. In many risk-sensitive applications this is not sufficient, as the distribution of errors is important. In such cases, the quantiles of the loss distribution incurred by a predictor are an alternative and informative way of quantifying its performance. I will present a new framework we have developed for deriving a variety of efficient upper bounds on loss quantiles, which
encompasses previous methods and offers novel formulations. The quantiles can be used as the basis for model validation to select the best predictor from a set, and issue rigorous guarantees on its generalization performance. I will present theoretical properties of our proposed method and demonstrate its ability to control loss quantiles on several real-world datasets.
https://www.cs.columbia.edu/~zemel/