Validation Analysis of Robust Stochastic Approximation Method

Guanghui Lan(glanisye.gatech.edu)
Arkadi Nemirovski(nemirovsisye.gatech.edu)
Alexander Shapiro(ashapiroisye.gatech.edu)

Abstract: The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing robust stochastic approximation (SA) type algorithms. To this end we show that while running a Robust Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective value. We demonstrate that for a certain class of convex stochastic programs these bound are comparable in quality with similar bounds computed by the sample average approximation method, while their computational cost is considerably smaller.

Keywords: stochastic approximation, sample average approximation method, stochastic programming, Monte Carlo sampling, mirror descent algorithm, prox mapping, optimality bounds, large deviations estimates, asset allocation problem, conditional value at risk

Category 1: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 05/20/2008
Entry Accepted: 05/20/2008
Entry Last Modified: 05/20/2008

Modify/Update this entry