Variable-sample methods for stochastic optimization

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 128 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.