Analysis and improvement for a class of variance reduced methods
Yan Liu, Guo Tiande, Congying Han · Scientia Sinica Mathematica · 2020
Stochastic variance reduced methods have recently surged into prominence for solving large scale optimization problems in machine learning. However, how to choose the step sizes is still a problem to work out. Inspired by SVRG-BB (stochastic variance reduced gradient with Barzilai-Borwein step size), we propose an adaptive step size which is based on local estimation of Lipschitz constant for variance reduced methods. A framework was given of how to select the crucial parameter for different algorithms in our step size by solving a minimax problem.Then we adapt this step size to SARAH (stochastic recursive gradient algorithm) and SVRG (stochastic variance reduced gradient),which leads to two algorithms SARAH-AS (SARAH with adaptive step size) and SVRG-AS (SVRG with adaptive step size), respectively. Both of them converge linearly in the strongly convex case. Furthermore, we provide a novel perspective to explore why SARAH+ performs well in practice. Numerical experiments on standard datasets demonstrate the efficiency of our adaptive step size for stochastic variance reduced methods.