{"ID":2837891,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.18273","arxiv_id":"2511.18273","title":"Time-uniform concentration bounds for iterative algorithms","abstract":"We develop a new framework for deriving time-uniform concentration bounds for the output of stochastic sequential algorithms satisfying certain recursive inequalities akin to those defining the almost-supermartingale processes introduced by \\cite{robbins1971convergence}. Our approach is of wide applicability, and can be deployed in settings in which exponential supermartingale processes, required by prevailing methodologies for anytime-valid concentration inequalities, are not readily available. Our results can be viewed as quantitative versions of the classical Robbins-Siegmund Lemma. We demonstrate the effectiveness of our method by providing new and optimal time-uniform concentration bounds for Oja's algorithm for streaming PCA, stochastic gradient descent, and stochastic approximations.","short_abstract":"We develop a new framework for deriving time-uniform concentration bounds for the output of stochastic sequential algorithms satisfying certain recursive inequalities akin to those defining the almost-supermartingale processes introduced by \\cite{robbins1971convergence}. Our approach is of wide applicability, and can b...","url_abs":"https://arxiv.org/abs/2511.18273","url_pdf":"https://arxiv.org/pdf/2511.18273v1","authors":"[\"Tuan Pham\",\"Alessandro Rinaldo\",\"Purnamrita Sarkar\"]","published":"2025-11-23T03:51:30Z","proceeding":"math.ST","tasks":"[\"math.ST\"]","methods":"[]","has_code":false}