Spring 2014 Seminar Series

DATE: 3/13/2014
LOCATION: E51-149
TIME: 4:15pm
Reception immediately following

SPEAKER:
Nathan Kallus and Vishal Gupta

TITLE
Robust SAA

ABSTRACT
Sample average approximation (SAA) is an incredibly popular approach to optimization under uncertainty in operations research, particularly in data-driven settings. Under mild assumptions, SAA enjoys strong asymptotic performance guarantees. Unfortunately, similar guarantees do not typically hold in finite samples. In this paper, we propose a tractable modification of SAA, which we call Robust SAA, which retains SAA's asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees.

 

The key to the approach is linking SAA, distributionally robust optimization, and the theory of hypothesis testing from statistics. Beyond Robust SAA, this connection provides a unified perspective, enabling us to characterize the finite-sample and asymptotic performance of various other data-driven procedures in the literature that are based upon distributionally robust optimization.

 

We illustrate the practicality of our new approach through canonical inventory and portfolio allocation problems and show that the resulting optimization problems can be solved tractably using linear or second-order cone optimization, and sometimes in closed-form solution. Computational experiments confirm that Robust SAA typically outperforms other data-driven techniques with similar finite-sample guarantees by a wide margin.