Adaptive stochastic approximation by the simultaneous perturbation method

Stochastic approximation (SA! has long been applied for problems of minimiz ing loss functions or root finding with noisy input information. As with al l stochastic search algorithms, there are adjustable algorithm coefficients that must be specified, and that can have a profound effect on algorithm p erformance. It is known that choosing these coefficients according to an SA analog of the deterministic Newton-Raphson algorithm provides an optimal o r near-optimal form of the algorithm. However, directly determining the req uired Hessian matrix (or Jacobian matrix for root finding) to achieve this algorithm form has often been difficult or impossible in practice, This pap er presents a general adaptive SA algorithm that is based on a simple metho d for estimating the Hessian matrix, while concurrently estimating the prim ary parameters of interest. The approach applies in both the gradient-free optimization (Kiefer-Wolfowitz) and root-finding/stochastic gradient-based (Robbins-Monro) settings, and is based on the "simultaneous perturbation (S P)" idea introduced previously: The algorithm requires only a small number of loss function or gradient measurements per iteration-independent of the problem dimension-to adaptively estimate the Hessian and parameters of prim ary interest. Aside from introducing the adaptive SP approach, this paper p resents practical implementation guidance, asymptotic theory, and a nontriv ial numerical evaluation. Also included is a discussion and numerical analy sis comparing the adaptive SP approach with the iterate-averaging approach to accelerated SA.