Suppose there are numbers $\{1, \ldots, 10\}$

You pick one at random, call it $i$

Then $i$ is a Uniform random variable (https://en.wikipedia.org/wiki/Discrete_uniform_distribution), $i \sim U\{1, 10\}$. Then you use it for SGD by taking the gradient of the $i$th loss.

What about minibatch $B$?

In this case you are sampling several numbers from $\{1, \ldots, 10\}$ without replacement. Suppose you are assuming a batch size of $2$.

The probability of sampling the first one is $1/10$, the second one is $1/9$.

Then the random vector $B$ follows some joint distribution. Does anyone know how to model this joint distribution? I feel like this is something super obvious (thinking in the line of products of uniform distribution - not sure how to express this mathematically).


By symmetry, $B$ must be uniformly distributed over the set of subsets of the original dataset whose size is equal to the batch size.

For example, if the batch size is 2, then $B$ can take on any value in the set $$ \{\{1,2\}, \{1,3\}, \{1,4\}, ..., \{8,9\}\} = \{S: S \in \mathcal{P}(\mathcal{D}), \hspace{0.3em} |S| = 2 \}\, $$ where $\mathcal{P}$ is the power set function and $\mathcal{D}$ is the full dataset. Since there's no reason why, say, the batch $\{2, 7\}$ should be more likely than the batch $\{4, 5\}$, we can conclude that $B$ is uniformly distributed over the set of batches above.

  • $\begingroup$ Sure, I added some words to illustrate the argument with a batch size of 2. $\endgroup$ – tddevlin Oct 14 '20 at 18:27

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.