Universal Rates of Empirical Risk Minimization

Thank you for your encouraging comments and insightful suggestions on our paper. Below, we provide detailed responses to your concerns and questions:

1. For the assumption of realizability, as is traditional in the learning theory literature, we first focus on the realizable case to build insights due to its simplicity, and the next natural step is to extend to the non-realizable (agnostic) setting.
2. The algorithm of [Bousquet et al., 2021] is not expressed as a reduction-to-ERM, and it is really unclear whether such a reduction is possible. Their algorithm is expressed in terms of an extension of Littlestone's SOA algorithm allowing for infinite ordinal values of the Littlestone dimension. Moreover, for finite Littlestone dimension, the recent work of [Assos, Attias, Dagan, Daskalakis, & Fishelson, 2023] have found that online learning of Littlestone classes is achievable via a reduction to ERM, but this reduction relies on the relation between the Littlestone dimension and threshold dimension, a relation which breaks down for infinite ordinal Littlestone dimensions, since thresholds on the natural numbers do not admit an infinite Littlestone tree.
3. Thank you for pointing out this typo. The VC dimension of halfspaces is d+1.
4. To get an intuition of the so-called "best-case ERM", consider the following alternative to our Definition 2: for the upper bound, "for every ERM algorithm" $\rightarrow$ "there exists an ERM algorithm"; and for the lower bound, "there exists an ERM algorithm" $\rightarrow$ "for every ERM algorithm". In particular for the realizable case, studying the "best-case ERM" is equivalent to studying the learning rates of general proper learners.

Thank you for your comments on our paper. We are happy to know that you found the problem and our results interesting.

1. For the weakness, we adopted the same universal learning framework of the work of [Bousquet et al., 2021] as well as some related definitions. However, our theory differs a lot from theirs, including but not limited to a different problem setting (we focus on ERM learners), different possible universal rates, new-developed combinatorial structures and plenty of concrete examples for nuanced analysis.
2. For the questions, we appreciate your careful reading. These are very fair comments on grammar, allowing us to enhance the quality of our manuscript. We will go through the paper to correct other potential errors.
3. For the limitation you mentioned, we would like to extend our sincere thanks to you for pointing out areas where our paper could be improved. In our manuscript, we left the universal learnability by ERM an open question for future work, which is not within the scope of this work. One might guess that the universal Glivenko-Cantelli property might be the correct characterization but it turns out that it is not (see Example 5). We suspect such a characterization would be of a significantly different nature compared to the combinatorial structures we find for the characterizing the rates. For instance, note that the set $\mathcal{H}$ of all concepts with finitely-many 1's or finitely-many 0's is learnable by ERM (albeit at arbitrarily slow rates) if $\mathcal{X}$ is countable but not if $\mathcal{X}$ is the real line. These cases won't be distinguished by a discrete combinatorial structure.

Thank you for your insightful comments and positive remarks on our paper.

For the weakness you mentioned, we would like to point out that, in addition to numerous practical works, the interdisciplinary NeurIPS conference also has a rich history of many seminal purely-theoretical works in learning theory.

Here is a response for your question. Mathematically, the agnostic case stands for the situation $\inf_{h\in\mathcal{H}}\text{er}_{P}(h)>0$, which is more practical than realizable case since we usually have no knowledge about the ground-truth model in real-world applications.

Thank you for your insightful feedback and helpful suggestions on our paper. Below, we provide detailed responses to your comments and questions:

1. For the weakness, we will definitely try to improve the writing and add intuitive explanations in the final version.
2. To answer the first question: the notion of a "worst-case ERM" arises because of the non-uniqueness of the minimizer of the 0-1 loss in classification, i.e., there may be many different ways of breaking this tie, and our analysis aims to provide a rate that holds for all such choices. The notion of "random selection" requires first that there is some well-defined measure on the concept class, and such an idea may require a different analysis. In particular for the Example 4 that you pointed out, we actually give out the explicit form of a bad (the worst) ERM algorithm in Appendix B.1 (see Example 11, lines 584-585), which is a deterministic algorithm.
3. For the second question, in particular for the realizable case, studying the ``best-case ERM" is equivalent to studying the optimal rates of general "proper learners", which is a fascinating and important question for future work. We suspect the categorization of rates will somewhat differ from those we establish for the worst-case ERM, analogously to the uniform analysis in [Bousquet, Hanneke, Moran, & Zhivotovskiy, 2020].

Thank you for your insightful feedback on our paper. Below, we provide detailed responses to your questions:

1. ERM learners are quite different from the designed optimal learners constructed in [Bousquet et al., 2021]. Our analysis reveals a completely different characterization of when ERM learners achieve each of the possible rates, and indeed also reveals a $\log(n)/n$ rate is possible for ERM learners, which does not appear as an optimal universal rate. The main difficulty in establishing our theory comes from identifying the correct characterizations, which are different from those characterize the optimal universal rates. As for the proofs, most of them are actually built on the classic PAC theory of the ERM principle, together with arguments connecting combinatorial structures from PAC theory to appropriate infinite structures, such as eluder sequences, star-eluder sequences, and VC-eluder sequences, instead of the techniques in [Bousquet et al., 2021]. Moreover, the universal learning by ERM has many nuanced cases (those constructed examples in the paper) that we have to consider.

2. The notion of a "worst-case ERM" arises because of the non-uniqueness of the minimizer of the 0-1 loss in classification, i.e., there may be many different ways of breaking this tie, and our analysis aims to provide a rate that holds for all such choices. The so-called "worst-case ERM" is actually reflected in our Definition 2. Note that for the upper bound, if the worst-case ERM can achieve some learning rate, then every ERM algorithm can achieve that rate as well. For the lower bound, if there exists an ERM algorithm that fail to achieve some learning rate, then it must be that this is also true for the worst-case ERM. Another way to define the worst-case ERM is presented in Remark 2, i.e., $\sup_{h\in V_{n}(\mathcal{H})}\text{er}_{P}(h)$, which reflects the error rate of the worst-case ERM. We would like to emphasize that the classic PAC theory of ERM also considers the worst-case ERM, one of the equivalences in the Fundamental Theorem of Statistical Learning is stated as "Any ERM rule is a successful PAC learner for $\mathcal{H}$", which is essentially the same as saying "The worst-case ERM rule is a successful PAC learner for $\mathcal{H}$".