SDS Seminar Series – Tuan Pham, University of Texas at Austin

Title: Time-uniform Bounds for Iterated Algorithms

Abstract: Confidence sequences provide valid inferential guarantees uniformly in time and are fundamentally linked to the problem of obtaining time-uniform bounds for a sequence of estimators. Existing results regarding time-uniform concentration inequalities mostly focus on settings where the estimators possess some form of martingale structure. In this talk, we approach the problem from a different perspective—minimizing reliance on martingale structures, as is often the case in many iterative algorithms such as SGD. We show that, under mild regularity conditions, it is always possible to obtain time-uniform bounds using a variant of the classical Robbins–Siegmund lemma. Step size schedules, convergence rates, and applications to several popular algorithms will also be discussed. This is based on a joint work with Alessandro Rinaldo and Purnamrita Sarkar.