Variance reduction techniques for stochastic proximal point algorithms
Cheik Traoré Vassilis Apidopoulos Saverio Salzo Silvia Villa
In the context of finite sums minimization, variance reduction techniques are
widely used to improve the performance of state-of-the-art stochastic gradient
methods. Their practical impact is clear, as well as their theoretical
properties. Stochastic proximal point algorithms have been studied as an
alternative to stochastic gradient algorithms since they are more stable with
respect to the choice of the stepsize but a proper variance reduced version is
missing. In this work, we propose the first study of variance reduction
techniques for stochastic proximal point algorithms. We introduce a stochastic
proximal version of SVRG, SAGA, and some of their variants for smooth and
convex functions. We provide several convergence results for the iterates and
the objective function values. In addition, under the Polyak-{\L}ojasiewicz
(PL) condition, we obtain linear convergence rates for the iterates and the
function values. Our numerical experiments demonstrate the advantages of the
proximal variance reduction methods over their gradient counterparts,
especially about the stability with respect to the choice of the step size.