Universal Rates of Empirical Risk Minimization
Authors: Steve Hanneke
Mingyue Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Statistical learning theory
Universal learning
Empirical risk minimization
PAC learning
Primary area: learning_theory
TL;DR: We consider the problem of universal learning by ERM in the realizable case and study the possible universal rates.

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.

Universal Rates of Empirical Risk Minimization
Steve Hanneke
Mingyue Xu Department Computer Science Purdue University xu xu su18640purddee.cmm edu
Department of Computer Science Purdue University steve. www.hheennnellll.... com
Abstract
The well-known empirical risk minimization (ERM) principle the basis of many widely used machine learning algorithms, and plays an essential role in the classical PAC theory. A common description 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 explain the behavior of learning curves, recent research has explored alternative universal learning model and has ultimately revealed distinction between optimal universal and uniform learning rates (Bousquet et al., 2021). However, basic understanding of such differences with a particular focus on the ERM principle has yet to be developed.
learning algorithm's performance is its
In this paper, we consider the problem of universal learning by ERM in the realiz- able case and study the possible universal rates. Our main result fundamental 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 1/n,, log (n)/n /n, or arbitrarily slow rates. Moreover, we provide a complete characteriza- tion of which concept classes fall into each of these categories, via new complexity structures. We also develop new combinatorial dimensions which supply sharp asymptotically-vant valid constant factors for these rates, whenever possible.
Introduction
The classical statistical learning theory mainly focuses on the celebrated PAC (Probably Approxi- mately Correct) model (Vapnik and Chervonenkis, 1974; Valiant, 1984) with emphasis supervised learning. A particular setting therein, called the realizable case, has been extensively studied. Comple- mented 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 learning algorithm over all realizable distributions. Such learning rates 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 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-uniffrm 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 (2021) via iistribution-dependerr framework. Unlike the simple dicholomy 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 trichotomy: every concept class H. has 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 sumple-consistent classifier. other words, an ERM
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

algorithm is any learning rule, which outputs concept in H. that minimizes the empirical error (see Appendix A for a formal definition). For notation simplicity, we first introduce
Definition (Version space, Mitchell, 1977). Let H. be a concept class and S, := {(x,, y:) be a dataset, the version space induced by S... denoted by Vs, (H) (or (HH(H) for short), is defined as Vs., (H) = (h E H h(x,) ye, Vi E [n]]-
Now given labeled samples S, := (:),,,)) H an ERM algorithm is any learning algorithm that outputs concept in the sample-induced version space, that is, sequence of universally measurable functions An : S.. + hm Vs., (H), n E N. Throughout this paper, we will simply denote an ERM algorithm by its output predictors {hn JneN-
It is well-known that the ERM principle plays an important role in understanding general uniform learnability: 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, 201 2016a), ERM algorithms can at best achieve uniform rate of (VC(H) /n) log (n (n/VC(H)). Moreover, such a gap has been shown to be unavoidable in general (Auer and Ortner. 2007), which leaves 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/ (C()) with log (0(VC(H)/n)) where 8(-) is called the disagreement coefficient. Based on this, Hanneke and Yang (2015) proposed a new dependent bound with log (CCH)) where u. is a quantity related to the version space compression sel size (a.k.a. the empirical teaching dimension). As a milestone, the work of Hanneke (201 proved an upper bound (VC(H)) n) log ($H/VCCC /VCH)) and lower bound (VC(H) + log /nn) where Sh is called the star number of H (see Definition in Section 2). Though not quite matching, these two bounds together yield an optimal linear rate when sy < 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-deeeedden 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, aim to answer the following fundamental question:
Question 1. Given 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 C {0, 1 Given a probability distribution P on X x {0, 1}. the error rate of a classifier h X + {0, 13 is defined as (h) := P((x, v) E X {0, 1} : h(w) A y). A distribution P is (H), if inf (4) = O. Note that in is called the target concept of the learning problem, and is not necessary in H. We may also say that P realizable distribution centered at h.. Given an integer n. we denote by S, := [Ix, y1) y:))
called realizable with respect to H. denoted by P E
this definition, ht* satisfying er (h*) = inf p
_mm a 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 al., 2023), that is, the decay of the expected error rate Ejer (T..)) as a function of sample size n. With these settings settled, we now able to formalize the problem of universal lcarning by ERM.
Definition 2 (Universal learning by ERM). Let H be concept class, and R(n) + 0 be rate function. We say
H. is universally learnable at rate R by ERM, if for every distribution P E RE(H), there exist parameters C, e such that for every ERM algorithm, [ferr((h..)) S CR((n)) for all n E N.
2

---

H. is not universally learnable at rate faster than R by ERM, if there exists distribution
P E RE(H) and parameters C,c > 0 such that there exists an ERM algorithm satisfying E Elerp(hn)) 2 CR(cn)) for infinitely many n. E N.
H. is universally learnable with exact rate R by ERM, if is universally learnable at rate
R by ERM, and is not universally learnable rate faster than R by ERM.
H requires arbitrarily slow rates to be universally learned by ERM, if for every rate func- tion 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 > O are allowed to depend on the distribution P. In other words, the PAC model can be defined similarly, but requires uniform constants C, e > O. Consequently, H. is universally learnbale at rate R. by ERM if it is PAC learnable rate R by ERM.
Remark 2. It is not hard to see that the error rate achieved by any ERM algorithm, given Sn ~ PD as inpul, al most supheVs, ss, (2H) erp(h). Farthermore, for any distribution P RE(H), there exist ERM algorithms obtaining error rates arbitrarily close to this value. Hence, obtain upper bounds of the universal rates by ERM, it requires us to bound the random variable suphevs,, (H1) erp(h) where a common technique is to bound P P(supheVs, (H) erp(h) > c) P(3h E Vs, (H) :rp(()) > c). To obtain lower bounds, it requires us to construct specific "hard" distributions.
1.1 Basic examples
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.
Example 1 (e 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/ learning rate). Let Hehresh, == (h, :t E N) be the class of all threshold classifiers on natural numbers, where hx(x)) == 1 (a 2 for all x E N. Hihnesh, 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 hall-0's which is the function that labels zero everywhere (see Appendix A).
Example 3 (log (n)/ n learning rate). Let X = N and Hsingloton. == (h+ E X} be the class of all singletons on X. where (z)) := 1(z = t), for all E N. It is clear that VC((Hinggeton. that Hiingleton. N is universally learnable at exponential rate since it has finite Littlestone dimension LD x) 1. However, the exact universal rate by ERM is instead log (n)/n. This is because Heingtenon, N admits certain realizable distributions centered at hall-Or-- Indeed, it is an example where the universal rate by ERM matches the uniform rate, up to a iistribution-depennee
1. Note
constant.
Example 4 (Arbitrarily slow learning rate). Let X' = UIEN X, be the disjoint union of finite sets with [x = 2 for all i E N. For each i E N, let Hi := [hs-= 1= S C X, |S| > 21-1) and consider the concept class H = UPEN His H is universally learnable at exponential rate since it does not have an infinite Littlestone free. However, bad ERM algorithm can perform arbitrarily slowly.
Example 5 (Not Glivenko-Cantelli but learnable by ERM). Let X = 10, 1}, H == {1ss : S C X, |S| < oo), and P be the uniform (Lebesgue) distribution on [0, 1]. H is universally learnable at exponential rate (no infinite Littlstonee 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 U (hat-ras. which is still not a universal Glivenko- Cantelll class for P. but no longer universally learnable by any ERM algorithm since (fp()..) 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 n (but not faster), or is universally
3

---

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.
1.2 Main results
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 complete answer to Question 1. It expresses fundamental tetrachotomy: there are exactly four possibilities for the universal learning rates by ERM: being either exponential, or linear, 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 (Universal rates for ERM). For every class H. with [H]] 2 3, the following hold:
H is universally learnable by ERM with exact rate e if and only if [H] < co.
H is universally learnable by ERM with exact rate 1/n if and only if [H] = oc and H does not have infinite star-eluder sequence.
H is universally learnable by ERM with exact rate log (n)/ n if and only if H. has an infinite star-eluder sequence and VC(H) < 0o.
H requires at least arbitrarily slow rates to be learned by ERM if and only if VFVCH = co.
Remark 3. The formal definition of the star-eluder sequence can be found in Section 2. Unlike the separation between exact em 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 /nn and log (n)/n rates is unclear and might be an interesting direction for future work. We thought that is likely the star number Sh (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, distinction between the performance of ERM algorithms and the optimal universal learning algorithms can be revealed, which we present in the following table (the required definitions in "Case" are deferred to Section 2, and examples can be found in Appendix B.2).
Optimal rate
Exact rate by ERM
Case
Example
1/n
infinite cluder sequence but no infinite Littletoone
Example 12
e-
log (n)/n
infinite star-cluder sequence but no infinite Littlestone tree
Example 13
arbitrarily slow
infinite VC-oluder sequence but no infinite Littlestone tree infinite star-eluder sequence but no infinite VCL
Example 15
1/n
log /
Example 14
1/n
arbitrarily slow
infinite VC-eluder sequence but infinite VCL tree
Example 16
Furthermore, the distinction between the universal rates and the uniform rates by ERM can also be fully captured, and are depicted schematically in Figure I as an analogy to the Fig.4 of Bousquet al. (2021). Besides the examples in Section 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, == IR²2 and Himnlspaces, := (1 x + b 2 0): u E RR2 b E R). is a classical fact that for any integer d, the class of halfspaces on Rd has a finte VC dimension d, but has infinite Littlestone tree, and thus having unbounded Littlestone dimension Shalev-Shwart. and Ben- DDvidd 2014). Finally, to show that this class is universally learnable by ERM at exact log (n)/n rate, we simply consider the subspace S C X, this is indeed infinite star set of Hholfiacces centered at han-o's and thus an infinite star-eluder sequence.
As complement to Theorem 1, the following Theorem gives out We say a target concept h" is universally learnable by ERM with exact rate R if all realizable distribution P considered Definition are centered at h²" other words, H universally learnable with exact rate R is equivalent to say all realizable target concepts are universally learnable with exact rate R. Concretely, for each of the four possible rates stated Theorem 1, Theorem 2 specifies the target concepts that can be learned at such exact rate by ERM.
universal rates.

---

Ex.3
finite
Ex.2
Ex.
Ex.1
exponential rate
Littlestone
SH <
linear rate
Ex.6
log (n)/no /m
rate
Ex.4
Ex.5
universal Glivenko-Canede
arbitrary rate
Figure I: 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
2 (Target specified universal rates). For every class with [H] and a target concept h", the following hold:
and only if H. does not have an h" is universally learnable by ERM with exact rate e Th infinite eluder sequence centered at h²,
h" universally learnable by ERM with exact rate 1/n n and only if H. has an infinite eluder sequence centered at h", but does not have an infinite star-eluder sequence centered h².
h² is universally learnable by ERM with exact rate log (n.) if and only if H has infinite star-eluder sequence centered h", but does not have an infinite VC-eluder sequence centered at ht.
ht requires at least arbitrarily slow rates to be universally learned by ERM if and only if H has an infinite VC-eluder sequence centered at h².
All detailed proofs appear Appendix D. We also provide a brief overview of the main idea each proof well some related concepts in Section 2.
An additional part of this work presents fine-grained analysis (Bousquet et al., 2023) the universal rates by ERM, which complements the course rates used in Theorem 1. Concretely, we provide a characterization of sharp distribution- possible. The characterization is based 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- certain cases (Remark 16). Such a characterization can also be considered as a refinement to the classical PAC theory, in sense that it is sometimes better but only asymptoticalllyvaait Due to space limitation, we defer the definition of fine-grained rates and related results to Appendix C.
constant factors the ERM universal rates, whenever
constants unavailable for
1.3 Related works
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 al. (1989) gave out a log (n)/n nn 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 the version space, the work of Giné and Koltchinskii (2006); Hanneke (2009) refined the logarithmic factor in certain scenarios. Furthermore, not only being relevant

---

measure in the context of active learning (Cohn et al., 1994; EI- Yaniv and Wiener, 2012; Hanneke, 2011, 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-Vivies et al., 2018, etc.). Additionally, van Handel (2013) studied the uniform convergence property from a universal perspective, and proposed the universal
property. Until very recently, the universal ciistrbuttion-eeendded 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 fine-grained analysis on the "distribution-fier 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.
2 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.
Definition 3 (Realizable data). Let H be concept class on an instance space X, we say that (finite or infinite) data sequence {(z1, (1), (I2, (I2,92).... y2)....} E (X' x (0,1))²o is realizable (with respect to H), for every n E N. there exists hnp E H such that hz,x) = yi for all i E [n].
Definition 4 (Star number). Let X be an instance space and H be a concept class. We define the region of disagreement of H. as DIS(H) == {x= E X 3h,9 g H. s.t. h(z) # g(z)}- Let h be classifier, the star number of h, denoted by (H)) or 5h for short, is defined be the largest integer such that there exist distinct points .1,..., Is E X and concepts ht....,h. hi E H satisfying DIS(Ah, h,)) n (.,,...,T..) = [rr).for every 1 S i < 8. (We say [II,...,Zs] is a star set of H centered at h.) If no such largest integer exists, define 5/2 co. The star number of H. denoted by s sHH) or sH, is defined to be the maximum possible cardinality of a star set of H. SH co if no such maximum exists.
Remark 4. From this definition, it is clear that the star number sy of H. satisfies sH 2 VC(H).
Indeed, any set {x1...., R.) that shattered by H is also a star set of H based on the following reasoning: Since {x1,.... .ta} is shattered by H. there exists h E H such that h(*1) = h((aa) O. Moreover, for any E [d], there exists h, E H satisfying hę(z;) = 1 and ha(sr)) = 0 for all + i. An immediate implication is that VC-eluder sequence is always star-eluder sequence (see Definition 6 and Definition below).
With these basic definitions in hand, we next define the three aforementioned sequences:
Definition 5 (Eluder sequence). Let H be concept class, we say that H has an eluder sequence
yt)...,,, (x Ya)}, if it is realizable and for every integer k E [d], there exists h2 E H such that by (2ra) = y, for all i < le and hy (xx) # yk- The eluder dimension of H, denoted by E(H), defined to be the largest integer d 221 1 such that H has an eluder sequence {( V1). (x2, y2)..... (x ya) If no such largest d exists, we say H has an infinite eluder sequence and define E(H) = We say an infinite eluder sequence (11, y1), (22, v2)....) . is centered at h, if h(zz)) y for all i e N.

---

Remark 5. It has been proved that max (8,, (LD(H)) S. E(H) S 4maxisu 20000 (Li et al., 2022, Thm.8), where LD(H) is the Littlestone dimension of H. Moreover, the very recent work of Hanneke (2024) proved that B(H) S [ I 2 LD(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 b as 01 = O. v4g- : (t) for all k b>> 1, which satisfies Ti+++1 Tig = k for all E N.
Definition (Star-eluder sequence). Let H- be a concept class and h be a classifier. We say that H has an infinite star-eluder sequence {z 11), (22,, v2),...) centered at h, , if is realizable and for every integer k 2 1, (Tug tnu+k) } is a star set Vn (H) centered at h. Definition 7 (VC-eluder sequence). Let H be concept class and h be classifier. We say that H. has an infinite VC-eluder sequence {(11, 81), (I2, ... centered at h, if is realizable and labelled by h, and for every integer l 2 1, (Ineti...... Ing+k] is a shattered set of (H..
Remark In the definitions of eluder sequence and VC-eluder sequence, "[(21,9)); (22, y2),-..
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 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 cannol grow infinitely, the largest possible size of the star (shattered) set is called the star-eluder (V (VC-eluder) dimension (Definition 9), which plays an important role in our fine- -neeggrinedd analysis (Appendix C). To distinguish the notion of star-eluder (VC-eluder) sequence here from the d-star-eluded (d- (L-VCelluder) 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 I and 2. The proof of Theorem 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 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 associated target-dependent version, and is directly proved by those corresponding lemmas in Section 3. The complete proof structure for Theorem can be summarized as follow:
For the first bullet, we start by proving that H. is universally learnable with exact rate e 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 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).
3 Exact universal rates
Sections 3 and of this paper are devoted to the proof ideas of Theorems I and with further details. In this section, we give complete characterization of the four possible exact universal rates by ERM (e- 1/n, log (n)/n and arbitrarily slow rates) via the existence/nonexisteene 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 upper bound and a lower bound since we proving the exact universal rates. The
7

---

necessity also follows simply by the method of contradiction, given the rates are exact. All technical proofs are deferred to Appendix D.I.
3.1 Exponential rates
Theorem 3. H. is universally learnable by ERM with exact rate e if and only if does not have an infinite eluder sequence.
The lower bound for sufficiency straightforward and was established by Schuurmans (1997).
Lemma (e-n lower bound). Given concept class H. for any learning algorithm h. there exists realizable distribution P with respect to HH. such that Elerp 2 2 ( for infinitely many which implies that H not universally learnable at rate faster than exponential rate e
Remark 8. Note that this lower bound is actually stronger than desired in sense that it holds for any learning algorithm (not necessarily for ERM algorithms).
Lemma 2 (e upper bound). If H. does not have an infinite eluder sequence (centered at h") then H (l²) ) is universally learnable by ERM at rate e e
Proof of Theorrmm 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 a linear lower bound of the ERM universal rates. Therefore, the necessity follows by using the method of contradiction.
3.2 Linear rates
Theorem 4. H is universally learnable by ERM with exact rate 1/n and only if H. has an infinite eluder sequence but does not have an infinite star-eluder sequence.
Lemma 3 (1/n lower bound). I has an infinite eluder sequence centered h², then h is not universally learnable by ERM at rate faster than 1/n.
Lemma (1/n upper bound). H. does not have an infinite star-eluder sequence (centered h²), then H. (h") is universally learnable by ERM at rate 1/n.
Proof of Theorem 4. prove the sufficiency, on one hand, the existence of an infinite eluder se- quence implies linear lower bound based on Lemma 3. On the other hand, if 7 does not have an infinite star-eluder sequence, Lemma yields 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 R or at least log (n)/n, based on Lemma Section 3.1 and Lemma Section 3.3. D
3.3 log (n)/n rates
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 have an infinite VC-eluder sequence.
Lemma 5 (log (n)/nn lower bound). If H has an infinite star-eluder sequence centered at h², then h" 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 Figure 1. However, we mention in Remark 3 that infinite details). Hence, Remark 5 cannot explain why the intersection of "infinite Littlestone classes" and "classes that learnable linear rate by ERM" is also empty. To address this problem, give the following additional result:
number does not guarantee infinite star-eluder sequence (see Appendix B.3 for
Proposition 1. Any infinite concept class H has either an infinite star-eluder sequence or infinite Littlestone dimension.
Lemma (log (n)/n upper bound). H does not have an infinite VC-eluder sequence (centered at h²) then H (h") ) is universally learnable by ERM at log (no /n rate.
Proof of Theorem 5. 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 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.
3.4 Arbitrarily slow rates
Theorem 6. H requires at least arbitrarily slow rates to be learned by ERM if and only if 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 completed by the following Lemma
Lemma (Arbitrarily slow rates). If H has an infinite VC-eluder sequence centered at h", then ht requires at least arbitrarily slow rates be universally learned by ERM.
4 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 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 (sce Appendix D.2 for their complete proofs).
Lemma 8. H has an infinite eluder sequence if and only (H) = xc. Lemma 9, H has an infinite VC-eluder sequence if and only if VC(H) = oc.
Maybe surprisingly, unlike the above two equivalences, 9 = oo is inequivalent to the existence of an infinite star-eluder sequence. Indeed, is straightforward from definition that if H has an infinite star-cluder sequence, then it must have sn co. However, the converse is not true.
oo if H has infinite star-eluder sequence. Moreover, there exist concept classes H with अय = oo but does not have any infinite star-eluder sequence.
Proposition 2.
Remark 10. Based on the results in Section the proposition essentially states that the gap between I/n and log (n)/n exact universal rates by ERM is not characterized by the star number sy. We wonder whether there is some other simple combinatorial quantity that is determinant this gap, which would be an valuable direction for future work.
Why is the case star-eluder sequence different from the other two structures? We suspect that such distinction may arise from the following: unlike the eluder sequence and the VC-eluder sequence, the centered concept of star-eluder sequence is much more meaningful (see Remark 6). Concretely, within its definition, the set of the following i points is not only required to be star set of the version space Va (7C). but is required to be centered at the same labelling target. This intuitively implies that there might exists class such that for arbitrarily large integer k, it witness 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 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 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 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. we provide direct mathematical analysis (without using our characterization in Section 1.2) for those basic examples 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 distinguish between the following notions: star number 9H (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 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 ane-grained universal learning curves studied in Bousquet et al. (2023). Concretely, we provide a characterization of sharp distribution-Fr 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-fiee constants are unavailable for certain cases (see our discussion in Remark 16). Such a characterization can be considered as refinement to the classical PAC theory, in sense that it is sometimes better but only asymplotically-valid
Finally, Appendix D includes all the missing proofs for the theorems and lemmas that have shown up in previous sections.
6 Conclusion and Future Directions
In this paper, we reveal fundamental tetrachotomy of the universal learning rates by the ERM principle and provide complete characterization of the exact universal rates via certain appropriate complexity structures. Additionally, by introducing new combinatorial dimensions, characterize sharp asymptotically-valin 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 the "best-case" ERM is also an interesting problem which we leave for future work.
are able to
References
Antos, A. and Lugosi, G. (1996), "Strong minimax lower bounds for learning," in Proceedings of the 9th Annual Conference Computational Learning Theory, pp. 303-309.
Audibert, J.-Y. and Tsybakov, A. B. (2007), "Fast learning rates for plug-in classifiers," The Annals of Statistics, 35, -33..
Auer, P. and Ortner, R. (2007), "A new PAC bound for intersection-closed concept classes," Machine Learning, 66, 151-163.
Benedek, G. M. and Itai, A. (1988), "Nonuniform learnability," in Automata, Languages and Pro- gramming: 15th International Colloquium Tampere, Finland, July 11-15, 1988 Proceedings 15, Springer, pp. 82-92.
Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. (1989), "Leamability and the Vapnik-Chervoneen Chervonenkis dimension." Journal of the ACM (JACM), 36, 929-965.
Bousquet, O., Hanneke, S., Moran, S., Shafer, J., and Tolstikhin, I. (2023), "Fine-grained distribution- dependent learning curves," in Proceedings of the 36th Annual Conference on Learning Theory, PMLR, pp. 1890-5924
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.
Cohn, D., Atlas, L., and Ladner, R. (1994), "Improving generalization with active learning," Machine Learning, 15, 201-221.
10

---

Cohn, D. and Tesauro, G. (1990), "Can neural networks do better than the bounds?" Advances in Neural Information Processing Systems, 3.
- -(192)), "How tight are the Aapiik-Chevooneniis bounds?" Neural Computation, 4, 249-269.
El-Yaniv, R. and Wiener, Y. (2012), "Active Learning via Perfect Selective Classification." Journal of Machine Learning Research, 13, 255-279.
Giné, E. and Koltchinskii. V. (2006), "Concentration inequalities and asymptotic results for ratio type empirical processes," The Annals of Probability, 34, 1143-1216.
Hanneke, S. (2009), Theoretical foundations of active learning, Carnegie Mellon University.
(201 1), "Rates of convergence in active learning," The Annals of Statistics, 39, 333-311.
(2014), "Theory of disagreement-bassee active learning." Foundations and Trends in Machine Learning, 7, 131-309.
(2016a), "The optimal sample complexity of PAC learning," Journal of Machine Learning Research, 17, 1-15.
(2016b), "Refined error bounds for several learning algorithms," Journal of Machine Learning Research, 17, 1-55.
-(2024), "The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement," in Proceedings of the 37th Annual Conference Learning Theory.
Hanneke, S., Karbasi, A., Moran, S., and Velegkas, G. (2022), "Universal rates for interactive learning," Advances in Neural Information Processing Systems, 35, 28657-28669.
Hanneke, S., Moran, S., and Zhang, Q. (2023), "Universal Rates for Multiclass Learning." in Proceedings of the 36th Anmual Conference on Learning Theory, PMLR, pp. 5615-5681.
Hanneke, S. and Yang, L. (2015), "Minimax analysis of active learning." Journal of Machine Learning Research, 16. 3487-3602.
Kalavasis, A., Velegkas, G., and Karbasi, A. (2022), "Multiclass learnability beyond the pac frame- work: Universal rates and partial concept classes," Advances Neural Information Processing Systems, 35, 20809-20822.
Koltchinskii, V. and Beznosova, O. (2005), "Exponential convergence rates in classification," in Proceedings of International Conference on Computational Learning Theory, Springer, pp. 295- 307.
Li, G., Kamath, P., Foster, D. J., and Srebro, N. (2022), "Understanding the eluder dimension," Advances in Neural Infommaion Processing Systems, 35, 23737-23750.
Littlestone, N. and Warmuth, M. (1986), "Relating data compression and learnability." Unpublished manuscript.
Mitchell, T. M. (1977), "Version spaces: A candidate elimination approach rule learning." in Proceedings of the 5th International Joint Conference on Artificial Intelligence, vol. 1, pp. 305-310.
Pillaud-Vivie Vivien, L., Rudi, A., and Bach, F. (2018), "Exponential convergence of testing error for stochastic gradient methods," Conference on Learning Theory, PMLR, pp. 250-296.
Ramsey, F. P. (1987), "On a problem of formal logic," in Classic Papers in Combinatorics, Springer, pp. 1-24.
Sauer, N. (1972), "On the density of families sets," Journal of Combinatorial Theory, Series A, 13, 145-147.
Schuurmans, D. (1997), "Characterizing rational versus exponential learning curves," Journal of Computer and System Sciences, 55, 140-160.

---

Shalev-Shwartz, S. and Ben-David, S. (2014), Understanding machine learning: From theory to algorithms, Cambridge university press.
Valiant, G. (1984), "A theory the learnable," Communications of the ACM, 27, 1134-1142.
van Handel, R. (2013), "The universal Clivenko-Cantton property," Probability and Related Fields, 155, 911 1 1-994.
Vapnik, V. and Chervonenkis, A. (1974), "Theory of pattern recognition," Nauka, Moscow.
Vapnik, V. N. and Chervonenkis, A. Y. (1971), "On uniform convergence of the frequencies of events to their probabilities," Theory of Probability and its Applications, 16, 264-280.
Wiener, Y., Hanneke, S., and El-Yaniv, R. (2015), "A compression technique for analyzing disagreement-baat active learning." " Journal of Machine Learning Research, 16, 713-745.
12

---

A Preliminaries
Notation 1. We denote by N the set of all natural numbers {0, (.. For any n E N. we denote [n] == nn....,n..
Notation 2. For any x > 0, we redefine In (z) == In (x V) and log (z) == log2 (x V 2). Moreover, for correctness, we also adopt the conventions that In (0) log (0) = 0. 0ln (oo) 0log (xc) 0. After then, is reasonable to define 0 In (0/0)- = 0 log (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 e > O such that f(z) S c. (((()))))))))))))))()) for all x E RR. For example, In (I) S log (r) and log (z) S (z)).
Notation& 4. Let X be an instance space, we write hal-o's and halll's denote the hypotheses that output all zero labels and all one labels, respectively, that is, han-os(z) = 0, honlrrs(x) = 1, Vz E X. Notation 5. For an infinite union of spaces (X) X2 U...) and an integer ks we write Xek to denote the finite union of prefix U.. and write Xz to denote the infinite union suffix (Xx+1 U Xk+2 U...).
Definition 8 (Empirical risk minimization). Let H. be concept class instance space X. For every n E N, let Sn == {(a, w)) (X x {0, 13)" be a set of samples. learning algorithm that oulputs (haine is called an Empirical Risk Minimization (ERM) algorithm, if it satisfies hn E arg min érs, (h) == arg mingents t/ Ei=1 1 [h((s)) # y:) for all n E N, where érs., (ha) is called the empirical error rate of hn Sn. It is clear that érs, (h.)) = 0 when P E RE(H).
B Detailed examples
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 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 complements to Proposition 2 in Section 4.
B.1 Details of examples in Section 1.1
We provide direct analysis 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 case where extremely fast universal learning is achievable, but where some bad ERM algorithms can give rise to arbitrarily slow rates.
Example 7 (Example 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 have
E errp(hn))
S P(3h E ::: :erpphh) > 0, ér,,, (h) 0)
union bound
Σ
IP (érr,, (h) =0) 0)
he Hzerp (zerp(h))
Σ
(1 (1-err(h)))
he (t)p
[H|
(1-
heHierp(h)>o erp((1)
min
( erp(()) (- min
H exp
n
Example 8 (Example 2 restated). Let HirreshN == [h+ : N) be the class of all threshold classifiers on the space of natural numbers defined by he(x)) == 1(x 2 1). Hitrrsh is universally learnable at exponential rate since this concept class does not have infinite Littlestone tree
13

---

(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 hy- E 3s be the target hypothesis. Given a dataset Sn, let hig = (RR((S.) be the output of an ERM algorithm. For any realizable distribution P satisfying P((t, for all t < t² and P( 1)} = for all t 2 t,, we define
4 == max {1 < :<=::(()) > 0}.
According the definition of threshold classifiers, if the dataset Sn contains at least copy of both t and t", then ( = 0. Therefore, we have
E [ler S (erp(hy) > 0) (1 (1-)) + (1 (1- P(4))
Note thatfor any E (0, 1 Ese it follows immediately that
T [(err(ha)) & (1 (1- P(1))) + (1- P(4))) S -nP()) + -nP(()) < 2e -=min(((("))P()))
However, let us consider distribution P satisfying P((t, 0)} = Note that P is also realizable with respect to Hawresh, according to the definition, that is
2- and P((t, 1)} = 0 for all e N.
inf Hi
(h)(h) inf (hr inf 2 0. EEN
SEN
Given dataset S., = (11, 1)) Pm, let in max Iy be the largest point in the dataset, it is straightforward that the worst-case ERM outputs h 1 and we have that
E erp
Σ
maxx; =
Σ 2-1 [11 (1-2- (1-2-(1-1)) {
(iE/m]
121
On one hand, we can lower bound the above infinite series by
E [1
-1-2- (11-2))"((1-22(-1)) (1- - -11-2(0-1)) "]
121
[log
2 2-1-1
1=1
lo
(1-27t)" - (112-1)-(1122-11))) (1-2-((-1)]]
2
2n
[=1
1 for infinitely many n.
2
2n
18n'
This implies that Hohresh. is not learnable by ERM at rate faster than 1/n. On the other hand, we have the following upper bound for all n.
2 (11---))-11-2---111 2
& de n ++11 1
21
121
which implies that Hahnesh is indeed learnable by ERM at linear rate 1 1/n. In conclusion, Hohresh, universally learnable by ERM with exact 1/ 1/n rate.
Example 9 (Threshold classifier on R). This example serves as a complement to Example Here, we show that ERM algorithms can sometimes be optimal for universal learning. Specifically, let Hyhvesh. = (he : R be the class of all threshold classifiers on the real line defined by hx(x)= 1(x > t), Vx E R. It has been shown that H is universally learnable with optimal linear rate (Schuurmans, 1997).
To show that Hawees.B. is also universally learnable with exact linear rate by ERM, we only need to prove an upper bound. To this end, let h4- E H be the larget hypothesis. For any realizable distribution P sutisfying (( 0)}
for all 1, < 1' and (( = for all I 2 1", dataset Sn and E (0, 1), let h = ERM((.) be the output of an ERM algorithm. Now we define A and B be the minimal regions left and right to t" E RR such that ((A) P(B) If at least one of A
14

---

and B does not contain any sample, then the worst-case ERM can output hg E Hahresh such that erp(h;) 2 c. Therefore, it follows that
I [(erp(hi)]= = PP (eer((())) 2 2 S { 2 < 2e deme S 220mdd {
2 n
Note that such analysis is also applicable to the realizable distribution with the target concept hatt-Os- Therefore, we have that Hitresh, is universally learnable by ERM with exact rate 1/n.
Example 10 (Example 3 restated). Let X = M and define H Haingleton. == (hĄ- t. E X be the class of all singletons on X, where hz(z) ;= [(z = for all x E X. is clear that VC(H (Ciisingteoonn) = Note that Haungleton,3 N is universally learnable at exponential rate since it does not have infinite Littlestone tree (Actually, we have LD (Hainglesonn)) = 1). In the following part, we show that the worst-case ERM algorithm has an exact universal rate log (n)/m..
To get the exact rate by ERM on universally learning Hsiiggiton... we consider marginal uniform distribution over {1, ........... .1/c] with all zero labels with E (0, 1), if the dataset S,, does not have a copy of a point S x S 1/e, the worst-case ERM can label at a, and thus has an error rate (br) 2 c. Based on the Coupon Collector's 's Problem, we know that to have B[erp(hn)] S G, we need n - logl="log((//0 1/c)). In other words, Elerp(hn)] 2 Q2 ((og)), that is, Haingleton. 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
Uvex Nr be the disjoint union of finite sets with
[& = 2'. For each i E N, let
Hi = (hs 1s: S X2
and consider the concept class H = USEN H4. In the following part, we show that the worst-case ERM can be arbitvarily slow in learning this class.
Given any rate function R(n) + 0, let {nete11 and (ie)e21 be two strictly increasing sequences such that {pr- ;= 24 2/n,, vt 2 1} satisfies
(pe is decreasing
Σn pc S and pt 2 4R(n)).
121
We consider any ERM algorithu with the following property: if the data Sn, ((.,,)))< satisfies
= 0 for all E [n), outputs hn E Hir, with
T, = min {t: 3h Hi, s.t. h(x)) =... -h(x)) = 0}
We construct the following distribution P:
P((x, -2 for all x E Xi, t E N,
where we set P((2 0)} 1 1-E1>1 Pt for some arbitrary choice of USEN Nr. Since
inf (h) inf inf err(h) S inf err()x)) inf err()xx)) inf P : x [x) =0, hE
KEH
VEN
WeEN
SateN
we know that P is realizable with respect to H. Finally, we claim that the ERM defined above behave poorly on P by showing (her)(h,)) R(n) for infinitely many n. To this end, note that for a dataset Sm, (1 9i) 1 pis, and for any f. E N, it holds
(T,,, 2)2P((E [n.] :2 E &.al 22 =P
Σ 1a, 52
2
15

---

where the last inequality follows from the Markov's 's inequality. Therefore,
(hm)
z
2R(m)) IP
(er((mm)) 2 2R(m))
2 4R(me)
1 erp(hnn) TPh)
2R(n)) IP
IV I Ma
1
2R(nt) IP
(ep(hmm))
2 pp Tn, St PTn. St)
2R(m)) IP
(er((hm)) 2 pP The S1 P (Tne S1)
1
2R(n)) IP (TT,, $
R(n.).
B.2 Optimal universal rates versus exact universal rates by ERM
In this section, we provide evidence that ERM algorithms cannot guarantee the best achievable univer- sal learning rates. Recall that the optimal universal learning rates and the associated characterization have been fully understood by Bousquet 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 if does not have 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 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 infinite Littlestone tree, and thus can be universally learned with optimal exponential rate. However, there exists a class H. having infinite eluder sequence but no infinite Littlestone tree (see Example 12 below). This implies that such class cannot be universally learned by ERM at rate faster than 1/n, but can be learned by some other "optimal" learning algorithms at em rate.
Every branch of (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 concept class that has infinite star-eluder sequence, but does have an infinite VCL tree (see Example 14 below). Furthermore, there also exists concept class that has an infinite star-eluder sequence, but does 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 1/n or even e- 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 rates.
To summarize, able to illustrate all the distinctions in the following table.
16

---

Optimal rate
Exact rate by ERM
Case
Example
en"
I/n
infinite cluder sequence but no infinite Litrlestone
Example 12
e-
log (n)/n
infinite star-cluder sequence but no infinite Litrlestone tree
Hxample 13
e en"
arbitrarily slow
infinite VC-cluder sequence but do infinite Littlestonc tree
Example 15
1/n 1/n
log (n)/n
infinite star eluder sequence but no infinite VCL.
Example 14
arbitrarily slow
infinite VC-oluder soquence but no infinite VCL
Example 16
Example 12 (Infinite eluder sequence but no infinite Littlestone tree). A simple example is given in Example 8, where H = Hitreshh is the class of all threshold classifiers on N. Note that H does not have an infinite Littlestone tree, but any infinite sequence {z1,, 0), (),.0),.... with Iı < 22 < <... is an infinite eluder sequence of H centered at han.d's In particular, hanl'ss the only realizable target that allows an infinite eluder sequence. In other words, for H. all the realizuble distribution with target concept h* E H is universally learnable by ERM at exponential rate, except that special one hall-O's. which matches our analysis within Example 8.
Example 13 (Infinite star-eluder sequence but no infinite Littlestone tree). Ler N' x= UkEN Nx be the disjoint union of finite sets with [Xg] and H. == Uw2i Hy, where Hy := {42 : E N. Note that this is exactly singletons on an infinite domain and we have the following hold:
1. H does not have an infinite Littlesoone tree since for any root x X. the subclass {h E H. h(x)) =1 has only size I, and thus the corresponding subtree of the Littlestone tree must be finite.
2. H. has infinite star- star-eluder sequence. Indeed, any infinite sequence {(x11 0), (I2, (z22,0),.. O)....} with I E N's for all k 2 1. is an infinite star-eluder sequence. To see this, note that for any k E N, and any Tuk the version space VnL (H) contains Uyzme Hy. Therefore, (( 0), (Ing+ +. O),..., .,.,, (Ing+h, kk, 0)} is star set of (H) centered at hano's wit- nessed by concepts {1l (um,++)) ): (2bo.t ( [(ng+21h
Example 14 (Infinite star-eluder sequence but no infinite VCL tree), Let X₂ and H1 be defined in Example 13, let X₂ R. and H2 = Hihnesh. R. be the class of all threshold classifiers on R. Note that Ho has an infinite Littlestone tree. Now we define X = == X1 U X2 and H == Hi U H2, and have the following hold:
1. H does not have an infinite VCL tree since for any fixed root x E X, the subclass {h E H. h(z)) 1} has VC dimension only 1, and thus the corresponding subtree of the VCL tree
must be finite.
2. H has an infinite star-eluder sequence (see Example 13).
Example 15 (Infinite VC-eluder sequence but no infinite Littlestone tree). Let X' = -UEEN Nx be the disjoint union of finite sets with [X4]] = k and H. = U221 Hy. where H4 := {1s : S C Xx We have the following hold:
1. H does not have infinite Littlestone tree since for any root X, the subclass {h H iu fx(x)) = 1} is finite, and thus the corresponding subtree of the Littlestone tree must be finite.
2. H has infinite VC-eluder sequence. Indeed, any sequence {(x11, 0), (x2, 0), (rz,0),... .), with knutls.... Tng+k E Xx for all k 2 1, is an infinite VC-eluder sequence. Furthermore, it has been argued that VC((L) oo (Ex.2.3 Bousquet et al., 2021), which is consistent with our Lemma in Section 4.
Example 16 (Infinite VC-eluder sequence but no infinite VCL tree). Let X, and Hi be defined in Example 15, let X2 = R and H2 Hatresh, be the class of all threshold classifiers on R.. Note that Hy has an infinite Littlestone tree. Now we define X X1 X2 and H = H4 Hz, and have the following hold:
1. H. does not have infinite VCL tree since for any fixed root X, the subclass {h
H : hxx)) = 1} has a bounded VC dimension, and thus the corresponding subtree of the VCL-tree must be finite.
2. H has an infinite VC-eluder sequence (see Example 15).
B.3 Star-related notions
In this section, we provide examples to distinguish between the following star-related notions: star number zx (Definition 4), the star-eluder dimension SE(H) (Definition 9), star set (Definition 4) and star cluder sequence (Definition 6).
17

---

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 6 oo 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) xo and infinite star-eluder sequence are not equivalent as well. For comparison, we recall that E(H) = infinite eluder sequence, and VCE(H) oc is equivalent to an infinite VC-eluder sequence (see discussion in Appendix C).
Do is equivalent to an
Example 17 (Infinite star number and infinite star-cluder sequence with different centers). Let us recall Example 3, where Haingteton is the class of singletons on natural numbers. According to the analysis in Example 13, we know that Hssingleton.3 has an infinite star number of hall-O's. and also an infinite star-eluder sequence centered at hallO's-
Now slightly change the setting: Let X = UKER Nx be the disjoint union of finite sets with
Xel = l (one may simply assume X = N). Denote Xn 11 FK.k) } and define ha,
[r = Tkgi or x $ Nx),for all S S K. We let 7 = (1x,6, k N, S. S k}, and have the
following hold:
1. Shasos 00: Given arbitrarily large integer k. {[ 0), (Zx.2, O),... (I 0)} is star
set centered hall-O's witnessed by hypotheses {hg,is 1 < S k).
2. Sharss = oo: Given arbitrarily large integer k. {(I1,1, 1), (T2,1, l)..... (IN.11 1)3 is star set centered hall-rs, witnessed by hypotheses (h4,2, S k).
3. A has an infinite star-eluder sequence centered at hall-ry: Indeed, {(1111 (I21, .).... is an example of infinite star-eluder sequence.
4. H does not have infinite star-eluder sequence centered at hau.0's
Example 18 (Infinite star number but no infinite star set). We slightly change the setting in Example 17: Let X := UKEN X₂ be the disjoint union of finite sets with |&&l = k (one may again simply assume X == N). Denote Xx == [.g.1...... Fg.R), ), let ss.)))) == 1ax = FR,s or x E X>x),, for all 1 < S k and k E N, and let H == (he,, 1
k. h: E NJ. We have the following hold:
1. S = oo since H has a star set of arbitrarily large finite size.
2. H does not have an infinite
set.
It is worthwhile to mention that in this example, H does have an infinite star-eluder sequence {(x1,1.0), (22,1. 0), .).... centered hanLo's Hence, an infinite star set an infinite star- eluder 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 = UbeN X₂ be the disjoint union of finite sets with [2 (one may again simply assume X == N). Denote My- {0k.1..... ,Ikkk let hx,(() 1(x
Ik,i or x E R2 for all 1 < < l and k E N. and let H. = (hr. S K. E N}. Then the following hold:
1. SH = oo since H has a star set arbitrarily large finite size.
2. H. does not have an infinite star-eluder sequence, and SE(H) < oc.
Example 20 (Infinite star-cluder dimension but no infinite star-eluder sequence). For any l E N. let Xxs := UseN Xx. be disjoint union of finite sets with [Rtal = k for all 1 E N. Let X' = UKEN Xx also with disjoint subspaces {K For notation simplicity, let us denote X2, = (Kh.e,l.... ( for all k. I E N. Now we can define a hypothesis class as follow: let
h (x) 11(x IKas) (x Xn.>a) V (x E Xxx) for all k, E N and 1 < j S k, and let
H = (hr,es 1 S Sjsk, k, NJ. We have the following hold:
1. SE(H) = 0o since for arbitrarily large E M, has an infinite k-star-eluder sequence Xx with all labels O.
2. does not have an infinite (strong) star-eluder sequence.
18

---

Remark 11. Altogether, we have the follow relations
Bx
Ex.0
H has an infinite star set
SE(H) = 000
E8.18
Ex.
Ex.19
H has infinite star-eluder sequence
9:
Exc 19
Remarkably, complete theory to the relations between these notions is still lacking here, which might be of independent interests.
C Fine-grained analysis
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 analogy the optimal fine-grained universal learning curves studied in Bousquet et al. (2023). Our characterization of the sharp distribution constant factors is based named the star-eluder dimension or SE dimension and the VC-eluder dimension or VCE dimension. We present their formal definitions first.
newly-introduced combinatorial dimensions
Definition 9 (Star(VC)-eluder dimension). Let H. be concept class, say H has an infinite
d-star-eluder sequence ((11,11), (I2, .... centered at h, if it is realizable and for ev- ery ks E N, {Ikd4I,.... Ikd+d) ) is a star set of Vka(H) centered h. Furthermore, the star-eluder dimension of H. denoted by SE(H), is defined to be the largest integer d 2 O such that H. has an infinite d-star-eluder sequence. If H. does not have any infinite 1-star- eluder sequence, we define SE(H) 0. for arbitrarily large integer d, H. has an infinite d-star-eluder sequence, we define SE(H) = c0.
d- -VCCelluer sequence ((11, v1), (12, 12) 82)...... centered at h, if it is realizable, and for ev- ery ie E N, h(xx)) = yı and [xad+1..... Fkd+d } is a shattered set of (Ha(H). Furthermore, the VC-eluder dimension of H. denoted by VCE(H), is defined to be the largest integer d 2 O such that H has an infinite d- d-VC-eluder sequence. If H. does not have any infinite 1- I-VC-eluder sequence. we define VCE(H) O. ffr arbitrarily large integer d, H has an infinite d-VC-eluder sequence, we define VCE(H) CO.
Remark 12. We recall that the eluder dimension E(H) in Definition represents the length of the longest eluder sequence that exists in H. Indeed, an eluder sequence is exactly one branch of Littlestone tree, and thus E(H) < co 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, 2023). Indeed, an infinite (strong) VC-eluder sequence is exactly one branch of a strong VCL tree, and an infinite d- L-VC-eluder sequence is exactly one branch of an infinite d-VCL. tree. Since an infinite I-VCI--tree exactly an infinite Litlestone tree, infinite I-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 cluder sequence.
Remark 13. For any concept class H. the following hold:
1. E(H) > SE(H) VCE(H).
2. VCE(H) 2 - SE(H) 2 - E(H) = co.
3. VCE(H)
SE(H) -
E(H) DG.
19

---

We then state the formal definition of the fine- the-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
H. is universally learnable at fine-grained rate R by ERM, if for every distribution E RE(H), there exists a distribution-dependeni rate X(n) = o (R(n)) such that every ERM algorithm, Elerp(h,,) S R(n) + X()), for all nt E N.
H. is not universally learnable at fine-grained rate faster than R by ERM. if there exists
distribution P E RE(H)) such that there is an ERM algorithm satisfying (ler 2 R(n), for infinitely many n. E N.
H is universally learnable with exact fine- grained rate R by ERM, if is universally learn- able at fine-grained rate R by ERM, and is not universally learnable at finegraine rate faster than R by ERM.
Note that the crucial difference between this definition and Definition 2 is that here R(n) is indepen- dent of the data distribution P. other words, the fine- aeeegraaied rates provide optimal distribution-ffee 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 is universally learnable at fine ereiggraied rate (no faster than) R by ERM, then it universally learnable at rate (no faster than) R by ERM as well. Briefty 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
learning curves, light up to numerical constant factors.
We now turn to state our results of fine- ane-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] 2 3, the following hold:
If VCE(H) oc, then H is universally learnable at fine-grained rate VCE(H) log and is not universally learnable at fine-grained rate faster than VCE(H) by ERM.
If SE(H) < oo, then H is universally learnable at fine-grained rate VCE(H) log VCE(H) )
SE(P))
but is not universally learnable at fine tne-ggained rate faster than VCE(H)+ (SE(H)) by ERM. or equivalently, there exist finite numerical constants ax B >> 0 such that VCH(H) < oo, then
VCE(H) for infinitely many n E N,
E (erp(ha) 2 a. E [err(h)))
(1)
SB. VCE(H) log +2-1m/2nJ Vn E N,
(2)
n
where = (P) is distribution-depeneeen constant.
SE()) < 00, then
2a. VCE(H) + logg (SE(H)
E (rr((ha)
for infinitely many n E N,
(3)
<B. VCE(H)
log VCE(H) )
SE(H)
E eerp(hm)
+2-Lm/2A
An E N.
(4)
where R = R(P) is distribution- constant.
Remark 15. Our proofs use 1/20 and 3 160.
Remark 16. When SE(H) = VCE(H) = 0, E(H) < oc, or SE(H) = VCE(H) = 1, E(H) = co. we still have the bounds (3) and (4) since we define log (0) 0, 0 (0/0) = 0 and log (z) = log (z V 2) for any x 0. Moreover, we remark that neither VCE(H) = 8o nor SE(H) = ca is considered in these fine-gruined rates. This is because when VCE(H) = oo, arbitrurily slow rates cannot admit distribution-frer constants. And when SE(H) = co, 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.
20

---

Remark 17. It is not hard to understand that carget-speciffer version of rates by ERM is also derivable, based on a centered version of the star-eluder dimension SE and VC-eluder dimension VCE..
universal
Remark 18. It is worth noting that, when SE(H) < cc, there is mismatch between the lower bound and the upper bound. This serves as an analogy to the mismatch between Cor. 12 and Thm. 13 in Hanneke (2016b), and certain demonstrating examples have been exhibited in Hanneke and Yang (2015), In the following two examples, we provide evidence that such a gap does exist, in a sense that both the upper bound and the lower bound can sometimes be tight for some classes. Roughly speaking, if an infinite SE(H))-star star-elderr sequence in H is also an infinite VCEE(H)-VC-elunn
sequence (see is the optimal rate, otherwise VCE(?)) (SE(30) is optimal. VCE(R)
Definition 9), then VCE(H) log
SE(H)
n
Example 21 (Optimal (VCE(H) + log (SE(H)))/ rate). We construct concept class H such that an infinite VCE((H)VC-elunn
sequence and an infinite -tar-eeerr sequence cannot be realized by an infinite sequence. To this end, we slightly change the example presented in Appendix D.2 of Hanneke and Yang (2015), which yields the tightness of a lower bound (VC(H) + log (sx))/n.
Specifically, let d, s >> O be two integers satisfying d S. Let == 2 \(0} == X1 U X2, where
X1 := {0} and X2 := -N {0} -X1. We can also write
X1 = (Ki.D U 11, U..... where X1,k == fkis + 1,.... (k + 1)s} for all l E EN,
X₂2 (N2,0 U 2 U... U...). where &2,2 == 1 + 1)d................. kdd - for all & E N.
Now we let H = Hi, U H2 satisfying VCE(H) dl and SE(H) = 8, where
Hi = (1i.. : VVj E Ki, Vk E N), where hx.(()) = (sx = or E x)
H2 == (hx,s VS S N2, E N}. where hx,s(x) == 1(x E S or I E 22,2k).
In particular, X1 itself is infinite s-star-eluder sequence centered hall-'s and X2 itself is infinite d-VC-eluder sequence, but they do not intersect. To show that the upper bound can be decreased match the lower bound, simply note that for any infinite s-star-eluder sequence, its associated VC-eluder dimension is exactly 1, resulting in a log (s) n upper bound. For any infinite d-VC-eluder sequence, its associated star-eluder dimension is also d, resulting in d upper bound. The maximum of the two upper bounds yields the desired one.
Example 22 (Optimal (VCE(H) /n) log (SE(H)) /VCC(())) rate). We construct a concept class H. such that there exists an infinite sequence in H which is both an infinite (CE(H))-C-eelud) sequence and an infinite -ttrree-rrr sequence. To this end, we slightly change the example presented in Appendix D.1 of Hanneke and Yang (2015), which yields the tightness of an upper bound (VC(H)/)) /n) log ($x/ (V))).
Specifically, let d, s > 0 be two integers satisfying d I s. Let X : and for every k N, define for
hg.s(() = 1(x E S or x > (k + 1)s) for every subset S S +1... (k 1)s} with [S] S d. Let H = (ha,s : S C (ks 1,..., (k + 1)s},1S1 S d, k E N). Note that for this class, we have VCE(H) = d, SE(H) = and there exists an infinite sequence serving as an infinite d- L-VC-eluder sequence as well as an infinite s-star-eluder sequence. To show in this case that the lower bound can be increased to match the upper bound, the realizable distribution that witnesses this rate is referred to Appendix D.1.1 of Hanneke and Yang (2015).
Now let us turn to the proof of Theorem 8, which is based on the following two lemmas and within each an upper bound as well as a lower bound are established.
Lemma 10. For every concept class H with [H]| 2 3, if VCE(H) < <0,, then the following hold:
2 VCE(H) for infinitely many n E N,
E [err(hh)) E (erp(hm))
18n
28VCE(HH) log +2-1n/2k), Vn N,
<
n
where k= = k(P) is distribution constant.
Remark 19, Note that a concept class with its VCE dimension finite can either have infinite star-eluder sequence or not, which results in a difference (of a logarithmicface in the upper bound and lower bound stated in Lemma 10.
21

---

Recall that VC(H) < 3o yields a uniform upper bound (C(H) log (n)/n. n. On one hand, VCE(H) oo implies that H. has shattered set of arbitrarily large size. which further implies an unbounded VC dimension. On the other hand, according to Lemma 9, VC(H) = x implies that H has an infinite VC-eluder sequence, and thus VCE(H) = do holds as well. Therefore, VCE(H) = oc if and only VC(H) do if and only if H has an infinite VC-eluder sequence. Moreover, when VCE(H) < co, trivial observation is VCE(H) & VC(H) < oo. However, the following example reveals that VCE and VC are not the same dimension, namely, there exists class H having strictly VCE(H) < VC(H) (see the following Example 23). Therefore, Lemma 10 sometimes reflects an improvement over the classical uniform bound.
Example 23 (VCE(H)) < VC(H)) < co). To make it more convincing, we provide an example of infinite classes here. Let X1 be finite set of size d, and X₂ be an infinite instance space that is disjoint with X1. For simplicity, one may assume that X₂ == { {-d.- - (d 1)...., -.,,,,1, and X2 == N. (s) 4S _ X, vk &N.. This class has VC(H) (d 1) but VCE(H.) = since there is infinite 2- VC-eluder sequence. Similarly,
We define X == X1 U X2 and let H == {hg
can also construct an example that witnesses strictly SE(H) < 5y < cc.
Lemma 11. For every concept class H. with 1H1| 2 3, if SE(H) < co, then the following hold:
log (SE(H))
E (er((hn)
N
for infinitely many n E N,
12n 160VCE(H)
SE(H)
E erp((n))
log
+ 222 Vn E N,
VCE(H)
12
where R= = R(P) is distribution-dependee constant.
Remark 20. Note that in Theorem 8, the lower bound appears as VCE(H) Hog (SE(H)) n SE(H) < oc immediately implies VCE(H) < oo 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. a = 1/20.
Indeed,
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.
Example 24 (VCE(H) < log (SE(H)) < oo). Let X = ULEN Xx be the disjoint union of finite
sets with [2g] = d < co. We denote Xx := {. ., d. for every k E N, let hx. (x) (2))== 1fx
for
Ik.j or x: E ), for every & E N and every 1 S j d, and finally let H == [hk.j. S $ S d,
N). For this class, we have VCE(H) = 2 < log (SE(L)) = log d for a sufficiently large
Example 25 (log (SE(H)) < VCE(H)
oo). Let X UsEN Xx be the disjoint union of finite sets with [&&] = d < co. We denote Xs= := "Uk.I....,KR,A for every & E N, let ha,s(x) == 1(x e or x E Xxx). ). for every & E N and every subset S C Xz. and finally let H. == (hr,s, S C Xx. l e
N}. For this class, we have log (SE(H)) log d < VCE(H) d.
D Proofs
D.1 Omitted Proofs in Section
Proposition 3 (Proposition 1 restated). Any infinite concept class H. has either an infinite star-eluder sequence or infinite Littlestone dimension.
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 { (1), (I2, v2),..., .. if it is realizable and for every integer k, there exists h E H such that (xx) = Yi for all i < l and hx(x;) + ys for all i 2 k. We say an infinite threshold sequence {(11, 91). (x2, y2)..... .} is centered at h, if hfx))) = for all E 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 slarerluder sequence. Morcover, infinite threshold sequence
22

---

> j. Since hi, (2i.)) implies that {(I., Mr, ), (Zig) V:2)....) .... is an infinite star set centered at h", witnessed by {hi, Jeen- Moreover, if the infinite subgraph comprised of the vertices {iz, ......} is monochromatically blue, gives rise to infinite Littlestone dimension since H. can have Littlestone tree of arbitrarily large depth (an easy example is H.hresh.y). Therefore. 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 's theorem states that one will find monochromatic cliques in any edge labelling (with colors) of sufficiently large complete graph. Specifically, let be an positive integer, simple 2-colors version of the Ramsey's '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 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 '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 I. Based on Lemma 8, we know that any infinite class H has an infinite eluder sequence. Let [(11,91), (2gg (2).)))...) be an infinite eluder sequence centered at h", that is, for any j E N. there exists h2 E H such that hy (z;) y/i ht (a;) for all i < and hy (2z) # yj = h² (I₂). (Iig. Vo.)..... that is either an infinite star set centered at ht an infinite threshold sequence centered at k". To this end, we consider the infinite eluder sequence {(21. Y1), (2'2. v2)....) as a audbllue coloring of an infinite complete graph according to the following: let the vertices be indexed by N, then for every edge ex, with integers >> j. we color it red if (x,) = yı and blue otherwise.
We aim to show that there exists an infinite subsequence {(
Note that for any infinite subsequence {(x Ui,) ). (Zig, ( Vig),...) if the infinite subgraph comprised of the vertices (2....... - is monochromatically red, then (1...) = 1/., = h² (2...) for all integers Vi, h- (2),,) for all integers < j and (x.,,) + Vi, h (ai.) )
it is not hard to verify that { [ ). (Zi, Ve. )..).... is an infinite threshold sequence centered at h The proof is completed by applying the infinite Ramsey's 's theorem.
Lemma 12 (Lemma 1 restated). Given a concept class H. for any learning algorithm h there exists realizable distribution with respect to H such that Blery(h,,) 2 2- 2-(m+)) for infinitely many which implies that H is not universally learnable at rale faster than exponential e-
Proof of Lemma 12. We prove the lemma by using the "probabilistic method". Let us consider non-trivially that [H] > 2, let h1, h2 E H and x, x E X such that hy (x) = h2(x)) = y/ and h, h1 o hz(x'') ). Now for any learning algorithm hen we define the following two realizable distributions Po and PI, where P: Pr((x, y)} = 0.5 and Pzf(2', f)} = 0.5, i E {0, 1). Let I ~ Bernoulli(0.5) and conditioned on I, let Sn := [211 31), ). (2-2, y2), ., (In, fn)} and (In+1, Vn+1) be i.i.d. samples from P1 that the learning algorithm hn is trained on. We note that
E [P (ho(En+1) # IS.. 1) 2 1 p(( ==== In = x, Int1 = x') = 22((+2)
2
Furthermore, by the law of total probability, we have
E iP (Zn+1)) # Bntzl AnttaSmn.1
1
Σ
EE [P (Zn+1) # Untz|Sm1 1 = =)) | ==
= 2
E J ((n(( F Un-1|Sny I - 1) -1) [=
< max
(0(0,1)
The above two inequalities imply that for every n. there exists in E {0, 1] such that
E [ ( (2)+1) * yo+ Sm,, - in || = in] = E[erp.,, (fm) ) 2 2 (m+22
In particular, by the pigeonhole principle, there exists i {0, 1) such that in i infinitely often, which completes the proof.
Lemma 13 (Lemma restated). H does not have an infinite eluder sequence centered at he, then h" is universally learnable by ERM at rate e en
23

---

Proof of Lemma 13. Since H. does not have an infinite eluder sequence centered at h", then for any realizable distribution centered at he and data sequence S := {(2), h (z1)) (z2, h (x2)).....) ps, we have
IIEN. > s.t. ah E Vs, (H) h(xr)) # h1" (xx))) < oc.
For the largest such integer i, we further have P(3h E (H): h(xr)) + ht" (z())) = 1 for some i' = 1' (S) > l. This true because the probability decays exponentially. Therefore, we have
lim PS-Ps (P E X: 3h E V, (H) s.t. h(x) + hº (x=) 0) = 1,
which implies that there is distributionn-dependent positive integer k == k(P) such that IP (P (x: E X 3h E Ví (H) s.t. h(x) + (x:) 0) 2 1/2.
Now for any integer n > k, we split the dataset S, ~ P" into [n/k] parts with each one sized at least ht denoted by s......., Sn. [n/A]- It holds then
(P E X 3h E (H) s.t. h(x) (1)(z) *
<V [n/kk] P Ex X: 3h E Vs.,. (H) s.t. h(x) + (x)))) + 0)
[n/k]
II P ( 3h E V s.t. h(x) + h² * 00) 2 2- Ln/k1
which also holds for S k. Finally, it follows that
E [err((hm)
SP (3h V. (H) (h) > 0)
=P x 3h E Vn, (H) s.t. h(z) # hx())) #0) 2--1n/ Vn N.
Lemma 14 (Lemma 3 restated). 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 ((11,11 )1). (12, ..)....} be an infinite eluder sequence centered at h", we consider the following distribution P: P((x; vi) = 2- and Pf Pf 1 1-1-- y:)} 0 for all E N. Note that P is realizable (with respect to H) with target ht* Given dataset S, == {( 9: ) pa let the worst-case ERM outputs h, ERM(S.) For any N. if Sn does not contain any copy of the points in {a,, > t), we have (h..) 2 - The probability of such event
n
Σ (X, 342...
II P PX, E (a (21...., ..]) (1 - --
Therefore, it follows immediately that
E [(orp((m))
> Σ 2 2- 2 1 2
In'
1=1
where the second inequality follows from choosing t = [log n...
Lemma 15 (Lemma restated). If H does not have an infinite star-eluder sequence centered at h", then he 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 originally stated in Littlestone and Warmuth (1986).
Definition 12 (Sample compression scheme). Let H be a concept class and S, == (I,,, ) A sample compression scheme for HL consists of two maps (k. p) such that the following hold:
The compression map &. takes Sn to T == =(Sn), for some T U y) E S.Y²
- The reconstruction function p takes T to p(T) X - {0, 1}.
24

---

The size of the sample compression scheme (K. p) is defined as maxs,, [xx (0.1))" ((exx compression scheme (K, p) is called sumple-consistett for H. for any realizable distribution P with respect to Ht and Sn := (:)):=1))==1 ~ pr, it holds that érs, (p(k(Sn))) = 0. A sample compression scheme (K.,P) p) is called stable if for every subsequence S' satisfying k(S,) S S' c S.. = ((k(S.))
|k(S,)) A sample
it holds that p(<(S)))+(((({)), that is, removing any non-compression point Sn does not change the classifier returned by the sample compression scheme.
Definition 13 (Version space compression set). Let be concept class and P be a realizable distribution with respect to H. For any E N, and any dataset Sn == {(zi. 3)) ~ Pm, the version space compression set C₁ is defined to be the smallest subset of Sn satisfying Vs,, (H) Ve, (H). Furthermore, we define the version space compression set size as i((S))) == 1c,b which is data-dependent quantity. Finally, we define ui.n == maxigmşn (f(m). which is also data- dependent. However, iimm 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 (?)) be described a compression scheme, where the size of the compression scheme is exactly the version space compression set size f((.))
With these definitions in hand, are now able prove the lemma.
Proof of Lemma 15. Let P be a realizable distribution with respect to H centered at It",, let S. == {(r,, y:) ]:)];= ~ Pm be dataset and C₂ S S2 be the corresponding version space compression set with size |Cal = (.S)). We let (k., p) be a sample compression scheme of size n((S.) defined by R(Sa) Cn and p(C.) hn, Since any ERM algorithm will output predictors {h. NeeN satisfying
hn E (H),, is clear that
érs.. (o (1 (S,))) = Σ 1
# = Στ (1 # v1 # 3 =0,
and thus it is sample-consistent. Furthermore, let S' be any subsequence satisfying On C c C On one hand, we have (H) C V.s (H). On the other hand, we also have V (H) C Vo, (H)
Vs., (H). Therefore, we conclude Vs,, (H) = Vs (H), and thus p(x(S') = p(x(S,)), that is, the compression scheme (K,, p) is also stable. Now we can apply Lemma 24, and then obtain
[[,)
E (h..) = E [err (p (S.))))
n n+1
Indeed, it has been proved that ((Ss)) < (Thm.13 Hanneke and Yang, 2015), and for complete- ness, 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 5д* < oc. However, 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 = {(11, 31), (xz,, .... ~ P&, there exists data-dependent integer ie := k(S) < oo such that 5n- (Vng (H)) < k. Moreover, we know there exists distribution-dependeed constant factor
k : k(P) do such that k(S) k(P) with probability at least 1/2. By using similar argument in the proof of Lemma 15, we have
E (erp((n)) x k +22 -2-kk/kk (.n.),VVne E N,
which proves a target-specified linear upper bound.
Lemma 16 (Lemma restated). If has an infinite star-eluder sequence centered at ht, then le" is not universally learnable by ERM at rate faster than log (n)/n.
Proof of Lemma 16. Suppose that S ;= {(211 (1), (.2, 82)....) ... is an infinite star-cluder sequence in H. centered at ht,, that is h² (x;) y4 for all i N. For notation simplicity, let Xi := {x1], X2 == {z2, 3, Xx {I1, Fs. 26)...... strictly increasing sequence (kehee that will be specified later, and only put non-zero probability
:= fI Tmg +k).... #x) with n& == (*) We consider
25

---

masses on these disjoint sets As, with t E N. Then, let X := USEN Xx, be a union of disjoint finite sets with | = kig and consider the following marginal distribution Px on X::
Px fx E kx = 2- and (x( = 2-022"/appp Vx E Xx., It immediately implies the joint distribution P P(Px, h*) that is realizable with respect to H: h ((xx = / P (z, 1 - h² (m))) = 0. Vr E Mr.: Vk E N.
P
Now for any n E N. we let Sn == (( y:) ~ pm and consider the event & = El n E2, where
& (S,, does not contain a copy of any point in Nxs }: 8g = (S,, does not contain a copy of at least one point in Xx,
If & happens, the worst-case ERM can output some hn Vs. (H) such that er 2 2 This is because: Vo., (H) C V...kee (H), where Sn,ker contains the samples of S, that falling into Ns. U... Xk,., and then Xx. = (Fnu, +l, Inn, tk. is a star set of Vs.,.ze (H) witnessed by a set of functions, denoted by {/hn, +I,..., Amy, }. In other words, Vs.,te, (H) contains a size-kr "singletons" with point- probability mass 2 2 //k. However, the remaining samples S, n Xx. does not contain a copy of every point in Xx. which results an error rate ( 2 2 1/k, with hn := Am +j for some 1 S S kr.
Hence, it remains to characterize the probability of To this end, we refer to the so-called Coupon Collector's 's Problem, and define a random variable
iu. == min {n N: NR. Spt.
Note that Ωu. can be represented sum Σド= Gj of independent geometric random variables Gj Geometric( ls (--1-22-)) for 1 S j s k2 with
{ where Hm is mh harmonic number satisfying Hm 2 log (m)- Then the standard Chebyshev's inequality implies that (M, Eluu,ll > z) S Var[fuu]= - =²2 By choosing / Var we have with probability at least 1/2,
EE/- k(111)) k2 2t Hk. E [frxul = Σt E [G,]] Σ/= kitl-j =ke 2t
k,-2"
2 1,2.220
Var [mn: Σن Var [Gy] < Σラ= Autl-i2-1)
nk. E [na,] Var [k..] 2 Rig 2t, 1og ke
T
v3
In particular, when h2 2 38, it holds that log he 2 2 / /3,, and thus fikk > 2k log hi with probability least 1 1/2. Altogether, we have for any 2t- k2 log lit
P (E2) 2 P (n- fu..) 2 P( < 2 log 2'- ke log ke < mixe) 2 1/2.
Moreover, to characterize the probability of E note that for any x ~ Px, F(x E Nez.) 2- Kr, which implies immediately that for any n N. P(E) (1 - 2 ke)n Now for any integer Ki 2 38, we let n = 2' log kt. and have (for infinitely many n) that
2-1 PP 2 (()))(())))))) 2 21-2-h1)"
PP erpp ( 2 Kt
which implies further
2-1 2 2 P (crp(hn)) E (hm)) 2
kz 2 (1-2-ke) k-)))" =: Tn,t-
k.
Finally, by choosing K. =2(22), we can guarantee that 2 nn, log nnl Applying Lemma 29, have (fer 2 nn. 2 log (n)/n, /n. for infinitely many n. Lemma 17 (Lemma 6 restated). H does not have an infinite VC-eluder sequence centered at h?, then h² is universally learnable by ERM at log (n)/nu n rate.
26

---

Proof of Lemma 17. We first prove that any class 7/. is universally learnable by ERM at log (n) rate
if VHH) < c0. For any realizable distribution P with respect to H, we let S2n == (z yr) |== p2n, and denote S, == [[ )i)) and T, = {(T,, [:)] namely, the "ghost samples".
Given E (0, 1), Lemma 31 states that for any n 2 8/c.
P (ah H érs, (h) and (h) c) 2P (3h H. éts, (h) 0 and er (h) > c/2).
Moreover, Lemma 32 states that for any 2 VC(H)//2
Zen (VCH))
VC(H)
P (3h E H: ets, (h) = 0 and étr,, (h) > e/2) <
2 2
Altogether, we have
P (erp(hn)) > x) S P (3h H crs, (h) 0 and erp(h) > E) 2
2en VC(H)
VC(H)
2 (5)
for any 2 max/8/e, VC(H)/2). Finally, the upper bound on the expectation can be derived via the follow analysis (which will be used several times later): let
2en VCC(H) log VC(H))
+ +1)s
==
and then by letting the RHS of (5) =; 8, we have
VC((H) log
2en (VC(H)) ) + log
(2)) (2)) 6n
2
n
When S En. we of course still have P(erp(hn)) > e) < 1. It follows that for all 2 VC(H)/2.
(erp((n))) / P (erp(hn)) >g >c)de
P (err((n)) > de [ P (err((nm) > >)) de
Jo
/ P
(eepp((n)) > de So (erp((m)) > >c) de
(erp(hh)) > >c) de +
(5)
2en
VC(H)
cn
2
VC(H)
2 2-ne/2
2VC(H)
2en
2 2 2ln
VC(H) log (VC(H))
log
+
VC(H))
n
n
n
For < VC(H)/2, the result is trivial.
Now to prove a target-specified upper bound, let P be any realizable distribution centered at the target concept ht with associated marginal distribution denoted by Px. Suppose that H does not have an infinite VC-eluder sequence centered at h², then there is a largest target-dependent integer d : d(h*) do such that there exists infinite d-VC-eluder sequence centered h², but no infinite (d + 1)-VC-eluder sequence centered at ht* (see Definition 9). We know that there exists a positive distribution-deepeddee integer A = k(P) < such that (PVVC(V((7)) d) 1/2.
We let S, := {(,,, )/ ~ P" be a dataset, and consider the event E,, := [VC(V[m/2)())) (PL) & d}. The probability of this event can be characterized follow: for any π N, assume first > k. we then split the dataset 5n ~ pm into [n/k] parts with each one sized at least k denoted by Su,1y...,
Sn. ....----.... For every < i i [n/k], know that the corresponding induced version space has VC dimension VC(Vs,, (,,, (H() < d with probability at least 1/2. Note that V.(H))
Aisigln/k) Vs.., satisfies VC(V..(Z)) < VC(Vs.. (H)), for every 1 < i [n/k]. Therefore, we have P(VCC(V,(P))) (P)) > d) - IP(1 < < |n/k] VC(Vs.. (7)) > d) < 2- [m/RJ, Note that this bound also holds when < k since probability is always most 1. Altogether, obtain P(-En) = P(VC(V (H)) d) 2- [m|//2k), Conditioning on this event, the previous analysis
27

---

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.
E (erp((m))
= / P (erp((hn) > >))
- L (P (P(erp(ha)) >c ( de S d log + Ln/k| n
11
where both := d(h") and k := k(P) are distributtion-deeendent constants. In conclusion, h" is universally learnable by ERM at log (n)/n rate.
Lemma 18 (Lemma restated). If has an infinite VC-eluder sequence centered at h", then ht requires at least arbitrarily slow rates be universally learned by ERM.
Proof of Lemma 18. Let S == {(x1, 31), (I2, ..)....} be an infinite VC-eluder sequence in H centered at h", that is, h² (x;) ys for all E N. We inherit the notations used in Lemma 5 by letting Xx : ( +1,- ....... [nn++k with ni = (2). for all k N. Let X == Uken X₂. be union of disjoint finite sets with [ggl = k. and consider the following marginal distribution Px X:
Px {a E Xx} = Pk: and Px(x) = Pk/k; Vx E Xx.
where {p& JENN is sequence of probabilities satisfying A>1 1 Pk: S 1 that will be specified later. It implies immediately the following realizable (joint) distribution P P(Px,h*).
P [(x (x))) = pk/k, P 1er,1-h1"x)) = 0, Vr E Xx. Wk E.
Our remaining target is to show that for any rate function R(n) O, 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, = ((1), v:)) Pr. For any & N and any j E [kr], we consider the following event
En,kit.i Snn does not contain copy of any point in Xr., U (Zne, +i}}
where JEe is an increasing sequence of integers that will be specified later. If En,K,.J happens,
then the worst-case ERM algorithm can output some hn E Vnx, (H) such that erp(hn)) 2 pt, /kr, that is the classifier that predicts incorrectly on the "missing" point in Nk. Moreover, to characterize the probability of event En,k.e.j. we have P(En,k,),)) (1 Eksh, Pe Pk./ /²)" Therefore, we make a construction by applying Lemma 30, and finally get for all t E N,
erp (hm..)
2
Σ JE(kg
Pk," PP (Eng,k.t.)) 2 Pk.
1
Σ k>
Pk
Pki
2 Pk:
1
2 -
2 R (ne)
hi
D.2 Omitted Proofs in Section 4
Lemma 19 (Lemma 8 restated). has an infinite eluder sequence and only if [H] co.
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 Iι X such that both V(r,,0)(H (H) == (h H h(x1) 0} and V( (H) (h E H. h(x1) = 1} are non-empty. Such a point Ti must exist since otherwise we will have [H] 1. Furthermore,
know that at least one of them is infinite, since otherwise we will have [7[ < co. We assume, without loss of generality, that 1) (70) h((1)) = 0, h(x2) = 0} and V[(=.. (z,, (H)
Then pick some Z2 X such that both V((z)).)) (H) := {h H.
(h E H: M(x1) = 0. hx22) = 1} are non-empty. Note that such an exists, because otherwise we will have (V .0 (7() < co. Again, at least one of them infinite for the same reason, and then we choose my from that infinite one. Following similar procedure, we can get an infinite sequence {(æ1, y1), (I2, V2) ..... where {2... are chosen to keep the separates of version space non-empty, and {g), 12. .2...., ... are chosen to keep the version space infinite. Now note that for any E N, we can find some h; E Vs, (H) * 0, where
S. (#1, ; y1), (x2, --2),.... (z4-1, 1i-1), (r,, y:)). According to Definition 5, we know that ((11 (1), (x2, v2), is infinite eluder sequence consistent with H.
D
28

---

Lemma 20 (Lemma 9 restated). H. has an infinite VC-eluder sequence if and only if VC(H) = co.
Proof of Lemma 20. According Definition 7, the necessity is straightforward, i.e. we must have VC(H) oo if H has an infinite VC-eluder sequence. It remains to prove the sufficiency, that is, VC(H) = oc yields the existence of an infinite VC-eluder sequence.
We construct an infinite VC-eluder sequence via the following procedure: Let I E X be any point, then least one of (((e,00) (H) and V((z..1))(H) has infinite VC dimension, which is because otherwise H. ((1 (H) U ((1),11-1)) will have finite VC dimension based on Lemma 28. Let y1 E {0,1} such that Vi (H) has an infinite VC dimension, and let {.2, 233 be shattered set of V((a an) (H). Similarly, we know least one of the follow- ing four subclasses V((zr. (1 (xr.)))))) (H), ((11..8))
(H), V( (oa.) (H). Vi( ( (e2.1)). (=). (H) has an infinite VC dimension since otherwise VC(V ((((()))))))) (?0) < 0o
will lead to a contradiction. We then pick labels 1/: M/ E {0, 13 such that (( (22.))))))). (H) has an infinite VC dimension. For notation simplicity, let = {(11, 9/ (222 y2), y2)....) and let meg = ( Inductively, for any & E N, if -5 +(k-- (H) Vs... (H) has an infinite VC di-
mension, let {Ia,+1:......................... In + be shattered set of Vs., (H). Lemma 28 yields the existence of set of labels (Im.+1....,,an Otherwise,
{0, 13 such that Vs V (H) has an infinite VC dimension.
VC (Vs.., (7t) = vC
U
Visunn (H) S 2k-44max VC (VS.e11(H)) < oc,
(gmg (e---.-
which leads contradiction! By such construction, the returned infinite sequence (1)1,31) (2), is an infinite VC-eluder sequence consistent with H.
D.3 Omitted Proofs in Appendix C
Lemma 21 (Lemma 10 restated). For every concept class H with [H]] 2 3. if VCE(H) < oc, then the following hold:
VCE(H)
E (er((hn)) 2
for infinitely many E N,
18n
28VCE(H) log + 22- Vn N,
E
((er((hm))
<
where k= = x(P) is distribution-dependee constant.
Proof of Lemma 21. Let H. be a concept class with VCE(H) = d < co. Note that when VCE(H.) 0, the results hold trivially, and hence we consider only d 2 1 in the remaining part of the proof.
To show the upper bound, let P be realizable distribution with respect to H. and for any N, let S, = ((I1,11)..... w......, (In, }n)} ~ p" be dataset. Since VCE(H) = d, for any infinite sequence = ((11,31), (222.82)..... ) ~ p there exists a (smallest) non-negative integer & = k(S)) < co such that VC)V S d. For any ERM algorithm A, let hn := (s( E V, (H), which can also be written as hn := hn. == AVECH) (Sk+1.n), for every A E [n)] Recall that for any E (0. 1),
using the same argument as in the proof of Lemma 6, we can get
(inn-k)) k)) 2e(n (2(2
P (hr e) 2
2 2n Vn 2 k + max (8/c, d/2).
(6)
d
Now for any n E N. we consider the event &, : (VC(V (H)) S d]. Applying the inequality
P(A) < P(A B) + P(-B), we have
P (hm) > >c) SP (erp(( c(E,) (
(7)
Let the RHS of (6) =: 8 E (), then for the first probability in (7), we have
P ((epp(hm)) > clen) (erp(hn..n/2)) VC (H)) S 5o,
29

---

for all n 2 max (16/e, d] 2
|n/2| + max f8/c, d/2), and also
6
2
dlog
22e(n ( + log ( 2
d dog
)
me t
+1
= c.
(8)
To characterize the second probability in (7), we define k(P), distribution-dependent quantity, to be the smallest integer such that (S)) S x with probability at least 1/2, where the randomness is from the data sequence S. Note that such an integer ń exists since otherwise there will exist at least an infinite (d + 1)-VC-eluder sequence. We then prove:
Claim 2. For any n E N, E() S 2-
Proof of Claim 2. For any N, assume first that 2 we then split the dataset Sn ~ P" into [n/x] parts with each one sized k, denoted by Sn.,,..., Sn,In/kj. According to the definition, for every 1 1-c - [n/k], we know that the induced version space has VC dimension VC(Vs.,, (H)) S with probability at least 1/2. Note that V, (H)) Misisi//e! Vs.,.(H. satisfies VC(V, (H)) S VC(Vs... (H)), for all S i S [n/k]- Therefore, we have
I (VC(V,, (H)) d) S (A1 S is [n/k]: VC(Vs... (H)) > d) 22 In/A],
which also holds when < K. Finally, P P(-E,) = P(VC(V//2))))) (H)) d) S 2 Lm/2a]
Putting together, we have that for all n 2 d.
E [crp(( S 10/m P (erp((on) > de f (erp((bn) > >6) de
fliin
2
{"d P ((etp(bnin//))) > ee(n)) de ( f0//n IP (errp((mnii/1)) > e(E,) de + (( P ((
116/
P ((err((m,.n/2)) > c(e.) de + f (e
"n +
<n +
2
ne
2 g-ne/4 de + de
d
4d
4 + 12 (2)
[-' P(-En) de
$ n
log
n
Claim 2 4d
log
4 + 12 (2)
+ 2-1m//k
28d 28dlog n
2 2112/2
n
n
n
When I d, the upper bound is trivial.
To show the lower bound, let S = { w1); (222 v2).... be any infinite d-VC-eluder sequence that is consistent with H. We denote X == {Ikd [ d+1. Rbdd for all integers k 2 1, and consider the following realizable distribution P:
Med-a4 0, VI S j < d, Vk 2 1, where {p& Ja21 is a sequence of probabilities satisfying Σ.21 Ph S 1, which will be specified later.
P (IRa--44j Uhd (hd-atj)) pa/d, P P
We use similar argument in the proof of Lemma 7, but instead of considering an arbitrarily slow rate function R(n) - O, we consider here R(n) == d/n.. Specifically, let S, == { 3)) ~ pm be a dataset. Note that for any the points in X U {Ind-d+s} == UP Xe U {IIddd+s}, the worst-case ERM can have an error rate (h,, 2 Pk/ d. The probability of such event is PPEL, 1{X, E X U (abd-d+t))) = 0) IT PP(x, & X U (zbd-a-))) (1 E.s P: Pk/d)"
and any j E [d]. if the dataset Sn, does not contain any copy of
Based on Lemma 30, for the rate function R(n) == d/n, there exist probabilities (pl Ja2I satisfying
Σx21 Pk= = two increasing sequences of integers fiat and {m:)211 and constant 1/2 s
C S 1 such that Eksk, Pk S 1/nn, and pk. = C d/n,. Therefore, it follows that for all integers
t > 1 (and thus for infinitely many N),
E erp (lmn.) C. d
Σ n1 12
C+1
d
1
2 m d
n4
2n
T4g
18n,
12
30

---

Lemma 22 (Lemma 11 restated), For every concept class H. with [H] 2 3, if S SE(H) < 00,
then the following hold:
log (SE(H))
E (rr((n))
for infinitely many I E N,
12m
E (rp((hm)
160VCE(H)
log VCE(H)
SE(H)
+ +22-1/2281 Vn E N,
)
where i- = P(P) is distribution-dependdddd constant.
Proof of Lemma 22. Let H. be a concept class with SB(H) = < oo and VCB(H) = d < xc.
To prove the upper bound, let P be realizable distribution with respect to H. centered at h. and for any n E N. let S, == ((11,)1)......... 91)..... (In: Bn)] ~ Pa be a dataset. Indeed, distribution upper bound for any consistent learning rule has been proved in Hanneke (2016b) (see Lemma 26 in Appendix E), which states that for any E (0, 1) and any n E N, with probability at least 1 - 8,
8 (VC(2)) n
49ESA
6 8 )))
sup ( (H)
+ +77 + 8 In VC(H)
Since H. does not have an infinite (d + 1)-VC-eluder sequence, and also does not have an infinite (s + ))-star-eluder sequence, for any infinite sequence S = {( 3n), (222, y2),.... cxists a (smallest) non-negative integer & = kSS) < oo such that VC(V)(H)) I d and (V)(())) S Following similar argument in the proof of Lemma 10, we define A R(P). a distribution- dependent quantity. to be the smallest integer such that k(S) S & with probability at least 1/2, and then consider the following event &, [VC(V[n/2]( (H)) S d, su (Vin21) (H)) S 8) with probability E < 2 2l1m/281, For notation simplicity, let us denote by en = {(d In 49cs + +7) + 8 In (6)), then conditioning on En, we have that for all E N,
PM there
sup (hn)) = =f0 P (err((hn) > de (n))).(
E
P (erp(hm)) > $l e(En) de
PP (((En) de
+
0
((erp((i)) > >((n) de ( TP ((Ex) de
P
(fr
> 6 En
de
P
Jo
S En
+
6exp
d
ln
49cs
+ 37
nC
de + 1m/22
8
d
64
cn
384
exp
d
In
49es
+ 37
nEn
+ 2 |n/2a]
d
64
8
49es
64
dln
+37
+ 37
+ 88 In (6)
+
+ 2 [n/2aJ
11
d
VA
8d
log
(49e + 37)s)
64 (6)
+ 64
2 [n/28]
160d
log (2) + [n/2A]
d
n
n
To show the lower bound, let := (21 yı), (I22, 82), } be any infinite d-star-eluder sequence that is consistent with H. We denote X₁ = {#kd {#kd-d+1,-- #ed } for every integer k 2 1, and consider
the following realizable distribution P (with the same center of S):
P P(Tkdd- Uhd- ++))) = px/d, P ((Fkd-
- ykd [kd- = O. VI S j s d, Vk 2 1,
where {px]a21 is sequence of probabilities satisfying Σσ>1 P < 1, which will be specified later.
Let Sn = (2 bi pm be dataset and consider the event & = E1 n Eg, where
ε = (Sn does not contain copy any point X²x)
32 = (S, does not contain copy of at least one point in Xx).
31

---

If the event & happens, the worst-case ERM can have an enror rate (hp 2 /d. This is because [ dold-dd1....... F f is a star set (with the same center) of V, (H) 2 Vid-a(H), and so we know that for any 1 I J I d, there exists heg E V, (H) such that he. (TRd((tddd))))) * -ld-d+j-- and the HRM outputting hgg will have such an error rate. The probability of & follows simply as P(E1) = (1 Ersa Pt) Moreover, characterizing the probability of & can be approached as an instance of the so-called Coupon Collector's 's Problem. Specifically, we let
nu min {n E N: X S S.),
which can be represented as a sum Σj= G3 of independent geometric random variables Gj Geometric d pk) for 1 S j S d, with the following properties
d'p d. E [AJ] Σラ= d E [G,]] Σÿ=1
[ -2
-aa
d+l-j Ph
a+1-j
Ph.
Var [Nu]] = プラ Var [G,]
< Σッ d+1-1 Pk.
a²d
6p4
where Ha is dth harmonic number satisfying HJ 2 log d, for all d 2 1. Chebyshev's inequality implies that P( E[nx]
Then the standard By choosing
2) S Var [ig]
/2Var[ux]. we have with probability at least 1/2,
2 d log v3
ng E [m]]
2ar [ix]
pk
In particular, when d 2 38, it holds that log d 2 2 /3, and thus ûu > Pk 11d log d/2, with probability at least 1/2. Altogether, we have for any n S Pk: d log d/2,
P (E2) 2 IP (n < fg.) 2 P (n S PF dd d/2, Pk PT dlog d/2 < 1n)) 2 1/2. Now for all d 2 38, it follows from the proceeding analysis that
P (erp((h))
Pk
P()) 2 P
1/1
1
1-
1
Pt 12A
n
which further implies that for all d 2 38.
E perp (han)
2 Ptp p (crp(ha)) 2 d
Pk
Pk
1 -
Σ
d
2d
t>k
for all S P 'd'' dog d/2. By letting ny Pk d doo d/2, we have for all E N (infinitely many
E N),
Alog
E erp (hmm))
>
Pk 2d
1
Σ C>*
log d
-
1 1
>
Pt
2
log
4nk
4en=
where the last inequality follows from choosing probabilities {p= satisfying Ersh S 1/nR When 5 38, the result is trivial.
E
Technical lemmas
Lemma 23 (Chernoff's bound). Let Zi,..., Un be independent random variables in {0, 1}, let Z Ei Zi. For all E (0, 1), we have
P PZ S (1-t) Se
?
Lemma 24, Let H he a concept class, and (R. p) be a stable sample compression scheme of size A(S,) < n that is sample-consisten for given data Sn, For any realizable distribution P with respect to H and S, = {(r, 1))r ~ pn, let hi, = p(r((S))) Then it holds
B(((S,))
E Terp(hnn) s
n
32

---

Proof of Lemma 24. We claim that if (Ix+11 Mn++1 satisfies (T+11) o Un+1, we must have
(In-1. (..1)+1)) ) x( x( Suppose not, then there is a subsequence S, := Sn+1 {F Dn+1) satisfying +1) S S, C Sn+1 and ((x(S,))(Exx)) F Vn+1 = p(k(Sn+11 (xx++)) based on the sample-consistency of the compression scheme, which contradicts to our assumption that (R, p) is
stable. Now by the exchangeability of random variables (22 we have
E [hn)
=Es, (S,)) (In+1) + yn+1ll
= S
[1 (p (5x)) (In+1) # yo+1]]
n+1
[ (n \ ((2,, (2,) * y:H
11
E [1 (( ( B(A(S,)]
n +1
Lemma 25 (Hanneke and Yang, 2015, Lemma 44). Let H be concept class, and P be realizable distribution centered at the larget h. For any E N, let S. == {(T,, v)) ~ p be dataset, and let On be the version space compression set (Definition 13), that is, the smallest subset of Sn such that Ve, (H) Vs, (H). We have [Cn] S Sh.
Proof of Lemma 25. We assume that the dataset S, consistent with the target h, i.e. h(xx) = yj for all j E [n]. Note that, if there exists (rj, Mj) E én such that every hypothesis E V,,,((2,,,,,) (H) satisfies g(z;) h(zz); then have VV, ((=) (H) Ve, (H) Vs, (H), which contradicts the definition of the version space compression set as the smallest subset. Therefore, for any (az.88) Mj) Cn. there exists g V(.M(())))) (H) such that g(z,) * h(zz). Moreover, note that "g E Ve,M((55.0))) (H)" equivalent to saying "g(z) = y = h(x), for all (x, v) E C, \ [(z,, V;))". which precisely matches the definition of star set centered at h, that is, CN a star set for centered h, witnessed by those hypotheses g's. We must have |c,! S 9h-
Lemma 26 (Hanneke, 2016b, Theorem 11), Let H be a concept class, and P be a realizable u:)l2_ pm be dataset, for any distribution with respect to H centered h, let Sn == ={)=,, n E N. Then for any E (0,1) 1) and any n E N, we have with probability at least 8,
8 (vC170 In sup erp S n (HV
(49cm1m (VC(H) + +37 + 8l (0)).
where the data- dete-depnndent quantity Ωu. is defined in Definition 13 sattsffyng Ωun Sh-
Lemma 27 (Sauer's 's lemma, Sauer, 1972). Let H. be concept class with VC(H) defined on X and S,, = {(1,,):)]2 1i E (X x {0, 1) 1). Then for all n E N, it holds that
VC(H)
[H((SW) S
Σ
2=
In particular, in 2 VC(H),
en VC(R)
[H(SW)] S
VC(H))
Lemma 28 (VC dimension of unions). Let N,T N and Hi...., Hx be concept classes with maxisieN VC(H:) < T, then it holds
N U i=1
VC
H,
S log N 4T.
33

---

Proof of Lemma 28. According to Sauer's lemma (Lemma 27), for any v N and S. ==
(:) with n 2 T, we have
(S.))))
VC(H.)
T
n
en
T
(10)
Then we can upper bound the number of possible classifications (of S..) by the union U Hi as
( Hh.
(10)
(Sn) S
N
(11)
T
T
Let VC(U- Hi) and Sn, be a set shattered by U Hi, the LHS of (11) is exactly 2", and thus
En T
en
2 N
n n log + T log
= n S log N + 4T,
T
where the last step follows from the fact that m S + q log (em/ /q) implies S 2s + 4g, for any 8 2 0 and 2 q 2
Lemma 29 (Shalev-Shwartz and Ben-David, 2014, Lemma A.1). Let > 0, then 2 2a log implies 2 alogz. Conversely, I < a log x implies x < 2a log a.
Lemma 30 (Bousquet et al., 2021, Lemma 5.12). For any function R(n) - O, there exist proba- bilities (pt HEN satisfying Σ121 Pt 1, two increasing sequences of integers {nehEeN and {ks KeEIN and constant 1/2 < C < 1 such that the following hold for all E N:
(1) EkSR, Pk S m (2) niPk, li- CR(n)).
(3) Pk.
Lemma 31 (Ghost samples). Let H. be concept class and P be realizable distribution with respect to H. Let S2n == {1r, 11)) p2n, Sn = {1,, b and Tn := {( 9:) y:)
Then for any E (0, 1) and 2 8/E, holds
P (ah E H. érs,, (h) 0 and (h) E) 2Ph H érs, (h) and err, (h) e/2).
Proof of Lemma 31. If there exists h H such that éts, (h) 0 and erp(h) E, since Ta is independent of S., by applying the Chernoff's s bound (Lemma 23), we have
P (érr, (h) </2(h) TP
Σ 1=n+1
(h(x;) + vi eer((h) >0) exp {-
Then for any 2 8/c, it follows
PP (err, (h) > c/2(h) = P (err, (h) s c/2(h) > exp {
NE 1
2
8 2'
which completes the proof.
Lemma 32 (Random swaps). Let be a concept class with VC(H) < xo and P a realizable distribution with respect to H. Let S2n : {1: M1 ) p2n S. == v:) and Tn,
{(x,, y1) 3m) Then for any e E (0, and n 2 /C(H)/2, it holds
2en (C(H))
VC(H)
P ((3h E H. érs, (h) 0 and ērr, (h) > e/2) <
2 2-ne/2
Proof of Lemma 32. We prove the lemma by using the "random swaps" technique. Specifically, we define ... an to be independent random variables with Unif( (i, + i}] for all 1 < S n, which are also independent of S2n- For notation simplicity, we denote by o to be the remaining element in (i,n + i} {o,). Now we let Sn [[Zor )o.)...., (Fo., Vo..) and
34

---

T, = (Tonn:: Vont1):...... .......... (Fozn+ Voza ), and note that So UT, follows the same distribution as S2n. Hence, we have
P P E H éts, (h) 0 and érr, (1)> > c/2)
P E H érs, (h) = O and érr, (1) > e/2)
=
-ー= {yonns # &Yati > c/2 )
1 "
(yo, * Yo, = 0.
=
P
3(1
Y2n) E H((2m))
1 -i 1 YVo, & Yo, = 0,
LotF
E
IP
Y2n) E H(S2a):
1 =ii=1 {Vouts o +Yotr } > e/2 S2n
Union bound
E
E
1 2n
-i=i 1
1 -E Yyo, * %o,) = 0,
(oon4 # Yonts > e/2
S2n
(12)
Next, we consider that given S2n, how possibly that the following event happens
Ey
Σ (yo, Yo, and
a
1 (yo... + Yout 2 25
Ti
for a given labeling (Yí, ........ Y2n) ). Indeed, if Ey happens, then there must exist at least [ne/2]] indices n. such that either yi Yi, Untii * Ynti or yi + Yi,Inti = Y otherwise, the difference between - 1yy, * Yo,) and 1 Zi=1 (yyr # Yo...) is less than c/2.. Based on this and the distribution of a, s, we have
1 EE 1 (yo, * Yo,} = 0, (Vant: # Yo..:) ) > 6/2
S2n $ 2-1 11.
P
I 1
Plugging into (12), finally get for all VC(H)/22
P (3h E H. érs,, (h) 0 and ery, (h) c/2)
E
Σ
2 2-1 [
E (H(
2 2-
Lemmu 27
2en VC(H))
VC(H)
.2 2
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main results made in the abstract are discussed with details in Section 1.2. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Certain limitations are discussed in the paper (see e.g. Sections 1.1, 2). Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well- sell-specffication, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The theoretical model that we are working on formalized in Section 1. Due space limitations, the complete proofs are postponed to the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
36

---

The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
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. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-soure dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper is theoretical in its nature and does not include experiments. Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. ec/ public/ seriic/guidess guides//Cdeeuummn www.oeebiiiissooooo...oo onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
37

---

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. //wpss.ccppubll////// /tteiii/ggi///////
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 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 much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 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, supplemental material.
7. 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, confi- dence intervals, statistical significance tests, 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
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).
should be clear whether the error bar is the standard deviation the standard error of the mean.
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 96% CI, if the hypothesis of Normality 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 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.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter 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.
38

---

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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tte:///neuip....eee cc/public/ c/Ethi/Eeeceee esGuidelines.
Answer: [Yes]
Justification: The research conducted in this paper follows the NeurlPS Code of Ethics. Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration 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 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 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 unintentional) misuse of the technology.
If there are negative socictal 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).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have 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 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.
39

---

Datasets that have been scraped from the Internet could pose safety risks. The authors
should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper is theoretical in its nature and does not use existing assets. Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is theoretical in its nature and does not release new assets. Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
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.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
40

---

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 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 crowdsoureing 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
41


Reviews:
[{"review_id": "wNuxzc06vI", "reviewer": "Reviewer_q1H2", "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.", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a tetrachotomy for universal rates of the ERM learners: there are only four possible learning rates, i.e., e^{-n}, 1/n, \\log(n)/n, or arbitrarily slow. The authors also provide results for target specified universal rates and introduce some new complexity measures.", "weaknesses": "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?\n\nAlso, it's not clear to me what is the \"worst-case\" ERM algorithm (line 101). Can author elaborate on that?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback on our paper. Below, we provide detailed responses to your questions:\n\n1. ERM learners are quite different from the designed optimal learners constructed in [Bousquet et al., 2021]. Our analysis reveals a completely different characterization of when ERM learners achieve each of the possible rates, and indeed also reveals a $\\log(n)/n$ rate is possible for ERM learners, which does not appear as an optimal universal rate. The main difficulty in establishing our theory comes from identifying the correct characterizations, which are different from those characterize the optimal universal rates. As for the proofs, most of them are actually built on the classic PAC theory of the ERM principle, together with arguments connecting combinatorial structures from PAC theory to appropriate infinite structures, such as eluder sequences, star-eluder sequences, and VC-eluder sequences, instead of the techniques in [Bousquet et al., 2021]. Moreover, the universal learning by ERM has many nuanced cases (those constructed examples in the paper) that we have to consider.\n\n2. The notion of a \"worst-case ERM\" arises because of the non-uniqueness of the minimizer of the 0-1 loss in classification, i.e., there may be many different ways of breaking this tie, and our analysis aims to provide a rate that holds for all such choices. The so-called \"worst-case ERM\" is actually reflected in our Definition 2. Note that for the upper bound, if the worst-case ERM can achieve some learning rate, then every ERM algorithm can achieve that rate as well. For the lower bound, if there exists an ERM algorithm that fail to achieve some learning rate, then it must be that this is also true for the worst-case ERM. Another way to define the worst-case ERM is presented in Remark 2, i.e., $\\sup_{h\\in V_{n}(\\mathcal{H})}\\text{er}_{P}(h)$, which reflects the error rate of the worst-case ERM. We would like to emphasize that the classic PAC theory of ERM also considers the worst-case ERM, one of the equivalences in the Fundamental Theorem of Statistical Learning is stated as \"Any ERM rule is a successful PAC learner for $\\mathcal{H}$\", which is essentially the same as saying \"The worst-case ERM rule is a successful PAC learner for $\\mathcal{H}$\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dr02SBu0bt", "reviewer": "Reviewer_EqSd", "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.", "questions": "What does a `\"bad ERM algorithm\" (line 135) look like? Random selection from the version space? \n\nDo you have any conjectures as to if and where the rates for ``best-case'' ERM differ from the rates presented here?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Given the ubiquity of ERM, and the looseness of the more classical minimax analyses, the work makes a clear contribution towards the understanding of learning in practice. The work is comprehensive, points out interesting future directions and potential improvements to their theory (e.g. the potential for a simple combinatorial measure separating the $1/n$ and $\\log(n)/n$ regimes).", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and helpful suggestions on our paper. Below, we provide detailed responses to your comments and questions:\n\n1. For the weakness, we will definitely try to improve the writing and add intuitive explanations in the final version.\n2. To answer the first question: the notion of a \"worst-case ERM\" arises because of the non-uniqueness of the minimizer of the 0-1 loss in classification, i.e., there may be many different ways of breaking this tie, and our analysis aims to provide a rate that holds for all such choices. The notion of \"random selection\" requires first that there is some well-defined measure on the concept class, and such an idea may require a different analysis. In particular for the Example 4 that you pointed out, we actually give out the explicit form of a bad (the worst) ERM algorithm in Appendix B.1 (see Example 11, lines 584-585), which is a deterministic algorithm.\n3. For the second question, in particular for the realizable case, studying the ``best-case ERM\" is equivalent to studying the optimal rates of general \"proper learners\", which is a fascinating and important question for future work. We suspect the categorization of rates will somewhat differ from those we establish for the worst-case ERM, analogously to the uniform analysis in [Bousquet, Hanneke, Moran, \\& Zhivotovskiy, 2020].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oQOv8bCuGx", "reviewer": "Reviewer_MghQ", "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.", "questions": "Can the authors explain what do they mean by \"learning scenarios such as the agnostic case\" in l421?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is extremely well-written. I appreciate the effort put in by the authors to provide such a clear exposition. One of this paper's key strengths is exploring and finally characterizing all possible universal learning rates by ERM for the first time. I particularly like the detailed picture featuring the dichotomies between several learning rates with particular examples.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and positive remarks on our paper. \n\nFor the weakness you mentioned, we would like to point out that, in addition to numerous practical works, the interdisciplinary NeurIPS conference also has a rich history of many seminal purely-theoretical works in learning theory.\n\nHere is a response for your question. Mathematically, the agnostic case stands for the situation $\\inf_{h\\in\\mathcal{H}}\\text{er}_{P}(h)>0$, which is more practical than realizable case since we usually have no knowledge about the ground-truth model in real-world applications.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RA4N33PCon", "reviewer": "Reviewer_qCB2", "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. \n\nThis 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.\n\n\n\n[1]: Bousquet, O., Hanneke, S., Moran, S., Van Handel, R., and Yehudayoff, A. (2021), “A theory of\nuniversal learning,” in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of\nComputing, pp. 532–541.", "questions": "minor comments:\n+ lines 69-70: \"unlike that\" -> \"while\".\n+ line 72: \"to the characterization of\" -> \"characterizing\".\n+ line 82: \"necessary\" -> \"necessarily\".\n+ line 107: \"exist\" -> \"exists\".\n+ line 108: \"it requires us\" -> \"we need\"", "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.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The problem studied as well as the results are interesting.", "weaknesses": "+ The writing of the paper is at times uncomfortably close to that [1].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments on our paper. We are happy to know that you found the problem and our results interesting. \n\n1. For the weakness, we adopted the same universal learning framework of the work of [Bousquet et al., 2021] as well as some related definitions. However, our theory differs a lot from theirs, including but not limited to a different problem setting (we focus on ERM learners), different possible universal rates, new-developed combinatorial structures and plenty of concrete examples for nuanced analysis.\n2. For the questions, we appreciate your careful reading. These are very fair comments on grammar, allowing us to enhance the quality of our manuscript. We will go through the paper to correct other potential errors.\n3. For the limitation you mentioned, we would like to extend our sincere thanks to you for pointing out areas where our paper could be improved. In our manuscript, we left the universal learnability by ERM an open question for future work, which is not within the scope of this work. One might guess that the universal Glivenko-Cantelli property might be the correct characterization but it turns out that it is not (see Example 5). We suspect such a characterization would be of a significantly different nature compared to the combinatorial structures we find for the characterizing the rates. For instance, note that the set $\\mathcal{H}$ of all concepts with finitely-many 1's or finitely-many 0's is learnable by ERM (albeit at arbitrarily slow rates) if $\\mathcal{X}$ is countable but not if $\\mathcal{X}$ is the real line. These cases won't be distinguished by a discrete combinatorial structure.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6fiuWasbQ6", "reviewer": "Reviewer_NPxP", "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.", "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?\n\n2. A minor typo: in example 6, the VC dimension of halfspaces is $d+1$ not $d$.\n\n3. In the conclusion, you suggest the study of \"best-case ERM,\" but I am confused as to what that means?", "limitations": "The authors have adequately addressed the limitations.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper presents interesting and valuable contributions to statistical learning theory, following in the footsteps of an earlier work that seeks to understand learning beyond the classical PAC setting.  The algorithm considered, ERM, is classical and the standard approach to virtually all supervised learning problems and thus is an important setting to understand, hewing closer to practice than the more involved algorithms of the earlier work to study universal rates.  Furthermore, the presentation is excellent, with a number of helpful concrete examples included for grounding and clear exposition on the technical combinatorial details.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging comments and insightful suggestions on our paper. Below, we provide detailed responses to your concerns and questions:\n\n1. For the assumption of realizability, as is traditional in the learning theory literature, we first focus on the realizable case to build insights due to its simplicity, and the next natural step is to extend to the non-realizable (agnostic) setting.\n2. The algorithm of [Bousquet et al., 2021] is not expressed as a reduction-to-ERM, and it is really unclear whether such a reduction is possible. Their algorithm is expressed in terms of an extension of Littlestone's SOA algorithm allowing for infinite ordinal values of the Littlestone dimension. Moreover, for finite Littlestone dimension, the recent work of [Assos, Attias, Dagan, Daskalakis, \\& Fishelson, 2023] have found that online learning of Littlestone classes is achievable via a reduction to ERM, but this reduction relies on the relation between the Littlestone dimension and threshold dimension, a relation which breaks down for infinite ordinal Littlestone dimensions, since thresholds on the natural numbers do not admit an infinite Littlestone tree.\n3. Thank you for pointing out this typo. The VC dimension of halfspaces is d+1.\n4. To get an intuition of the so-called \"best-case ERM\", consider the following alternative to our Definition 2: for the upper bound, \"for every ERM algorithm\" $\\rightarrow$ \"there exists an ERM algorithm\"; and for the lower bound, \"there exists an ERM algorithm\" $\\rightarrow$ \"for every ERM algorithm\". In particular for the realizable case, studying the \"best-case ERM\" is equivalent to studying the learning rates of general proper learners.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)