A question of quantification

This is about methods for phrasing and think about the scope of some theorems in learning theory. The basic claim is that there are several different ways of quantifying the scope which sound different yet are essentially the same.

1. For all sequences of examples. This is the standard quantification in online learning analysis. Standard theorems would say something like “for all sequences of predictions by experts, the algorithm A will perform almost as well as the best expert.”
2. For all training sets. This is the standard quantification for boosting analysis such as adaboost or multiclass boosting.
   Standard theorems have the form “for all training sets the error rate inequalities … hold”.
3. For all distributions over examples. This is the one that we have been using for reductions analysis. Standard theorem statements have the form “For all distributions over examples, the error rate inequalities … hold”.

It is not quite true that each of these is equivalent. For example, in the online learning setting, quantifying “for all sequences of examples” implies “for all distributions over examples”, but not vice-versa.

However, in the context of either boosting or reductions these are equivalent because the algorithms operate in an element-wise fashion. To see the equivalence, note that:

1. “For any training set” is equivalent to “For any sequence of examples” because a training set is a sequence and vice versa.
2. “For any sequence of examples” is equivalent to “For any distribution over examples” when the theorems are about unconditional example transformations because:
   1. The uniform distribution over a sufficiently long sequence of examples can approximate any distribution we care about arbitrarily well.
   2. If the theorem holds “for all distributions”, it holds for the uniform distribution over the elements in any sequence of examples.

The natural debate here is “how should the theorems be quantified?” It is difficult to answer this debate based upon mathematical grounds because we just showed an equivalence. It is nevertheless important because it strongly influences how we think about algorithms and how easy it is to integrate the knowledge across different theories. Here are the arguments I know.

1. For all sequences of examples.
   1. Learning theory people (at least) are used to thinking about “For all sequences of examples”.
   2. (Applied) Machine learning people are not so familiar with this form of quantification.
   3. When the algorithm is example-conditional such as in online learning, the quantification is more general than “for all distributions”.
2. For all training sets.
   1. This is very simple.
   2. It is misleadingly simple. For example, a version of the adaboost theorem also applies to test sets using the test error rates of the base classifiers. It is fairly common for this to be misunderstood.
3. For all distributions over examples.
   1. Distributions over examples is simply how most people think about learning problems.
   2. “For all distributions over examples” is easily and often confused with “For all distributions over examples accessed by IID draws”. It seems most common to encounter this confusion amongst learning theory folks.

What quantification should be used and why?
(My thanks to Yishay Mansour for clarifying the debate.)