Rate of Convergence for Constrained Stochastic Approximation Algorithms (Q4537775)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1758220
Language Label Description Also known as
default for all languages
No label defined
    English
    Rate of Convergence for Constrained Stochastic Approximation Algorithms
    scientific article; zbMATH DE number 1758220

      Statements

      Rate of Convergence for Constrained Stochastic Approximation Algorithms (English)
      0 references
      0 references
      0 references
      23 June 2002
      0 references
      constrained stochastic approximation
      0 references
      rate of convergence
      0 references
      weak convergence
      0 references
      The authors consider stochastic approximation-type algorithms of the form (essentially, extensions are stated and referred to) (1) \( \theta_{n+1} = \theta_{n} + \varepsilon_n Y_n\), decreasing step-size, and \(\varepsilon_n \rightarrow 0\). They treat the case where the stochastic approximation algorithm is constrained, that is the iterates are required not to leave a certain set \(H\). The constraint is enforced by orthogonal projection back onto \(H\), resulting in the inclusion of a correction term \(\varepsilon_n Z_n\) on the right-hand-side of (1). They assume that there is \(\overline \theta\), such that \(\theta_n\) converges to \(\overline \theta\) with probability one. Convergence of this kind of algorithms (with probability one or in the weak sense) is well-established, for the unconstrained, as well as for the constrained case. Results concerning the rate of convergence have been obtained for the unconstrained case and, under the restriction that the limit point \({\overline \theta}\) is in the interior of \(H\), for the constrained case. The authors prove rate of convergence theorems for a large class of systems in the case where the limit \({\overline \theta}\) is on the boundary of \(H\). Under the assumption that the noise is a martingale difference, they prove weak convergence, that is, tightness of \(U_n\), the centered and normalized iterate, to an appropriate stationary reflected linear diffusion, whose variance then plays the usual role as a measure of the rate of convergence. Extensions and applications are also provided.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references