High-arity Sample Compression Leonardo N. Coregliano
William Opich
arXiv:2605.12465v1 [cs.LG] 12 May 2026
May 13, 2026 Abstract Recently, a series of works have started studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. In this work, we consider a high-arity variant of sample compression schemes and we prove that the existence of a high-arity sample compression scheme of non-trivial quality implies high-arity PAC learnability.
1
Introduction
Given a family H of subsets of some fixed X, can we approximately recover a hidden set F ∈ H from its behavior on a finite random i.i.d. sample from a distribution on X? Classes that admit such a procedure are called probably approximately correctly (PAC) learnable. An a priori unrelated question about the family H is: given a sample x1 , . . . , xm ∈ X along with the behavior of some F ∈ H on x1 , . . . , xm , is it possible to compress this information by selecting a small subsample xi1 , . . . , xis so that it is possible to perfectly retrieve F from its behavior only on the subsample xi1 , . . . , xim along with very little extra information? Procedures that achieve this compression and retrieval are called sample compression schemes. As it turns out [LW86, DMY16, MY16], PAC learnability of a class is equivalent to the existence of a sample compression scheme that is non-trivial in the sense that the subsample (along with the extra information) is of size o(m). In turn, sample compression also enjoys a boosting phenomenon in the sense that when a non-trivial sample compression scheme exists, then there is also a sample compression scheme of size O(ln m · ln ln m). This puts sample compression into the list of the many learning theory notions that are equivalent to finiteness of the Vapnik–Červonenkis (VC) dimension (see e.g. [SSBD14, Theorem 6.7] for a non-comprehensive list as starting point). Recently, there has been a series of works [Kob15, KT15, LM19a, LM19b, CM24, CM25a, CM25b, HMS26] studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. The overall philosophy of high-arity learning theory is that when we replace the underlying set X by a product space X1 × · · · × Xk and require the learning theory concept to respect the product space structure, then more classes satisfy the high-arity learning concept than the classic learning concept. To illustrate this high-arity learning theory principle, introduce some of the high-arity concepts and frame the current work, let us briefly describe some of the results that appear in the works that are more closely related to the current one (see Section 1.1 for a brief description of the others): • In [LM19a, LM19b], Livni–Mansour introduce the high-arity uniform convergence property of a class H of subsets of X1 × · · · × Xk as the property that for all distributions µi over Xi , if we 1
sample m = m(ε, δ) i.i.d. points xi1 , . . . , xim from each µi , then with probability at least 1 − δ, the sample will be ε-representative for H in the sense that for every F ∈ H, the proportion of N k-tuples of the form (x1j1 , . . . , xkjk ) that belong to F is ε-close to the ki=1 µi -measure of F . Livni–Mansour then introduced the graph-VC dimension (gVC) of such a class H as the maximum VC dimension of the classes of slices of H, that is, once we fix values for k − 1 coordinates, this produces a slice class of sets on the last coordinate, of which one can compute the VC dimension and maximize over the choice of fixed values. Finally, they proved that high-arity uniform convergence property is equivalent to finiteness of gVC dimension and further equivalent to the existence of discriminating algorithms in terms of IPM distance. • In [CM24, CM25a], the first author and Malliaris introduced high-arity PAC learnability and proved that it is also equivalent to finiteness of gVC in the binary label case, and in the more general setting of finite labels is equivalent to an analogous dimension, which they called the Vapnik–Červonenkis–Natarajan k-dimension (VCNk ), which is defined analogously to gVC as the maximum Natarajan dimension of the slices. This work also identified a phenomenon exclusive to high-arity theory: the presence of two variant of each high-arity concept called the partite and non-partite. For partite k-PAC learnability, we have a class H of functions of the form X1 × · · · × Xk → Y and we want an algorithm A such that for all distributions µi over Xi , if we sample m = m(ε, δ) i.i.d. points xi1 , . . . , xim from each µi and give A these k · m points along with the mk values F (x1j1 , . . . , xkjk ) on every k-tuple (j1 , . . . , jk ), then with probability at least 1 − δ, the algorithm N A outputs some H that is ε-close in ki=1 µi -measure to F (see Definition 2.1 for a formal statement). For non-partite k-PAC learnability, we instead assume that X1 = · · · = Xk and we only require A to handle the case in which µ1 = · · · = µk (see Definition 3.1 for a formal statement). For a non-partite class H, we can certainly interpret it as a partite class Hk -part by simply ignoring the fact that X1 = · · · = Xk and it is easy to see that partite k-PAC learnability of Hk -part implies non-partite k-PAC learnability, but one of the main results of [CM24] is that, provided the label set Y is finite, these are in fact equivalent, and both characterized by finiteness of VCNk dimension. This work also introduced a (quite technical) notion of high-arity agnostic learnability based on exchangeability theory, which we will briefly discuss in Section 4.2. • In [HMS26], Holzman–Moran–Shlimovich showed that partite k-PAC learnability can be upgraded to handle measures that are not product measures, but are in a sense not far from them. More specifically, suppose P is a collection of distributions on X1 × · · · × Xk that are uniformly absolutely continuous with respect to their marginals in the sense that for every α > 0, there exists β > 0 such that for every µ ∈ P and every measurable B ⊆ X1 × · · · × Xk N with µ(B) ≥ α, then ( ki=1 µi )(B) ≥ β, where µi is the marginal of µ on Xi . In this work, finiteness of gVC dimension (which is given the name “linear VC dimension” here) is equivalent to learnability (in the usual classic PAC sense) versus all collections of distributions that are uniformly absolutely continuous with respect to their marginals (but, as expected, the learning guarantee depends on the quality of the modulus of uniform absolute continuity, i.e., the function β = β(α)). 2
In this work, we introduce the notion of high-arity sample compression (see Definitions 2.2 and 3.2) and we prove that both in the partite and non-partite settings, high-arity sample compression implies high-arity PAC learnability (Theorems 2.4 and 3.4). As is typical with high-arity concepts, the main challenge is the fact that labels in high-arity no longer are i.i.d., which precludes us from applying concentration estimates such as Chernoff or Bernstein Inequalities. However, we show that both in the partite and non-partite setting, we can appropriately define a martingale that allows us to use Azuma’s Inequality instead. We briefly discuss in Section 4.1 the difficulties in proving the converse implication (i.e., that high-arity PAC learnability implies high-arity sample compression).
1.1
Other related work
High-arity learning is much more complex than classical theory. In particular, even for something as simple as PAC learning, the big picture is that there should be different levels of learnability depending on the particular information that is received by the learner. For example, the PACk learnability model introduced by Kobayashi [Kob15], in which the learner also receives oracles for slices of the sample, was shown [KT15] to be governed by a combinatorial dimension connected to the model-theoretic notion of k-dependence introduced by Shelah [She14, § (H)]. The same notion of k-dependence is what governs [CPT19] the asymptotic drop via a high-arity analogue of the Sauer–Shelah–Perles Lemma [Sau72, She72, Per72] in the number of possible patterns on a grid of size m from mk to mk−Ω(1) . In turn, such a drop in the number of possible patterns was then used to characterize [CM25b] when one can perform matrix-completion in Netflix-like problems. In a different direction, there is a strong connection between combinatorial dimensions from learning theory to the tamer Szemerédi Regularity Lemmas. In particular, the VC dimension was shown to characterize [AFN07, LS10] classes of graphs that admit regularity partitions that are homogeneous and classes of hypergraphs that admit a regularity partition into polynomially many parts [FPS19, Ter24b]. On the high-arity side, the gVC dimension (known under other names such as slicewise VC dimension in the combinatorial community) was shown to characterize [TW22, CT20] classes of hypergraphs that admit homogeneous (vertex) partitions and classes of hypergraphs that admit weak regularity lemmas into exponentially many parts [Ter24a, Ter24b, GSW25]. Finally, the aforementioned k-dependence was shown to characterize hypergraph classes that admit a 0/1-valued strong regularity lemma [TW22, CT20]. Most of these connections happen via Haussler packing property [Hau95] and a high-arity version of it [CT20, CM25a].
1.2
General notation def
The set of non-negative integers is denoted N and the set of positive integers is denoted N+ = N\{0}. def For a finite set V and k ∈ N, we let Vk = {U ⊆ V | |U | = k} be the set of subsets of V of size k def
and we let (V )k be the set of injective functions of the form [k] → V , where [k] = {1, . . . , k}. Given def further n ∈ N, we let (n)k = n(n − 1) · · · (n − k + 1) denote the falling factorial (so |(V )k | = (|V |)k ). For the particular case of ([k])k , we use the more standard notation Sk (as ([k])k is the set of permutations on [k]). For a measurable space Ω = (X, B), we let Pr(Ω) be the set of probability measure on Ω. Countable sets will always be equipped with the discrete σ-algebra.
3
2
Partite setting
In this section we cover the partite case, that is, the case in which our hypotheses classes are collections of functions of the form F : X1 × · · · × Xk → Y , k-PAC learning notions are with respect N to product measures ki=1 µi and samples are thought of as having m points xj1 , . . . , xjm from each Xj as well as labels F (x1α1 , . . . , xkαk ) ∈ Y for each k-tuple α ∈ [m]k . We use a simplified version of the notation of [CM24] (the main difference is that since we do not either agnostic or higher-order variables, which allows us to drastically simplify the notation; however, we briefly comment on how our proofs adapt to these settings in Section 4.2). Definition 2.1 (Partite setting). Let k ∈ N+ , let Ω = (Ωi )ki=1 be a k-tuple of non-empty standard Borel spaces Ωi = (Xi , Bi ), let Λ = (Y, B ′ ) be a non-empty standard Borel space and let m ∈ N. 1. A k-partite unlabeled sample of size m with respect to Ω is an element of ki=1 Xim . A k-partite Q k labeled sample of size m with respect to Ω and Λ is an element (x, y) of ( ki=1 Xim ) × Y [m] ; we think of the coordinate yα indexed by some k-tuple α ∈ [m]k as the label on xα1 , . . . , xαk . This concept is formalized as follows: for every α ∈ [m]k , we contra-variantly define maps Q
α∗ :
k Y
Xim →
i=1
k Y
k
α∗ : Y [m] → Y
Xi ,
i=1
that select the k-tuple indexed by α and its label respectively via def
α∗ (x)i = xαi
x ∈
k Y
Xjm , i ∈ [k] ,
j=1 def
k
α∗ (y) = yα ,
y ∈ Y [m] .
2. With a slight abuse of notation, we denote by Pr(Ω) the set of k-tuples µ = (µi )ki=1 , where def N
µi ∈ Pr(Ωi ) is a probability measure on Ωi . Given further m ∈ N, we let µm = ki=1 µm i Q denote the product probability measure on the set ki=1 Xim of k-partite unlabeled samples of size m that is m copies of each measure µi . With a small abuse of notation, we view µ1 also Q Q as a measure over ki=1 Xi via the natural identification with ki=1 Xi1 . 3. A k-partite hypothesis from Ω to Λ is a measurable function F : k-partite hypothesis from Ω to Λ is denoted Fk (Ω, Λ).
i=1 Xi → Y .
Qk
The set of
k ∗ : m Given a k-partite hypothesis F ∈ Fk (Ω, Λ) and m ∈ N, we define the function Fm i=1 Xi → k Y [m] that when given an unlabeled sample of size m, provides the labels of F on the k-tuples of the sample; in a formula:
Q
def ∗ Fm (x)α = F
∗
α (x)
x∈
k Y
!
Xim , α ∈ [m]k
.
i=1
4. A k-partite hypothesis class is a set H ⊆ Fk (Ω, Λ) of k-partite hypotheses that is further equipped with a σ-algebra such that: • the evaluation map ev : H ×
Qk
i=1 Xi → Y
4
def
given by ev(H, x) = H(x) is measurable;
• for every H ∈ H, the singleton {H} is measurable; • for every Borel space Υ and every measurable set A ⊆ H × Υ, the projection of A onto Υ, i.e., the set {υ ∈ Υ | ∃H ∈ H, (H, υ) ∈ A} is universally measurable1 . 5. A k-partite loss function over Λ is a measurable function ℓ : ( ki=1 Xi ) × Y × Y → R≥0 that when given a k-tuple x and two labels y and y ′ assigns a value ℓ(x, y, y ′ ) that is the penalty of guessing y on the tuple x when the correct label was y ′ . Q
We define def
∥ℓ∥∞ =
ℓ(x, y, y ′ )
sup
Qk
x∈ i=1 Xi y,y ′ ∈Y
and we say that ℓ is bounded if ∥ℓ∥∞ < ∞. Given further µ ∈ Pr(Ω) and k-partite hypotheses F and H, the total loss of H with respect to µ, F and ℓ is h
def
i
Lµ,F,ℓ (H) = Ex∼µ1 ℓ x, H(x), F (x) . We say that F is realizable in a k-partite hypothesis class H ⊆ Fk (Ω, Λ) with respect to µ and ℓ if inf H∈H Lµ,F,ℓ (H) = 0. 6. For a k-partite hypothesis class H′ ⊆ Fk (Ω, Λ), a (k-partite) learning algorithm with outputs in H′ is a measurable function A:
[
k Y
m∈N
i=1
!
Xim
×Y
[m]k
!
→ H′ .
We say that a k-partite hypothesis class H ⊆ Fk (Ω, Λ) is improperly k-PAC learnable with reQ spect to a k-partite loss function ℓ : ( ki=1 Xi )×Y ×Y → R≥0 if there exists a learning algorithm 2 A with outputs in some k-partite hypothesis class H′ and a function mPAC H,ℓ,A : (0, 1) → R≥0 such that for every ε, δ ∈ (0, 1), every µ ∈ Pr(Ω), every F ∈ Fk (Ω, Λ) that is realizable in H with respect to µ and ℓ and every integer m ≥ mPAC H,ℓ,A (ε, δ), we have
∗ Px∼µm Lµ,F,ℓ A x, Fm (x)
≤ ε ≥ 1 − δ.
In plain English: when given a random sample of size m drawn from µm labeled according to some realizable F , the algorithm A outputs some hypothesis H with total loss at most ε with probability at least 1 − δ over the randomness of the sample. 1
The reader unfamiliar with these technical measurability conditions can simply assume that H is equipped with a σ-algebra that makes it a standard Borel space as it will imply this condition. The reader that wants to ignore measurability concerns can simply interpret this as “all probabilities computed must make sense”; in fact, this universal measurability condition is required only to make sense of the notion of high-arity uniform convergence to make sense, which is out of the scope of this paper.
5
The function mPAC H,ℓ,A is called the learning guarantee of A and A is called an improper k-PAC learner for H with respect to ℓ. The notions of proper k-PAC learnability and proper k-PAC learner are defined analogously but requiring further that H′ = H. k
7. Given a k-partite labeled sample (x, y) ∈ ( ki=1 Xim )×Y [m] of size m, a k-partite loss function Q ℓ : ( ki=1 Xi ) × Y × Y → R≥0 and a hypothesis H ∈ Fk (Ω, Λ), the empirical loss (or empirical risk) of H with respect to (x, y) and ℓ is Q
def
Lx,y,ℓ (H) =
X 1 ∗ ℓ α∗ (x), Hm (x)α , yα , k ·
m
if m > 0,
α∈[m]k
0,
if m = 0.
We say that (x, y) is sample realizable in a k-partite hypothesis class H ⊆ Fk (Ω, Λ) with respect to ℓ if inf H∈H Lx,y,ℓ (H). It is straightforward to check that if µ ∈ Pr(Ω), F ∈ Fk (Ω, Λ) is realizable in H with respect to µ and ℓ and x ∼ µm , then with probability 1, we have that ∗ (x)) is sample realizable in H with respect to ℓ. (x, Fm k
8. Given a k-partite labeled sample (x, y) ∈ ( ki=1 Xim ) × Y [m] of size m, a k-tuple α = (αi )ki=1 of injective functions αi : [n] → [m] induces naturally a subsample (α# (x), α# (y)) of size n by picking the points and labels corresponding to the coordinates indexed by α1 , . . . , αk (in their order). This is formalized as follows: we contra-variantly define the maps Q
α# :
k Y
Xim →
i=1
k Y
k
k
α# : Y [m] → Y [n]
Xin ,
i=1
that select the points and labels according to def
α# (x)i v = (xi )αi (v)
x ∈
k Y
Xjm , i ∈ [k], v ∈ [n] ,
j=1
def
k
α (y) β = yα1 (β1 ),...,αk (βk ) #
y ∈ Y [m] , β ∈ [n]k .
With slight abuse of notation, we also contra-variantly define the map α# :
k Y
!
Xim × Y
[m]k
→
i=1
k Y
!
k
Xin × Y [n]
i=1
by letting it act as the previous two maps in the corresponding coordinates. The overload in ∗ of 2.1.3 equivariant in the notation is justified by the fact that it makes the definition of Fm the sense that the following diagram is commutative: Qk
m i=1 Xi
∗ Fm
k
Y [m]
α#
α#
Qk
n i=1 Xi
Fn∗
k
Y [n]
The avid reader will note that the maps α∗ of 2.1.1 are essentially the particular case of the above when n = 1. 6
The next definition is that of a high-arity selection/compression scheme. Informally, a selection scheme has to have two procedures: a selection procedure κm that takes in a sample of size m and outputs a smaller subsample of size sm along with some extra information (a header) and a reconstruction procedure ρm that takes in the output of κm and reconstructs the original sample. The selection scheme is then called a compression scheme when it correctly reconstructs the original sample (in the sense of zero loss). Definition 2.2 (Partite selection/compression schemes). Let k ∈ N+ , let Ω = (Ωi )ki=1 be a k-tuple of non-empty standard Borel spaces Ωi = (Xi , Bi ) and let Λ = (Y, B ′ ) be a non-empty standard Borel space. 1. A k-partite selection scheme with outputs in a k-partite hypothesis class H′ ⊆ Fk (Ω, Λ) is a tuple S = (σ, η, ρ) such that: • σ = (σm )m∈N is a sequence of maps, called selection maps, such that each σm when given a sample of size m, outputs k tuples of some length sm that are the indices of the subsample selected. Formally, each σm is a measurable function
σm :
k Y
k Xjm × Y [m] →
j=1
k Y
([m])sm ,
i=1
where sm ∈ N is some integer, which we call the selection size (note that we must have sm ≤ m as the domain of σm is never empty). • η = (ηm )m∈N is a sequence of maps, called the header maps, that when given a sample of size m, outputs some extra information, encoded as an element of [hm ] for some fixed hm ∈ N, that will aid in the reconstruction of the original sample. Formally, each ηm is a measurable function
ηm :
k Y
k
Xjm × Y [m] → [hm ],
j=1
where hm ∈ N+ is called the header size of ηm . • ρ = (ρm )m∈N is a sequence of maps, called the reconstruction maps, that when given a labeled sample of size sm and header of size hm (intended to have come from σm and ηm ), reconstruct a labeled sample of size m. Formally, each ρm is a measurable function ρm :
k Y
!
Xism
k
× Y [sm ] × [hm ] → H′ .
i=1
The compression procedure of S is formalized by defining a sequence κ = (κm )m∈N of compression maps of the form κm :
k Y
!
Xim
×Y
[m]k
→
i=1
k Y
!
Xism
k
× Y [sm ] × [hm ]
i=1
by def
κm (x, y) = σm (x, y)# (x, y), ηm (x, y)
x∈
k Y i=1
7
Xim , y ∈ Y
[m]k
!
.
(Recall from Definition 2.1.8 that since σm (x, y) ∈ ki=1 ([m])sm is a k-tuple of injections, it contra-variantly induces a map that selects a subsample σm (x, y)# (x, y) of size sm from the sample (x, y) of size m and the map κm then takes this subsample an appends to it the header ηm (x, y).) Q
We will use the notation def
η S = η = (ηm )m∈N ,
def
hSm = hm ,
σ S = σ = (σm )m∈N , sSm = sm ,
def
ρS = ρ = (ρm )m∈N ,
def
def
κS = κ = (κm )m∈N .
def
If Y is finite, the compression size and the compression bitlength functions of S are the functions cS , bS : N → R≥0 given by def
def
k
cS (m) = hm · |Y |sm ,
bS (m) = log2 cS (m) .
2. A k-partite selection scheme S with outputs in a k-partite hypothesis class H′ ⊆ Fk (Ω, Λ) is called a sample compression scheme for a k-partite hypothesis class H ⊆ Fk (Ω, Λ) with Q respect to a k-partite loss function ℓ : ( ki=1 Xi ) × Y × Y → R≥0 if for every m ∈ N and every Q k labeled sample (x, y) ∈ ( ki=1 Xim ) × Y [m] of size m that is sample realizable with respect to ℓ, we have
Lx,y,ℓ ρSm κSm (x, y)
= 0,
or in plain English: if we compress (x, y) via κS then reconstruct via ρS , then the result has zero empirical loss. We say that the sample compression scheme is proper if H = H′ . Our goal is to prove that the existence of a k-partite compression scheme (of essentially nontrivial quality) implies k-PAC learnability. We start with a concentration lemma based on Azuma’s Inequality. Lemma 2.3. Let k ∈ N+ , let Ω = (Ωi )ki=1 be a k-tuple of non-empty standard Borel spaces Ωi = (Xi , Bi ), let Λ = (Y, B ′ ) be a non-empty standard Borel space, let S be a k-partite selection Q scheme and let ℓ : ki=1 Xi × Y × Y → R≥0 be a bounded k-partite loss function. Then for every ε > 0, every µ ∈ Pr(Ω), every integer m ∈ N such that (m − sSm )k 1− mk
!
(2.1)
· ∥ℓ∥∞ < ε,
every η ∈ [hSm ], every k-tuple σ = (σi )ki=1 of injections σi : [sSm ] → [m] and every F ∈ Fk (Ω, Λ), we have "
Px∼µm Lµ,F,ℓ ρ
S
σ
#
∗ x, Fm (x) , η
S
− Lx,Fm∗ (x),ℓ ρ
σ
#
∗ x, Fm (x) , η
#
≥ε
εe · (m − sSm ) ≤ exp − , 2 · k · ∥ℓ∥2∞ !
8
where def
εe = (ε − (1 − (m − sSm )k /mk ) · ∥ℓ∥∞ )2 > 0. In particular, if sSm ≤ o(m) as m → ∞, then "
∗ (x) , η Px∼µm Lµ,F,ℓ ρS σ # x, Fm
∗ (x) , η − Lx,Fm∗ (x),ℓ ρS σ # x, Fm
#
≥ε
ε2 ε · (ε + ∥ℓ∥∞ ) ≤ exp − ·m+ · o(m) , 2 · k · ∥ℓ∥2∞ ∥ℓ∥2∞ !
where the o(m) error term is as m → ∞ with k fixed, is uniform in ε, and has the same uniformity in ∥ℓ∥∞ as the estimate sSm ≤ o(m). Proof. The result is trivial if m = 0, so suppose m > 0. By symmetry, we may suppose without loss of generality that for each i ∈ [k], σi : [sSm ] → [m] is such that im(σi ) = {m − sSm + 1, m − sSm + 2, . . . , m}. Pick x at random according to µm and for ease of notation, let def
n = m − sSm ,
def
def
∗ H = ρSm σ # x, Fm (x) , η ,
x′ = ι# (x),
where ι = (ιi )ki=1 is the k-tuple of inclulsion maps ιi : [n] → [m] (so x′ is the random sample corresponding to the first n points of x in each of the k coordinates, in their natural order). Note that Lx,Fm∗ (x),ℓ (H) − Lx′ ,Fn∗ (x′ ),ℓ (H) =
X 1 ∗ ∗ ∗ · ℓ α (x), H (x) , F (x) α m m mk k α∈[m]
−
X 1 ∗ ∗ ∗ ℓ α (x), H (x) , F (x) · α m m nk k α∈[n]
=
1 1 − k k m n +
1 · mk
·
X
∗ ∗ ℓ α∗ (x), Hm (x)α , Fm (x)
α∈[n]k
X
∗ ∗ (x)α , Fm (x) , ℓ α∗ (x), Hm
α∈[m]k \[n]k
and since ℓ is bounded and noting that the first term in the above is non-positive (as n ≤ m) and the second term is non-negative, we conclude that Lx,Fm∗ (x),ℓ (H) − Lx′ ,Fn∗ (x′ ),ℓ (H) ≤ ∥ℓ∥∞ · max =
nk 1− k m
1 1 − k k n m
!
· nk ,
1 · (mk − nk ) mk
(2.2)
· ∥ℓ∥∞ .
Since we are mostly concerned with the setting in which sSm ≤ o(m) (i.e., n = (1 − o(1)) · m), the difference above is small so we will compare Lµ,F,ℓ (H) with Lx′ ,Fn∗ (x′ ),ℓ first.
9
Let F0 be the σ-algebra generated by ((xi )v )i∈[k],v∈[m]\[n] (i.e., generated by σ # (x)), so H is F0 -measurable. For each t ∈ [k · n], we let Fi be the σ-algebra generated by F0 and all (xi )v with (i, v) ∈ [k] × [n] satisfying (i − 1) · n + v − 1 < t, that is, from Ft−1 to Ft , we add the variable (xit )vt , where def
it =
t−1 + 1, n
def
vt = (t − 1) mod n + 1.
(2.3)
def
We also let Zt = E[Lx′ ,Fn∗ (x′ ),ℓ (H) | Ft ] and we note that (Zt )k·n t=0 forms a (Doob) martingale k·n with respect to (Ft )t=0 : h
E[Zt+1 | Ft ] = E E Lx′ ,Fn∗ (x′ ),ℓ (H) Ft+1
i
Ft = E Lx′ ,Fn∗ (x′ ),ℓ (H) Ft = Zt .
Note further that Z0 = E Lx′ ,Fn∗ (x′ ),ℓ (H) F0 = Lµ,F,ℓ (H),
Zk·n = E Lx′ ,Fn∗ (x′ ),ℓ (H) Fk·n = Lx′ ,Fn∗ (x′ ),ℓ (H),
where the former is by linearity of conditional expectation (and the fact that H is F0 -measurable) and the latter is simply because the underlying random variable is Fk·n -measurable. We will show that Z0 and Zk·n are close with high (conditional) probability using Azuma’s Inequality. Toward that, we note that for each t ∈ [k · n] we have |Zt − Zt−1 | =
i X h 1 ∗ ′ ∗ ′ ∗ ′ E ℓ α (x ), H (x ), F (x ) F · t n n nk k α∈[n]
h
− E ℓ α∗ (x′ ), Hn∗ (x′ ), Fn∗ (x′ )
Ft−1
i
. (2.4)
Let us now argue that most of the terms in the sum above are zero. Recall that what changes from Ft−1 to Ft is the addition of the variable (xit )vt , where (it , vt ) are given by (2.3). Consider a term α ∈ [n]k such that αit ̸= vt , then ℓ α∗ (x′ ), Hn∗ (x′ ), Fn∗ (x′ )
is independent from (xit )vt ; in fact, since ((xi )v )i∈[k],v∈[m] is mutually independent, the above is conditionally independent from (xit )vt given Ft−1 , so the above gives the same value when conditioned on Ft−1 as it does when conditioned on Ft . Thus, whenever αit ̸= vt , the corresponding term in (2.4) is zero. As there are exactly nk−1 many α ∈ [n]k with αit = vt , using triangle inequality and the fact that ℓ is bounded, we conclude that |Zt − Zt−1 | ≤
nk−1 ∥ℓ∥∞ · ∥ℓ∥∞ = . k n n 10
Recalling that nk εe = ε − 1 − k m def
!
· ∥ℓ∥∞ > 0
(where the inequality follows from our assumption (2.1)), by Azuma’s Inequality (conditioned on F0 ), we get
Px∼µm Lµ,F,ℓ (H) − Lx′ ,Fn∗ (x′ ),ℓ (H) ≥ εe = P[Zk·n − Z0 ≤ −εe] εe2 ≤ exp − Pk·n 2 · t=1 (∥ℓ∥∞ /n)2 εe2 · n = exp − 2 · k · ∥ℓ∥2∞
!
!
εe2 · (m − sSm ) = exp − . 2 · k · ∥ℓ∥2∞ !
Putting this together with (2.2), we conclude that εe · (m − sSm ) Px∼µm Lµ,F,ℓ (H) − Lx,Fm∗ (x),ℓ (H) ≥ ε ≤ exp − , 2 · k · ∥ℓ∥2∞ !
as desired. Let us now estimate the above asymptotically when sSm ≤ o(m). First note that 1 − (m − sS )k /mk = o(1) as m → ∞ with k fixed as m − sSm = (1 − o(1)) · m. Then we get εe2 · (m − sSm ) (ε − ∥ℓ∥∞ · o(1))2 · (1 − o(1)) · m exp − , = exp − 2 · k · ∥ℓ∥2∞ 2 · k · ∥ℓ∥2∞ !
!
ε · (ε + ∥ℓ∥∞ ) ε2 ·m+ · o(m) , ≤ exp − 2 2 · k · ∥ℓ∥∞ ∥ℓ∥2∞ !
where the o(m) error term is as m → ∞ with k fixed, is uniform in ε, and has the same uniformity in ∥ℓ∥∞ as the estimate sSm ≤ o(m). The next theorem shows that every k-partite hypothesis class that admits a k-partite compression scheme S of essentially non-trivial quality must be k-PAC learnable. More specifically, a trivial k-partite compression scheme has sSm = m and hSm = 1, which yields ln(hSm ) + k · sSm · ln(m) = k · m · ln(m) and our assumption is that we have a k-partite compression scheme in which the quantity above is o(m) instead. Theorem 2.4. Let k ∈ N+ , let Ω = (Ωi )ki=1 be a k-tuple of non-empty standard Borel spaces Q Ωi = (Xi , Bi ), let Λ = (Y, B ′ ) be a non-empty standard Borel space with |Y | ≥ 2, let ℓ : ki=1 Xi ×
11
Y × Y → R≥0 be a bounded k-partite loss function and let S be a k-partite compression scheme for a k-partite hypothesis class H ⊆ Fk (Ω, Λ) such that ln(hSm ) + k · sSm · ln(m) ≤ o(m)
(2.5)
as m → ∞ (which in particular follows from bS (m) ≤ o(m/ ln(m)) when Y is finite), then H is k-PAC learnable with respect to ℓ. More specifically, letting A be given by def
A(x, y) = ρSm κSm (x, y)
m ∈ N, x ∈
k Y
!
Xim , y ∈ Y ([m])k
i=1
gives a k-PAC learner for H with respect to ℓ with learning guarantee def
(m − sSm )k ∀m ≥ m0 , 1 − mk
(
mPAC H,ℓ,A (ε, δ) = min m0 ∈ N+ , ∧ (m)ksSm · hSm · exp
!
<ε
(ε − (1 − (m − sSm )k /mk ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k · ∥ℓ∥2∞
!
)
≤ δ . (2.6)
In particular, if √
ln(hSm ) + k · sSm · ln(m) ≤ 1 + o(1) ·
2 · k · m · ln(m),
(2.7)
as m → ∞, then mPAC H,ℓ,A (ε, δ) ≤
2 · k · ∥ℓ∥2∞
1 + o(1) ·
ε2
· max 1, ln
1 δ
,
where the o(1) error term is as ε → 0 with k fixed, is uniform in δ, and has the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (2.7) provided ∥ℓ∥∞ is bounded away from 0. Proof. We start by showing that bS (m) ≤ o(m/ ln(m)) (when Y is finite) implies the condition (2.5) (i.e., ln(hSm ) + k · sSm · ln(m) ≤ o(m)). Indeed, for m ≥ e, we have ln(hSm ) + k · sSm · ln(m) ≤ ln(m) · log2 (hSm ) + k · sSm · log2 |Y | ≤ ln(m) · bS (m) ≤ o(m).
Let us now argue that the minimum in (2.6) indeed exists. For this, it suffices to argue that there exists m0 ∈ N satisfying both conditions in the definition of the minimum. But indeed, since we are assuming that (2.5) (i.e., ln(hSm ) + k · sSm · ln(m) ≤ o(m)) holds, it follows that both (m − sSm )k 1− mk (m)ksSm · hSm · exp
!
· ∥ℓ∥∞ ,
(ε − (1 − (m − sSm )k /mk ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k · ∥ℓ∥2∞
!
converge to 0 as m → ∞ (with all other parameters fixed). So there must exist m0 ∈ N large enough so that for every m ≥ m0 , the first expression above is less than ε and the second expression above is at most δ. 12
We now prove the result. Let µ ∈ Pr(Ω) and F ∈ Fk (Ω, Λ) be a k-partite hypothesis that is e be realizable with respect to µ and ℓ. Given ε, δ ∈ (0, 1), let m ≥ mPAC H,ℓ,A (ε, δ) be an integer and let ε defined in terms of m, sSm , k and ℓ as in Lemma 2.3 and note that since m ≥ mPAC (ε, δ), the first H,ℓ,A condition in the definition of the latter implies that the condition (2.1) of Lemma 2.3 is satisfied. We now pick x at random according to µm and for each k-tuple σ = (σi )ki=1 of injections [sSm ] → [m] and each η ∈ [hSm ], we let Eσ,η (x) be the event
∗ Lµ,F,ℓ ρSm σ # x, Fm (x) , η
∗ − Lx,Fm∗ (x),ℓ ρSm σ # x, Fm (x) , η
≥ε
so that Lemma 2.3 says that εe2 · (m − sSm ) Px∼µm Eσ,η (x) ≤ exp − . 2 · k · ∥ℓ∥2∞ !
If we let E(x) be the disjunction of the events Eσ,η (x), since there are (m)ksS many such σ and m
hSm many such η, by the union bound, we get εe2 · (m − sSm ) − . 2 · k · ∥ℓ∥2∞ !
Px∼µm E(x)
≤ (m)ksSm · hSm · exp
We now ntoat that we have the compression scheme guarantee that
Lx,Fm∗ (x),ℓ ρSm
∗ κSm x, Fm (x)
=0
∗ (x)) is sample realizable in H with respect to ℓ, which happens with probability 1 whenever (x, Fm as F is realizable in H with respect to ℓ. S (x, F ∗ (x)) and the (random) The above along with the fact that the (random) injection σm m S (x, F ∗ (x)) are elements of ([m])k and [hS ], respectively, implies that header ηm m m sS
∗ Px∼µm Lµ,F,ℓ A x, Fm (x)
"
>ε
∗ = Px∼µm Lµ,F,ℓ ρSm κSm x, Fm (x)
#
>ε
≤ Px∼µm E(x)
≤ (m)ksSm · hSm · exp
εe2 · (m − sSm ) − . 2 · k · ∥ℓ∥2∞
= (m)ksSm · hSm · exp
(ε − (1 − (m − sSm )k /mk ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k · ∥ℓ∥2∞
!
!
≤ δ, where the last inequality follows from m ≥ mPAC H,ℓ,A (ε, δ) and using the second condition in the definition of the latter. Thus A is a k-PAC learner with respect to ℓ.
13
It remains to make the asymptotic estimate of mPAC H,ℓ,A (ε, δ) when the stronger assumption (2.7) √ S S (i.e., ln(hm ) + k · sm · ln(m) ≤ (1 + o(1)) · 2 · k · m · ln(m)) holds. (It is clear that (2.7) implies the condition (2.5) that ln(hSm ) + k · sSm · ln(m) ≤ o(m).) Let m1 (ε) ∈ N+ be the least integer such that for every m ≥ m1 (ε), we have (m − sS )k 1− mk
!
(2.8)
· ∥ℓ∥∞ < ε
and let m2 (ε, δ) be the least integer such that for every m ≥ m2 (ε, δ), we have (ε − (1 − (m − sSm )k /mk ) · ∥ℓ∥∞ )2 · (m − sSm ) (m)ksSm · hSm · exp − 2 · k · ∥ℓ∥2∞
!
≤ δ,
(2.9)
Since mPAC H,ℓ,A (ε, δ) = max{m1 (ε), m2 (ε, δ)}, it suffices to give asymptotic estimates for m1 (ε) and m2 (ε, δ). To estimate m1 (ε), note that if ∥ℓ∥∞ < ε, then m1 (ε) = 1, so suppose that ∥ℓ∥∞ ≥ ε and note that sSm (m − sSm )k = 1 − 1 − 0≤1− mk m ≤ 1 − 1 − 1 + o(1) ·
r
2 k·m
!k
!k
s
= 1 + o(1) ·
(2.10)
2·k m
as m → ∞ with k fixed. Plugging this asymptotic estimate in the definition (2.8) of m1 (ε), we conclude that m1 (ε) ≤ 1 + o(1)
2 · k · ∥ℓ∥2∞
(2.11)
ε2
where the o(1) error term is as ε → 0 with k fixed, is uniform in δ (as m1 (ε) does not depend on δ at all), and has the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (2.7) provided ∥ℓ∥∞ is bounded away from 0 (this is to cover the case ∥ℓ∥∞ < ε when m1 (ε) = 1). To estimate m2 (ε, δ), we use (2.10) along with the weaker condition (2.5) (i.e., ln(hSm ) + k · sSm · ln(m) ≤ o(m)) to get (m)ksSm · hSm · exp
(ε − (1 − (m − sSm )k /mk ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k · ∥ℓ∥2∞
(ε − o(1) · ∥ℓ∥∞ )2 · (1 + o(1)) · m ≤ exp − + o(m) 2 · k · ∥ℓ∥2∞ !
!
!
!
ε2 − o(1) · m , ≤ exp − 2 · k · ∥ℓ∥2∞ where the error terms are as m → ∞ with k fixed, are uniform in ε, and have the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (2.7). Plugging this asymptotic estimate in the definition (2.9) of m2 (ε, δ), we conclude that 2 · k · ∥ℓ∥2 1 + o(1) · ln , 2 ε δ !
m2 (ε, δ) ≤
14
where the o(1) error term is as ε → 0, is uniform in δ, and has the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (3.6). Putting the above together with our estimate (2.11) for m1 (ε), we get mPAC H,ℓ,A (ε, δ) ≤
2 · k · ∥ℓ∥2∞
1 + o(1) ·
ε2
· max 1, ln
1 δ
,
as desired since mPAC H,ℓ,A = max{m1 (ε), m2 (ε, δ)}.
3
Non-partite setting
In this section, we cover the non-partite case, that is, the case in which our hypotheses classes are collections of functions of the form F : X k → Y , k-PAC learning notions are with respect to power measures µk of the same probability measure on X and sample are thought of as having m points x1 , . . . , xm from X as well as labels F (xα1 , . . . , xkαk ) ∈ Y for each injective k-tuple α ∈ ([m])k . Let us point out some of the peculiarities of the non-partite case: • Labels on k-ary samples only take into account injective tuples, that is, once we are given m points x1 , . . . , xm ∈ X, to form a labeled sample, we only collect labels from a hypothesis F : X k → Y of the form F (xα1 , . . . , xkαk ) ∈ Y with α : [k] → [m] injective. The reason why we do not collect labels of non-injective tuples is technical and comes from the agnostic setup via exchangeability theory. Nevertheless, we point out that even if we included non-injective tuples, since these account for a negligible proportion of all tuples (for m large), this would only change bounds on lower order terms by discounting non-injective tuples from calculations. • Loss functions ℓ collect labels from all orientations of a k-set, that is, given a k-tuple (x1 , . . . , xk ) ∈ X k and hypotheses F, H : X k → Y , we collect the labels of the hypotheses on all possible orientations of the k-tuple (x1 , . . . , xk ) into an element of Y Sk (recall that Sk = ([k])k is the symmetric group on [k]) before feeding them into the loss function. This accounts for the fact that X does not come with an inherent ordering and allows loss functions to take into account other orientations of the k-tuples before assigning a penalty. • When computing the empirical loss on a sample of m points x1 , . . . , xm , the k-tuples of it do not come with an inherent order, so there must be an order choice that picks one particular orientation for each k-subset of [m] as the “standard direction” in which the loss function is going to be computed. We again follow a simplified notation of [CM24]. Definition 3.1 (Non-partite setting). Let k ∈ N+ , let Ω = (X, B) and Λ = (Y, B ′ ) be non-empty standard Borel spaces and let m ∈ N. 1. A k-ary unlabeled sample of size m with respect to Ω is an element of X m . A k-ary labeled sample of size m with respect to Ω and Λ is an element of X m × Y ([m])k ; we think of the coordinate yα indexed by some injective k-tuple α ∈ ([m])k as the label on xα1 , . . . , xαk . More generally, every injection α : [n] → [m] induces naturally a subsample α∗ (x) of size n by picking the points and labels corresponding to the coordinates indexed by α (in the order of α). This is formalized as follows: we contra-variantly define the maps α∗ : X m → X n ,
α∗ : Y ([m])k → Y ([n])k 15
that select the points and labels according to def
x ∈ X m , i ∈ [n] ,
def
y ∈ Y ([m])k , β ∈ ([m])k .
α∗ (x)i = xα(i)
α∗ (y)β = yα◦β
With slight abuse of notation, we also contra-variantly define the map α∗ : X m × Y ([m])k → X n × Y ([n])k by letting it act as the previous two maps in the corresponding coordinates. 2. A k-ary hypothesis from Ω to Λ is a measurable function F : Xi → Y . The set of k-ary hypothesis from Ω to Λ is denoted Fk (Ω, Λ). ∗ : X m → Y ([m])k Given a k-ary hypothesis F ∈ Fk (Ω, Λ) and m ∈ N, we define the function Fm that when given an unlabeled sample of size m, provides the labels of F on the injective k-tuples of the sample; in a formula: def
∗ Fm (x)α = F α∗ (x)
x ∈ X m , α ∈ ([m])k .
Similarly to the partite case, this definition is equivariant in the sense that the following diagram is commutative: Xm
∗ Fm
Y ([m])k α∗
α∗
Xn
Fn∗
Y ([n])k
3. A k-ary hypothesis class is a set H ⊆ Fk (Ω, Λ) of k-ary hypotheses that is further equipped with a σ-algebra such that: def
• the evaluation map ev : H × X k → Y given by ev(H, x) = H(x) is measurable; • for every H ∈ H, the singleton {H} is measurable; • for every Borel space Υ and every measurable set A ⊆ H × Υ, the projection of A onto Υ, i.e., the set {υ ∈ Υ | ∃H ∈ H, (H, υ) ∈ A} is universally measurable2 . 4. A k-ary loss function over Λ is a measurable function ℓ : X k × Y Sk × Y Sk → R≥0 that when given a k-tuple x and two labels y and y ′ of all possible orientations of the k-tuple x, assigns a value ℓ(x, y, y ′ ) that is the penalty of guessing y on the tuple x when the correct label was y ′ . We define def
∥ℓ∥∞ =
sup
x∈X k y,y ′ ∈Y Sk
ℓ(x, y, y ′ )
2 Similarly to the partite case, the reader unfamiliar with these technical measurability conditions can simply assume that H is equipped with a σ-algebra that makes it a standard Borel space as it will imply this condition; or they can simply interpret this as “all probabilities computed must make sense”.
16
and we say that ℓ is bounded if ∥ℓ∥∞ < ∞. Given further µ ∈ Pr(Ω) and k-ary hypotheses F and H, the total loss of H with respect to µ, F and ℓ is h
def
i
Lµ,F,ℓ (H) = Ex∼µk ℓ x, Hk∗ (x), Fk∗ (x) . We say that F is realizable in a k-ary hypothesis class H ⊆ Fk (Ω, Λ) with respect to µ and ℓ if inf H∈H Lµ,F,ℓ (H) = 0. 5. For a k-ary hypothesis class H′ ⊆ Fk (Ω, Λ), a (k-ary) learning algorithm with outputs in H′ is a measurable function A:
(X m × Y ([m])k ) → H′ .
[ m∈N
We say that a k-ary hypothesis class H ⊆ Fk (Ω, Λ) is improperly k-PAC learnable with respect to a k-ary loss function ℓ : X k × Y Sk × Y Sk → R≥0 if there exists a learning algorithm A with 2 outputs in some k-ary hypothesis class H′ and a function mPAC H,ℓ,A : (0, 1) → R≥0 such that for every ε, δ ∈ (0, 1), every µ ∈ Pr(Ω), every F ∈ Fk (Ω, Λ) that is realizable in H with respect to µ and ℓ and every integer m ≥ mPAC H,ℓ,A (ε, δ), we have
Px∼µm
∗ Lµ,F,ℓ A x, Fm (x)
≤ ε ≥ 1 − δ.
In plain English: when given a random sample of size m drawn from µm labeled according to some realizable F , the algorithm A outputs some hypothesis H with total loss at most ε with probability at least 1 − δ over the randomness of the sample. The function mPAC H,ℓ,A is called the learning guarantee of A and A is called an improper k-PAC learner for H with respect to ℓ. The notions of proper k-PAC learnability and proper k-PAC learner are defined analogously but requiring further that H′ = H. 6. A (k-ary) order choice for [m] is a sequence α = (αU )U ∈(V ) of injections of the form αU : [k] → k
[m] with im(αU ) = U .
[m] Any such order choice α naturally induces a map bα : Y ([m])k → (Y Sk )( k ) that bundles up all labels corresponding to orientations of a k-set U into the coordinate indexed by U , where the standard orientation is considered to be in the direction of αU ; formally, the map bα is given by
def
bα (y)U π = yαU ◦π
[m] , π ∈ Sk . k !
y∈Y
([m])k
,U ∈
Qk
!
Given further k-ary labeled sample (x, y) ∈ ( ki=1 Ximi ) × Y i=1 [mi ] of sizes m, a k-ary loss function ℓ : X k × Y Sk × Y Sk → R≥0 and a hypothesis H ∈ Fk (Ω, Λ), the empirical loss (or Q
17
empirical risk) of H with respect to (x, y), ℓ and α is 1 m ·
def k Lαx,y,ℓ (H) =
X U ∈(
[m] k
)
∗ ∗ ℓ αU (x), bα Hm (x) U , bα (y)U ,
0,
if m ≥ k, if m < k.
We say that (x, y) is sample realizable in a k-ary hypothesis class H ⊆ Fk (Ω, Λ) with respect to ℓ and α if inf H∈H Lαx,y,ℓ (H). It is straightforward to check that if µ ∈ Pr(Ω), F ∈ Fk (Ω, Λ) is realizable in H with respect to µ and ℓ and x ∼ µm , then with probability 1, we have that ∗ (x)) is sample realizable in H with respect to ℓ and α. (x, Fm The next definition is that of a high-arity selection/compression scheme in the non-partite case. Note that since the definition of a compression schemes rely on empirical loss, in the non-partite case, we will also need to specify an order choice. Definition 3.2 (Non-partite setting). Let k ∈ N+ and let Ω = (X, B) and Λ = (Y, B ′ ) be non-empty standard Borel spaces. 1. A k-ary selection scheme with outputs in a k-ary hypothesis class H′ ⊆ Fk (Ω, Λ) is a tuple S = (σ, η, ρ) such that: • σ = (σm )m∈N is a sequence of maps, called selection maps, such that each σm when given a sample of size m, outputs a tuple of some length sm that contains the indices of the subsample selected. Formally, each σm is a measurable function σm : X m × Y ([m])k → ([m])sm where sm ∈ N (i ∈ [k]) is some integer, which we call the selection size (note that we must have sm ≤ m as the domain of σm is never empty). • η = (ηm )m∈N is a sequence of maps, called the header maps, that when given a sample of size m, outputs some extra information, encoded as an element of [hm ] for some fixed hm ∈ N, that will aid in the reconstruction of the original sample. Formally, each ηm is a measurable function ηm : X m × Y ([m])k → [hm ], where hm ∈ N+ is called the header size of ηm . • ρ = (ρm )m∈N is a sequence of maps, called the reconstruction maps, that when given a labeled sample of size sm and header of size hm (intended to have come from σm and ηm ), reconstruct a labeled sample of size m. Formally, each ρm is a measurable function ρm : X sm × Y ([sm ])k × [hm ] → H′ . The compression procedure of S is formalized by defining a sequence κ = (κm )m∈N of compression maps of the form κm : X m × Y ([m])k → X sm × Y ([sm ])k × [hm ] 18
by def
κm (x, y) = σm (x, y)∗ (x, y), ηm (x, y)
x ∈ X m , y ∈ Y ([m])k .
(Recall from Definition 3.1.1 that since σm (x, y) ∈ ([m])sm is a injection, it contra-variantly induces a map that selects a subsample σm (x, y)∗ (x, y) of size sm from the sample (x, y) of size m and the map κm then takes this subsample an appends to it the header ηm (x, y).) We will use the notation def
η S = η = (ηm )m∈N ,
def
hSm = hm ,
σ S = σ = (σm )m∈N , sSm = sm ,
def
ρS = ρ = (ρm )m∈N ,
def
def
κS = κ = (κm )m∈N .
def
The compression size and the compression bitlength functions of S are the functions cS , bS : N → R≥0 given by def
def
cS (m) = hm · |Y |(sm )k ,
bS (m) = log2 cS (m) .
2. A k-ary selection scheme S with outputs in a k-ary hypothesis class H′ ⊆ Fk (Ω, Λ) is called a sample compression scheme for a k-ary hypothesis class H ⊆ Fk (Ω, Λ) with respect to a k-ary loss function ℓ : X k × Y Sk × Y Sk → R≥0 if for every m ∈ N and every labeled sample (x, y) ∈ X m × Y ([m])k of size m that is sample realizable with respect to ℓ and every order choice α for [m], we have
Lαx,y,ℓ ρSm κSm (x, y)
= 0,
or in plain English: if we compress (x, y) via κS then reconstruct via ρS , then the result has zero empirical loss. Our goal is to prove the non-partite analogue of Theorem 2.4. We start with a concentration lemma based on Azuma’s Inequality that is the non-partite analogue of Lemma 2.3; the main differences of this lemma to its partite counterpart is that we need to keep track of the order choice k α and the bounds are slightly different due to normalization by m k as opposed to m and the fact that the martingale has m steps instead of k · m steps. Lemma 3.3. Let Ω = (X, B) and Λ = (Y, B ′ ) be non-empty standard Borel spaces, let k ∈ N+ , let S be a k-ary selection scheme and let ℓ : X k × Y Sk × Y Sk → R≥0 be a bounded k-ary loss function. Then for every ε > 0, every probability measure µ ∈ Pr(Ω), every integer m ∈ N such that (m − sSm )k 1− (m)k
!
(3.1)
· ∥ℓ∥∞ < ε,
every order choice α for [m], every η ∈ [hSm ], every injection σ : [sSm ] → [m] and every F ∈ Fk (Ω, Λ), we have "
Px∼µm Lµ,F,ℓ ρ
S
σ
∗
∗ x, Fm (x) , η
− Lαx,Fm∗ (x),ℓ
ρ
S
σ
∗
∗ (x) , η x, Fm
#
≥ε
εe2 · (m − sSm ) ≤ exp − , 2 · k 2 · ∥ℓ∥2∞ !
19
where (m − sSm )k εe = ε − 1 − (m)k def
!
· ∥ℓ∥∞ > 0.
In particular, if sSm ≤ o(m) as m → ∞, then "
S
Px∼µm Lµ,F,ℓ ρ
σ
∗
∗ x, Fm (x) , η
− Lαx,Fm∗ (x),ℓ
ρ
S
σ
∗
∗ x, Fm (x) , η
#
≥ε
ε2 ε · (ε + ∥ℓ∥∞ ) ≤ exp − ·m+ · o(m) , 2 2 2 · k · ∥ℓ∥∞ ∥ℓ∥2∞ !
where the o(m) error term is as m → ∞ with k fixed, is uniform in ε, and has the same uniformity in ∥ℓ∥∞ as the estimate sSm ≤ o(m). Proof. The result is trivial if m < k, so suppose m ≥ k. By symmetry, we may also suppose without loss of generality that σ : [sSm ] → [m] is such that im(σ) = {m − sSm + 1, m − sSm + 2, . . . , m}. Let us pick x at random according to µm and for ease of notation, we let def
def
n = m − sSm ,
def
∗ H = ρSm σ ∗ x, Fm (x) , η ,
x′ = ι∗ (x),
where ι : [n] → [m] is the inclusion map (so x′ is the random sample corresponding to the first n def coordinates of x, in their natural order). We also let α′ = α|([n]) be the order choice for [n] obtained k
by restricting α to the k-subsets of [n]. Note that ′
Lαx,Fm∗ (x),ℓ (H) − Lαx′ ,Fn∗ (x′ ),ℓ (H) X 1 ∗ ∗ ∗ ℓ αU (x), bα Hm = m · (x) U , bα Fm (x) U k U ∈([m] k ) X 1 ∗ ∗ ∗ ℓ αU (x), bα Hm (x) U , bα Fm (x) U − n · k U ∈([n] k ) =
1
1
k
k
!
m − n
+
·
X U ∈([n] k )
1
∗ ∗ ∗ ℓ αU (x), bα Hm (x) U , bα Fm (x) U
X
m · k U ∈ [m] \ [n]
( k ) (k)
∗ ∗ ∗ ℓ αU (x), bα Hm (x) U , bα Fm (x) U ,
and since ℓ is bounded and noting that the first term in the above is non-positive (as n ≤ m) while the second is non-negative, we conclude that ′
Lαx,Fm∗ (x),ℓ (H) − Lαx′ ,Fn∗ (x′ ),ℓ (H) (
≤ ∥ℓ∥∞ · max
= 1−
(n)k (m)k
1
n − k
1
!
m k
· ∥ℓ∥∞ . 20
n 1 · , m · k k !
!
m n − k k
!!)
(3.2)
Since we are mostly concerned with the setting in which sSm ≤ o(m) (or equivalently, n = ′ (1 − o(1)) · m), the difference above is small, it will suffice to compare Lµ,F,ℓ (H) with Lαx′ ,F ∗ (x′ ),ℓ (H) n (instead of comparing with Lαx,F ∗ (x),ℓ (H) directly). m Let F0 be the σ-algebra generated by xm−sSm +1 , . . . , xm (i.e., generated by σ ∗ (x)), so H is F0 -measurable. For each i ∈ [m], let Fi be the σ-algebra generated by F0 and (x1 , x2 , . . . , xi ) and ′ def let Zi = E[Lαx′ ,F ∗ (x′ ),ℓ (H) | Fi ]. n We note that (Zi )ni=0 forms a (Doob) martingale with respect to (Fi )ni=0 : h
′
E[Zi+1 | Fi ] = E E Lαx′ ,Fn∗ (x′ ),ℓ (H) Fi+1
i
′
Fi = E Lαx′ ,Fn∗ (x′ ),ℓ (H) Fi = Zi .
We also note that ′
Z0 = E Lαx′ ,Fn∗ (x′ ),ℓ (H) F0 = Lµ,F,ℓ (H),
′
′
Zn = E Lαx′ ,Fn∗ (x′ ),ℓ (H) Fn = Lαx′ ,Fn∗ (x′ ),ℓ (H),
where the former is by linearity of conditional expectation (and the fact that H is F0 -measurable) and the latter is simply because the underlying random variable is Fn -measurable. We will show that Z0 and Zn are close with high (conditional) probability using Azuma’s Inequality. Toward that, let us bound |Zi − Zi−1 | for each i ∈ [n]. By linearity of conditional expectation, we have |Zi − Zi−1 | =
1
X
k
U ∈([n] k )
n ·
∗ ∗ ∗ E ℓ αU (x), bα Hm (x) U , bα Fm (x) U
Fi
∗ ∗ ∗ − E ℓ αU (x), bα Hm (x) U , bα Fm (x) U
!
Fi+1
. (3.3)
We now argue that most of the terms in the above cancel out. Namely, consider a term corresponding to U ∈ [n] such that i ∈ / U , then k
∗ ∗ ∗ ℓ αU (x), bα Hm (x) U , bα Fm (x) U
is independent from xi ; in fact, since (xj )m j=1 is mutually independent, the above is conditionally independent from xi given Fi−1 , so the above gives the same value when conditioned on Fi−1 as it does when conditioned on Fi . Thus, whenever i ∈ / U , the corresponding term in (3.3) cancels out. [n] n−1 As there are exactly k−1 many U ∈ k with i ∈ U , using triangle inequality and the fact that ℓ is bounded, we conclude that |Zi − Zi−1 | ≤
n−1 k k−1 · ∥ℓ∥∞ . n · ∥ℓ∥∞ = n k
We now note that since (m − sSm )k εe = ε − 1 − (m)k def
!
(n)k · ∥ℓ∥∞ = ε − 1 − (m)k
21
· ∥ℓ∥∞ ,
the condition (3.1) implies εe > 0, so by Azuma’s Inequality (conditioned on F0 ), we get
′
Px∼µm Lµ,F,ℓ (H) − Lαx′ ,Fn∗ (x′ ),ℓ (H) ≥ εe = P[Zn − Z0 ≤ −εe] εe2 ≤ exp − Pn 2 · i=1 (k · ∥ℓ∥∞ /n)2 εe2 · n = exp − 2 · k 2 · ∥ℓ∥2∞
!
!
εe2 · (m − sSm ) = exp − . 2 · k 2 · ∥ℓ∥2∞ !
Putting this together with (3.2), we conclude that εe2 · (m − sSm ) − , 2 · k 2 · ∥ℓ∥2∞ !
Px∼µm Lµ,F,ℓ (H) − Lαx,Fn∗ (x),ℓ (H) ≥ ε ≤ exp
as desired. Let us now estimate the above asymptotically when sSm ≤ o(m). First note that (m − sSm )k sS 0≤1− ≤1− 1− m (m)k m
!k
≤ o(1)
as m → ∞ with k fixed. Since we also have m − sSm = (1 − o(1)) · m, we conclude that εe2 · (m − sSm ) exp − 2 · k 2 · ∥ℓ∥2∞
!
(ε − ∥ℓ∥∞ · o(1))2 · (1 − o(1)) · m = exp − 2 · k 2 · ∥ℓ∥2∞
!
ε · (ε + ∥ℓ∥∞ ) ε2 ·m+ · o(m) , ≤ exp − 2 2 2 · k · ∥ℓ∥∞ ∥ℓ∥2∞ !
where the o(m) error term is as m → ∞ with k fixed, is uniform in ε, and has the same uniformity in ∥ℓ∥∞ as the estimate sSm ≤ o(m). The next theorem shows that every k-ary hypothesis class that admits a k-ary compression scheme S of essentially non-trivial quality must be k-PAC learnable. More specifically, a trivial k-ary compression scheme has sSm = m and hSm = 1, which yields ln(hSm ) + sSm · ln(m) = m · ln(m) and our assumption is that we have a k-ary compression scheme in which the quantity above is o(m) instead. The main differences of the next theorem to its partite counterpart, Theorem 2.4, stem from the fact that the bounds of Lemma 3.3 are different from those in Lemma 2.3 and the union bound involves a different number of events. Theorem 3.4. Let Ω = (X, B) and Λ = (Y, B′ ) be non-empty standard Borel spaces with |Y | ≥ 2, let k ∈ N+ , let ℓ : X k × Y Sk × Y Sk → R≥0 be a bounded k-ary loss function and let S be a k-ary compression scheme for a k-ary hypothesis class H ⊆ Fk (Ω, Λ) such that ln(hSm ) + sSm · ln(m) ≤ o(m) 22
(3.4)
as m → ∞ (which in particular follows from bS (m) ≤ o(m/ ln(m)) when Y is finite), then H is k-PAC learnable with respect to ℓ. More specifically, letting A be given by def
A(x, y) = ρSm κSm (x, y)
(m ∈ N, x ∈ X m , y ∈ Y ([m])k )
gives a k-PAC learner for H with respect to ℓ with learning guarantee def mPAC H,ℓ,A (ε, δ) = min
(m − sSm )k ∀m ≥ m0 , 1 − (m)k
(
m0 ∈ N+
!
· ∥ℓ∥∞ < ε
(ε − (1 − (m − sSm )k /(m)k ) · ∥ℓ∥∞ )2 · (m − sSm ) ∧ (m)sSm · hSm · exp − 2 · k 2 · ∥ℓ∥2∞
!
)
≤ δ . (3.5)
In particular, if √
ln(hSm ) + sSm · ln(m) ≤ 1 + o(1) ·
2 · m · ln(m),
(3.6)
as m → ∞, then mPAC H,ℓ,A (ε, δ) ≤
2 · k 2 · ∥ℓ∥2∞
1 + o(1) ·
ε2
· max 1, ln
1 δ
,
where the o(1) error term is as ε → 0 with k fixed, is uniform in δ, and has the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (3.6) provided ∥ℓ∥∞ is bounded away from 0. Proof. Let us start by showing that bS (m) ≤ o(m/ ln(m)) (when Y is finite) implies the condition (3.4) (i.e., ln(hSm ) + sSm · ln(m) ≤ o(m)). Indeed, for m ≥ e, we have ln(hSm ) + sSm · ln(m) ≤ ln(m) · log2 (hSm ) + sSm · log2 |Y | ≤ ln(m) · bS (m) ≤ o(m).
Let us now argue that the minimum in (3.5) indeed exists. For this, we simply need to argue that there exists m0 ∈ N+ satisfying both conditions in the definition of the minimum. But indeed, since we are assuming that (3.4) (i.e., ln(hSm ) + sSm · ln(m) ≤ o(m)) holds, it follows that both (m − sSm )k 1− (m)k (m)sSm · hSm · exp
!
· ∥ℓ∥∞ ,
(ε − (1 − (m − sSm )k /(m)k ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k 2 · ∥ℓ∥2∞
!
tend to 0 as m → ∞ (with all other parameters fixed). So there must exist some m0 ∈ N large enough so that for every m ≥ m0 , the first expression above is less than ε and the second expression above is at most δ. We now prove the result. Let µ ∈ Pr(Ω) be a probability measure and F ∈ Fk (Ω, Λ) be a k-ary hypothesis that is realizable with respect to µ and ℓ. Given ε, δ ∈ (0, 1), let m ≥ mPAC H,ℓ,A (ε, δ) be S an integer, let α be an order choice for [m] and let εe be defined in terms of m, sm , k and ℓ as in Lemma 3.3 and note that since m ≥ mPAC H,ℓ,A (ε, δ), the first condition in the definition of the latter implies that the condition (3.1) of Lemma 3.3 is satisfied. 23
We now pick x at random according to µm and for each σ ∈ ([m])sSm and each η ∈ [hSm ], we let Eσ,η (x) be the event
Lµ,F,ℓ ρSm
σ
∗
∗ x, Fm (x) , η
− Lαx,Fm∗ (x),ℓ
ρSm
σ
∗
∗ x, Fm (x) , η
≥ε
so that Lemma 3.3 says εe2 · (m − sSm ) Px∼µm Eσ,η (x) ≤ exp − . 2 · k 2 · ∥ℓ∥2∞ !
If we let E(x) be the disjunction of the events Eσ,η (x), since there are (m)sSm many such σ and
hSm many such η, by the union bound, we get
εe2 · (m − sSm ) − . 2 · k 2 · ∥ℓ∥2∞ !
Px∼µm E(x)
≤ (m)sSm · hSm · exp
Note also that we have the compression scheme guarantee that Lαx,Fm∗ (x),ℓ
ρSm
∗ κSm x, Fm (x)
=0
∗ (x)) is sample realizable in H with respect to ℓ and α, which happens with whenever (x, Fm probability 1 as F is realizable in H with respect to ℓ. S (x, F ∗ (x)) and the (random) The above along with the fact that the (random) injection σm m S (x, F ∗ (x)) are elements of ([m]) S ], respectively, implies that header ηm and [h sS m m m
∗ Px∼µm Lµ,F,ℓ A x, Fm (x)
"
Lµ,F,ℓ ρSm
= Px∼µm
>ε
∗ κSm x, Fm (x)
#
>ε
≤ Px∼µm E(x)
εe2 · (m − sSm ) ≤ (m)sSm · hSm · exp − 2 · k 2 · ∥ℓ∥2∞ = (m)sSm · hSm · exp
!
(ε − (1 − (m − sSm )k /(m)k ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k 2 · ∥ℓ∥2∞
!
≤ δ, where the last inequality follows since m ≥ mPAC H,ℓ,A (ε, δ) and using the second condition in the definition of the latter. Thus A is a k-PAC learner for H with respect to ℓ. It remains to make the asymptotic estimate of mPAC H,ℓ,A (ε, δ) when the stronger condition (3.6) √ S S (i.e., ln(hm ) + sm · ln(m) ≤ (1 + o(1)) · 2 · m · ln(m)) holds. (It is clear that the condition (3.6) implies the condition (3.4) that ln(hSm ) + sSm · ln(m) ≤ o(m).) Let m1 (ε) ∈ N+ be the least integer such that for every m ≥ m1 (ε), we have (m − sSm )k 1− (m)k 24
!
· ∥ℓ∥∞ < ε
(3.7)
and let m2 (ε, δ) ∈ N+ be the least integer such that for every m ≥ m2 (ε, δ), we have (m)sSm · hSm · exp
(ε − (1 − (m − sSm )k /(m)k ) · ∥ℓ∥∞ )2 · (m − sSm ) − 2 · k 2 · ∥ℓ∥2∞
!
≤ δ.
(3.8)
Since mPAC H,ℓ,A (ε, δ) = max{m1 (ε), m2 (ε, δ)}, it suffices to give asymptotic estimates for m1 (ε) and m2 (ε, δ). To estimate m1 (ε), note that if ∥ℓ∥∞ < ε, then m1 (ε) = k, so suppose that ∥ℓ∥∞ ≥ ε and note that (m − sSm )k sS + k 0≤1− ≤1− 1− m (m)k m ≤ 1 − 1 − 1 + o(1) ·
r
2 m
!k
!k
= 1 + o(1) · k ·
r
(3.9)
2 m
as m → ∞ with k fixed. Plugging this asymptotic estimate in the definition (3.7) of m1 (ε), we conclude that 2 · k 2 · ∥ℓ∥2∞
m1 (ε) ≤ 1 + o(1) ·
ε2
(3.10)
,
where the o(1) error term is as ε → 0 with k fixed, is uniform in δ (as m1 (ε) does not depend on δ at all), and has the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (3.6) provided ∥ℓ∥∞ is bounded away from 0 (this is to cover the case ∥ℓ∥∞ < ε when m1 (ε) = k). To estimate m2 (ε, δ), we use (3.9) along with the condition (3.4) (i.e., ln(hSm )+sSm ·ln(m) ≤ o(m)) to obtain (ε − (1 − (m − sSm )k /(m)k ) · ∥ℓ∥∞ )2 · (m − sSm ) (m)sSm · hSm · exp − 2 · k 2 · ∥ℓ∥2∞ (ε − o(1) · ∥ℓ∥∞ )2 · (1 + o(1)) · m ≤ exp − + o(m) 2 · k 2 · ∥ℓ∥2∞ !
!
!
!
ε2 ≤ exp − − o(1) · m , 2 · k 2 · ∥ℓ∥2∞ where the error terms are as m → ∞ with k fixed, are uniform in ε, and have the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (3.6). Plugging this asymptotic estimate in the definition (3.8) of m2 (ε, δ), we conclude that 2 · k 2 · ∥ℓ∥2 1 + o(1) · ln , 2 ε δ !
m2 (ε, δ) ≤
where the o(1) error term is as ε → 0, is uniform in δ, and has the same uniformity in ∥ℓ∥∞ as the estimate o(1) in (3.6). Putting the estimate above with our estimate for m1 (ε) in (3.10), we get 2 · k 2 · ∥ℓ∥2∞
mPAC H,ℓ,A (ε, δ) ≤ 1 + o(1) ·
ε2
as desired since mPAC H,ℓ,A = max{m1 (ε), m2 (ε, δ)}. 25
· max 1, ln
1 δ
4
Discussion and final remarks
Let us conclude the paper by briefly addressing what was not covered in this work.
4.1
What about the other direction?
First and foremost, in the classical setting, David–Moran–Yehudayoff [DMY16] proved that sample compression is in fact equivalent to PAC learnability3 , that is, given a PAC learner A, one can produce from it a sample compression scheme. In a very high-level, their proof follows by first considering a two-player game over a given sample in which a learner attempts to pick a hypothesis H that is the output of A on a subsample of size mPAC (1/3, 1/3) while a spoiler tries to pick a point of the sample on which H has large loss. The PAC learning guarantee says that if the spoiler plays a mixed strategy first, then the learner can ensure small loss even with a pure strategy playing second. By von Neumann’s Minimax Theorem, there must be a mixed strategy S that the learner can play first that ensures that any pure strategy of the spoiler playing second yields small loss. This then allows us to compress the sample by considering a large enough sample from the mixed strategy S and taking a majority vote. The most natural way to adapt the proof above to high-arity is in the partite setting. However the issue here is that since in high-arity we only allow product distributions over X1 × · · · × Xk , von Neumann’s Minimax Theorem no longer applies (there is no reason to believe that optimal mixed strategies must necessarily come from product distributions). An alternative would be to setup the Minimax as a game with one learner and k spoilers, but even though the corresponding cost function is multilinear in the probability distributions, there is no reason to believe (nor is it a reasonable assumption to make) that we have the correct (quasi-)concavities/convexities. The non-partite setting is even worse: since it requires product distributions, the k spoilers would then have to play the same mixed strategy.
4.2
Approximate/agnostic compression schemes and higher-order variables
In [DMY16], David–Moran–Yehudayoff also defined the notions of approximate and approximate agnostic sample compression schemes. In an approximate compression scheme, instead of assuming that the reconstruction process yields zero loss, one assumes that it gives small loss, that is, for every realizable sample (x, y) of size m, we want Lx,y,ℓ (ρm (κm (x, y))) ≤ εm where εm > 0 (and typically thought to satisfy εm → 0 as m → ∞). For approximate agnostic compression schemes, one drops the realizability assumption but requires instead that the reconstruction is competitive in the sense that Lx,y,ℓ (ρm (κm (x, y))) ≤ inf Lx,y,ℓ (H) + εm . H∈H
As was observed in [DMY16], the fact that (agnostic, respectively) PAC learnability implies approximate (agnostic, respectively) sample compressibility is very simple: one simply considers the uniform measure on the sample, uses the PAC guarantee to claim that there exists a small subsample that when fed to the algorithm yields small loss (or is competitive in the agnostic case), then uses a bit of extra information to encode potential repetitions. In the other direction, the 3 Their proof is when Y = {0, 1} and with 0/1-loss, but it readily adapts to the case when Y is finite and ℓ is separated in the sense that it assigns 0 penalty to correct guesses and is bounded away from 0 in incorrect guesses.
26
argument that sample compressibility implies PAC learnability easily adapts to the approximate (agnostic) case. Of course, the definitions of approximate and approximate agnostic sample compressibility readily adapt to the high-arity setting (both partite and non-partite). It is straightforward to check that the proof of equivalence between approximate sample compressibility and PAC learnability lifts to the high-arity case (both partite and non-partite). In the remainder of this section, we sketch the equivalence of the agnostic case. First, what is high-arity agnostic PAC learnability? In the definition of [CM24] and in analogy with classical PAC theory, there are two changes: the adversary is allowed to play an “agnostic” distribution and the learner is only tasked with being competitive. The key technicality is in what an “agnostic” distribution is. In the non-partite, the adversary k N N picks a distribution ν over X1 + × · · · × Xk + × Y N+ (we want to think of elements of this set as infinite k-dimensional tensors with names on each of the indices) that satisfies: Separately exchangeability in the sense that ν is invariant under the natural right-action of N SNk + (the ith copy of SN+ permutes the coordinates of Xi + and SNk + as a whole permutes the coordinates of Y N+ ). Locality in the sense that marginals on U1 × · · · × Uk and V1 × · · · × Vk are independent provided Ui ∩ Vi = ∅ for every i ∈ [k]. A labeled m sample is then generated by taking the marginal of ν on [m]k . In the non-partite, the adversary picks a distribution ν over (X N+ )k × Y (N+ )k that satisfies: (Joint) Exchangeability in the sense that ν is invariant under the natural right-action of SN+ . Locality in the sense that marginals on U k and V k are independent provided U ∩ V = ∅. A labeled m sample is then generated by taking the marginal of ν on [m]k . One then gets a handle on these distributions by invoking the Aldous–Hoover Theorem [Hoo79, Ald85, Ald81] from exchangeability theory (see also [Kal05, §7] for a more modern presentation) to get a normal representation of such distributions. Without getting into the (highly) technical details, let us mention that the proof presented here readily adapts to this more general setting simply because using this Aldous–Hoover representation, one can check that the martingales defined in the proofs remain martingales (with the same bounds on martingale differences), which allow the key application of (two-sided) Azuma’s Inequality. In fact, similar martingales and an application of Azuma’s Inequality were used in [CM24, Lemma 7.3].
References [AFN07] Noga Alon, Eldar Fischer, and Ilan Newman. Efficient testing of bipartite graphs for forbidden induced subgraphs. SIAM J. Comput., 37(3):959–976, 2007. [Ald81]
David J. Aldous. Representations for partially exchangeable arrays of random variables. J. Multivariate Anal., 11(4):581–598, 1981.
[Ald85]
David J. Aldous. Exchangeability and related topics. In École d’été de probabilités de Saint-Flour, XIII—1983, volume 1117 of Lecture Notes in Math., pages 1–198. Springer, Berlin, 1985. 27
[CM24]
Leonardo N. Coregliano and Maryanthe Malliaris. High-arity PAC learning via exchangeability, 2024.
[CM25a] Leonardo N. Coregliano and Maryanthe Malliaris. A packing lemma for VCNk -dimension and learning high-dimensional data, 2025. [CM25b] Leonardo N. Coregliano and Maryanthe Malliaris. Sample completion, structured correlation, and Netflix problems, 2025. [CPT19] Artem Chernikov, Daniel Palacin, and Kota Takeuchi. On n-dependence. Notre Dame J. Form. Log., 60(2):195–214, 2019. [CT20]
Artem Chernikov and Henry Towsner. Hypergraph regularity and higher arity VCdimension, 2020.
[DMY16] Ofir David, Shay Moran, and Amir Yehudayoff. On statistical learning via the lens of compression, 2016. [FPS19]
Jacob Fox, János Pach, and Andrew Suk. Erdős-Hajnal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom., 61(4):809–829, 2019.
[GSW25] Lior Gishboliner, Asaf Shapira, and Yuval Wigderson. Is it easy to regularize a hypergraph with easy links?, 2025. arXiv:2506.15582. [Hau95]
David Haussler. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension. J. Combin. Theory Ser. A, 69(2):217–232, 1995.
[HMS26] Ron Holzman, Shay Moran, and Alexander Shlimovich. Uniform laws of large numbers in product spaces, 2026. [Hoo79]
D. N. Hoover. Relations on probability spaces and arrays of random variables. Preprint, Institute of Advanced Study, Princeton, NJ, 1979.
[Kal05]
Olav Kallenberg. Probabilistic symmetries and invariance principles. Probability and its Applications (New York). Springer, New York, 2005.
[Kob15]
Munehiro Kobayashi. A generalization of the pac learning in product probability spaces (model theoretic aspects of the notion of independence and dimension). Model theoretic aspects of the notion of independence and dimension, 1938:33–37, 04 2015.
[KT15]
Takayuki Kuriyama and Kota Takeuchi. On the PACn learning. Model theoretic aspects of the notion of independence and dimension, 1938:54–58, 2015.
[LM19a]
Roi Livni and Yishay Mansour. Graph-based discriminators: Sample complexity and expressiveness, 2019.
[LM19b] Roi Livni and Yishay Mansour. Graph-based discriminators: Sample complexity and expressiveness. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
28
[LS10]
László Lovász and Balázs Szegedy. Regularity partitions and the topology of graphons. In An irregular mind, volume 21 of Bolyai Soc. Math. Stud., pages 415–446. János Bolyai Math. Soc., Budapest, 2010.
[LW86]
Nick Littlestone and Manfred Warmuth. Relating data compression and learnability. Unpublished, 1986.
[MY16]
Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. J. ACM, 63(3):Art. 21, 10, 2016.
[Per72]
Micha Perles. Credited by Shelah in 1972, 1972.
[Sau72]
Norbert Sauer. On the density of families of sets. J. Combinatorial Theory Ser. A, 13:145–147, 1972.
[She72]
Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247–261, 1972.
[She14]
Saharon Shelah. Strongly dependent theories. Israel J. Math., 204(1):1–83, 2014.
[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. [Ter24a]
Caroline Terry. Growth of regular partitions 1: Improved bounds for small slicewise VC-dimension, 2024. arXiv:2404.01274.
[Ter24b]
Caroline Terry. Growth of regular partitions 2: Weak regularity, 2024.
[TW22]
Caroline Terry and Julia Wolf. Irregular triads in 3-uniform hypergraphs, 2022.
29