An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization
This is an incremental improvement for researchers in optimization, reducing computational cost in stochastic gradient evaluations.
The authors tackled the problem of stochastic composite nonconvex optimization by proposing a variant of a hybrid variance-reduced proximal gradient method, which saves one stochastic gradient per iteration compared to prior work and achieves optimal stochastic oracle complexity up to a constant factor.
In this note we propose a new variant of the hybrid variance-reduced proximal gradient method in [7] to solve a common stochastic composite nonconvex optimization problem under standard assumptions. We simply replace the independent unbiased estimator in our hybrid- SARAH estimator introduced in [7] by the stochastic gradient evaluated at the same sample, leading to the identical momentum-SARAH estimator introduced in [2]. This allows us to save one stochastic gradient per iteration compared to [7], and only requires two samples per iteration. Our algorithm is very simple and achieves optimal stochastic oracle complexity bound in terms of stochastic gradient evaluations (up to a constant factor). Our analysis is essentially inspired by [7], but we do not use two different step-sizes.