On the Bias-Variance Tradeoff in Stochastic Gradient Methods

We present a general analysis of variance reduced stochastic gradient methods with bias for minimising convex, strongly convex, and non-convex composite objectives. The key to our analysis is a new connection between bias and variance in stochastic gradient estimators, suggesting a new form of bias-variance tradeoff in stochastic optimisation. This connection allows us to provide simple convergence proofs for biased algorithms, extend proximal support to biased algorithms for the first time in the convex setting, and show that biased gradient estimators often offer theoretical advantages over unbiased estimators. We propose two algorithms, B-SAGA and B-SVRG, that incorporate bias into the SAGA and SVRG gradient estimators and analyse them using our framework. Our analysis shows that the bias in the B-SAGA and B-SVRG gradient estimators decreases their mean-squared errors and improves their performance in certain settings.