×

zbMATH — the first resource for mathematics

Generalization of a result of Fabian on the asymptotic normality of stochastic approximation. (English) Zbl 1428.62372
Summary: Stochastic approximation (SA) is a general framework for analyzing the convergence of a large collection of stochastic root-finding algorithms. The Kiefer-Wolfowitz and stochastic gradient algorithms are two well-known (and widely used) examples of SA. Because of their applicability to a wide range of problems, many results have been obtained regarding the convergence properties of SA procedures. One important reference in the literature, V. Fabian [Ann. Math. Stat. 39, 1327–1332 (1968; Zbl 0176.48402)], derives general conditions for the asymptotic normality of the SA iterates. Since then, many results regarding asymptotic normality of SA procedures have relied heavily on Fabian’s theorem. Unfortunately, some of the assumptions of Fabian’s result are not applicable to some modern implementations of SA in control and learning. In this paper we explain the nature of this incompatibility and show how Fabian’s theorem can be generalized to address the issue.
MSC:
62L20 Stochastic approximation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benveniste, A.; Métivier, M.; Priouret, P., Adaptive algorithms and stochastic approximations, (1990), Springer-Verlag: Springer-Verlag New York
[2] Bhatnagar, S.; Prasad, H. L.; Prashanth, L. A., Stochastic recursive algorithms for optimization: Simultaneous perturbation methods, (2013), Springer · Zbl 1260.90002
[3] Blum, J. R., Multidimensional stochastic approximation methods, Annals of Mathematical Statistics, 25, 737-744, (1954) · Zbl 0056.38305
[4] Cramér, H., Mathematical methods of statistics, (1946), Princeton University Press: Princeton University Press New Jersey · Zbl 0063.01014
[5] Duflo, M., Random iterative models, (1997), Springer-Verlag: Springer-Verlag Germany
[6] Fabian, V., Stochastic approximation of minima with improved asymptotic speed, Annals of Mathematical Statistics, 191-200, (1967) · Zbl 0147.18003
[7] Fabian, V., On asymptotic normality in stochastic approximation, Annals of Mathematical Statistics, 39, 1327-1332, (1968) · Zbl 0176.48402
[8] Hernandez, K. (2016). Cyclic stochastic optimization via arbitrary selection procedures for updating parameters. In Proc. Annual conference on information science and systems (CISS) (pp. 349-354).
[9] Hernandez, K., & Spall, J. C. (2014). Cyclic stochastic optimization with noisy function measurements. In Proc. American control conference (aCC) (pp. 5204-5209).
[10] Hernandez, K., & Spall, J. C. (2016). Asymptotic normality and efficiency analysis of the cyclic seesaw stochastic optimization algorithm. In Proc. American control conference (ACC) (pp. 7255-7260).
[11] Horn, R. A.; Johnson, C. R., Matrix analysis, (2010), Cambridge University Press: Cambridge University Press New York
[12] Hu, J.; Hu, P.; Chang, H. S., A stochastic approximation framework for a class of randomized optimization algorithms, IEEE Transactions on Automatic Control, 57, 1, 165-178, (2012) · Zbl 1369.90168
[13] Kar, S.; Moura, J. M.; Poor, H. V., Distributed linear parameter estimation: Asymptotically efficient adaptive strategies, SIAM Journal on Control and Optimization, 51, 3, 2200-2229, (2013) · Zbl 1272.93112
[14] Kushner, H. J.; Clark, D. S., Stochastic approximation methods for constrained and unconstrained systems, (1978), Springer-Verlag: Springer-Verlag New York · Zbl 0381.60004
[15] Kushner, H. J.; Yin, G. G., Stochastic approximation algorithms and applications, (2003), Springer-Verlag: Springer-Verlag New York · Zbl 1026.62084
[16] Nesterov, Y., Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM Journal on Optimization, 22, 2, 341-362, (2012) · Zbl 1257.90073
[17] Nevel’son, M. B.; Has’minskii, R. Z., Stochastic approximation and recursive estimation, (1973), American Mathematical Society: American Mathematical Society Providence RI · Zbl 0355.62075
[18] Renotte, C., & Wouwer, A. V. (2003). Stochastic approximation techniques applied to parameter estimation in a biological model. In Proc. Second IEEE international workshop on intelligent data acquisition and advanced computing systems: Technology and applications (pp. 261-265).
[19] Robbins, H.; Monro, S., A stochastic approximation method, Annals of Mathematical Statistics, 22, 400-407, (1951) · Zbl 0054.05901
[20] Spall, J. C., Multivariate stochastic approximation using a simultaneous perturbation gradient approximation, IEEE Transactions on Automatic Control, 37, 3, 332-341, (1992) · Zbl 0745.60110
[21] Spall, J. C., Adaptive stochastic approximation by the simultaneous perturbation method, IEEE Transactions on Automatic Control, 45, 10, 1839-1853, (2000) · Zbl 0990.93125
[22] Spall, J. C., Introduction to stochastic search and optimization: Estimation, simulation, and control, (2003), John Wiley & Sons: John Wiley & Sons New Jersey · Zbl 1088.90002
[23] Tsitsiklis, J. N., Asynchronous stochastic approximation and Q-learning, Machine Learning, 16, 3, 185-202, (1994) · Zbl 0820.68105
[24] Zhou, E.; Hu, J., Gradient-based adaptive stochastic search for non-differentiable optimization, IEEE Transactions on Automatic Control, 59, 7, 1818-1832, (2014) · Zbl 1360.90295
[25] Zorin, A.; Mayer-Proschel, M.; Noble, M.; Yakovlev, A. Y., Estimation problems associated with stochastic modeling of proliferation and differentiation of O-2A progenitor cells in vitro, Mathematical Biosciences, 167, 2, 109-121, (2000) · Zbl 0984.62091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.