{"id":661,"date":"2024-06-06T17:03:57","date_gmt":"2024-06-06T17:03:57","guid":{"rendered":"https:\/\/www.let-all.com\/blog\/?p=661"},"modified":"2024-08-06T22:02:34","modified_gmt":"2024-08-06T22:02:34","slug":"one-inclusion-graphs-and-the-optimal-sample-complexity-of-pac-learning-part-1","status":"publish","type":"post","link":"https:\/\/www.let-all.com\/blog\/2024\/06\/06\/one-inclusion-graphs-and-the-optimal-sample-complexity-of-pac-learning-part-1\/","title":{"rendered":"One-Inclusion Graphs and the Optimal Sample Complexity of PAC Learning: Part 1"},"content":{"rendered":"\n

We’re back again with another post! In case you missed the first two in the series, on calibration<\/a> and multi-class classification<\/a>, please check them out.<\/p>\n\n\n\n

Today, we have the first in a two-parter by Ishaq Aden-Ali<\/a>, Yeshwanth Cherapanamjeri<\/a>, Abhishek Shetty<\/a>, and Nikita Zhivotovskiy<\/a>, again on sample-efficient methods for PAC learning. In the first post, they revisit and discuss a refutation<\/a> of the strong version of Warmuth’s one-inclusion graph conjecture.<\/p>\n\n\n\n

Introduction<\/strong><\/h1>\n\n\n\n

One of the key contributions of computer science is the formalization of the concept of learning. These definitions try to get at the heart of the question of what patterns can be recognized from examples. In this (and the next) blog post, we will discuss a probabilistic formalization of this question through the Probably Approximately Correct (PAC) model of learning, and we will try to understand how many examples are needed to learn a pattern with high probability over the data generating process, i.e. the sample complexity<\/em>. Towards this goal of characterizing the optimal sample complexity, we will see connections between the PAC model and a model of learning known as transductive learning. Further, we will characterize learning in the transductive setting using an elegant combinatorial argument.<\/p>\n\n\n\n

Finally, we will connect high probability PAC bounds to transductive learning using a general connection with online learning using a simple argument connecting beyond worst-case analysis of sequential decision-making can lead to sharp bounds in an a priori offline learning setting.<\/p>\n\n\n\n

Probably Approximately Correct (PAC) Learning<\/h2>\n\n\n\n

The basic mathematical setup for learning involves a set \"\mathcal{X}\" and a set \"\mathcal{Y}\" which we will refer to as the domain and the label set respectively. The domain \"\mathcal{X}\" is the set of all possible examples and the label set \"\mathcal{Y}\" is the set of all possible labels. An example to keep in mind is \"\mathcal{X}\" is the set of all images and \"\mathcal{Y}\" is the set of all possible labels for the images (e.g. cat, dog, etc.). For simplicity, we will focus on the case where \"\mathcal{Y}. This is referred to as binary classification. Later in the post, we will comment on how the ideas apply to more general settings such as when \"\mathcal{Y}\" has larger cardinality or even when \"\mathcal{Y}\" is a continuous set such as \"\left[.<\/p>\n\n\n\n

The key modeling assumption is the presumption of the existence of a distribution \"\mathcal{D}\" over the domain \"\mathcal{X}\" and that the examples are drawn independently from this distribution. This distribution models the idea that the examples are produced from some underlying data generating process which, though unknown, is fixed and does not change over time. The learner has access to labelled examples drawn from this distribution. This set of examples is referred to as the training set.<\/p>\n\n\n\n

Since one cannot expect to learn arbitrary labelling functions, simplicity of the labelling function is usually encoded by assuming that the labelling function \"f^{\star}\" is chosen from a class of functions \"\mathcal{F}\", known as the hypothesis class. This setting is referred to as the realizable setting since we are assuming that the labels are realized<\/em> by some function in the hypothesis class. One can consider extensions to allow for label noise or even arbitrary labels but in this post we will focus on the realizable setting.<\/p>\n\n\n\n

The learner, thus, has access to a training set \"S drawn i.i.d. from \"\mathcal{D}\". The aim of the learner is to output, with probability at least \"1 over the choice of the training set \"S\" (i.e. probably), a hypothesis \"h\" 1<\/a><\/sup> which is approximately correct with respect to an unseen example from the same distribution \"\mathcal{D}\", i.e.<\/p>\n\n\n\n

\"\mathcal{R}(h)<\/p>\n\n\n\n


We will refer to \"\mathcal{R}(h)\" as the risk<\/em> of the function \"h\" (under \"\mathcal{D}\" with respect to \"f^\star\"). This model of learning is known as Probably Approximately Correct (PAC) learning. The choice of \"\delta\" controls the probability of failure while \"\epsilon\" controls the accuracy of the output hypothesis.<\/p>\n\n\n\n

Empirical Risk Minimization<\/h2>\n\n\n\n

In the above model, given that there is a consistent hypothesis respecting the labels, a natural algorithm would be to find a function consistent with the labels seen so far. That is, output \"\tilde{f}. Note that this set is non-empty because \"f^{\star}\" is in this set. Any algorithm that returns such a function is referred to as an Empirical Risk Minimization (ERM) algorithm. The main challenge in analyzing the algorithm is that this set is typically very large and the different functions in this set can make different predictions on the unseen points. Since we are choosing an arbitrary realizable function, we would like to argue any of them will typically make good predictions on unseen points.

The idea is to argue that if it is likely that a candidate function \"\tilde{f}\" disagrees with \"f^{\star}\" on the test example, then it is likely that \"\tilde{f}\" would have disagreed with \"f^{\star}\" on the training examples as well and thus the algorithm would have output a different function. This hints at the idea of exchangeability of the training examples with the test example playing an important role in the behavior of learning algorithms. Though this is indeed the case, typical analyses of ERM do not discuss exchangeability directly but rather go through independence and concentration arguments. What we will see later is that exchangeability will play a crucial role in our understanding of optimal sample complexity of PAC learning.<\/p>\n\n\n\n

But, getting back to the ERM algorithm, we need a formal notion of complexity of the hypothesis class \"\mathcal{F}\" to bound the error of the ERM algorithm. This is formalized by the Vapnik-Chervonenkis (VC) dimension. Intuitively, the VC dimension controls how many “different” functions the hypothesis class can express. We will not go into the details of this notion of complexity right now, but we will return it later in the post (Definition 1 and Theorem 4) and see how it plays a crucial role in the analysis of optimal learning algorithms albeit capturing a slightly different aspect of the complexity of a function class. Now, we will state the sample complexity of the ERM algorithm in the PAC model.<\/p>\n\n\n\n

Theorem<\/strong> 1 [VC Theorem, See e.g. [SB14]] Let \"\mathcal{X}\" be a domain and \"\mathcal{F}\" be a class of functions from \"\mathcal{X}\" to \"\{0,1\}\" with VC dimension \"d\". Let \"\epsilon,. Let<\/p>\n\n\n\n


\"n
<\/p>\n\n\n\n

Let \"S be a sample of size \"n\" drawn i.i.d. from \"\mathcal{D}\" and \"f^{\star}. Then, with probability at least \"1 over the choice of the training set \"S\", any \"f\" that is consistent with \"S\" satisfies<\/p>\n\n\n\n

\"\Pr_{X
<\/p>\n\n\n\n

Optimal Sample Complexity of PAC Learning<\/h2>\n\n\n\n


A natural question is to ask whether the sample complexity of the ERM algorithm is tight. Using simple arguments, one can show lower bounds on the sample complexity of any<\/em> learning algorithm in terms of the parameters \"d\", \"\epsilon\" and \"\delta\" appearing in Theorem 1.
<\/p>\n\n\n\n

Theorem<\/strong> 2 [Sample Complexity Lower Bound, See e.g. [SB14]] Let \"\mathcal{X}\" be a domain and \"\mathcal{F}\" be a class of functions from \"\mathcal{X}\" to \"\{0,1\}\" with VC dimension \"d\". Let \"\epsilon,. Then, any algorithm that outputs a hypothesis \"h\" that has error at most \"\epsilon\" with probability at least \"1 over the choice of the training set \"S\", must require a sample size \"n\" satisfying<\/p>\n\n\n\n

\"n<\/p>\n\n\n\n


Note that the upper and lower bounds differ by a factor of \"\log(1\/\epsilon)\". Given this mismatch, the first question that one might ask is which of the bounds is tight. Unfortunately, for the ERM algorithm, the upper bound is indeed tight. But, one might wonder if there is a better algorithm than ERM. This question remained open for several decades until the breakthrough works of Simon [Sim15] and Hanneke [Han16] who showed that the lower bound is tight by presenting an algorithm that achieves this sample complexity. In the rest of the current and the following post, we will see why the sample complexity from Theorem 2 is natural and present a general technique recently discovered by [AACSZ23a] to achieve this sample complexity in the PAC model, leading up to the following theorem.
<\/p>\n\n\n\n

Theorem 3<\/strong> [Optimal Sample Complexity of PAC Learning] Let \"\mathcal{X}\" be a domain and \"\mathcal{F}\" be a class of functions from \"\mathcal{X}\" to \"\{0,1\}\" with VC dimension \"d\". Let \"\epsilon,. Let<\/p>\n\n\n\n

\"n<\/p>\n\n\n\n


Let \"S be a sample of size \"n\" drawn i.i.d. from \"\mathcal{D}\" and \"f^{\star}. There is an prediction strategy \"\hat{f}\" such that, with probability at least \"1 over the choice of the training set \"S\", we have<\/p>\n\n\n\n

\"\Pr_{x
<\/p>\n\n\n\n



A key feature of the techniques we will see in this post is that they allow us to generalize from binary classification to more general settings, leading to a unified perspective on optimal PAC learning algorithms.<\/p>\n\n\n\n

Transductive Learning and the One-Inclusion Graph Algorithm<\/h1>\n\n\n\n


In order to motivate Theorem 3, we will take a detour and discuss a learning setting known as transductive learning<\/em>. We will view transductive learning as a game where a player is competing against an adversary. As before we will will fix a function class \"\mathcal{F}\". The game proceeds as follows:<\/p>\n\n\n\n