Convergence Rates and Decoupling in Linear Stochastic Approximation\n Algorithms

2014/01/01 by Michael A. Kouritzin, Kouritzin, Michael A., Samira Sadeghi +1 · 1 citation
Computer Science · Engineering · Mathematics · #41A25 #62L12 #62L20 #Approximation Theory and Sequence Spaces #Distributed Sensor Networks and Detection Algorithms #FOS: Mathematics #Primary: 60F15 #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques #secondary: 62J05

paper · pdf · doi:10.48550/arxiv.1501.02414

openalex publication_date 2015/01/10 · openalex created_date 2022/08/06 · openalex updated_date 2026/07/28

Abstract

Almost sure convergence rates for linear algorithms h_k+1 = h_k\n+\(1)/(k^\χ) (b_k-A_kh_k) are studied, where \χ\∈(0,1),\n A_{k k=1}^\∞ are symmetric, positive semidefinite random matrices\nand b_{k k=1}^\∞ are random vectors. It is shown that |h_n-\nA^-1b|=o(n^-\γ) a.s. for the \γ\∈[0,\χ), positive definite\nA and vector b such that frac1n^\χ-\γ\∑\_k=1ⁿ\n(A_k- A)\→ 0 and frac1n^\χ-\γ\∑\_k=1ⁿ (b_k-b)\→\n0 a.s. When \χ-\γ\∈\( frac12,1\), these assumptions are\nimplied by the Marcinkiewicz strong law of large numbers, which allows the\n A_k and b_k to have heavy-tails, long-range dependence or both.\nFinally, corroborating experimental outcomes and decreasing-gain design\nconsiderations are provided.\n

Citations

• A Stochastic Approximation Method
• An algorithm for linearly constrained adaptive array processing

Cited by

• Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning

Related

• Revisiting Step-Size Assumptions in Stochastic Approximation
• Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Statistical inference for Linear Stochastic Approximation with Markovian Noise
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation