%{search_type} search results

• 1. Introduction
• 2. Convergence Analysis
• 3. Finite Time Bounds and Traps
• 4. Stability Criteria
• 5. Stochastic Recursive Inclusions
• 6. Asynchronous Schemes
• 7. A Limit Theorem for Fluctuations
• 8. Multiple Timescales
• 9. Constant Stepsize Algorithms
• 10. General Noise Models
• 11. Stochastic Gradient Schemes
• 12. Liapunov and Related Systems
• 13. Appendix A: Topics in Analysis
• 14. Appendix B: Ordinary Differential Equations
• 15. Appendix C: Topics in Probability
• Bibliography
• Index. .

This book serves as an advanced text for a graduate course on stochastic algorithms for graduate students in probability and statistics, engineering, economics and machine learning. This second edition gives a comprehensive treatment of stochastic approximation algorithms based on the ordinary differential equation (ODE) approach which analyses the algorithm in terms of a limiting ODE. It has a streamlined treatment of the classical convergence analysis and includes several recent developments such as concentration bounds, avoidance of traps, stability tests, distributed and asynchronous schemes, multiple time scales, general noise models, etc., and a category-wise exposition of many important applications. It is also a useful reference for researchers and practitioners in the field.

• Preface
• 1. Introduction
• 2. Basic convergence analysis
• 3. Stability criteria
• 4. Lock-in probability
• 5. Stochastic recursive inclusions
• 6. Multiple timescales
• 7. Asynchronous schemes
• 8. A limit theorem for fluctuations
• 9. Constant stepsize algorithms
• 10. Applications
• 11. Appendices
• References
• Index.
• (source: Nielsen Book Data)

This simple, compact toolkit for designing and analyzing stochastic approximation algorithms requires only basic literacy in probability and differential equations. Yet these algorithms have powerful applications in control and communications engineering, artificial intelligence and economic modelling. The dynamical systems viewpoint treats an algorithm as a noisy discretization of a limiting differential equation and argues that, under reasonable hypotheses, it tracks the asymptotic behaviour of the differential equation with probability one. The differential equation, which can usually be obtained by inspection, is easier to analyze. Novel topics include finite-time behaviour, multiple timescales and asynchronous implementation. There is a useful taxonomy of applications, with concrete examples from engineering and economics. Notably it covers variants of stochastic gradient-based optimization schemes, fixed-point solvers, which are commonplace in learning algorithms for approximate dynamic programming, and some models of collective behaviour. Three appendices give background on differential equations and probability.
(source: Nielsen Book Data)

• Preface. Acknowledgments.
• 1. Robbins-Monro Algorithm.
• 2. Stochastic Approximation Algorithms with Expanding Truncations.
• 3. Asymptotic Properties of Stochastic Approximation Algorithms.
• 4. Optimization by Stochastic Approximation.
• 5. Applications To Signal Processing.
• 6. Application to Systems and Control.
• 7. Appendices. References. Index.
• (source: Nielsen Book Data)

This book presents the recent development of stochastic approximation algorithms with expanding truncations based on the TS (trajectory-subsequence) method, a newly developed method for convergence analysis. This approach is so powerful that conditions used for guaranteeing convergence have been considerably weakened in comparison with those applied in the classical probability and ODE methods. The general convergence theorem is presented for sample paths and is proved in a purely deterministic way. The sample-path description of theorems is particularly convenient for applications. Convergence theory takes both observation noise and structural error of the regression function into consideration. Convergence rates, asymptotic normality and other asymptotic properties are presented as well. Applications of the developed theory to global optimization, blind channel identification, adaptive filtering, system parameter identification, adaptive stabilization and other problems arising from engineering fields are demonstrated.
(source: Nielsen Book Data)

• Applications and issues
• application to learning, state dependent noise and queueing
• applications to signal processing and adaptive control
• mathematical background
• convergence with probability one - Martingale difference noise
• convergence with probability one - correlated noise
• weak convergence - introduction
• weak convergence methods for general algorithms
• applications - proofs of convergence
• rate of convergence
• averaging of the iterates
• distributed/decentralized and asynchronous algorithms.
• (source: Nielsen Book Data)

In recent years, algorithms of the stochastic approximation type have found applications in new and diverse areas and new techniques have been developed for proofs of convergence and rate of convergence. The actual and potential applications in signal processing have exploded. New challenges have arisen in applications to adaptive control. This book presents a thorough coverage of the ODE method used to analyze these algorithms.
(source: Nielsen Book Data)

• Strong approximations of partial sums of independent identically distributed random variables
• renewal and related processes
• uniform empirical and quantile processes and their approximations
• weighted approximations of uniform empirical and quantile processes
• asymptotic distributions of functionals of weighted uniform empirical and quantile processes
• general quantile processes and their approximations.
• (source: Nielsen Book Data)

A survey of recent developments in probability and statistics research, which concentrates on renewal and related processes, weighted approximations of empirical and quantile processes, and the asymptotic distributions of functionals of these weighted processes.
(source: Nielsen Book Data)

• Preface Introduction Elements of probability and martingales Discrete time Markov processes Markov processes and stochastic equations Convergence of stochastic approximation procedures. I Convergence of stochastic approximation procedures. II Asymptotic normality of the Robbins-Monro procedure Some modifications of stochastic approximation procedures Recursive estimation (discrete time) Recursive estimation (continuous time) Recursive estimation with a control parameter

This book is devoted to sequential methods of solving a class of problems to which belongs, for example, the problem of finding a maximum point of a function if each measured value of this function contains a random error. Some basic procedures of stochastic approximation are investigated from a single point of view, namely the theory of Markov processes and martingales. Examples are considered of applications of the theorems to some problems of estimation theory, educational theory and control theory, and also to some problems of information transmission in the presence of inverse feedback.
(source: Nielsen Book Data)

• Preface
• 1. Introduction
• 2. The Robbins-Monro method
• 3. The Kiefer-Wolfowitz method
• 4. Applications
• 5. Multivariate stochastic-approximation methods
• 6. Asymptotic normality
• 7. The approximation for continuous random processes
• 8. Up-and-down method
• Appendices
• Bibliography
• Index.
• (source: Nielsen Book Data)

Stochastic approximation is a relatively new technique for studying the properties of an experimental situation; it has important applications in fields such as medicine and engineering. The subject can be treated either largely as a branch of pure mathematics, or else from an empirical and practical angle. In this book, Dr Wasan gives a rigorous mathematical treatment of the subject, drawing together the scattered results of a number of authors. He discusses the conditions under which the method gives a valid approximation to the required solution; methods for optimal choice of parameters to hasten convergence; the comparison of the method with other techniques. The discussion and proofs of theorems are given in enough detail to make them easy to follow, while a number of interesting examples show how the techniques may be applied in many fields.
(source: Nielsen Book Data)

• Introduction
• 1 Review of Continuous Time Models 1.1 Martingales and Martingale Inequalities 1.2 Stochastic Integration 1.3 Stochastic Differential Equations: Diffusions 1.4 Reflected Diffusions 1.5 Processes with Jumps
• 2 Controlled Markov Chains 2.1 Recursive Equations for the Cost 2.2 Optimal Stopping Problems 2.3 Discounted Cost 2.4 Control to a Target Set and Contraction Mappings 2.5 Finite Time Control Problems
• 3 Dynamic Programming Equations 3.1 Functionals of Uncontrolled Processes 3.2 The Optimal Stopping Problem 3.3 Control Until a Target Set Is Reached 3.4 A Discounted Problem with a Target Set and Reflection 3.5 Average Cost Per Unit Time
• 4 Markov Chain Approximation Method: Introduction 4.1 Markov Chain Approximation 4.2 Continuous Time Interpolation 4.3 A Markov Chain Interpolation 4.4 A Random Walk Approximation 4.5 A Deterministic Discounted Problem 4.6 Deterministic Relaxed Controls
• 5 Construction of the Approximating Markov Chains 5.1 One Dimensional Examples 5.2 Numerical Simplifications 5.3 The General Finite Difference Method 5.4 A Direct Construction 5.5 Variable Grids 5.6 Jump Diffusion Processes 5.7 Reflecting Boundaries 5.8 Dynamic Programming Equations 5.9 Controlled and State Dependent Variance
• 6 Computational Methods for Controlled Markov Chains 6.1 The Problem Formulation 6.2 Classical Iterative Methods 6.3 Error Bounds 6.4 Accelerated Jacobi and Gauss-Seidel Methods 6.5 Domain Decomposition 6.6 Coarse Grid-Fine Grid Solutions 6.7 A Multigrid Method 6.8 Linear Programming
• 7 The Ergodic Cost Problem: Formulation and Algorithms 7.1 Formulation of the Control Problem 7.2 A Jacobi Type Iteration 7.3 Approximation in Policy Space 7.4 Numerical Methods 7.5 The Control Problem 7.6 The Interpolated Process 7.7 Computations 7.8 Boundary Costs and Controls
• 8 Heavy Traffic and Singular Control 8.1 Motivating Examples 8.2 The Heavy Traffic Problem 8.3 Singular Control
• 9 Weak Convergence and the Characterization of Processes 9.1 Weak Convergence 9.2 Criteria for Tightness in $D^{k}\left [0, \infty \right )$ 9.3 Characterization of Processes 9.4 An Example 9.5 Relaxed Controls
• 10 Convergence Proofs 10.1 Limit Theorems 10.2 Existence of an Optimal Control 10.3 Approximating the Optimal Control 10.4 The Approximating Markov Chain 10.5 Convergence of the Costs 10.6 Optimal Stopping
• 11 Convergence for Reflecting Boundaries, Singular Control, and Ergodic Cost Problems 11.1 The Reflecting Boundary Problem 11.2 The Singular Control Problem 11.3 The Ergodic Cost Problem
• 12 Finite Time Problems and Nonlinear Filtering 12.1 Explicit Approximations: An Example 12.2 General Explicit Approximations 12.3 Implicit Approximations: An Example 12.4 General Implicit Approximations 12.5 Optimal Control Computations 12.6 Solution Methods 12.7 Nonlinear Filtering
• 13 Controlled Variance and Jumps 13.1 Controlled Variance: Introduction 13.2 Controlled Jumps
• 14 Problems from the Calculus of Variations: Finite Time Horizon 14.1 Problems with a Continuous Running Cost 14.2 Numerical Schemes and Convergence 14.3 Problems with a Discontinuous Running Cost
• 15 Problems from the Calculus of Variations: Infinite Time Horizon 15.1 Problems of Interest 15.2 Numerical Schemes for the Case $k(x, \alpha ) \geq k_0 > 0$ 15.3 Numerical Schemes for the Case $k(x, \alpha ) \geq 0$ 15.4 Remarks on Implementation and Examples
• 16 The Viscosity Solution Approach 16.1 Definitions and Some Properties of Viscosity Solutions 16.2 Numerical Schemes 16.3 Proof of Convergence References Index List of Symbols.
• (source: Nielsen Book Data)

The book presents a thorough development of the modern theory of stochastic approximation or recursive stochastic algorithms for both constrained and unconstrained problems. There is a complete development of both probability one and weak convergence methods for very general noise processes. The proofs of convergence use the ODE method, the most powerful to date, with which the asymptotic behavior is characterized by the limit behavior of a mean ODE. The assumptions and proof methods are designed to cover the needs of recent applications. The development proceeds from simple to complex problems, allowing the underlying ideas to be more easily understood. Rate of convergence, iterate averaging, high-dimensional problems, stability-ODE methods, two time scale, asynchronous and decentralized algorithms, general correlated and state-dependent noise, perturbed test function methods, and large devitations methods, are covered. Many motivational examples from learning theory, ergodic cost problems for discrete event systems, wireless communications, adaptive control, signal processing, and elsewhere, illustrate the application of the theory. This second edition is a thorough revision, although the main features and the structure remain unchanged. It contains many additional applications and results, and more detailed discussion. Harold J. Kushner is a University Professor and Professor of Applied Mathematics at Brown University. He has written numerous books and articles on virtually all aspects of stochastic systems theory, and has received various awards including the IEEE Control Systems Field Award.
(source: Nielsen Book Data)

• Invited Papers.- On Computation and Communication with Small Bias.- Design Strategies for Minimal Perfect Hash Functions.- Hamming, Permutations and Automata.- Probabilistic Techniques in Algorithmic Game Theory.- Randomized Algorithms and Probabilistic Analysis in Wireless Networking.- Contributed Papers.- A First Step Towards Analyzing the Convergence Time in Player-Specific Singleton Congestion Games.- Communication Problems in Random Line-of-Sight Ad-Hoc Radio Networks.- Approximate Discovery of Random Graphs.- A VNS Algorithm for Noisy Problems and Its Application to Project Portfolio Analysis.- Digit Set Randomization in Elliptic Curve Cryptography.- Lower Bounds for Hit-and-Run Direct Search.- An Exponential Gap Between LasVegas and Deterministic Sweeping Finite Automata.- Stochastic Methods for Dynamic OVSF Code Assignment in 3G Networks.- On the Support Size of Stable Strategies in Random Games.
• (source: Nielsen Book Data)

This book constitutes the refereed proceedings of the 4th International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2007. The nine revised full papers and five invited papers presented were carefully selected for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations with a special focus on investigating the power of randomization in algorithmics.
(source: Nielsen Book Data)

This book constitutes the refereed proceedings of the Third International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2005, held in Moscow, Russia in October 2005. The 14 revised full papers presented together with 5 invited papers were carefully reviewed and selected for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations whith a special focus on new algorithmic ideas involving stochastic decisions and the design and evaluation of stochastic algorithms within realistic scenarios.
(source: Nielsen Book Data)

This book constitutes the refereed proceedings of the Second International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2003, held in Hatfield, UK in September 2003.The 12 revised full papers presented together with three invited papers were carefully reviewed and selected for inclusion in the book. Among the topics addressed are ant colony optimization, randomized algorithms for the intersection problem, local search for constraint satisfaction problems, randomized local search and combinatorial optimization, simulated annealing, probabilistic global search, network communication complexity, open shop scheduling, aircraft routing, traffic control, randomized straight-line programs, and stochastic automata and probabilistic transformations.
(source: Nielsen Book Data)