Tuan Pham: Confidence sequences for iterated algorithms

Abstract

Confidence sequences are a fundamental tool for inference in sequential experiments. Most existing methods for constructing confidence sequences rely on identifying appropriate non-negative supermartingales. However, such structures are often unavailable in complex settings, such as problems involving stochastic gradient algorithms or high-dimensional parameters.  

In this talk, we propose a new approach to constructing confidence sequences using an adaptive version of the classical Robbins-Siegmund lemma. Our main examples include Oja's algorithm for estimating principal subspaces, the SGD and the Robbins-Monro scheme in stochastic approximation. Notably, we show that the width of our confidence sequences asymptotically matches that of the classical law of the iterated logarithm. This is based on a joint work with Alessandro Rinaldo and Puranamita Sarkar.