Is stochastic gradient descent biased?

In the paper Mutual Information Neural Estimation, the authors derive the following gradient for the network $$\nabla_\theta\mathcal V(\theta)=\mathbb E\left[\nabla_\theta T_\theta\right]-{\mathbb E\left[e^{T_\theta}\nabla_\theta T_\theta\right]\over \mathbb E\left[e^{T_\theta}\right]}$$ and say it's biased because, in the second term, the expectations are over the sample of a minibatch.

However, based on my knowledge, SGD is high variance indeed but it shouldn't introduce any bias. Is my previous understanding wrong?

Furthermore, the authors say that by replacing the expectation in the denominator with an exponential moving average, the bias can be reduced. Why does that make sense?

1 Answer

For a typical loss function $L = E_{x_i \sim \text{D}}[f(x_i)]$ and true gradient $\nabla L = E[\nabla f(x_i)]$, the expectation of the SGD gradient is $E[\nabla f(x')]$ where $x'$ is the datapoint in our batch of size this is 1. This is clearly unbiased.

The loss function in the paper takes the form $L = \log E[e^{f(x)}]$ and has the gradient $$\nabla L = \frac{1}{E[e^{f(x)}]} E[\nabla e^{f(x)}] = \frac{E[\nabla f(x) e^{f(x)}]}{E[e^{f(x)}]}$$

Note that the SGD gradient $\frac{\nabla f(x') e^{f(x')}}{e^{f(x')}} = \nabla f(x')$ is biased.

However, what we we only "did SGD" for the numerator and computed the exact expectation for the denominator? This pseudo-SGD gradient $\frac{\nabla f(x') e^{f(x')}}{E[e^{f(x)}]}$ is indeed unbiased.

Although it is too expensive to recompute the denominator at every SGD step, if we assume that the parameters of $f$ do not change too rapidly (and therefore $f(x)$ also does not change rapidly), one way to estimate the denominator is to use an exponentially weighted moving average. This would lead us to a relatively unbiased estimate.

• Hi, first I'm so sorry for responding so late. I'm still quite confused about your answer. Why did you say ${\nabla f(x')e^{f(x')}\over e^{f(x')}}=\nabla f(x')$ is biased? – Maybe Mar 17 '19 at 13:10
• @Sherwin Chen consider $x$ to be uniform -1 to 1, $f(x) = \log(x+\theta)$, where $\theta >1$. Then the unbiased gradient is $1/\theta$. The sgd gradient has an expectation $E[1/(\theta+x)]$ which is different! For $\theta=2$ the expectation is about 0.549 – shimao Mar 17 '19 at 15:10
• Thank you, @shimao. I see your point. It's Jensen's inequality! – Maybe Mar 18 '19 at 0:41
• Does this mean that any time $\log(f(x))$ appears in a network trained with SGD, the gradient estimate will be biased? Because that seems really common but I haven't heard of this issue before. – zplizzi Sep 27 '19 at 19:58
• Ahh, I see. It's only biased if the loss function has the form $\log E[f(x)]$ – zplizzi Sep 27 '19 at 20:04