What is the probability distribution of a minibatch of data?

Question

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

Answer 1

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.