Variance Reduction on General Adaptive Stochastic Mirror Descent

Abstract

In this work, we propose a simple and generalized algorithmic framework for applying variance reduction to adaptive mirror descent algorithms for faster convergence. We introduce the SVRAMD algorithm, and provide its general convergence analysis in both the nonsmooth nonconvex optimization problem and the generalized P–L conditioned nonconvex optimization problem. We prove that variance reduction can reduce the gradient complexity of all adaptive mirror descent algorithms that satisfy a mild assumption and thus accelerate their convergence. In particular, our general theory implies that variance reduction can be applied to different algorithms with their distinct choices of the proximal function, such as gradient descent with time-varying step sizes, mirror descent with L1\documentclass[12pt]minimal \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}-69pt \begin{document}$L_1$\end{document} mirror maps, and self-adaptive algorithms such as AdaGrad and RMSProp. Moreover, the proved convergence rates of SVRAMD recover the existing rates without complicated algorithmic components, which indicates their optimality. Extensive experiments validate our theoretical findings.