5 papers
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke +4
The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both…
The Role of Randomness in Stability
Max Hopkins, Shay Moran
Stability is a central property in learning and statistics promising the output of an algorithm does not change substantially when applied to similar datasets and . It…
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…
On Differentially Private Linear Algebra
Haim Kaplan, Yishay Mansour, Shay Moran +2
We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities ove…
Probably Approximately Precision and Recall Learning
Lee Cohen, Yishay Mansour, Shay Moran +1
Precision and Recall are fundamental metrics in machine learning tasks where both accurate predictions and comprehensive coverage are essential, such as in multi-label learning, la…