Non-asymptotic error bounds for constant stepsize stochastic approximation for tracking mobile agents

被引：2
|
作者：
Kumar, Bhumesh [1 ,2 ]
Borkar, Vivek [1 ]
Shetty, Akhil [1 ,3 ]
机构：
[1] Indian Inst Technol, Dept Elect Engn, Mumbai 400076, Maharashtra, India
[2] Univ Wisconsin, Dept Elect & Comp Engn, 1415 Johnson Dr, Madison, WI 53706 USA
[3] Univ Calif Berkeley, Dept Elect Engn & Comp Sci, Cory Hall,Hearst Ave, Berkeley, CA 94720 USA
来源：
MATHEMATICS OF CONTROL SIGNALS AND SYSTEMS | 2019年 / 31卷 / 04期
关键词：
Stochastic approximation; Constant stepsize; Non-asymptotic bound; Alekseev's formula; Martingale concentration inequalities; Perturbation analysis; Non-stationary optimization; EXPONENTIAL STABILITY; ASYMPTOTIC ANALYSIS; ALGORITHMS; SYSTEMS; CONVERGENCE; SIZE;
D O I：
10.1007/s00498-019-00249-4
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This work revisits the constant stepsize stochastic approximation algorithm for tracking a slowly moving target and obtains a bound for the tracking error that is valid for the entire time axis, using the Alekseev nonlinear variation of constants formula. It is the first non-asymptotic bound for the entire time axis in the sense that it is not based on the vanishing stepsize limit and associated limit theorems unlike prior works, and captures clearly the dependence on problem parameters and the dimension.
引用
收藏
页码：589 / 614
页数：26
相关论文
共 23 条
  • [1] Non-asymptotic error bounds for constant stepsize stochastic approximation for tracking mobile agents
    Bhumesh Kumar
    Vivek Borkar
    Akhil Shetty
    Mathematics of Control, Signals, and Systems, 2019, 31 : 589 - 614
  • [2] Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
    Karimi, Belhal
    Miasojedow, Blazej
    Moulines, Eric
    Wai, Hoi-To
    CONFERENCE ON LEARNING THEORY, VOL 99, 2019, 99
  • [3] Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT
    Anastasiou, Andreas
    Balasubramanian, Krishnakumar
    Erdogdu, Murat A.
    CONFERENCE ON LEARNING THEORY, VOL 99, 2019, 99
  • [4] Recursive Quantile Estimation: Non-Asymptotic Confidence Bounds
    Chen, Likai
    Keilbar, Georg
    Wu, Wei Biao
    JOURNAL OF MACHINE LEARNING RESEARCH, 2023, 24
  • [5] On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
    Mou, Wenlong
    Li, Chris Junchi
    Wainwright, Martin J.
    Bartlett, Peter L.
    Jordan, Michael I.
    CONFERENCE ON LEARNING THEORY, VOL 125, 2020, 125
  • [6] Non-asymptotic bounds for percentiles of independent non-identical random variables
    Xia, Dong
    STATISTICS & PROBABILITY LETTERS, 2019, 152 : 111 - 120
  • [7] Non-Asymptotic Bounds on the Performance of Dual Methods for Resource Allocation Problems
    Goertzen, Simon
    Schmeink, Anke
    IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, 2014, 13 (06) : 3430 - 3441
  • [8] Sharp non-asymptotic concentration inequalities for the approximation of the invariant distribution of a diffusion
    Honore, Igor
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2020, 130 (04) : 2127 - 2158
  • [9] Non-asymptotic Gaussian estimates for the recursive approximation of the invariant distribution of a diffusion
    Honor, I
    Menozzi, S.
    Pages, G.
    ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2020, 56 (03): : 1559 - 1605
  • [10] New Non-Asymptotic Bounds on Numbers of Codewords for the Fixed-Length Lossy Compression
    Matsuta, Tetsunao
    Uyematsu, Tomohiko
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2016, E99A (12): : 2116 - 2129
123