Stochastic Approximation: A Dynamical Systems Viewpoint

by Vivek S. Borkar

Overview

Simple, compact toolkit for designing and analyzing algorithms, with concrete examples from control and communications engineering, artificial intelligence, economic modelling.

Product Details

ISBN-13:	9780521515924
Publisher:	Cambridge University Press
Publication date:	09/01/2008
Pages:	176
Product dimensions:	6.10(w) x 9.00(h) x 0.60(d)

About the Author

Vivek Shripad Borkar is Professor at the Department of Electrical Engineering, Indian Institute of Technology (IIT) Bombay, Powai, Mumbai, India. Earlier, he held positions at the TIFR Centre for Applicable Mathematics and Indian Institute of Science in Bengaluru; Indian Institute of Science, Bengaluru; Tata Institute of Fundamental Research and Indian Institute of Technology Bombay in Mumbai. He also held visiting positions at the Massachusetts Institute of Technology (MIT), the University of Maryland at College Park, the University of California at Berkeley, and the University of Illinois at Urbana-Champaign, USA.

Professor Borkar obtained his B.Tech. (Electrical Engineering) from the IIT Bombay in 1976, MS (Systems and Control Engineering) from Case Western Reserve University in 1977, and Ph.D. (Electrical Engineering and Computer Sciences) from the University of California, Berkeley, USA, in 1980. He is Fellow of American Mathematical Society, IEEE, and the World Academy of Sciences, and of various science and engineering academies in India. He has won several awards and honours in India and was an invited speaker at the ICM 2006 in Madrid. He has authored/co-authored six books and several archival publications. His primary research interests are in shastic optimization and control, covering theory and algorithms.

Table of Contents

Preface vii

1 Introduction 1

2 Basic Convergence Analysis 10

2.1 The o.d.e. limit 10

2.2 Extensions and variations 16

3 Stability Criteria 21

3.1 Introduction 21

3.2 Stability criterion 21

3.3 Another stability criterion 27

4 Lock-in Probability 31

4.1 Estimating the lock-in probability 31

4.2 Sample complexity 42

4.3 Avoidance of traps 44

5 Stochastic Recursive Inclusions 52

5.1 Preliminaries 52

5.2 The differential inclusion limit 53

5.3 Applications 56

5.4 Projected stochastic approximation 59

6 Multiple Timescales 64

6.1 Two timescales 64

6.2 Averaging the natural timescale: preliminaries 67

6.3 Averaging the natural timescale: main results 73

6.4 Concluding remarks 76

7 Asynchronous Schemes 78

7.1 Introduction 78

7.2 Asymptotic behavior 80

7.3 Effect of delays 82

7.4 Convergence 85

8 A Limit Theorem for Fluctuations 88

8.1 Introduction 88

8.2 A tightness result 89

8.3 The functional central limit theorem 96

8.4 The convergent case 99

9 Constant Stepsize Algorithms 101

9.1 Introduction 101

9.2 Asymptotic behaviour 102

9.3 Refinements 107

10 Applications 117

10.1 Introduction 117

10.2 Stochastic gradient schemes 118

10.3 Stochastic fixed point iterations 125

10.4 Collective phenomena 131

10.5 Miscellaneous applications 137

11 Appendices 140

11.1 Appendix A: Topics in analysis 140

11.1.1 Continuous functions 140

11.1.2 Square-integrable functions 141

11.1.3 Lebesgue's theorem 143

11.2 Appendix B: Ordinary differential equations 143

11.2.1 Basic theory 143

11.2.2 Linear systems 146

11.2.3 Asymptotic behaviour 147

11.3 Appendix C: Topics in probability 149

11.3.1Martingales 149

11.3.2 Spaces of probability measures 152

11.3.3 Stochastic differential equations 153

References 156

Index 163

Editorial Reviews

"I highly recommend it to all readers interested in the theory of recursive algorithms and its applications in practice."
Oleg N. Granichin, Mathematical Reviews

From the Publisher