Computational Learning Theory
Credal Learning Theory
Statistical learning theory is the foundation of machine learning, providing theoretical bounds for the risk of models learned from a (single) training set, assumed to issue from an unknown probability distribution.
Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions
Trauger, Jacob, Trauger, Tyson, Tewari, Ambuj
Classification is one of the most common tasks in machine learning. Within classification, there is normally a split between binary classification (only two possible outputs) and multiclass classification (more than two possible outputs). The theoretical analysis of these settings shares the same split. Under the P AC-learning model, binary classification learnability under the 0-1 loss is known to be characterized by the VC-dimension [V apnik and Chervonenkis, 1974, Shalev-Shwartz and Ben-David, 2014]. For multiclass classification, there has also been a further split between finite and infinite label cases.
Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems
In this paper, we study the role of machine-learned predictions in offline NP-hard problems.
Causal Discovery from Event Sequences by Local Cause-Effect Attribution
Suppose we are considering a multivariate event sequence. What caused a specific event to happen? Which variables are causes of each other?
A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems
Learn-to-Defer is a paradigm that enables learning algorithms to work not in isolation but as a team with human experts.
Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
The study of online algorithms with machine-learned predictions has gained considerable prominence in recent years.
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi
The full version of this paper is available at [DKM19].