# How to handle weighted examples in stochastic gradient descent (with mini-batches)?

Suppose I have $$M$$ data points $$x_i$$ and associated weights $$w_i > 0$$. I want to optimize a function,

$$F(\theta) = \frac{1}{M}\sum_i w_i f(x_i;\theta)$$

in the parameters $$\theta$$. I will assume for simplicity that $$\sum_i w_i = M$$, the number of data points.

Since I have a huge dataset, I want to optimize $$F(\theta)$$ using stochastic-gradient descent, with minibatches. Now, I have not seen a lot of papers handling weights $$w_i$$ in this context in practice. One usually assumes that the data constitutes a uniform sample of the underlying distribution.

How should one handle the weights $$w_i$$?

A possibility is to obtain the mini-batches by sampling from the data points indices $$i$$ with weights $$\propto w_i$$. But this seems inefficient? Another possibility is to sample the minibatch indices $$i$$ uniformly as usual, and then treat the data points as a pair $$(x_i, w_i)$$ and re-define the objective function as

$$F(\theta) = \frac{1}{M}\sum_i f(x_i, w_i; \theta)$$

where $$f(x_i, w_i; \theta) = w_i f(x_i; \theta)$$. This is just a notational change but it means that one can do ordinary SGD.

What's the best way to handle the weights here? Is there some literature on this topic?

Thanks.

Gradient descent is about following the derivatives (gradients). Recall that the derivative rule for calculating the derivative of a function $$f$$ times a constant $$c$$ is just

$$\frac{\partial}{\partial x} c f(x) = c f'(x)$$

So you only need to multiply the gradient by the weight.

The weighted average is equivalent to using a regular average but with different observations repeated a number of times that is proportional to the sampling weights. In batch gradient descent, you would use weighted average instead of regular average, so it would be the same as if you used regular batch gradient descent, just the batches may vary in size because of using different weights. The changes in size are not a problem because we are averaging the result.

That said, there is interesting empirical research by Byrd and Lipton (2018) showing that neural networks trained with SGD learn to ignore the sampling weights if they are trained long enough. It is an open question when exactly it happens, but worth keeping in mind that it can happen.

• @becko is an unweighted average over the batch an unbiased estimate for full data? When using batches, each update is given the batch. If you want to update given all data, use all data. Using weights is equivalent to repeating the observations number of times proportional to the weight. So it's like using standard batch gradient descent with varying batch sizes due to the weights if they are not uniform.
– Tim
Commented May 4, 2022 at 13:11
• @becko is exactly the same as usual gradient descent, but you replace the "$\tfrac{1}{M} \sum_{i=1}^M$" part with weighted average, that's all.
– Tim
Commented May 4, 2022 at 17:16
• @becko I'm not sure what you mean. An unweighted average is just a special case of a weighted average. If you consider sampling according to the weights it is equivalent to using the weights in the loss function.
– Tim
Commented May 4, 2022 at 21:26
• @becko if weights are proportional to frequencies, the weighted average is the same as you repeated each row the number of times proportional to the weight. So if weights tell you how frequent the value is, it is exactly the same as the standard average. So if you consider sampling proportionally to weights it is the same as using weighted average.
– Tim
Commented May 5, 2022 at 12:58
• @becko there is weighted variance as well, but the variance is not used by the gradient descent algorithm when doing the update. By weighted average, I mean weighted average over batch when doing the update in place of regular average in non-weighted case.
– Tim
Commented May 5, 2022 at 13:04