On the step size selection in variance-reduced algorithm for nonconvex optimization

Abstract

Abstract Nonconvex problems have recently received considerable attention in statistics, machine learning and vision areas. Variance reduction techniques like the SVRG-type and SARAH-type methods, originally proposed for convex optimization, have been proved to be effective for nonconvex optimization. The performance of variance-reduced stochastic gradient methods greatly depends on how step sizes are tuned and decreased over time. However, research on specifying online step size in nonconvex optimization is quite limited. Motivated by this gap, we propose using the random stabilized Barzilai–Borwein (RSBB) method to compute step size for variance-reduced stochastic gradient methods. In particular, we incorporate RSBB into the modern variance-reduced stochastic gradient method, the SARAH-type method, for nonconvex optimization. We theoretically prove that the proposed method converges sub-linearly for general nonconvex objective functions and converges linearly for gradient dominated functions. We also show that the complexity of our proposed method is comparable to modern stochastic gradient methods. To further show the efficacy of the RSBB method, we proposed MSVRG-RSBB, by introducing it into MSVRG (a variant of the SVRG method). We provide experimental results on various datasets to show the efficacy of our proposed methods.