Universal Rates of Empirical Risk Minimization

Authors: steve  hanneke
mingyue  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 22:33:01

Abstract: The well-known $\textit{empirical risk minimization}$ (ERM) principle is the basis of many widely used machine learning algorithms, and plays an essential role in the classical PAC theory. A common description of a learning algorithm's performance is its so-called “learning curve”, that is, the decay of the expected error as a function of the input sample size. As the PAC model fails to explain the behavior of learning curves, recent research has explored an alternative universal learning model and has ultimately revealed a distinction between optimal universal and uniform learning rates (Bousquet et al., 2021). However, a basic understanding of such differences with a particular focus on the ERM principle has yet to be developed. 
  
  In this paper, we consider the problem of universal learning by ERM in the realizable case and study the possible universal rates. Our main result is a fundamental $\textit{tetrachotomy}$: there are only four possible universal learning rates by ERM, namely, the learning curves of any concept class learnable by ERM decay either at $e^{-n}$, $1/n$, $\log{(n)}/n$, or arbitrarily slow rates. Moreover, we provide a complete characterization of which concept classes fall into each of these categories, via new complexity structures. We also develop new combinatorial dimensions which supply sharp asymptotically-valid constant factors for these rates, whenever possible.

Main paper: 
 introduction: 
 The classical statistical learning theory mainly focuses on the celebrated PAC (Probably Approximately Correct) model (Vapnik and Chervonenkis, 1974; Valiant, 1984) with emphasis on supervised learning. A particular setting therein, called the realizable case, has been extensively studied. Complemented by the "no-free-lunch" theorem (Antos and Lugosi, 1996) , the PAC framework, which adopts a minimax perspective, can only explain the best worst-case learning rate by a learning algorithm over all realizable distributions. Such learning rates are thus also called the uniform rates. However, the uniform rates can only capture the upper envelope of all learning curves, and are too coarse to explain practical machine learning performance. This is because real-world data is rarely worst-case, and the data source is typically fixed in a given learning scenario. Indeed, Cohn and Tesauro (1990, 1992) observed from experiments that practical learning rates can be much faster than is predicted by PAC theory. Moreover, many theoretical works (Schuurmans, 1997; Koltchinskii and Beznosova, 2005; Audibert and Tsybakov, 2007, etc.) were able to prove faster-than-uniform rates for certain learning problems, though requiring additional modelling assumptions. To distinguish from the uniform rates, these rates are named the universal rates and was formalized recently by Bousquet et al. (2021) via a distribution-dependent framework. Unlike the simple dichotomy of the optimal uniform rates: every concept class H has a uniform rate being either linear VC(H)/n or "bounded away from zero", the optimal universal rates are captured by a trichotomy: every concept class H has a universal rate being either exponential, linear or arbitrarily slow (see Thm.1.6 Bousquet et al., 2021) .In supervised learning, a family of successful learners called the empirical risk minimization (ERM) consist of all learning algorithms that output a sample-consistent classifier. In other words, an ERM algorithm is any learning rule, which outputs a concept in H that minimizes the empirical error (see Appendix A for a formal definition). For notation simplicity, we first introduce Definition 1 (Version space, Mitchell, 1977) . Let H be a concept class and S n := {(x i , y i )} n i=1 be a dataset, the version space induced by S n , denoted by V Sn (H) (or V n (H) for short), is defined as V Sn (H) := {h ∈ H : h(x i ) = y i , ∀i ∈ [n]}. Now given labeled samples S n := {(x i , y i )} n i=1 , an ERM algorithm is any learning algorithm that outputs a concept in the sample-induced version space, that is, a sequence of universally measurable functions A n : S n → ĥn ∈ V Sn (H), n ∈ N. Throughout this paper, we will simply denote an ERM algorithm by its output predictors { ĥn } n∈N .It is well-known that the ERM principle plays an important role in understanding general uniform learnability: a concept class is uniformly learnable if and only if it can be learned by ERM. However, while the optimal VC(H)/n rate is achievable by some improper learner (Hanneke, 2016a) , ERM algorithms can at best achieve a uniform rate of (VC(H)/n) log (n/VC(H)). Moreover, such a gap has been shown to be unavoidable in general (Auer and Ortner, 2007) , which leaves a challenging question to study: what are the sufficient and necessary conditions on H for the entire family of ERM algorithms to achieve the optimal error? Indeed, many subsequent works have devoted to improving the logarithmic factor in specific scenarios. The work of Giné and Koltchinskii (2006) refined the bound by replacing log (n/VC(H)) with log (θ(VC(H)/n)), where θ(•) is called the disagreement coefficient. Based on this, Hanneke and Yang (2015) proposed a new data-dependent bound with log (n 1:n /VC(H)), where n1:n is a quantity related to the version space compression set size (a.k.a. the empirical teaching dimension). As a milestone, the work of Hanneke (2016b) proved an upper bound (VC(H)/n) log (s H /VC(H)) and a lower bound (VC(H) + log (s H ))/n, where s H is called the star number of H (see Definition 4 in Section 2). Though not quite matching, these two bounds together yield an optimal linear rate when s H < ∞. Thereafter, the uniform rates by ERM can be described as a trichotomy, namely, every concept class H has a uniform rate by ERM being exactly one of the following: 1/n, log (n)/n and "bounded away from zero".From a practical perspective, many ERM-based algorithms are designed and are widely applied in different areas of machine learning, such as the logistic regression and SVM, the CAL algorithm in active learning, the gradient descent (GD) algorithm in deep learning. Since the worst-case nature of the PAC model is too pessimistic to reflect the practice of machine learning, understanding the distribution-dependent performance of ERM algorithms is of great significance. However, unlike that a distinction between the optimal uniform and universal rates has been fully understood, how fast universal learning can outperform uniform learning in particular by ERM remains unclear. Furthermore, we are lacking a complete theory to the characterization of the universal rates by ERM, though certain specific scenarios that admit faster rates by ERM have been discovered (Schuurmans, 1997; van Handel, 2013) . In this paper, we aim to answer the following fundamental question: Question 1. Given a concept class H, what are the possible rates at which H can be universally learned by ERM?We start with some basic preliminaries of this paper. We consider an instance space X and a concept class H ⊆ {0, 1} X . Given a probability distribution P on X × {0, 1}, the error rate of a classifier h : X → {0, 1} is defined as er P (h) := P ((x, y) ∈ X × {0, 1} : h(x) ̸ = y). A distribution P is called realizable with respect to H, denoted by P ∈ RE(H), if inf h∈H er P (h) = 0. Note that in this definition, h * satisfying er P (h * ) = inf h∈H er P (h) is called the target concept of the learning problem, and is not necessary in H. We may also say that P is a realizable distribution centered at h * . Given an integer n, we denote by S n := {(x i , y i )} n i=1 ∼ P n a i.i.d. P -distributed dataset. In the universal learning framework, the performance of a learning algorithm is commonly measured by its learning curve (Bousquet et al., 2021; Hanneke et al., 2022; Bousquet et al., 2023) , that is, the decay of the expected error rate E[er P ( ĥn )] as a function of sample size n. With these settings settled, we are now able to formalize the problem of universal learning by ERM. Definition 2 (Universal learning by ERM). Let H be a concept class, and R(n) → 0 be a rate function. We say • H is universally learnable at rate R by ERM, if for every distribution P ∈ RE(H), there exist parameters C, c > 0 such that for every ERM algorithm, E[er P ( ĥn )] ≤ CR(cn), for all n ∈ N.• H is not universally learnable at rate faster than R by ERM, if there exists a distribution P ∈ RE(H) and parameters C, c > 0 such that there exists an ERM algorithm satisfying E[er P ( ĥn )] ≥ CR(cn), for infinitely many n ∈ N. • H is universally learnable with exact rate R by ERM, if H is universally learnable at rate R by ERM, and is not universally learnable at rate faster than R by ERM. • H requires arbitrarily slow rates to be universally learned by ERM, if for every rate function R(n) → 0, H is not universally learnable at rate faster than R by ERM. Remark 1. The above definition inherits the structure of the definition to the optimal universal learning (Definition 1. 4 Bousquet et al., 2021) . Here, we are actually considering the "worst-case" ERM algorithm, which is consistent with the PAC theory. A crucial difference between this definition and the PAC one is that here the constants C, c > 0 are allowed to depend on the distribution P . In other words, the PAC model can be defined similarly, but requires uniform constants C, c > 0. Consequently, H is universally learnbale at rate R by ERM if it is PAC learnable at rate R by ERM. Remark 2. It is not hard to see that the error rate achieved by any ERM algorithm, given S n ∼ P n as input, is at most sup h∈V Sn (H) er P (h). Furthermore, for any distribution P ∈ RE(H), there exist ERM algorithms obtaining error rates arbitrarily close to this value. Hence, to obtain upper bounds of the universal rates by ERM, it requires us to bound the random variable sup h∈V Sn (H) er P (h), where a common technique is to bound P(sup h∈V Sn (H) er P (h) > ϵ) = P(∃h ∈ V Sn (H) : er P (h) > ϵ). To obtain lower bounds, it requires us to construct specific "hard" distributions.In order to develop some initial intuition for what universal learning rates are possible for ERM, we first introduce several basic examples that illustrate the possibilities in the following Section 1.2. To convince the reader, we provide direct analysis (without using our characterization in Section 1.2) for those examples (see details in Appendix B.1). Example 1 (e -n learning rate). Any finite class H is universally learnable at exponential rate (Schuurmans, 1997) . Indeed, according to their analysis, such exponential rates can also be achieved by any ERM algorithm. Example 2 (1/n learning rate). Let H thresh,N := {h t : t ∈ N} be the class of all threshold classifiers on natural numbers, where h t (x) := 1(x ≥ t), for all x ∈ N. H thresh,N is universally learnable at exponential rate since this class does not have an infinite Littlestone tree (Bousquet et al., 2021) . However, ERM algorithms cannot guarantee such exponential rates but at best linear rates, when encountering certain realizable distributions centered at the target concept h all-0's , which is the function that labels zero everywhere (see Appendix A). Example 3 (log (n)/n learning rate). Let X = N and H singleton,N := {h t : t ∈ X } be the class of all singletons on X , where h t (x) := 1(x = t), for all x ∈ N. It is clear that VC(H singleton,N ) = 1. Note that H singleton,N is universally learnable at exponential rate since it has finite Littlestone dimension LD(H singleton,N ) = 1. However, the exact universal rate by ERM is instead log (n)/n. This is because H singleton,N admits certain realizable distributions centered at h all-0's . Indeed, it is an example where the universal rate by ERM matches the uniform rate, up to a distribution-dependent constant. Example 4 (Arbitrarily slow learning rate). Let X = i∈N X i be the disjoint union of finite setswith |X i | = 2 i , for all i ∈ N. For each i ∈ N, let H i := {h S := 1 S : S ⊆ X i , |S| ≥ 2 i-1 } and consider the concept class H = i∈N H i .H is universally learnable at exponential rate since it does not have an infinite Littlestone tree. However, a bad ERM algorithm can perform arbitrarily slowly. Example 5 (Not Glivenko-Cantelli but learnable by ERM). Let X = [0, 1], H := {1 S : S ⊂ X , |S| < ∞}, and P be the uniform (Lebesgue) distribution on [0, 1]. H is universally learnable at exponential rate (no infinite Littlestone tree). Moreover, H is not a universal Glivenko-Cantelli class for P (van Handel, 2013), but is still universally learnable by ERM. However, if we consider the class H ∪ {h all-1's }, which is still not a universal Glivenko-Cantelli class for P , but no longer universally learnable by any ERM algorithm since er P ( ĥn ) = 1 regardless of the sample size.The above examples indicate that the cases of universal learning by ERM do not match the uniform learning, but contains at least five possible cases: every nontrivial concept class H is either universally learnable at exponential rate (but not faster), or is universally learnable at linear rate (but not faster), or is universally learnable at slightly slower than linear rate log (n)/n (but not faster), or is universally learnable but necessarily with arbitrarily slow rates, or is not universally learnable at all. Throughout this paper, we only consider the case where the given concept class is universally learnable by ERM. We leave it an open question whether there exists a nice characterization that determines the universal learnability by ERM.In this section, we summarize the main results of this paper. The examples in Section 1.1 reveal that there are at least four possible universal rates by ERM. Interestingly, we find that these are also the only possibilities. The following two theorems consist of the main results of this work. In particular, Theorem 1 gives out a complete answer to Question 1. It expresses a fundamental tetrachotomy: there are exactly four possibilities for the universal learning rates by ERM: being either exponential, or linear, or log (n)/n, or arbitrarily slow rates. Moreover, Theorem 2 specifies the answer by pointing out for what realizable distributions (targets), those universal rates are sharp.Theorem 1 (Universal rates for ERM). For every class H with |H| ≥ 3, the following hold: Remark 3. The formal definition of the star-eluder sequence can be found in Section 2. Unlike the separation between exact e -n and 1/n rates is determined by the cardinality of the class, and the separation between exact log (n)/n and arbitrarily slow rates is determined by the VC dimension of the class, whether there exists a simple combinatorial quantity that determines the separation between exact 1/n and log (n)/n rates is unclear and might be an interesting direction for future work. We thought that it is likely the star number s H (Definition 4) is the correct characterization here, but it turns out not unfortunately (see details in Section 4 and Appendix B.3).Based on Theorem 1, a distinction between the performance of ERM algorithms and the optimal universal learning algorithms can be revealed, which we present in the following Furthermore, the distinction between the universal rates and the uniform rates by ERM can also be fully captured, and are depicted schematically in Figure 1 as an analogy to the Fig. 4 of Bousquet et al. (2021) . Besides the examples in Section 1.1, we also need the following additional example concerning the Littlestone dimension to appear in the diagram.Example 6 (log (n)/n learning rate and unbounded Littlestone dimension). We consider here the class of two-dimensional halfspaces, that is,X := R 2 and H halfspaces,R := {1(w • x + b ≥ 0) : w ∈ R 2 , b ∈ R}.It is a classical fact that for any integer d, the class of halfspaces on R d has a finte VC dimension d, but has an infinite Littlestone tree, and thus having unbounded Littlestone dimension (Shalev-Shwartz and Ben-David, 2014) . Finally, to show that this class is universally learnable by ERM at exact log (n)/n rate, we simply consider the subspace S 1 ⊂ X , this is indeed an infinite star set of H halfspaces,R centered at h all-0's and thus an infinite star-eluder sequence.As a complement to Theorem 1, the following Theorem 2 gives out target-specified universal rates. Figure 1 : A venn diagram depicting the tetrachotomy of the universal rates by ERM and its relation with the uniform rates characterized by the VC dimension and the star number.Theorem 2 (Target specified universal rates). For every class H with |H| ≥ 3, and a target concept h * , the following hold: All detailed proofs appear in Appendix D. We also provide a brief overview of the main idea of each proof as well as some related concepts in Section 2.An additional part of this work presents a fine-grained analysis (Bousquet et al., 2023 ) of the universal rates by ERM, which complements the coarse rates used in Theorem 1. Concretely, we provide a characterization of sharp distribution-free constant factors of the ERM universal rates, whenever possible. The characterization is based on two newly-developed combinatorial dimensions, called the star-eluder dimension (or SE dimension) and the VC-eluder dimension (or VCE dimension) (Definition 9). We say "whenever possible" because distribution-free constants are unavailable for certain cases (Remark 16). Such a characterization can also be considered as a refinement to the classical PAC theory, in a sense that it is sometimes better but only asymptotically-valid. Due to space limitation, we defer the definition of fine-grained rates and related results to Appendix C.PAC learning by ERM. The performance of consistent learning rules (including the ERM algorithm) in the PAC (distribution-free) framework has been extensively studied. For VC classes, Blumer et al. (1989) gave out a log (n)/n upper bound of the uniform learning rate. Despite the well-known equivalence between uniform learnability and uniform learnability by the ERM principle (Vapnik and Chervonenkis, 1971) , the best upper bounds for general ERM algorithms differ from the optimal sample complexity by an unavoidable logarithmic factor (Auer and Ortner, 2007) . By analyzing the disagreement coefficient of the version space, the work of Giné and Koltchinskii (2006) ; Hanneke (2009) refined the logarithmic factor in certain scenarios. Furthermore, not only being a relevant measure in the context of active learning (Cohn et al., 1994; El-Yaniv and Wiener, 2012; Hanneke, 2011 Hanneke, , 2014)) , the region of disagreement of the version space was found out to have an interpretation of sample compression scheme with its size known as the version space compression set size (Wiener et al., 2015; Hanneke and Yang, 2015) . Based on this, the label complexity of the CAL algorithm can be converted into a bound on the error rates of all consistent PAC learners (Hanneke, 2016b) . Finally, Hanneke and Yang (2015) ; Hanneke (2016b) introduced a simple combinatorial quantity named the star number, and guaranteed that a concept class with finite star number can be uniformly learned at linear rate.Universal Learning. Observed from empirical experiments, the actual learning rates on real-world data can be much faster than the one described by the PAC theory (Cohn and Tesauro, 1990, 1992) . The work of Benedek and Itai (1988) considered a setting lies in between the PAC setting and the universal setting called nonuniform learning, in which the learning rate may depend on the target concept but still uniform over the marginal distributions. After that, Schuurmans (1997) studied classes of concept chains and revealed a distinction between exponential and linear rates along with a theoretical guarantee. Later, more improved learning rates have been obtained for various practical learning algorithms such as stochastic gradient decent and kernel methods (Koltchinskii and Beznosova, 2005; Audibert and Tsybakov, 2007; Pillaud-Vivien et al., 2018, etc.) . Additionally, van Handel (2013) studied the uniform convergence property from a universal perspective, and proposed the universal Glivenko-Cantelli property. Until very recently, the universal (distribution-dependent) learning framework was formalized by Bousquet et al. (2021) , in which a complete theory of the (optimal) universal learnability was obtained as well. After that, Bousquet et al. (2023) carried out a fine-grained analysis on the "distribution-free tail" of the universal learning curves by characterizing the optimal constant factor. As generalizations, Kalavasis et al. (2022) ; Hanneke et al. (2023) studied the universal rates for multiclass classification, and Hanneke et al. (2022) studied the universal learning rates under an interactive learning setting. 
technical overview: 
 In this section, we discuss some technical aspects in the derivation of our main results in Section 1.2. Our analysis to the universal learning rates by ERM is based on three new types of complexity structures named the eluder sequence, the star-eluder sequence and the VC-eluder sequence. More details can be found in Sections 3-4 and all technical proofs are deferred to Appendix D. H) , which implies that any concept class with finite star number and finite Littlestone dimension must be a finite class.Before proceeding to the next two definitions, we define a sequence of integers {n k } k∈N as n 1 = 0, n k := k 2 for all k > 1, which satisfies n k+1 -n k = k for all k ∈ N. Definition 6 (Star-eluder sequence). Let H be a concept class and h be a classifier. We say that H has an infinite star-eluder sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .} centered at h , if it is realizable and for every integer k ≥ 1, {x n k +1 , . . . , x n k +k } is a star set of V n k (H) centered at h. Definition 7 (VC-eluder sequence). Let H be a concept class and h be a classifier. We say that H has an infinite VC-eluder sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .} centered at h , if it is realizable and labelled by h, and for every integer k ≥ 1, {x n k +1 , . . . , x n k +k } is a shattered set of V n k (H). Remark 6. In the definitions of eluder sequence and VC-eluder sequence, "{(x 1 , y 1 ), (x 2 , y 2 ), . . .} centered at h" simply means the sequence is labelled by h. However, the words "centered at" in the definition of star-eluder sequence is more meaningful. In this paper, we give them a uniform name in order to make Theorem 2 look consistent. Remark 7. An infinite star-eluder (VC-eluder) sequence requires the version space to keep on having star (shattered) sets with infinitely increasing sizes. If the size cannot grow infinitely, the largest possible size of the star (shattered) set is called the star-eluder (VC-eluder) dimension (Definition 9), which plays an important role in our fine-grained analysis (Appendix C). To distinguish the notion of star-eluder (VC-eluder) sequence here from the d-star-eluder (d-VC-eluder) sequence defined in Appendix C, we may call the construction in Definition 6 an infinite strong star-eluder sequence, and the construction in Definition 7 an infinite strong VC-eluder sequence.Proof Sketch of Theorem 1 and 2. The proof of Theorem 1 is devided into two parts (Section 3 and Section 4). Roughly speaking, for each equivalence therein, we first characterize the exact universal rates by ERM via the three aforementioned sequences (see Theorems 3-6 in Section 3). We have to prove a lower bound together with an upper bound for the sufficiency since we are showing the "exact" universal rates. The lower bound is established by constructing a realizable distribution on the existent infinite sequence, and the derivation of upper bound is strongly related to the classical PAC theory. To prove the necessity, we will use the method of contradiction. Then in Section 4, we establish equivalent characterizations via those well-known complexity measures, whenever possible. Theorem 2 is an associated target-dependent version, and is directly proved by those corresponding lemmas in Section 3. The complete proof structure for Theorem 1 can be summarized as follow:For the first bullet, we start by proving that H is universally learnable with exact rate e -n if and only if H does not have an infinite eluder sequence (Theorem 3), and then we extend the equivalence by showing that H does not have an infinite eluder sequence if and only if H is a finite class (Lemma 8). For the second bullet, we prove that H is universally learnable with exact rate 1/n if and only if H has an infinite eluder sequence but does not have an infinite star-eluder sequence (Theorem 4). Then the desired equivalence follows immediately from the first bullet. For the third bullet, we prove that H is universally learnable with exact rate log (n)/n if and only if H has an infinite star-eluder sequence but does not have an infinite VC-eluder sequence (Theorem 5). The desired equivalence comes in conjunction with the claim that H has an infinite VC-eluder sequence if and only if H has infinite VC dimension (Lemma 9). Finally, for the last bullet, it suffices to prove that H requires at least arbitrarily slow rates to be universally learned by ERM if and only if H has an infinite VC-eluder sequence (Theorem 6).Example 15 (Infinite VC-eluder sequence but no infinite Littlestone tree). Let X := k∈N X k be the disjoint union of finite sets with |X k | = k and H := k≥1 H k , where H k := {1 S : S ⊆ X k }. We have the following hold:1. H does not have an infinite Littlestone tree since for any root x ∈ X , the subclass {h ∈ H : h(x) = 1} is finite, and thus the corresponding subtree of the Littlestone tree must be finite. 2. H has an infinite VC-eluder sequence. Indeed, any sequence {(x 1 , 0), (x 2 , 0), (x 3 , 0), . . .} with x n k +1 , . . . , x n k +k ∈ X k for all k ≥ 1, is an infinite VC-eluder sequence. Furthermore, it has been argued that VC(H) = ∞ (Ex.2.3 Bousquet et al., 2021) , which is consistent with our Lemma 9 in Section 4. Example 16 (Infinite VC-eluder sequence but no infinite VCL tree). Let X 1 and H 1 be defined in Example 15, let X 2 = R and H 2 = H thresh,R be the class of all threshold classifiers on R. Note that H 2 has an infinite Littlestone tree. Now we define X := X 1 ∪ X 2 and H := H 1 ∪ H 2 , and have the following hold:1. H does not have an infinite VCL tree since for any fixed root x ∈ X , the subclass {h ∈ H : h(x) = 1} has a bounded VC dimension, and thus the corresponding subtree of the VCL-tree must be finite. 
exact universal rates: 
 Sections 3 and 4 of this paper are devoted to the proof ideas of Theorems 1 and 2 with further details. In this section, we give a complete characterization of the four possible exact universal rates by ERM (e -n , 1/n, log (n)/n and arbitrarily slow rates) via the existence/nonexistence of the three combinatorial sequences defined in Section 2. For each of the following "if and only if" results (Theorems 3-6), we are required to prove both the sufficiency and the necessity. The sufficiency consists of both an upper bound and a lower bound since we are proving the exact universal rates. The necessity also follows simply by the method of contradiction, given the rates are exact. All technical proofs are deferred to Appendix D.1.Theorem 3. H is universally learnable by ERM with exact rate e -n if and only if H does not have an infinite eluder sequence.The lower bound for sufficiency is straightforward and was established by Schuurmans (1997) .Lemma 1 (e -n lower bound). Given a concept class H, for any learning algorithm ĥn , there exists a realizable distribution P with respect to H such that E[er P ( ĥn )] ≥ 2 -(n+2) for infinitely many n, which implies that H is not universally learnable at rate faster than exponential rate e -n . Remark 8. Note that this lower bound is actually stronger than desired in a sense that it holds for any learning algorithm (not necessarily for ERM algorithms). Lemma 2 (e -n upper bound). If H does not have an infinite eluder sequence (centered at h * ), then H (h * ) is universally learnable by ERM at rate e -n .Proof of Theorem 3. The sufficiency follows directly from the lower bound in Lemma 1 together with the upper bound in Lemma 2. Furthermore, Lemma 3 in Section 3.2 proves that the existence of an infinite eluder sequence leads to a linear lower bound of the ERM universal rates. Therefore, the necessity follows by using the method of contradiction.Theorem 4. H is universally learnable by ERM with exact rate 1/n if and only if H has an infinite eluder sequence but does not have an infinite star-eluder sequence. Lemma 3 (1/n lower bound). If H has an infinite eluder sequence centered at h * , then h * is not universally learnable by ERM at rate faster than 1/n. Lemma 4 (1/n upper bound). If H does not have an infinite star-eluder sequence (centered at h * ), then H (h * ) is universally learnable by ERM at rate 1/n.Proof of Theorem 4. To prove the sufficiency, on one hand, the existence of an infinite eluder sequence implies a linear lower bound based on Lemma 3. On the other hand, if H does not have an infinite star-eluder sequence, Lemma 4 yields a linear upper bound. The necessity can be proved by the method of contradiction. Concretely, if either of the two conditions fail, the universal rates will be either e -n or at least log (n)/n, based on Lemma 2 in Section 3.1 and Lemma 5 in Section 3.3.Theorem 5. H is universally learnable by ERM with exact rate log (n)/n if and only if H has an infinite star-eluder sequence but does not have an infinite VC-eluder sequence. Lemma 5 (log (n)/n lower bound). If H has an infinite star-eluder sequence centered at h * , then h * is not universally learnable by ERM at rate faster than log (n)/n. Remark 9. Note that the conclusion in Remark 5 explains why the intersection of "infinite Littlestone classes" and "classes with finite star number" is empty in Figure 1 . However, we mention in Remark 3 that infinite star number does not guarantee an infinite star-eluder sequence (see Appendix B.3 for details). Hence, Remark 5 cannot explain why the intersection of "infinite Littlestone classes" and "classes that are learnable at linear rate by ERM" is also empty. To address this problem, we give out the following additional result: Proposition 1. Any infinite concept class H has either an infinite star-eluder sequence or infinite Littlestone dimension. Lemma 6 (log (n)/n upper bound). If H does not have an infinite VC-eluder sequence (centered at h * ), then H (h * ) is universally learnable by ERM at log (n)/n rate.Proof of Theorem 5. To prove the sufficiency, on one hand, if H has an infinite star-eluder sequence, the universal rates have a log (n)/n lower bound based on Lemma 5. On the other hand, if H does not have an infinite VC-eluder sequence, then Lemma 6 yields a log (n)/n upper bound. The necessity can be proved using the method of contradiction based on Lemma 4 in Section 3.2 and Lemma 7 in Section 3.4 below.Theorem 6. H requires at least arbitrarily slow rates to be learned by ERM if and only if H has an infinite VC-eluder sequence.Proof of Theorem 6. Given the necessity proved by Lemma 6 in Section 3.3, it suffices to prove the sufficiency, which is completed by the following Lemma 7.Lemma 7 (Arbitrarily slow rates). If H has an infinite VC-eluder sequence centered at h * , then h * requires at least arbitrarily slow rates to be universally learned by ERM. 
equivalent characterizations: 
 In Section 3, it has been shown that the eluder sequence, the star-eluder sequence and the VC-eluder sequence are the correct characterizations of the exact universal learning rates by ERM. However, the definitions to them are somewhat non-intuitive. Therefore, in this section, we aim to build connections between these combinatorial sequences and some well-understood complexity measures, which will then give rise to our Theorem 1. Concretely, we have the following two equivalences (see Appendix D.2 for their complete proofs). Lemma 8. H has an infinite eluder sequence if and only if |H| = ∞.(H) = ∞.Maybe surprisingly, unlike the above two equivalences, s H = ∞ is inequivalent to the existence of an infinite star-eluder sequence. Indeed, it is straightforward from definition that if H has an infinite star-eluder sequence, then it must have s H = ∞. However, the converse is not true. Proposition 2. s H = ∞ if H has an infinite star-eluder sequence. Moreover, there exist concept classes H with s H = ∞ but does not have any infinite star-eluder sequence. Remark 10. Based on the results in Section 3, the proposition essentially states that the gap between 1/n and log (n)/n exact universal rates by ERM is not characterized by the star number s H . We wonder whether there is some other simple combinatorial quantity that is determinant to this gap, which would be an valuable direction for future work.Why is the case of star-eluder sequence different from the other two structures? We suspect that such a distinction may arise from the following: unlike the eluder sequence and the VC-eluder sequence, the centered concept of a star-eluder sequence is much more meaningful (see Remark 6). Concretely, within its definition, the set of the following k points is not only required to be a star set of the version space V n k (H), but is required to be centered at the same labelling target. This intuitively implies that there might exists a class such that for arbitrarily large integer k, it can witness a star set of size k, but with a k-specified center (for different k). Such a class (e.g. Examples 19, 20 in Appendix B.3) does have infinite star number but will not have an infinite star-eluder sequence. Indeed, the relations between those star-related notions (star number, star-eluder dimension, star set and star eluder sequence) turn out to be more complicated than expected, and we leave it to Appendix B.3. 
appendix summary: 
 Due to page limitation, we leave some interesting results as well as all the proofs to Appendices, which are briefly summarized below. Given extra required notations and definitions in Appendix A and related technical lemmas in Appendix E, the main body of supplements consists of three parts, namely, Appendices B, C and D. Specifically, Appendix B contains three sub-parts. In Appendix B.1, we provide direct mathematical analysis (without using our characterization in Section 1.2) for those basic examples in Section 1.1. In Appendix B.2, we provide details of examples that appeared in Section 1.2. These examples are carefully constructed, providing evidence that ERM algorithms cannot guarantee the optimal universal rates (Bousquet et al., 2021) . In Appendix B.3, we construct nuanced examples to distinguish between the following notions: star number s H (Definition 4), the star-eluder dimension SE(H) (Definition 9), star set (Definition 4) and star eluder sequence (Definition 6). These examples will convince the readers why our characterization in Theorem 1 uses the star eluder sequence rather than the star number (see our discussions in Remarks 3 and 10).Appendix C presents a fine-grained analysis of the asymptotic rate of decay of the universal learning curves by ERM, whenever possible. This will be an analogy to the optimal fine-grained universal learning curves studied in Bousquet et al. (2023) . Concretely, we provide a characterization of sharp distribution-free constant factors of the ERM universal rates. Our characterization of these constant factors is based on two newly-developed combinatorial dimensions, namely, the star-eluder dimension (or SE dimension) and the VC-eluder dimension (or VCE dimension) (Definition 9). We say "whenever possible" because distribution-free constants are unavailable for certain cases (see our discussion in Remark 16). Such a characterization can be considered as a refinement to the classical PAC theory, in a sense that it is sometimes better but only asymptotically-valid.Finally, Appendix D includes all the missing proofs for the theorems and lemmas that have shown up in previous sections. 
conclusion and future directions: 
 In this paper, we reveal a fundamental tetrachotomy of the universal learning rates by the ERM principle and provide a complete characterization of the exact universal rates via certain appropriate complexity structures. Additionally, by introducing new combinatorial dimensions, we are able to characterize sharp asymptotically-valid constant factors for these rates, whenever possible. While only the realizable case is considered in this paper, we believe analogous results can be extend to different learning scenarios such as the agnostic case. Generalizing the results from binary classification to multiclass classification would be another valuable future direction. Moreover, since this paper considers the "worst-case" ERM in its nature, studying the universal rates of the "best-case" ERM is also an interesting problem which we leave for future work. A Preliminaries Notation 1. We denote by N the set of all natural numbers {0, 1, . . .}. For any n ∈ N, we denote[n] := {1, . . . , n}. Notation 2. For any x > 0, we redefine ln (x) := ln (x ∨ e) and log (x) := log 2 (x ∨ 2). Moreover, for correctness, we also adopt the conventions that ln (0) = log (0) = 0, 0 ln (∞) = 0 log (∞) = 0.After then, it is reasonable to define 0 ln (0/0) = 0 log (0/0) = 0. Notation 3. For any R-valued functions f and g, we write f (x) ≲ g(x) if there exists a finite numerical constant c > 0 such that f (x) ≤ c • g(x) for all x ∈ R. For example, ln (x) ≲ log (x) and log (x) ≲ ln (x). Notation 4. Let X be an instance space, we write h all-0's and h all-1's to denote the hypotheses that output all zero labels and all one labels, respectively, that is, h all-0's (x) = 0, h all-1's (x) = 1, ∀x ∈ X . Notation 5. For an infinite union of spaces (X 1 ∪ X 2 ∪ • • • ) and an integer k, we write X <k to denote the finite union of prefix(X 1 ∪ • • • ∪ X k-1) and write X >k to denote the infinite union of suffix(X k+1 ∪ X k+2 ∪ • • • ).Definition 8 (Empirical risk minimization). Let H be a concept class on an instance space X . For every n ∈ N, letS n := {(x i , y i )} n i=1 ∈ (X × {0, 1}) n be a set of samples. A learning algorithm that outputs { ĥn } n∈N is called an Empirical Risk Minimization (ERM) algorithm, if it satisfies ĥn ∈ arg min h∈H êr Sn (h) := arg min h∈H { 1 n n i=1 1(h(x i ) ̸ = y i )} for all n ∈ N, where êr Sn ( ĥn )is called the empirical error rate of ĥn on S n . It is clear that êr Sn ( ĥn ) = 0 when P ∈ RE(H).Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: The paper is theoretical in its nature and does not include experiments. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: The paper is theoretical in its nature and does not include experiments. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The paper is theoretical in its nature and does not include experiments. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The research conducted in this paper follows the NeurIPS Code of Ethics. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: The paper is theoretical in its nature and holds no foreseeable societal impacts as far as we can discern. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper is theoretical in its nature and poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this appendix section, we provide further examples. Specifically, in Appendix B.1, we present direct analysis (without using our newly-developed characterization) of each example illustrated in Section 1.1. The aim of the examples in Appendix B.2 is to reveal that ERM algorithms can sometimes be optimal but sometimes not in a universal learning framework, and compare their performance with the optimal universal learning algorithms. Finally, we also provide additional examples related to the star number in Appendix B.3 as complements to Proposition 2 in Section 4.We provide direct analysis to the examples illustrated in Section 1.1 without using the characterization in Theorem 1. Concretely, Examples 8 and 9 illustrate scenarios where linear universal rates occur. Example 10 specifies a case where universal rate matches uniform rate by ERM as log (n)/n. Example 11 specifies a case where extremely fast universal learning is achievable, but where some bad ERM algorithms can give rise to arbitrarily slow rates. Example 7 (Example 1 restated). Any finite class H is universally learnable at exponential rate by ERM. To show this, for any realizable distribution P with respect to H, we haveE er P ( ĥn ) ≤ P (∃h ∈ H : er P (h) > 0, êr Sn (h) = 0) union bound ≤ h∈H:er P (h)>0 P ( êr Sn (h) = 0) = h∈H:er P (h)>0(1-er P (h)) n ≤ |H| • 1 - min h∈H:er P (h)>0 er P (h) n 1 -t ≤ e -t ≤ |H| • exp - min h∈H:er P (h)>0 er P (h) • n .Example 8 (Example 2 restated). Let H thresh,N := {h t : t ∈ N} be the class of all threshold classifiers on the space of natural numbers defined by h t (x) := 1(x ≥ t). H thresh,N is universally learnable at exponential rate since this concept class does not have an infinite Littlestone tree (Bousquet et al., 2021) . In the following part, we show that the worst-case ERM cannot achieve such exponential rate, but has a rate 1/n.Let h t * ∈ H thresh,N be the target hypothesis. Given a dataset S n , let h t = ERM(S n ) be the output of an ERM algorithm. For any realizable distribution P satisfying P {(t, 0)} = 1 for all t < t * and P {(t, 1)} = 1 for all t ≥ t * , we definet l := max {t < t * : P (t) > 0} .According to the definition of threshold classifiers, if the dataset S n contains at least a copy of both t l and t * , then er P (h t) = 0. Therefore, we haveE [er P (h t)] ≤ P (er P (h t) > 0) ≤ (1 -P (t * )) n + (1 -P (t l )) n .Note that for any ϵ ∈ (0, 1), 1 -ϵ ≤ e -ϵ , it follows immediately thatE [er P (h t)] ≤ (1 -P (t * )) n + (1 -P (t l )) n ≤ e -nP (t * ) + e -nP (t l ) ≤ 2e -n•min{P (t * ),P (t l )} .However, let us consider a distribution P satisfying P {(t, 0)} = 2 -t and P {(t, 1)} = 0 for all t ∈ N.Note that P is also realizable with respect to H thresh,N according to the definition, that isinf h∈H thresh,N er P (h) = inf t∈N er P (h t ) = inf t∈N 2 -t = 0.Given a dataset S n := {(x i , y i )} n i=1 ∼ P n , let t n := max i∈ [n] x i be the largest point in the dataset, it is straightforward that the worst-case ERM outputs h tn+1 , and we have thatE er P h tn+1 = t≥1 2 -t-1 • P max i∈[n] x i = t = t≥1 2 -t-1 1 -2 -t n -1 -2 -(t-1) n .On one hand, we can lower bound the above infinite series byt≥1 2 -t-1 1 -2 -t n -1 -2 -(t-1) n ≥ ⌊log n⌋ t=1 2 -t-1 1 -2 -t n -1 -2 -(t-1) n ≥ 1 2n ⌊log n⌋ t=1 1 -2 -t n -1 -2 -(t-1) n ≥ 1 2n 1 - 2 n n ≥ 1 18n, for infinitely many n.This implies that H thresh,N is not learnable by ERM at rate faster than 1/n. On the other hand, we have the following upper bound for all n:t≥1 2 -t-1 1 -2 -t n -1 -2 -(t-1) n ≤ t≥1 2 -t 1 -2 -t n ≤ 1 0 ϵ(1 -ϵ) n dϵ = 1 n + 1 ,which implies that H thresh,N is indeed learnable by ERM at linear rate 1/n. In conclusion, H thresh,N is universally learnable by ERM with exact 1/n rate.Example 9 (Threshold classifier on R). This example serves as a complement to Example 8.Here, we show that ERM algorithms can sometimes be optimal for universal learning. Specifically, let H thresh,R := {h t : t ∈ R} be the class of all threshold classifiers on the real line defined by h t (x) := 1(x ≥ t), ∀x ∈ R. It has been shown that H thresh,R is universally learnable with optimal linear rate (Schuurmans, 1997) .To show that H thresh,R is also universally learnable with exact linear rate by ERM, we only need to prove an upper bound. To this end, let h t * ∈ H thresh,R be the target hypothesis. For any realizable distribution P satisfying P {(t, 0)} = 1 for all t < t * and P {(t, 1)} = 1 for all t ≥ t * , a dataset S n and ϵ ∈ (0, 1), let h t = ERM(S n ) be the output of an ERM algorithm. Now we define A and B be the minimal regions left and right to t * ∈ R such that P(A) = P(B) = ϵ. If at least one of A and B does not contain any sample, then the worst-case ERM can output h t ∈ H thresh,R such that er P (h t) ≥ ϵ. Therefore, it follows thatE [er P (h t)] = 1 0 P (er P (h t) ≥ ϵ) dϵ ≤ 1 0 2(1 -ϵ) n dϵ ≤ 1 0 2e -nϵ dϵ ≤ 2 n .Note that such analysis is also applicable to the realizable distribution with the target concept h all-0's . Therefore, we have that H thresh,R is universally learnable by ERM with exact rate 1/n.Example 10 (Example 3 restated). Let X = N and define H singleton,N := {h t : t ∈ X } be the class of all singletons on X , where h t (x) := 1(x = t), for all x ∈ X . It is clear that VC(H singleton,N ) = 1.Note that H singleton,N is universally learnable at exponential rate since it does not have an infinite Littlestone tree (Actually, we have LD(H singleton,N ) = 1). In the following part, we show that the worst-case ERM algorithm has an exact universal rate log (n)/n.To get the exact rate by ERM on universally learning H singleton,N , we consider a marginal uniform distribution over {1, 2, . . . , 1/ϵ} with all zero labels with ϵ ∈ (0, 1), if the dataset S n does not have a copy of a point 1 ≤ x ≤ 1/ϵ, the worst-case ERM can label 1 at x, and thus has an error rate er P ( ĥn ) ≥ ϵ. Based on the Coupon Collector's Problem, we know that to have E[er P ( ĥn )] ≤ ϵ, we need n = Ω(ϵ -1 log(1/ϵ)). In other words, E[er P ( ĥn )] ≥ Ω( log n n ), that is, H singleton,N is not universally learnable by ERM at rate faster than log (n)/n. Finally, the classical PAC theory yields the same upper bound, and thus log (n)/n is tight.Example 11 (Example 4 restated). Let X = i∈N X i be the disjoint union of finite sets with|X i | = 2 i . For each i ∈ N, let H i := h S := 1 S : S ⊆ X i , |S| ≥ 2 i-1 ,and consider the concept class H = i∈N H i . In the following part, we show that the worst-case ERM can be arbitrarily slow in learning this class.Given any rate function R(n) → 0, let {n t } t≥1 and {i t } t≥1 be two strictly increasing sequences such that {p t := 2 it-2 /n t , ∀t ≥ 1} satisfies {p t } t≥1 is decreasing , t≥1 p t ≤ 1 and p t ≥ 4R(n t ).We consider any ERM algorithm with the following property: if the data S n = {(x i , y i )} n i=1 satisfies y i = 0 for all i ∈ [n], outputs ĥn ∈ H i Tn withT n := min {t : ∃h ∈ H it s.t. h(x 1 ) = • • • = h(x n ) = 0} .We construct the following distribution P :P {(x, 0)} = 2 -it p t , for all x ∈ X it , t ∈ N,where we set P {(x ′ , 0)} = 1 -t≥1 p t for some arbitrary choice of x ′ / ∈ t∈N X it . Sinceinf h∈H er P (h) = inf i∈N inf h∈Hi er P (h) ≤ inf i∈N er P (h Xi ) ≤ inf it:t∈N er P (h Xi t ) = inf it:t∈N P {(x, 0) : x ∈ X it } = 0,we know that P is realizable with respect to H. Finally, we claim that the ERM defined above behave poorly on P by showing E[er P ( ĥn )] ≥ R(n) for infinitely many n. To this end, note that for a dataset S nt = {(x i , y i )} nt i=1 ∼ P nt , and for any t ∈ N, it holdsP (T nt ≤ t) ≥ P {j ∈ [n t ] : x j ∈ X it } ≤ 2 it-1 = P   nt j=1 1 {x j ∈ X it } ≤ 2 it-1   ≥ 1 2 ,where the last inequality follows from the Markov's inequality. Therefore,E er P ( ĥnt ) ≥ 2R(n t ) • P er P ( ĥnt ) ≥ 2R(n t ) p t ≥ 4R(n t ) ≥ 2R(n t ) • P er P ( ĥnt ) ≥ 1 2 p t LoFT ≥ 2R(n t ) • P er P ( ĥnt ) ≥ 1 2 p t T nt ≤ t P (T nt ≤ t) ≥ 2R(n t ) • P er P ( ĥnt ) ≥ 1 2 p Tn t T nt ≤ t P (T nt ≤ t) ≥ 2R(n t ) • P (T nt ≤ t) ≥ R(n t ).In this section, we provide evidence that ERM algorithms cannot guarantee the best achievable universal learning rates. Recall that the optimal universal learning rates and the associated characterization have been fully understood by Bousquet et al. (2021) , which we present first as follow:Theorem 7 (Bousquet et al., 2021, Theorem 1.9). For every concept class H with |H| ≥ 3, the following hold:• H is universally learnable with optimal rate e -n if H does not have an infinite Littlestone tree. • H is universally learnable with optimal rate 1/n if H has an infinite Littlestone tree but does not have an infinite (strong) VCL tree. • H requires arbitrarily slow rates if H has an infinite (strong) VCL tree.Based on our Theorem 1, to distinguish the optimal universal rates from the exact universal rates by ERM, we have to distinguish their corresponding characterizations. Indeed, those sequences we defined in Section 2 are strongly related to the Littlestone tree and the VCL tree in Theorem 7. According to the definitions, it is not hard to figure out all the following relations:• Every branch of a Littlestone tree is an eluder sequence. Hence, if H does not have an infinite eluder sequence, then H must not have an infinite Littlestone tree, and thus can be universally learned with optimal exponential rate. However, there exists a class H having an infinite eluder sequence but no infinite Littlestone tree (see Example 12 below). This implies that such a class cannot be universally learned by ERM at rate faster than 1/n, but can be learned by some other "optimal" learning algorithms at e -n rate. • Every branch of a (strong) VCL tree is a VC-eluder sequence, and also a star-eluder sequence.Therefore, if H does not have an infinite star-eluder sequence, then it must not have an infinite VCL tree, and thus can be universally learned with optimal linear rate. However, there exists a concept class that has an infinite star-eluder sequence, but does not have an infinite VCL tree (see Example 14 below). Furthermore, there also exists a concept class that has an infinite star-eluder sequence, but does not even have an infinite Littlestone tree (see Example 13 below). These two examples imply that there exist classes that can not be universally learned by ERM at rate faster than log (n)/n, but can be learned by some other "optimal" learning algorithms at 1/n or even e -n rates. • Moreover, there exists a concept class that has an infinite VC-eluder sequence, but does not have an infinite VCL tree (see Example 16 below), or even no infinite Littlestone tree (see Example 15 below). Such examples imply that there exist classes that require arbitrarily slow rates to be universally learned by ERM, but can be learned by some other "optimal" learning algorithms at 1/n or even e -n rates.To summarize, we are able to illustrate all the distinctions as in the following , where H = H thresh,N is the class of all threshold classifiers on N. Note that H does not have an infinite Littlestone tree, but any infinite sequence {(x 1 , 0), (x 2 , 0), . . .} with x 1 < x 2 < . . . is an infinite eluder sequence of H centered at h all-0's . In particular, h all-0's is the only realizable target that allows an infinite eluder sequence. In other words, for H, all the realizable distribution with target concept h * ∈ H is universally learnable by ERM at exponential rate, except that special one h all-0's , which matches our analysis within Example 8. Example 13 (Infinite star-eluder sequence but no infinite Littlestone tree). Let X := k∈N X k be the disjoint union of finite sets with|X k | = k and H := k≥1 H k , where H k := {1 x : x ∈ X k }.Note that this is exactly singletons on an infinite domain and we have the following hold:1. H does not have an infinite Littlestone tree since for any root x ∈ X , the subclass {h ∈ H : h(x) = 1} has only size 1, and thus the corresponding subtree of the Littlestone tree must be finite. 2. H has an infinite star-eluder sequence. Indeed, any infinite sequence {(x 1 , 0), (x 2 , 0), . . .} with x k ∈ X k for all k ≥ 1, is an infinite star-eluder sequence. To see this, note that for any k ∈ N, and any n k , the version spaceV n k (H) contains j>n k H j . Therefore, {(x n k +1 , 0), (x n k +2 , 0), . . . , (x n k +k , 0)} is a star set of V n k (H) centered at h all-0's , wit- nessed by concepts {1 {xn k +1} , 1 {xn k +2} , . . . , 1 {x n k +k } }.Example 14 (Infinite star-eluder sequence but no infinite VCL tree). Let X 1 and H 1 be defined in Example 13, let X 2 = R and H 2 = H thresh,R be the class of all threshold classifiers on R. Note that H 2 has an infinite Littlestone tree. Now we define X := X 1 ∪ X 2 and H := H 1 ∪ H 2 , and have the following hold:1. H does not have an infinite VCL tree since for any fixed root x ∈ X , the subclass {h ∈ H : h(x) = 1} has a VC dimension only 1, and thus the corresponding subtree of the VCL tree must be finite.In this section, we provide examples to distinguish between the following star-related notions: star number s H (Definition 4), the star-eluder dimension SE(H) (Definition 9), star set (Definition 4) and star eluder sequence (Definition 6).In particular, Example 17 reveals that having an infinite star number of h * does not guarantee that H has an infinite star-eluder sequence centered at the same target h * . Note that if s H = ∞ always yields an infinite star set, then we can simply choose this infinite star set to be an infinite star-eluder sequence. Unfortunately, Example 18 fails the conjecture. Furthermore, Proposition 2 in Section 4 is convinced by Example 19. Finally, Example 20 gives an instance that SE(H) = ∞ and infinite star-eluder sequence are not equivalent as well. For comparison, we recall that E(H) = ∞ is equivalent to an infinite eluder sequence, and VCE(H) = ∞ is equivalent to an infinite VC-eluder sequence (see a discussion in Appendix C).Example 17 (Infinite star number and infinite star-eluder sequence with different centers). Let us recall Example 3, where H singleton,N is the class of singletons on natural numbers. According to the analysis in Example 13, we know that H singleton,N has an infinite star number of h all-0's , and also an infinite star-eluder sequence centered at h all-0's . Now we slightly change the setting: Let X := k∈N X k be the disjoint union of finite sets with|X k | = k (one may simply assume X := N). Denote X k := {x k,1 , . . . , x k,k } and define h k,i (x) := 1{x = x k,i or x / ∈ X k }, for all 1 ≤ i ≤ k. We let H := {h k,i , k ∈ N, 1 ≤ i ≤ k},and have the following hold:1. s hall-0's = ∞: Given arbitrarily large integer k, {(x k,1 , 0), (x k,2 , 0), . . . , (x k,k , 0)} is a star set centered at h all-0's , witnessed by hypotheses {h k,i , 1 ≤ i ≤ k}. 2. s hall-1's = ∞: Given arbitrarily large integer k, {(x 1,1 , 1), (x 2,1 , 1), . . . , (x k,1 , 1)} is a star set centered at h all-1's , witnessed by hypotheses {h i,2 , 1 ≤ i ≤ k}. 3. H has an infinite star-eluder sequence centered at h all-1's : Indeed, {(x 1,1 , 1), (x 2,1 , 1), . . .} is an example of infinite star-eluder sequence. 4. H does not have an infinite star-eluder sequence centered at h all-0's .Example 18 (Infinite star number but no infinite star set). We slightly change the setting in Example 17: Let X := k∈N X k be the disjoint union of finite sets with |X k | = k (one may again simply assumeX := N). Denote X k := {x k,1 , . . . , x k,k }, let h k,i (x) := 1{x = x k,i or x ∈ X >k },for all 1 ≤ i ≤ k and k ∈ N, and let H := {h k,i , 1 ≤ i ≤ k, k ∈ N}. We have the following hold:1. s H = ∞ since H has a star set of arbitrarily large finite size. 2. H does not have an infinite star set.It is worthwhile to mention that in this example, H does have an infinite star-eluder sequence {(x 1,1 , 0), (x 2,1 , 0), (x 2,2 , 0), . . .} centered at h all-0's . Hence, an infinite star set is an infinite stareluder sequence, but not the only possibility.Example 19 (Infinite star number but no infinite star-eluder sequence). We slightly change the setting in Example 18 as follow: Let X := k∈N X k be the disjoint union of finite sets with |X k | = k (one may again simply assumeX := N). Denote X k := {x k,1 , . . . , x k,k }, let h k,i (x) := 1{x = x k,i or x ∈ X <k }, for all 1 ≤ i ≤ k and k ∈ N, and let H := {h k,i , 1 ≤ i ≤ k, k ∈ N}.Then the following hold:1. s H = ∞ since H has a star set of arbitrarily large finite size. 2. H does not have an infinite star-eluder sequence, and SE(H) < ∞.Example 20 (Infinite star-eluder dimension but no infinite star-eluder sequence). For any k ∈ N, let X k := t∈N X k,t be disjoint union of finite sets with |X k,t | = k for all t ∈ N. Let X := k∈N X k also with disjoint subspaces {X k } k∈N . For notation simplicity, let us denote X k,t := {x k,t,1 , . . . , x k,t,k } for all k, t ∈ N. Now we can define a hypothesis class as follow: let h k,t,j (x) := 1{(x = x k,t,j ) ∨ (x ∈ X k,>t ) ∨ (x ∈ X <k )}, for all k, t ∈ N and 1 ≤ j ≤ k, and let H := {h k,t,j , 1 ≤ j ≤ k, k, t ∈ N}. We have the following hold:1. SE(H) = ∞ since for arbitrarily large k ∈ N, H has an infinite k-star-eluder sequence X k with all labels 0. 2. H does not have an infinite (strong) star-eluder sequence. Remarkably, a complete theory to the relations between these notions is still lacking here, which might be of independent interests.In this appendix section, we provide a fine-grained analysis of the asymptotic rate of decay of the universal learning curves by ERM, whenever possible. This will be an analogy to the optimal fine-grained universal learning curves studied in Bousquet et al. (2023) . Our characterization of the sharp distribution-free constant factors is based on two newly-introduced combinatorial dimensions named the star-eluder dimension or SE dimension and the VC-eluder dimension or VCE dimension. We present their formal definitions first. Definition 9 (Star(VC)-eluder dimension). Let H be a concept class, we say H has an infinite • d-star-eluder sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .} centered at h, if it is realizable and for every k ∈ N, {x kd+1 , . . . , x kd+d } is a star set of V kd (H) centered at h. Furthermore, the star-eluder dimension of H, denoted by SE(H), is defined to be the largest integer d ≥ 0 such that H has an infinite d-star-eluder sequence. If H does not have any infinite 1-stareluder sequence, we define SE(H) = 0. If for arbitrarily large integer d, H has an infinite d-star-eluder sequence, we define SE(H) = ∞. • d-VC-eluder sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .} centered at h, if it is realizable, and for every k ∈ N, h(x k ) = y k and {x kd+1 , . . . , x kd+d } is a shattered set of V kd (H). Furthermore, the VC-eluder dimension of H, denoted by VCE(H), is defined to be the largest integer d ≥ 0 such that H has an infinite d-VC-eluder sequence. If H does not have any infinite 1-VC-eluder sequence, we define VCE(H) = 0. If for arbitrarily large integer d, H has an infinite d-VC-eluder sequence, we define VCE(H) = ∞. Remark 12. We recall that the eluder dimension E(H) in Definition 5 represents the length of the longest eluder sequence that exists in H. Indeed, an eluder sequence is exactly one branch of a Littlestone tree, and thus E(H) < ∞ implies that H has no infinite Littlestone tree. The converse is not true, because H may have a finite Littlestone tree with some of the branches being infinitely long (see Example 12). Similarly, the star-eluder dimension SE(H) and the VC-eluder dimension VCE(H) here are also strongly related to certain combinatorial structures that have been studied before. In particular for VCE(H), one may refer to the concepts of the (strong) VCL tree, d-VCL tree and the VCL dimension introduced by Bousquet et al. (2021 Bousquet et al. ( , 2023)) . Indeed, an infinite (strong) VC-eluder sequence is exactly one branch of a strong VCL tree, and an infinite d-VC-eluder sequence is exactly one branch of an infinite d-VCL tree. Since an infinite 1-VCL-tree is exactly an infinite Littlestone tree, an infinite 1-VC-eluder sequence is thus exactly an infinite eluder sequence. Moreover, recall that VCL(H) = 0 implies that H does not have an infinite Littlestone tree, and similarly, here we have VCE(H) = 0 implies that H does not have an infinite eluder sequence. Remark 13. For any concept class H, the following hold:1. E(H) ≥ SE(H) ≥ VCE(H). 2. VCE(H) ≥ 1 ⇐⇒ SE(H) ≥ 1 ⇐⇒ E(H) = ∞. 3. VCE(H) = 0 ⇐⇒ SE(H) = 0 ⇐⇒ E(H) < ∞.We then state the formal definition of the fine-grained universal rates by ERM. Definition 10 (Fine-grained universal rates by ERM). Let H be a concept class and R(n) → 0 be a distribution-free rate function. We say Note that the crucial difference between this definition and Definition 2 is that here R(n) is independent of the data distribution P . In other words, the fine-grained rates provide optimal distribution-free upper and lower envelopes of the universal learning curves up to numerical constant factors. Remark 14. Definition 10 describes special cases of Definition 2 in the following sense: If H is universally learnable at fine-grained rate (no faster than) R by ERM, then it is universally learnable at rate (no faster than) R by ERM as well. Briefly speaking, the fine-grained analysis aims to find the correct characterization that captures the optimal distribution-free upper envelope and lower envelope of all the distribution-dependent learning curves, tight up to numerical constant factors.We now turn to state our results of fine-grained universal rates by ERM. All technical aspects of the proofs are deferred to Appendix D.3. Theorem 8 (Fine-grained learning rates). For every class H with |H| ≥ 3, the following hold:• If VCE(H) < ∞, then H is universally learnable at fine-grained rate VCE(H) log n n, and is not universally learnable at fine-grained rate faster than VCE(H) n , by ERM.• If SE(H) < ∞, then H is universally learnable at fine-grained rate VCE(H) n log ( SE(H) VCE(H) ), but is not universally learnable at fine-grained rate faster than VCE(H)+log (SE(H)) n , by ERM.or equivalently, there exist finite numerical constants α, β > 0 such thatEQUATIONEQUATIONEQUATIONEQUATION)where κ = κ(P ) is a distribution-dependent constant.Remark 15. Our proofs use α = 1/20 and β = 160.Remark 16. When SE(H) = VCE(H) = 0, E(H) < ∞, or SE(H) = VCE(H) = 1, E(H) = ∞,we still have the bounds (3) and (4) since we define log (0) = 0, 0 log (0/0) = 0 and log (x) := log (x ∨ 2) for any x > 0. Moreover, we remark that neither VCE(H) = ∞ nor SE(H) = ∞ is considered in these fine-grained rates. This is because when VCE(H) = ∞, arbitrarily slow rates cannot admit distribution-free constants. And when SE(H) = ∞, it is still impossible because it does not guarantee an infinite star-eluder sequence, that is, the lower bound of (1) cannot be increased to log (n)/n, and is the sharpest one we can have here. To make it more convincing, we provide an example of infinite classes here. Let X 1 be a finite set of size d, and X 2 be an infinite instance space that is disjoint with X 1 . For simplicity, one may assume that X 1 := {-d, -(d -1), . . . , -1} and X 2 := N.We define X := X 1 ∪ X 2 and let H := {h S,k := 1 S∪{k} , ∀S ⊆ X , ∀k ∈ N}. Remark 20. Note that in Theorem 8, the lower bound appears as VCE(H)+log (SE(H)) n . Indeed, SE(H) < ∞ immediately implies VCE(H) < ∞ and then the lower bound in Lemma 10 holds. Combining with the lower bound in Lemma 11 will give us the desired result in Theorem 8 with some sufficiently small constant, e.g. α = 1/20.Remarkably, when both SE(H) and VCE(H) are finite, either of VCE(H) and log (SE(H)) can be larger than the other, and we provide the following examples for evidence. Therefore, none of the quantities can be removed in the lower bound. To prove the proposition, we first introduce a new complexity structure named the threshold sequence. Definition 11 (Threshold sequence). Let H be a concept class, we say that H has an infinite threshold sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .}, if it is realizable and for every integer k, there exists h k ∈ H such that h k (x i ) = y i for all i < k and h k (x i ) ̸ = y i for all i ≥ k. We say an infinite threshold sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .} is centered at h, if h(x i ) = y i for all i ∈ N.The following claim turns out to be an alternative result to the proposition. Claim 1. Any infinite class H has either an infinite star set or an infinite threshold sequence.Given that the claim holds, the proof to the proposition is then straightforward. This is because an infinite star set itself is an infinite star-eluder sequence. Moreover, an infinite threshold sequence gives rise to infinite Littlestone dimension since H can have a Littlestone tree of arbitrarily large depth (an easy example is H thresh,N ). Therefore, it suffices to prove Claim 1. The remaining proof relies on a connection to the classical Ramsey theory, which we briefly introduced as follow.The classical Ramsey's theorem states that one will find monochromatic cliques in any edge labelling (with colors) of a sufficiently large complete graph. Specifically, let r be an positive integer, a simple 2-colors version of the Ramsey's theorem states that there exists a smallest positive integer R(r, r), named the (diagonal) Ramsey number, such that every red-blue edge coloring of the complete graph on R(r, r) vertices contains either a red clique on r vertices or a blue clique on r vertices. However, we will need the following extension of the theorem to an infinite graph. Theorem 9 (Infinite Ramsey's theorem, Ramsey, 1987) . For any countably infinite set, if its induced complete graph is colored with finitely many colors, then there is an infinite monochromatic clique.Proof of Claim 1. Based on Lemma 8, we know that any infinite class H has an infinite eluder sequence. Let {(x 1 , y 1 ), (x 2 , y 2 ), . . .} be an infinite eluder sequence centered at h * , that is, for any j ∈ N, there exists h j ∈ H such that h j (x i ) = y i = h * (x i ) for all i < j and h j (x j ) ̸ = y j = h * (x j ). We aim to show that there exists an infinite subsequence {(x i1 , y i1 ), (x i2 , y i2 ), . . .} that is either an infinite star set centered at h * or an infinite threshold sequence centered at h * . To this end, we consider the infinite eluder sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .} as a red-blue coloring of an infinite complete graph according to the following: let the vertices be indexed by N, then for every edge e i,j with integers i > j, we color it red if h j (x i ) = y i and blue otherwise.Note that for any infinite subsequence {(x i1 , y i1 ), (x i2 , y i2 ), . . .}, if the infinite subgraph comprised of the vertices {i 1 , i 2 , . . .} is monochromatically red, thenh ij (x i k ) = y i k = h * (x i k ) for all integers k > j. Since h ij (x i k ) = y i k = h * (x i k ) for all integers k < j and h ij (x ij ) ̸ = y ij = h * (x ij ), it implies that {(x i1 , y i1 ), (x i2 , y i2 ), . . .} is an infinite star set centered at h * , witnessed by {h ij } j∈N .Moreover, if the infinite subgraph comprised of the vertices {i 1 , i 2 , . . .} is monochromatically blue, it is not hard to verify that {(x i1 , y i1 ), (x i2 , y i2 ), . . .} is an infinite threshold sequence centered at h * . The proof is completed by applying the infinite Ramsey's theorem.Lemma 12 (Lemma 1 restated). Given a concept class H, for any learning algorithm ĥn , there exists a realizable distribution P with respect to H such that E[er P ( ĥn )] ≥ 2 -(n+2) for infinitely many n, which implies that H is not universally learnable at rate faster than exponential e -n . Proof of Lemma 12. We prove the lemma by using the "probabilistic method". Let us consider non-trivially that|H| > 2, let h 1 , h 2 ∈ H and x, x ′ ∈ X such that h 1 (x) = h 2 (x) = y and h 1 (x ′ ) ̸ = h 2 (x ′ ). Now for any learning algorithm ĥn , we define the following two realizable distributions P 0 and P 1 , where P i {(x, y)} = 0.5 and P i {(x ′ , i)} = 0.5, i ∈ {0, 1}. Let I ∼ Bernoulli(0.5), and conditioned on I, let S n := {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x n , y n )} and (x n+1 , y n+1 ) be i.i.d. samples from P I that the learning algorithm ĥn is trained on. We note thatE P ĥn (x n+1 ) ̸ = y n+1 S n , I ≥ 1 2 P x 1 = . . . = x n = x, x n+1 = x ′ = 2 -(n+2) .Furthermore, by the law of total probability, we haveE P ĥn (x n+1 ) ̸ = y n+1 S n , I = 1 2 i∈{0,1} E P ĥn (x n+1 ) ̸ = y n+1 S n , I = i I = i ≤ max i∈{0,1} E P ĥn (x n+1 ) ̸ = y n+1 S n , I = i I = i .The above two inequalities imply that for every n, there exists i n ∈ {0, 1} such thatE P ĥn (x n+1 ) ̸ = y n+1 S n , I = i n I = i n = E[er Pi n ( ĥn )] ≥ 2 -(n+2) .In particular, by the pigeonhole principle, there exists i ∈ {0, 1} such that i n = i infinitely often, which completes the proof.Lemma 13 (Lemma 2 restated). If H does not have an infinite eluder sequence centered at h * , then h * is universally learnable by ERM at rate e -n .Proof of Lemma 13. Since H does not have an infinite eluder sequence centered at h * , then for any realizable distribution P centered at h * and data sequence S := {(x 1 , h * (x 1 )), (x 2 , h * (x 2 )), . . .} ∼ P N , we have# t ∈ N : ∃t ′ > t s.t. ∃h ∈ V St (H) : h(x t ′ ) ̸ = h * (x t ′ ) < ∞.For the largest such integer t, we further haveP(∃h ∈ V St (H) : h(x t ′ ) ̸ = h * (x t ′ )) = 1 for some t ′ := t ′ (S) > t.This is true because the probability decays exponentially. Therefore, we havelim n→∞ P S∼P N (P (x ∈ X : ∃h ∈ V n (H) s.t. h(x) ̸ = h * (x)) = 0) = 1,which implies that there is a distribution-dependent positive integer k := k(P ) < ∞ such thatP (P (x ∈ X : ∃h ∈ V k (H) s.t. h(x) ̸ = h * (x)) = 0) ≥ 1/2.Now for any integer n > k, we split the dataset S n ∼ P n into ⌊n/k⌋ parts with each one sized at least k, denoted by S n,1 , . . . , S n,⌊n/k⌋ . It holds thenP (P (x ∈ X : ∃h ∈ V n (H) s.t. h(x) ̸ = h * (x)) ̸ = 0) ≤P ∀i ∈ {1, . . . , ⌊n/k⌋} : P x ∈ X : ∃h ∈ V Sn,i (H) s.t. h(x) ̸ = h * (x) ̸ = 0 = ⌊n/k⌋ i=1 P P x ∈ X : ∃h ∈ V Sn,i (H) s.t. h(x) ̸ = h * (x) ̸ = 0 ≤ 2 -⌊n/k⌋ ,which also holds for n ≤ k. Finally, it follows thatE er P ( ĥn ) ≤P (∃h ∈ V n (H) : er P (h) > 0) =P (P (x ∈ X : ∃h ∈ V n (H) s.t. h(x) ̸ = h * (x)) ̸ = 0) ≤ 2 -⌊n/k⌋ , ∀n ∈ N.Lemma 14 (Lemma 3 restated). If H has an infinite eluder sequence centered at h * , then h * is not universally learnable by ERM at rate faster than 1/n.Proof of Lemma 14. Let {(x 1 , y 1 ), (x 2 , y 2 ), . . .} be an infinite eluder sequence centered at h * , we consider the following distribution P : P {(x i , y i )} = 2 -i and P {(x i , 1-y i )} = 0 for all i ∈ N. Note that P is realizable (with respect to H) with target h * . Given a dataset S n := {(x i , y i )} n i=1 ∼ P n , let the worst-case ERM outputs ĥn := ERM(S n ). For any t ∈ N, if S n does not contain any copy of the points in {x i , i > t}, we have er P ( ĥn ) ≥ 2 -t . The probability of such event isP n i=1 1 {X i ∈ {x t+1 , x t+2 , . . .}} = 0 = n i=1 P (X i ∈ {x 1 , . . . , x t }) = 1 -2 -t n .Therefore, it follows immediately thatE er P ( ĥn ) ≥ ∞ t=1 2 -t 1 -2 -t n ≥ 1 n 1 - 2 n n ≥ 1 9n ,where the second inequality follows from choosing t = ⌊log n⌋.Lemma 15 (Lemma 4 restated). If H does not have an infinite star-eluder sequence centered at h * , then h * is universally learnable by ERM at rate 1/n.Before proceeding to the proof of Lemma 15, we first introduce several useful tools. The following definition of the sample compression scheme was originally stated in Littlestone and Warmuth (1986) .Definition 12 (Sample compression scheme). Let H be a concept class and S n := {(x i , y i )} n i=1 . A sample compression scheme for H consists of two maps (κ, ρ) such that the following hold:-The compression map κ takes S n to T:= κ(S n ), for some T ∈ ∞ t=0 {(x, y) ∈ S n } t .-The reconstruction function ρ takes T to ρ(T ) : X → {0, 1}.The size of the sample compression scheme ρ) is defined as max Sn∈(X ×{0,1}) n |κ(S n )|. A sample compression scheme (κ, ρ) is called sample-consistent for H, if for any realizable distribution P with respect to H and S n := {(x i , y i )} n i=1 ∼ P n , it holds that êr Sn (ρ(κ(S n ))) = 0. A sample compression scheme (κ, ρ) is called stable if for every subsequence S′ satisfying κ(S n ) ⊆ S ′ ⊂ S n , it holds that ρ(κ(S ′ )) = ρ(κ(S n )), that is, removing any non-compression point from S n does not change the classifier returned by the sample compression scheme. Definition 13 (Version space compression set). Let H be a concept class and P be a realizable distribution with respect to H. For any n ∈ N, and any dataset S n := {(x i , y i )} n i=1 ∼ P n , the version space compression set Ĉn is defined to be the smallest subset of S n satisfying V Sn (H) = V Ĉn (H). Furthermore, we define the version space compression set size as n(S n ) := | Ĉn |, which is a data-dependent quantity. Finally, we define n1:n := max 1≤m≤n m(S m ), which is also datadependent. However, n1:n is not only just dependent on the full sample, but is also dependent on any prefix of the sample (that is, the order of the sample). Remark 21. It has been argued in Wiener et al. (2015) that the region of disagreement of the version space DIS(V n (H)) can be described as a compression scheme, where the size of the compression scheme is exactly the version space compression set size n(S n ).With these definitions in hand, we are now able to prove the lemma.Proof of Lemma 15. Let P be a realizable distribution with respect to H centered at h * , let S n := {(x i , y i )} n i=1 ∼ P n be a dataset and Ĉn ⊆ S n be the corresponding version space compression set with size | Ĉn | = n(S n ). We let (κ, ρ) be a sample compression scheme of size n(S n ) defined by κ(S n ) = Ĉn and ρ( Ĉn ) = ĥn . Since any ERM algorithm will output predictors { ĥn } n∈N satisfying ĥn ∈ V n (H), it is clear thatêr Sn (ρ (κ (S n ))) = n i=1 1 {ρ (κ (S n )) (x i ) ̸ = y i } = n i=1 1 ĥn (x i ) ̸ = y i = 0,and thus it is sample-consistent. Furthermore, let S ′ be any subsequence satisfying Ĉn ⊆ S ′ ⊂ S n . On one hand, we have V Sn (H) ⊆ V S ′ (H). On the other hand, we also have V S ′ (H) ⊆ V Ĉn (H) = V Sn (H). Therefore, we conclude V Sn (H) = V S ′ (H), and thus ρ(κ(S ′ )) = ρ(κ(S n )), that is, the compression scheme (κ, ρ) is also stable. Now we can apply Lemma 24, and then obtainE er P ( ĥn ) = E [er P (ρ (κ (S n )))] ≤ E[n(S n )] n + 1 .Indeed, it has been proved that n(S n ) ≤ s h * (Thm.13 Hanneke and Yang, 2015) , and for completeness, we prove it as in Lemma 25 in Appendix E. The only remaining concern is that the fact "H does not have an infinite star-eluder sequence centered at h * " does not guarantee s h * < ∞. However, it essentially states that the version space will eventually have a bounded star number centered at h * . Since H does not have an infinite star-eluder sequence centered at h * , for any sequence S := {(x 1 , y 1 ), (x 2 , y 2 ), . . .} ∼ P N , there exists a data-dependent integer k := k(S) < ∞ such that s h * (V nk (H)) < k. Moreover, we know there exists a distribution-dependent constant factor k := k(P ) < ∞ such that k(S) ≤ k(P ) with probability at least 1/2. By using a similar argument in the proof of Lemma 15, we haveE er P ( ĥn ) ≲ k n + 2 -⌊n/k⌋ , ∀n ∈ N,which proves a target-specified linear upper bound.Lemma 16 (Lemma 5 restated). If H has an infinite star-eluder sequence centered at h * , then h * is not universally learnable by ERM at rate faster than log (n)/n.Proof of Lemma 16. Suppose that S := {(x 1 , y 1 ), (x 2 , y 2 ), . . .} is an infinite star-eluder sequence in H centered at h * , that is h * (x i ) = y i for all i ∈ N. For notation simplicity, let X 1 := {x 1 }, X 2 := {x 2 , x 3 }, X 3 := {x 4 , x 5 , x 6 }, . . . , X k := {x n k +1 , . . . , x n k +k }, . . ., with n k := k 2 . We consider a strictly increasing sequence {k t } t∈N that will be specified later, and only put non-zero probability masses on these disjoint sets X kt with t ∈ N. Then, let X := t∈N X kt be a union of disjoint finite sets with |X kt | = k t , and consider the following marginal distribution P X on X :P X {x ∈ X kt } = 2 -t and P X (x) = 2 -t /k t , ∀x ∈ X kt .It immediately implies the joint distribution P := P (P X , h * ) that is realizable with respect to H:P {(x, h * (x))} = 2 -t /k t , P {(x, 1 -h * (x))} = 0, ∀x ∈ X kt , ∀k ∈ N.Now for any n ∈ N, we let S n := {(x i , y i )} n i=1 ∼ P n and consider the event E := E 1 ∩ E 2 , where E 1 := {S n does not contain a copy of any point in X k>t } , E 2 := {S n does not contain a copy of at least one point in X kt } .If E happens, the worst-case ERM can output some ĥn ∈ V Sn (H) such that er P ( ĥn ) ≥ 2 -t /k t . This is because: V n k t (H) ⊆ V S n,k <t (H), where S n,k<t contains the samples of S n that falling into X k1 ∪ • • • ∪ X kt-1 , and then X kt = {x n k t +1 , . . . , x n k t +kt } is a star set of V S n,k <t (H) witnessed by a set of functions, denoted by {h n k t +1 , . . . , h n k t +kt }. In other words, V S n,k <t (H) contains a size-k t "singletons" with point-wise probability mass 2 -t /k t . However, the remaining samples S n ∩ X kt does not contain a copy of every point in X kt , which results in an error rate er P ( ĥn ) ≥ 2 -t /k t , with ĥn := h n k t +j for some 1 ≤ j ≤ k t .Hence, it remains to characterize the probability of E. To this end, we refer to the so-called Coupon Collector's Problem, and define a random variable nkt := min {n ∈ N : X kt ⊆ S n } .Note that nkt can be represented as a sum kt j=1 G j of independent geometric random variablesG j ∼ Geometric( kt+1-j kt 2 -t ) for 1 ≤ j ≤ k t , with    E [n kt ] = kt j=1 E [G j ] = kt j=1 kt•2 t kt+1-j = k t • 2 t kt j=1 1 kt+1-j = k t • 2 t • H kt Var [n kt ] = kt j=1 Var [G j ] < kt j=1 kt+1-j kt 2 -t -2 < π 2 •k 2 t •2 2t 6, where H m is m th harmonic number satisfying H m ≳ log (m). Then the standard Chebyshev's inequality implies thatP(|n kt -E[n kt ]| > z) ≤ Var[n kt ] • z -2. By choosing z = 2Var[n kt ], we have with probability at least 1/2,nkt > E [n kt ] -2Var [n kt ] ≥ k t • 2 t • log k t - π √ 3 .In particular, when k t ≥ 38, it holds that log k t ≥ 2π/ √ 3, and thus nkt > 2 t-1 k t log k t with probability at least 1/2. Altogether, we have for any n ≤ 2 t-1 k t log k t ,P (E 2 ) ≥ P (n < nkt ) ≥ P n ≤ 2 t-1 k t log k t , 2 t-1 k t log k t < nkt ≥ 1/2.Moreover, to characterize the probability of E 1 , note that for any x ∼ P X , P(x ∈ X k>t ) = 2 -kt , which implies immediately that for any n ∈ N, P(E 1 ) = (1 -2 -kt ) n . Now for any integer k t ≥ 38, we let n = 2 t-1 k t log k t , and have (for infinitely many n) thatP er P ( ĥn ) ≥ 2 -t k t ≥ P (E) ≥ P (E 1 ) P (E 2 ) ≥ 1 2 1 -2 -kt n ,which implies furtherE er P ( ĥn ) ≥ 2 -t k t P er P ( ĥn ) ≥ 2 -t k t ≥ 1 k t 2 t+1 1 -2 -kt n =: η n,t .Finally, by choosing k t = Ω(2 t ), we can guarantee that n ≥ η -1 n,t log η -1 n,t . Applying Lemma 29, we have E[er P ( ĥn )] ≥ η n,t ≥ log (n)/n, for infinitely many n.Lemma 17 (Lemma 6 restated). If H does not have an infinite VC-eluder sequence centered at h * , then h * is universally learnable by ERM at log (n)/n rate.of the uniform rate log (n)/n can be applied since the version space has a bounded VC dimension d. Finally, we have that for all n ∈ N, E er P ( ĥn ) = Lemma 18 (Lemma 7 restated). If H has an infinite VC-eluder sequence centered at h * , then h * requires at least arbitrarily slow rates to be universally learned by ERM.Proof of Lemma 18. Let S := {(x 1 , y 1 ), (x 2 , y 2 ), . . .} be an infinite VC-eluder sequence in H centered at h * , that is, h * (x i ) = y i for all i ∈ N. We inherit the notations used in Lemma 5 by letting X k := {x n k +1 , . . . , x n k +k } with n k := k 2 , for all k ∈ N. Let X := k∈N X k be a union of disjoint finite sets with |X k | = k, and consider the following marginal distribution P X on X :P X {x ∈ X k } = p k and P X (x) = p k /k, ∀x ∈ X k ,where {p k } k∈N is a sequence of probabilities satisfying k≥1 p k ≤ 1 that will be specified later. It implies immediately the following realizable (joint) distribution P := P (P X , h * ):P {(x, h * (x))} = p k /k, P {(x, 1 -h * (x))} = 0, ∀x ∈ X k , ∀k ∈ N.Our remaining target is to show that for any rate function R(n) → 0, H cannot be universally learned by the worst-case ERM at rate faster than R(n) under the distribution P . To this end, we let S n := {(x i , y i )} n i=1 ∼ P n . For any t ∈ N and any j ∈ [k t ], we consider the following event E n,k,t,j := S n does not contain a copy of any point in X k>t ∪ {x n k t +j } , where {k t } t∈N is an increasing sequence of integers that will be specified later. If E n,k,t,j happens, then the worst-case ERM algorithm can output some ĥn ∈ V n k t (H) such that er P ( ĥn ) ≥ p kt /k t , that is the classifier that predicts incorrectly on the "missing" point in X kt . Moreover, to characterize the probability of event E n,k,t,j , we have P(E n,k,t,j ) = (1 -k>kt p k -p kt /k t ) n . Therefore, we make a construction by applying Lemma 30, and finally get for all t ∈ N,E er P ĥnt ≥ j∈[kt] p kt •P (E nt,k,t,j ) ≥ p kt 1 - k>kt p k - p kt k t nt ≥ p kt 1 - 2 n t nt ≳ R (n t ) .Lemma 19 (Lemma 8 restated). H has an infinite eluder sequence if and only if |H| = ∞.Proof of Lemma 19. The necessity is straightforward. To show the sufficiency, we construct such an infinite eluder sequence via the following procedure: pick some x 1 ∈ X such that both V (x1,0) (H) := {h ∈ H : h(x 1 ) = 0} and V (x1,1) (H) := {h ∈ H : h(x 1 ) = 1} are non-empty. Such a point x 1 must exist since otherwise we will have |H| = 1. Furthermore, we know that at least one of them is infinite, since otherwise we will have |H| < ∞. We assume, without loss of generality, that|V (x1,0) (H)| = ∞. Then we pick some x 2 ∈ X such that both V {(x1,0),(x2,0)} (H) := {h ∈ H : h(x 1 ) = 0, h(x 2 ) = 0} and V {(x1,0),(x2,1)} (H) := {h ∈ H : h(x 1 ) = 0, h(x 2 ) = 1} are non-empty.Note that such an x 2 exists, because otherwise we will have |V (x1,0) (H)| < ∞. Again, at least one of them is infinite for the same reason, and then we choose x 3 from that infinite one. Following a similar procedure, we can get an infinite sequence {(x 1 , y 1 ), (x 2 , y 2 ), . . .}, where {x 1 , x 2 , . . .} are chosen to keep the separates of version space non-empty, and {y 1 , y 2 , . . .} are chosen to keep the version space infinite. Now note that for any i ∈ N, we can find some h i ∈ V Si (H) ̸ = ∅, where S i = {(x 1 , 1 -y 1 ), (x 2 , 1 -y 2 ), . . . , (x i-1 , 1 -y i-1 ), (x i , y i )}. According to Definition 5, we know that {(x 1 , y 1 ), (x 2 , y 2 ), . . .} is an infinite eluder sequence consistent with H.Lemma 20 (Lemma 9 restated). H has infinite VC-eluder sequence if and only if VC(H) = ∞.Proof of Lemma 20. According to Definition 7, the necessity is straightforward, i.e. we must have VC(H) = ∞ if H has an infinite VC-eluder sequence. It remains to prove the sufficiency, that is, VC(H) = ∞ yields the existence of an infinite VC-eluder sequence.We construct an infinite VC-eluder sequence via the following procedure: Let x 1 ∈ X be any point, then at least one of V {(x1,0)} (H) and V {(x1,1)} (H) has an infinite VC dimension, which is because otherwise EQUATIONk := k 2 . Inductively, for any k ∈ N, if V S 1+2+•••+(k-1) (H) = V Sn k (H) has an infinite VC di- mension, let {x n k +1 , . . . , x n k +k } be shattered set of V Sn k (H). Lemma 28 yields the existence of a set of labels {y n k +1 , . . . , y n k +k } ∈ {0, 1} k such that V Sn k+1 (H) has an infinite VC dimension. Otherwise, VC V Sn k (H) = VC   (yn k +1,...,yn k +k )∈{0,1} k V Sn k+1 (H)   ≤ 2k+4 max VC V Sn k+1 (H) < ∞,which leads us to a contradiction! By such a construction, the returned infinite sequence S := {(x 1 , y 1 ), (x 2 , y 2 ), . . .} is an infinite VC-eluder sequence consistent with H. To show the upper bound, let P be a realizable distribution with respect to H, and for any n ∈ N, let S n := {(x 1 , y 1 ), . . . , (x n , y n )} ∼ P n be a dataset. Since VCE(H) = d, for any infinite sequence S := {(x 1 , y 1 ), (x 2 , y 2 ), . . .} ∼ P N , there exists a (smallest) non-negative integer k= k(S) < ∞ such that VC(V k (H)) ≤ d. For any ERM algorithm A, let ĥn := A H (S n ) ∈ V n (H), which can also be written as ĥn := ĥn,k := A V k (H) (S k+1:n ), for every k ∈ [n].Recall that for any ϵ ∈ (0, 1), using the same argument as in the proof of Lemma 6, we can getEQUATIONNow for any n ∈ N, we consider the event E n := {VC(V ⌊n/2⌋ (H)) ≤ d}. Applying the inequality P(A) ≤ P(A|B) + P(¬B), we haveEQUATIONLet the RHS of (6) =: δ ∈ (0, 1), then for the first probability in (7), we haveP er P ( ĥn ) > ϵ E n = P er P ( ĥn,⌊n/2⌋ ) > ϵ VC(V ⌊n/2⌋ (H)) ≤ d ≤ δ,If the event E happens, the worst-case ERM can have an error rate er P ( ĥn ) ≥ p k /d. This is because {x kd-d+1 , . . . , x kd } is a star set (with the same center) of V n (H) ⊇ V kd-d (H), and so we know that for any 1 ≤ j ≤ d, there exists h k,j ∈ V n (H) such that h k,j (x kd-d+j ) ̸ = y kd-d+j , and the ERM outputting h k,j will have such an error rate. The probability of E 1 follows simply as P(E 1 ) = (1 -t>k p t ) n . Moreover, characterizing the probability of E 2 can be approached as an instance of the so-called Coupon Collector's Problem. Specifically, we let nk := min {n ∈ N : X k ⊆ S n } , which can be represented as a sum d j=1 G j of independent geometric random variables G j ∼ Geometric( d+1-j d p k ) for 1 ≤ j ≤ d, with the following properties EQUATION-E[n k ]| > z) ≤ Var[n k ] • z -2 . By choosing z = 2Var[n k ], we have with probability at least 1/2, nk > E [n k ] -2Var [n k ] ≥ d p k log d - π √ 3 .In particular, when d ≥ 38, it holds that log d ≥ 2π/ √ 3, and thus nk > p -1 k d log d/2, with probability at least 1/2. Altogether, we have for any n ≤ p -1 k d log d/2, P (E 2 ) ≥ P (n < nk ) ≥ P n ≤ p -1 k d log d/2, p -1 k d log d/2 < nk ≥ 1/2.Lemma 23 (Chernoff's bound). Let Z 1 , . . . , Z n be independent random variables in {0, 1}, let Z := 1 n n i=1 Z i . For all t ∈ (0, 1), we haveP Z ≤ (1 -t)E[ Z] ≤ e -nE[ Z]t 2 2 .Lemma 24. Let H be a concept class, and (κ, ρ) be a stable sample compression scheme of size n(S n ) < n that is sample-consistent for H given data S n . For any realizable distribution P with respect to H and S n := {(x i , y i )} n i=1 ∼ P n , let ĥn := ρ(κ(S n )). Then it holdsE er P ( ĥn ) ≤ E[n(S n )] n + 1 .T σ := {(x σn+1 , y σn+1 ), . . . , (x σ2n , y σ2n )}, and note that S σ ∪ T σ follows the same distribution as S 2n . Hence, we have P (∃h ∈ H : êr Sn (h) = 0 and êr Tn (h) > ϵ/2) = P (∃h ∈ H : êr Sσ (h) = 0 and êr Tσ (h) > ϵ/2)EQUATIONNext, we consider that given S 2n , how possibly that the following event happensE Y := 1 n n i=1 1 {y σi ̸ = Y σi } = 0 and 1 n n i=1 1 y σn+i ̸ = Y σn+i > ϵ 2 ,for a given labeling Y := (Y 1 , . . . , Y 2n ) ∈ H(S 2n ). Indeed, if E Y happens, then there must exist at least ⌈nϵ/2⌉ indices i ≤ n such that eithery i = Y i , y n+i ̸ = Y n+i or y i ̸ = Y i , y n+i = Y n+i , otherwise, the difference between 1 n n i=1 1{y σi ̸ = Y σi } and 1 n n i=1 1{y σn+i ̸ = Y σn+i } is less than ϵ/2.Based on this and the distribution of σ i 's, we have • 2 -nϵ/2 .P 1 n n i=1 1 {y σi ̸ = Y σi } = 0, 1 n n i=1 1 y σn+i ̸ = Y σn+i > ϵ/2 S 2n ≤ 2 -⌈ nϵ 2 ⌉ .• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.1≤i≤⌊n/k⌋ V Sn,i (H) satisfies VC(V n (H)) ≤ VC(V Sn,i (H)), for every 1 ≤ i ≤ ⌊n/k⌋. Therefore, we have P(VC(V n (H)) > d) ≤ P(∀1 ≤ i ≤ ⌊n/k⌋ : VC(V Sn,i (H)) > d) ≤ 2 -⌊n/k⌋ . Note that this bound also holds when n < k since a probability is always at most 1. Altogether, we obtain P(¬E n ) = P(VC(V ⌊n/2⌋ (H)) > d) ≤ 2 -⌊n/2k⌋ . Conditioning on this event, the previous analysis 


Decision: This paper applies the universal learning framework to ERM learners for the realizable case. Instead of 3 cases, ERM learners can have 4 different rates. The majority of the reviewers think this is a good quality work and therefore I recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper studies the universal rates for ERM learners in the realizable case. While a complete characterization of universal rates for PAC has been studied, it was previously not clear what are the universal rates for the popular ERM learners. This papers presents a tetrachotomy for the ERM learners. In doing so, the authors also develop some new combinatorial complexity measures.
strength_weakness: strength_weakness: It seems that lot of techniques used in this paper were borrowed from "A Theory of Universal Learning" by Bousquet et al. Can authors highlight what are the main difficulties of proving universal rates for ERM learners (compared to PAC learners), and what are new techniques developed for that?

Also, it's not clear to me what is the "worst-case" ERM algorithm (line 101). Can author elaborate on that?
questions: questions: See above.
limitations: limitations: N/A
paper_summary: paper_summary: The work contributes to a recent line of work on universal learning rates, i.e. rates with distribution-dependent constants. It characterizes the universal learning rates for the ERM learning rule (specially, the "worst-case" version thereof), showing a partition into four possible optimal universal ERM rates -- which of these rates the "worst-case" ERM follows determined by combinatorial measures on the hypothesis class.
strength_weakness: strength_weakness: While the examples of different rates in Section 1.1 are expanded on mathematically in the Appendix, they don't add much as written in the body and could use a bit more intuitive framing. The presentation of section 3 feels a bit pedantic at items.
questions: questions: What does a `"bad ERM algorithm" (line 135) look like? Random selection from the version space? 

Do you have any conjectures as to if and where the rates for ``best-case'' ERM differ from the rates presented here?
limitations: limitations: Yes
paper_summary: paper_summary: The main goal of the proposed work is to understand the learning procedure with a focus on Empirical risk minimization. The authors claim to provide a complete picture of the four possibilities of different learning rates by ERM. The work also introduces many new concepts related to combinatorial dimensions.
strength_weakness: strength_weakness: The paper is overall an enjoyable read, but I am not entirely sure how well it fits NeurIPS since the work is mostly theoretical and centred around learning theory. I believe the paper would be more suitable for a venue entirely dedicated to learning theory, such as COLT.
questions: questions: Can the authors explain what do they mean by "learning scenarios such as the agnostic case" in l421?
limitations: limitations: NA
paper_summary: paper_summary: This paper studies the performance of ERM on realizable binary classification problems in the "Universal learning" framework of [1]. Specifically, the original work [1] showed that the optimal universal rate of convergence was in general not achieved by ERM procedures. Nevertheless, characterizing the universal rate of convergence of ERM procedures as a function of the hypothesis class in this setting is still interesting as these procedures are widely used in practice. 

This paper tackles this question and shows that if a hypothesis class $\mathcal{H}$ is universally learnable by ERM procedures, then the universal rate of convergence of the worst ERM procedure is either $\exp(-n)$, $1/n$, $\log(n)/n$ or arbitrarily slow. Necessary and sufficient conditions in terms of properties of $\mathcal{H}$ are given that indicate which of these cases occurs. A second result provides a more refined such characterization as a function of the target function $h_{*} \in \mathcal{H}$ as well.



[1]: Bousquet, O., Hanneke, S., Moran, S., Van Handel, R., and Yehudayoff, A. (2021), “A theory of
universal learning,” in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of
Computing, pp. 532–541.
strength_weakness: strength_weakness: + The writing of the paper is at times uncomfortably close to that [1].
questions: questions: minor comments:
+ lines 69-70: "unlike that" -> "while".
+ line 72: "to the characterization of" -> "characterizing".
+ line 82: "necessary" -> "necessarily".
+ line 107: "exist" -> "exists".
+ line 108: "it requires us" -> "we need"
limitations: limitations: A main limitation of this work is that it does not characterize when a class is universally learnable by ERM. This is mentionned in lines 147-150. More discussion about why this is difficult to achieve would enhance the paper.
paper_summary: paper_summary: In this paper, the authors build on earlier work in learning theory that provides an alternative to the classical PAC theory in the setting of realizable binary classification.  That earlier work considered *universal* learning rates, where a rate is universal if the data source is fixed across sample sizes (as opposed to being allowed to depend on the sample size &n&) and demonstrated a trichotomy in the possible rates of learning.  The present work considers a similar setting, where the data distribution is fixed and $n$ increases, but analyzes only the natural algorithm ERM.  As opposed to the earlier setting where arbitrary algorithms are allowed, the universal learning rates of ERM satisfy a tetrachotomy, depending on several technical combinatorial notions of complexity of the hypothesis class.  The paper complements their theoretical results with a number of concrete examples of hypothesis classes that fall into different cases of the tetrachotomy as well as comparing these cases to the universal rates attainable with more general algorithms than ERM.
strength_weakness: strength_weakness: The primary weakness of the work is the restrictive assumption of realizability, as well as the focus purely on binary classification.  In the setting studied, however, the paper does a good job of essentially completely answering the question of the universal rates.  There is a minor gap in the combinatorial characterization of when rates $1/n$ vs $\log(n)/n$ are expected, but this limitation is adequately discussed in Remark 3.
questions: questions: 1. Are the algorithms that Bousquet et al 2021 use to demonstrate universal learning rates in the absence of computational considerations oracle-efficient with respect to an ERM oracle?  If not, it might be good to emphasize this point.  If so, what are the computational advantages of considering ERM?

2. A minor typo: in example 6, the VC dimension of halfspaces is $d+1$ not $d$.

3. In the conclusion, you suggest the study of "best-case ERM," but I am confused as to what that means?
limitations: limitations: The authors have adequately addressed the limitations.

Comments: title: Thank you for the response
comment: Thanks for the reply and the pointer to Appendix B.1.
Thank you for the clarifying points, especially on the reduction to ERM of prior work.  I would encourage you to include this discussion in the paper.  I maintain my (quite high) score.  Great work!
I thank the authors for their response. I would like to emphasis that my evaluation is an educated guess, I do not know enough about the work [1] to fairly judge the current work.
Thank you for your reply. I have increased my score to 7.
I thank the authors for their explanation.