2
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ I don't think this answers my question? It's really a matter of the variance of the gradients estimates and which approach leads to less noisy estimates in a mini-batch. $\endgroup$
    – becko
    May 4 at 12:33
  • $\begingroup$ THanks for the reference though! $\endgroup$
    – becko
    May 4 at 12:35
  • $\begingroup$ @becko in batch gradient descent you just use weighted average in place of average. $\endgroup$
    – Tim
    May 4 at 12:48
  • $\begingroup$ Can you be explicit in how the weighted average is taken? This is the central point of my question. $\endgroup$
    – becko
    May 4 at 12:51
  • $\begingroup$ For example, suppose you do $\frac{\sum_{i \in \mathcal{B}} w_i f'_i}{\sum_{i \in \mathcal{B}} w_i}$, where $\mathcal{B}$ denotes the mini-batch. Then this is not an unbiased estimate of the gradient in the full data. $\endgroup$
    – becko
    May 4 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.