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?
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.
