Stochastic Approximation and Recursive Algorithms with Applications, 2nd Edn by H. J. Kushner and G. G. Yin
A. C. Brooms · Journal of the Royal Statistical Society Series A (Statistics in Society) · 2006
Consider the discrete time stochastic model where Yn is an observation or a ‘noisy’ estimate of some process taken at the nth epoch, and where the ‘step size’ sequence {ɛn} might tend to 0, or, perhaps, to something very small. The behaviour of stochastic recursive algorithms of this form is the subject of comprehensive discussion in this revised, second, edition. These schemes can also be viewed as stochastic ‘approximation’ algorithms, where major interest is in determining under what sorts of conditions the sequence of random variables {θn} converges, and, if it does converge, to what limit, and in which sense; how might the scheme be tuned so that the sequence converges to some proposed limit? The book attempts to convince that these kinds of algorithm naturally arise in many application areas by exploring problems in, for example, parameter estimation for distribution functions, finding the roots of a function, efficient use of incoming data to find the optimal dose for a particular drug and the optimization of cost functions in queuing control problems. Chapters 1–3 consider and work through some motivating examples, in heuristic fashion, guiding the reader through the intuition. Chapter 4 flags and distils the major mathematical tools that are to be utilized in the remaining chapters for the more rigorous derivations of the convergence results. Chapter 5 studies those processes in which the ‘noise’ terms in the algorithm can be expressed as (uncorrelated) martingale differences, whereas Chapter 6 considers those in which the noise terms are correlated. Both chapters work within the ‘probability 1’ setting, with convergence and stability being examined via the study of an associated ordinary differential equation. These techniques are then revised and extended within the context of the weak convergence paradigm in the subsequent two chapters and are applied, in Chapter 9, to some of the earlier examples. Chapters 10 and 11 look at issues concerning the rates of convergence of the algorithms. The book closes with the more recent developments in distributed asynchronous algorithms, and applications thereof. For those who are unsure whether their research problem can be posed in terms of a stochastic approximation algorithm and whether anything useful can be obtained from doing so, then Chapters 1–3 should be able to address that issue. For those who would like to have a feel for, but are unsure whether they can understand, the fundamental mathematics underpinning the analysis of the algorithms, Chapter 4, and a browse through the subsequent chapters, should be able to address that. However, for those wishing to make a contribution to the research area, over straightforward applications of known results, and to move it into new application areas, Chapters 4–12 are likely to be essential reading. For the practitioner, who is interested in just applying main results and techniques, and who is much more of the ‘engineering’ frame of mind, Benveniste et al. (1990) would be an interesting companion read. The mathematical background chapter (Chapter 4) does appear to be a little terse, and perhaps some of the martingale concepts could be expanded on a little. Otherwise, I do not hesitate to conclude that this book is exceptionally well written. The literature citation is extensive, and pertinent to the topics at hand, throughout. This book could be well suited to those at the level of the graduate researcher and upwards.