Asymptotic behavior of constrained stochastic approximations via the theory of large deviations
type: Item
instance of: scholarly article
title: Asymptotic behavior of constrained stochastic approximations via the theory of large deviations
zbMATH Open document ID: 0599.60028
DOI: 10.1007/BF00354035
author: Paul Dupuis
author: Harold J. Kushner
publication date: 1987-01-01T00:00:00Z
review text: Let G be a bounded convex set, and \(\Pi_ G\) the projection onto G, and \(\{\xi_ j\}^ a \)bounded random process. Projected algorithms of the types \[ X^{\epsilon}_{n+1}=\Pi_ G(X_ n^{\epsilon}+\epsilon b(X_ n^{\epsilon},\xi_ n))\quad (or\quad X_{n+1}=\Pi_ G(X_ n+a_ nb(X_ n,\xi_ n)), \] where \(0<a_ n\to 0\), \(\sum a_ n=\infty)\) occur frequently in applications (among other places) in control and communications theory. The asymptotic convergence properties of \(\{X_ n^{\epsilon}\}\) as \(\epsilon\) \(\to 0\), \(\epsilon\) \(n\to \infty\), have been well analyzed in the literature. Here, we use large deviations methods to get a more thorough understanding of the global behavior. Let \(\theta\) be a stable point of the algorithm in the sense that \(X_ n^{\epsilon}\to \theta\) in distribution as \(\epsilon\) \(\to 0\), \(n\epsilon\) \(\to \infty\). For the unconstrained case, rate of convergence results involve showing asymptotic normality of \(\{(X_ n^{\epsilon}- \theta)/\sqrt{\epsilon}\}\), and use linearizations about \(\theta\). In the constrained case \(\theta\) is often on \(\partial G\), and such methods are inapplicable. But the large deviations method yields an alternative which is often more useful in the applications. The action functionals are derived and their properties (lower semicontinuity, etc.) are obtained. The statistics (mean value, etc.) of the escape times from a neighborhood of \(\theta\) are obtained, and the global behavior on the infinite interval is described.
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 62L20
zbMATH DE Number: 3967563
zbMATH Keywords: asymptotic convergence properties
zbMATH Keywords: large deviations methods
zbMATH Keywords: asymptotic normality
zbMATH Keywords: escape times
MaRDI profile type: Publication
cites work: Stochastic approximation methods for constrained and unconstrained systems
cites work: An Invariant Measure Approach to the Convergence of Stochastic Approximations with State Dependent Noise
cites work: Q3944348
cites work: Stochastic Approximation in Hilbert Space: Identification and Optimization of Linear Continuous Parameter Systems
cites work: Stochastic Minimization with Constant Step-Size: Asymptotic Laws
cites work: THE AVERAGING PRINCIPLE AND THEOREMS ON LARGE DEVIATIONS
cites work: Robustness and Approximation of Escape Times and Large Deviations Estimates for Systems with Small Noise Effects
cites work: Stochastic Approximations via Large Deviations: Asymptotic Properties
cites work: Q3341599
cites work: Q3672830
cites work: Selection theorems and their applications
cites work: Q3344923
cites work: On Upper Functions for Stochastic Approximation Procedures
full work available at URL: https://doi.org/10.1007/bf00354035
OpenAlex ID: W1975622974
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
Recommended article: Q4729198
Recommended article: Asymptotic behavior of stochastic approximation and large deviations
Recommended article: Stochastic Approximations via Large Deviations: Asymptotic Properties
Recommended article: Large deviations analysis of reflected diffusions and constrained stochastic approximation algorithms in convex sets†
Recommended article: Asymptotic behaviour of a class of stochastic approximation procedures
Recommended article: Stochastic Approximation and Large Deviations: Upper Bounds and <scp>w.p.1</scp> Convergence
Recommended article: Concentration bounds for stochastic approximations
Recommended article: Q3336539
description: scientific article; zbMATH DE number 3967563