In local search, gradient descent, one update is very costly in large datasets

https://podcast.ucsd.edu/watch/fa23/cse151a_a00/11

Stochastic: look at just one point at a time

Decomposable Loss Functions

Mini-Batch

Convexity

Positive Semi-Definite