Samplability Makes Learning Easier

The sample complexity of learning in standard PAC is fairly well-understood, in large part due to an elegant characterization in terms of VC dimension [26, 9] – a foundational result now called “The Fundamental Theorem of PAC Learning” [23]. A VC dimension lower bound is generally viewed as an information-theoretic no-go in terms of efficient learnability: If a learning task cannot be learned with a reasonable number of samples, that trivially implies that it cannot be learned in a reasonable amount of time either.

Our first result is as follows:

This shows that VC dimension lower bounds can be overly pessimistic. A learning task with large VC dimension may nevertheless be efficiently learnable if one assumes that these samples are generated according to a reasonable distribution. Put differently, the VC dimension lower bound may be witnessed by an extremely complicated shattering set, one that is intractable to sample from and hence arguably will not arise in the real world – indeed, this intuition is the starting point for our proof of Theorem 1.

The concept class in Theorem 1 has exponential circuit complexity, necessarily so since the class of size-$s$ circuits has VC dimension $\tilde{O}(s)$. It is natural to then ask about samplable vs. standard PAC learning of classes of polynomial-size circuits. Such classes are of interest because functions that arise in practice can be assumed to be efficiently computable, and relatedly, the barriers to their efficient learnability are solely computational in nature and cannot rely on information-theoretic impossibility.

As already observed in [25], if $\mathrm{𝖱𝖯}=\mathrm{𝖭𝖯}$ then every concept class of polynomial-size circuits is efficiently learnable in polynomial time in standard PAC. So short of proving $\mathrm{𝖱𝖯}\ne \mathrm{𝖭𝖯}$, any computational separation will have to either rely on complexity assumptions or be relativized. Implicit in the work of Xiao [27] is a separation relative to a specific oracle. We discuss [27]’s result in Section 3, mentioning for now that this is an oracle relative to which one-way functions do not exist. This therefore should not be viewed as evidence as to whether such a separation exists in the unrelativized world – and [27] did not claim it as such – since presumably we believe that one-way functions do exist in the unrelativized world.

Our second result gives a computational separation conditioned on two complexity assumptions, a standard one (ironically, the existence of one-way functions) and a new one that we introduce (the existence of explicit “evasive sets”, Conjecture 11):

The definition of an explicit evasive set is rather technical and we defer it to Section 2. For now, we mention that it is a set $H\subseteq {\{0,1\}}^n$ that is explicit in the sense that membership in $H$ can be easily verified (i.e. the function $x\mapsto \mathrm{𝟙}[x\in H]$ is computable in polynomial time), and yet is evasive in the sense that any samplable distribution must “mostly miss” it. The crux of the connection to learning lies in pinning down the appropriate notion of “mostly miss” (Definition 7).

Proving the existence of explicit evasive sets unconditionally is likely difficult: Like in the case of one-way functions, doing so will imply $𝖯\ne \mathrm{𝖭𝖯}$ (we show this in the full version of this paper). We nevertheless prove that they exist relative to a random oracle (see the full version of this paper). Since one-way functions also exist relative to a random oracle, we obtain as a corollary a computational separation of samplable PAC from standard PAC that holds relative to a random oracle, improving on [27]’s separation for a specific oracle:

As is standard in complexity theory, we view Corollary 3 as saying that the speedups offered by samplable PAC over standard PAC hold not just for certain structured instances (that may have been tailored for such a separation), but even for generic, unstructured ones. See [1] for a discussion of this point and the role of random oracle separations more generally.

The techniques we use to prove Theorems 1 and 2 extend to give finer-grained separations within samplable PAC, showing that learning under distributions with size-$s$ generators can be much easier than under those with size-$S$ generators, even if $s$ is only slightly smaller than $S$.

While Theorem 1 shows that there are learning tasks whose sample complexity scale smoothly with the complexity of the distribution, Theorem 5 shows that there are ones for which a slight increase in the complexity of the distribution results in a dramatic increase in sample complexity. See Figure 1. We also prove a computational analogue of Theorem 5 in the full version of this paper.

Another well-studied model of supervised learning is the online mistake bound model [21]. Learning in this model proceeds in rounds. In each round, the adversary presents the learner with an unlabeled instance $x\in {\{0,1\}}^n$. The learner responds with its prediction $y\in \{0,1\}$ and is then told whether that is correct (i.e. whether $y=f(x)$). The goal of the learner is to minimize its total number of mistakes.

Here again the standard definition allows the adversary to be computationally unbounded – it can take superpolynomial time to produce the test instance in each round. Yet, efficient online learners are expected to be efficient even against such adversaries. For the same reasons as in the PAC setting, it is therefore natural to consider the variant where the adversary is also assumed to be efficient. In the full version of this paper, we show how our techniques can be extended to the online setting to similarly show how the complexity of online learning – both in terms of mistake bounds and the runtime of learners – can depend on the power of the adversary.

Our statistical separation of samplable PAC from standard PAC (Theorem 1) relies on the existence of large evasive sets. Largeness will be useful for our lower bounds against standard PAC whereas the evasiveness will be useful for our upper bounds in samplable PAC. We prove:

We prove Lemma 10 using the probabilistic method. For intuition, consider the special case of flat distributions (those that are uniform over their support). For such distributions $𝒟$, if $\mathrm{supp}(𝒟)$ is sufficiently large, we can show that $𝒟$ is highly unlikely to $\epsilon$-hit a randomly chosen $𝑯$. The failure probability decays exponentially with $|\mathrm{supp}(𝒟)|$, allowing us to union bound over all size-$s$ distributions with sufficiently large supports. This argument no longer works if $\mathrm{supp}(𝒟)$ is small, but in this case we can use the fact that $𝒟$ trivially $(0,|\mathrm{supp}(𝒟)|)$-misses every $H$. The parameters of Lemma 10 are near-optimal, since every $H$ is $(1-\lambda ,\mathrm{\Theta }(\lambda s/n))$-hit by any size-$s$ distribution that is uniform on $\mathrm{\Theta }(s/n)$ many memorized points in $H$.

Our computational separation of samplable PAC from standard PAC (Theorem 2) relies on the existence of a large set that not only evasive, but is furthermore explicit in the sense that membership in it (i.e. the function $x\mapsto \mathrm{𝟙}[x\in H]$) is easy to decide:

We study Conjecture 11 in detail in the full version of this paper. We show that it implies $𝖯\ne \mathrm{𝖭𝖯}$ and that it holds relative to a random oracle. The proof of the latter strengthens that of Lemma 10. The key idea is to show that a samplable distribution $𝒟$ is highly unlikely to hit a randomly chosen $𝑯$, even if the circuit generating $𝒟$ is allowed unit-time membership queries to $𝑯$.

We first describe how Lemma 10 yields a statistical separation of samplable PAC from standard PAC. For a set $H\subseteq {\{0,1\}}^n$ and function $f:{\{0,1\}}^n\to \{0,1\}$, we write $f_H:{\{0,1\}}^n\to \{0,1\}$ to denote the following restriction of $f$ to $H$:

For a concept class $𝒞$, we similarly write ${𝒞}_H$ to denote the restriction of $𝒞$ to $H$:

Now consider ${𝒜}_H$ where $𝒜$ is the class of all functions $f:{\{0,1\}}^n\to \{0,1\}$. It is easy to check that $H$ is the largest set shattered by ${𝒜}_H$ and hence the VC dimension of ${𝒜}_H$ is exactly $|H|$. The sample complexity of learning ${𝒜}_H$ in standard PAC is therefore governed by the size of $H$. In particular, if $H$ has exponential size then learning ${𝒜}_H$ in standard PAC requires exponential sample complexity. (This is why we are concerned with evasive sets of large size in Lemma 10.)

On the other hand, we are able to exploit the evasiveness of $H$ to design an efficient algorithm for learning ${𝒜}_H$ in samplable PAC:

The intuition for Lemma 12 is simple. If $H$ is $(\epsilon ,k)$-evasive, then a learner that memorizes the labels for the $k$ heaviest points in $H$ will only incur $\epsilon$ error. While a learner may not see the $k$ heaviest points, or even know when it has seen them, we show that memorizing $O(k/\epsilon )$ samples suffices to achieve good accuracy.

In the proof of Theorem 1, since $H$ is not explicit and $𝒜$ is the class of all functions, there are no nontrivial upper bounds on circuit complexity of the functions in ${𝒜}_H$. We now describe how we extend the proof strategy so that the separating concept class is a class of polynomial-size circuits. As mentioned, the lower bounds against standard PAC will now be computational in nature and can no longer rely on the information-theoretic arguments that underlie VC dimension lower bounds.

Consider the class ${ℱ}_H$ where $H$ is an explicit evasive set given by Conjecture 11 and $ℱ$ is a pseudorandom function family [13], the existence of which follows from the existence of one-way functions. First note that ${ℱ}_H$ now does in fact have polynomial circuit complexity: every function in this class can be computed by a circuit of size $O(S_1+S_2)$, where $S_1$ is the circuit complexity of deciding membership in $H$ and $S_2$ is the circuit complexity of $ℱ$.

It is well known that pseudorandom function families are hard to learn: an efficient learner for $ℱ$ in standard PAC can be used to break $ℱ$’s security guarantees [25]. We extend this to show that as long as $H$ is sufficiently large, an efficient learner for ${ℱ}_H$ suffices to break $ℱ$’s security guarantees. Stated in the contrapositive, $ℱ$’s security guarantees implies hardness of learning ${ℱ}_H$ in standard PAC. (This is why we are concerned with evasive sets of large size in Conjecture 11.)