Abstract
We study asymptotic behavior of stochastic approximation procedures with three main characteristics: truncations with random moving bounds, a matrix-valued random step-size sequence, and a dynamically changing random regression function. In particular, we show that under quitemild conditions, stochastic approximation procedures are asymptotically linear in the statistical sense, that is, they can be represented as weighted sums of random variables. Therefore, a suitable formof the central limit theoremcan be applied to derive asymptotic distribution of the corresponding processes. The theory is illustrated by various examples and special cases.
Similar content being viewed by others
References
S. Andradóttir, “A Stochastic Approximation Algorithm with Varying Bounds”, Operations Res. 43 (6), 1037–1048 (1995).
A. Benveniste, M. Métivier, and P. Priouret, Stochastic Approximations and Adaptive Algorithms (Springer, 1990).
V. S. Borkar, Stochastic Approximation (Cambridge Books, 2008).
H. F. Chen, L. Guo, and A. J. Gao, “Convergence and Robustness of the Robbins–Monro Algorithm Truncated at Randomly Varying Bounds”, Stoch. Proc. and Their Appl. 27, 217–231 (1987).
H. F. Chen and Y. M. Zhu, “Stochastic Approximation Procedures with Randomly Varying Truncations”, Scientia Sinica, Series A, Math. Phys. Astron. & Techn. Sci. 29 (9), 914–926 (1986).
H. Cramér, Mathematical Methods of Statistics (Princeton Univ. Press, Princeton, 1946).
V. Fabian, “On Asymptotically Efficient Recursive Estimation”, Ann. Statist., 854–866 (1978).
O. Kallenberg, Foundations of Modern Probability (Springer, 2002).
R. Z. Khas’minskii and M. B. Nevelson, Stochastic Approximation and Recursive Estimation (Nauka, Moscow, 1972).
H. J. Kushner, “Stochastic Approximation: a Survey”, Wiley Interdisciplinary Reviews: Computational Statistics 2 (1), 87–96 (2010).
H. J. Kushner and G. Yin, Stochastic Approximation and Recursive Algorithms and Applications, in Springer Science & Business Media (2003), Vol.35.
T. L. Lai, “Stochastic Approximation”, Ann. Statist., 391–406 (2003).
J. Lelong, “Almost Sure Convergence of Randomly Truncated Stochastic Algorithms under Verifiable Conditions”, Statist. & Probab. Lett. 78 (16), 2632–2636 (2008).
R. Liptser and A. N. Shiryayev, “Theory of Martingales”, in Math. and its Appl. (Kluwer, Dordrecht, 1989), pp. 835–873.
M. Loève, Probability Theory (Springer, New York, 1977).
H. Robbins and S. Monro, “A Stochastic ApproximationMethod”, Ann.Math. Statist., 400–407 (1951).
T. Sharia, “Truncated recursive estimation procedures”, in Proc. A. Razmadze Math. Inst. 115, 149–159 (1997).
T. Sharia, “Recursive Parameter Estimation: Convergence”, Statist. Infer. for Stoch. Proc. 11 (2), 157–175 (2008).
T. Sharia, “Recursive Parameter Estimation: Asymptotic Expansion”, Ann. Inst. Statist.Math. 62 (2), 343–362 (2010).
T. Sharia, “Truncated Stochastic Approximation with Moving Bounds: Convergence”, Statist. Infer. for Stoch. Proc., 17 (2), 163–179 (2014).
T. Sharia and L. Zhong, “Rate of Convergence of Truncated Stochastic Approximation Procedures”, Math. Meth. of Statist. 25 (4), 262–180 (2016).
A. N. Shiryayev, Probability (Springer, 1984).
V. Tadić, “Stochastic Gradient Algorithm with Random Truncations”, European J. of Operat. Res. 101 (2), 261–284 (1997).
V. Tadić, “Stochastic Approximation with Random Truncations, State-Dependent Noise and Discontinuous Dynamics”, Stochastics: Internat. J. of Probab. and Stoch. Proc. 64 (3–4), 283–326 (1998).
E. T. Whittaker and G. N. Watson, A Course of Modern Analysis (Cambridge Univ. Press, Cambridge, 1927).
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Sharia, T., Zhong, L. Asymptotic behavior of truncated stochastic approximation procedures. Math. Meth. Stat. 26, 37–54 (2017). https://doi.org/10.3103/S1066530717010033
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S1066530717010033