On almost-sure bounds for the LMS algorithm

Almost-sure (a.s.) bounds for linear, constant-gain, adaptive filtering algorithms are investigated. For instance, under general pseudo-stationarity and dependence conditions on the driving data {ψk,k=1,2,3,...}, {Y_k,k=0,1,2,...} a.s. convergence and rates of a.s. convergence (as the algorithm gain ε→0) are established for the LMS algorithm h_k+1^ε=h _k^ε+εY_k(ψ_k+1 -Y_k^Th_k^ε) subject to some nonrandom initial condition h₀^ε=h ₀. In particular, defining {g_k^ε} _k=0^∞ by g₀^ε=h ₀ and g_k+1^ε=g_k^ε +ε(E[Y_kψ_k+1]-E[Y_kY _k^T]g_k^ε) for k=0,1,2,..., the author shows that for any γ>0 max_{0⩽k⩽γε(-1/)|h}sub k/^ε-g_k^ε|→0 as ε→0 a.s. and under a stronger dependency condition, the author shows that for any 0<ζ⩽1 and γ>0, max_{0⩽k⩽γε(-ζ/)|h}sub k/^ε -g_k^ε| converges (as ε→0) a.s. At a rate marginally slower than O((ε^2-ζlog log(ε^-ζ))^½). Then, under a stronger pseudostationarity assumption it is shown that similar results hold if the sequences {g_k^ε}_k=0 ^∞,ε>0 in the above results are replaced with the solution g⁰(·) of a nonrandom linear ordinary differential equation, i.e. one has, max_{0⩽k⩽[γε(-ζ/])|h}sub k/^ε -g⁰(εk)|→0 as ε→0 a.s., where one can attach a rate to this convergence under the stronger dependency condition. The almost-sure bounds contained in the paper complement previously developed weak convergence results in Kushner and Shwartz [IEEE Trans. Information Theory, IT-30(2), 177-182, 1984] and, as are “near optimal”. Moreover, the proofs used to establish these bounds are quite elementary