Adaptive algorithms and stochastic approximations. Translated from the French by Stephen S. Wilson. (English) Zbl 0752.93073

Applications of Mathematics. 22. Berlin etc.: Springer-Verlag. xi, 365 p. (1990).
[For a review of the French original (1987) see Zbl 0639.93002.]
This is a book in the theory and the application of adaptive algorithms and stochastic approximation, which consists of two parts. The first part provides the user of adaptive algorithms with a clear and comprehensive guide illustrated with diverse examples covering signal processing and pattern recognition; the second part deals with the mathematical background of stochastic approximation as one requires in the analysis and design of adaptive systems. Before we pass to describe in detail the topics treated in this highly interesting work, we recall some general notions of the theory of systems.
System theory investigates a variety of phenomena regardless their specific nature; it focuses on relationships linking the objects that constitute a system and on questions concerning change as it emanates from interactions among the objects themselves and from the interplay of the system with its environment. A central feature of systems theory is its emphasis on links relating fundamentally the parts to the totality and hence its concern with goal-conductive behaviour of the system and decision making.
The system-theoretical picture of the world, we would like to point out, rests on matter, energy and information, three components capable of explaining the existence of patterns underlying its structure, organization and order, which in turn are essential understanding systems. As the application of mathematical methods to the end of studying systems assumes that presence of a precise although concise account of them — for instance in the form of a model — one is led to the conclusion that systems description — model building — and the design of decision mechanisms are in a way system-theoretical versions of human observations of reality and communicative actions on which knowledge, cognition and learning rely. The human brain — a remarkable active model builder — continuously captures, stores, creates, updates, rejects, destroys and recreates pictures of reality. Approaching reality on the basis of model building is thus the natural outgrowth of recognising this relatively transitory character of knowledge.
The procedure leading to the construction of a model with the help of observations of system behaviour, measuring certain of its features and processing the obtained information is usually known as identification. In this sense identification builds links between the real world and that of mathematical models. Techniques of identification start in general choosing a family of suitable models and seek to specify a particular member with the aid of measured data by means of parameter estimation. As a way of example we may think of problems related to steering dynamics of a large ship affected by random components of wind and wave motion; short-term prediction of power load and demand for electric power, so that operations in a network of plants can be effectively coordinated; digital transmission of speech over a communication channel; or determining adequately the critical doses expected to induce a measurably biological joint-response when \(k\) drugs are administered to an organism.
The complexity and dynamism of real-world systems account for the relevance of recursive and adaptive features to methods used in the investigation of systems; here the term recursive suggests an estimation procedure in which current estimates are expressible in terms of estimates obtained in the preceding step of the procedure and current observations as well, while the term adaptive refers to the presence of a parameter that reflects the need of updating the model at issue as additional information becomes available.
The work under review concentrates on various aspects of adaptive algorithms and assumes the problem of model building as already settled. The role of the algorithm is to adjust the aforementioned parameter so as to reflect how the system adapts to the current state of information, a task usually casted in the language of random difference equations. A simple version of this algorithm takes the form \(\theta_ n=\theta_{n- 1}+\gamma_ n H(\theta_{n-1},X_ n)\). Here \(\theta=(\theta_ n)_{n\geq 1}\) stands for the sequence of vectors representing the parameter to be updated: \(X=(X_ n)_{n\geq 1}\) the state vector where \(X_ n\) represents the on-line observation of the system at the time \(n\); \(H(\theta,X)\) describes a function reflecting updating operations; and \(\gamma=(\gamma_ n)_{n\geq 1}\) is a sequence of small gains.
In the first chapter of the book the authors examine with the aid of examples basic properties the state vector \(X\), the function \(H\) and the gain \(\gamma\) may attain as well as the nature of associate problems. Chapters 2 and 3 in Part I discuss heuristically questions on the convergence and rate of convergence of such algorithms related to a stochastic version of the averaging principle. Chapters 4 and 5 are dedicated to the analysis of nonstationary systems, first when changes are slow in time and then when they are abrupt; the problems of measuring the tracking ability of an algorithm and change detection are also considered setting aside to a major extent technical difficulties. Each chapter in Part I is complemented by a number of exercises which are either direct applications or extensions of the material exposed.
In Part II fundamental mathematical questions on the analysis of adaptive algorithms are at the centre of attention. To this end basic notions of conditioning, Markov chains and martingales are used. In a sufficiently general framework Chapters 1, 2 and 3 are dedicated respectively to the study of certain convergence issues, to discuss in detail the applications and generalization of the results obtained. Chapter 4 states formally and proves the property of asymptotic normality in the behaviour of adaptive algorithms using diffusion approximations, distribution of stochastic processes and weak convergence in a Gaussian guide.
Chapter 6 in Part I consists of three appendices aimed at acquainting mathematicians with the rudiments of systems theory, second-order stationary processes and Kalman filtering as used in engineering applications. In Part II Chapter 5, which is also an appendix, presents various notions and results of stochastic approximation. Comments on the literature for each chapter and a subject index for each part are also included.
Adaptive Algorithms and Stochastic Approximation is a highly welcome addition to the literature on the theory and application of stochastic analysis. It presents a wealth of interesting examples from various fields of modern engineering accompanied with a stimulating discussion of the mathematical foundations underlying them. The truly interdisciplinary character of this book deserves particular attention, since it grew out of the attempt to forward a guide for engineer’s everyday usage and the willingnes to show that the most elegants tools of probability can be effectively used to support sensible applications.
Reviewer: G.Gomez (Erlangen)


93E12 Identification in stochastic control theory
62E20 Asymptotic distribution theory in statistics
60H30 Applications of stochastic analysis (to PDEs, etc.)
93C40 Adaptive control/observation systems
93E11 Filtering in stochastic control theory


Zbl 0639.93002