机器学习与数据科学博士生系列论坛（第五十七期）—— On the Convergence Rates of Two-Time-Scale Stochastic Approximation

摘要：
Two-time-scale stochastic approximation is a variant of the classic stochastic approximation (SA) to find the root of a system of two coupled equations. It has been widely used in various applications spanning stochastic optimization and reinforcement learning. In this algorithm, there are two iterates: the fast iterate and the slow iterate. The fast iterate is updated by using step sizes that are much larger than the ones used to update the slow iterate. Meanwhile, the update rule of the fast iterate depends on the slow iterate and vice versa. Despite the double dependence between the two time scales, decoupled convergence rates could also be established under certain conditions, e.g., the linear case.

In this talk, we first present some typical examples of two-time-scale SA and then discuss the asymptotic and non-asymptotic convergence rates. For the linear case, we show how to achieve decoupled convergence; for the nonlinear case, we compare the convergence results under different conditions.

论坛简介：该线上论坛是由张志华教授机器学习实验室组织，每两周主办一次（除了公共假期）。论坛每次邀请一位博士生就某个前沿课题做较为系统深入的介绍，主题包括但不限于机器学习、高维统计学、运筹优化和理论计算机科学。