Adaptive Algorithms and Stochastic Approximations

I. Adaptive Algorithms: Applications.- 1. General Adaptive Algorithm Form.- 1.1 Introduction.- 1.2 Two Basic Examples and Their Variants.- 1.3 General Adaptive Algorithm Form and Main Assumptions.- 1.4 Problems Arising.- 1.5 Summary of the Adaptive Algorithm Form: Assumptions (A).- 1.6 Conclusion.- 1.7 Exercises.- 1.8 Comments on the Literature.- 2. Convergence: the ODE Method.- 2.1 Introduction.- 2.2 Mathematical Tools: Informal Introduction.- 2.3 Guide to the Analysis of Adaptive Algorithms.- 2.4 Guide to Adaptive Algorithm Design.- 2.5 The Transient Regime.- 2.6 Conclusion.- 2.7 Exercises.- 2.8 Comments on the Literature.- 3. Rate of Convergence.- 3.1 Mathematical Tools: Informal Description.- 3.2 Applications to the Design of Adaptive Algorithms with Decreasing Gain.- 3.3 Conclusions from Section 3.2.- 3.4 Exercises.- 3.5 Comments on the Literature.- 4. Tracking Non-Stationary Parameters.- 4.1 Tracking Ability of Algorithms with Constant Gain.- 4.2 Multistep Algorithms.- 4.3 Conclusions.- 4.4 Exercises.- 4.5 Comments on the Literature.- 5. Sequential Detection; Model Validation.- 5.1 Introduction and Description of the Problem.- 5.2 Two Elementary Problems and their Solution.- 5.3 Central Limit Theorem and the Asymptotic Local Viewpoint.- 5.4 Local Methods of Change Detection.- 5.5 Model Validation by Local Methods.- 5.6 Conclusion.- 5.7 Annex: Proofs of Theorems 1 and 2.- 5.8 Exercises.- 5.9 Comments on the Literature.- 6. Appendices to Part I.- 6.1 Rudiments of Systems Theory.- 6.2 Second Order Stationary Processes.- 6.3 Kaiman Filters.- II. Stochastic Approximations: Theory.- 1. O.D.E. and Convergence A.S. for an Algorithm with Locally Bounded Moments.- 1.1 Introduction of the General Algorithm.- 1.2 Assumptions Peculiar to Chapter 1.- 1.3 Decomposition of the General Algorithm.- 1.4 L2 Estimates.- 1.5 Approximation of the Algorithm by the Solution of the O.D.E.- 1.6 Asymptotic Analysis of the Algorithm.- 1.7 An Extension of the Previous Results.- 1.8 Alternative Formulation of the Convergence Theorem.- 1.9 A Global Convergence Theorem.- 1.10 Rate of L2 Convergence of Some Algorithms.- 1.11 Comments on the Literature.- 2. Application to the Examples of Part I.- 2.1 Geometric Ergodicity of Certain Markov Chains.- 2.2 Markov Chains Dependent on a Parameter ?.- 2.3 Linear Dynamical Processes.- 2.4 Examples.- 2.5 Decision-Feedback Algorithms with Quantisation.- 2.6 Comments on the Literature.- 3. Analysis of the Algorithm in the General Case.- 3.1 New Assumptions and Control of the Moments.- 3.2 Lq Estimates.- 3.3 Convergence towards the Mean Trajectory.- 3.4 Asymptotic Analysis of the Algorithm.- 3.5 "Tube of Confidence" for an Infinite Horizon.- 3.6 Final Remark. Connections with the Results of Chapter 1.- 3.7 Comments on the Literature.- 4. Gaussian Approximations to the Algorithms.- 4.1 Process Distributions and their Weak Convergence.- 4.2 Diffusions. Gaussian Diffusions.- 4.3 The Process U?(t) for an Algorithm with Constant Step Size.- 4.4 Gaussian Approximation of the Processes U?(t).- 4.5 Gaussian Approximation for Algorithms with Decreasing Step Size.- 4.6 Gaussian Approximation and Asymptotic Behaviour of Algorithms with Constant Steps.- 4.7 Remark on Weak Convergence Techniques.- 4.8 Comments on the Literature.- 5. Appendix to Part II: A Simple Theorem in the "Robbins-Monro" Case.- 5.1 The Algorithm, the Assumptions and the Theorem.- 5.2 Proof of the Theorem.- 5.3 Variants.- Subject Index to Part I.- Subject Index to Part II.