Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-22T05:17:40.447Z Has data issue: false hasContentIssue false
  • English
  • Français

On W.P.1 Convergence of A Parallel Stochastic Approximation Algorithm

Published online by Cambridge University Press:  27 July 2009

G. Yin  and
Y. M. Zhu
G. Yin
Affiliation:
Department of MathematicsWayne State University, Detroit, Michigan 48202
Y. M. Zhu
Affiliation:
Institute of Mathematical Sciences Chengdu Branch of Academia Sinica, Sichuan 610015,People's Republic of China
Get access Rights & Permissions [Opens in a new window]

Abstract

To find zeros or locate maximum values of a regression function with noisy measurements, a commonly used algorithm is the RM or KW procedure. In various applications, the dimensionality of the problems involved might be quite large. As a result, enormous memory space and extensive computation time may be needed. Motivated by the recent progress in stochastic approximation methods for decentralized and distributed computing, a parallel stochastic approximation algorithm is developed in this paper. The essence is to take advantage of state-space decompositions, and to exploit the opportunities provided by parallel processing and asynchronous communication. In lieu of utilizing a single processor as in the classical cases, a number of parallel processors are employed to solve the underlying problem in a cooperative way. First, the large dimensional vector is partitioned into a number of subvectors with relatively small dimension, then each of the subvectors is assigned to one of the processors. The processors compute and communicate in an asynchronous manner and at random times. Under rather weak conditions, the global convergence of the parallel algorithm is obtained via the methods of randomly varying truncations.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 1 , January 1989 , pp. 55 - 75
Copyright
Copyright © Cambridge University Press 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Tsitsiklis, J.N. (1984). Problems in decentralized decision making and computation. Ph.D. Thesis, Electrical Engineering Department, M.I.T., Cambridge.Google Scholar
Tsitsiklis, J.N., Bertsekas, D.P. & Athans, M. (1986). Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control AC-31:803–812.CrossRefGoogle Scholar
Kushner, H.J. & Yin, G. (1987). Asymptotic properties of distributed and communicating stochastic approximation algorithms. SIAM Journal on Control and Optimization 25:1266–1290.CrossRefGoogle Scholar
Kushner, H.J. & Yin, G. (1987). Stochastic approximation algorithms for parallel and distributed processing. Stochastics 22:219–250.CrossRefGoogle Scholar
Chen, H.F. & Zhu, Y.M. (1986). Stochastic approximation procedure with randomly varying truncations. Scientic Sinica (Series A) 22:914–926.Google Scholar
Yin, G. & Zhu, Y.M. On almost sure convergence of stochastic approximation algorithms with non-additive noise. To appear in Int. J. Control.Google Scholar
Kushner, H.J. & Clark, D.S. (1978). Stochastic approximation methods for constrained and unconstrained systems. Berlin: Springer-Verlag.CrossRefGoogle Scholar
Chen, H.F. (1985). Recursive estimation and control for stochastic systems. New York: John Wiley.Google Scholar