Journal of University of Chinese Academy of Sciences >
Averaging-based truncated stochastic approximation algorithm
Received date: 2014-04-16
Revised date: 2014-08-06
Online published: 2015-05-15
In this work the stochastic approximation problem of perturbed linear systems was examined. Inspired by the averaging-based accelerated algorithm of Polyak and Juditsky(SIAM J. Control & Optimization,1992,30:838-855), we propose an averaging-based truncated algorithm. The almost sure convergence and asymptotic normality of the sequence defined by this algorithm are proved.
Key words： asymptotic normality; linear system; strong consistency
LIU Renlong , YANG Jiankui , XIONG Shifeng . Averaging-based truncated stochastic approximation algorithm[J]. Journal of University of Chinese Academy of Sciences, 2015 , 32(3) : 289 -294 . DOI: 10.7523/j.issn.2095-6134.2015.03.001
[1] Robbins H, Siegmund D. A stochastic approximation method[J]. Ann Math Statist, 1951,22:400-407.
[2] Kiefer E, Wolfovitz J. Stochastic estimation of the maximum of a regression function[J]. Ann Math Statist, 1952,23:462-466.
[3] Kornfelev A P, Stochastic recurrent procedures[M]. Nauka, 1981 (in Russian).
[4] Kushner H J, Clark D S, Stochastic approximation methods for constrained and unconstrained systems[M].Springer, New York, 1978.
[5] Nemirovski A, Juditsky A, Lan G,et al. Robust stochastic approximation approach to stochastic programming[J]. SIAM J Optim, 2009,19:1 574-1 609.
[6] Stein M L, Chen J, Anitescu M. Stochastic approximation of score functions for Gaussian processes[J]. Ann Appl Stat, 2013,7:1 162-1 191.
[7] Benaim M, Faure M. Stochastic approximation, cooperative dynamics and supermodular games[J]. Ann Appl Probab, 2012,22:2 133-2 164.
[8] Koshal J, Nedic A, Shanbhag U V. Regularized iterative stochastic approximation methods for stochastic variational inequality problems[J]. IEEE Trans Automat Control, 2013, 58:594-609.
[9] Polyak B T. New stochastic approximation type procedures[J]. Avtomat Telemekh, 1990,N7:98-107(in Russian).
[10] Ruppert D. Efficient estimators from a slowly convergent Robbins-Monro process[R]. Tech Report No. 781, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1988.
[11] Polyak B T, Juditsky A B. Acceleration of stochastic approximation by averaging[J]. SIAM J Control and optimization, 1992,30:838-855.
[12] 陈翰馥, 朱允民.随机逼近[M]. 上海:上海科学技术出版社, 1996.
[13] 陈翰馥, 扩展截尾的随机逼近算法[J].系统科学与数学, 2012, 12:1 472-1 487
[14] Liptzer R S, Shiryaev A N. Martingale theory[M]. Nauka, Moscow,1986(in Russian).
/
| 〈 |
|
〉 |