why do offline learning algorithms perform better than their online learning counterparts? (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?
 A: 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.
