Stochastic Approximation: A Dynamical Systems Viewpoint

Inhaltsverzeichnis

1. Frontmatter

2. Chapter 1. Introduction

   Vivek S. Borkar

   Abstract

   Consider an initially empty urn to which balls, either red or black, are added one at a time. Let \(y_n\) denote the number of red balls at time n and \(x_n {\mathop {=}\limits ^{{\text {def}}}}y_n/n\) the fraction of red balls at time n.

3. Chapter 2. Convergence Analysis

   Vivek S. Borkar

   Abstract

   In this chapter, we begin our formal analysis of the stochastic approximation scheme in \(\mathcal {R}^d\) given by

4. Chapter 3. Finite Time Bounds and Traps

   Vivek S. Borkar

   Abstract

   Recall the urn model of Chap. 1. When there are multiple isolated stable equilibria, it turns out that there can be a positive probability of convergence to one of these equilibria which is not, however, necessarily among the desired ones. This, we recall, was the explanation for several instances of adoption of one particular convention or technology as opposed to another.

5. Chapter 4. Stability Criteria

   Vivek S. Borkar

   Abstract

   In this chapter, we discuss a few schemes for establishing the a.s. boundedness of iterates assumed above.

6. Chapter 5. Stochastic Recursive Inclusions

   Vivek S. Borkar

   Abstract

   This chapter considers an important generalization of the basic stochastic approximation scheme of Chap. 2, which we call ‘stochastic recursive inclusions’.

7. Chapter 6. Asynchronous Schemes

   Vivek S. Borkar

   Abstract

   Until now, we have been considering the case where all components of \(x_n\) are updated simultaneously at time n and the outcome is immediately available for the next iteration. There may, however, be situations when different components are updated by possibly different processors. These could be in different locations, e.g., in remote sensing applications.

8. Chapter 7. A Limit Theorem for Fluctuations

   Vivek S. Borkar

   Abstract

   To motivate the results of this chapter, consider the classical strong law of large numbers: Let \(\{X_n\}\) be i.i.d. random variables with \(E\left[ X_n\right] = \mu , E\left[ X_n^2\right] < \infty \).

9. Chapter 8. Multiple Timescales

   Vivek S. Borkar

   Abstract

   In the preceding chapters, we have used a fixed stepsize schedule \(\{a(n)\}\) for all components of the iterations in stochastic approximation. In the ‘o.d.e. approach’ to the analysis of stochastic approximation, these are viewed as discrete nonuniform time steps.

10. Chapter 9. Constant Stepsize Algorithms

    Vivek S. Borkar

    Abstract

    In many practical circumstances, it is more convenient to use a small constant stepsize \(a(n) \equiv a \in (0, 1)\) rather than the decreasing stepsize considered thus far. One such situation is when the algorithm is ‘hard-wired’ and decreasing stepsize may mean additional overheads.

11. Chapter 10. General Noise Models

    Vivek S. Borkar

    Abstract

    We now consider a stochastic approximation scheme in the framework of Chap. 2, but with noise models that go beyond simple martingale difference noise, viz., noise with long range dependence and heavy tails. This scenario has become important because of the many situations where such models are more natural, e.g., internet traffic and finance.

12. Chapter 11. Stochastic Gradient Schemes

    Vivek S. Borkar

    Abstract

    By far the most frequently applied instance of stochastic approximation is the stochastic gradient descent (or ascent) algorithm and its many variants. As the name suggests, these are noisy cousins of the eponymous algorithms from optimization that seek to minimize or maximize a given performance measure.

13. Chapter 12. Liapunov and Related Systems

    Vivek S. Borkar

    Abstract

    We consider here algorithms which cannot be cast as stochastic gradient schemes, but have associated with their limiting (d-dimensional) o.d.e.

14. Backmatter