Distribution-free PAC learning. In PAC learning [Val84], the learner is given labeled examples (x, f (x)) where f is an unknown target function and x is distributed according to an unknown distribution D. While f is assumed to belong to a known concept class C, no assumptions are made about D. This distribution-free aspect of the model is a notable strength: the guarantees of a PAC learning algorithm hold for all distributions, regardless of how simple or complicated they may be.
On the other hand, it is also this very aspect of the model that has skewed the balance between positive and negative results heavily towards the latter. Indeed, the introduction of the model quickly led to a flurry of works (e.g. [KLPV87, PV88, LV88, PW88, BR88, Han89, PW89, KV89] ...) showing that even simple concept classes C can be computationally hard to learn. The unifying idea across all such results is that many canonical hard problems-from factoring to NP-complete problems-can, roughly speaking, be embedded within the distribution D. This therefore shows that the simplicity of C can be negated by the complexity of D.
Distribution-specific PAC learning. This suggests the distribution-specific variant of PAC learning where the underlying distribution D is fixed, known, and "nice". Kearns, Li, Pitt, and Valiant [KLPV87] were the first to consider this setting, citing it as a way of circumventing the hardness of distribution-free learning. Other early works include [BI91,Nat92].
Allowing for distributional assumptions has indeed led to a bounty of positive results, with most of them assuming that D belongs to the class D prod of product distributions. We now have fast product-distribution learners for basic classes such as DNF formulas [Ver90, Jac97, GKK08] and intersections of halfspaces [KOS04,Kan14]. These contrast with the strong lower bounds that have been shown for these classes in the distribution-free setting [KS07, KS09,RS10,She10,She13]. The connection between product-distribution learning and the Fourier analysis of boolean functions has given us general and powerful techniques for designing learners [LMN93,KM93]. Notably, these techniques extend to the agnostic setting [KSS94, GKK08, KKMS08], yielding fast and noise-tolerant learners for many expressive classes. This again contrasts with the distribution-free setting where even the agnostic learning of disjunctions is well-known to be a difficult open problem.
The main caveat that comes with product-distribution learners is, of course, that the assumption of independence is a strong and stylized one. Much of the richness and complexity of real-world data distributions come from the correlations among features. Therefore, while product-distribution PAC learning has become an important area of study within theoretical computer science, it admittedly departs from Valiant's original intention for the PAC model to serve as a theoretical framework for machine learning.
The two extremes of distributional assumptions. Summarizing, much of the work in PAC learning has focused on two extremes in terms of distributional assumptions. At one extreme we have distribution-free PAC learning where no assumptions are made about the underlying distribution. Algorithms in this setting come with an extremely strong guarantee, but obtaining such algorithms has been correspondingly challenging. At the other extreme we have distribution-specific PAC learning. This setting has enjoyed algorithmic success in the form of fast algorithms and sophisticated techniques, but at the price of a strong, arguably unrealistic, distributional assumption. Research on these settings has resulted in two large and mostly separate islands of work.
1.1 Prior work of [BLMT23] Interpolating between the extremes via distributional lifting. Towards addressing this, recent work of Blanc, Lange, Malik, and Tan [BLMT23] proposed the possibility of interpolating between uniform-distribution learning, the simplest case of product-distribution learning, and distribution-free learning. Their motivation was twofold. First, if the distribution-free setting is overly demanding and the assumption of independence is overly strong, perhaps we should search for fruitful middle grounds that allow for efficient algorithms whose guarantees hold for limited yet still broad classes of distributions. Second, just as PAC learning has benefited from the study of function complexity-under the hood of every new PAC learning algorithm are new insights about the structure of functions in the concept class-perhaps it could also benefit from the equally large literature on distributional complexity.
[BLMT23] instantiated this proposal with decision tree complexity as the interpolating notion of distributional complexity. The decision tree complexity of a distribution D ⋆ over {±1} n is the smallest integer d such that D ⋆ can be decomposed into a depth-d decision tree of uniform pieces. This is therefore a complexity measure that indeed interpolates between the uniform distribution (d = 0) and the class of all distributions (d = n). Small depth decision tree distributions were first considered by Feldman, O'Donnell, and Servedio [FOS08] in the context of distribution learning. Such distributions generalize junta distributions [ABR16] and are in turn a special case of mixtures of subcubes [CM19] and mixtures of product distributions [FM99,Cry99,CGG01,FOS08].
[BLMT23]'s main result is a distributional-lifting theorem that transforms, in a blackbox fashion, a uniform-distribution learner into one that works for any distribution D ⋆ , with an overhead the scales with the decision tree complexity of D ⋆ :
[BLMT23]'s lifter. Let C be a concept class over {±1} n that is closed under restrictions. Suppose there is an algorithm that learns C under the uniform distribution in poly(n) time. There is an algorithm that, given a conditional sample oracle to any depth-d decision tree distribution D ⋆ , learns
The conditional sample oracle [CRS15, BC18, CCK + 21, CJLW21] allows the learner to specify any subset S ⊆ {±1} n and receive unlabeled samples drawn from the conditional distribution of D ⋆ over S. We will soon say more about this oracle. Setting it aside for now, we note that the n O(d) runtime of [BLMT23]'s lifted learner indeed scales with the inherent complexity of D * , retaining the base learner's poly(n) runtime for constant d, and remaining subexponential for d as large as Θ(n 0.99 ). On a more technical level, their result carries the appealing message that the large technical toolkit for uniform-distribution learning-all of which relies crucially on the assumption of independence among features-now have implications on settings where distributions have highly-correlated features.
1. The conditional sample oracle is a strong form of access not afforded by the standard PAC model. In fact, [BLMT23]'s lifter uses this oracle with a near-maximal "amount of conditioning": it requests for samples of D ⋆ conditioned on sets S of constant size, allowing it to receive samples that are extremely unlikely under D ⋆ itself. This is a serious downside as the lifted learner now has active control over the samples that it receives, allowing it to "home in" on small and specific parts of the distribution. The assumption of uniformity is therefore traded for what is arguably an equally unrealistic assumption that the learner has access to such an oracle. Put differently, their result does not perform distributional lifting within the PAC model: it takes a random-example PAC learner and lifts it to one that is no longer a random-example PAC learner.foot_0
2. Their lifter only lifts uniform-distribution base learners. Notably, as we explain in the body of the paper, their lifter is unable to even lift product-distribution base learners. (It is easy to see that most product distributions require the maxmimal decision tree depth n to decompose into uniform pieces.) This is especially unfortunate since the analyses of uniformdistribution learners tend to extend straightfowardly, sometimes even in a blackbox fashion, to the setting of general product distributions. In particular, Fourier-based uniform-distribution learners all have product-distribution analogues.
Ideally, one would like to lift base learners for an arbitrary class D of distributions into one that succeeds under any distribution D ⋆ , with an overhead that scales with the complexity of expressing D ⋆ as a decision tree of distributions in D. 3. Their lifter does not preserve the noise tolerance of learners. That is, even if the base learners are noise-tolerant, the resulting lifted learner is not guaranteed to be. This is again unfortunate, given the large literature on noise-tolerant learning under product distributions and other distribution-specific settings.
Our main result is a new lifter that addresses all three downsides: Theorem 1 (Informal; see Theorem 2 for the formal version). Let C be a concept class and D be a family of distributions over {±1} n that is closed under restrictions. Suppose there is an algorithm A that learns C under any D ∈ D in poly(n) time.
There is an algorithm that, for any D ⋆ that admits a depth-d decomposition into distributions in D, learns C under D ⋆ in n O(d) time and with 2 O(d) • poly(n) samples. Furthermore, if the base learner A is noise tolerant, then so is the lifted learner.
Overcoming an impossibility result. Our approach to obtaining Theorem 1 is entirely different from [BLMT23]'s-necessarily so, as we now explain. Drawing on ideas from semi-supervised learning, [BLMT23] advocated for a two-step approach to distributional-lifting:
Step 1: Learn the decision tree decomposition of D ⋆ into uniform pieces.
Step 2: Exploit this knowledge of the decomposition to lift.
The bulk of their work goes into designing an algorithm for Step 1-with the decomposition in hand, a lifter follows quite straightforwardly. It is also Step 1 for which they use the conditional sample oracle, and in their paper they pointed to several aspects of their algorithm for which the oracle is necessary.
The starting point of our work is an impossibility result (Theorem 5) for the whole two-step approach: We show, via a reduction to uniformity testing, that it is information-theoretically impossible to carry out the first step using only random examples. The novelty of our work is therefore a lifter that, by necessity, sidesteps the need to learn D ⋆ . While the main conceptual message of [BLMT23]'s work is that techniques from distributional learning can be useful for the distributional lifting of PAC learners, our work provides the complementary message that an algorithm for the former is not a prerequisite for the latter.
We prove this impossibility result in Section 8, where we also explain why [BLMT23]'s approach leads to the the second and third downsides listed above.
Additional advantages of Theorem 1. In addition to addressing these downsides, our new approach comes with a couple of additional advantages:
1. Improved sample complexity. The sample complexity of our lifted learner is 2 O(d) • poly(n), a substantial improvement over [BLMT23]'s n O(d) . In particular, our sample complexity remains poly(n) for d = Θ(log n) whereas theirs becomes superpoly(n) for any d = ω(1).
Handles general subcube partitions. We are able to handle a complexity measure that is significantly more expressive than decision tree depth. A depth-d decision tree induces a partition of {±1} n into subcubes of codimension d, but the converse is not true: a partition of {±1} n into subcubes of codimension d may not be realized by a decision tree. Furthermore, we only require that the subcubes of codimension d partition supp(D ⋆ ) instead of all of {±1} n . See Figure 2.
As we note in Section 5, there is an exponential separation in the expressiveness of these measures. It is easy to construct distributions D ⋆ whose support can be partitioned into uniform distributions over subcubes of codimension d, and yet any decision tree decomposition of D ⋆ into uniform pieces requires depth 2 Ω(d/ log d) .
[BLMT22]'s lifter appears to rely quite crucially on the hierarchical structure of the partitions induced by a decision tree. Our analysis, on the other hand, extends to handle subcube partitions with the same performance guarantees. This extension requires a few additional ideas beyond those that go into Theorem 1; we describe them in Section 3.
The work of [BOW10]. While [BLMT23] was the first to explicitly study distributional lifting of PAC learners, the general idea dates back (at least) to the work of Blais, O'Donnell, and Wimmer [BOW10]. The main result of their paper was an efficient algorithm for performing polynomial regression under product distributions. As an application, they observed that their algorithm can be used as a base learner in conjunction with a distributional learning algorithm of Feldman, O'Donnell, and Servedio [FOS08] for learning mixtures of product distributions. Like [BLMT23], [BOW10]'s observation is based on a two-stage approach of first learning the marginal distribution and then exploiting this information to learn the target function. (This general approach is ubiquitous in semi-supervised learning; see e.g. [GBDB + 19] and the references therein.) As discussed, the crux of our work is in departing from such an approach.
Composition theorems in PAC learning. Distributional-lifting theorems may be viewed as the distributional analogue of composition theorems in PAC learning [KLPV87, PW90, AKMW96, BDBK97, Bsh98, BM06]. At a high level, these theorems show how learning algorithms for a concept class C (or a family of concept classes) can be generically lifted to give learning algorithms for larger concept classes.
As mentioned, obtaining a distributional-lifting theorem that uses only random examples necessitates an approach that is different from [BLMT23]'s. Since the challenges are evident even in their specific setting of lifting uniform-distribution learners, in this overview we specialize our discussion to that setting. Our approach also extends rather easily from that setting to that of lifting from arbitrary distribution families, so this overview captures the essential ideas.
We briefly describe [BLMT23]'s two-stage approach while also introducing notation that will be useful for describing and contrasting our approach. Suppose D ⋆ admits a decomposition into a small-depth decision tree T ⋆ of uniform pieces. Let us denote this as D = T ⋆ • unif. [BLMT23] first uses the conditional sample oracle to learn D ⋆ , i.e. find a hypothesis tree T such that dist TV (T •unif, T ⋆ •unif) is small: [BLMT23]'s lifter: Learning the decision tree decomposition With T in hand, they draw a training set S from D ⋆ . This tree T induces a natural partition of S into S = S 1 ⊔ • • • ⊔ S s where s is the number of leaves in T . They then run the base learner A on S 1 , . . . , S s parts to obtain high-accuracy hypotheses h 1 , h 2 , . . . , h s . Their final lifted hypothesis will be T composed with h 1 , h 2 , . . . , h s : Let us denote this hypothesis as H := T • (h 1 , . . . , h s ). It is straightforward to see that, with an appropriate choice of parameters, H will w.h.p. be a high-accuracy hypothesis for the target function f with respect to D ⋆ . The simple but crucial fact here is that if S is drawn according to D ⋆ , then each of the induced parts S 1 , . . . , S s will be distributed near-uniformly. We will return to this point in Section 3.3.
We know that we cannot hope to learn the decomposition of D ⋆ from random examples only. Our approach is therefore more direct in nature, by necessity: Rather than first searching for a tree T that is a good approximation of T ⋆ and then running the base learner A on the partition induced by T , we will search directly for a tree T such that running A on the partition induced by T yields a lifted hypothesis that is close to the target function. Indeed, this seems like such a direct approach would even result in an algorithm that is simpler than [BLMT23]'s.
However, the fact that T may not be a good approximation of T ⋆ , i.e. that T may not satisfy the property depicted in Figure 3, poses difficulties for the analysis. To illustrate these difficulties, consider the following candidate algorithm (which is much simpler than [BLMT23]'s):
2. Search for a tree T such that A returns high-accuracy hypotheses h 1 , . . . , h s when run on each of the parts in the partition S = S 1 ⊔ • • • ⊔ S s induced by T .
Note that the search criterion for T here is indeed laxer than that of [BLMT23]'s:
. . , S s will therefore be distributed near-uniformly and A will return high-accuracy hypotheses when run on them.
̸ ⇐ Just because A returns high-accuracy hypotheses when run on S 1 , . . . , S s does not imply that they are distributed near-uniformly. The base learner A is guaranteed to succeed when run on data drawn from near-uniform distributions, but it could also succeed on data drawn from distributions that are far from uniform.
The issue: Having to run A on distributions we have no guarantees for. When we say that "A returns a high-accuracy hypothesis when run on S i " above, we mean a hypothesis with high accuracy as measured according to S i , i.e. one that achieves high training accuracy. We would be done if we were then able to infer that this hypothesis also achieves high true accuracy, i.e. accuracy as measured according to D ⋆ . [BLMT23] are able to make this inference since they are running A on near-uniform distributions for which its performance guarantees hold: As long as the size of S i is at least the sample complexity of A, its training error will be close to its true error-its hypothesis will generalize. However, in our case we may be running A on data drawn from distributions that are far from uniform, for which its guarantees no longer hold. Indeed, given our impossibility result we know that we will be running A on such data-otherwise, we would have learned the decomposition of D ⋆ , which we have shown is impossible. When this happens, we do not have any bound on the number of samples sufficient for generalization.
Our actual lifter remains almost as simple as the first attempt:
Our actual lifter 1. Draw independent sets S train and S test of random examples from D ⋆ .
2. For each candidate tree T , let h 1 , . . . , h s denote the hypotheses returned by A when run on the parts in the partition
3. Return the lifted hypothesis H = T • (h 1 , . . . , h s ) with the highest accuracy on S test .
We implement this lifter in a way that avoids exhaustively searching through the roughly n 2 d candidate depth-d trees over n variables, and instead runs in n O(d) time (see Section 6.1).
Overview of our analysis. Rather than showing that each of the hypotheses of A generalizes (as [BLMT23] does), we directly show that our lifted hypothesis H generalizes. To describe our analysis, we need to be more explicit about how our lifter depends on the samples it draws: For a tree T and a set S of samples, we write T S to denote T • (h 1 , . . . , h s ) where h 1 , . . . , h s are the hypotheses that A returns when run on the parts in the partition of S induced by T .
There are three components to our analysis:
1. Our hypothesis minimizes test loss: By definition, our lifter returns the hypothesis T S train that minimizes test loss, error(T S train , S test ).
The true tree T ⋆ induces a partition of S train into parts that are each near-uniformly distributed. If each of these parts is sufficiently large-at least m, the sample complexity of A-the hypotheses returned by A will generalize. Therefore, as long as S train is sufficiently large, T ⋆ S train will have low true loss, error(T ⋆ S train , D ⋆ ).
3. Test loss ≈ true loss: Finally, we show that if S test is sufficiently large, the test loss will be close to the true loss:
Applying this twice, once to T S train and once to T ⋆ S train , yields the desired conclusion that our lifted hypothesis achieves low true loss.
Since we would like to apply this to T S train where T is not guaranteed to partition S train into near-uniform pieces, we cannot rely on the sample complexity guarantee of A to reason about how large S test has to be. To get around this, we use the fact that each tree T determines A's behavior on the partitions it induces. Our analysis in fact shows that S test 's size actually only needs to depend on the number of possible trees, not on A's sample complexity.
We remark that this approach of using a training set to build a "cover" guaranteed to have at least one good hypothesis, and a test set to select the best hypothesis is fairly standard; see e.g. [HKLM22] and the references therein. The key innovation in our setting is, for the particular cover we build, we are able to search for the best hypothesis in a computationally efficient manner.
Our approach can handle distributions that decompose into subcubes but do not have the hierarchical structure of a decision tree. In this setting, we assume that the support of D can be decomposed into s disjoint subcubes, each of codimension ≤ d, such that the distribution over each subcube is in the base distribution family (see Definition 10). The high-level structure of our algorithm is similar to the decision tree lifter described in Section 3.3.
Our lifter for subcube partitions 1. Draw independent sets S train and S test of random examples from D ⋆ .
A on all possible subcubes of codimension ≤ d, returning a hypothesis for each.
3. Run the approximation algorithm described in Lemma 3.1 to find a hypothesis with low test error.
New technical ingredients for this setting. However, the decision tree setting provides a convenience we cannot use in the subcube partitions setting: the existence of a n O(d) -time recursive search process that minimizes test loss over all depth-d candidate trees. Without this nice bit of structure, it is not clear that one can do any better than enumerating all ≈ n d s possible subcube partitions. In Lemma 3.1, we circumvent this issue by relaxing the problem in the following ways:
• A more expressive hypothesis: Though our assumption is that the distribution has a ground-truth subcube partition, we return a global hypothesis where the individual subcube hypotheses are not indexed by a subcube partition; rather, an ordered list of subcubes such that each x ∈ {±1} n maps to the first subcube in the list consistent with it.This "list hypothesis" need not have subcubes that are disjoint, and it also may be of length up to s log(1/ε) rather than s.
• Approximate test error minimization: On each restriction, we run A on S train to error ε log(1/ε) . This means that the ground truth partition would have true loss ε log(1/ε) , however, we return a hypothesis of true loss ε.
With these relaxations, we are able to prove the following.
There is an efficient algorithm that takes as input a test set S test and hypotheses h ρ for every restriction |ρ| ≤ d with the following guarantee: If there is size-s subcube partition P := (ρ 1 , . . . , ρ s ) for which P • (h ρ 1 , . . . , h ρs ) has test error at most ε, then the algorithm returns a size-(k
The algorithm in Lemma 3.1 uses a greedy approach inspired by the classical approximation algorithm for set cover. We show, at each step, there is a restriction that can be added to L that simultaneously covers a large portion of the remaining test examples and has small test error.
The data that a PAC learner receives is jointly determined by the unknown target function f and the unknown distribution D. However, its performance guarantees are allowed to scale with the complexity of f -for example, we seek poly(n, s)-time algorithms for learning size-s boolean circuits over n variables-but usually not with the complexity of D. On one hand, this seems reasonable since it has long been known that the sample complexity of learning is determined by the complexity of f (i.e. the VC dimension of the concept class that f belongs to) and suffices for all distributions. On the other hand, given the apparent difficulty of obtaining computationally-efficient learners even for simple concept classes, perhaps the computational complexity of learning depends jointly on the complexity of f and the complexity of D for most learning tasks. Our work contributes to the understanding of this phenomenon by giving a general method for designing efficient learners that succeed for natural notions of "sufficiently simple" distributions, but there is much more to be done.
For example, the focus of our work is mostly algorithmic in nature. An avenue for future work is to study these questions from the perspective of lower bounds. As mentioned in the introduction, the long list of lower bounds for distribution-free PAC learning shows that canonical hard problems from complexity theory and cryptography can be embedded in underlying distribution D, thereby negating the assumed simplicity of the target function f . Can we formalize and quantify this? For each concept class for which there are distribution-free lower bounds, can we show that these lower bounds in fact hold for distributions D that are "complicated" in a certain formal sense? Such an understanding will in turn suggest ways in which these lower bounds can be circumvented, and pave the way to efficient algorithms for learning these concept classes under restricted but still broad classes of distributions.
Notation. We use boldfont to denote random variables and calligraphic font to denote distributions (e.g. x ∼ D). For any set S, we use x ∼ S as shorthand for x sampled uniformly from S. The support of a distribution D denotes all points with nonzero probability mass. We write [n] as shorthand for the set {1, 2, . . . , n}. For any function f : {±1} n → {±1} and distribution D over {±1}, we use D f as shorthand for the distribution of (x, f (x)) where x ∼ D.
Definition 1 (Total variation distance). For any distributions D 1 and D 2 over the same finite domain X, the total variation distance between D 1 and D 2 is defined as,
where D(x) denotes the probability mass function of D evaluated at x.
Learning theory basics. We operate in the distribution-specific model of PAC learning. First, we define the error of a hypothesis.
Definition 2 (Error of a hypothesis). For any distribution D over {±1} n × {±1} and hypothesis h : {±1} n → {±1}, we define,
In a slight abuse of notation, for any S ∈ {±1} n × {±1}, we similarly define.
error(h, S) := Pr
Definition 3 (Distribution-specific PAC learning). For any ε, δ > 0, we say a learner A (ε, δ)-learns a concept class C over distribution D if the following holds: For any f ∈ C, given iid samples from D f , with probability at least 1 -δ, A returns a hypothesis h with error(h, D f ) ≤ ε.
To simplify analysis and notation, we will drop the dependence on the failure probability and focus only on the expected accuracy.
Definition 4 (PAC learning with expected error). For any ε > 0, we say a learner A ε-learns a concept class C over distribution D if the following holds: For any f ∈ C, given iid samples from D f , the hypothesis h that A returns satisfies
where the randomness of h is over the randomness of the sample and A.
It is possible to generically convert expected error learners to those that succeed with very high probability.
Fact 5.1 (Boosting success probability, folklore). For any ε, δ > 0 and efficient learner A using m samples, there is an efficient learner A ′ using
with the following guarantee: If A ε-learns a concept class C over distribution D (in expected error), then A ′ (2ε, δ)-learns C over distribution D.
The proof of Fact 5.1 is simple: A ′ runs O(log(1/δ)) independent copies of A. With very high probability, at least one will have low error. It then uses a test set to determine which hypothesis has the lowest error.
With slightly more cumbersome notation, our results can be directly proven for (ε, δ)-learning. Given Fact 5.1, our focus on expected error learning is without loss of generality and simplifies notation.
Restrictions. To formalize our lifters, we will use the concept of a restriction, which gives a convenient way of specifying a subcube of the domain.
Definition 5 (Restrictions). For the domain {±1} n , a restriction is specified by a string ρ ∈ {±1, ⋆} n . An input x ∈ {±1} n is consistent with ρ, denoted x ∈ ρ, if
The depth of ρ, denoted depth(ρ), is the number of i ∈ [n] for which ρ i ̸ = ⋆.
For any i ∈ [n] and b ∈ {±1}, we use x i = b as shorthand for the depth-1 restriction ρ where ρ i = b and for all j ̸ = i, ρ j = ⋆. Similarly, for any restriction ρ where ρ i = ⋆, we use ρ ′ := ρ∩(x i = b) to denote the restriction satisfying ρ ′ i = b and for all j ̸ = i, ρ ′ j = ρ j . We extend the notation of restrictions to sets and distributions. For any S ⊆ {±1} n , we define,
Similarly, for any distribution D over {±1} n , we use D ρ to denote the distribution of x ∼ D conditioned on x ∈ ρ.
In a slight abuse of notation, we will also extend this notation to labeled sets and distributions over {±1} n × {±1}. For any S ⊆ {±1} n × {±1}, we define,
Similarly, for a distribution D over {±1} n × {±1}, we use D ρ to denote the distribution of (x, y) ∼ D conditioned on x ∈ ρ.
As an example of combining this notation, let D be a distribution on {±1} n and f : {±1} n → {±1} be some function. Then notation (D f ) x i =1 denotes the distribution of (x, f (x)) when x ∼ D conditioned on x i = 1.
Our lifters will assume that the family of base distributions is closed under restrictions.
Definition 6 (Closed under restrictions). A family of distributions, D, is closed under restrictions if for any D ∈ D and any restriction ρ, D ρ ∈ D.
For example, the family of product distributions is closed under restrictions. Even when a family of distributions is not already closed under restrictions, this assumption is mild. Typically, it is only easier to learn over D ρ than D, so learners that succeed over some D typically succeed over all restrictions of D.
Decomposed distributions. The main focus of this work is to learn over a distribution D ⋆ which can be decomposed into simpler distributions contained within some family of distributions, D. We define two related ways of decomposition distributions, one based on decision trees and one based on subcube covers. We view a depth-d decision tree as a collection of 2 d restrictions, with each restriction denoting the portion of the domain {±1} n that reaches a single leaf.
Definition 7 (Decision trees). For any 0 ≤ d ≤ n, a depth-d decision tree T over domain {±1} n is a collection of 2 d leaf restrictions defined recursively:
T is defined by a root query i ∈ [n] and two subtrees T x i =-1 and T x i =+1 with the property ℓ i = ⋆ for every ℓ ∈ T x i =-1 ∪ T x i =1 . It contains the restrictions,
Definition 8 (Decomposition distributions via decision trees). For a family of distributions D over {±1} n , we say that a distribution D ⋆ has a depth-d decomposition into distributions in D if there is some depth-d decision tree T for which (D ⋆ ) ℓ ∈ D for every ℓ ∈ T .
We similarly decompose distributions into subcube partitions. Note that we do not require our partition to cover the entire domain {±1} n . Eventually, when we apply these covers in Definition 10, we will require the partitions to cover the support of the distribution D ⋆ , which may not be all of {±1} n . Definition 9 (Subcube partitions). A size-s depth-d subcube partition is a collection of s restrictions, P := (ρ (1) , . . . , ρ (s) ), with the following properties.
• Disjointness: For every i ̸ = j ∈ [s], there is no x ∈ {±1} n for which x ∈ ρ (i) and x ∈ ρ (j) .
• Codimension d: For every i ∈ [s], the number of j ∈ [n] for which (ρ (i) ) j ̸ = ⋆ is at most d.
Definition 10 (Decomposing distributions via subcube partitions). For a family of distributions D over {±1} n , we say that a distribution D ⋆ has a depth-d size-s subcube decomposition into distributions in D if there is some size-s depth-d subcube partition P satisfying,
• Coverage: For every x in the support of D ⋆ , there is some ρ ∈ P for which x ∈ ρ.
• Valid decomposition: (D ⋆ ) ρ ∈ D for every ρ ∈ P .
It's straightforward to see that if D ⋆ has a depth-d decomposition into distributions in D (by decision trees), it has a depth-d size-2 d subcube decomposition into distributions in D, but the converse is not true: There are depth-O(log n) size-O(n) subcube decompositions that require a depth-Ω(n) decomposition by decision trees. Therefore, our lifter for subcube covers can handle a much more expressive class of distributions.foot_1 6 Our lifter for decision tree decompositions and its analysis Theorem 2 (Our lifter for decision tree decompositions). Let C be a concept class and D be a class of distributions that is closed under restrictions. Let A be a base learner that uses t time and m samples to learn C to expected error ≤ ε under any distribution D ∈ D. Then, for
there is a t ′ -time m ′ -sample algorithm that learns C to expected error ε under any distribution D ⋆ that has a depth-d decomposition into distributions in D.
The definition of a depth-d decomposition, given informally in the introduction, is detailed in Definition 8. The algorithm used in the proof of Theorem 2 is the algorithm TreeLearn A , described in Figure 5. We further show the noise tolerance of this algorithm in Theorem 3.
In that algorithm, we use notation to compose a decision tree with hypotheses:
Definition 11 (Decision tree composed hypotheses). For any decision tree T and mapping H from restrictions to hypotheses, we use T • H to denote the function that, on input x, finds the unique leaf ρ ∈ T for which x ∈ ρ and outputs H(ρ)(x).
We analyze TreeLearn A 's time complexity in Section 6.1, and then prove its correctness and analyze its sample complexity Section 6.2. We analyze its noise tolerance in Section 6.3. Training phase: For every depth-d restriction ρ ∈ {±1, ⋆} n , set h ρ ← A((S train ) ρ ). Let H denote the mapping from ρ to h ρ .
Test phase: Let T ← FindTree(S test , d, H, ρ all ), where (ρ all ) i = ⋆ for all i ∈ [n], be the decision tree minimizing error(T • H, S test ). Return H := T • H.
• Combine trees: Let T (i) be the tree with x i at the root and T x i =-1 and T x i =1 as its left and subtrees respectively.
3. Return the T (i) the minimizes error(T (i) , (S test ) ρ ) among i ∈ ρ -1 (⋆).
Figure 5: The lifting algorithm with the guarantees in Theorem 2. TreeLearn terminates in time,
Proof. In the training phase, TreeLearn one call to A for each of the n O(d) depth-d restrictions ρ.
For each such restriction, TreeLearn needs to filter the size m train dataset to just those samples that are consistent with ρ and make a call to A. The total time for this is easily upper bounded by n O(d) • (m train t).
In the test phase, we observe that FindTree makes a total of 1 + 2n + (2n
recursive calls. The most expensive computation each call makes is to determine the accuracy of n hypotheses. Since A runs in time-t, the largest hypothesis it can output is a size-t circuit, which can be evaluated in time O(t log t) [AB09]. Therefore, this step takes at most n O(d) • m test • O(t log t) time.
Lemma 6.2 (Correctness). Let C be a concept class, D be a class of distributions that is closed under restrictions, D ⋆ a distribution that has a depth-d decomposition into distributions in D, and A be a base learner using m samples to learns C to expected error ≤ ε under any distribution D ∈ D. Then for any f ∈ C and,
ε and m test := O 2 d ln n ε 2 , if S train and S test are samples consisting m train and m test respectively i.i.d. examples from D * f , TreeLearn A (S train , S test , d) returns a hypothesis H satisfying E[error(H, D ⋆ f )] ≤ 4ε.
Our proof has three parts. First, we show that FindTree A returns the hypothesis with the lowest error on S test (Claim 6.3). Next, we show, in expectation over the randomness of S train and the learner A, there is a tree T for which E[error(T • H, D ⋆ f )] ≤ ε. With these two results, the proof would be complete if error(T • H, D ⋆ f ) = error(T • H, S test ). Indeed, using Claim 6.6, we show that these two values cannot differ much (in expectation) for any depth-d tree T . Claim 6.3 (FindTree minimizes empirical loss.). For any test set S test , depth d, mapping of restrictions from hypothesis H, and restriction ρ, FindTree A (S test , d, H, ρ) returns a tree T satisfying,
Proof. By induction on the depth d. If d = 0, the desired claim holds because there is only one possible tree structure of depth 0. For the inductive step, consider any d > 1. For any tree T with root x i and subtrees T -1 and T 1 , we observe its error can be easily decomposed: Using raw error(h, S) := |S| • error(h) to denote the number of points in S that h fails to classify, raw error(T •H, (S test ) ρ ) = raw error(T 1 •H, (S test ) ρ ∩(x i = 1))+raw error(T -1 •H, (S test ) ρ ∩(x i = -1)).
Next, let T ′ be a tree minimizing the error in Equation (1) and x i ⋆ be its root. Using the notation in FindTree, we claim that error(T (i ⋆ ) , (S test ) ρ ) ≤ error(T ′ , (S test ) ρ ), which implies the desired result since FindTree returns the tree with minimum error. This follows from the inductive hypothesis: Each of the subtrees (T x i ⋆ =-1 and T x i ⋆ =1 ) will have error at least as good as the corresponding subtrees of T ′ . Since the error of a tree decomposes in terms of its subtrees' error, this implies T (i ⋆ ) has error at least as good as T ′ . Claim 6.4 (The existence of a tree with low error in expectation). In the context of Lemma 6.2, for any,
and any f ∈ C, let S train consist of m train i.i.d. examples from D ⋆ f . Then, let H denote the set of hypotheses (H in Figure 5) found by TreeLearn A , where the randomness of H is the randomness of S train and the base learner A.
Our proof of Claim 6.4 will use the following standard Chernoff bound.
Fact 6.5 (Chernoff bound). Let z be the sum of independent random variables each supported on {0, 1} and µ its mean. Then,
Proof of Claim 6.4. Let T ⋆ be the depth-d tree decomposing D ⋆ in D guaranteed to exist by Definition 8. We will show that
which implies the desired bound. The key property of this T ⋆ is: for every ℓ ∈ T ⋆ , conditioned on there being at least m points in (S train ) ρ , the expected error of H(ℓ) on (D ⋆ f ) ℓ is at most ε. This follows from (D ⋆ ) ℓ being within the family of distributions D and the guarantees of the learner A in Theorem 2.
Therefore, the main technical step in this proof is to argue that all leaves ℓ ∈ T for which |(S train ) ℓ | ≤ m collectively have small mass (under D ⋆ ) in expectation (over the randomness of S train ). To formalize this analysis, let p(ℓ) be shorthand for
We will show that for any leaf ℓ, Here, we use that the function p → pe -pm train /8 is decreasing whenever p ≥ 8/m train . By the requirement that m train ≥ 8•2 d ε , we therefore have the quantity p(ℓ)
, in which case Equation (2) still holds. Finally, we bound the expected error of T ⋆ • H:
Next we use a standard argument to connect empirical error to true error.
Claim 6.6 (Empirical error is close to true error.). Let G be a set of functions and S test consist of m i.i.d. points from D ⋆ f . Then,
The proof of Claim 6.6 uses two standard facts about sub-Gaussian random variables. We refer the reader to [Ver18] for a more thorough treatment of sub-Gaussian random variables.
Definition 12 (Sub-Gaussian random variables). A random variable z is said to be sub-Gaussian with variance-proxy σ 2 if, for all λ ∈ R,
Fact 6.7 (Mean of Bernoulli random variables is sub-Gaussian). Let z 1 , . . . , z m each be independent random variables supported on {0, 1} and Z := z 1 +•••+zm m is sub-Gaussian with variance-proxy 1 4m . Fact 6.8 (Expected maximum of sub-Gaussian random variables). Let z 1 , . . . , z n be (not necessarily independent) sub-Gaussian random variables each with variance proxy σ 2 . Then,
Proof of Claim 6.6. By Fact 6.7, for any fixed g ∈ G, the quantity error(g, D ⋆ f ) -error(g, S test ) is sub-Gaussian with variance proxy 1 4m . The desired bound follows from Fact 6.8.
Proof of Lemma 6.2. We have now assembled all the ingredients needed to prove the main result of this subsection.
Proof. An easy counting argument gives that there are at most n 2 d decision trees of depth d. Therefore, by Claim 6.6, for any fixed H and
If we view H as a random variable (with randomness based on the randomness of S train ), then have that H and S test . Therefore, conditioning on any fixed value of H, S test still has the same distribution, and so we still have that,
By Claim 6.4, over the randomness of H, there is a tree T ⋆ with expected error on D ⋆ f at most 2ε. By Equation (3), over the randomness of H and S test , there is a tree with expected error on S test at most 3ε. Since TreeLearn outputs the tree with minimal test error (Claim 6.3), the expected error on S test of the hypothesis that FindTree outputs is at most 3ε. One more application of Equation (3) gives that the expected error on D ⋆ f of the hypothesis outputted is at most 4ε.
Our lifter generically upgrades robust learners on the base distributions D to a robust learner on D ⋆ . We demonstrate this with the following notion of robustness, though similar techniques would apply to other notions.
Definition 13 (Robust learner). We say a learner A c-robustly ε-learns a concept class C over distribution D if the following is true: For any f ∈ C, given iid samples from some
Put differently, if an adversary corrupts η-fraction of the labeled distribution, a robust learner should return a hypothesis with O(η) error in expectation. Recent work [BV24] showed that this notion of robustness is equivalent to nasty noise [BEK02] and strong contamination [DK23] in the sense that a learner satisfying Definition 13 can be black-box transformed into a learner that is robust to nasty noise and strong contamination with only a polynomial increase in runtime and sample size.
Theorem 3 (Lifting robust learners). Let C be a concept class and D = {D 1 , D 2 , . . .} be a class of distributions that is closed under restrictions. If there is a learning algorithm A running in time t and using m samples that c-robustly ε-learns C over every D ∈ D, for
then there is an algorithm A ′ running in time T and using M samples that (2c + 2)-robustly O(ε)-learns C over any distribution D ⋆ that has a depth-d decomposition into distribution in D.
The key property we need about total variation distance we need is the following. Fact 6.9 (Total variation distance distributes over the leaves of a tree, Lemma B.4 of [BLMT22]).
For any distributions D, D ′ with dist TV (D, D ′ ) ≤ η and decision tree T ,
Since the proof of Theorem 3 is essentially the same as Theorem 2, we just sketch the structure of the argument and (minor) differences. We use the same algorithm, TreeLearn from Figure 5. Recall there are three key steps to proving the accuracy of that algorithm:
1. Claim 6.3, that this algorithm finds the tree with the minimum error on the test set. This step remains unchanged in the robust setting.
2. Claim 6.4, that there is a tree with low true error. This step is extremely similar, except we now need to apply Fact 6.9. If the adversary decided to corrupt η fraction of the labeled distribution, by Fact 6.9, the average leaf will have at most 2η corruptions. Hence, using the same logic as in the proof of Claim 6.4, the expected error of the true tree will be at most 2cη + 2ε.
3. Claim 6.6, that empirical error is close to the true error. This step is also essentially the same, except that the expected difference between the emprical error and true error will be upper bounded by (η + ε) rather than ε. This is because the test set will give an ε-accurate estimate of the hypotheses error on the noisy distribution (D c ) ′ (as defined in Definition 13), and so these estimates may only be (ε
Combining these, Learn A is guaranteed to return a hypothesis with empirical error 2cη + η = (2c + 1)η, which translates to at most (2c + 1)η + η = (2c + 2)η error on the true distribution (without noise).
7 Lifting learners over subcube partition distributions 7.1 Subcube lists and the lifting algorithm
In this section, we present a learner that works when the distribution has a small subcube partition into instances of the base distribution family (see Definition 10). We define a subcube list hypothesis, since the hypothesis we return will have a set of restrictions that are not necessarily disjoint.
Definition 14 (Subcube list hypothesis). For an ordered list of restrictions L and a mapping H from restrictions to hypotheses, the subcube list hypothesis L • H is defined as follows:
The main result of this section is the following:
Theorem 4 (Lifting learners using subcube lists). Let C be a concept class and D be a class of distributions closed under restrictions. Let A be a base learner that learns C over distributions in D to expected error ≤ ε log(1/ε) , with sample complexity m and time complexity t. Then there is an algorithm that learns C over any distribution that admits a size-s subcube partition of codimension d into distributions in D, with expected error O(ε). The algorithm has sample complexity
and time complexity
We will analyze the sample complexity and correctness in Lemma 7.1, and the time complexity in Lemma 7.6 . The algorithm is described as follows.
PartitionLearn A (d, s, ε, S train , S test ):
Input: codimension bound d, size bound s, error bound ε, failure probability bound δ, sample sets S train , S test drawn from the unknown distribution D ⋆ .
Output: hypothesis h.
Training phase: For every restriction ρ ∈ {±1, ⋆} n with depth at most d, set h ρ ← A((S train ) ρ ). Let H denote the mapping from ρ to h ρ .
Test phase: Let L ← FindSubcubeList(S test , H, ε, s), as defined in Figure 7. Return H := L • H. First, we will argue that there exists a subcube partition L such that in expectation over S train , after the training phase the error of L • H is sufficiently small. This immediately follows from the proof of Claim 6.4, as Claim 6.4 is in fact a special case of this statement.
Corollary 7.2 (Existence of a subcube partition with low expected error). In the context of Lemma 7.1, for any
and any f ∈ C, let S train consist of m train i.i.d. examples from D ⋆ f . Then, let H denote the set of hypotheses (H in Figure 6) found by PartitionLearn A , where the randomness of H is the randomness of S train and the base learner A. Let L ⋆ be the ground-truth subcube partition of D ⋆ (ordered arbitrarily). We then have
Proof. We may observe that the proof of Claim 6.4 does not require the decomposition of D ⋆ to have treelike structure; rather, the assumption of D ⋆ having a depth-d tree decomposition is used only to prove that D ⋆ has a subcube partition of size 2 d . This corollary follows by substituting s for 2 d and ε log(1/ε) for ε.
Now we argue the analogue of Claim 6.
3, showing that FindSubcubeList finds a list L such that error(L • H, S test ) ≤ O(ε). Here we no longer argue about sample complexity; instead we fix S test and the mapping H. Since here we cannot exactly minimize test loss by backtracking search as in the decision tree setting, we approximately minimize it by an approach inspired by greedy approximate set-cover instead. Lemma 7.3. The algorithm FindSubcubeList in Figure 7 has the following guarantee: If there is some disjoint list of s restrictions with depth-(≤ d) restrictions P for which P • H has error at most ε on S test , then FindSubcubeList(S test , H, ε additional , s) outputs a (not necessarily disjoint) list L satisfying error(L • H, S test ) ≤ O(ε log(1/ε additional ) + ε additional ). FindSubcubeList(S test , H, ε additional , s) : Input: A test set S test , mapping H from restrictions to hypotheses, and parameters ε additional , s. Output: A hypothesis H. Initialize: Set S remaining ← S test and L to an empty list. Greedily grow list: While |S remaining | |S| > ε additional and at most ⌈2s ln(1/ε additional )⌉ iterations have run: 1. Among all depth-(≤ d) restrictions ρ satisfying that a large fraction of the remaining test set is consistent with ρ, |(S remaining ) ρ | |S remaining | ≥ 1 2s , set ρ ⋆ to minimize error(H(ρ), (S remaining ) ρ ). 2. Update parameters: Append ρ ⋆ to L and set S remaining ← S remaining \ (S remaining ) ρ ⋆ . Return L. The first step of this proof is to show that in every step, there exists some restriction that simultaneously has low error over the remaining test sample and covers a large enough fraction of it.
Claim 7.4 (A greedy piece exists). Let S ∈ ({±1} n × {±1}) m be a labeled test set and P := {ρ 1 , . . . , ρ s } be a set of disjoint restrictions for which error(P • H, S) ≤ ε. Then, for any S remaining ⊆ S, there exists some i ∈ [s] for which, 1. ρ i contains a large fraction of S remaining ,
) 2. H(ρ i ) has little error, error(H(ρ i ), (S remaining ) ρ i ) ≤ 2ε • |S| |S remaining | (5) Proof. Let p i := |(S remaining )ρ| |(S remaining )| and p total = m i=1 p i . By the definition of error, we have that (1 -p total ) + i∈[m] p i • error(H(ρ i ), (S remaining ) ρ ) = error(P • H, S remaining ) ≤ |S| |S remaining | • error(P • H, S) ≤ |S| |S remaining | • ε. Let G ⊆ [s] consist of all i ∈ [s] satisfying Equation (5). Then, we must have that i∈G p i ≥ 1/2. Otherwise, the above equation would be violated (since 1/2 of S remaining would have loss greater than 2ε • |S| |S remaining | ). Finally, we observe that since |G| ≤ s, there is some i ∈ G for which p i ≥ 1 2s . This i meets both of the desired criteria. Proof of Lemma 7.3. By Claim 7.4, at each step, FindSubcubeList finds a restriction ρ satisfying, |(S remaining ) ρ | |S remaining | ≥ 1 2s and error(H(ρ), (S remaining ) ρ ) ≤ 2ε • |S test | |S remaining | . First, we show that when the loop in FindSubcubeList terminates, |S remaining | |S|
≤ ε additional . Observe that at each step, the size of S remaining shrinks by a multiplicative factor of (1 -1/(2s)) or better. Therefore, after 2s ln(1/ε additional ) iterations,
≤ ε additional . Next, we bound the test loss of the hypothesis, L • H, for the list that FindSubcubeList outputs. For this, it will be helpful to introduce some notation:
1. Let r i be ratio
at the start of the i th iteration, so that r 1 = 1, r k > ε additional , and r k+1 ≤ ε additional .
2. Let ℓ i be the error of the hypothesis selected in the i th iteration. We have the guarantee that ℓ i ≤ 2ε r i .
Then, using that (r i -r i+1 ) fraction of S test is classified in the i th step, we can decompose the error of H asfoot_2
error(H,
Using the bounds ℓ i ≤ 2ε r i and r k+1 ≤ ε additional , we have
Note that each term in the above summation is at most 1. We can therefore remove the last term to obtain the upper bound,
Finally, we argue that this quantity is O(ε
• log(1/ε additional ) + ε additional ). If ε additional ≤ 1/2, this holds because 2 + 2 ln(1/ε additional ) ≤ O(log(1/ε additional )). Otherwise, if ε additional > 1/2, it holds because the error is upper bounded by 1 which is O(ε additional ). We also give a simple analysis of the time complexity of FindSubcubeList. Proposition 7.5 (FindSubcubeList is efficient). Let T be an upper bound on the time needed to evaluate any hypothesis in H. Then, FindSubcubeList(S test , ε, s) runs in O(T s ln(1/ε) • |S test | • n O(d) ) time. Proof. The time is dominated by determining the loss of each restriction hypothesis in the loop. The loop runs for at most O(2s ln(1/ε)) iterations, there are n O(d) many restriction hypotheses, and determining the loss for one hypothesis takes time at most T • |S test |. 7.2.2 Finishing the proof of correctness Now we can put the above claims together and argue that PartitionLearn finds a hypothesis with small true distributional error in expectation over S train and S test . Proof. There are at most n O(ds ′ ) subcube lists of length s ′ := ⌈2s ln(1/ε)⌉ and depth d, so by Claim 6.6, for any fixed H and m test
), we have
By Corollary 7.2, the training phase produces a mapping H is such that for the ground-truth partition L ⋆ , we have
Putting together Equation (6) and Equation (7), we have
For a fixed H and S test , we will denote ε H := error(L ⋆ • H, S test ). By Lemma 7.3, with parameter "ε" set to ε H and parameter "ε additional " set to ε, we have that PartitionLearn returns a hypothesis L such that error
Putting it all together, we have
Finally, another application of Equation ( 6), gives that error
Now we will analyze the running time of PartitionLearn. Lemma 7.6. PartitionLearn runs in time n O(d) • t log t + log 4 (1/ε) ε 2 . Proof. The training phase runs in time t • n O(d) , since it runs A on each restriction of depth ≤ d. The test phase, by Proposition 7.5, runs in time O(T s ln(1/ε) • |S test | • n O(d) ), where T is a bound on the time required to evaluate a hypothesis returned by A. The size of S test is O( ds log n log 3 (1/ε) ε 2
), and we have T ≤ O(t log t) (see Lemma 6.1). We can eliminate the factors of d, s, and log n since d ≤ n and s ≤ n O(d) , and the desired running time bound follows.
Recall that the approach of [BLMT23] worked in two distinct steps.
1. First, they use subcube-conditional queries to learn the unknown distribution D ⋆ . In more detail, they attempt to find to find a small d for which D ⋆ admits a depth-d decomposition into distributions that are uniform on a subcube, and learn this decomposition.
2. They use this decomposition of D ⋆ to learn the unknown function f . We show that this first step is information-theoretically impossible to perform efficiently if we only have access to random samples, rather than subcube-conditional queries.
Theorem 5 (Impossibility of determining the depth of a distribution using few random samples). Let the base distributions, D, consist of the uniform distribution and all of its restrictions. It takes Ω(2 n/2 ) samples from D ⋆ to, with success probability at least 2/3, distinguish between 1. D⋆ has a depth-0 decomposition into distributions in D, meaning that D ⋆ is the uniform distribution. Our proof of Theorem 5 builds on the classic result that testing whether D ⋆ is uniform or far from uniform takes Ω(2 n/2 ) samples [Pan08]. That classic result uses the following approach: Suppose we draw S ⊆ {±1} n uniformly among all subsets of 2 n 2 elements. Then, D S = Unif(S) is guaranteed to be far from uniform, since S contains only half of the domain. Furthermore, a sample of m ≤ 2 n/2 points from D S is unlikely to have any collisions. The key observation is that, if no collisions occur, the algorithm cannot tell if it received a sample from the uniform distribution over {±1} n or a sample from D S , since S is unknown to the algorithm.
One difficulty of directly applying this result is that D S may only require a depth-1 decompositionfor example, if S contains x iff x 1 = 1. The key novel technical step in the proof of Theorem 5 is the following lemma showing this is unlikely. Lemma 8.1. Let the base distributions, D, be the uniform distribution and all of its restrictions, and d = n -O(log n). For S be drawn uniformly over all size-2 n 2 subsets of {±1} n and D S = Unif(S), Pr S dist TV (D S , D ′ ) ≤ 1/3 for some D ′ with a depth-d decomposition by D ≤ 1 100 .
Proof sketch: A natural approach to proving Lemma 8.1 is a two step process.
1. For any fixed depth-d decision trees T , proving that it is very unlikely a D ′ that is uniform over the leaves of T is close to D S .
2. Union bounding over the ≈ n 2 d unique depth-d decision trees T .
This approach requires union bounding over a doubly exponential number of decision trees. To avoid this doubly exponential quantity, we observe that it is sufficient to prove that all possible depth-d leaves have "high error". This is because, the distance of a D ′ to be D S can be decomposed into the sum of a corresponding distance measure over every leaf ℓ of T . Furthermore, there are at most 2 O(n) possible leaves, so we only need to union bound over a singly-exponential number of leaves. This proof will use Hoeffding's concentration inequality, applied to random variables drawn without replacement. Fact 8.2 (Hoeffding's inequality for samples drawn without replacement, [Hoe63]). Let S ∈ [0, 1] m be a bounded finite population, and let x 1 , . . . , x n be drawn uniformly without replacement from S, and X their sum. Then,
where µ := E[X].
Proof of Lemma 8.1. This proof is broken into two pieces. First, we show that, with high probability over the choice of S, the following holds: For all restrictions ℓ of depth ≤ d,
where count(ℓ) is the random variable counting the number of x consistent with ℓ that are contained in S. Then, we show that if Equation (9) holds for all ℓ of depth ≤ d, then D S is far from all distributions D ′ with decompositions of depth at most d.
Consider any fixed ℓ of depth at most d. Then, since S is drawn uniformly among all size-
2 subsets of {±1} n , the indicators 1[x ∈ S] for each x ∈ {±1} n are drawn uniformly without replacement from a population containing 2 n 2 many 1s and 2 n 2 many 0s. Therefore, applying Fact 8.2 with ε = 1/6,
For our choice of d = n -O(log n), the above probability is less than 3 -n /100. There are at most 3 n restrictions ℓ, since every restriction can be specified by a string in {±1, ⋆} n , so a union bound gives that Equation (9) holds for all ℓ with depth ≤ d with probability at least 0.99. Next, we show that if Equation (9) holds for all such ℓ, then D S is far from all D ′ with depth at most d. Consider any such D ′ . Then, there is some decision tree T of depth at most d such that the marginal distribution of D ′ on any leaf of T is uniform. We can decompose the TV distance between D S and D ′ as a summation over the leaves of T , dist TV (D S , D ′ ) = 1 2 • Finally, we observe that every x ∈ {±1} n must be covered by exactly one leaf ℓ ∈ T , and each ℓ ∈ T covers 2 n-depth(ℓ) unique x. Therefore ℓ∈T 2 -depth(ℓ) = 1. Combining this with the above gives the desired result.
We are now ready to prove the main result of this section.
Proof of Theorem 5. Assume, for the sake of contradiction, there exists an algorithm A that uses m = 2 n/2 20 samples with the following guarantee: If its samples are drawn iid from Unif({±1} n ), it outputs 1 with probability at least 2/3. If its samples are drawn iid from some D ⋆ that robustly requires a depth-(d := n -Ω(log n)) decomposition, then A outputs 0 with probability at least 2/3. Define,
where x 1 , . . . , x m be drawn uniformly without replacement from {±1} n .
We consider two cases based on whether p is large or small and show A fails in both.
Case 1: (p ≤ 1/2). In this case, we will show that when its input distribution truly is uniform, A does not correctly output 1 with probability at least 2/3. For any y 1 , . . . , y m , let collision(y) indicate whether there is some i ̸ = j for which y i = y j . Then, Pr The probability that y i = y j for any i ̸ = j is 1 2 n . By a union bound over all m 2 choices of i ̸ = j for which y i could be equal to y j , we see that
Another downside of [BLMT23]'s approach is that they can only decompose distributions into uniform base distributions. For example, their decomposition algorithm fails if the base distributions are D prod := {all product distributions}. The issue here is, once again, the use of influences in [BLMT23]'s algorithm. They use the influence of a coordinate i ∈ [n] as a proxy for whether x i must be queried to decompose D ⋆ into uniform pieces. This is justified by the fact that, if the base distributions are uniform, the only coordinates with nonzero influence will be coordinates queried by the true decomposition of D ⋆ . However, this is no longer true if the base distributions are D prod . Even when d = 0 (i.e. D ⋆ is itself just a product distribution), all n coordinates can have high influence. Therefore, influence no longer provides a good proxy for what to query.
[BLMT23] and[KKVZ24] do show that the oracle is not necessary in the case of monotone distributions D ⋆ .
This separation is achieved by setting D ⋆ to be the uniform distribution over accepting inputs of the Tribes function and D to consist of the uniform distribution and all its restrictions. See [O'D14] for the definition of and standard properties of Tribes that imply the desired separation.
In the below, we are using that H outputs ⊥ on the remaining r k+1 fraction of points not covered by one of the selected restrictions.