A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization

arXiv2102.09893MaRDI QIDQ6361052

Author name not available (Why is that?)

Publication date: 19 February 2021

Abstract: In this paper, we proposed a new technique, {em variance controlled stochastic gradient} (VCSG), to improve the performance of the stochastic variance reduced gradient (SVRG) algorithm. To avoid over-reducing the variance of gradient by SVRG, a hyper-parameter $lambda$ is introduced in VCSG that is able to control the reduced variance of SVRG. Theory shows that the optimization method can converge by using an unbiased gradient estimator, but in practice, biased gradient estimation can allow more efficient convergence to the vicinity since an unbiased approach is computationally more expensive. $lambda$ also has the effect of balancing the trade-off between unbiased and biased estimations. Secondly, to minimize the number of full gradient calculations in SVRG, a variance-bounded batch is introduced to reduce the number of gradient calculations required in each iteration. For smooth non-convex functions, the proposed algorithm converges to an approximate first-order stationary point (i.e. $mathbbE|ablaf(x){|}^{2}leqepsilon$) within $mathcalO(min1/epsilo{n}^{3/2},n^{1/4}/epsilon)$ number of stochastic gradient evaluations, which improves the leading gradient complexity of stochastic gradient-based method SCS $(mathcalO(min1/epsilo{n}^{5/3},n^{2/3}/epsilon)$. It is shown theoretically and experimentally that VCSG can be deployed to improve convergence.

This page was built for publication: A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6361052)