Back

G-2026-27

Vector generalizations of the Robbins-Siegmund theorem and stochastic gradient descent with delays

, , and

BibTeX reference

The almost supermartingale convergence theorem of Robbins and Siegmund (1971) is a fundamental tool for establishing the convergence of various stochastic iterative algorithms arising in system identification, adaptive control, machine learning, and reinforcement learning. However, the original theorem is limited to scalar-valued stochastic processes. In this paper, we generalize the Robbins-Siegmund theorem to non-negative vector-valued stochastic processes and provide multiple sufficient conditions for such processes to converge almost surely, relying on the convergence of infinite products of matrices. We demonstrate the utility of this framework by introducing the concept of an autoregressive almost supermartingale and applying it to establish the almost sure convergence of stochastic gradient descent with delayed updates.

, 16 pages

Research Axis

Research applications

Document

G2627.pdf (400 KB)