ON SAMPLING CONTROLLED STOCHASTIC-APPROXIMATION

In the general area of optimization under uncertainty, there are a large number of applications which require finding the "best" values for a set of control variables or parameters and for which the only data available consist of measurements prone to random errors. Stochastic approximation provides a method of handling such noise or randomness in data; it has been widely studied in the literature and used in several applications. In this paper, we examine a new class of stochastic approximation procedures which are based on carefully controlling the number of observations or measurements taken before each computational iteration. This method, which we refer to as "sampling controlled stochastic approximation," has advantages over standard stochastic approximation such as requiring less computation and the ability to handle bias in estimation. We address the growth rate required of the number of samples and prove a general convergence theorem for this new stochastic approximation method. In addition, we present applications to optimization and also derive a sampling controlled version of the classic Robbins-Munro algorithm.