SPSA Algorithms with Measurement Reuse
Mohammed Shahid Abdulla and Shalabh Bhatnagar
IISc-CSA-TR-2006-8
(August 2006) Available formats: [ps] [ps.gz]
Filed on August 14, 2006
Updated on August 14, 2006
Five algorithms, all variants of Simultaneous Perturbation Stochastic
Approximation (SPSA), are proposed.
The original one-measurement SPSA uses an estimate of the gradient of
objective function L containing an additional bias term not seen in
two-measurement SPSA.
As a result, the asymptotic covariance matrix of the iterate convergence
process has a bias term.
We propose a one-measurement algorithm that eliminates this bias, and has
asymptotic convergence properties making for easier comparison with the
two-measurement SPSA.
The algorithm, under certain conditions, outperforms both forms of SPSA
with the only overhead being the storage of a single measurement.
We also propose a similar algorithm that uses perturbations obtained from
normalized Hadamard matrices.
The convergence w.p. 1 of both algorithms is established.
We extend measurement reuse to design three second-order SPSA algorithms
and sketch the convergence analysis.
Finally, we present simulation results on an illustrative minimization
problem.
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2006/8/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]