# Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent

I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so would require a different metric to comparing the variance of univariate estimators.

I've seen a paper (https://arxiv.org/pdf/1705.07880.pdf) where variance reduction techniques are applied to minimise the trace of the estimator covariance matrix, however there are usually dependencies between gradient components which is not accounted for when taking the trace.

I have heard that it is standard in the optimisation community to compare the relative efficiency of two gradient estimators by using the expected value of the squared norm of the gradient (apparently convergence is dependent on this). Is this correct? If so, can anyone share a reference?

Thanks!

• I don't understand your question. Are you asking how one could compare the two different stochastic gradient oracles? How do you compute "expected value of the squared norm of the gradient" when you don't have the gradient? – Maziar Sanjabi Aug 3 '18 at 17:34
• Yes, I mean how would you compare two gradient oracles. Since I'm from a stats background, I'm not too familiar with the nature of an oracle. I framed this question in terms of estimators. You have an optimisation objective, and evaluate the gradient with respect to a vector of parameters. Since in this context we cannot compute this exactly, we construct an unbiased estimator of the gradient (which is a random vector). My question is around how we can compare these two estimators/oracles. – Ming Xu Aug 8 '18 at 4:26