Abstract
Stability and convergence properties of stochastic approximation algorithms are analyzed when the noise includes a long range dependent component (modeled by a fractional Brownian motion) and a heavy tailed component (modeled by a symmetric stable process), in addition to the usual ‘martingale noise’. This is motivated by the emergent applications in communications. The proofs are based on comparing suitably interpolated iterates with a limiting ordinary differential equation. Related issues such as asynchronous implementations, Markov noise, etc. are briefly discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Here and elsewhere, f n =Θ(g n ) will hold for the statement: both f n =O(g n ) and g n =O(f n ) hold simultaneously.
Extension to more general state spaces is possible—see [5].
References
Abounadi, J., Bertsekas, D.P., Borkar, V.S.: Stochastic approximation for nonexpansive maps: application to Q-learning algorithms. SIAM J. Control Optim. 41(1), 1–22 (2003)
Benaim, M.: Dynamics of stochastic approximation. In: Azema, J., Emery, M., Ledoux, M., Yor, M. (eds.) Le Séminaire de Probabilités. Lecture Notes in Mathematics, vol. 1709, pp. 1–68. Springer, Berlin (1996)
Benveniste, A., Metivier, M., Priouret, P.: Adaptive Algorithms and Stochastic Approximation. Springer, Berlin (1990)
Berman, S.M.: Sojourns and Extremes of Stochastic Processes. Wadsworth and Brooks/Cole, Belmont (1992)
Borkar, V.S.: Stochastic Approximation: A Dynamical Systems Viewpoint. Hindustan Publishing Agency/Cambridge University Press, New Delhi/Cambridge (2008)
Borkar, V.S.: Some examples of stochastic approximation in communications. In: Chahed, T., Tuffin, B. (eds.) Network Control and Optimization. Lecture Notes in Computer Science, vol. 4465, pp. 150–157. Springer, Berlin (2007)
Borkar, V.S., Kumar, P.R.: Dynamic Cesaro–Wardrop equilibration in networks. IEEE Trans. Autom. Control 48(3), 382–396 (2003)
Borkar, V.S., Meyn, S.P.: The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim. 38(2), 447–469 (2000)
Grüne, L., Sontag, E.D., Wirth, F.R.: Asymptotic stability equals exponential stability, and ISS equals finite energy gain—if you twist your eyes. Syst. Control Lett. 38, 127–134 (1999)
Joulin, A.: On maximal inequalities for stable stochastic integrals. Potential Anal. 26, 57–78 (2007)
Kushner, H.J., Yin, G.: Stochastic Approximation and Recursive Algorithms and Applications, 2nd edn. Springer, New York (2003)
Mikosch, T., Resnick, S., Rootzen, H., Stegeman, A.: Is network traffic approximated by stable Lèvy motion or fractional Brownian motion? Ann. Appl. Probab. 12(1), 23–68 (2002)
Neveu, J.: Discrete-Parameter Martingales. North-Holland, Amsterdam (1975)
Wilson, F.W. Jr.: Smoothing derivatives of functions and applications. Trans. Am. Math. Soc. 139, 413–428 (1969)
Zhang, J., Zheng, D., Chiang, M.: The impact of stochastic noisy feedback on distributed network utility maximization. IEEE Trans. Inf. Theory 54(2), 645–665 (2008)
Acknowledgements
Research of V. Anantharam was supported by the ARO MURI grant W911NF-08-1-0233 “Tools for the Analysis and Design of Complex Multi-Scale Networks” and by the NSF grants CCF-0500234, CCF-0635372 and CNS-0627161.
Research of V.S. Borkar was supported in part by the ARO MURI grant W911NF-08-1-0233 “Tools for the Analysis and Design of Complex Multi-Scale Networks” and the J.C. Bose Fellowship.
Author information
Authors and Affiliations
Corresponding author
Appendix: Fernique’s inequality
Appendix: Fernique’s inequality
Let I=[0,1] and (X t ,t∈I) a zero mean scalar Gaussian process. Define for h>0,
Assume lim h↓0 φ(h)=0, so that X is stochastically continuous. Let k≥2 and define
Then Fernique’s inequality says that for any interval J⊂I of width at most h>0,
where \(\varPsi(x) := (2\pi)^{-\frac{1}{2}}\int_{x}^{\infty}e^{-\frac {y^{2}}{2}}\,dy\) as usual. The consequence of important to us is the following ((10.1.9) of [4]): For
J as above, and t 0∈J,
See pp. 197–198 of [4].
Rights and permissions
About this article
Cite this article
Anantharam, V., Borkar, V.S. Stochastic approximation with long range dependent and heavy tailed noise. Queueing Syst 71, 221–242 (2012). https://doi.org/10.1007/s11134-012-9283-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-012-9283-0