87 citations · 170 across the 16 of their papers we have counts for
17 papers
Surprises in Proper Positive-Only Learning
Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1
Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, bu…
Online Learning with Improving Agents: Multiclass, Budgeted Agents and Bandit Learners
Sajad Ashkezari, Shai Ben-David
We investigate the recently introduced model of learning with improvements, where agents are allowed to make small changes to their feature values to be warranted a more desirable…
Active learning from positive and unlabeled examples
Farnam Mansouri, Sandra Zilles, Shai Ben-David
Learning from positive and unlabeled data (PU learning) is a weakly supervised variant of binary classification in which the learner receives labels only for (some) positively labe…
Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models
Alireza F. Pour, Farnam Mansouri, Shai Ben-David
We study the problem of learning with multiple correct answers, where each instance admits a set of valid labels. We primarily focus on the online setup, where in each round the le…
A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes
Alireza F. Pour, Shai Ben-David
We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common appro…
Learning from positive and unlabeled examples -Finite size sample bounds
Farnam Mansouri, Shai Ben-David
PU (Positive Unlabeled) learning is a variant of supervised classification learning in which the only labels revealed to the learner are of positively labeled instances. PU learnin…
Distribution Learnability and Robustness
Shai Ben-David, Alex Bie, Gautam Kamath +1
We examine the relationship between learnability and robust (or agnostic) learnability for the problem of distribution learning. We show that, contrary to other learning settings (…
Out of the Ordinary: Spectrally Adapting Regression for Covariate Shift
Benjamin Eyre, Elliot Creager, David Madras +2
Designing deep neural network classifiers that perform robustly on distributions differing from the available training data is an active area of machine learning research. However,…
Continual Learning: Applications and the Road Forward
Eli Verwimp, Rahaf Aljundi, Shai Ben-David +17
Continual learning is a subfield of machine learning, which aims to allow machine learning models to continuously learn on new data, by accumulating knowledge without forgetting wh…
Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem
Tosca Lechner, Shai Ben-David
We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer…
On Computable Online Learning
Niki Hasrati, Shai Ben-David
We initiate a study of computable online (c-online) learning, which we analyze under varying requirements for "optimality" in terms of the mistake bound. Our main contribution is t…
Enforcing Interpretability and its Statistical Impacts: Trade-offs between Accuracy and Interpretability
Gintare Karolina Dziugaite, Shai Ben-David, Daniel M. Roy
To date, there has been no formal study of the statistical cost of interpretability in machine learning. As such, the discourse around potential trade-offs is often informal and mi…
Provably noise-robust, regularised -means clustering
Shrinu Kushagra, Yaoliang Yu, Shai Ben-David
We consider the problem of clustering in the presence of noise. That is, when on top of cluster structure, the data also contains a subset of \emph{unstructured} points. Our goal i…
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes
Hassan Ashtiani, Shai Ben-David, Nick Harvey +3
We prove that samples are necessary and sufficient for learning a mixture of Gaussians in , up to error in total va…
2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
Shai Ben-David
The Vapnik-Chervonenkis dimension is a combinatorial parameter that reflects the "complexity" of a set of sets (a.k.a. concept classes). It has been introduced by Vapnik and Chervo…
Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss
Shai Ben-David, David Loker, Nathan Srebro +1
We carefully study how well minimizing convex surrogate loss functions, corresponds to minimizing the misclassification error rate for the problem of binary classification with lin…
A Uniqueness Theorem for Clustering
Reza Bosagh Zadeh, Shai Ben-David
Despite the widespread use of Clustering, there is distressingly little general theory of clustering available. Questions like "What distinguishes a clustering of data from other d…