Abstract
Parallel recursive algorithms of stochastic approximation type are discussed. The basic idea is to utilize a collection of parallel processors in lieu of using a single one alone as in the classical algorithms. The processors compute and communicate with each other asynchronously. By asynchronous implementations, we mean that each processor updates on its own pace, and uses the most recently received information from other processors. Several procedures are dealt with. These include distributed communicating schemes via convexifications, parallel algorithms with interacting processors and renewal type of computation times, and real time implementable procedures with pipeline arrangements. It appears that from the closed connection between real world applications and mathematical theories, the study of parallel stochastic approximation methods gains not only much of its special appeal, but also much of its intrinsic tension. The main emphasis and interest are the asymptotic properties of the algorithms. The parallel interacting algorithm and its variation are used as representatives for illustrating various limiting results. Convergence and rate of convergence issues are addressed, and robustness analysis is carried out.
This research has been supported in part by the National Science Foundation under grant DMS-8814624, and in part by the Institute for Mathematics and its Applications with fund provided by the National Science Foundation.
Preview
Unable to display preview. Download preview PDF.
References
A.E. Albert and L.A. Gardner, Stochastic Approximation and Nonlinear Regression, MIT Press, Cambridge, MA, 1967.
A. Benveniste, M. Metivier and P. Priouret, Algorithmes Adaptatifs et Approximations Stochastiques, Masson, Paris, 1987.
D.P. Bertsekas, Distributed computation of fixed points, Mathematical Programing 27 (1983), 107–120.
D.P. Bertsekas and J.N. Tsitsiklis, Parallel and Distributed Computing, Prentice-Hall, New Jersey, 1989.
D.P. Bertsekas and J.N. Tsitsiklis, Parallel and distributed iterative algorithms: A selective survey, Technical Report, Laboratory for Information and Decision Systems, LIDS-P-1835, MIT, 1988.
P. Billingsley, Convergence of Probability Measures, J. Wiley & Sons, New York, 1968.
G.B. Blankenship and G.C. Papanicolaou, Stability and control of stochastic systems with wide band noise, SIAM J. Appl. Math. 34 (1978), 437–476.
P. E. Caines, Linear Stochastic Systems, J. Wiley, New York, 1988.
D. Chazan and W. Miranker, Chaotic relaxation, Linear Algebra and Appl. 2 (1969), 199–222.
H.F. Chen, Recursive Estimation and Control for Stochastic Systems, J. Wiley, New York, 1985.
H.F. Chen, L. Guo and A.J. Gao, Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds, Stochastic Process. Appl. 27 (1988), 217–231.
H.F. Chen and Y.M. Zhu, Stochastic approximation procedures with randomly varying truncations, Scientia Sinica (series A) XXIX (1986), 914–926.
P. Dupuis and H.J. Kushner, Stochastic approximation and large deviations: upper bounds and w.p.1 convergence, SIAM J. Control Optim. 27 (1989), 1108–1135.
Yu. Ermoliev, Stochastic quasigradient Methods and their applications to system optimization, Stochastics 9 (1983), 1–36.
S. Ethier and T.G. Kurtz, Markov Processes: Characterization and Convergence, J. Wiley & Sons, New York, 1986.
V. Fabian, On asymptotic normality in stochastic approximation, Ann. Math. Statist. 39 (1968), 1327–1332.
L. Gerencsér, Rigorous results in the theory of recursive identification, in this volume.
L. Gerencsér, On a class of mixing processes, Stochastics 26 (1989), 165–191.
G. Goodwin, P. Ramadge and P. Caines, Discrete time stochastic adaptive control, SIAM J. Control Optim. 19 (1981), 829–853.
A.J. Gao, Y.M. Zhu and G. Yin, Joint robustness on noise and Liapunov function for parallel stochastic approximation algorithms, Preprint, 1989.
J. Kiefer and J. Wolfowitz, Stochastic estimation of the maximum of a regression function, Ann. Math. Statist. 23 (1952), 462–466.
P.R. Kumar and P.P. Varaiya, Stochastic Systems: Estimation, Identification and Adaptive Control, Prentice-Hall, Englewood Cliffts, NJ, 1986.
H.J. Kushner, Stochastic approximation with discontinuous dynamics and state dependent noise: w.p.l and weak convergence, J. Math. Anal. Appl. 82 (1981), 527–542.
H.J. Kushner, Approximation and Weak Convergence Methods for Random Processes with Applications to Stochastic Systems Theory, MIT Press, Cambridge, MA, 1984.
H.J. Kushner and D.S. Clark, Stochastic Approximation for Constrained and Unconstrained Systems, Springer-Verlag, Berlin, 1978.
H.J. Kushner and H. Huang, Asymptotic properties of stochastic approximations with constant coefficients, SIAM J. Control Optim. 19 (1981), 86–105.
H.J. Kushner and A. Shwartz, An invariant measure approach to the convergence of stochastic approximations with state-dependent noise, SIAM J. Control Optim. 22 (1984), 13–27.
H.J. Kushner and G. Yin, Asymptotic properties of distributed and communicating stochastic approximation algorithms, SIAM J. Control Optim. 25 (1987), 1266–1290.
H.J. Kushner and G. Yin, Stochastic approximation algorithms for parallel and distributed processing, Stochastics 22 (1987), 219–250.
T.L. Lai and H. Robbins, Consistency and asymptotic efficiency of slope estimates in stochastic approximation schemes, Z. Wahr. 56 (1981), 329–360.
S. Li and T. Basar, Asymptotic agreement and convergence of stochastic algorithm, IEEE Tran. Automat. Control AC-32 (1987), 612–618.
L. Ljung, Analysis of recursive stochastic algorithms, IEEE Trans. Automat. Control AC-22 (1977), 551–575.
L. Ljung and T. Söderström, Recursive identification, MIT Press, Cambridge, MA, 1983.
M. Metivier and P. Priouret, Applications of a Kushner and Clark Lemma to general classes of stochastic algorithms, IEEE Trans. Inform. Theory IT-30 (1984), 140–151.
W.L. Miranker, A survey of parallelism in numerical analysis, SIAM Review 13 (1971), 524–547.
M.B. Nevel'son and R.Z. Khas'minskii, Stochastic Approximation and Recursive Estimation, Translation of Math. Monographs, v47, AMS, Providence, 1973.
G. Ch. Pflug, Stochastic minimization with constant step-size: asymptotic laws, SIAM J. Control Optim. 24 (1986), 655–666.
B.T. Polyak, Convergence and convergence rate of iterative stochastic algorithms, I, II, Automatic Remote Control 38 (1978), 537–542.
B.T. Polyak, New stochastic approximation type procedures, to appear in Automatic Remote Control.
Yu. V. Prohorov, Convergence of random processes and limit theorems in probability theory, Theory Probab. Appl. 1 (1956), 157–214.
G.C. Papanicolaou, D. Stroock and S.R.S. Varadhan, Martingale approach to some limit theorems, Proc. of the 1976 Duke Univ. Conference on Turbulence, M. Reed ed., Duke University Mathematics Series, vol. 3, Durham, NC, 1977.
M.J. Quinn, Designing Efficient Algorithms for Parallel Computers, McGraw-Hill, New York, 1987.
H. Robbins and S. Monro, A stochastic approximation method, Ann. Math. Statist. 22 (1951), 400–407.
R.Y. Rubinstein, Monte Carlo Optimization and Sensitivity of Queueing Networks, J. Wiley & Sons, New York, 1986.
D. Ruppert, A Newton-Raphson version of the multivariate Robbins-Monro Procedure, Ann. of Statist. 13 (1985), 236–245.
J. Sacks, Asymptotic distribution of stochastic approximation procedures, Ann. Math. Statist. 29 (1958), 159–167.
A.V. Skorohod, Limit theorems for stochastic processes, Theory Probab. Appl. 1 (1956), 261–290.
J. Tsitsiklis, Problem in decentralized decision making and computation, Ph.D thesis, Elect. Eng. Dept., MIT, Cambridge, MA, 1984.
J.N. Tsitsiklis, D.P. Bertsekas and M. Athans, Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Automat. Control AC-31 (1986), 803–812.
Ya. Z. Tsypkin, Adaptation and Learning in Automatic Systems, Academic Press, New York, 1971.
J.H. Venter, An extension of the Robbins-Monro procedure, Ann. Math. Statist. 38 (1967), 181–190.
M.T. Wasan, Stochastic Approximation, Cambridge Press, London, 1969.
R.B. Washburn and D. Teneketzis, Asymptotic agreement among communicating decision makers, Stochastics 13 (1984), 103–129.
C.Z. Wei, Multivariate adaptive stochastic approximation, Ann. Statist. 15 (1987), 1115–1130.
G. Yin, A stop** rule for the Robbins-Monro method, J. Optim. Theory. Appl. 67 (1990), 151–173.
G. Yin and Y.M. Zhu, On parallel processing approach to adaptive stochastic approximation, Proc. 27th Conference on Decision and Control.
G. Yin and Y.M. Zhu, On w.p.l convergence of a parallel stochastic approximation algorithm, Probab. Eng. Inform. Sci. 3 (1989), 55–75.
G. Yin and Y.M. Zhu, On robustness of the Robbins-Monro method for parallel processing, System Control Lett. 12 (1989), 77–86.
G. Yin and Y.M. Zhu, On H-valued Robbins-Monro processes, Journal of Multivariate Analysis, Vol. 34 (1990), 116–140.
Y.M. Zhu and G. Yin, Stochastic approximation in real time: pipelining computation and communication, Preprint, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag
About this chapter
Cite this chapter
Yin, G. (1991). Recent progress in parallel stochastic approximations. In: Gerencséer, L., Caines, P.E. (eds) Topics in Stochastic Systems: Modelling, Estimation and Adaptive Control. Lecture Notes in Control and Information Sciences, vol 161. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0009304
Download citation
DOI: https://doi.org/10.1007/BFb0009304
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54133-2
Online ISBN: 978-3-540-47435-7
eBook Packages: Springer Book Archive