<p>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 <em>vector</em> and so would require a different metric to comparing the variance of univariate estimators.</p>

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

<p>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?</p>

<p>Thanks!</p>

CC BY-SA 4.0
2018-08-03T17:34:28.637Z
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
CC BY-SA 4.0
2018-08-08T04:26:45.523Z
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
<reference-request><optimization><machine-learning>
Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent
Ming Xu
# Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent

(Asked by: username_0 on 2018-08-03)

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!

**Tags:** reference-request, optimization, machine-learning

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  

---

## 0 answers

