6 papers
Active Learning on Adversarially Corrupted Graphs
Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi +2
Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} insi…
Learning Conditional Averages
Marco Bressan, Nataly Brukhim, Nicolo Cesa-Bianchi +4
We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in…
Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
Marco Bressan, Victor Chepoi, Emmanuel Esposito +1
Abstract notions of convexity over the vertices of a graph, and corresponding notions of halfspaces, have recently gained attention from the machine learning community. In this wor…
Of Dice and Games: A Theory of Generalized Boosting
Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi +4
Cost-sensitive loss functions are crucial in many real-world prediction problems, where different types of errors are penalized differently; for example, in medical diagnosis, a fa…
Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
Marco Bressan, Emmanuel Esposito, Maximilian Thiessen
We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices t…
A Theory of Interpretable Approximations
Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito +3
Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning model…