What really means stochastic in field of signal processing

Question

I met two definitions of word stochastic, the first one (cited from wikipedia Stochastic)

The word stochastic is an adjective in English that describes something that was randomly determined

The explanation of stochastic and deterministic what is used in textbooks really make sense according to definition above. The second definition is

Stochastic means sample by sample

For example SGD - stochastic gradient descent.

This seems to be a little confusing for me. I do not really see any relation between random and step by step.

Do I miss something? Or it is really different meanings for the same word?

Answer 1

Well, getting a bit linguistic, according to the Oxford dictionary:

stochastic (adj.): Having a random probability distribution or pattern that may be analysed statistically but may not be predicted precisely.

So the definition would be the first one (I don't know where you might have found the second one as you didn't put any source about it). Nevertheless, regarding your specific question, SGD is indeed stochastic. It is an iterative method, but this doesn't mean it is not stochastic. It is iterative and stochastic at the same time: the two concepts are not related to each other.

To put it clearer: if something is blue, couldn't it be big? Well... why not? That's exactly what you are asking here. As size isn't related to colour (absurd example that I think can help here), an approximation can be iterative and stochastic (such as SGD): being one thing doesn't mean it can't be the another one too.

Answer 2

I never saw the second definition, but the example of SGD actually fits the first definition. SGD works with a random estimator of the gradient, and just GD is using the real gradient (calculated). To sum up, as far as I know and saw stochastic relates to randomness and not iterative (step by step).

Answer 3

I wanted to chime in a little only because I think I see why someone would have given you the obviously flawed definition of sample-by-sample. Adaptive algorithms like the LMS filter are based on a stochastic gradient update. For LMS in particular, the updates are typically made on a sample-by-sample basis. In other words, you don't try to do a lot of averaging over the samples before making your update (which may be less noisy but results in additional latency to your updates). Stochastic gradients typically involve minimizing the expectation of some cost or error function. This is because the (not squared) error is a random variable, but it typically has a mean of zero. The sample-by-sample updates in an LMS filter lead to a stochastic gradient descent over time. It is stochastic due to the randomness of the error random variable. Otherwise, you could solve the problem deterministically. The LMS algorithm can be shown to move toward the optimal solution (in the least mean square sense). I'm guessing that whoever gave you the second definition was thinking in terms of an algorithm like this. It's still wrong though.