Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP ``dichotomy'' in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT -- the core concept at the center of the parameterized complexity paradigm -- and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs.

We present a new general-purpose algorithm for learning classes of [0,1]-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of this algorithm in terms of a scale-sensitive generalization of the Vapnik dimension proposed by Alon, Ben-David, Cesa-Bianchi and Haussler. We give lower bounds implying that our upper bounds cannot be improved by more than a constant factor in general. We apply this result, together with techniques due to Haussler and to Benedek and Itai, to obtain new upper bounds on packing numbers in terms of this scale-sensitive notion of dimension. Using a different technique, we obtain new bounds on packing numbers in terms of Kearns and Schapire's fat-shattering function. We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of agnostic learning. For each ǫ > 0, we establish weaker sufficient and stronger necessary conditions for a class of [0,1]-valued functions to be agnostically learnable to within ǫ, and to be an ǫ-uniform Glivenko-Cantelli class. This is a manuscript that was accepted by JCSS, together with a correction. Also affiliated with University of California, Berkeley.

We introduce and study a learning theory which is roughly automatic, that is, it does not require but a minimum of initial programming, and is based on the potential computational phenomenon of self-reference, (i.e. the potential ability of an algorithm to have its program as an input). The conclusions agree with scientific findings in both biology and neuroscience and provide a plethora of explanations both (in conjunction with Darwinism) about evolution, as well as for the functionality and learning capabilities of human brain, (most importantly), as we perceive them in ourselves.

The Natarajan dimension is a fundamental tool for characterizing multi-class PAC learnability, generalizing the Vapnik-Chervonenkis (VC) dimension from binary to multi-class classification problems. This work establishes upper bounds on Natarajan dimensions for certain function classes, including (i) multi-class decision tree and random forests, and (ii) multi-class neural networks with binary, linear and ReLU activations. These results may be relevant for describing the performance of certain multi-class learning algorithms.

Cryptography requires "useful" sources of computational hardness for most of its constructs. For example, in the classic setting of encryption schemes, decryption should be easy when given an appropriate decryption key, while it must be infeasible without it. Fortunately, the theory of computational complexity generously provides a wide variety of sources of computational hardness, but which ones may be useful for cryptography? The long-celebrated interplay between cryptography and computational complexity has been challenged constantly with understanding what "useful" hardness means, where it may be found, and how it may be utilized. This has led the cryptography community to embark on an exciting journey initiated by the pioneering work of Whitfield Diffie and Martin Hellman back in 1976.

Littlestone and Warmuth [51] introduced sample compression schemes as an abstraction of the underlying structure of learning algorithms. Roughly, the aim of a sample compression scheme is to compress samples of a concept class (i.e., of a set system) C as much as possible, such that data coherent with the original samples can be reconstructed from the compressed data. There are two types of sample compression schemes: labeled, see [35, 51] and unlabeled, see [7, 34, 49]. A labeled compression scheme of size k compresses every sample of C to a labeled subsample of size at most k and an unlabeled compression scheme of size k compresses every sample of C to a subset of size at most k of the domain of the sample (see the end of the introduction for precise definitions). The Vapnik-Chervonenkis dimension (VC-dimension) of a set system, was introduced by [69] as a complexity measure of set systems. VC-dimension is central in PAC-learning and plays an important role in combinatorics, algorithmics, discrete geometry, and combinatorial optimization. In particular, it coincides with the rank in the theory of (complexes of) oriented matroids. Furthermore, within machine learning and closely tied to the topic of this paper, the sample compression conjecture of [35] and [51] states that any set system of VC-dimension d has a labeled sample compression scheme of size O(d). This question remains one of the oldest open problems in computational learning theory.

In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classification. In this paper, we address this issue by providing optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. Our framework converts the leave-one-out error of permutation invariant predictors into high probability risk bounds. As an application, by adapting the one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth, we propose an algorithm that achieves an optimal PAC bound for binary classification. Specifically, our result shows that certain aggregations of one-inclusion graph algorithms are optimal, addressing a variant of a classic question posed by Warmuth. We further instantiate our framework in three settings where uniform convergence is provably suboptimal. For multiclass classification, we prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, addressing the suboptimality of the analysis of Daniely and Shalev-Shwartz. For partial hypothesis classification, we determine the optimal sample complexity bound, resolving a question posed by Alon, Hanneke, Holzman, and Moran. For realizable bounded regression with absolute loss, we derive an optimal risk bound that relies on a modified version of the scale-sensitive dimension, refining the results of Bartlett and Long. Our rates surpass standard uniform convergence-based results due to the smaller complexity measure in our risk bound.

We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniques allow us to show similar results for several general notions of characterizing learnability and for several learning tasks. We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. We then consider the weaker requirement of only characterizing learnability (rather than the quantitative sample complexity function). We propose some natural requirements for such a characterization and go on to show that there exists no characterization of learnability that satisfies these requirements for classes of distributions. Furthermore, we show that our results hold for various other learning problems. In particular, we show that there is no notion of dimension characterizing (or characterization of learnability) for any of the tasks: classification learning for distribution classes, learning of binary classifications w.r.t. a restricted set of marginal distributions, and learnability of classes of real-valued functions with continuous losses.

No free lunch theorems for supervised learning state that no learner can solve all problems or that all learners achieve exactly the same accuracy on average over a uniform distribution on learning problems. Accordingly, these theorems are often referenced in support of the notion that individual problems require specially tailored inductive biases. While virtually all uniformly sampled datasets have high complexity, real-world problems disproportionately generate low-complexity data, and we argue that neural network models share this same preference, formalized using Kolmogorov complexity. Notably, we show that architectures designed for a particular domain, such as computer vision, can compress datasets on a variety of seemingly unrelated domains. Our experiments show that pre-trained and even randomly initialized language models prefer to generate low-complexity sequences. Whereas no free lunch theorems seemingly indicate that individual problems require specialized learners, we explain how tasks that often require human intervention such as picking an appropriately sized model when labeled data is scarce or plentiful can be automated into a single learning algorithm. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.

We apply the theory of Tishby, Levin, and Sol1a (TLS) to two problems. First we analyze an elementary problem for which we find the predictions consistent with conventional statistical results. Second we numerically examine the more realistic problem of training a competitive net to learn a probability density from samples. We find TLS useful for predicting average training behavior. Recently a theory of learning has been constructed which describes the learning of a relation from examples (Tishby, Levin, and Sol1a, 1989), (Schwarb, Samalan, Sol1a, and Denker, 1990).