9
$\begingroup$

When sampling the data, either one at a time (as in online learning), or in mini-batches, there exist gradient descent methods which sample with replacement and without replacement.

For Mini-Batch Gradient Descent, why do the methods that sample with replacement work? Why don't we care, for example, that the same data point could be sampled multiple times, or that some data points from the training set may never get sampled at all?

$\endgroup$
1
  • $\begingroup$ Very good question (+1). Asking for a friend: could you provide a reference for mini-batch with replacement? $\endgroup$
    – Jim
    Sep 17, 2020 at 21:14

1 Answer 1

0
$\begingroup$

It works (and we don’t care about sampling points multiple times) because it’s an unbiased estimator of the full gradient.

Gradient distributes over summation (and expectation). The expected value of the gradient of a mini-batch, over all possible mini-batches, is the full gradient.

More details are in Leon Bottou’s paper Stochastic Gradient Descent Tricks. Section 2 talks about SGD as an unbiased estimator, and the same argument holds for the minibatch estimator.

$\endgroup$

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.