Marginal-Nonuniform PAC Learnability
Authors: Steve Hanneke
Shay Moran
Maximilian Thiessen
Venue: NeurIPS 2025 poster ()
Keywords: statistical learning theory
nonuniform learning
PAC learning
universal learning
VC dimension
Primary area: theory
TL;DR: We study a variant of nonuniform PAC learning, where the constants in the learning rate may depend on the marginal distribution, and devise a trichotomy of possible rates.

Abstract: We revisit the classical model of nonuniform PAC learning, introduced by Benedek and Itai [1994], where generalization guarantees may depend on the target concept (but not on the marginal distribution). In this work, we study a complementary variant, which we call *marginal-nonuniform learning*. In this setting, guarantees may depend on the marginal distribution over the domain, but must hold uniformly over all concepts. This captures the intuition that some data distributions are inherently easier to learn from than others, allowing for a flexible, distribution-sensitive view of learnability. Our main result is a complete characterization of the achievable learning rates in this model, revealing a trichotomy: exponential rates of the form $e^{-n}$ arise precisely when the hypothesis class is finite; linear rates of the form $d/n$ are achievable when a recently introduced combinatorial parameter, the VC-eluder dimension $d$, is finite; and arbitrarily slow rates may occur when $d = \infty$. Additionally, in the original (concept-)nonuniform model, we show that for all learnable classes linear rates are achievable. We conclude by situating marginal-nonuniform learning within the landscape of universal learning, and by discussing its relationship to other distribution-dependent learning paradigms.

Marginal-Nonuniform PAC
LACLLernabiliii Learnability
Steve Hanneke
Shay Moran Technion and Google Research
Purdue University
steve. hamneee@gmail.com
smoran@technion. ac. .il
Maximilian Thiessen
TU Wien
maximilian thiessen@tuwien. ac
Abstract
We revisit the classical model of nonuniform PAC learning, introduced by Benedek and Itai 1994], where generalization guarantees may depend on the target concept (but not on the marginal distribution). In this work, we study a complementary learning. In this setting, guarantees may depend on the marginal distribution over the domain, but must hold uniformly over all concepts. This captures the intuition that some data distributions are inherently easier to learn from than others, allowing for a flexible, distribution- sensitive view of learnability. Our main result is complete characterization of the achievable learning rates in this model, revealing a trichotomy: exponential rates of the form e- arise precisely when the hypothesis class is finite; linear rates of the form 4/n, are achievable when a recently introduced combinatorial parameter, the VC-eluder dimension d, is finite; and arbitrarily slow rates may occur when d = cc. Additionally, in the original (concept-)nonunifoon model, we show that for all learnable classes linear rates are achievable. We conclude by situating marginal-nonunice learning within the landscape of universal learning, and by discussing its relationship other -eeeeddennnddeeeentt learning paradigms.
variant, which we call marginal-nonunife
Introduction
We study the possible learning rates for binary classification in variant of nonuniform learning introduced by [Benedek and Itai [1994]. In standard PAC learning, generalization guarantees take the form of uniform rate: the learning rate applies simultaneously to all target concepts and all marginal distributions over the data domain. contrast, the concept-nonunifory model Benedek and Itai [194]] allows the rate to depend on the target concept f" while still requiring it to hold uniformly over all marginal distributions.
In this work, we study the complementary variant: marginal-nonumijonn learning, in which the learning rate may depend the marginal distribution P over the domain, but must hold uniformly over all target concepts once the marginal is fixed. This model captures the intuition that some data distributions may be inherently casier learn from than others, while still requiring a single algorithm to generalize well for all possible labelings under fixed marginal.
Together, these choices give rise to four basic notions of PAC learnability, depending whether the learning rate is uniform or nonuniform over concepts and distributions. This taxonomy was introduced by Ben-David, Benedek, and Mansour [1955] who studied learnability in all four cases.
In the literature this is simply known as nonuniform learning. We use the term concept-nonumffomm to distinguish it from marginal- -onoinform learning studied here.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In the marginal-nonumifone nonuniform setting, they exhibited examples showing that different rates can arise depending on the hypothesis class.
In this work, we go further and provide a complete characterization of the achievable rates in the marginal-nonuniform regime. Our main result reveals clean trichotomy: exponential rates of the form em arise precisely when the hypothesis class is finite; linear rates of the form 4/n are achievable when a recently introduced combinatorial parameter-the the VC-eluder dimension d-is finite; and arbitrarily slow rates may occur when d = 00.
(Concept-)noone Jonuniform learning is well-known [Benedek and Itai 1994 Vapnik 1998 Lugosi and
Zeger 1996] Shalev-Shwartz and Ben- David, 2014] and inspired various practical learning paradigms, such as, structural risk minimization |Vapnik 1998]. . Occam's 's razor [Blumer, Ehrenfeucht, Haussler and Warmuth, 1987]. and the minimum description length principle [Rissanen] 1978]. Concept- nonuniform learning allows to consider broader family of learnable classes than uniform learning,
where the latter is characterized by the finiteness of the VC dimension. Moreover, nonuniformity allows to distinguish easy to learn concepts from hard to learn ones and through that potentially achieve better learning rates with smaller constants for specific concepts, which would not be possible with worst-case uniform rates. Similarly, marginal-nonuniform learning allows distinguish between easy to learn marginal distributions and hard to learn ones. For example, linear classifiers are learnable with lower sample complexity for distributions supported on a subspace of smaller dimension.
Further related work. Marginal-nonunifoma learning is related to learning with single fixed (and potentially even known) distribution, see Benedek and Itai] [199T] and to recent results on learnability for (families of) fixed distributions [Lechner and Ben- David 2024 Hopkins, Kane Lovett, and Mahajan 2025). Moreover, our work continues the line of work on universal learning and their learning rates [Bousquet, Hanneke, Moran, van Handel, and Ychudayoff [021] Blanchard 2022. Hanneke, Karbasi, Moran, and Velegkas| [222]] Attias, Hanneke, Kalavasis, Karbasi, and
Velegkas 2024]. Recently, HHanneke and Xul [0244] studied the possible universal rates for (worst- case) empirical risk minimizers (ERMs) in contrast to the optimal learners proposed by [Bousquet et al.
(202T]. Interestingly, one of the parameters introduced by Hanneke and Xu [2024) tte VC-eluder dimension-is also characterizing learnability in our marginal-nonuninn
setting. Indeed, one of our main results is that the VC-eluder dimension VCE(H) characterizes the exact fine-grained rate learning. Here, fine-grained learning rates were introduced by Bousquer Hanneke, Moran, Shafer, and Tolstikhin [0233 allowing to state parameter dependent rates like VC(H)/n, instead of simply 1/n, with sharper control over the tails of the learning curves. For a discussion on the relationship of the VC-eluder dimension with relevant parameters from universal
4/n of marginal-nonunifonn
learning, see Hanneke and Xu (2024). Separations between distribution independent and distribution dependent learning, as we study here, were considered before by Feldman (2017) in the statistical query setting.
Overview of main contributions.
1. We initiate the study of marginal-nonumifone learning rates and provide complete charac- terization of the rates that can arise in this setting, depending on natural parameters of the hypothesis class. Our main result is trichotomy of possible rates (Theorem 3 along with fine-grained characterization of the linear regime (Theorem S
2. Our characterization reveals that the family of hypothesis classes that are marginal- nonuniformly Icarnable with a linear rate coincides with the family that are uniformly Iearnable with a linear rate-that is, the PAC learnable classes. At first glance, this may seem to suggest that allowing the constants to depend on the marginal offers no additional power. However, a closer look shows that the linear rate in depends on the VCE(H) dimension, whereas the rate in uniform PAC learning depends on the VC(H) dimension. Since VCE(H) < VC(H) always, and the gap can be arbitrarily large (e.g., when VCE(H) but VC(H) is unbounded), this distinction is significant.
learning
3. We revisit known results on concept-nonuniform learnability and provide an improvement over the previously established log n//n rate [Lugosi and Zeger 1996), showing that linear rate of 3/n is achievable and optimal in this setting.

---

4. We discuss the relationships between the possible learning rates across all four learning settings; see Figure ! and Section We also highlight open problems from both the existing literature and our own work (Section 66.
2 Preliminaries and main results
Let be a domain and distributions on X and call them marginal distributions (in contrast to distributions on X x {0, 1)). For every P (XX) and f*, H. let err.s- (h) = Pf (z) o h(z)) be the expected error
{0, 11.x a hypothesis space. We denote by 4(X) the set of all
of hypothesis h under the distribution P with points labeled by f" This is a strict version of the realizabiliity assumption, see Section 6 for discussion. Fix P, f Let h, A(S,) be the output hypothesis learning algorithm A taking a sample S,, = ((r.; yt) M)));= of size n with æs iid from P and 34 = (x;). We write E|-] = Es, []] the expectation over such sample S.,. We denote by Sge the subsequence of length E N S.
The version space induced by S, is VS(S H) {h E H h(z,) = y, for all i E [m]]. A set S X is shattered if for all y S > {0. 1] there exists H such that h(x) = y(x) for all x e The VC dimension VC(H) of H is the size of largest shattered set. If there exist shattered sets of all sizes E N then VC(H) co. We call We will use the following related, recently introduced combinatorial parameter.
VC-class if the VC dimension VC(H) of is finite.
Definition 1 (VC-cluder dimension, Hanneke and Xu 2024). Let H. be a hypothesis space, d E N, and h E H. We say H has infinite d-VC-eluder sequence S = {II, h(y1)), (22, hyy2)),... centered at if {Ikd+1s... , ] is shattered by VS(S<kdr kdd H) for all E N. A I-VC-eluder sequence is an infinite eluder sequence. The VC-eluder dimension of H is the largest integer VCE(H) d 2 0 such that H has an infinite d- d-VCeel sequence centered at some h E H. If H has an infinite d-VC-elun VC-eeuder sequence for all d N then VCE(H) =
By definition VCE(H) < VC(H). Moreover, there are families of classes such that VCE(H) = while VC(H) is arbitrarily large Hanneke and Xu 2024).
rate function is function N - [0, with 1im R(n) 0. Adapting Bousquet [2021] we have the following cases of learning with rate R, which only differ in the order of quantifiers.
Uniform learning:
3hn s.t. 3C Sst VP e A(X) e H: E(erp, (hw)) s C'((en) for all n.
Universal learning
3hn s.t. vP E A(X))V E H. c 0: E(erp,.- S C'((en) for all n.
Concept-nonuniform learning:
3hn s.t. vf* E H. 3C, Sst.t VP E A(X): E(erp,- (hw) S C'((en) for all n.
Marginal-nonunifom learning:
Bhn s.t. VP e ((X) cC S.t vf E H: Elerp. (h.)) & CR((c)) for all n.
More explicitly we define marginal-nonunifomm -nounnifomm learning with rate function as follows.
Definition (Marginal-nonunifoml nonuniform learning). Let be a class and R a rate function.
1. marginal- -onuniformly learnable rate if there exists a learning algorithm hn such that for all marginal distributions P E ((X) there exists C, c > O such that for all target functions f E H. we have E. (h..) < CR(cn) for all n.
2. H is not rithm hn, there exists a marginal distributions P A(X), constants C,C O, such that for infinitely many n there exists a target concept f E H. (dependent on n) such that Ef (h.,)) 2 CR(cn)..
learnable at rate faster than R for every learning algo-
We emphasize that this slightly differs from the standard definition of universal learning Bousquet et al. 2021 in which broader set of "realizable" distributions is used. See Section @ for discussion.
3

---

3. H. is marginal nonuniformly learnable at exact rate R if H. is marginal-nonuniforiit learn- able rate R and not faster than rate R.
marginal-nonunifomme
4. H requires at least arbitrarily slow rates to be marginal- nonunifornly learnable if every rate function R', the class H is not marginal-nonuniffrmi learnable at rale faster than R'.
5. H. is marginal-nomunifone algorithm hn and function R' N A(X) - [o, 1] with lim,-roo R. (n, P) for all (X) such that for all target concepts f H we have Elerp. (ha)] R (n, P).
learnable (independently of rates) if there exists learning
We now state main result, trichotomy of rates for marginal-nonunifome learning.
Theorem 3 (Marginal- nomunioorm trichotomy). Every class H with [H] 2 3 satisfies:
1. is
learnable with exact rate e Th if and only if VCE(H) fequivalently [H]] < oc).
2. H is marginal- tonngiina-nounnformml. learnable with exact rate 1/n if and only if VCE(H) < co (equivalently [H] = xc. and VC(H) < co).
3. H requires at least arbitrarily slow rates to be marginal-nonuniffrmyyy learnable if and only (equivalently VC(H) oo).
i/ VVVCE(H)
In Theorem we deepen the result for the linear case: we show that the exact fine-grained rate is VCE(H)/n. See Section 3.3 for more details.
3 Marginal-nonuniforn learning
In this section we give the details of the marginal-nonunifon learning trichotomy by going through the individual cases. Missing proofs can be found in Appendix A
3.1 Exponential rates for finite classes
We first show that all finite classes are marginal-nonuniforne learnable with exact exponential rate.
Lemma 4. Any class H with 3 < [ < oc is
learnable with exact rate e
The |H] 2 3 assumption is simply for excluding trivially learnable classes [Bousquet al. 2021
By Lemma 8 Hanneke and Xu [2024] we know that H. is finite if and only if VCE(H) = 0 (i.c., H. has no infinite eluder sequence). Hence the if-direction of the first bullet point of Theorem follows.
3.2 Linear rates through finite VC dimension
We first show that class with VC-eluder dimension 1 < VCE(H) < x can be marginal- nonuniformly learned with linear rate. Moreover, VCE(H) finite if and only if VC(H) finite (Hanncke and Xu, 2024 Remark 19]. Thus it suffices prove the following lemma.
Lemma 5. Every class H with finite VC-dimension is marginal-nonunifure learnable at rate 1/n.
Next we show that this is the best possible rate. Lemma 6. Every infinite class is not marginal-nonumiton learnable at rate faster than 1/n.
This proves the if-direction of the second bullet point of Theorem However, will see in the next section a much stronger bound is possible; while still resulting in a linear rate it determined by the VC-eluder dimension instead of the VC dimension of the class.
3.3 Fine-grained linear rates through finite VC-eluder dimension
Using the notion of fine-grained rates Bouuquett et al. 202.3 we deepen the results for the linear case. In partieular, we provide fine-grained rates characterized by the VC-eluder dimension. Let us first define fine-grained rates for marginal monennfoom learning.

---

Definition 7 (Marginal nonuniform fine- fine-graines grained rates). Let H S 10, be a class and R be distribution-indes indeeeeden- rate function.
-Marginalnnonunffom
1. The class H. is algorithm in such that for every distribution P ((X) there exists distribution- dependent rate function X(1) o(B(n) such that for all I E H holds Bler (h.)) S R(n)) + M()..
learnable at fine- tne-grained rate R if there exists
2. The class is not marginal-non mooiinoooonnnnifornlyy learnable at fine-grained rate faster than R if for each learner hin there exists distribution P E (XX) such that for infinitely many a there exists target function f E '.l (dependent on n) such that E| (h..)) 2 R(n).
3. The class is
learnable at exact fine- thee-griied rate R if 1. and 2. hold.
We now state the fine-graine ane-grained version of the main result of this work.
Theorem 8 (Fine-grained marginal- -nngunnfonnn rate). Let H. be class with VC-eluder dimension VCE(H) = oo. The class H is
learnable at exuct fine--iinnggeeee fine-grained rate d/n.
Proof. The proof follows from Lemma 9 and Lemma
12
Lemma 9. There exists an absolute constant a such that for each class H with VCE(H) < co, there exists a learner hn such that for all f E H. and all marginal distributions P A(X) we have:
VCE(H)
aa sa- +e =x())
where k(P) is a ditiiddiiitiionneeeeeee (but target concept independent) constant.
Proof. Let P be marginal distribution, f* be the target concept, let nn/2, and Sm, Sy (X x Y)m be two iid samples of size m from labeled by f*. Denote by A the event that the version space VS(Sm, H) has VC dimension at most d VCE(H) on S Let hoie be the classifier corresponding the one-inclusion graph algorithm on the sample Si, with hypothesis class H' = VS(Sm, H). By the law of total expectation (and as the error is bounded by one) we have
P, (horc)] < Pr(-A) Elerp, (hOIG) A].
By Lemma 11 there exists n = xP(P) such that Pr(-A) S -=m'm e 5". If A holds the version space has VC dimension most d on Sym Under this event, bound the error of hOIG by a' d 2a for some absolute constant a' [Haussler, Littlestone, and Warmuth 1994).
O
For the upper bound we rely on an application of König lemma, which characterizes the finiteness of tree by the finiteness of all its subpaths.
Lemma 10 (König's lemma, König 1927). Let be rooted tree with a finite or countable number of nodes such that each node has a finite number of neighbours. Then [V] finite if and only if every root to leaf path has finite length.
The next lemma the core result allowing marginal-nonunifore nonuniform learning with rate depending on VCE(H) instead of VC(H).
Lemma 11. Let be a class with VC-eluder dimension VCE(H) marginal distribution. There exists constant C only depending P such that with probability at least 1 e Cn over a sample Sn ~ pa labeled by an arbitrary f E H. the version space TS(S2n/22 H.) induced by the first half of the sample Sgn/2 has, with probability one, VC dimension most on the second half of the sample S SSgn/2
< oo and P A(X) a
Proof. Let d VCE(H). Fix a marginal distribution P over X. Consider an infinite sequence (2,, ... of iid samples from P. Let T be rooted binary tree given by all possible realizable classifications over S. More precisely, the nodes in each level i of 7 correspond to æj, and the two descending edges of each node correspond to labeling the respective z; either as positive or negative. A descending edge is only added node if the path from the root to this node including
5

---

the label given by the edge is realizable (i.e., there exists hypothesis h E H, such that h(z;) y: with yt given by the edges). In other words, T is a Littlestone tree, which is level-constraieed to the sequence S [Littlestone 1988). With every node in 7 we associate version space given by all hypotheses that realize the classifications on the path leading from the root to this node. Finally, we truncate T at node whenever its associated version space has VC dimension at most d on the remaining sequence.
Claim. Every path starting in the root T has finite length.
Assume there is an infinite path starting in the root of T. Take the first node on The version space associated with this node has VC dimension at least d 1 the remaining sequence. Let S1 be shattered set of size d + 1 on the remaining sequence. As the tree is level-constrained, we can reach all nodes corresponding St on p after finite number of steps. The node after S on p again has an associated version space with VC dimension at least d + 1 on the remaining sequence. We can thus repeat this argument to get an infinite sequence of version spaces and corresponding shattered sets S1, S.,... leading to a (d + 1)-VC-eluder sequence, which is not possible. This proves the claim.
Thus, by König's 's lemma, the tree T is finite and in particular has finite depth. Denote by (S) the integer random variable indicating the depth of T induced by S. As depth(S) is always finite, the median qr, i.e., qr min(n N PM (Septh(S) < n)) 2 1/2], is also finite constant (only dependent on P). That is, the version space (S(S<ge, H) of a sample Sggp of size gr (labeled by any target) has, with probability least 1/2, VC dimension of most d on the remaining sequence.
This has further consequences. Specifically, for any target f E H. denote by p = (
H) shatters S"). We claim that with probability at least 1/2 (over Sgap) we have p = O. To see this, note that since Scop may be regarded as the first qp examples from an infinite sequence 5 ~ PN, and independent of the remainder of the sequence, given ý the conditional probability that (S(S<ap: H) has VC dimension at most d on the remaining sequence (i.e., does not shatter any d' + 1 examples in the remaining sequence) is at most lim (1 p)". which is 0 unless p- 0. Thus, with probability one, if 0 then VS(S<gp> H.) does not have VC dimension at most on the remaining sequence. Since the latter occurs with probability at most 1 1/2, conclude that with probability least 1/2 we have p = O.
Now, for any E N. if we have l independent samples of size qp, all labeled by a common target concept, since the version space VS(S<t.qp H) for the total set of L. qp examples is the intersection of the version spaces for the & samples of size qp, the above implies that with probability least 1 - -2)), we have Prs (VS(S H) shatters S') = O. In particular, given this occurs, the conditional probability that (S(S H) has VC dimension at most on an additional independent n/2 examples is 1.
Overall, if we draw sample of size n, we have that the version space induced by the first n/2
samples has VC dimension at most on the other n/2 samples with probability at least 1 - (4) This finishes the proof.
m/2
Lemma 12. There exists an absolute constant 3 such that for each class H with VCF(H) < 0o, all learners hn there a marginal distribution P E A(X), such that for infinitely many n E N there exists a target concept I with
Elerp,y: (hx)) 2 VCE(H)
n
3.4 Arbitrarily slow rates
The third case of Theorem is given by the following lemma.
Lemma 13. Let H. be class with infinite VC-eluder dimension. Marginal- learning H. requires at least arbitrarily slow rates.
Overall, as these three cases, distinguished by VCE(H), are disjoint and cover all possibilities, this completes the proof of Theorem

---

4 Concept-nonuniform learning
In this section, we recap known results on concept- nonunifoom learnability and state an improvement over the best rate known in the literature [Lugosi and Zeger 1996]. Missing proofs are in Appendix B We start again with a definition of learning with specific rate.
Definition 14 (Concept-nonunifor) learning). Let H. be a class and R rate function.
1. H is concept-nonuniformt learnable at rate R if there exists a learning algorithm ha such that for all target functions f E H there exists C, >> 0 such that for all marginal distributions P ((X) we have Elerp,,- (h..)l S CR((e)) for all n.
2. H. is not concept- nonccpt-nonun learnable rate faster than for every learning algo- rithm hn there exists a target function f E H and constants C, > O, such that for infinitely many there exists marginal distribution P E A(X) (dependent on n) such that Elerr.y- (f.)) 2 CR(en).
3. H is concept-nonuniformly learnable at exact rate R if'H is concept-nonumiformly learnable at rate R. and not faster than rate R.
4. H. is concept-nonuniformll learnable (independently of rates) if there exists learning algorithm in and a function It N x H - [0, 1] with lima-soo R (n, h) = 0 for all f e H such that for all marginal distributions P E ((X) have E (h..) S R(n,f*)
The following characterization of concept-nonunifoms learnability is well known.
Lemma 15 (Benedek and Itai 1994). A class H. is concept-nonuniornnly learnable (independently of rates) if and only if H. a countable union of VC classes.
Without loss of generality
assume that concept-nonumiforml) learnable class H is union H = U H, of a nested sequence Hi S H2 .... of VC classes. Common approaches rely on empirical risk minimization (ERM) on each VC class Hi, which leads to overall log R/n rate Lugosi and Zeger 1996). By using a combination of one-inclusion graph predictors [Haussler et al.) 1994] with online-to-bal to-tatch conversion instead, we achieve the optimal linear rate 1/n. This leads to the following dichotomy.
Theorem 16 Coonccet-nonunifom dichotomy). For every class H with [H] 2 3 the following holds:
1. H is concept-nomuiifornly learnable with exact rate 1/n H is a countable union of VC classes.
2. H. is not concept-nonuiffommy learnable H is not countable union of VC classes.
The proof of Theorem follows from the following two lemmas.
Lemma 17. Let H be countable union of VC classes. The class is concept-nonunifornly learnable at rute 1/n.
Proof. If H has finite VC dimension we just run the one-inclusion graph algorithm and obtain linear error rate Haussler et al 1994]. Thus we can assume VC(H) co. Without loss of generality H is nested union Hi C H2 C... of VC classes (we set H = U H.). Denote by di d2 S ... the respective VC dimensions. Since d, - 0o, again by taking unions of subclasses. Let S be an iid sample of size n from a distribution P over X labeled by some f" H and define i* min f H.). We use the first half S' of S to train classifier for each Hi and the second half 5" of S as validation set to aggregate them into a final classifier achieving the linear error rate.
moreover assume that d, > In(i + 1) for all i,
For each subclass H., if is realizable by H. let h; be the one-inclusion graph predictor with training sample S', which satisfies Ejerp,s-hh) (h:)] < dd for some universal constant e RR S' is not realizable by Hi we let by be arbitrary. Furthermore, we only consider h; with ed, < and let the remaining h; be arbitrary. This way we only have to compute finitely many one-inclusion graph predictors hú, since d; + 0C.
7

---

Next we perform an online-to toaee-to-bee to-batch conversion argument to aggregate these predictors. We fix an arbitrary order on S" and run the weighted majority algorithm [Littestone and Warmuth; 1994). In particular, we let each hy be an expert with initial weight wi {[+1J and on mistake we multiply the weights by e for some dj 2 2. Denote by M, the number of mistakes of each expert h2
The total number M of mistakes of the weighted majority algorithm on S" satisfies
S inf M, + 1/m)n(11/x) & inf M2 + Iu(i + 1) < M,- + In(i" + 1)
by standard analysis (see, e.g.. Corollary 3.1 by Gesa-Bianchi and Lugosi er (h /== = pn/2, and 2 2p. Conditioned on S", we have Mr- I M en/2 = (p+ with probability at least
(006]). Let p
Selpi 2437P
lc/w 2678
= =1 6n/4
1
1
by a (multiplicatiie) Chernoff bound. We thus have with the latter probability
M $ (crp, (hr) + In(i" + +)
(I)
Let hi...., .,,,, be the weighted majority predictors in each step of the algorithm over S"
Claim. The expected enror (conditioned S') of the (unweighted) majority vote h Maj(h! is (etp,,-(hx))) + In(i + 1))n).
Theorem 6 and Proposition 11, for 0, with probability at least 1 - e e0n/2 for some universal constant d', we have
By Zhang 2005
n/2 Σ
M
M
log
+ +5) +5)+s) +s) s sc(M/n+s) +
eerp (1)) O
+
using the AM-GM inequality in the last step. For h this implies
n/2
Σ 1 [M(x)) + (1)) 2 1
erp.s-(h) S E xmp
(2/m)
n/2
n/2 erp,y-(h)) < 2d (M/n E).
2 E
(2/m) 1k((x)) + F(01)]
2 > im1
Combining this with Equation [p. the expected error of h (conditioned S') is at most 3d' + s) where 3 er (h..) + In(i" + 1)/n with probability least 1 2e- 2en44/ The claim follows by
E (err.,-(h)]SS) = Ja>u
Pr(err, (f)) > a)da
/ Jasaes Pr(erp, (h) > a)da
Pr(erp, (h) > a)da+ +
Jocasar8
2c ( (b)/4)a/4 da O 3 1
<3d +
Ja>30'
Finally, as his satisfies Elerp, = (S' is realizable by Hi-) and by the assumption d,. 2 In(i 1), the expected error (conditioned on S") of h is at most Odd./n) Taking the expectation over S' and by the law of total expectation, the lemma follows.
Lemma 18. Let H be class with [H|] 2 3. The class H. is not concept-nonunfoortty learnable at rate faster than 1/n.
TT keep the of experts finite, all experts with cd; 2 and treat them
8

---

Examples and broader perspective
In this section discuss some examples and put the results into broader perspective. For a rate R and I' E {uniform, universal, concept-nonuniform, marginal-nonunifomn we denote by R-T the family of hypothesis classes that are T-learnable with rate R. By definition of learning with fixed rate R we have the following trivial inclusions:
1/n-uniform C w/-mmarginalnoomnifon
1/ concept-nonuniform ///n-universal.
Our results yield that the inclusion "3/n-uniform C mmarrinall-oonniiorrr is actually an equality, This is the case as the first family is characterized by the finiteness of the VC dimension, the latter family characterized by the finiteness the VC-eluder dimension (Theorem 3) and both parameters are finite together [Hanneke and Xu 2024] Remark 19]. Then, as each class that is nonuept-nonumiformly learnable with linear rate is a countable union of VC classes (Theorem [T6) we also have the inclusion shows that this is indeed a strict inclusion.
C /c--cooocctt-nonuiffmo The next example
Example co but not 1/n-marginal motpriifonnnnnniiooomm...... Let = (ACN |A| oo). Note that VC(H) = VCE(H) = oc, which means that H is not marginal-nonumifone nonunifornly learnable with linear rate and not uniformly learnable. However, it can be easily seen that Ht U Hi with Hi = {A C N |A| S i} and VC(H)) = i. Thus H is concept-nonuiffomll learnable with rate 1/v. Furthermore, this class is countable and hence marginal-nonunifommn learnable with arbitrarily slow rates, see Benedek and Ital [191]] and Section 6
Additionally, by definition we have (with m.nu. marginal-nonumiforii nonuniforn):
m.n.u C. m/n.m.n. S arbitrarily slow-m.nu. S arbitrarily slow-universal.
The first inclusion strict, as the first family contains exactly all finite hypothesis classes, while the second family contains all VC classes (Theorem 3). The other two inclusions are also strict as shown in the next two examples.
Example 2 Marginal-nonnniffmn with arbitrarily slow rate but not l/n-universal learnable). Let = N and H 2dd Ben-David et al. (1995) showed that this class is murginul-nonuniffrmn learnable (independently of rates) but not concept- suncept-nonunffomllly learnable. Moreover, as this class shatters countable set, it is not universally learnable with linear rate, see Bousquet et al. (202Ty,
Example (Only arbitrarily slow universal). Lei X = [0, 1] and H the set of all open sets over X. Ben-David et al. [1995] showed that this class is universally learnable with arbitrarily slow rate, but neither marginal nor concept- concept-nonuniffee nonunifornly learnable. It is easy to see that this class also shatters a countable set, and is, thus, not universally learnable with linear rate (see Bousquet al. (202]).
There are also classes that are concept- connept-n but not marginal-nonuniforme
learnable.
Example 4 (Concept-nonunifom nonuniform but not marginal nonuniform). Let X = (0. 1), S be the set of all sub- intervals with rational endpoints in X. and H be all finite unions of S. Den--avidd et al. [195]] showed that this class is norunfforly learnable (and thus with linear rate) but not marginul-nonanffore nonuniformly learnable (independently of rates).
Example 5 (Linear universal but neither concept-nomunifome nor pragiiial-nonniffomn Les X1 {A C |A| < }o} and Hi (hy y E R3 with h,,(5) = 1y E S... Boousquet et al. (2021) (Example 2.7) argued that Hi is not representable as countable union of VC classes, thus not concept-nonuniformll learnable. is universally learnable with exponential rate however (and thus also linear rate). Let Hz be from Example [ which is not
learnable. As Hz learnable at linear rate it is also universally learnable at linear rate. Take
is cmncept-nonuniffn the disjoint union H. Hi U H2. It is easy see that H. is still universally learnable with linear rate but neither concept nor marginal-nonmiifon nommnifornly learnable (independently of rates).
The only remaining open case is whether there exists a class that is not concept- concept-nnnuifrrmly learnable at arbitrarily
learnable, is universally learnable with linear rate, and marginal-nonunifomee slow rate. Except this case, this shows all possible inclusions of the rates in marginal and concept- nonuniform learning, and their relationship to uniform and universal learning. Figure T gives an overview with the missing case marked as "?"

---

Example
Example
Examppe
VC(H)
Example
||| < oc +
"I marginal nomuniform
eye-margiul-mmmmniifom nonunifomm 1/n-unifomm
Examale
1/m-niieriall
ubitrusiyy slow marginal nonuniform
arbitrariyy universal
Figure I: Overview on the learning rates related to marginal and concept-nonunifomm learning.
6
Discussion and future work
We end with some discussion on related aspects and some potential future work.
Weaker notions of realizability. [Busqueet al. 2222
considered a weaker notion of realiz-
ability: a distribution Pxy over X x Y realizable if in A er (h) = O where er (h) Pr( (h(x:) # y)- Any such distribution P has P(y 1/x) E 13 for almost all x. Hence
we can more generally say that marginal distribution over X and a target f E {0. 1]x is realizable if inf erp (h) = 0. This allows slightly more general definitions of marginal and concept-nonunifore learning, with again constants depending on either P or f Our proofs for the marginal- -onirinfonnnnnnorm case can be adapted to the weakly realizable case. Thus, the landscape of potential learning rates stays exactly the same, independently of weak or strict realizability. This also the case in uniform learning. However, for universal and nonunifom learning the two variants of realizability result in different Iearnable classes. Characterizing the differences is open.
Universal Glivenko-Cantell does not determine learnability. The problem of distinguishing a marginal-nnonuiffrmmyy learnable class with arbitrarily slow rates from a not learnable class is still open. A natural candidate is the universal Glivenko-Canteli property, which is the analogue of uniform convergence in the context of universal learning (Bousquet et al. 202 van Handel| (013)
However, the class {A R A|| < 3o} does not have the Jeveenko-Cantelll property [van Handel 2013). but is marginal and concept-nonuniformly learnable [Ben- BeviDavid et al. 1995].
norginal-nonuniforn learning on countable domains. Benedek and Itai 1991 show that discrete distributions are fixed-distribution learnable and thus all classes countable domains are narginal-nonunifore learnable. However, our results show that the family of all such classes require at least arbitrarily slow rates. Thus, while all classes countable domains marginal- nonuniformly learnable (independently rate), there no single rate capturing the learnability.
Marginal-nonuniform O connnpt-n uniform learning. We showed that in the case learning collapses to uniform learning. Interestingly, if we of linear rates, independently of rates a different situation arises. The intersection of marginal- consider learning
nonuniform and concept-nonunifomn is then a strict superset of uniformly learnable classes, see Ben-David et al. [1995]. In fact Example I the concept class of all finite subsets of N, is in the intersection of the two nonuniform settings but not uniformly learnable.
Other learning settings. Universal rates were also considered for active [Hanneke et al., 2024 and online learning [Blanchard] 2022). Marginal-nonunifol example, typical worst-case lower bounds in active learning for linear classifiers, are achieved by fixed marginal distributions [Balcan, Hanneke, and Vaughan 2010 Hanneke et al. 2024
rates could be interesting here, as well. For
10

---

Acknowledgments and Disclosure of Funding
SM is supported by a Robert J. Shillman Fellowship. by ISF grant 1225/20. by BSF grant 2018385, by an Azrieli Faculty Fellowship, by Israel PBC-VATAT, and by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency, Neither the European Union nor the granting authority can be held responsible for them.
MT acknowledges support from DOC fellowship of the Austrian Academy of Sciences (ÖAW).
References
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, and Grigoris Velegkas. Universal rates for regression: Separations between cut-off and absolute loss. In Conference on Learning Theory, COLT, 2024.
Maria-Florinn Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Machine Learning, 80:111-133 2010.
Shai Ben-David, Gyora M Benedek, and Yishay Mansour. A parameterization scheme for classifying models of PAC learnability. Information and Computation, 120(1):11-211 1995.
Gyora M Benedek and Alon Itai. Learnabilityy with respect to fixed distributions. Theoretical Computer Science, 86(2):377-389, 1991.
Gyora M Benedek and Alon Itai. Nonuniform learnability. Journal of Computer and System Sciences, 18-2)331--323, 1994.
Moise Blanchard. Universal online learning: An optimistically universal learning rule. In Conference on Learning Theory, COLT, 2022.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Occam's 's razor. Information Processing Letters, 2476):377-380, 1987.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the Chenin-Chervoneekis dimension. Journal of the ACM, 36(4):929-966 1989.
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. A theory of universal learning. In Symposium on Theory of Computing, STOC, 2021.
Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin. Fine-grained distribution-depeeneett learning curves. In Conference on Learning Theory, COLT, 2023.
Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Vitaly Feldman. A general characterization of the statistical query complexity. In Conference Learning Theory, COLT, 2017.
Steve Hanneke and Mingyue Xu. Universal rates of empirical risk minimization. In Advances in Neural Information Processing Systems, NeurIPS, 2024.
Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Universal rates for active learning. In Advances in Neural Information Processing Systems, NeurIPS, 2024.
David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting 10 funcciiss on randomly drawn points. Information and Computation, 115(2):248-22 2922, 1994.
Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Do PAC-learners learn the marginal distribution? In Conference on Algorithmic Learning Theory, ALT, 2025.

---

Dénes König. Über eine Schlussweise aus dem Endlichen ins Unendliche. Acta Sci. Math.(Sreged)) 3(2-3):121-330, 1927.
Tosca Lechner and Shai Ben-David. Inherent limitations of dimensions for characterizing learnability of distribution classes. In Conference Learning Theory, COLT, 2024.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning. 2:285-318, 1988.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-661, 1994.
Gábor Lugosi and Kenneth Zeger. Concept learning using complexity regularization. IEEE Transac- tions on Information Theory,
1996.
Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465-771, 1978.
Dale Schuurmans. Characterizing rational versus exponential learning curves. Journal of Computer and System Sciences, 55(1):140-160, 1997.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
Ramon van Handel. The universal Glivenko-Cantelll property. Probability Theory and Related Fields, 155(3):911-934, 2013.
Vladimir N Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.
Tong Zhang. Data dependent concentration bounds for sequential prediction algorithms. In Confer- ence on Learning Theory, COLT, 2005.
12

---

A Marginal nonuniform
Lemma 4, Any class H. with 3 S [H|] < is marginal-ronunjfrmiy learnable with exact rate
Proof. We start with the upper bound for all finite classes. The standard analysis of PAC learning with
finite H. (see e.g., Example of Hanneke and Xu (2024) yields for any fixed P E A(X), H:
min Elerp.r. (h.)) s H|] exp (- NEH.err, (h)20
Now H finite and by taking the maximum over f H we get for some constant c:
min (- (- (b)20
Elerp, (hnn) = [H] exp
e.p.y.(h)
prp (t)) n)
$ [H] max exp
min
K'EH
hEH. (1))0 (h)s0
S [H] exp(-cn).
Note that the constant is independent of any concept h H (or rather it is the worst the finitely many /t' and thus only depends on the marginal P.
We continue with the lower bound. A finite class H with H > 3 is not universally learnable rate faster than e see Bousquet et al. [2021] Schuurmans 1997]. Thus, this also not possible C stricter maagginalnoouniform case.
Lemma 5. Every class H with finite VC-dimension is marginal-nonumiiforee learnable at rate I/n.
The class H. is uniformly learnable at rate 1/2 (using the one-inclusion graph algorithm (Haussler et 1994)). Thus, it is also learnable at this rate in the less strict marginal nonuniform setting.
Proof.
marginal-nommmiffm
Lemma 6. Every infinite class H is not marginal-nooumiifrnee learnable at rate faster than 1/n.
Proof. We adapt the proof of Lemma 14 by Hanneke and Xu 2024 As H has infinite size it has an infinite eluder sequence [Hanneke and Xu 2024 Lemma 8) Tet E {(x1, 31). (x22, v.),...) be
such a sequence. Define the following marginal distribution P on X with P(x,) = 2 for all E N.
Let Sn . } ~ pm be an unlabeled iid sample of size n 2 2. For t [log n the
probability that 5, does not contain any point in {ar 1h:1>>> 1) is
Pr(S, for t 0) II Pr(si (x1,...,, (1 - 2 2 (1 1/n)" 2 1/4. (2)
Let S. = (81, ,..,...,,.. (Sn, yn)} be a labeled (realizable) sample and i. A(Sa). As E is
an eluder sequence, there concepts h, W H with h(x;)) h (x:)) yı for all i E [t] and M(x+11) * h (x(++1). 1 Let the target concept f be chosen uniformly at random from (h, 1!). For any deterministic learner A under the event that S, n (a, : t = we have
2 2- ((+1) 1
erp,r- (A(S))
4n
This holds as -z-1 is drawn with probability 1 and as Tz+1 & S, the learner A will err with probability 1/2 the true label of # is drawn uniformly at random from {0, 1}. By combining Equation ( and Equation 3 we get
11 1 4n
(erp, (A(S.))) 2 Sa.f-
(A(S)))
16m
Note that the uniform distribution over h, h yields a lower bound of 1 /4n simultaneously for all deterministic learners. Thus, by e-g., Yao's principle, we know that any randomized learner, either h h gives deterministically the same lower bound, proving the claim.
D
13

---

A.1 Arbitrarily slow rates
We use here the notion of an infinite VC-eluder sequence, see, e.g., Hanneke and Xu [0224] Let
H be a class and nt = (2) for all E N. A sequence S = { h(r1)) )), (T2, h(22)) ), is an infinite VC-eluder sequence (centered h) if for all E N, the set ( Lng + is shattered by the version space VS(S<mm H.), The class H. has an infinite VC-eluder sequence if and only if VCE(H) = oa Hanneke and Xu 2024].
Moreover, we rely on the following technical lemma by Bousquet et al. 2021
Lemma 19 (Lemma 5.12, Bousquet et al. 2021). For every rate function R, there exists probabilities {pthen with ΣIEN Pt = I. two increasing sequences of positive integers {netEE JeNN,, and a constant 1/2 S I 1 such that all the following hold:
1. Σσ ke Ps S nhe"
2. ntPk, kt. and
3. Pk. CR(m)).
Lemma 13. Let H be a class with infinite VC-eluder dimension. Marginal-ronumiiormny learning H. requires at least arbitrarily slow rates.
Proof. We adapt the proof of Lemma by Hanneke and Xu 2024]. As VCE(H) co, the class H has an infinite VC-eluder sequence E {[ J'(x) }), (#2,
} for some I' E H. Let X = +1 Fn.++) be the shattered sets of increasing size in E for all k: N. We define the following marginal distribution P E A(X). For all all k E N, let Pr(x E Xx))
p& and Pr(x) p&/k for all e Xg. where the sequence [ will be specified later. Let R be an arbitrary rate function. We will show that no learner can marginal-nonunifomne nonuniformly learn under P faster than rate R.
Let S, be an unlabeled iid sample from of size n. Let fhi HeN n be an increasing sequence of positive integers be specified later. Denote N2y. Upit Xx, for all N. For all t N. j E [kr]. and we define the event
An.kit = {Sn ( U (Ing,t)) = 0}.
Note that, An,k,t. indicates whether the sample S, contains no points from any XE,. (for t' > t) nor the point Fna, +j E Xx,- That is, by definition of an infinite VC-eluder sequences, if An,,,t. holds, the version space under the sample S, labeled by I' contains a hypothesis f" E that classifies Tnu,+5 +. differently, i.e., f'( +j) # I" (Ine, +z). This holds because k2 is shatterable in this case and t5 E Xk, is not in the sample. Note that f" can depend on n. Consider an algorithm h, and its prediction on I Tnne +- given by sample Sn (labeled by f' (or equally f") restricted to S,).. Select the ground truth f E {f' as the one hypothesis whose label (*(nnat)) the more unlikely one be predicted by the classifier returned by the learner. Thus, if An,k,t, holds have that erp.y- (f.,) 2 2 Pke as Inu,+s will be drawn with the probability Pki and then misclassified with probability at least 1 1/2. Also note that Pr(An,k,.5) = (1 EESA, Pk -k..
Re
We now apply Lemma 19 get the {pe)eeN (Ke)NEN, and {mt)eeN sequences, and C with the properties as stated. Then we get for all f E N with 2 3 (and thus for infinitely many E N):
Elerp.s (hnm))
Σ
2kr
Pke Pr Pr(Am,,aa5)
2
Pk: (1
2
Σ kDNk
Pk
Pk./ m
Pke
2
nre
Pk.
C
R(ne):
54
54
14

---

A.2 Fine-grained linear rates through finite VC-eluder dimension
Lemma 12. There exists un absolute constant 3 such that for each class H with VCE(H) < 0o, for all learners hn there is a marginal distribution P E A(X), such that for infinitely many n E N there exists target concept fü with
E Elerp.s.(hn)) (hn)) VCE(H)
n
Proof. The proof similar to Lemma 13 but uses rate d/n instead of arbitrarily slow ones. Let VCE(H)
d. The class H. has an infinite d-VC-eluder sequence S ( (x2))
for some f E H. Let for all k E N the Xs -Ekd-d-1:.. Lkdd be the shattered sets of size d in S. We define the following marginal dis- tribution P (X).. For all N. let Pr(x E Xx) = Pa and Pr(x) = pp/d for a E Xs, where the sequence {p* will be specified later. Let R(n) 4/n. We will show that no learner can learn under P faster than rate R.
Let S₁ be an unlabeled iid sample from P of size n. Let (he heN be an increasing sequence of positive integers be specified later. Denote N Uト>* X, for all k E N. For all E N. j [d]. and & we define the event
An.k. = (S n
f}.
Note that, An.s. indicates whether the sample Sn contains no points from any X, (for j > k) nor the point Tkd-d+j Xx. That is, by definition of an infinite d-VC-eluder sequences, if An,k. holds, the version space under the sample Sn labeled by f contains a hypothesis f" E H that classifies IRd-d+j differently, i.e. f' ("(xddd+t) # (I This holds because X₃ is shatterable in this case and Ixd-d+j E X2 is not in the sample. Note that f" can depend on n. Consider an algorithm hn and its prediction on dRdd-++j given by sample Sn (labeled by I' (or equally f"") restricted to S.). Select the ground truth f" E (J', [") as the one hypothesis whose label I (axkd-d4))) is the more unlikely one to be predicted by the classifier returned by the learner. Thus, if An,k.j holds we have that erp. (h,, 2 Ph. as Tiddd+jj will be drawn with the probability Pt and then misclassified with probability at least 1/2. Also note that Pr(An,k.j) = (1 Σj>{P} p//d)".
d
We now apply Lemma to to get the Pt, hts and n. sequences, and with the properties as stated (we do not use the hs sequence here). Then we get for all t E N with n4 2 3 (and thus for infinitely many n E N):
Σ jE[d
Pk Pr(A Pr(Ann,es)
2
Pke (1
Σ
Pk Pk/dd'
2d
2
Pk1
2
1
2
Pk.
C d
>
54
54 n3
B Concept nonuniform
Lemma 18. Let H be a class with [H] 2 3. The class H. is not concep--nonnifommyy learnable at rate faster than 1/n
This is an adaptation of standard lower bounds for PAC learning, see, e.g., Blumer, Ehren feucht, Haussler, and Warmuth [1989] Anthony and Bartlett [999|. As [76] 2 3 there exist two hypotheses h, hi' and two points v, x' E such that h(()) = 1 (x) and h(xz) * 1 (z'). We will show that at least one of the two hypotheses requires rate of 1/n to be concept-nonuniformly learnable. Let n E N be a sample size with n 2 and the marginal distribution P E A(X) be given as P(x) 1 - and P(x')= 1. Let S,, be unlabelled iid sample from pa and denote the event
Proof.
15

---

that Sn does not contain x' as A. Note that
Pr (A) 1 Sp
n 71
1
2
1/4.
Now, for each E N. let hn be classifier returned by learning algorithm given the sample S. labelled by f {h, h"), where the latter be determined shortly. For each N, let yn {0. 1] be the label that is less likely to be predicted by (the potentially randomized) h, for x'. At least one yn appears infinitely often in the sequence (ya)n. Call this label y We select f as the hypothesis with (²') = y²- Consider the sample under the event A, i.e., the sample contains times the point For infinitely many n, under the event A, the classifier hn will have expected n 3. Indeed, the point x' will be drawn with probability 1/n and for infinitely many the classifier makes an error with probability at least 1/2 (by the choice of f*). Thus, overall the emror probability of hn for the target concept f" satisfies
of ya
error of at least 4.
1 2n
e.p.s- (hm) 2 P(A) 2
8n
for infinitely many n. The claim follows.
16

---

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: We do prove the main trichotomy for marginall-oouniform learning and provide further results and context.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our results only hold under the specific assumptions in the theorems. Further context given in the example and discussion section.
Guidelines:
The answer NA means that the paper has 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 a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 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-tex, system might not be used reliably to 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 faimesss.
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 complete (and correct) proof?
17

---

Answer:
[Yes]
Justification:
Yes in the main paper and in 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 or referenced in the statement of any theorems.
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 to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be 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 affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
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.
If 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 a novel architecture, describing the architecture fully might suffice, or if the contribution 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 one good way to 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 are appropriate to the research performed.
specific model and empirical evaluation, may
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 new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.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 open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
18

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
aabbic//uides/DodeStttmssss sollliilssiiooy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: ctsps.cc/public//eeeecc guwdee/eee//e// /CodeSubmia ssi sgionPolicy) 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. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
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 provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:[NA [NA]
Justification:
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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
19

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: heerrps........ cc/pubbicc/thhicccceeeeeele
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make 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: This work mostly theoretical with no immediate societal impact, neither positive nor negative.
Guidelines:
The answer NA means that there 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.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
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)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses 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 usage guidelines or restrictions to access the model or implementing safety filters.
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. Lieenses 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:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com 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.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 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:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, 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
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 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.
16. Declaration of LLM usage
22

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https /ttp://eeuup..//eeee cc///oofeeeenccce/22////. for what should or should not be described.
23


Reviews:
[{"review_id": "5jIYHRo2cs", "reviewer": "Reviewer_SdTA", "summary": "This paper discusses the question marginal-nonuniform learnability, requiring learners to depend only non-uniformly on the marginal, but uniformly on the concept. Thus this notion contrast standard non-uniform learning, which requires guarantees to be uniform for all marginals but non-uniform over concepts. These notions are in-between notion of uniform PAC learning, which provides uniform rates for all concepts and distributions and universal learning, which allow for non-uniform guarantees for both concept and marginal. \n\nThey relate this learnability to a recently introduced complexity measure - the VC-eluder dimension. In particular they show that:\n- A class is marginal non-uniformly learnable, with exponential rates if and only if it is finite\n- A class is marginal non-uniformly learnable with linear rates if and only if the class has finite VC-eluder dimension\n- A class has at best arbitrarily slow non-uniform rates for marginal non-uniform learnability if it has infinite VC-eluder dimension. \n\nThey also show improved rates for concept-nonuniform learning. \n\nTheir results rely on established methods within the literature of universal learning rates.", "questions": "One downside of non-uniform learning approaches as opposed to uniform PAC learning approaches is that non-uniform learning guarantees do not provide any error/confidence guarantees for a learned classifier. \nIs this something you can still overcome in the marginal non-uniform setting?\n\nCan you say anything about learnability in the agnostic case?", "limitations": "The authors provide proofs for all of their statements. Limitations and assumptions have been acknowledged in the main text of the paper.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nI overall enjoyed the presentation of the paper. I enjoyed the use of color to highlight different quantifiers as well as the picture separating between different cases.\nThere is a good overview of the literature, highlighting many important results. \nThe results discuss a relevant non-uniform learnability notion and it provides novel results.\nI enjoyed the discussion section. \n\nOverall I enjoyed reading the paper and found it insightful and well-rounded.\n\n\nWeaknesses:\n-In contrast to the universal learning rates, this work does not provide a full characterization, as there is no distinction between arbitrarily slow rates and a class not being non-uniform marginally learnable. In universal learning every class (with sufficient measurability conditions) is universally learnable at least with arbitrarily slow rates. As the authors mention, in previous work it has been shown that this is not the case for marginal non-uniform learning. However there is no clear characterization of what distinguishes marginal non-uniformly learnable classes from not marginal non-uniformly learnable classes. I think this should be highlighted more, as the presentation as trichotomy which is akin to the universal learning rates paper from Bousquet et al 2021 (and follow-up works), where the trichotomy gives a more complete characterization (as there is no fourth case of unlearnable classes)\n- I wish there was a bit more intuition given for cases in which marginal non-uniform learnability is distinct from universal learning. There are some examples mentioned from the literature, but it would be nice if they could be discussed in more detail. How do the complexity measures infinite Littlestonetree/VCL-tree and VC-eluder dimension relate? A lot of the examples from old work are merely stated, which makes sense for space constraints. In order to understand the intuition of this paper, it might help though to rewrite those examples and relate them explicitly to those complexity measures. \n- The insight of this paper heavily relies on bringing together insights from previous work and the ideas within this work itself aren't as novel or ground-breaking. (I don't view this as a reason to reject the paper, as it was still insightful to read the paper)\n- As is often the case for results on universal learning rates the results rely on the realizable case, which is arguably a very strong assumption. (However, as this is a general drawback of this line of work I would not count it as heavily against this work in particular)\n\n\nOverall I feel that this was a decent paper and I enjoyed reading it. The characterization and discussion is a good addition to the literature and fits well within the NeurIPS program.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your encouraging feedback!\n\n> In contrast to the universal learning rates, this work does not provide a full characterization, as there is no distinction between arbitrarily slow rates and a class not being non-uniform marginally learnable.\n\nWe agree that the learnability question is interesting and view it as an intriguing direction for future work.\nNevertheless, our characterization is complete in the case of countable $X$, where learnability always holds. For uncountable $X$, the outcome depends on the choice of sigma-algebra, and some measure-theoretic distinctions are required. For instance, under the power set sigma-algebra, learnability is always possible, as only discrete distributions are allowed.\nMoreover, notice that our results do provide a complete characterization of what optimal learning rates are possible—exponential, linear, arbitrarily slow, and non-learnable.\n\n> I wish there was a bit more intuition given for cases in which marginal non-uniform learnability is distinct from universal learning. There are some examples mentioned from the literature, but it would be nice if they could be discussed in more detail. How do the complexity measures infinite Littlestonetree/VCL-tree and VC-eluder dimension relate?\n\nWe thank the reviewer for this insightful question—we agree that elaborating on the distinctions between marginal non-uniform and universal learning would add clarity, and we will include a more detailed discussion in the next revision.\n\nThere are some clean implications in both directions. On one hand, any class that admits a linear rate in the marginal non-uniform setting must have finite VC dimension, and therefore admits at most a linear rate in the universal setting. Similarly, any class with an exponential rate in the marginal non-uniform setting must be finite, and hence also enjoys an exponential rate in the universal setting.\n\nOn the other hand, there exist classes that achieve exponential rates in the universal setting but are arbitrarily slow in the marginal non-uniform setting. This occurs, for example, when a class has no infinite Littlestone tree but has infinite VC dimension. Such examples are discussed in the work of Bousquet et al.; one nice such example is that of monotone functions over the grid of natural numbers $\\mathbb{N}^d$, and wrt the natural partial order over grid points.\n\nWe will expand on these points and add more such concrete examples to our examples section in the revised version.\n\n> The insight of this paper heavily relies on bringing together insights from previous work and the ideas within this work itself aren't as novel or ground-breaking (I don't view this as a reason to reject the paper, as it was still insightful to read the paper)\n\nWhile the combinatorial structures used in our work resemble those in the analysis of ERM by Hanneke and Xu (2024), we emphasize that this connection is far from obvious. The two settings are conceptually quite distinct: ERM concerns a specific learning algorithm, while our work addresses the more fundamental question of optimal learning rates in a different, non-uniform setting. That similar combinatorial dimensions emerge in both contexts is not something that could have been foreseen—it took us considerable effort to uncover this link.\n\nFurthermore, even once this connection was recognized, the technical paths diverge significantly. A particularly notable difference lies in our fine-grained analysis of learning rates in terms of $\\text{VCE}(H)/n$, which introduces new ideas—most prominently, the use of König’s lemma to show that the version space will eventually have VC dimension at most $\\text{VCE}(H)$ on future instances. This use of König’s lemma is novel and central to our analysis.\n\n> As is often the case for results on universal learning rates the results rely on the realizable case, which is arguably a very strong assumption. (However, as this is a general drawback of this line of work I would not count it as heavily against this work in particular)\n\nThe agnostic case is of course interesting.  There is even an interesting question about what is the appropriate formulation of the setting for the agnostic case.  For instance, we could consider the supremum over all conditional distributions $Y|X$, or we could consider only deterministic labels and consider the supremum over all labeling functions.  This is an interesting direction for future work.\n\n> One downside of non-uniform learning approaches as opposed to uniform PAC learning approaches is that non-uniform learning guarantees do not provide any error/confidence guarantees for a learned classifier. Is this something you can still overcome in the marginal non-uniform setting?\n\nWe agree. Note that marginal-nonuniform learning also provides bounds in the case when the marginal distribution is known (e.g., uniform over sphere, etc.) or comes from a known family of distributions. In such cases, at least in principle, the marginal-dependent constants in our bounds could be computable/boundable (they are mostly given by certain tail probabilities indicating when all version spaces will have bounded VC dimension with constant probability).\n\n> Can you say anything about learnability in the agnostic case?\n\nSee above."}, {"review_id": "bdUFCGz6lD", "reviewer": "Reviewer_f8zt", "summary": "This paper formalizes \"marginal-nonuniform learning\" as a variant of the PAC model that allows for distribution-specific learning rates that hold uniformly over all possible target concepts. Specifically, a concept class is learnable at rate R if for every marginal distribution over examples, there exists a (distribution-dependent) constant c such that every concept in the class is learnable with error at most ~R(cn) using n samples. This ordering of quantifiers makes it a relaxation of distribution-free PAC learning (uniform), a strengthening of universal learning, and complementary to (concept)-nonuniform learning.\n\nThe paper proves the following results. The main result is a trichotomy of rates for marginal-nonuniform learning in terms of the VC-eluder (VCE) dimension of the target class. Moreover, in the case where the learning rate is linear, it scales as VCE(H)/n. The paper then revisits concept-nonuniform learning, for which it shows that the one-inclusion graph algorithm achieves a linear rate for countable unions of VC classes. Finally, the paper discusses the relationships between uniform, non-uniform, and universal learning and presents examples of classes separating these notions.", "questions": "* Does Theorem 16 (or its proof) suggest a characterization of the fine-grained rate of concept-nonuniform learnability of countable unions of VC classes?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(+) The paper studies a mathematically natural learning model that cleanly fills in a gap between previously studied ones.\n\n(+) The main trichotomy result and characterization via VCE dimension is sharp and satisfying.\n\n(+) Proofs are conceptually simple and do a nice job intuitively illuminating why the corresponding statements are true.\n\n(-) While the question of understanding learning rates for marginal-nonuniform learners is new, it's debatable how new the model of marginal-nonuniform learning itself is. As acknowledged in the paper, it's related to distribution-specific and distribution-family learning. But even more closely related questions about the difference between uniform PAC learning and learnability with respect to known, but arbitrary, marginal distributions have been studied in the past. For example, in Section 7.2 of the arXiv version of \"A General Characterization of the Statistical Query Complexity,\" Feldman showed a strong separation between distribution-independent SQ complexity and the max over all distributions of distribution-specific SQ complexity.\n\n(-) The paper's statements and proofs very closely track those of recent prior work of Hanneke and Xu on universal learning rates. As such, there isn't much in the way of new technical ideas or tools developed in this paper.", "was_revised": true, "final_justification": "This is a nice conceptual submission which, based on discussion with the authors, I am confident they can refine into a strong presentation.", "rebuttal": "Thank you for your feedback.\n\n> While the question of understanding learning rates for marginal-nonuniform learners is new, it's debatable how new the model of marginal-nonuniform learning itself is. As acknowledged in the paper, it's related to distribution-specific and distribution-family learning. But even more closely related questions about the difference between uniform PAC learning and learnability with respect to known, but arbitrary, marginal distributions have been studied in the past. For example, in Section 7.2 of the arXiv version of \"A General Characterization of the Statistical Query Complexity,\" Feldman showed a strong separation between distribution-independent SQ complexity and the max over all distributions of distribution-specific SQ complexity.\n\nThanks for bringing Feldman’s results to our attention. We will add a more thorough  discussion of related work to the revised version. We believe that the fact that this model was studied before makes our result arguably more interesting.\nOur main starting point was the taxonomy of Ben-David et al. (1995) (on different nonuniform learnability models). We believe that establishing possible error rates for the settings proposed there is valuable. \n\n> The paper's statements and proofs very closely track those of recent prior work of Hanneke and Xu on universal learning rates. As such, there isn't much in the way of new technical ideas or tools developed in this paper.\n\nWhile the combinatorial structures used in our work resemble those in the analysis of ERM by Hanneke and Xu (2024), we emphasize that this connection is far from obvious. The two settings are conceptually quite distinct: ERM concerns a specific learning algorithm, while our work addresses the more fundamental question of optimal learning rates in a different, non-uniform setting. That similar combinatorial dimensions emerge in both contexts is not something that could have been foreseen—it took us considerable effort to uncover this link.\n\nFurthermore, even once this connection was recognized, the technical paths diverge significantly. A particularly notable difference lies in our fine-grained analysis of learning rates in terms of $\\text{VCE}(H)/n$, which introduces new ideas—most prominently, the use of König’s lemma to show that the version space will eventually have VC dimension at most $\\text{VCE}(H)$ on future instances. This use of König’s lemma is novel and central to our analysis.\n\n> Does Theorem 16 (or its proof) suggest a characterization of the fine-grained rate of concept-nonuniform learnability of countable unions of VC classes?\n\nGood question! Let us first unpack the interpretation of the question.  In the standard sense of fine-grained rates (Bousquet et al., 2023), a fine-grained rate of, say, linear $1/n$ are expressed as a bound $d/n$ holding for all sufficiently large $n$ (dependent on the distribution and target concept), where $d$ is only dependent on the class $\\mathcal{H}$ and not the distribution.  In the concept-nonuniform case the achieved rate is $\\operatorname{VC}(\\mathcal H_f)/n$ where $\\mathcal H_f$ is the “smallest” class containing the target concept $f$.  In some sense, this is a kind of fine-grained rate, but there is perhaps a more-natural analogue to the sense studied by Bousquet et al., 2023: Namely, to express a fine-grained concept-nonuniform rate, we would require a bound $d/n$ to hold for all sufficiently large $n$, where \"sufficiently large\" may only depend on $f$ (not the marginal on $x$) and where $d$ may only depend on the class $\\mathcal{H}$.  For this definition, we can argue that the smallest such $d$ possible is proportional to the VC dimension of $\\mathcal{H}$ (or else such a constant $d$ does not exist if the VC dimension is infinite).  To see this, consider any shattered set of some size $k$, and for each sample size $n$ consider a marginal distribution which puts $1-O(k/n)$ mass on one point and $O(1/n)$ mass on each of the remaining $k-1$ points.  By standard lower bound arguments, for any learning algorithm, among the $2^{k-1}$ concepts which shatter these $k-1$ points while labeling the other point $0$, there exists one for which the expected error rate is $\\Omega(k/n)$. By the pigeonhole principle, among these $2^{k-1}$ functions, there exists at least one function witnessing this $\\Omega(k/n)$ lower bound for infinitely many $n$ (so that the marginal distribution in these lower bounds varies with $n$ but the target concept does not).  Therefore, for this concept, any $d/n$ lower bound holding for all sufficiently large $n$ must have $d = \\Omega(k)$, and since $k$ is simply the size of a shattered set, the conclusion follows."}, {"review_id": "LmMAyfoM64", "reviewer": "Reviewer_1Rvq", "summary": "The paper explores one of the four fundamental notions of PAC learnability that has not been thoroughly studied: marginal-nonuniform learnability, where the generalization rate may depend on the marginal distribution but must be consistent across all concepts. The authors present a clear trichotomy of possible learning rates under this framework: 1) exponential rate for finite classes, 2) linear rates determined by the VC-eluder dimension, and 3) arbitrarily slow rates when the dimension is unbounded. The results are accompanied by multiple matching lower bounds, a detailed analysis of the linear case, and a contextualization within the broader landscape of universal learning. The paper is purely theoretical and offers useful characterizations of how distribution dependence affects learnability.", "questions": "Please take a moment to review the comments and suggestions in the sections above. Let me know if anything seems missing, misunderstood, or could benefit from further clarification. Additionally,\n- Could the authors elaborate on whether the results are applicable in agnostic/non-realizable settings?\n- What common assumptions could cause the VC-eluder dimension to be significantly smaller than the VC dimension?\n- Are there specific examples that match the theoretical findings to illustrate the idea that \"some data distributions are inherently easier to learn from than others\"?", "limitations": "This work is purely theoretical and has minimal negative impact on society. The authors have already identified some gaps in their results and future directions, such as active learning settings, which should help address the limitations.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper examines a natural variation of nonuniform PAC learning that is both conceptually interesting and technically well-defined.\n- The main accomplishment is a precise trichotomy, providing a comprehensive classification of learning rates based on a single combinatorial parameter, the VC-euler dimension.\n- The presentation is clear, especially in the abstract and introduction, and the proofs use existing tools from prior work transparently.\n- The paper connects to established frameworks in universal and concept-non-uniform learning, effectively placing its contribution within the existing literature.\n\nWeaknesses:\n- The formulation of marginal-nonuniform learning is not entirely new. It originates from the taxonomy introduced by Ben-David et al. (1995), and the paper does not distinguish itself in terms of foundational definitions.\n- Many of the theoretical claims, including several lemmas and various example-based separations, directly build on existing results in the literature, which seem to require only modest adjustments rather than significant innovation.\n- The fine-grained analysis of the linear rate regime using the VC-eluder dimension appears to be the most technically challenging part of the paper (e.g., Lemmas 10-12). It would be helpful if the authors more clearly highlighted where genuine technical novelty appears.", "was_revised": true, "final_justification": "I assigned a score of 4 and supported the paper's acceptance because it presents \"a precise trichotomy, providing a comprehensive classification of learning rates based on a single combinatorial parameter, the VC-euler dimension.\"\n\nTo receive more substantial support, the authors should demonstrate novelty in some ways, such as in formulation or technical strategies. I understand that researchers often build their results on top of prior works and ideas. Still, a relatively straightforward extension or application of existing theorems and tools does not meet the novelty bar. \n\nThat being said, I thank the authors again for the helpful discussion and promised revisions, including adding more insights regarding the communicated points.", "rebuttal": "Thanks for your feedback.\n\n> The formulation of marginal-nonuniform learning is not entirely new. It originates from the taxonomy introduced by Ben-David et al. (1995), and the paper does not distinguish itself in terms of foundational definitions. \n\nWe will emphasize the distinction to Ben-David et al. (1995) more clearly in the revised version. Ben-David et al. introduced the marginal nonuniform setting; we characterized all possible rates and when they can occur. The fact that the model was studied before makes our results arguably more interesting in our opinion.\n\n> Many of the theoretical claims, including several lemmas and various example-based separations, directly build on existing results in the literature, which seem to require only modest adjustments rather than significant innovation.\nThe fine-grained analysis of the linear rate regime using the VC-eluder dimension appears to be the most technically challenging part of the paper (e.g., Lemmas 10-12). It would be helpful if the authors more clearly highlighted where genuine technical novelty appears.\n\nWe thank the reviewer for this thoughtful remark and for highlighting the fine-grained analysis of the linear rate regime as a technically challenging contribution.\n\nFrom a technical standpoint, the closest prior work is that of Hanneke and Xu (2024), who study the performance of ERM in the universal learning setting. While some of the combinatorial structures that appear in both works are related, the connection is far from immediate. Their work focuses on the behavior of a specific algorithm—ERM—whereas our work addresses the more fundamental problem of characterizing optimal learning rates in an online, non-realizable setting. The emergence of similar combinatorial dimensions in these distinct contexts was not something we anticipated, and uncovering this link required significant conceptual effort.\n\nEven after this connection was identified, the technical approaches differ substantially. A key novelty in our work is the precise characterization of the linear rate regime via the VC-eluder dimension. In particular, Lemmas 10–12 hinge on a new and central argument based on König’s lemma, which we use to show that the version space eventually becomes confined to a subclass of VC dimension at most $\\mathrm{VCE}(H)$. To our knowledge, this application of König’s lemma is new in the learning theory literature and plays a critical role in our analysis. We are pleased that the reviewer found this component to be technically challenging—it is indeed one of the central contributions of the paper.\n\n\n> Could the authors elaborate on whether the results are applicable in agnostic/non-realizable settings?\n\nNo our approach does not immediately apply in the agnostic setting. We believe that this would likely require considerable effort and novel techniques. Nevertheless, we think that the realizable case is already technically rich and substantial by itself. \n\nThe agnostic case is of course interesting. There is even an interesting question about what is the appropriate formulation of the setting for the agnostic case. For instance, we could consider the supremum over all conditional distributions, or we could consider only deterministic labels and consider the supremum over all labeling functions. This is an interesting direction for future work.\n\n> What common assumptions could cause the VC-eluder dimension to be significantly smaller than the VC dimension?\n\nGreat question! A simple necessary condition for the VC-eluder dimension to be large is an infinite number of large disjoint shatterable sets. Thus, if the VC dimension is large, however only a bounded number of large disjoint sets are shatterable, the VC-eluder dimension will be small (or even 0). For example finite classes can have $\\operatorname{VC}$ up to $\\log|\\mathcal{H}|$ while $\\operatorname{VCE}=0$ always.\n\n> Are there specific examples that match the theoretical findings to illustrate the idea that \"some data distributions are inherently easier to learn from than others\"?\n\nThe proof of our $\\operatorname{VCE}(\\mathcal H)/n$ upper bound might provide some intuition. The marginal-dependent constants are mostly given by certain tail probabilities indicating when all version spaces will have bounded VC dimension on the data sequence with constant probability. In some sense samples from worst-case distributions behave in a way such that the version space (for a specific labeling) continues to have large VC dimension. By contrast, \"simpler\" distributions will produce samples that likely result in small VC dimension of the version space on data sets which can be sampled from the distribution.\n\nAs a simple example of a distribution where the dimension of learning is smaller than the worst-case distribution (even before restricting to a version space), consider the class of linear classifiers in $\\mathbb{R}^d$ but with a distribution supported on a $k < d$ dimensional subspace."}, {"review_id": "yYpmpMnapp", "reviewer": "Reviewer_ycGG", "summary": "This paper revisits the classical model of non-uniform PAC learning, where the error convergence rate includes constants depend on the true concept or the data distribution. The main conclusion of this paper is that when considering marginal-nonuniform learning (case that the constant allows to be dependent on feature distribution but is required to be uniform across concepts), the optimal rate is a trichonomy, characterized by the VC-eluder dimension. This reveals some inclusions regarding uniform learning at rate $1/n$ and some non-uniform rates.", "questions": "- I am concerning the significance and applicability of theoretically studying the non-uniform settings of learning \\emph{in the present days}. Specifically, casting at its greatest generality, what conclusions can be drawn from research in this direction, and what problems can be solved? How does resolving these issues promote the study of machine learning theory or assist in solving real-world machine learning problems? I appreciate that this is a fundamental research area that worth to investigate, but to be honest, such concern affect my score to some extent (and sadly, I can hardly tell a clear criteria of how this affects). I would appreciate it if the authors could share some opinions at this point. \n - In line 106-107 you've mentioned that \"there are families of classes such that $VCE(\\mathcal{H})=1$\", while $VC(\\mathcal{H})$ is unbounded\", while in line 135-136 you said that $1\\leq VCE(\\mathcal{H}) <\\infty$ is equivalent to $|\\mathcal{H}|=\\infty$ and $VC(\\mathcal{H})<\\infty$. Do these two statements mean that while there exists classes $\\mathcal{H}$ with VCE-dimension $1$ and *arbitrarily large* VC-dimension, there does not exist a class $\\mathcal{H}$ with VCE-dimension $1$ and *infinite* VC-dimension?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The problem is fundamental in machine learning theory. The paper is generally well-written. The problem investigated in the paper is clearly proposed and defined, the symbols and proofs are standard that easy to follow. The results are clear, with proper comparison and discussions to the results in related topics.\n\nWeaknesses: I only have some suggestions:\n  - Current draft seems somewhat \"heavy\" in math. The definitions of \"different learning cases\", \"trichonomy rates\" and notions of \"at rate\", \"not faster than\", all require large text space. Besides, the authors provide most of the proofs in main text. As a paper with page limit of 9, the main body of the paper is full of definitions, theorems and proofs, sometimes hard to follow. Is it possible to reduce the appearance of similar definitions or theorems, and put more proofs into the appendix?\n  - While it is definitely OK to prove some of the results in this paper by adapting from [Hanneke and xu, 2024], it would be better if the authors could discuss how the proof techniques (rather than setting) in this paper differ from that of previous works. \n  - The cross-marks in Fig.1 may incur some mis-understandings that the corresponding regions are empty, while the marked areas are proven to be non-empty. It would be better if they could be replaced by some other symbols.\n  - The last section includes 8 paragraphs of discussions, while some of them are similar and some of them seems a bit minor. Fewer paragraphs of discussions with better organization of the topics may be better.", "was_revised": true, "final_justification": "Thanks the authors for the detailed response. My concern has been properly resolved, and specifically, it convinced me that the paper fits within the borader theme of beyond-the-worst-case generalization analysis, which definitely serves as one of the necessary directions that push forward the study of learning theory. Therefore, I have updated the review and kept my score.", "rebuttal": "Thank you for the feedback.\n\n> Current draft seems somewhat \"heavy\" in math. The definitions of \"different learning cases\", \"trichonomy rates\" and notions of \"at rate\", \"not faster than\", all require large text space. Besides, the authors provide most of the proofs in main text. As a paper with page limit of 9, the main body of the paper is full of definitions, theorems and proofs, sometimes hard to follow. Is it possible to reduce the appearance of similar definitions or theorems, and put more proofs into the appendix?\n\nWe will add more exposition and explanation to the revised version. \n\n\n> While it is definitely OK to prove some of the results in this paper by adapting from [Hanneke and xu, 2024], it would be better if the authors could discuss how the proof techniques (rather than setting) in this paper differ from that of previous works. \n\nWe thank the reviewer for prompting a more detailed comparison with the recent work of Hanneke and Xu (2024). While the combinatorial structures in our analysis resemble those used in their study of ERM, we stress that this connection is far from immediate. Conceptually, the two works address different questions: Hanneke and Xu analyze the performance of a specific algorithm—ERM— in the univsesal setting , whereas our work investigates *optimal learning rates* in a different, semi non-uniform context. The fact that related combinatorial dimensions appear in both analyses is surprising and not something that could have been anticipated a priori; uncovering this connection required significant effort.\n\nEven after identifying this link, our technical development diverges in important ways. Most notably, our fine-grained characterization of learning rates in terms of $\\text{VCE}(H)/n$ introduces new analytical techniques. In particular, we make essential use of a novel application of König’s lemma to show that the version space eventually collapses to a class of VC dimension at most $\\text{VCE}(H)$ on future instances. This argument plays a central role in our analysis and, to the best of our knowledge, does not appear in prior work.\n\n> The cross-marks in Fig.1 may incur some mis-understandings that the corresponding regions are empty, while the marked areas are proven to be non-empty. It would be better if they could be replaced by some other symbols.\n\nThanks, we will improve Figure 1.\n\n> The last section includes 8 paragraphs of discussions, while some of them are similar and some of them seems a bit minor. Fewer paragraphs of discussions with better organization of the topics may be better.\n\nThanks for the comment. We will improve the exposition here.\n\n> I am concerning the significance and applicability of theoretically studying the non-uniform settings of learning \\emph{in the present days}. Specifically, casting at its greatest generality, what conclusions can be drawn from research in this direction, and what problems can be solved? How does resolving these issues promote the study of machine learning theory or assist in solving real-world machine learning problems? I appreciate that this is a fundamental research area that worth to investigate, but to be honest, such concern affect my score to some extent (and sadly, I can hardly tell a clear criteria of how this affects). I would appreciate it if the authors could share some opinions at this point. \n\nWe believe that our results can provide guidance and improve our understanding when and how sample efficient learning from data is possible. We provide some theoretical support for the intuition that some distributions are easier to learn than others. In this sense our work can be placed into the broader theme of generalization guarantes **beyond the worst-case**. E.g., standard uniform PAC learning rates are typically “too worst-case” and in practice much better error rates are observed. Marginal non-uniform learning, similarly to universal learning and classic concept-nonuniform rates (e.g., structural risk minimization), can provide some understanding and explanation for these faster rates (and/or rates with much smaller constants) observed in real applications. This is possible as in such nonuniform/universal learning models a different order of quantifiers is used compared to standard PAC learnability, allowing it to be less focused on the worst-case. Overall this promotes the development of a generalization theory that is more flexible and expressive to capture properties of the data, which makes it easier to learn.\n\n> In line 106-107 you've mentioned that \"there are families of classes such that $\\operatorname{VCE}(\\mathcal H)=1$ \", while $\\operatorname{VC}(\\mathcal H)$ is unbounded\", while in line 135-136 you said that $1\\le\\operatorname{VCE}(\\mathcal H)<\\infty$ is equivalent to $|\\mathcal H|=\\infty$ and  $\\operatorname{VC}(\\mathcal H)<\\infty$. Do these two statements mean that while there exists classes $\\mathcal H$ with VCE-dimension 1 and arbitrarily large VC-dimension, there does not exist a class $\\mathcal H$ with VCE-dimension $1$ and infinite VC-dimension?\n\nExactly, $\\operatorname{VCE}\n\\leq \\operatorname{VC}$ but for each $d \\in\\mathbb{N}$\nthere is a class $\\mathcal H_d$\nwith $\\operatorname{VC}(\\mathcal\nH_d)=d$ and $\\operatorname{VCE}\n(\\mathcal H_d)=1$. However, $ \\operatorname{VC}=\\infty$ if and only if $\\operatorname{VCE}=\\infty$. Such a class $\\mathcal H_d$ can be obtained by taking a disjoint union of shattered sets."}, {"review_id": "dRgfCYZmfw", "reviewer": "Reviewer_NqaX", "summary": "This paper considers the problem of marginal-nonuniform PAC learning. Here there is a known class C of functions on a space X. One wants to (realizably) PAC learn an unknown function f in C on an unknown distribution D on X, but in a way where the rate at which the error converges to 0 in terms of samples is allowed to depend on the marginal distribution D.\n\nIn particular, they say that you can learn with rate R (for some function R going monotonly to 0) if there is an algorithm A so that after receiving n samples (x,y) where x ~ D and y = f(x) for some f in C returns a hypothesis h with error over C at most O_D( R( Omega_D(n) ) ). In other words, when run with any fixed marginal D, the error goes to 0 at a rate with the same functional form as R.\n\nThe main result of this paper is a classification of achievable rates. In particular:\n1) In some trivial cases, one can learn in <= 1 sample and take R = 0.\n2) Otherwise, if C is finite, one learns with exponential rate R(n) = e^{-n}.\n3) Otherwise, if C has finite VC dimension, one learns with rate R(n) = 1/n.\n4) Finally, if C has infinite VC dimension, then there is no rate R(n) that goes to 0 so that we can learn with rate R.\n\nThey also show that in case (3) the learning rate can be taken more precisely to be bounded by O(d/n) where d is the VC-eluder-dimension.", "questions": "* Is the proof of Theorem 16 essentially just contained in the citations given? If not, what is the proof?\n* What *was* previously known about this problem?\n* What in general do you mean by considering fine-grained rates?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The basic idea of marginal-nonuniform learning is a nice one and this paper essentially solves some version of it.\n* The final classification is clean and not entirely expected.\n* The proofs are easy to follow.\n* Generally the background is well explained.\n\nWeaknesses:\n* The technical definition of this kind of marginal-nonuniform learning in terms of rate functions R is a bit complicated and not especially natural.\n* The results here are all relatively easy and do not seem to introduce technical tools that are likely to have broader applicability. (Though the VCE stuff has some more complicated ideas)\n\nComments:\n* Line 91: *What* is a strict version of the realizability assumption? My initial read was that you were claiming that the function er was.\n* Definition 2:\n - Isn't h_n^ more naturally the (randomized) output of an algorithm rather than the algorithm itself?\n - What do you mean by \"a faster rule than rate R\"?", "was_revised": true, "final_justification": "It's a solid paper. I am not quite sure that it meets the threshold of \"Technically solid paper, with high impact on at least one sub-area of AI or moderate-to-high impact on more than one area of AI\" because the result seems a little specialized.", "rebuttal": "Thanks for the feedback.\n\n> The technical definition of this kind of marginal-nonuniform learning in terms of rate functions R is a bit complicated and not especially natural.\n\nWe will provide more exposition in the revised version. Intuitively our error rates allow a dependence on the marginal distribution generating the unlabeled data points. In the context of universal PAC learning (Bousquet et al., 2021) our definition (Definition 2) is the natural variant of an error rate with constants depending on just the marginal distribution instead of the full distribution over $X\\times Y$ (as in universal learning).\n\n> The results here are all relatively easy and do not seem to introduce technical tools that are likely to have broader applicability.\n\nWe politely disagree. We believe that identifying the right structure (VCE-dimension) for marginal nonuniform learning is non-trivial and valuable. After considerable technical difficulties this then lead to our rate trichotomy. In particular, our result on fine-grained learnability with rate $\\operatorname{VCE}(H)/n$ requires novel ideas to show that any version space will have eventually finite VC dimension (with probability $1$) relying on König’s Lemma. This might be of interest for other learning settings, as well. We will clarify our exposition in the revised version and add a proof sketch of this main result, which is currently only in the appendix.\n\n> Line 91: What is a strict version of the realizability assumption? My initial read was that you were claiming that the function er was.\n\nWe call it \"strict\", since we assume that $f^*\\in\\mathcal H$. That is in contrast to the (weaker) realizability notion of Bousquet et al. (2021) in unviersal learning. Basically we take the minimum instead of an infimum, see Section 6 for more details.\n\n> Isn't h_n^ more naturally the (randomized) output of an algorithm rather than the algorithm itself?\n\nWe choose to follow the notation in universal PAC learning (Bousquet et al., 2021 and follow up works), which slightly conflates the algorithm and the output hypothesis. The reason is that writing $A(S)$ for the output hypothesis requires explicitly stating/defining the learning algorithm $A$, which can be a bit convoluted sometimes.\n\n> What do you mean by \"a faster rule than rate R\"?\n\nIf you mean “rate faster than rate R” then please see Definition 2.2. This follows similar definitions in universal learning (Bousquet et al. 2021).\n\n> Is the proof of Theorem 16 essentially just contained in the citations given? If not, what is the proof?\n\nNo. Previous results show that a class is concept-nonuniformly learnable (ignoring rates) if and only if it is a countable union of VC classes (Lemma 15, which is proven by Benedek and Itai (1994)). The best known rate was $\\log(n)/n$. We show that the optimal rate is $1/n$, which is achievable whenever the class is concept-nonuniformly learnable at all. The proof is in the appendix.\n\n> What was previously known about this problem?\n\nIf you mean concept-nonuniform learnability see the above comment. If you instead mean marginal-nonuniform learnability then not much was known besides the definition itself and certain relationships with related learning settings (see Ben-David et al., 1995). We are the first to obtain the three possible cases and the exact rates.\n\n> What in general do you mean by considering fine-grained rates?\n\nBy fine-grained rates, we refer to tighter bounds that offer sharper control over the tails of the learning curves—that is, in the regime of large sample sizes. In both this paper and earlier work by Bousquet et al (2023), the bounds are distribution-dependent: for each distribution $D$, the bound may begin to apply only after a certain threshold $N(D)$, but once it does, it is significantly sharper than the counterpart coarse-grained counterparts. For example, in this work, the VC-eluder dimension (VCE) replaces the VC dimension in the linear-rate regime, yielding potentially much tighter rates when VCE is substantially smaller than VC."}]

Author rebuttal:

Meta-review: This paper considers the question of marginal-nonuniform learnability, requiring learners to depend uniformly on the target concept but only non-uniformly on the marginal distribution.

The reviewers found the paper to be clearly written and the results, which fill in the gap between previously studied models, to be sharp and satisfying. Hence, this would be a nice addition to NeurIPS.

The reviewers had several suggestions, which I expect the authors to address in the camera-ready version. Here are a few of these suggestions, but I encourage the reviewers to apply as many of these suggestions as possible. (1) The proofs closely follow prior work (Hanneke and Xu 2024), so it would be good to highlight the difference more clearly. (2) Please cite and discuss Feldman's work, which is missing. (3) Please specify the origin of the model studied in this paper more clearly. (4)  Please provide a bit more intuition or cases in which marginal non-uniform learnability is distinct from universal learning.
Decision: Accept (poster)