Weighted averaging and stochastic approximation (Q1367100)

The authors investigate the relations between weighted averaging and stochastic approximation (SA) algorithms. First, they define the weighted averaging operator and introduce two properties of the operator: regularity and effectiveness. They establish necessary and sufficient conditions on a sequence for convergence of its average. The equivalence between weighted averaging and SA in terms of convergence is proved, i.e., it is shown that the convergence of a weighted average of the noise sequence is necessary and sufficient for the convergence of standard SA algorithms. Based on this, they present necessary and sufficient noise conditions for convergence of averaged SA algorithms in the linear case. The established noise conditions for convergence of the averaged SA algorithms are substantially weaker than the conditions for convergence of the standard SA algorithms without averaging. The analysis is deterministic by studying the sample-path behavior of the algorithms.