Variable-Sample Methods for Stochastic Optimization

Research output: Contribution to journalArticlepeer-review

86 Scopus citations

Abstract

In this article we discuss the application of a certain class of Monte Carlo methods to stochastic optimization problems. Particularly, we study variable-sample techniques, in which the objective function is replaced, at each iteration, by a sample average approximation. We first provide general results on the schedule of sample sizes, under which variable-sample methods yield consistent estimators as well as bounds on the estimation error. Because the convergence analysis is performed pathwisely, we are able to obtain our results in a flexible setting, which requires mild assumptions on the distributions and which includes the possibility of using different sampling distributions along the algorithm. We illustrate these ideas by studying a modification of the well-known pure random search method, adapting it to the variable-sample scheme, and show conditions for convergence of the algorithm. Implementation issues are discussed and numerical results are presented to illustrate the ideas.

Original languageEnglish
Pages (from-to)108-133
Number of pages26
JournalACM Transactions on Modeling and Computer Simulation
Volume13
Issue number2
DOIs
StatePublished - Apr 2003
Externally publishedYes

Keywords

  • Monte Carlo methods
  • Pathwise bounds
  • Random search
  • Stochastic optimization

Fingerprint

Dive into the research topics of 'Variable-Sample Methods for Stochastic Optimization'. Together they form a unique fingerprint.

Cite this