Theory Seminar - From Predictions to Decisions: Limitations and Possibilities of Optimization from Samples

From Predictions to Decisions: Limitations and Possibilities of Optimization from Samples

Abstract: We will consider the following question: can we optimize decisions on models learned from data and achieve desirable outcomes? We will discuss this question in a framework we call optimization from samples: we are given samples of function values (model) and our goal is to (approximately) optimize the function (i.e. make a good decision). On the negative front we show that there are well-studied classes of functions which are both (approximately) optimizable and statistically learnable from samples, but cannot be optimized from samples within any reasonable approximation guarantee. On a positive front, we show natural conditions under which optimization from samples is achievable. 

 Joint work with Aviad Rubinstein and Yaron Singer.