Online learning is in vogue, which means we should expect to see in the near future:
- Online boosting.
- Online decision trees.
- Online SVMs. (actually, we’ve already seen)
- Online deep learning.
- Online parallel learning.
There are three fundamental drivers of this trend.
- Increasing size of datasets makes online algorithms attractive.
- Online learning can simply be more efficient than batch learning. Here is a picture from a class on online learning:
The point of this picture is that even in 3 dimensions and even with linear constraints, finding the minima of a set in an online fashion can be typically faster than finding the minima in a batch fashion. To see this, note that there is a minimal number of gradient updates (i.e. 2) required in order to reach the minima in the typical case. Given this, it’s best to do these updates as quickly as possible, which implies doing the first update online (i.e. before seeing all the examples) is preferred. Note that this is the simplest possible setting—making the constraints nonlinear, increasing the dimensionality, introducing noise, etc… all make online learning preferred.
- Online learning is conceptually harder, and hence more researchable. The essential difficulty is that there is no well defined static global optima, as exists for many other optimization-based learning algorithms. Grappling with this lack is of critical importance.