Abstract
This paper is concerned with a continuous time stochastic approximation/optimization problem. The algorithm is given by a pair of differential-integral equations. Our main effort is to derive the asymptotic properties of the algorithm. It is shown that ast → ∞, a suitably normalized sequence of the estimation error,Τ√t(¯x tr−θ) is equivalent to a scaled sequence of the random noise process, namely, (1/√t)∫ tr0 ξsds. Consequently, the asymptotic normality is obtained via a functional invariance theorem, and the asymptotic covariance matrix is shown to be the optimal one. As a result, the algorithm is asymptotically efficient.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Robbins, H. and Monro, S.: A stochastic approximation method,Ann. Math. Statist. 22 (1951), 400–407.
Nevelson, M. B. and Khasminskii, R. Z.:Stochastic Approximation and Recursive Estimation, Translation of Math. Monographs 47, Amer. Math. Soc., Providence, 1976.
Benveniste, A., Metivier, M. and Priouret, P.:Adaptive Algorithms and Stochastic Approximation, Springer-Verlag, Berlin, 1990.
Chung, K. L.: On a stochastic approximation method,Ann. Math. Statist. 25 (1954), 463–483.
Venter, J. H.: An extension of the Robbins-Monro procedure,Ann. Math. Statist. 38 (1967), 181–190.
Lai, T. L. and Robbins, H.: Consistency and asymptotic efficiency of slope estimates in stochastic approximation schemes,Z. Wahrsch. verw. Gebiete 56 (1981), 329–360.
Wei, C. Z.: Multivariate adaptive stochastic approximation,Ann. Statist. 15 (1987), 1115–1130.
Polyak, B. T.: New method of stochastic approximation type,Automat. Remote Control 51 (1990), 937–946.
Ruppert, D.: Efficient estimations from a slowly convergent Robbins-Monro process, Technical Report No. 781, School of Oper. Res. & Industrial Eng., Cornell Univ., 1988.
Yin, G.: On extensions of Polyak's averaging approach to stochastic approximation,Stochastics 36 (1991), 245–264.
Polyak, B. and Juditsky, A.: Acceleration of stochastic approximation by averaging,SIAM J. Control Optim. 30 (1992), 838–855.
Kushner, H. J. and Yang, J.: Stochastic approximation with averaging of the iterates: optimal asymptotic rate of convergence for general processes, Technical Report LCDS No. 91-9, Brown Univ. (1991), also to appear inSIAM J. Control Optim.
Bather, J. A.: Stochastic approximation: A generalization of the Robbins-Monro procedure, in P. Mandl and M. Hušková (eds),Proc. Fourth Prague Symp. Asymptotic Statist., 1989, pp. 13–27.
Schwabe, R.: Stability results for smoothed stochastic approximation procedures,Fachbereich Mathematik, Series A, Mathematik, Preprint No. A-92-14, Freie UniversitÄt Berlin, 1992.
Moore, J. B.: Convergence of continuous time stochastic ELS parameter estimation,Stochastic Process. Appl. 27 (1988), 195–215.
Kushner, H. J. and Clark, D. S.:Stochastic Approximation Methods for Constrained and Unconstrained Systems, Springer-Verlag, New York, 1978.
Ethier, S. N. and Kurtz, T. G.:Markov Processes, Characterization and Convergence, Wiley, New York, 1986.
Kushner, H. J.:Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory, MIT Press, Cambridge, Mass., 1984.
Papanicolaou, G. C., Stroock, D. and Varadhan, S. R. S.: Martingale approach to some limit theorems, in M. Reed (ed.),Proc. Conf. Statistical Mechanics, Dynamical Systems and Turbulence, Duke Univ. Math. Series 3, 1977.
Baleckii, J. L., and Krien, M. G.:Stability of Solutions of Differential Equations in Banach Spaces, Amer. Math. Soc., Providence, 1974.
Billingsley, P.:Convergence of Probability Measures, Wiley, New York, 1968.
Chen, H. F.: Continuous-time stochastic approximation: convergence and asymptotic efficiency, Preprint, 1992.
Antamoshkin, A., Schwefel, H. P., Törn, A., Yin, G. and Žilinskas, A.:Introduction to Systems Analysis: Design and Optimization (to appear).
Author information
Authors and Affiliations
Additional information
Supported in part by the National Science Foundation, and in part by Wayne State University.
Supported in part by Wayne State University through a research assistantship.
Rights and permissions
About this article
Cite this article
Yin, G., Gupta, I. On a continuous time stochastic approximation problem. Acta Appl Math 33, 3–20 (1993). https://doi.org/10.1007/BF00995492
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00995492