ABSTRACT RANDOMIZED-DIRECTION STOCHASTIC APPROXIMATION ALGORITHMS USING DETERMINISTIC SEQUE.pdf

Proceedings of the 2002 Winter Simulation Conference
E. Yücesan, C.-H. Chen, J. L. Snowdon, and J. M. Charnes, eds.
RANDOMIZED-DIRECTION STOCHASTIC APPROXIMATION ALGORITHMS
USING DETERMINISTIC SEQUENCES
Xiaoping Xiong I-Jeng Wang
The Robert H. Smith School of Business Johns Hopkins University
University of Maryland Applied Physics Laboratory
College Park, MD 20742, . Laurel, MD 20723, .
Michael C. Fu
The Robert H. Smith School of Business
University of Maryland
College Park, MD 20742, .
ABSTRACT presented in Spall (1992). Typically SPSA or RDKW algo-
rithms randomly perturbs all ponents in two
We study the convergence and asymptotic normality of a parallel simulations at each iteration for any p− dimensional
generalized form of stochastic approximation algorithm with problem. An SPSA requiring only one simulation at each
deterministic perturbation sequences. Both one-simulation iteration has also been proposed in Spall (1997). These
and two-simulation methods are considered. Assuming a algorithms all rely on proper randomization to avoid the
special structure of deterministic sequence, we establish large number simulations required in each iteration, and at
sufficient condition on the noise sequence for . con- the same time move along the gradient descent direction on
vergence of the algorithm. Construction of such a special the a