3
$\begingroup$

(I'm assuming infinite data, finite time for this comparison)

I was wondering why it is exactly that online learning algorithms usually perform more poorly than their offline counter-parts.. Does anyone have a good intuitions and/or theoretical reason for this?

Why does being able to look at the same sample multiple times allow for a better learning algorithm?

For many general algorithms it's very obvious why offline algorithms are better. Simply because the more data you have, the more informed of a decision you can make.

But for machine learning we are trying to learn a distribution where the more data points you have the better you will pick the distribution.

But we may pick poor decisions in the beginning that will have long-lasting consequences on our optimization.. Maybe this is the trade-off?

$\endgroup$
  • $\begingroup$ It doesn't say that; it simply tells you to use as much data as you can in your allotted time. If you had an online algorithm that usds the same amount of data in the same amount of time as an offline algorithm they could have the same performance. $\endgroup$ – Emre Nov 24 '14 at 2:18
  • $\begingroup$ I would think an online algorithm would always use more data, since an online algorithm is always looking at new data while an offline algorithm is sometimes looking at existing data. $\endgroup$ – anthonybell Nov 24 '14 at 2:52
  • $\begingroup$ Not necessarily. Not all processes generate "new" data that needs to be processed. People use online algorithms even when the "obvious" candidate is an offline algorithm because it is not feasible to process it all at once. You are comparing apples to oranges, and you've dropped the quote so the question has changed so I'm bowing out. $\endgroup$ – Emre Nov 24 '14 at 2:56
  • $\begingroup$ Thanks for your comments. I removed the comment about the article so people address the question in the title. $\endgroup$ – anthonybell Nov 24 '14 at 2:59
  • 1
    $\begingroup$ It will be great to have a statistical answer here, but are you really surprised? I imagine it's related to the reason out of sample performance is lower than in sample performance. $\endgroup$ – shadowtalker Nov 24 '14 at 13:38
1
$\begingroup$

One intuitive explanation could be that the search space is much bigger when you allow to look at points as often as you want. The bigger the search space, the lower loss you can achieve.

Take a look at an online implementation of kSVMs and especially at the kernel perceptron algorithm (Aizerman et al., 1964). As you can see, the support vectors can be added only once, and therefore, the set of support vectors will be highly dependent on the order of arrival of the data.

Likewise, with online decision trees (or random forests), in some implementations (see per example the one below), points are accumulated into leaves, until leaves contains enough point and a (high enough) gain can be achieved by splitting this leaf. On the other hand, training a decision tree on a complete dataset and "choosing the best split" will intuitively provide a better fit.


Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009, September). On-line random forests. In Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference on (pp. 1393-1400). IEEE.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.