Optimization Online


Validation Analysis of Robust Stochastic Approximation Method

Guanghui Lan (glan***at***isye.gatech.edu)
Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)
Alexander Shapiro (ashapiro***at***isye.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society