In reinforcement learning, the classic objectives of maximizing discounted
and finitehorizon cumulative rewards are PAClearnable: There are algorithms
that learn a nearoptimal policy with high probability using a finite amount of
samples and computation. In recent years, researchers have introduced
objectives and corresponding reinforcementlearning algorithms beyond the
classic cumulative rewards, such as objectives specified as linear temporal
logic formulas. However, questions about the PAClearnability of these new
objectives have remained open.
This work demonstrates the PAClearnability of general reinforcementlearning
objectives through sufficient conditions for PAClearnability in two analysis
settings. In particular, for the analysis that considers only sample
complexity, we prove that if an objective given as an oracle is uniformly
continuous, then it is PAClearnable. Further, for the analysis that considers
computational complexity, we prove that if an objective is computable, then it
is PAClearnable. In other words, if a procedure computes successive
approximations of the objective's value, then the objective is PAClearnable.
We give three applications of our condition on objectives from the literature
with previously unknown PAClearnability and prove that these objectives are
PAClearnable. Overall, our result helps verify existing objectives'
PAClearnability. Also, as some studied objectives that are not uniformly
continuous have been shown to be not PAClearnable, our results could guide the
design of new PAClearnable objectives.
more »
« less
MODEL THEORY AND MACHINE LEARNING
Abstract About 25 years ago, it came to light that a single combinatorial property determines both an important dividing line in model theory (NIP) and machine learning (PAClearnability). The following years saw a fruitful exchange of ideas between PAClearning and the model theory of NIP structures. In this article, we point out a new and similar connection between model theory and machine learning, this time developing a correspondence between stability and learnability in various settings of online learning. In particular, this gives many new examples of mathematically interesting classes which are learnable in the online setting.
more »
« less
 Award ID(s):
 1700095
 NSFPAR ID:
 10393851
 Date Published:
 Journal Name:
 The Bulletin of Symbolic Logic
 Volume:
 25
 Issue:
 03
 ISSN:
 10798986
 Page Range / eLocation ID:
 319 to 332
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some "extension" of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).more » « less

How quickly can a given class of concepts be learned from examples? It is common to measure the performance of a supervised machine learning algorithm by plotting its “learning curve”, that is, the decay of the error rate as a function of the number of training examples. However, the classical theoretical framework for understanding learnability, the PAC model of VapnikChervonenkis and Valiant, does not explain the behavior of learning curves: the distributionfree PAC model of learning can only bound the upper envelope of the learning curves over all possible data distributions. This does not match the practice of machine learning, where the data source is typically fixed in any given scenario, while the learner may choose the number of training examples on the basis of factors such as computational resources and desired accuracy. In this paper, we study an alternative learning model that better captures such practical aspects of machine learning, but still gives rise to a complete theory of the learnable in the spirit of the PAC model. More precisely, we consider the problem of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring uniformity over the distribution. The main result of this paper is a remarkable trichotomy: there are only three possible rates of universal learning. More precisely, we show that the learning curves of any given concept class decay either at an exponential, linear, or arbitrarily slow rates. Moreover, each of these cases is completely characterized by appropriate combinatorial parameters, and we exhibit optimal learning algorithms that achieve the best possible rate in each case. For concreteness, we consider in this paper only the realizable case, though analogous results are expected to extend to more general learning scenarios.more » « less

null (Ed.)We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentiallyprivate algorithm. This answers an open question of Alon et al. (STOC 2019) who proved the converse statement (this question was also asked by Neel et al. (FOCS 2019)). Together these two results yield an equivalence between online learnability and private PAC learnability. We introduce a new notion of algorithmic stability called “global stability” which is essential to our proof and may be of independent interest. We also discuss an application of our results to boosting the privacy and accuracy parameters of differentiallyprivate learners.more » « less