Marginal-Nonuniform PAC Learnability

Thanks for the feedback.

The technical definition of this kind of marginal-nonuniform learning in terms of rate functions R is a bit complicated and not especially natural.

We 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).

The results here are all relatively easy and do not seem to introduce technical tools that are likely to have broader applicability.

We 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.

Line 91: What is a strict version of the realizability assumption? My initial read was that you were claiming that the function er was.

We 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.

Isn't h_n^ more naturally the (randomized) output of an algorithm rather than the algorithm itself?

We 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.

What do you mean by "a faster rule than rate R"?

If you mean “rate faster than rate R” then please see Definition 2.2. This follows similar definitions in universal learning (Bousquet et al. 2021).

Is the proof of Theorem 16 essentially just contained in the citations given? If not, what is the proof?

No. 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.

What was previously known about this problem?

If 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.

What in general do you mean by considering fine-grained rates?

By 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.

Thank you for the feedback.

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?

We will add more exposition and explanation to the revised version.

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.

We 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.

Even 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.

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.

Thanks, we will improve Figure 1.

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.

Thanks for the comment. We will improve the exposition here.

I am concerning the significance and applicability of theoretically studying the non-uniform settings of learning 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.

We 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.

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?

Exactly, $\operatorname{VCE} \leq \operatorname{VC}$ but for each $d \in\mathbb{N}$ there is a class $\mathcal H_d$ with $\operatorname{VC}(\mathcal H_d)=d$ and $\operatorname{VCE} (\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.

Thanks for your feedback.

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.

We 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.

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. 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.

We thank the reviewer for this thoughtful remark and for highlighting the fine-grained analysis of the linear rate regime as a technically challenging contribution.

From 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.

Even 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.

Could the authors elaborate on whether the results are applicable in agnostic/non-realizable settings?

No 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.

The 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.

What common assumptions could cause the VC-eluder dimension to be significantly smaller than the VC dimension?

Great 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.

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"?

The 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.

As 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.

Thank you for your feedback.

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.

Thanks 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. Our 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.

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.

While 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.

Furthermore, 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.

Does Theorem 16 (or its proof) suggest a characterization of the fine-grained rate of concept-nonuniform learnability of countable unions of VC classes?

Good 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.

Thanks a lot for your encouraging feedback!

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.

We agree that the learnability question is interesting and view it as an intriguing direction for future work. Nevertheless, 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. Moreover, notice that our results do provide a complete characterization of what optimal learning rates are possible—exponential, linear, arbitrarily slow, and non-learnable.

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?

We 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.

There 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.

On 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.

We will expand on these points and add more such concrete examples to our examples section in the revised version.

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)

While 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.

Furthermore, 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.

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)

The 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.

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?

We 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).

Can you say anything about learnability in the agnostic case?

See above.