DeLTA seminar by Amir Yehudayoff
Speaker
Amir Yehudayoff
Title
A characterization of multiclass learnability
Abstract
A seminal result in the theory of machine learning characterizes the PAC learnability of binary classes through the VC dimension. Extending this characterization to the general multiclass setting has been an open problem since the pioneering works on multiclass PAC learning in the late 1980s. We solve this open problem, and characterize PAC learnability in the multiclass setting through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz. The proof in the classical binary case boils down to uniform convergence and empirical risk minimization. Our characterization involves a variety of algorithmic techniques. We also introduce a novel and natural setting we call list PAC learning. In list PAC learning, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of likely predictions.
The Natarajan dimension has been the most-studied candidate for characterizing multiclass learnability. Our second main result is that the Natarajan dimension does not characterize multiclass PAC learnability. We construct a non-learnable class with Natarajan dimension 1. This settles an open problem posed in several papers since the 1980s. For the construction, we identify a fundamental connection between concept classes and topology (i.e., colorful simplicial complexes). We crucially rely on a deep and involved construction of a ``hyperbolic pseudo-manifold'' by Januszkiewicz and Swiatkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no ``obvious obstacles'' exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics.
This is joint work with Nataly Brukim, Daniel Carmon, Irit Dinur and Shay Moran.
_____________________________
You can subscribe to DeLTA Seminar mailing list by sending an empty email.
Information about DeLTA Seminars is available at DeLTA Lab page
DeLTA is a research group affiliated with the Department of Computer Science at the University of Copenhagen studying diverse aspects of Machine Learning Theory and its applications, including, but not limited to Reinforcement Learning, Online Learning and Bandits, PAC-Bayesian analysis