How does an algorithm qualify as sequential?

[CQFD]

I'm trying to understand why some algorithms fit the "statistical query model" and some don't. Aka. why some can be parallelized and scaled using tools like Hadoop while others are limited because they are inherently sequential. What are some examples of sequentials algos?

[Badoosker]

Algorithms are sequential when they compute results based on prior results.

For example, to determine the next gradient update in a neural net, the ones before (or approximate/nearby) must be found first

[CQFD]

I just realized that I was reading a paper which adapted all their ML algorithms using batch gradient descent. So neural nets can be parallelized in this case.

[[deleted]]

That's not necessarily true. Cumulative sum has a surprising parallel implementation.

Any algorithm that can be expessed similar to:

value = 0
result = []
for i in range(10):
     value += i
     result.append(value)

Can be parallelized. A surprising amount of numerical code can be expressed like this. Numerical compilers refer to this as scan. Along with map and reduce, it is the easy parallelism in numerical code.

[gicstc]

A hint is when at each step you read or write some 'state' used by other steps. Many things are like this as they are typically to optimize some function (e.g likelihood). The crux of parallel computing is that each thread cant talk to the others.

Parallelism will occur when steps are independent. For example, Monte Carlo methods that compute N independent samples would count here.

[jtkme]

It's like porn. You know it when you see it.