Asynchronous Stochastic Approximations (Q4388937)

The asymptotic behavior of a distributed, asynchronous stochastic approximation scheme is analyzed in terms of a limiting nonautonomous differential equation. The relation between the latter and the relative values of suitably rescaled relative frequencies of updates of different components is underscored. The model of asynchronism postulates a set-valued random process that marks the indices to be updated at each iteration. This clumping of indices into sets can be an artifice as long as causal relationships are not violated; thus the set-up is very general, indeed. We impose on this process a natural condition that requires all indices to be updated comparably often in a precise sense. In addition, we allow random, possibly nonstationary and unbounded delays that are required to satisfy a mild conditional moment condition.The analysis depends on proving that the algorithm asymptotically tracks a nonautonomous ODE, in contrast to the traditional autonomous ODE limit. In particular, it gives a handle on situations when the latter may not be feasible. The ODE in question differs from the traditional one in that each component of the driving vector field is now weighted by a time-varying nonnegative scalar. These scalars add to 1 and may be interpreted as relative frequencies of updates of different components after suitable time-scaling. This brings out the desired relationships between updated schemes for different components and paves the way for analyzing situations where they are not desirable.