113 citations · 241 across the 31 of their papers we have counts for
24 papers · 1 filter
Discriminative Feature Feedback with General Teacher Classes
Omri Bar Oz, Tosca Lechner, Sivan Sabato
We study the theoretical properties of the interactive learning protocol Discriminative Feature Feedback (DFF) (Dasgupta et al., 2018). The DFF learning protocol uses feedback in t…
Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies
Shlomi Weitzman, Sivan Sabato
We study adaptive combinatorial maximization, which is a core challenge in machine learning, with applications in active learning as well as many other domains. We study the Bayesi…
On the Capacity Limits of Privileged ERM
Michal Sharoni, Sivan Sabato
We study the supervised learning paradigm called Learning Using Privileged Information, first suggested by Vapnik and Vashist (2009). In this paradigm, in addition to the examples…
Improved Robust Algorithms for Learning with Discriminative Feature Feedback
Sivan Sabato
Discriminative Feature Feedback is a setting proposed by Dastupta et al. (2018), which provides a protocol for interactive learning based on feature explanations that are provided…
Disparate Conditional Prediction in Multiclass Classifiers
Sivan Sabato, Eran Treister, Elad Yom-Tov
We propose methods for auditing multiclass classifiers for fairness under multiclass equalized odds,by estimating the deviation from equalized odds when the classifier is not compl…
A Fast Algorithm for PAC Combinatorial Pure Exploration
Noa Ben-David, Sivan Sabato
We consider the problem of Combinatorial Pure Exploration (CPE), which deals with finding a combinatorial set or arms with a high reward, when the rewards of individual arms are un…
Active Structure Learning of Bayesian Networks in an Observational Setting
Noa Ben-David, Sivan Sabato
We study active structure learning of Bayesian networks in an observational setting, in which there are external limitations on the number of variable values that can be observed f…
A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering
Tom Hess, Michal Moshkovitz, Sivan Sabato
We study k-median clustering under the sequential no-substitution setting. In this setting, a data stream is sequentially observed, and some of the points are selected by the algor…
Active Feature Selection for the Mutual Information Criterion
Shachar Schnapp, Sivan Sabato
We study active feature selection, a novel feature selection setting in which unlabeled data is available, but the budget for labels is limited, and the examples to label can be ac…
Approximating a Target Distribution using Weight Queries
Nadav Barak, Sivan Sabato
We consider a novel challenge: approximating a distribution without the ability to randomly sample from that distribution. We study how such an approximation can be obtained using…
Robust Learning from Discriminative Feature Feedback
Sanjoy Dasgupta, Sivan Sabato
Recent work introduced the model of learning from discriminative feature feedback, in which a human annotator not only provides labels of instances, but also identifies discriminat…
Universal Bayes consistency in metric spaces
Steve Hanneke, Aryeh Kontorovich, Sivan Sabato +1
We extend a recently proposed 1-nearest-neighbor based multiclass learning algorithm and prove that our modification is universally strongly Bayes-consistent in all metric spaces a…
Sequential no-Substitution k-Median-Clustering
Tom Hess, Sivan Sabato
We study the sample-based k-median clustering objective under a sequential setting without substitutions. In this setting, an i.i.d. sequence of examples is observed. An example ca…
Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions
Aryeh Kontorovich, Sivan Sabato, Roi Weiss
We examine the Bayes-consistency of a recently proposed 1-nearest-neighbor-based multiclass learning algorithm. This algorithm is derived from sample compression bounds and enjoys…
Active Nearest-Neighbor Learning in Metric Spaces
Aryeh Kontorovich, Sivan Sabato, Ruth Urner
We propose a pool-based non-parametric active learning algorithm for general metric spaces, called MArgin Regularized Metric Active Nearest Neighbor (MARMANN), which outputs a near…
Submodular Learning and Covering with Response-Dependent Costs
Sivan Sabato
We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the response to the action. We propose a natural greedy a…
Loss minimization and parameter estimation with heavy tails
Daniel Hsu, Sivan Sabato
This work studies applications and generalizations of a simple estimation technique that provides exponential concentration under heavy-tailed distributions, assuming only bounded…
Auditing: Active Learning with Outcome-Dependent Query Costs
Sivan Sabato, Anand D. Sarwate, Nathan Srebro
We propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. We study binary classification in an ext…
Feature Multi-Selection among Subjective Features
Sivan Sabato, Adam Kalai
When dealing with subjective, noisy, or otherwise nebulous features, the "wisdom of crowds" suggests that one may benefit from multiple judgments of the same feature on the same ob…
Efficient Active Learning of Halfspaces: an Aggressive Approach
Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
We study pool-based active learning of half-spaces. We revisit the aggressive approach for active learning in the realizable case, and show that it can be made efficient and practi…
Multiclass Learning Approaches: A Theoretical Comparison with Implications
Amit Daniely, Sivan Sabato, Shai Shalev Shwartz
We theoretically analyze and compare the following five popular multiclass classification methods: One vs. All, All Pairs, Tree-based classifiers, Error Correcting Output Codes (EC…
Active Learning of Halfspaces under a Margin Assumption
Alon Gonen, Sivan Sabato, Shai Shalev-Shwartz
We derive and analyze a new, efficient, pool-based active learning algorithm for halfspaces, called ALuMA. Most previous algorithms show exponential improvement in the label comple…
Multi-Instance Learning with Any Hypothesis Class
Sivan Sabato, Naftali Tishby
In the supervised learning setting termed Multiple-Instance Learning (MIL), the examples are bags of instances, and the bag label is a function of the labels of its instances. Typi…
Tight Sample Complexity of Large-Margin Learning
Sivan Sabato, Nathan Srebro, Naftali Tishby
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L_2 regularization: We introduce the γ-adapted-dimension, whic…