Is stochastic gradient descent pseudo-stochastic?

Question

I know that stochastic gradient descent randomly chooses 1 sample to update the weights. An epoch is defined as using all $N$ samples. So with SGD, for each epoch, we update the weights $N$ times.

My confusion is doesn't this make it so you have to go through all $N$ samples before you can see the same sample twice? Doesn't that effectively make it pseudo-random/stochastic? If it was entirely random, then there would be a possibility of seeing the same sample more than once before going through all $N$ samples.

Answer 1

Exhausting all $N$ samples before being able to repeat a sample means that the process is not independent. However, the process is still stochastic.

Consider a shuffled deck of cards. You look at the top card and see $\mathsf{A}\spadesuit$ (Ace of Spades), and set it aside. You'll never see another $\mathsf{A}\spadesuit$ in the whole deck. However, you don't know anything about the ordering of the remaining 51 cards, because the deck is shuffled. In this sense, the remainder of the deck still has a random order. The next card could be a $\mathsf{2}\color{red}{\heartsuit}$ or $\mathsf{J}\clubsuit$. You don't know for sure; all you do know is that the next card isn't the Ace of Spades, because you've put the only $\mathsf{A}\spadesuit$ face-up somewhere else.

In the scenario you outline, you're suggesting looking at the top card and then shuffling it into the deck again. This implies that the probability of seeing the $\mathsf{A}\spadesuit$ is independent of the previously-observed cards. Independence of events is an important attribute in probability theory, but it is not required to define a random process.

You might wonder why a person would want to construct mini-batches using the non-independent strategy. That question is answered here: Why do neural network researchers care about epochs?