NDLI: Noise conditions for prespecified convergence rates of stochastic approximation algorithms

Content Provider	IEEE Xplore Digital Library
Author	Chong, E.K.P. I-Jeng Wang Kulkarni, S.R.
Copyright Year	1963
Abstract	We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {/spl rho//sub n/} is a given positive sequence converging monotonically to zero. Consider a stochastic approximation algorithm x/sub n+1/=x/sub n/-a/sub n/(A/sub n/x/sub n/-b/sub n/)+a/sub n/e/sub n/, where {x/sub n/} is the iterate sequence, {a/sub n/} is the step size sequence, {e/sub n/} is the noise sequence, and x* is the desired zero of the function f(x)=Ax-b. Then, under appropriate assumptions, we show that x/sub n/-x=o(/spl rho//sub n/) if and only if the sequence {e/sub n/} satisfies one of five equivalent conditions. These conditions are based on well-known formulas for noise sequences: Kushner and Clark's (1978) condition, Chen's (see Proc. IFAC World Congr., p.375-80, 1996) condition, Kulkarni and Horn's (see IEEE Trails Automat. Contr., vol.41, p.419-24, 1996) condition, a decomposition condition, and a weighted averaging condition. Our necessary and sufficient condition on {e/sub n/} to achieve a convergence rate of {/spl rho//sub n/} is basically that the sequence {e/sub n///spl rho//sub n/} satisfies any one of the above five well-known conditions. We provide examples to illustrate our result. In particular, we easily recover the familiar result that if a/sub n/=a/n and {e/sub n/} is a martingale difference process with bounded variance, then x/sub n/-x=o(n/sup -1/2/(log(n))/sup /spl beta//) for any /spl beta/>1/2.
Sponsorship	IEEE Information Theory Society
Starting Page	810
Ending Page	814
Page Count	5
File Size	211243
File Format	PDF
ISSN	00189448
Volume Number	45
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1999-03-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Convergence Stochastic resonance Approximation algorithms Sufficient conditions Hilbert space Writing Stochastic processes Physics Laboratories Neural networks
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the almost sure rate of convergence of linear stochastic approximation algorithms

Geometric Upper Bounds on Rates of Variable-Basis Approximation

An alternative proof for convergence of stochastic approximation algorithms

On Complexity Issues of Online Learning Algorithms

Stability and instability of limit points for stochastic approximation algorithms

Optimal detection of symmetric mixed quantum states

Performance of a Distributed Stochastic Approximation Algorithm

Convergence conditions of dynamic stochastic approximation method for nonlinear stochastic discrete-time dynamic systems

Sequential greedy approximation for certain convex optimization problems

Noise conditions for prespecified convergence rates of stochastic approximation algorithms

Similar Documents

On the almost sure rate of convergence of linear stochastic approximation algorithms

Geometric Upper Bounds on Rates of Variable-Basis Approximation

An alternative proof for convergence of stochastic approximation algorithms

On Complexity Issues of Online Learning Algorithms

Stability and instability of limit points for stochastic approximation algorithms

Optimal detection of symmetric mixed quantum states

Performance of a Distributed Stochastic Approximation Algorithm

Convergence conditions of dynamic stochastic approximation method for nonlinear stochastic discrete-time dynamic systems

Sequential greedy approximation for certain convex optimization problems

Noise conditions for prespecified convergence rates of stochastic approximation algorithms