Machine Learning Lunch Meeting

General: MLLM is a cross-discipline weekly seminar open to all where UW-Madison professors present their research in machine learning, both theory and applications.  The goal is to promote the great work at UW-Madison and stimulate collaborations. Please see our website for more information.

Speaker: Qiaomin Xie (ISYE)

Abstract: Many reinforcement/machine learning problems involve loss minimization, min-max optimization and fixed-point equations, all of which can be cast under the framework of Variational Inequalities (VIs). Stochastic methods like SGD, SEG and TD/Q Learning are prevalent, and their constant stepsize versions have gained popularity due to effectiveness and robustness. Viewing the iterates of these algorithms as a Markov chain, we study their fine-grained probabilistic behavior. In particular, we establish finite-time geometric convergence of the iterates distribution, and relate the ergodicity properties of the Markov chain to the characteristics of the VI, algorithm and data.

Using techniques of coupling and basic adjoint relationship, we characterize the limit distribution and how its bias depends on the stepsize. For smooth problems, exemplified by TD learning and smooth min-max optimization, the bias is proportional to the stepsize. For nonsmooth problems, exemplified by Q-learning and generalized linear model with nonsmooth link functions (e.g., ReLU), the bias has drastically different behavior and scales with the square root of the stepsize.

This precise probabilistic characterization allows for variance reduction via tail-averaging and bias reduction via Richardson-Romberg extrapolation. The combination of constant stepsize, averaging and extrapolation provides a favorable balance between fast mixing and low long-run error. Empirical results in statistical inference also illustrate the effectiveness of this approach compared to traditional diminishing stepsize schemes.