Online Statistical Inference for Proximal Stochastic Gradient Descent under Markovian Sampling

Abstract

Nonsmooth stochastic optimization has emerged as a fundamental framework for modeling complex machine learning problems, particularly those involving constraints. Proximal stochastic gradient descent (proximal SGD) is the predominant algorithm used to solve such problems. While most existing work focuses on the i.i.d. data setting, nonsmooth optimization under Markovian sampling remains largely unexplored. In this work, we propose an online statistical inference procedure for nonsmooth optimization under Markovian sampling using proximal SGD. We establish asymptotic normality of the averaged proximal SGD iterates and introduce a random scaling strategy that constructs parameter-free pivotal statistics through appropriate normalization. This approach enables asymptotically valid and fully online confidence intervals. Numerical experiments support the theory and demonstrate practical effectiveness.

Sen Na

Assistant Professor in ISyE

Sen Na is an Assistant Professor in the School of Industrial and Systems Engineering at Georgia Tech. Prior to joining ISyE, he was a postdoctoral researcher in the statistics department and ICSI at UC Berkeley. His research interests broadly lie in the mathematical foundations of data science, with topics including high-dimensional statistics, graphical models, semiparametric models, optimal control, and large-scale and stochastic nonlinear optimization. He is also interested in applying machine learning methods to problems in biology, neuroscience, and engineering.