Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale Shashaank Aiyer1 , Yishay Mansour2 , Shay Moran3 , Han Shao1 , and Tom Waknine4 1
arXiv:2605.13684v1 [cs.LG] 13 May 2026
2
University of Maryland Tel Aviv University and Google Research 3 Technion and Google Research 4 Technion
Abstract We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class F and every γ > 0, uniform convergence at scale γ, agnostic learnability at scale γ/2, and finiteness of the fat-shattering dimension at every scale γ ′ > γ are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press ’99) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS ’98), which incur such a loss. The key technical ingredient is a direct bound on empirical ℓ∞ covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale γ: an O(log2 n) bound holds already at scale γ/2, while an O(log n) bound holds at scale 2γ. We further show that the O(log2 n) bound is sometimes tight. These results resolve open questions by Alon et al. (JACM ’97) and Rudelson and Vershynin (Ann. of Math. ’06). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor c < 3, while 3-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML ’26). We also highlight several open questions on quantitative sample complexity and evaluability.
1
Introduction
One of the central results in statistical learning theory is the fundamental theorem of PAC learning, which establishes an equivalence between three different notions: agnostic learnability, uniform convergence, and finiteness of the VC dimension. In the binary classification setting, this theorem provides a complete characterization of when a class of functions can be learned from data in a distribution-free manner, and serves as a cornerstone of learning theory [Vap71, BEHW89]. A natural extension of this framework considers real-valued function classes F, where predictions are no longer binary but continuous. In this setting the VC dimension is replaced by a scale-sensitive Authors are ordered alphabetically. Emails: [email protected], [email protected], [email protected]
1
extension called the fat-shattering dimension (defined below). This notion was introduced in learning theory by Kearns and Schapire [KS94], and also appears in approximation theory (see Lorentz [Lor86], and Tikhomirov [Tik60] who attributes it to earlier work of Kolmogorov). Understanding the relationship between learnability, fat-shattering, and uniform convergence in the real-valued setting has been a long-standing goal. The classical no-free-lunch argument shows that if the γ-fat-shattering dimension is unbounded, then the class is not learnable at scale γ/2 and does not satisfy uniform convergence at scale γ, reflecting a scale-sensitive version of the no-free-lunch principle. In the opposite direction, Alon et al. [ABDCBH97] showed that finite γ-fat-shattering dimension implies uniform convergence (and hence learnability) at scale cγ for some universal constant c ≥ 10. This was later improved by Bartlett and Long [BL98], who established the same implication for any constant c > 2. However, it remained open whether the fat-shattering dimension provides a sharp characterization of learnability and uniform convergence at the optimal scale. This question has been investigated in a sequence of works, and is discussed in detail in the textbook of Anthony and Bartlett [AB99] (see Section 12.7), where it is noted that the gap between the necessary and sufficient scales may be unavoidable - a conjecture attributed there to Phil Long. For additional background, historical context, and a gentle technical introduction, we refer the reader to Chapters 11 and 12 of that book. Our first main result resolves this question by establishing an exact scale-sensitive analogue of the fundamental theorem of PAC learning in the real-valued setting, thereby refuting the conjecture that the factor-2 gap is unavoidable. To state the result, we briefly recall the relevant notions. Let X be a domain, let F ⊂ [−R, R]X be a class of bounded real-valued functions over X , and let γ > 0. We say that F satisfies γ-uniform convergence if for every ε, δ > 0 there exists m such that for every distribution q over X , with probability at least 1 − δ over a sample S ∼ q n of size n ≥ m, sup Ex∼q [f (x)] −
f ∈F
1X f (x) ≤ γ + ε. n x∈S
We say that F is γ-learnable if there exists a learner A (that is, a mapping from samples to hypotheses) such that for every ε, δ > 0 there exists m such that for every distribution q over X × [−R, R], with probability at least 1 − δ over S ∼ q n of size n ≥ m, E AS (x) − y ≤ inf E [|f (x) − y|] + γ + ε, (x,y)∼q
f ∈F (x,y)∼q
where AS denotes the hypothesis output by A on input sample S. Finally, the γ-fat-shattering dimension of F, denoted fatγ (F), is the largest integer d for which there exist points x1 , . . . , xd ∈ X and thresholds r1 , . . . , rd ∈ R such that for every b ∈ {±1}d there exists f ∈ F satisfying f (xi ) ≥ ri + γ2 if bi = +1,
and f (xi ) ≤ ri − γ2 if bi = −1.
If for arbitrarily large d there exist points x1 , . . . , xd and thresholds r1 , . . . , rd satisfying the above, we say that fatγ (F) = ∞. When F consists of {0, 1}-valued functions and the scale γ < 1, the fat-shattering dimension coincides with the VC dimension, and these notions reduce to their classical binary counterparts. Thus, the real-valued framework can be viewed as a strict generalization of the binary setting. Theorem 1. Let F ⊂ [−R, R]X be a bounded function class and let γ > 0. Then, the following are equivalent:
2
1. F is γ2 -learnable; 2. F satisfies γ-uniform convergence; 3. for every γ ′ > γ, the γ ′ -fat-shattering dimension of F is finite. The proof appears in Section 4.2. The challenging directions in Theorem 1 are (3) ⇒ (1) and (3) ⇒ (2). The converse implications (1) ⇒ (3) and (2) ⇒ (3) follow from standard no-free-lunch arguments, see, e.g., [AB99, BL98]. Covering Numbers. The derivation of uniform convergence from finite combinatorial dimension follows the classical approach of Vapnik and Chervonenkis. The argument proceeds via symmetrization (also known as double sampling), which reduces the problem to controlling the behavior of the class on a finite sample. In the binary case, the behavior of the class is controlled using the Sauer-Shelah Lemma [Sau72], which bounds the number of distinct labelings induced by the class on a sample of size n. This combinatorial bound allows one to replace an infinite union bound with a finite one. In the real-valued setting, the role of the Sauer–Shelah Lemma is played by covering numbers. Concretely, for F ⊂ [−R, R]X , the empirical ℓ∞ covering number N (F, γ, n) is the smallest integer N for which for any sequence x1 , . . . , xn , there exist functions g1 , . . . , gN : X → R such that for every f ∈ F, there exists i ∈ [N ] satisfying maxj∈[n] |f (xj ) − gi (xj )| ≤ γ. The quantity H(F , γ, n) := log N (F , γ, n) is called the (empirical) metric entropy, and serves as the appropriate analogue of the combinatorial growth function. A classical result of Dudley et al. [DGZ91] shows that sublinear entropy growth, namely H(F, γ/2, n) = o(n), implies γ-uniform convergence. A long line of work has sought to bound this entropy in terms of the fat-shattering dimension. Alon et al. [ABDCBH97] showed that if fatγ (F) < ∞, then H(F, 2γ, n) = O(log2 n) In addition to establishing this bound, they explicitly asked whether the log2 n dependence is inherent, or whether it can be improved to O(log n). Subsequent work of Rudelson and Vershynin [RV06] showed that if one allows the scale to increase further, then the entropy bound can be improved: for every ε > 0, 1+ε H F, cγ n . ε , n = O log They further asked whether the exponent of the logarithm can be reduced all the way to 1, i.e., whether an O(log n) bound is achievable. These results are obtained by first controlling packing numbers and then passing to covering numbers, which necessarily incurs a loss in the scale. Our approach departs from this line of work by bounding covering numbers directly, without passing through packing arguments. This allows us to obtain sharp bounds at the optimal scale. Our second main result establishes the optimal scale at which the metric entropy becomes sublinear, and refines the known bounds on its growth across different scales. Theorem 2. Let F ⊂ [−R, R]X be a bounded function class, and let γ ⋆ = inf{γ > 0 : fatγ (F) < ∞}.
3
Thena , ⋆ Θ(n) γ ∈ (0, γ2 ), ⋆ H(F , γ, n) = O(log2 n) γ ∈ ( γ2 , 2γ ⋆ ], O(log n) γ ∈ (2γ ⋆ , R). ⋆ Moreover, the second regime is tight for γ ∈ γ2 , γ ⋆ : there exist F s.t. for all γ < γ ⋆ , H(F , γ, n) = Ω log2−o(1) n . The third regime is tight: there exist F such that H(F, γ, n) = Ω(log n) for γ ∈ (2γ ⋆ , R). a Throughout, the asymptotic notation treats n as the parameter tending to infinity; the implicit constants may depend on γ and on the fat-shattering dimension at scale γ.
The proof appears in Section 4.3. The same result holds for any bounded function class F ⊆ RX ; we restrict to the range [0, 1] for notational convenience. In light of the O(log1+ε n) bounds of Rudelson and Vershynin [RV06] mentioned above, which left open whether the exponent can be improved to 1, our result resolves this question. It also answers the question of Alon et al. [ABDCBH97] on whether the log2 n bound can be improved to log n, by showing that such an improvement is possible at scales above 2γ ⋆ , but impossible (up to lower-order terms) below γ ⋆ . The first and third regimes are tight and well understood from prior work: below γ ⋆ /2, linear entropy growth holds for every class, while above 2γ ⋆ there exist classes with entropy Ω(log n). Thus, on the lower bound side our main contribution is that the O(log2 n) bound is sometimes tight (up to lower-order terms). We remark that the case γ = γ ⋆ /2 is not covered by the theorem, and there are simple examples exhibiting either behavior; see Proposition 4. We leave open the problem of characterizing the precise behavior of the entropy in the intermediate range γ ⋆ < γ ≤ 2γ ⋆ , as well as obtaining sharp sample complexity bounds for learning and uniform convergence at the optimal scale. We also leave open the problem of obtaining optimal relationships between the fat-shattering dimension and covering numbers under other ℓp metrics. Such covering numbers have been studied extensively, e.g. [BKP97, AB99, Men02, MV03]. In Section 1.2, we illustrate a simple application of our results by deriving closure properties and composition theorems for uniform convergence and learnability. We next turn to a different - and perhaps more surprising - application, where we use the sharp scale-sensitive results to resolve an open question of [AMMS26] concerning the evaluability and estimability of generative models. Remarkably, the quantitative improvement from a factor of 2 to 1 in the scale unlocks a qualitative characterization: a sharp dichotomy between estimability and evaluability. We elaborate on this connection in the following section.
1.1
Evaluability and Estimability of Generative Models
How can one test whether a generative model truly generalizes? Consider a model trained to generate images or short musical tunes from a dataset. When it produces new samples, are these genuinely novel, or merely recombinations - or even copies - of the training data? Given only sample access to the true distribution, can we reliably determine whether the generator generalizes well? Can indistinguishability between generated and real samples be tested from finite data? In practice, such questions are addressed via evaluation metrics that quantify the discrepancy between the generated and target distributions. A recent work by [AMMS26] introduced a general 4
framework for studying such metrics as tools for generalization testing. A central class of metrics in this framework is given by integral probability metrics (IPMs): dF (q, q ⋆ ) := sup |Eq [f ] − Eq⋆ [f ]| , f ∈F
where F is a class of real-valued functions f : X → R defined on the data domain X . Intuitively, dF measures how well one can distinguish q from q ⋆ using tests from F . Classical examples of IPMs include total variation distance, obtained when F is the set of all measurable functions bounded in [0, 1], and the Wasserstein-1 distance, which arises when F is the class of 1-Lipschitz functions with respect to a given metric on X . We next formalize the setup and introduce evaluability and estimability, following the framework of [AMMS26]. Let X denote the data domain. A model is a probability distribution over X , representing a generative model of the data. We let M = ∆(X ) denote the set of all probability distributions over X . We assume there exists an unknown ground-truth model q ⋆ ∈ M from which data is sampled. An evaluation algorithm A takes as input two candidate models q1 , q2 ∈ M and an evaluation sample Seval drawn from q ⋆ , and outputs one of the two models, interpreted as the model it judges to be better. A common class of evaluation algorithms operates by assigning each model a score based on the evaluation data and selecting the model with the smaller score. Evaluability. For c ≥ 1, we say that dF is c-weakly evaluable if there exists a sample complexity function mevl : (0, 1)2 → N and an evaluation algorithm A such that for every pair of models q1 , q2 ∈ M, every ε, δ ∈ (0, 1) and every ground-truth model q ⋆ , given IID evaluation data Seval = {x1 , . . . , xm } of size m ≥ mevl (ε, δ) with xi ∼ q ⋆ , with probability at least 1 − δ, A({q1 , q2 }, Seval ) = q1 =⇒ dF (q1 , q ⋆ ) ≤ c · dF (q2 , q ⋆ ) + ε , and
A({q1 , q2 }, Seval ) = q2 =⇒ dF (q2 , q ⋆ ) ≤ c · dF (q1 , q ⋆ ) + ε .
Thus, evaluability asks whether two candidate models can be reliably compared using only samples from the ground-truth distribution. The evaluation algorithm need not estimate the true distances themselves; it only needs to select a model whose distance to q ⋆ is no worse than that of the alternative, up to a multiplicative factor c and an additive error ε. We say that dF is weakly evaluable with optimal scale c if it is c-weakly evaluable and there does not exist any c′ < c such that it is c′ -weakly evaluable. When c = 1, we say that dF is strongly evaluable. Estimability. We say that dF is estimable if there exists a sample complexity function mest : (0, 1)2 → N and a score function s such that for any ε, δ ∈ (0, 1), any ground-truth model q ⋆ , and any model q ∈ M, given IID evaluation data Seval = {x1 , . . . , xm } of size m ≥ mest (ε, δ) with xi ∼ q ⋆ , with probability at least 1 − δ, s(q, Seval ) − dF (q, q ⋆ ) ≤ ε. In contrast to evaluability, which concerns relative comparison, estimability requires accurately approximating the value of the metric itself. In particular, estimability implies strong evaluability. A central result of [AMMS26] establishes a dichotomy for IPMs induced by {0, 1}-valued test functions: such metrics are either estimable (and hence strongly evaluable), or weakly evaluable with optimal scale c = 3. Their proof, however, is tailored to the {0, 1}-valued setting, relying on tools such as VC-dimension and uniform convergence for binary-valued classes. 5
Extending this result to general real-valued test classes is significantly more challenging. In particular, the binary setting allows one to leverage VC-dimension arguments directly, whereas in the real-valued case the appropriate complexity measure is the fat-shattering dimension, and its connection to uniform convergence is more delicate. A key obstacle is that the classical results of [BL98] only guarantee uniform convergence at scale 2γ, which is insufficient for the evaluability guarantees required here. Our approach overcomes this difficulty by establishing uniform convergence at the optimal scale γ. Crucially, eliminating this factor-2 loss is essential: without it, the argument breaks down and yields no non-trivial weak evaluability guarantee for real-valued IPMs. Theorem 3. Every bounded IPM is either: 1. estimable, and hence strongly evaluable; or 2. weakly evaluable with optimal scale c = 3. We further characterize this dichotomy in terms of the fat-shattering dimension of the test class. Proposition 1. Let F be a class of bounded real-valued functions. 1. If fatγ (F) < ∞ for all γ > 0, then dF is estimable (and hence strongly evaluable). 2. If there exists γ ∈ (0, 1/2) such that fatγ (F) = ∞, then dF is weakly evaluable with optimal scale c = 3. The proof is in Section 5.2. The above results are qualitative in nature and are most meaningful over infinite domains. Indeed, over a finite domain X of size N , every bounded IPM is estimable with O(N/ε2 ) samples, and hence strongly evaluable. This raises the question of whether quantitative analogues of the above dichotomy hold in the finite-domain setting. For example, as a function of the domain size N , how does the sample complexity of weak evaluability behave as the approximation factor improves from c = 3 to c = 1? Moreover, is the sample complexity required for strong evaluability comparable to that required for estimability? Understanding these questions would provide a more refined picture of the trade-offs between sample complexity and evaluation in practical settings.
1.2
Composition and Closure Properties
We now return to the setting of real-valued function learning and uniform convergence, and describe a more direct and standard application of Theorem 1, in contrast to the more involved application to evaluability discussed above. Characterizations of learnability using combinatorial dimensions are ubiquitous in learning theory, and a natural litmus test for their usefulness is whether they can be used to derive new results that are otherwise harder to prove. While the usefulness of the fat-shattering dimension is well established, we use it here to illustrate another application of Theorem 1. Specifically, we show that the properties of being γ-learnable and of satisfying γ-uniform convergence are invariant under natural operations. By Theorem 1, this reduces to showing that the property of having finite γ-fat-shattering dimension is invariant under these operations. The latter is essentially well known and relies on arguments from prior work, which we include here for completeness. The novel ingredient is therefore Theorem 1, which establishes the equivalence between finite fat-shattering 6
dimension and learnability and uniform convergence at the optimal scale, thereby yielding closure properties for these notions. As a first example, consider the dual class. For a function class F ⊂ [0, 1]X , its dual class F ⋆ is a class of functions over F , defined by F ⋆ = {δx : x ∈ X }, where each δx : F → [0, 1] is given by δx (f ) = f (x). Assouad’s bound [Ass83] relates the VC dimension of a class to that of its dual. This result extends naturally to the setting of γ-shattering when a common threshold r ∈ (0, 1) is used across all points. A simple application of the pigeonhole principle then shows that fatγ (F) is finite if and only if fatγ+ε (F ⋆ ) is finite for every ε > 0. As a corollary, we obtain the following result, which shows that γ-uniform convergence is preserved under taking duals. Proposition 2. Let γ > 0, and let F be a bounded function class that satisfies γ-uniform convergence. Then the dual class F ⋆ also satisfies γ-uniform convergence. The proof is in Section 4.4. Another closure property is stability under aggregation. Let G : [0, 1]k → [0, 1] be a function, and let f1 , . . . , fk : X → [0, 1]. Their aggregation with respect to G is defined by G(f1 , . . . , fk )(x) = G f1 (x), . . . , fk (x) . Given a sequence of function classes F1 , . . . , Fk , we define the aggregated class G(F1 , . . . , Fk ) = { G(f1 , . . . , fk ) : fi ∈ Fi for all i }. The fat-shattering dimension of such aggregated classes was studied in [AK24]. Our next result is similar in spirit to Theorem 2 of [AK24], but avoids the blow-up in the fat-shattering scale. As a consequence, we obtain that uniform convergence is closed under aggregation. Proposition 3. Let F1 , . . . , Fk ⊂ [0, 1]X be bounded function classes, each satisfying γ-uniform convergence, and let G : [0, 1]k → [0, 1] be a 1-Lipschitz function with respect to the ℓ∞ metric. Then the aggregated class G(F1 , . . . , Fk ) also satisfies γ-uniform convergence. The proof is in Section 4.4, and follows as a consequence of Theorem 1, by showing that an aggregation of covers is a cover for the aggregated class.
2
Related Work
The relationship between fat-shattering dimension, uniform convergence, and covering numbers is well established in statistical learning theory. The characterization of uniform convergence via covering numbers is due to Dudley [Dud78, Dud84, DGZ91]. The fat-shattering dimension was introduced by Kearns and Schapire [KS94] as a complexity measure capturing the sample complexity of approximate learnability. In a seminal work, Alon et al. [ABDCBH97] showed that finite γfat-shattering dimension implies a O(log2 n) bound on the metric entropy at scale 2γ, thereby establishing a connection between fat-shattering and uniform convergence. They also conjectured that the log2 n dependence could be improved to log n. Building on these ideas, Bartlett and Long [BL98] made significant progress toward understanding the optimal dependence on the scale. In particular, they improved the result of [ABDCBH97] by 7
showing that finite γ-fat-shattering dimension implies a O(log2 n) bound on the metric entropy at scale γ + ε. They also established complementary lower bounds which, combined with classical results of Dudley and Pollard [DGZ91, Pol84], yield an equivalence between γ-fat-shattering and uniform convergence up to a factor of 2 in the scale. A comprehensive overview of these techniques appears in [AB99], where this factor-of-two gap is highlighted as an open problem; a conjecture attributed to Phil Long suggests that this gap may be unavoidable (see Sections 12.6–12.7). A complementary line of work focuses on improving covering number bounds themselves, rather than the scale at which they are obtained. These works often consider ℓ1 or ℓ2 metrics instead of ℓ∞ , leading to improved quantitative bounds on sample complexity. Early contributions include [BKP97, CBH98], followed by a sequence of works by Mendelson and Vershynin [MV02, MV03, Men02], which developed refined entropy bounds. This line of research culminated in the work of Rudelson and Vershynin [RV06], who obtained strong covering number bounds under various norms. Notably, they made progress toward the conjecture of [ABDCBH97] by improving the log2 n dependence to log1+ε n, at the cost of a multiplicative factor of 1/ε in the scale. They further conjectured that this dependence could be improved to O(log n). There are several additional directions related to these questions. Colomboni et al. [CEP25] used refined covering bounds to derive sharp sample complexity guarantees for uniform convergence. Hanneke et al. [HKS19] and Attias and Kontorovich [AHKS24] established connections between fat-shattering dimension and approximate sample compression schemes. Finally, recent works such as [AK24, KS23] study structural properties of fat-shattering dimension, including closure under aggregation and duality. The framework of evaluability was recently introduced by [AMMS26], which provides a theoretical formulation of the problem of statistically evaluating the performance of generative models from finite samples. This line of work is motivated in part by limitations of commonly used empirical scores, such as perplexity and its variants [FWL+ 25, HHT+ 24, PSZ+ 21, MMM20]. Commonly used metrics include KL divergence, total variation distance, and other divergences. One general class of metrics is integral probability metrics (IPMs), introduced by [Mü97], which subsume important examples such as total variation distance and the Wasserstein-1 distance. IPMs have been extensively studied in the context of density estimation, where, given sample access to a ground-truth distribution and a class of candidate distributions, the goal is to output the closest distribution in the class. In this setting, [Yat85] established an upper bound with multiplicative factor 3, and [BKM19] showed that this factor is optimal. [AMMS26] extended this factor of 3 from density estimation to evaluability for binary F . In this work, we further generalize these results to real-valued function classes.
3
Proof Overviews
3.1
Proof Overview of Theorem 1
The fact that a finite fat-shattering dimension is a necessary condition for uniform convergence and learnability is well established, and follows by considering the uniform distribution over large shattered sets; see, Theorem 22 and Theorem 26 in [BL98]. The main challenge is to show the converse direction, namely that finite fat-shattering dimension implies uniform convergence and learnability. The standard approach for deriving uniform convergence bounds, as in [BL98, ABDCBH97, CEP25], proceeds via symmetrization combined with classical probabilistic arguments, reducing the problem
8
to bounding covering numbers. Concretely, one needs to show that for all ε > 0, H(F , γ2 + ε, n) = 0, n→∞ n lim
where we recall H(F, γ, n) = log N (F, γ, n) denotes the empirical metric entropy of F with respect to the ℓ∞ metric. In prior works, the covering number is typically upper bounded via the packing number, which is easier to control. This reduction allows one to assume the existence of a well-separated set and bound its size using Sauer-type lemmas or volume arguments. However, this approach has an inherent limitation: a finite γ-fat-shattering dimension only guarantees a bound on the γ-packing number. This, in turn, yields a bound on the γ-covering number, leading to 2γ-uniform convergence and γ-learnability. To improve upon the result of [BL98], one must therefore bound the covering number directly, without relying on packing arguments. This introduces the main technical difficulty: bounding the covering number directly requires constructing an explicit cover, which may not consist of functions from the class itself. To address this, we employ the theory of partial concept classes [Lon01, AHHM22]. Let R > 0, and let F ⊂ [− R2 , R2 ]n be a bounded function class1 with finite γ-fat-shattering dimension fatγ (F) = d. We associate to each f ∈ F a partial binary function hf defined by f (x) ≥ γ2 , 1 hf (x) = −1 f (x) ≤ − γ2 , undefined otherwise. The VC dimension of the induced partial function class will be bounded by d. Hence, by [AHHM22], it admits a disambiguation of sub-exponential size: that is, there exists a set H ⊂ {−1, 1}n with |H| = nO(dlog n) such that for every f ∈ F, there exists h ∈ H satisfying h(x) = hf (x) whenever hf (x) is defined. This implies that if h(x) = 1, then f (x) ∈ [− γ2 , R2 ], and if h(x) = −1, then f (x) ∈ [− R2 , γ2 ]. Consequently, by associating, with each h ∈ H, a function ϕh , such that ϕh (x) = R−γ 4 when h(x) = 1 −R+γ O(dlog n) and ϕh (x) = 4 when h(x) = −1, we obtain a cover of F by n boxes of radius γ+R 4 . To obtain finer scales, we iterate this construction. Starting from a coarse cover and recursively refining each box, the radius decreases geometrically and converges to γ2 , while at each step we incur a multiplicative increase of nO(dlog n) in the covering number size. Thus after k iterations we have a bound of nO(dklog n) on the covering number size at scale γ2 + 21k , yielding an effective bound on the covering number at all scales strictly larger than γ2 H(F , γ2 + ε, n) = O(d log
1 log2 n). ε
The γ2 -learnability result follows from a covering argument based on the algorithm of Theorem 21 in [BL98], combined with our improved covering bound to obtain a sharp rate. Given a sample γ (xi , yi )2n i=1 and a test point x, the algorithm constructs a ( 2 + ε)-cover of the restriction of F to these 2n + 1 points. It then outputs f (x), where f ∈ F minimizes the empirical loss over the first n points. Standard concentration inequalities ensure that the excess loss is controlled by the covering scale, provided the size of the cover is appropriately bounded. 1 It suffices to assume that F is inside an ℓ∞ ball of radius R . The assumption it is centered at 0 is for notational 2 convenience
9
3.2
Proof Overview of Theorem 2
We begin with the first regime. Suppose a set of size n is γ-shattered. Then, for any γ ′ < γ/2, every γ ′ -cover of its projection must contain at least 2n functions. It follows that H(F, γ ′ , n) = Ω(n), as observed in [ABDCBH97, BL98]. On the other hand, standard volume estimates yield the existence of a γ-cover of size at most (1/γ)n . Hence, for γ ∈ (0, γ ⋆ /2), H(F , γ, n) = Θ(n). The O(log2 n) upper bound in the intermediate regime follows from the same covering argument used in the proof of Theorem 1. To establish tightness for γ ∈ (γ ⋆ /2, γ ⋆ ), we appeal to a result of [AHHM22], which shows that the disambiguation bound is tight. Specifically, they construct a partial concept class F with finite VC dimension for which any disambiguation must have size at least n(1−o(1)) log n . We embed this class into the real-valued setting by mapping 1-labels to γ ⋆ , −1-labels to −γ ⋆ , and undefined points to 0. In this construction, any γ-cover with γ ∈ (γ ⋆ /2, γ ⋆ ) induces a disambiguation as follows: given a γ-cover H, define Φh (x) = sign(h(x)). If |f (x) − h(x)| < γ ⋆ for all x, then f and h agree in sign on all points where f (x) ̸= 0. Thus Φh disambiguates the original partial class, yielding the desired lower bound. Finally, we consider the regime γ ∈ (2γ ⋆ , 1), where we rely on sample compression schemes. We begin by briefly recalling the notion of sample compression and how it leads to covering bounds. Formally, we say that F admits a γ-sample compression scheme of size k if there exists a reconstruction function ρ : (X × R)k → RX such that for every finite set X ⊆ X and every function f ∈ F, there exists a sequence T = {(xi , f (xi ))}ki=1 ,
xi ∈ X,
for which the reconstructed function ρ(T ) satisfies |ρ(T )(x) − f (x)| ≤ γ
for all x ∈ X.
Such a compression scheme yields a cover of polynomial size when k = O(1) (i.e., independent of the size of X), since discretizing the function values at scale ε and enumerating all possible reconstructions from k labeled points yields at most (n/ε)k candidate functions. This gives a cover of size polynomial in n, and hence a logarithmic bound on the metric entropy. It therefore remains to construct such a compression scheme. We follow the approach of [MY16], who studied sample compression in the binary-labeled setting, and adapt their argument to the real-valued case. Fix an empirical risk minimization (ERM) rule that maps any realizable dataset T = {(xi , yi )} (that is, a dataset for which there exists f ∈ F with yi = f (xi ) for all i) to a hypothesis hT ∈ F that is consistent with the dataset. By uniform convergence, if we take T to be of size m = m(ε, 1/3), where m(ε, δ) is the uniform convergence sample complexity (and 1/3 can be replaced by any constant δ < 1), then for any finite domain X = {x1 , . . . , xn }, any distribution p over X, and any function f ∈ F, there exists a realizable dataset T ⊆ X (with labels given by f ) such that the corresponding hypothesis hT satisfies Ex∼p [|f (x) − hT (x)|] ≤ γ + ε. This follows from the uniform convergence guarantee applied to a random draw of T from p. 10
A minimax argument now implies that there exists a distribution over such datasets T such that, when T is drawn from this distribution, the function hT (x) is close to f (x) in expectation for every point x ∈ X. We then use uniform convergence for the dual class to sparsify this distribution. Specifically, we approximate it by a uniform distribution over a finite multiset of datasets T1 , . . . , Tm⋆ , where m⋆ = m⋆ (ε, 13 ) is the uniform convergence sample complexity of the dual class at scale γ. This sparsification incurs an additional error of γ + ε. Averaging the corresponding hypotheses hTi then yields a function that is (2γ + O(ε))-close to f on all of X, giving the desired compression scheme. Crucially, this argument relies on the fact that the dual class satisfies γ-uniform convergence. This is not automatic, and follows from our Theorem 1 (see Proposition 2). Without this property, the sparsification step would not be possible.
3.3
Proof Overview of Theorem 3
Theorem 3 follows as a direct corollary of Proposition 1. Indeed, the proposition provides a complete characterization of the behavior of dF in terms of the fat-shattering dimension: if fatγ (F) is finite for all γ > 0 then dF is estimable, while if fatγ (F) = ∞ for some γ ∈ (0, 1/2) then dF is weakly evaluable with optimal scale 3. Thus, we focus on the proof of Proposition 1. The first item and the first part of the second item (that dF is 3-weakly evaluable) follow from standard arguments presented in [AMMS26]. The main challenge is to show that the factor 3 is optimal. The proof builds on the argument of [BKM19], which applies to total variation distance an example of an IPM induced by a class with infinite fat-shattering dimension. While their proof is technically involved, most of the required adaptations are straightforward. We therefore focus on the main conceptual step: reducing a general IPM with infinite fat-shattering dimension to the total variation setting. The result of [BKM19] shows that on a domain of size n, any evaluation algorithm with approximation √ factor strictly smaller than 3 requires at least n samples. Letting n → ∞, this rules out c-evaluability for any c < 3 on infinite domains. Thus, it suffices to embed arbitrarily large total variation instances into dF . Let γ ⋆ = inf{γ : fatγ (F) < ∞}, and fix γ − < γ ⋆ < γ + arbitrarily close to γ ⋆ . Let d = fatγ + (F). Since fatγ − (F) = ∞, we can find arbitrarily large γ − -shattered sets. Let X = {x1 , . . . , xN } be such a set, and let P be the uniform distribution over X. 2 ) i.i.d. e We sample n independent batches X1 , . . . , Xn , where each batch Xi consists of m = O(d/ε samples from P . With high probability, the following properties hold: 1. The batches X1 , . . . , Xn are pairwise disjoint (by taking N large enough to avoid collisions). 2. For every pair i ̸= j, the distance between the corresponding empirical distributions satisfies dF (Xi , Xj ) ≤ γ + + ε. This follows from a uniform convergence argument at scale γ + Let Pi denote the uniform distributionPover Xi , and let ∆ Pbe the set of all convex combinations of {P1 , . . . , Pn }. For any mixtures Pα = i αi Pi and Pβ = i βi Pi , we show that dF (Pα , Pβ ) ≈ γ ⋆ · TV(α, β).
11
The lower bound uses the γ − -shattering property. Since the batches are disjoint subsets of the shattered set, for the subset of indices S = {i : αi > βi }, there exists a function f ∈ F that separates S X from its complement at scale γ − . This function witnesses a discrepancy of i i∈S γ − · TV(α, β). The upper bound uses the fact that, by uniform convergence, any two batch distributions Pi and Pj are close under dF : namely, dF (Pi , Pj ) ≤ γ + + ε. A triangle-inequality argument then shows that moving mass between the Pi ’s can increase dF by at most roughly γ + + ε times the total amount of mass moved, giving dF (Pα , Pβ ) ≤ (γ + + ε)TV(α, β). Since γ − and γ + can be chosen arbitrarily close to γ ⋆ , and since ε can be taken arbitrarily small, these two bounds match up to a factor arbitrarily close to 1. This reduction embeds a total variation problem of dimension n into dF , allowing us to invoke the lower bound argument of [BKM19]. A crucial feature of the construction is that γ − and γ + can be taken arbitrarily close to γ ⋆ . This ensures that, for mixtures in ∆, the comparison between dF and total variation has distortion arbitrarily close to 1: γ − · TV(α, β) ≲ dF (Pα , Pβ ) ≲ γ + · TV(α, β). The critical point is that the upper bound must not lose a factor 2. While the lower bound already captures the correct scale, the difficulty lies in obtaining a sufficiently tight upper bound. In particular, the standard packing-based arguments used to relate uniform convergence to fat-shattering dimension - such as those underlying classical scale-sensitive bounds - incur an inherent factor-2 loss. Applied in our setting, such arguments would only yield dF (Pα , Pβ ) ≲ 2γ + · TV(α, β), rather than the near-tight bound we require. This loss is fatal for our purposes: it prevents obtaining the optimal factor 3 and invalidates this proof strategy altogether. In contrast, our use of the refined uniform convergence result at optimal scale avoids this loss and yields an upper bound matching the lower bound up to a factor arbitrarily close to 1. This tight control is what allows the reduction to go through and ultimately enables the dichotomy.
4
Proofs of Scale-Sensitive Learnability Results
4.1
Covering Lemmas
r X Lemma 1. Let F ⊂ [ −r 2 , 2 ] be a bounded set of functions, let γ ∈ (0, r), and denote fatγ (F) = d > 0. Then for any n > 1 we have r+γ N (F, , n) ≤ n7d log n 4
Proof. By restricting to an arbitrary set of size n we may assume that |X | = n, and we wish to find a cover for the function class F . For each f ∈ F define the partial function hf by if f (x) ≥ γ2 , 1 hf (x) = −1 if f (x) ≤ − γ2 , undefined otherwise. 12
By the definition of the fat-shattering dimension, the VC dimension of the induced partial concept class {hf : f ∈ F } is at most d. Hence, by Theorem 13 of [AHHM22], there exists a set of functions H ⊂ {−1, 1}X of size |H| ≤ (n + 1)(d+1) log2 (n)+2 ≤ n7d log n , that disambiguates this partial concept class; that is, for every f ∈ F there exists some h ∈ H such that h(x) = hf (x) whenever hf (x) is defined. For each h ∈ H, define Φh : X → [−r, r] by ( r−γ h(x) = 1, 4 Φh (x) = γ−r h(x) = −1. 4 We claim that {Φh : h ∈ H} is the desired r+γ 4 -cover. Indeed for any f ∈ F , if h disambiguates hf , r then for any x ∈ X with h(x) = 1 we have f (x) ∈ ( −γ 2 , 2 ], and for any x ∈ X with h(x) = −1 we γ have f (x) ∈ [ −r 2 , 2 ). Thus we indeed get that for all x ∈ X we have |f (x) − Φh (x)| ≤
r+γ . 4
This gives the desired result. Lemma 2 (Covering Number Bound). Let F ⊂ [−R, R]X be a bounded function class, let γ > 0, and denote fatγ (F) = d > 0. Then for any ε > 0, and n > 1 we have 2R
N (F, γ2 + ε, n) ≤ n14d log ε log n , Proof. By restricting to an arbitrary set of size n we may assume that |X | = n, and we wish to find a cover for the function class F . We prove by induction on k that for every integer k > 0, 2R N F, γ2 + k+1 ≤ n7dk log n . 2 2R Choosing k such that 22R k+1 ≤ ε ≤ 2k then yields the desired bound. For the base case k = 0, observe that F can be covered by a single ball of radius R in the ℓ∞ metric. For the inductive step, assume that F can be covered by n7d(k−1) log n balls of radius γ2 + 2R . For each 2k such ball F with center f we may apply Lemma 1 to the translated class F − f = {g − f : g ∈ F },
and find a covering of F of size n7d log n with balls of radius bounds give a ( γ2 + 22R k+1 )-covering of size
) γ+(γ+ 4R 2k = γ2 + 22R k+1 . Combining the 4
n7(k−1)d log n n7d log n = n7kd log n . From which we deduce the desired result.
13
4.2
Proof for Theorem 1
The following is a standard refinement of an argument by [DGZ91] relating uniform convergence and covering number. Similar results can be found in [AB99, BL98, Pol84] Lemma 3 (Uniform Convergence Rate vs Covering Number). Let F ⊆ [−R, R]X be a bounded function class, and let γ > 0. Then for any distribution q over X and any δ, ε > 0, if γ ε 1 128R2 H F, + , n + log , n> ε2 2 8 δ then
" Pr
S∼q n
# 1X sup f (x) − E [f (x)] > γ + ε ≤ δ. x∼q f ∈F n
x∈S γ In particular, if H(F , 2 + ε, n) = o(n) for all ε > 0, then F satisfies γ-uniform convergence.
Proof. Let ε > 0, let q be some distribution over X and for every dataset S = {xi }ni=1 define the random variable ZS by n 1X ZS = sup | E [f (x)] − f (xi )|. n f ∈F x∼q i=1
We need to show that Pr[ZS > γ + ε] < δ. We will do that by showing ε E n [ZS ] ≤ γ + , S∼q 2 ε P r[ZS > EZS + ] ≤ δ. 2 The second claim follows from McDiarmid’s inequality [M+ 89], which tells us that if ZS is such that |ZS − ZS ′ | ≤ cj for any S = {xi }ni=1 , S ′ = {x′i }ni=1 satisfying xi = x′i for all i ̸= j, then we have −2η 2 Pr[ZS > EZS + η] ≤ exp Pn 2 . i=1 ci Note that in our case this holds with cj = 2R n for all j, hence we have −ε2 n ε P r[ZS > EZS + ] ≤ e 8R2 ≤ δ. 2
So we just need to bound the expectation. For that we use symmetrization " # 1X f (xi ) E sup E [f (x)] − S∼q n f ∈F x∼q n " n " # # X 1X 1 = E n sup ′ E n f (x′i ) − f (xi ) S∼q n n f ∈F S ∼q i=1 " # n 1X 1X ′ ≤ E sup f (xi ) − f (xi ) . S,S ′ ∼q n f ∈F n n
(1) (2) (3)
i=1
We generate the samples S = {xi }ni=1 and S ′ = {x′i }ni=1 via the following symmetrization procedure. First draw a sample T = {ti }ni=1 ∪ {t′i }ni=1 14
of size 2n. Then, for each 1 ≤ i ≤ n, independently set (xi , x′i ) = (ti , t′i ) with probability 12 , and (xi , x′i ) = (t′i , ti ) with probability 21 . This construction yields " # " # n n X X 1X 1 1 E sup f (x′i ) − f (xi ) = E sup σi f (ti ) − f (t′i ) T,σ f ∈F n S,S ′ ∼q n f ∈F n n i=1
i=1
where σ = (σ1 , . . . , σn ) ∈ {±1}n are independent Rademacher random variables, with σi = 1 if (xi , x′i ) = (ti , t′i ) and σi = −1 otherwise. By the triangle inequality and sub-additivity of the supremum we have " " # # n n X 1X 1 E sup σi f (ti ) − f (t′i ) ≤ 2 sup E sup σi f (xi ) . T,σ f ∈F n x∈X n σ f ∈F n i=1
i=1
The quantity above is known as the Rademacher complexity of F. To bound fix some x ∈ X n and let H be a cover of F|x of size N = N (F, γ2 + 8ε , n). Then we may use Massart Lemma (see lemma 26.8 in [SSBD14]) for bounding the Rademacher complexity of finite classes to get " # " # r n n 8R2 log 2|H| 1X ε 1X ε 2E sup σi f (xi ) ≤ γ + + 2E sup σi h(xi ) ≤ γ + + . σ f ∈F n σ h∈H n 4 4 n i=1
i=1
This yields the bound ε E n [ZS ] ≤ γ + + S∼q 4
r
8R2 · H(F , γ2 + 8ε , n) + 8R2 ε ≤γ+ . n 2
Giving the desired result. The following result follows from analyzing the proof of Theorem 21 in [BL98], replacing their specific covering bound with a generic one. The proof is exactly the same and is repeated here for completeness. Lemma 4 (Learning Via Covering). Let γ > 0, and let F be a bounded function class. Assume that for all ε > 0 we have a bound H(F , γ + ε, n) = o(n) on the empirical entropy of F . Then F is γ-learnable. Proof. By normalization and translation assume F ⊂ [0, 1]X . The learning algorithm is as follows: 2n Given a sample S = {(xi , yi )}2n i=1 , and a test point x set X = {xi }i=1 ∪ {x}, and let H be a (γ + ε)-cover of F|X of size at most N (F, γ + ε, 2n + 1). Split S, as S1 = {xi }ni=1 , S2 = {xi }2n i=n+1 , and let h ∈ H be such that n 1X LS1 (h) := |h(xi ) − yi |, n i=1
is minimized over all functions in H. Our learner will return the value of h on the test point AS (x) = h(x). To see this gives a valid learner let µ be a distribution on X × [−R, R], and let ε, δ > 0. Let f ⋆ ∈ F be a function for which Lµ (f ⋆ ) :=
E
[|f ⋆ (x) − y|] ≤ inf
E
f ∈F (x,y)∼q
(x,y)∼q
15
[|f (x) − y|] + ε.
Now by Hoeffding inequality we have 2
Pr [LS (f ⋆ ) ≤ Lµ (f ⋆ ) + ε] > 1 − 2e−4ε n .
S∼µ2n
On this event, since H is a cover of F|X there is some h′ ∈ H such that LS (h′ ) ≤ LS (f ⋆ ) + γ + ε ≤ Lµ (f ⋆ ) + γ + 2ε ≤ inf Lµ (f ) + γ + 3ε. f ∈F
By symmetrization # n 1X σi |h(xi ) − yi | − |h(xn+i ) − yn+i | > ε Pr [sup |LS1 (h) − LS2 (h)| > ε] ≤ sup Pr sup S1 ,S2 ∼µn h∈H S∈(X ×[0,1])2n σ h∈H n "
i=1
≤ 2|H|e
−ε2 n 2
≤ 2N (F, γ + ε, 2n + 1)e
−ε2 n 2
.
Now since LS is the average of LS1 and LS2 , and h is the minimizer of LS1 we deduce that on the above event LS2 (h) ≤ LS1 (h) + ε ≤ LS1 (h′ ) + ε ≤ LS (h′ ) + 2ε ≤ inf Lµ (f ) + γ + 5ε. f ∈F
Averaging over permutation of the last n points and the test point, which does not affect h, yields that the above gives the same bound for Lµ (h). Hence we get that −ε2 n Pr Lµ (h) ≥ inf Lµ (f ) + γ + 5ε ≤ 4N (F, γ + ε, 2n + 1)e 2 . f ∈F
From which the desired result follows. Theorem 1. Let F ⊂ [−R, R]X be a bounded function class and let γ > 0. Then, the following are equivalent: 1. F is γ2 -learnable; 2. F satisfies γ-uniform convergence; 3. for every γ ′ > γ, the γ ′ -fat-shattering dimension of F is finite. Proof. (1) =⇒ (3) Follow from Theorem 22 in [BL98] and (2) =⇒ (3) follow from Theorem 26 in the same work. The implication (3) =⇒ (1) follow from Lemma 2 and Lemma 4. Thus we only need to prove (3) =⇒ (2). Let γ > 0 be such that fatγ ′ (F) is finite for all γ ′ > γ, and we will show that F satisfies γ-uniform convergence. Let ε, δ > 0, and denote d = fatγ+ 16ε , which is finite by assumption. By Lemma 2 we have γ ε 32R H F, + , n ≤ 14d log log2 n. 2 8 ε Thus, by Lemma 3 if n is large enough such that n 1792 32R 1 > log + log ε ε δ log2 n then we have
" Pr
S∼q n
# 1X sup f (x) − Ex∼q [f (x)] > γ + ε ≤ δ. f ∈F n x∈S
16
From which the desired result follow. We note that the induced sample size bound will be of order !! d log 1ε + log 1δ d log 1ε + log 1δ 2 m(ε, δ) = O log . ε2 ε2
4.3
Proof for Theorem 2
The following Lemma concerns approximate sample compression schemes, which were defined in [HKS19] as a natural generalization of sample compression schemes for discrete classes. We say that F has a γ-sample compression scheme of size k, if there exists a reconstructor ρ : (X × R)k → RX such that for any finite set X and function f ∈ F there exists a sequence of length k T = {(xi , f (xi ))}ki=1 ,
xi ∈ X for all 1 ≤ i ≤ k,
satisfying |ρ(T )(x) − f (x)| ≤ γ
for all x ∈ X.
Lemma 5 (Sample compression). Let F ⊆ [−R, R]X be a bounded function class, and assume that fatγ (F) < ∞. Then for every ε > 0, F has a (2γ + ε)-compression scheme of constant size. Proof. The proof is a real-valued analogue of [MY16]. Fix ε > 0. We will choose m, m⋆ below. For every realizable sample T = {(xi , f (xi ))}m i=1 , where xi ∈ X and f ∈ F , choose some hT ∈ F such that for all i ∈ [m].
hT (xi ) = f (xi )
We will show that for every finite set X = {x1 , . . . , xn } ⊆ X and every f ∈ F, there exist subsets J1 , . . . , Jm⋆ ⊆ X of size m such that, writing Ti = {(x, f (x)) : x ∈ Ji }, we have, for every x ∈ X,
m⋆
1 X hTi (x) − f (x) ≤ 2γ + ε. m⋆ i=1
The compression scheme stores the samples T1 , . . . , Tm⋆ and reconstructs by m⋆
1 X ρ(T1 , . . . , Tm⋆ ) = ⋆ hTi . m i=1
Fix X and f , and define H = {hT : T = {(xi , f (xi ))}m i=1 , xi ∈ X} .
17
We first claim that, for every distribution q over X, there exists h ∈ H such that ε E [|h(x) − f (x)|] ≤ γ + . 2
x∼q
For any function h : X → R, define ϕh (x) = |h(x) − f (x)|, and let LH,f = {ϕh : h ∈ H}. For any functions g, h and any x ∈ X, |ϕg (x) − ϕh (x)| = |g(x) − f (x)| − |h(x) − f (x)| ≤ |g(x) − h(x)|. Hence, for every finite sample size n and every scale α > 0, N (LH,f , α, n) ≤ N (H, α, n) ≤ N (F, α, n). Since fatγ (F) < ∞, the covering bound Lemma 2 and the uniform convergence bound Lemma 3 imply that the classes LH,f satisfy γ-uniform convergence with a sample size depending only on γ, ε, R and fatγ (F), but not on X, f , or q. Choose m large enough so that, with probability at least 2/3 over x1 , . . . , xm ∼ q, we have simultaneously for all h ∈ H, m
1 X ε E [ϕh (x)] − ϕh (xi ) ≤ γ + . x∼q m 2 i=1
For the sampled set
T = {(xi , f (xi ))}m i=1 ,
the corresponding function hT ∈ H satisfies hT (xi ) = f (xi ) for all i. Therefore m
1 X ϕhT (xi ) = 0, m i=1
and so
ε E [|hT (x) − f (x)|] = E [ϕhT (x)] ≤ γ + . x∼q x∼q 2
This proves the claim. Now consider the zero-sum game in which Player 1 chooses h ∈ H, Player 2 chooses x ∈ X, and the payoff is |h(x) − f (x)|. The claim says that for every mixed strategy q of Player 2, there is h ∈ H whose expected payoff is at most γ + 2ε . By minimax, there exists a distribution p over H such that, for every distribution q over X, ε E [|h(x) − f (x)|] ≤ γ + . h∼p, x∼q 2 In particular, for every x ∈ X, ε E [h(x)] − f (x) ≤ E [|h(x) − f (x)|] ≤ γ + . h∼p h∼p 2 18
Finally, by Proposition 2, the dual class H⋆ satisfies γ-uniform convergence. Choose m⋆ large enough so that, with probability at least 2/3 over h1 , . . . , hm⋆ ∼ p, m⋆
1 X ε sup E [h(x)] − ⋆ hi (x) ≤ γ + . h∼p m 2 x∈X i=1
Therefore there exist h1 , . . . , hm⋆ ∈ H satisfying this bound. Writing each hi as hTi , we obtain, for every x ∈ X, m⋆ 1 X ε ε hTi (x) − f (x) ≤ γ + + γ + = 2γ + ε. ⋆ m 2 2 i=1
Since m and m⋆ depend only on γ, ε, R and the relevant fat-shattering bounds, and not on X, f , or n, the resulting compression scheme has constant size mm⋆ . We remark that our uniform convergence bound imply the compression size is of order ⋆ fatγ (F)fatγ (F ⋆ ) ⋆ 6 fatγ (F)fatγ (F ) mm = O log . ε4 ε
Theorem 2. Let F ⊂ [−R, R]X be a bounded function class, and let γ ⋆ = inf{γ > 0 : fatγ (F) < ∞}. Then2 , ⋆ Θ(n) γ ∈ (0, γ2 ), ⋆ H(F , γ, n) = O(log2 n) γ ∈ ( γ2 , 2γ ⋆ ], O(log n) γ ∈ (2γ ⋆ , R). ⋆ Moreover, the second regime is tight for γ ∈ γ2 , γ ⋆ : there exist F s.t. for all γ < γ ⋆ , H(F , γ, n) = Ω log2−o(1) n . The third regime is tight: there exist F such that H(F , γ, n) = Ω(log n) for γ ∈ (2γ ⋆ , R). Proof. The first part is well established [ABDCBH97, BL98]. If S is a γ ′ -shattered set then the ′ ⋆ γ-covering number of F|S is at least 2n for any γ < γ2 . For the second part , let γ > γ2 and pick ⋆ some γ ′ such that γ > γ ′ > γ2 . By definition fat2γ ′ (F) is finite hence by Lemma 2 we have 1 14fat2γ ′ (F ) log γ−γ ′ log n
N (F, γ, n) ≤ n
. ⋆
Taking log gives the desired bound. To show this bound can be tight in the γ ∈ ( γ2 , γ ⋆ ) regime we use Theorem 11 of [AHHM22], which gives, for any n > 1, the existence of a partial concept class Fn ⊂ {−1, 1, ⋆}n , with VC dimension 1, such that any disambiguation of Fn is of size at least 1−o(1) n(log n) . 2
Throughout, the asymptotic notation treats n as the parameter tending to infinity; the implicit constants may depend on γ and on the fat-shattering dimension at scale γ.
19
For each f ∈ Fn define fb : X → [−γ ⋆ , γ ⋆ ] by ⋆ γ fb(x) = −γ ⋆ 0
f (x) = 1, f (x) = −1, f (x) = ⋆,
And set Fbn = {fb : f ∈ Fn }. Then fatγ (Fbn ) is finite (And equal to 1) if γ > γ ⋆ , other properties of this class will imply this is an if and only if but this is not necessary for our bound. Now let H be some γ-cover of Fbn , for γ < γ ⋆ . Define {Φh : h ∈ H} a disambiguation of Fn by ( 1 h(x) ≥ 0, Φh (x) = −1 h(x) < 0. For any f ∈ Fn there is h ∈ H such that fb − h
∞
≤ γ, hence we have h(x) ≥ γ ⋆ − γ > 0, whenever
f (x) = 1 and h(x) ≤ γ − γ ⋆ < 0 whenever f (x) = −1. Hence ϕh disambiguates f and {ϕh : h ∈ H} 1−o(1) is a disambiguation of Fn , implying that its size is at least n(log n) . This gives the result for a fixed n, to get F for which the bound will hold for all n simply take a disjoint union of all the Fn . each defined over its own domain and extend to be 0 on all other domains. ⋆ For the log n bound let γ > 2γ ⋆ and define ε = γ−2γ so γ = 2γ ⋆ + 8ε. First discretize the space at 8 scale ε, replacing each function f ∈ F with fε defined by f (x) ε, fε (x) = ε and Set Fε = {fε : f ∈ F}. Note that |f (x) − fε (x)| ≤ ε for all x ∈ X , hence we have fat γ −ε (Fε ) ≤ fat γ −3ε (F) = fatγ ⋆ +ε (F) < ∞. 2
2
Thus, by Theorem 1 we have that Fε satisfies ( γ2 − ε)-uniform convergence. By Proposition 2 we also have that its dual class Fε⋆ satisfies ( γ2 − ε)-uniform convergence. Hence by Lemma 5 Fε admits a (γ − ε)-sample compression of constant size k, i.e. there k is a reconstructor ρ, such that for any n dataset S = {(xi , f (xi ))}i=1 there is T = { xij , f (xij ) }i=1 such that the reconstructed function ρ(T ) is at most (γ − ε)-away from f on any point in S. We use this compression scheme to construct a covering as follow : given a dataset X of size n define the covering H by H = {ρ(T ) : T = {(xi , fε (xi )}ki=1 , fε ∈ Fε , xi ∈ X}. So H is all possible outputs of reconstructor on realizable subset of X of size k. Note that each function in H is defined by k points from X and the values of fε on them. By discretization fε has no more than 2R ε possible outputs at every point, yielding a bound of |H| ≤ (
2Rn k ) . ε
So it just remains to show that H is an γ-cover for F. By definition of compression scheme H forms a (γ − ε)-cover of Fε , and since |f (x) − fε (x)| ≤ ε for all x we indeed have that it is also a γ cover of F. Taking log, and noting that k, ε are independent on n gives the desired result. To see this log n bound can be tight let F ⊂ {−1, 1}N be the class of all singleton functions, so F = {fn : n ∈ N}, where fn (k) is 1 if n = k, and −1 otherwise. It is easy to see that fatγ (F) = 1, and N (F, γ, n) = n for all γ ∈ (0, 1). 20
Proposition 4. Let γ ⋆ > 0. There exists bounded function classes F1 , F2 such that inf{γ : fatγ (F1 ) < ∞} = γ ⋆ = inf{γ : fatγ (F2 ) < ∞}. But for all n > 0, we have γ⋆ , n) = 0, 2 γ⋆ n H(F2 , , n) = Ω( ). 2 log n H(F1 ,
⋆
⋆
Proof. Let F1 = [− γ2 , γ2 ]N . Clearly we have fatγ (F1 ) = 0 for γ > γ ⋆ and fatγ (F1 ) = ∞ for γ ≤ γ ⋆ ⋆ so γ ⋆ is indeed the critical threshold for finite fat shattering. It is also clear that N (F1 , γ2 , n) = 1 ⋆ for all n since the zero function is distance γ2 from any function in F1 , Now let F2 ⊂ [0, 1 + γ ⋆ ]N be the class of all function f from N to [0, 1 + γ ⋆ ] satisfying f (n) ≤ γ ⋆ +
1 . log n
It is simple to see that fatγ (F2 ) > n if and only if γ ≤ γ ⋆ + log1 n , thus γ ⋆ is indeed the critical threshold for finite fat shattering. Note that the restriction of F2 to 1, 2 . . . n, contains [0, γ ⋆ + log1 n ]n ⋆
as a subset. It has a volume of (γ ⋆ + log1 n )n , hence if we want to cover it with balls of radius γ2 , each of volume (γ ⋆ )n the number of functions we must use is at least !n n γ ⋆ + log1 n n 1 γ ⋆ log n . = 1 + ∼ e γ⋆ γ ⋆ log n ⋆
This shows that H(F2 , γ2 , n) = Ω( logn n ). Note that by replacing log1 n with a slower decaying sequence we may get arbitrarily close to a log n lower bound.
4.4
Composition and Closure
Lemma 6. Let F be a bounded function class. Let γ ⋆ = inf{γ : fatγ (F) < ∞}. Then for any γ − < γ ⋆ , and any n ∈ N, there exists r ∈ R such that there are at least n points that can be γ − -shattered at the same threshold r by F. Proof. By rescaling and translating F, we assume F ⊂ [0, 1]X . Fix n ∈ N and let M ∈ N be chosen later. Fix a scale γ ′ such that γ − < γ ′ < γ ⋆ . By definition, there exists a subset {x1 , ..., xM } ⊆ X that is γ ′ −shattered by F. with thresholds r1 , ..., rM . Observe that since F ⊆ [0, 1]X , any threshold ′ − ri ∈ [γ ′ /2, 1−γ ′ r/2]. Now, partition the interval [γ ′ /2, 1−γ ′ /2] into subintervals of length α ≤ γ −γ 2 . ′ Note that there can be at most S = ⌈ 1−γ α ⌉ subintervals and that we can identify any subinterval with an index set I ⊆ [M ]. It follows by the pigeonhole principle that if we take M ≥ Sn, there must exist an index set I ⋆ ⊆ [M ] with |I ⋆ | ≥ n for which there exists r ∈ R such that ri ∈ [r, r + α] ∀i ∈ I ⋆ . Now, we claim that {xi : i ∈ I ⋆ } is γ − -shattered by F with common threshold r. To see this, fix any labeling y ∈ {+1, −1}M (taking the subset of labelings corresponding to I ⋆ gives an arbitrary labeling on I ⋆ ). By definition, there exists f ∈ F such that for all i ∈ I ⋆ : 21
If yi = +1, then f (xi ) ≥ ri + If yi = −1, then f (xi ) ≤ ri −
γ′ γ− γ′ ≥r+ ≥r+ 2 2 2
γ′ γ′ γ− ≤r+α− ≤r− , 2 2 2 ′
−
where the last inequality uses the fact that α ≤ γ −γ 2 . The result follows. Proposition 2. Let γ > 0, and let F be a bounded function class that satisfies γ-uniform convergence. Then the dual class F ⋆ also satisfies γ-uniform convergence. Proof. By Theorem 1 it is enough to show that for any γ ′ > γ we have that fatγ ′ (F ⋆ ) < ∞. Indeed, let γ ′ > γ and choose some γ ′′ such that γ < γ ′′ < γ ′ . Assume toward contradiction that fatγ ′ (F ⋆ ) = ∞, and denote n = 2fatγ ′′ (F )+2 , which is finite by Theorem 1. By Lemma 6 there is some r ∈ R such that there are n points which are γ ′′ -shattered by F ⋆ at this same threshold r. Now that the points are shattered at the same threshold, standard Assouad type bounds, such as Theorem 3.7 in [KS23], will imply that F γ ′′ -shatters at least log(n) − 1 = fatγ ′′ (F) + 1 points. Giving the desired contradiction. Proposition 3. Let F1 , . . . , Fk ⊂ [0, 1]X be bounded function classes, each satisfying γ-uniform convergence, and let G : [0, 1]k → [0, 1] be a 1-Lipschitz function with respect to the ℓ∞ metric. Then the aggregated class G(F1 , . . . , Fk ) also satisfies γ-uniform convergence. Proof. Let ε > 0. By Theorem 1 we know that Fi has finite (γ + ε)-fat-shattering dimension for each 1 ≤ i ≤ k. Denote di = fatγ+ε (Fi ), then by Lemma 2 we have N (Fi ,
1 γ + ε) ≤ n14di log ε log n 2
For each 1 ≤ i ≤ k let Hi be such ( γ2 + ε)-cover for Fi and define G(H) = {G(h1 , h2 . . . hk ) : ∀i, hi ∈ Hi }. We claim that G(H) is a ( γ2 + ε)-cover for G(F). Indeed, for any f = (f1 , f2 , . . . fk ) ∈ F there is h = (h1 , h2 , . . . hk ), such that hi ∈ Hi , and ∥fi − hi ∥∞ ≤ γ2 + ε for all i. Then since G is 1-Lipschitz with respect to the ℓ∞ norm we have that ∥G(f ) − G(h)∥∞ ≤ ∥f − h∥∞ = sup sup |fi (x) − hi (x)| ≤ 1≤i≤k x∈X
γ + ε. 2
Thus we get that k
k
Y γ γ 1X N (G(F), + ε, n) ≤ N (Fi , + ε, n) ≤ exp 14 log2 n log di 2 2 ε i=1
i=1
The above with Lemma 3 implies the desired result.
22
! .
5
Proofs of Evaluability Results
5.1
Lower bound construction of [BKM19]
Lemma 7 (Lemma 22 of [BKM19]). Let D1 and D2 be two families of probability distributions, Di⊕m denotes the distribution obtained by sampling p ∼ Di (assuming some given fixed distribution over Di ) and then drawing m independent samples from p. Consider an algorithm (which can be randomized) that determines, given m i.i.d. examples from some p ∈ D1 ∪ D2 , whether p ∈ D1 or p ∈ D2 . Then such an algorithm will have a probability of making a mistake lower bounded by 1 1 − TV(D1⊕m , D2⊕m ) . 2 Proof. We first assume that the algorithm is deterministic. Any deterministic algorithm deciding whether p comes from D1 or D2 is associated with a set A ⊆ X m (the set such that if the sample falls in it, it decides i = 1, and i = 2 otherwise). The worst-case probability of the algorithm to err is given by max max pm (A), max pm (A) p∈D2
p∈D1
which can be lower bounded by the expectation under first choosing between i = 1 and i = 2 with probability 1/2 and then picking p ∼ Di : 1 1 Ep∼D1 pm (A) + Ep∼D2 pm (A) = 1 + D1⊕m (A) − D2⊕m (A) 2 2 1 ≥ 1 − TV(D1⊕m , D2⊕m ) . 2 If the algorithm is randomized then it may pick A randomly, so there is an additional expectation with respect to the distribution over sets A which also leads to the same lower bound. Lemma 8 (Lemma 23 of [BKM19]). Given two probability distributions P, Q on a domain X and an event E ⊆ X , denoting by P|E and Q|E the corresponding conditional distributions (i.e. P|E (A) := P (A | E)), we have TV(P, Q) ≤ TV(P|E , Q|E ) + 2P (E) + 2Q(E). Proof. TV(P, Q) = sup |P (A) − Q(A)| A
≤ sup |P (A ∩ E) − Q(A ∩ E)| + sup |P (A ∩ E) − Q(A ∩ E)| A A ≤ sup P (E) P (A | E) − Q(A | E) + Q(A | E) P (E) − Q(E) A
+ P (E) + Q(E) ≤ P (E) sup |P (A | E) − Q(A | E)| + |P (E) − Q(E)| A
+ P (E) + Q(E) ≤ TV(P|E , Q|E ) + |P (E) − Q(E)| + P (E) + Q(E) = TV(P|E , Q|E ) + |P (E) − Q(E)| + P (E) + Q(E) ≤ TV(P|E , Q|E ) + 2P (E) + 2Q(E).
23
Lower bound construction. We now present the construction of [BKM19]. Fix N ∈ N, β ∈ (0, 1) 1+β such that 1+β β ∈ N and let k = β . Given a collection of 2kN non-overlapping distributions over X , which we denote by µ = {µi,j |i ∈ [2N ], j ∈ [k]}, we construct mixtures over µ. We refer to distributions in µ as elements to avoid ambiguity. We define hypothesis class H = {q1 , q2 }: 1−β 1+β • q1 assigns probability 2kN to each µi,j and 2kN to each µi+N,j for all i ∈ [N ] and j ∈ [k]. 1−β 1+β to each µi,j and 2kN to each µi+N,j for all i ∈ [N ] and j ∈ [k]. • q2 assigns probability 2kN
For each i ∈ [N ], we pick one entry by an index function l : [2N ] 7→ [k] and then define distributions that concentrate all mass on that picked entries: 1−β 1 • p1,l : Starting from q1 , for all i ∈ [N ], we increase the probability of µi,l(i) from 2kN to kN and set the probability of µi+N,l(i+N ) to 0. All other elements retain their probabilities from q1 . 1−β • p2,l : Starting from q2 , for all i ∈ [N ], we increase the probability of µi+N,l(i+N ) from 2kN to 1 and set the probability of µ to 0. All other elements retain their probabilities from q 2. i,l(i) kN
We define two distributions D1 and D2 : D1 uniformly chooses from {p1,l |l ∈ [k][2N ] } and D2 uniformly chooses from {p2,l |l ∈ [k][2N ] }. The following claim comes directly from the information-theoretic part of Theorem 19 in [BKM19]. We reproduce the argument here for clarity. Lemma 9. Let F be a bounded function class. Fix N ∈ N, β ∈ N such that 1+β β ∈ N, and let k = 1+β evaluation algorithm A, there exists a β . Then, construct q1 , q2 , D1 and D2 as above. For any √ ⋆ q ∈ D1 ∪ D2 such that, given a sample Seval of size at most 2kN β from q ⋆ , with probability at least 1/3, qb = A({q1 , q2 }, Seval ) will be the wrong hypothesis, i.e., dF (b q , q ⋆ ) = max{dF (q1 , q ⋆ ), dF (q2 , q ⋆ )}. Proof. We can view A as a distinguisher between D1 and D2 . In particular, if the underlying distribution belongs to D1 , then A errs exactly when, given Seval , A({q1 , q2 }, Seval ) = q2 ; if the underlying distribution belongs to D2 , then A errs exactly when A({q1 , q2 }, Seval ) = q1 . Therefore, it suffices to lower bound the error probability of distinguishing D1 from D2 . By Lemma 7, Pr[A errs] ≥
1 1 − T V (D1⊕m , D2⊕m ) , 2
where Di⊕m denotes the distribution obtained by first drawing p ∼ Di and then drawing m independent samples from p. Hence it remains to show that 1 T V (D1⊕m , D2⊕m ) ≤ . 3 For each i ∈ [2N ], let Bi =
k [
supp(µi,j )
j=1
be the i-th big block. By construction, every distribution p ∈ D1 ∪ D2 assigns mass exactly p(Bi ) =
24
1 2N
1 kN 1+β 2kN
µ′1,1 µ′2,1 µ′3,1 µ′4,1 µ′5,1 µ′1,2 µ′2,2 µ′3,2 µ′4,2 µ′5,2 µ′1,3 µ′2,3 µ′3,3 µ′4,3 µ′5,3
0
µ1,1 µ2,1 µ3,1 µ4,1 µ5,1 µ1,2 µ2,2 µ3,2 µ4,2 µ5,2 µ1,3 µ2,3 µ3,3 µ4,3 µ5,3
1−β 2kN
q1 1 kN 1+β 2kN
µ′1,1 µ′2,1 µ′3,1 µ′4,1 µ′5,1 µ′1,2 µ′2,2 µ′3,2 µ′4,2 µ′5,2 µ′1,3 µ′2,3 µ′3,3 µ′4,3 µ′5,3
0
µ1,1 µ2,1 µ3,1 µ4,1 µ5,1 µ1,2 µ2,2 µ3,2 µ4,2 µ5,2 µ1,3 µ2,3 µ3,3 µ4,3 µ5,3
1−β 2kN
q2 1 kN 1+β 2kN
1 kN 1+β 2kN
µ′1,1 µ′2,1 µ′3,1 µ′4,1 µ′5,1 µ′1,2 µ′2,2 µ′3,2 µ′4,2 µ′5,2 µ′1,3 µ′2,3 µ′3,3 µ′4,3 µ′5,3
0
µ1,1 µ2,1 µ3,1 µ4,1 µ5,1 µ1,2 µ2,2 µ3,2 µ4,2 µ5,2 µ1,3 µ2,3 µ3,3 µ4,3 µ5,3
1−β 2kN
A p1,l from D1
µ′1,1 µ′2,1 µ′3,1 µ′4,1 µ′5,1 µ′1,2 µ′2,2 µ′3,2 µ′4,2 µ′5,2 µ′1,3 µ′2,3 µ′3,3 µ′4,3 µ′5,3
0
µ1,1 µ2,1 µ3,1 µ4,1 µ5,1 µ1,2 µ2,2 µ3,2 µ4,2 µ5,2 µ1,3 µ2,3 µ3,3 µ4,3 µ5,3
1−β 2kN
A p2,l from D2 Figure 1: Illustration of the distribution construction for k = 5 and N = 3. to each big block Bi . Let E be the event that the m samples fall in m distinct big blocks. Since the big-block marginal is uniform over [2N ] under every p ∈ D1 ∪ D2 , we have, under both D1⊕m and D2⊕m , m 1 m2 c Pr(E ) ≤ ≤ . 2 2N 4N We next show that
(D1⊕m )|E = (D2⊕m )|E.
Conditioned on E, each occupied big block contains exactly one sample. The occupied big blocks have the same law under D1⊕m and D2⊕m , because every distribution in D1 ∪ D2 gives mass 1/(2N ) to each big block. It remains to check the conditional distribution inside an occupied big block. Fix a block Bi , and
25
write
k
1X µi = µi,j . k j=1
We claim that, after averaging over the random selector ℓ(i), the conditional distribution of the unique sample inside Bi is µi , regardless of whether the underlying family is D1 or D2 . Indeed, consider a left block i ≤ N . For p1,ℓ , conditional on landing in Bi , the selected component µi,ℓ(i) has conditional weight 2/k, while each unselected component has conditional weight (1 − β)/k. Since ℓ(i) is uniform on [k], the averaged conditional weight of any fixed component µi,j is 1 2 k−1 1−β 1 2 + (k − 1)(1 − β) = , · + · = k k k k k2 k where we used k = (1 + β)/β. Thus the averaged conditional distribution is µi . For p2,ℓ on the same left block, the selected component has conditional weight 0, while each unselected component has conditional weight (1 + β)/k. Hence the averaged conditional weight of any fixed component is k−1 1+β (k − 1)(1 + β) 1 1 ·0+ · = = . k k k k2 k Thus the averaged conditional distribution is again µi . The calculation for right blocks i > N is identical, with the roles of D1 and D2 reversed. Because E ensures that no big block contributes more than one sample, there is no dependence coming from reusing the same hidden selector ℓ(i) twice within a block. Across different big blocks, the selectors ℓ(i) are independent. Therefore the full conditional joint distributions agree: (D1⊕m )|E = (D2⊕m )|E. Applying Lemma 8 with this event E, in the form T V (P, Q) ≤ T V (P |E, Q|E) + 2P (E c ) + 2Q(E c ), gives T V (D1⊕m , D2⊕m ) ≤ 0 + 2D1⊕m (E c ) + 2D2⊕m (E c ) ≤ 4 · Choosing N ≥ 3m2 , we obtain
m2 m2 = . 4N N
1 T V (D1⊕m , D2⊕m ) ≤ . 3
Therefore Lemma 7 implies 1 Pr[A errs] ≥ 2
1 1 1− = . 3 3
Equivalently, there exists some q ⋆ ∈ {p1,ℓ : ℓ ∈ [k][2N ] } ∪ {p2,ℓ : ℓ ∈ [k][2N ] } such that, with probability at least 1/3 over Seval ∼ (q ⋆ )m , the evaluation algorithm selects the hypothesis associated with the wrong family.
26
5.2
Proof for Theorem 3
Lemma 10. Let F ⊂ [0, 1]X be a bounded function class, and denote γ ⋆ = inf{γ : fatγ (F) < ∞}. Assume that γ ⋆ > 0. Then, for any γ − , γ + , such that γ + > γ ⋆ > γ − , and any n ∈ N, there exists r ∈ (0, 1), a set X and n subsets X1 , . . . , Xn ⊂ X such that: 1. The Xi ’s are pairwise disjoint. S 2. The union of the sets ni=1 Xi is γ − -shattered at the same threshold r by F. 3. Let Pi be the uniform distribution over Xi . Then for every i, j and every ϕ ∈ F |E [ϕ] − E [ϕ] | ≤ γ + . Pi
Pj
Proof of Lemma 10. Choose some γ such that γ + > γ > γ ⋆ . It follows that fatγ (F) < ∞. Let η = 2(γ + − γ), and let m, K > 0 to be chosen later. By Lemma 6, there is a set X of size K that is γ − -shattered by F at the same threshold. We generate the sets Xi by sampling m points from q, the uniform distribution over X. Note that by definition condition (2.) will hold. For condition (3.) we use the same symmetrization argument as in Lemma 3 (see also Lemma 16 in [BL98]) to deduce that the probability it will fail for any fixed pair (i, j) is bounded by 2 X X 1 1 −η m η f (x) − f (x) > γ + ≤ 2N (F , γ/2 + η/8, 2m) exp Pr m sup . Xi ,Xj ∼q m 2 32 f ∈F m x∈Xi
x∈Xj
So by the union bound, item (3.) will fail with probability at most 2 n −η m 2N (F, γ/2 + η/8, 2m) exp , 2 32 Applying Lemma 2 we see that the above probability goes to 0 as m goes to infinity, hence we may pick some m for which it is at most 14 . Now for the first item, note that the probability of two sampled points colliding is at most 2nm 1 . 2 |X| Hence if we take K the size of X to be larger than 4 2nm 2 , the above will happen with probability at most 14 . Thus by union bound all the conditions will hold with positive probability, implying the existence of such sets. Theorem 3. Every bounded IPM is either: 1. estimable, and hence strongly evaluable; or 2. weakly evaluable with optimal scale c = 3. Proof. The proof follows immediately from Proposition 1, with fatγ (F) underpinning the dichotomy.
27
Proposition 1. Let F be a class of bounded real-valued functions. 1. If fatγ (F) < ∞ for all γ > 0, then dF is estimable (and hence strongly evaluable). 2. If there exists γ ∈ (0, 1/2) such that fatγ (F) = ∞, then dF is weakly evaluable with optimal scale c = 3. Proof. When fatγ (F) < ∞ for all γ > 0, from Proposition 3.4 of [AMMS26], dF is estimable (and hence strongly evaluable) with sample complexity 1 1 2 4d m(ε, δ) = O , d log 2 + log ε2 ε δ where d = fatε/24 (F). This proves the first item. Now, consider the case where there exists γ ∈ (0, 1/2) such that fatγ (F) = ∞. We know again from Proposition 3.4 of [AMMS26] that dF is 3-weakly evaluable. It remains to show that for any c′ < 3, dF is not c′ -weakly evaluable. For any β ∈ (0, 1) and a collection of elements µ, following the construction and guarantee by Lemma 9, we can obtain a hypothesis class H = {q1 , q2 } and two distribution families D1 = {p1,l |l : [2N ] 7→ [k]} and D2 = {p2,l |l : [2N ] 7→ [k]} such that no evaluation algorithm can evaluate H. Fix any τ > 0. The only thing that remains is to find a collection of elements µ such that dF (q2 , p1,l ) ≥ (3 − τ )dF (q1 , p1,l ) for an index l. ⋆ + = γ ⋆ + α and Let k = 1+β β . Let γ = inf{γ > 0 : fatγ (F) < ∞}. For a small α > 0, let γ −
γ γ − = γ ⋆ − α. Now, choose β so that 3−β 1+β · γ + ≥ 3 − τ . By LemmaS10, we can find a set X and a sequence of 2kN disjoint subsets {Xi,j |i ∈ [2N ], j ∈ [k]} such that Xi,j is γ − -shattered by F at the same threshold and | E [ϕ] − E [ϕ] | ≤ γ + for every µi,j
µi′ ,j ′
pair (i, j), (i′ , j ′ ) ∈ [2N ] × [k] and every ϕ ∈ F, where µi,j is the uniform distribution over Xi,j . For any index function l, we have N
dF (q1 , p1,l ) =
X 1+β sup ( E [ϕ]) − E [ϕ])) . µi,l(i) µi+N,l(i+N ) 2kN ϕ∈F i=1
Note the function within the supremum is a weighted sum of
E [ϕ]’s and
µi,l(i)
E
µi+N,l(i+N )
[ϕ]’s. We
define the normalized weighted sum a(µ, l) as N
2k 1 X a(µ, l) := · dF (q1 , p1,l ) = sup ( E [ϕ]) − E [ϕ])) . µi,l(i) µi+N,l(i+N ) 1+β ϕ∈F N i=1
We also have N
X 1 X ((1 − β)( E [ϕ]) − E [ϕ])) + 2β ( E [ϕ] − E [ϕ])) . µi,l(i) µi+N,l(i+N ) µi+N,j µi,j ϕ∈F 2kN
dF (q2 , p1,l ) = sup
i=1
j̸=l(i)
Given µ and l, we define the normalized weighted sum b(µ, l) as 2k · dF (q2 , p1,l ) 3−β N X X 1 = sup ((1 − β)( E [ϕ]) − E [ϕ])) + 2β ( E [ϕ] − E [ϕ])) . µi,l(i) µi+N,l(i+N ) µi+N,j µi,j ϕ∈F (3 − β)N
b(µ, l) :=
i=1
j̸=l(i)
28
We can show thatSa(µ, l) ≤ γ + and b(µ, l) ≥ γ − . By Lemma 10, we have that a(µ, l) ≤ γ + for all l ∈ [k][2N ] . Since Xi,j can be γ − -shattered by F at the same threshold, we also have b(µ, l) ≥ γ − . Combining the two bounds, we obtain dF (q2 , p1,l ) 3 − β γ− ≥ · ≥ 3 − τ. dF (q1 , p1,l ) 1 + β γ+ Thus dF (q2 , p1,l ) ≥ (3 − τ ) dF (q1 , p1,l ). So conditional on the event that the evaluation algorithm returns the wrong hypothesis, we have dF (q ⋆ , qb) ≥ (3 − τ ) min {dF (q ⋆ , q1 ), dF (q ⋆ , q2 )} . Now, for any c′ < 3, if we take τ such that 3 − τ > c′ , by Lemma 9, we have that dF is not c′ -weakly evaluable, proving that the scale c = 3 is optimal.
6
Acknowledgements
Yishay Mansour received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation, the Yandex Initiative for Machine Learning at Tel Aviv University and a grant from the Tel Aviv University Center for AI and Data Science (TAD). Shay Moran is a Robert J. Shillman Fellow; he acknowledges support by Israel PBC-VATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the 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. Han Shao acknowledges support from an Adobe Research gift.
29
References [AB99] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 1999. [ABDCBH97] Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. J. ACM, 44(4):615–631, July 1997. [AHHM22] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022. [AHKS24] Idan Attias, Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. Agnostic sample compression schemes for regression. In Forty-first International Conference on Machine Learning, 2024. [AK24] Idan Attias and Aryeh Kontorovich. Fat-shattering dimension of k-fold aggregations. Journal of Machine Learning Research, 25(144):1–29, 2024. [AMMS26] Shashaank Aiyer, Yishay Mansour, Shay Moran, and Han Shao. A theoretical framework for statistical evaluability of generative models. arXiv preprint arXiv:2604.05324, 2026. [Ass83] Patrick Assouad. Densité et dimension. In Annales de l’institut Fourier, volume 33, pages 233–282, 1983. [BEHW89] Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapnik-chervonenkis dimension. J. ACM, 36(4):929–965, October 1989. [BKM19] Olivier Bousquet, Daniel Kane, and Shay Moran. The optimal approximation factor in density estimation. In Conference on Learning Theory, pages 318–341. PMLR, 2019. [BKP97] Peter L. Bartlett, Sanjeev R. Kulkarni, and Steven R. Posner. Covering numbers for real-valued function classes. IEEE Transactions on Information Theory, 43(5):1721– 1724, 1997. [BL98] Peter L. Bartlett and Philip M. Long. Prediction, learning, uniform convergence, and scale-sensitive dimensions. Journal of Computer and System Sciences, 56(2):174–190, 1998. [CBH98] Nicolò Cesa-Bianchi and David Haussler. A graph-theoretic generalization of the sauershelah lemma. Discrete Applied Mathematics, 86(1):27–35, 1998. Vapnik-Chervonenkis dimension. [CEP25] Roberto Colomboni, Emmanuel Esposito, and Andrea Paudice. An improved uniform convergence bound with fat-shattering dimension. Information Processing Letters, 188:106539, 2025. [DGZ91] Richard M Dudley, Evarist Giné, and Joel Zinn. Uniform and universal glivenkocantelli classes. Journal of Theoretical Probability, 4(3):485–510, 1991. 30
[Dud78] Richard M Dudley. Central limit theorems for empirical measures. The Annals of Probability, pages 899–929, 1978. [Dud84] Richard M. Dudley. A course on empirical processes. 1984. [FWL+ 25] Lizhe Fang, Yifei Wang, Zhaoyang Liu, Chenheng Zhang, Stefanie Jegelka, Jinyang Gao, Bolin Ding, and Yisen Wang. What is wrong with perplexity for long-context language modeling?, 2025. [HHT+ 24] Yutong Hu, Quzhe Huang, Mingxu Tao, Chen Zhang, and Yansong Feng. Can perplexity reflect large language model’s ability in long text understanding?, 2024. [HKS19] Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi. Sample compression for real-valued learners. In Algorithmic Learning Theory, pages 466–488. PMLR, 2019. [KS94] Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464–497, 1994. [KS23] Pieter Kleer and Hans Simon. Primal and dual combinatorial dimensions. Discrete Applied Mathematics, 327:185–196, 2023. [Lon01] Philip M. Long. On agnostic learning with {0, *, 1}-valued and real-valued hypotheses. In David P. Helmbold and Robert C. Williamson, editors, Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings, volume 2111 of Lecture Notes in Computer Science, pages 289–302. Springer, 2001. [Lor86] G. G. Lorentz. Approximation of functions. Chelsea Pub. Co., New York, N.Y, 2nd ed. edition, 1986. [M+ 89] Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1):148–188, 1989. [Men02] Shahar Mendelson. Rademacher averages and phase transitions in Glivenko–Cantelli classes. IEEE Transactions on Information Theory, 48(1):251–263, 2002. [MMM20] Pedro Henrique Martins, Zita Marinho, and André F. T. Martins. Sparse text generation, 2020. [MV02] Shahar Mendelson and Roman Vershynin. Entropy, combinatorial dimensions and random averages. In International Conference on Computational Learning Theory, pages 14–28. Springer, 2002. [MV03] Shahar Mendelson and Roman Vershynin. Entropy and the combinatorial dimension. Inventiones Mathematicae, 152(1):37–55, 2003. [MY16] Shay Moran and Amir Yehudayoff. Sample compression schemes for vc classes. Journal of the ACM (JACM), 63(3):1–10, 2016. [Mü97] Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429–443, 1997. 31
[Pol84] David Pollard. Convergence of stochastic processes. 1984. [PSZ+ 21] Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaid Harchaoui. Mauve: Measuring the gap between neural text and human text using divergence frontiers, 2021. [RV06] Mark Rudelson and Roman Vershynin. Combinatorics of random processes and sections of convex bodies. Annals of Mathematics, pages 603–648, 2006. [Sau72] Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972. [SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014. [Tik60] V. M. Tikhomirov. Diameters of sets in function spaces and the theory of best approximations. Russian Mathematical Surveys, 15(3):75–111, 1960. [Vap71] Vladimir Naumovich Vapnik. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. 1971. [Yat85] Yannis G. Yatracos. Rates of convergence of minimum distance estimators and kolmogorov’s entropy. The Annals of Statistics, 13(2):768–774, 1985.
32