Title: Guaranteed Sufficient Decrease for Variance Reduced Stochastic Gradient Descent,
Abstract: In this paper, we propose a novel sufficient decrease technique for variance
reduced stochastic gradient descent methods such as SAG, SVRG and SAGA. In
order to make sufficient decrease for stochastic optimization, we design a new
sufficient decrease criterion, which yields sufficient decrease versions of
variance reduction algorithms such as SVRG-SD and SAGA-SD as a byproduct. We
introduce a coefficient to scale current iterate and satisfy the sufficient
decrease property, which takes the decisions to shrink, expand or move in the
opposite direction, and then give two specific update rules of the coefficient
for Lasso and ridge regression. Moreover, we analyze the convergence properties
of our algorithms for strongly convex problems, which show that both of our
algorithms attain linear convergence rates. We also provide the convergence
guarantees of our algorithms for non-strongly convex problems. Our experimental
results further verify that our algorithms achieve significantly better
performance than their counterparts.