SPSA algorithms with measurement reuse

ABSTRACT

Four 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 two second-order SPSA algorithms and sketch the convergence analysis. Finally, we present simulation results on an illustrative minimization problem.

REFERENCES

• 1: Abdulla, M., and S. Bhatnagar. 2006. SPSA algorithms with measurement reuse. Technical Report 2006--8, Department of CSA, Indian Institute of Science. URL: <http://archive.csa.iisc.ernet.in/TR/2006/8/>.
• 2: Shalabh Bhatnagar, Adaptive multivariate three-timescale stochastic approximation algorithms for simulation based optimization, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.1, p.74-107, January 2005 [doi>10.1145/1044322.1044326]
• 3: Shalabh Bhatnagar , Michael C. Fu , Steven I. Marcus , I-Jeng Wang, Two-timescale simultaneous perturbation stochastic approximation using deterministic perturbation sequences, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.13 n.2, p.180-209, April 2003 [doi>10.1145/858481.858486]
• 4: Konda, V. R., and J. N. Tsitsiklis. 2004. Convergence rate of linear two-time-scale stochastic approximation. Annals Of Applied Probability 14 (2): 796--819.
• 5: Spall, J. C. 1992. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control 37 (1): 332--341.
• 6: James C. Spall, A one-measurement form of simultaneous perturbation stochastic approximation, Automatica (Journal of IFAC), v.33 n.1, p.109-112, Jan. 1997 [doi>10.1016/S0005-1098(96)00149-5]
• 7: Spall, J. C. 2000. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Transactions on Automatic Control 45 (10): 1839--1853.
• 8: Spall, J. C. 2001. Selected on references theory, applications, and numerical Analysis. URL <http://www.jhuapl.edu/SPSA/Pages/References--List_Ref.htm>, accessed Aug 2006.
• 9: Spall, J. C. 2005. Personal communication. Dated 5 October.
• 10: Xiaoping Xiong , I-Jeng Wang , Michael C. Fu, Optimization via simulation: randomized-direction stochastic approximation algorithms using deterministic sequences, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
• 11: Zhu, X., and J. C. Spall. 2002. A modified second-order SPSA optimization algorithm for finite samples. International Journal of Adaptive Control and Signal Processing 16:397--409.