Shai Ben-David

NeurIPS Conference 2025 Conference Paper

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 learning arises in many real-world applications. Most existing work relies on the simplifying assumption that the positively labeled training data is drawn from the restriction of the data generating distribution to positively labeled instances and/or that the proportion of positively labeled points (a. k. a. the class prior) is known apriori to the learner. This paper provides a theoretical analysis of the statistical complexity of PU learning under a wider range of setups. Unlike most prior work, our study does not assume that the class prior is known to the learner. We prove upper and lower bounds on the required sample sizes (of both the positively labeled and the unlabeled samples).

TMLR Journal 2024 Journal Article

Continual Learning: Applications and the Road Forward

• Eli Verwimp
• Rahaf Aljundi
• Shai Ben-David
• Matthias Bethge
• Andrea Cossu
• Alexander Gepperth
• Tyler L. Hayes
• Eyke Hüllermeier

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 what was learned in the past. In this work, we take a step back, and ask: "Why should one care about continual learning in the first place?". We set the stage by examining recent continual learning papers published at four major machine learning conferences, and show that memory-constrained settings dominate the field. Then, we discuss five open problems in machine learning, and even though they might seem unrelated to continual learning at first sight, we show that continual learning will inevitably be part of their solution. These problems are model editing, personalization and specialization, on-device learning, faster (re-)training and reinforcement learning. Finally, by comparing the desiderata from these unsolved problems and the current assumptions in continual learning, we highlight and discuss four future directions for continual learning research. We hope that this work offers an interesting perspective on the future of continual learning, while displaying its potential value and the paths we have to pursue in order to make it successful. This work is the result of the many discussions the authors had at the Dagstuhl seminar on Deep Continual Learning, in March 2023.

NeurIPS Conference 2023 Conference Paper

Distribution Learnability and Robustness

• Shai Ben-David
• Alex Bie
• Gautam Kamath
• Tosca Lechner

We examine the relationship between learnability and robust learnability for the problem of distribution learning. We show that learnability implies robust learnability if the adversary can only perform additive contamination (and consequently, under Huber contamination), but not if the adversary is allowed to perform subtractive contamination. Thus, contrary to other learning settings (e. g. , PAC learning of function classes), realizable learnability does not imply agnostic learnability. We also explore related implications in the context of compression schemes and differentially private learnability.

NeurIPS Conference 2023 Conference Paper

Private Distribution Learning with Public Data: The View from Sample Compression

• Shai Ben-David
• Alex Bie
• Clément L Canonne
• Gautam Kamath
• Vikrant Singhal

We study the problem of private distribution learning with access to public data. In this setup, which we refer to as *public-private learning*, the learner is given public and private samples drawn from an unknown distribution $p$ belonging to a class $\mathcal Q$, with the goal of outputting an estimate of $p$ while adhering to privacy constraints (here, pure differential privacy) only with respect to the private samples. We show that the public-private learnability of a class $\mathcal Q$ is connected to the existence of a sample compression scheme for $\mathcal Q$, as well as to an intermediate notion we refer to as \emph{list learning}. Leveraging this connection: (1) approximately recovers previous results on Gaussians over $\mathbb R^d$; and (2) leads to new ones, including sample complexity upper bounds for arbitrary $k$-mixtures of Gaussians over $\mathbb R^d$, results for agnostic and distribution-shift resistant learners, as well as closure properties for public-private learnability under taking mixtures and products of distributions. Finally, via the connection to list learning, we show that for Gaussians in $\mathbb R^d$, at least $d$ public samples are necessary for private learnability, which is close to the known upper bound of $d+1$ public samples.

ICML Conference 2023 Conference Paper

Strategic Classification with Unknown User Manipulations

• Tosca Lechner
• Ruth Urner
• Shai Ben-David

In many human-centric applications for Machine Learning instances will adapt to a classifier after its deployment. The field of strategic classification deals with this issue by aiming for a classifier that balances the trade-off between correctness and robustness to manipulation. This task is made harder if the underlying manipulation structure (i. e. the set of manipulations available at every instance) is unknown to the learner. We propose a novel batch-learning setting in which we use unlabeled data from previous rounds to estimate the manipulation structure. We show that in this batch-learning setting it is possible to learn a close-to-optimal classifier in terms of the strategic loss even without knowing the feasible manipulations beforehand. In line with recent advances in the strategic classification literature, we do not assume a best-response from agents but only require that observed manipulations are feasible.

UAI Conference 2021 Conference Paper

Identifying regions of trusted predictions

• Nivasini Ananthakrishnan
• Shai Ben-David
• Tosca Lechner
• Ruth Urner

Quantifying the probability of a label prediction being correct on a given test point or a given sub-population enables users to better decide how to use and when to trust machine learning derived predictors. In this work, combining aspects of prior work on conformal predictions and selective classification, we provide a unifying framework for confidence requirements that allows for distinguishing between various sources of uncertainty in the learning process as well as various region specifications. We then consider a set of common prior assumptions on the data generating process and show how these allow learning justifiably trusted predictors.

STOC Conference 2021 Invited Paper

Learnability can be independent of set theory (invited paper)

• Shai Ben-David
• Pavel Hrubes
• Shay Moran
• Amir Shpilka
• Amir Yehudayoff

AAAI Conference 2018 Conference Paper

Clustering – What Both Theoreticians and Practitioners Are Doing Wrong

• Shai Ben-David

Unsupervised learning is widely recognized as one of the most important challenges facing machine learning nowadays. However, in spite of hundreds of papers on the topic being published every year, current theoretical understanding and practical implementations of such tasks, in particular of clustering, is very rudimentary. This note focuses on clustering. The first challenge I address is model selection - how should a user pick an appropriate clustering tool for a given clustering problem, and how should the parameters of such an algorithmic tool be tuned? In contrast with other common computational tasks, for clustering, different algorithms often yield drastically different outcomes. Therefore, the choice of a clustering algorithm may play a crucial role in the usefulness of an output clustering solution. However, currently there exists no methodical guidance for clustering tool selection for a given clustering task. I argue the severity of this problem and describe some recent proposals aiming to address this crucial lacuna.

NeurIPS Conference 2018 Conference Paper

Empirical Risk Minimization Under Fairness Constraints

• Michele Donini
• Luca Oneto
• Shai Ben-David
• John Shawe-Taylor
• Massimiliano Pontil

We address the problem of algorithmic fairness: ensuring that sensitive information does not unfairly influence the outcome of a classifier. We present an approach based on empirical risk minimization, which incorporates a fairness constraint into the learning problem. It encourages the conditional risk of the learned classifier to be approximately constant with respect to the sensitive variable. We derive both risk and fairness bounds that support the statistical consistency of our methodology. We specify our approach to kernel methods and observe that the fairness requirement implies an orthogonality constraint which can be easily added to these methods. We further observe that for linear models the constraint translates into a simple data preprocessing step. Experiments indicate that the method is empirically effective and performs favorably against state-of-the-art approaches.

NeurIPS Conference 2018 Conference Paper

Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes

• Hassan Ashtiani
• Shai Ben-David
• Nicholas Harvey
• Christopher Liaw
• Abbas Mehrabian
• Yaniv Plan

We prove that ϴ(k d^2 / ε^2) samples are necessary and sufficient for learning a mixture of k Gaussians in R^d, up to error ε in total variation distance. This improves both the known upper bounds and lower bounds for this problem. For mixtures of axis-aligned Gaussians, we show that O(k d / ε^2) samples suffice, matching a known lower bound. The upper bound is based on a novel technique for distribution learning based on a notion of sample compression. Any class of distributions that allows such a sample compression scheme can also be learned with few samples. Moreover, if a class of distributions has such a compression scheme, then so do the classes of products and mixtures of those distributions. The core of our main result is showing that the class of Gaussians in R^d has an efficient sample compression.

AAAI Conference 2018 Conference Paper

Sample-Efficient Learning of Mixtures

• Hassan Ashtiani
• Shai Ben-David
• Abbas Mehrabian

We consider PAC learning of probability distributions (a. k. a. density estimation), where we are given an i. i. d. sample generated from an unknown target distribution, and want to output a distribution that is close to the target in total variation distance. Let F be an arbitrary class of probability distributions, and let Fk denote the class of k-mixtures of elements of F. Assuming the existence of a method for learning F with sample complexity mF (ε), we provide a method for learning Fk with sample complexity O(k log k · mF (ε)/ε2 ). Our mixture learning algorithm has the property that, if the Flearner is proper and agnostic, then the Fk -learner would be proper and agnostic as well. This general result enables us to improve the best known sample complexity upper bounds for a variety of important mixture classes. First, we show that the class of mixtures of k axis-aligned Gaussians in Rd is PAC-learnable in the agnostic setting with O(kd/ε4 ) samples, which is tight in k and d up to logarithmic factors. Second, we show that the class of mixtures of k Gaussians in Rd is PAC-learnable in the agnostic setting with sample complexity O(kd2 /ε4 ), which improves the previous known bounds of O(k3 d2 /ε4 ) and O(k4 d4 /ε2 ) in its dependence on k and d. Finally, we show that the class of mixtures of k log-concave distributions over Rd is PAClearnable using O(d(d+5)/2 ε−(d+9)/2 k) samples.

JMLR Journal 2016 Journal Article

A Characterization of Linkage-Based Hierarchical Clustering

• Margareta Ackerman
• Shai Ben-David

The class of linkage-based algorithms is perhaps the most popular class of hierarchical algorithms. We identify two properties of hierarchical algorithms, and prove that linkage- based algorithms are the only ones that satisfy both of these properties. Our characterization clearly delineates the difference between linkage-based algorithms and other hierarchical methods. We formulate an intuitive notion of locality of a hierarchical algorithm that distinguishes between linkage-based and global hierarchical algorithms like bisecting $k$-means, and prove that popular divisive hierarchical algorithms produce clusterings that cannot be produced by any linkage-based algorithm. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

NeurIPS Conference 2016 Conference Paper

Clustering with Same-Cluster Queries

• Hassan Ashtiani
• Shrinu Kushagra
• Shai Ben-David

We propose a framework for Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to interact with a domain expert, asking whether two given instances belong to the same cluster or not. We study the query and computational complexity of clustering in this framework. We consider a setting where the expert conforms to a center-based clustering with a notion of margin. We show that there is a trade off between computational complexity and query complexity; We prove that for the case of $k$-means clustering (i. e. , when the expert conforms to a solution of $k$-means), having access to relatively few such queries allows efficient solutions to otherwise NP hard problems. In particular, we provide a probabilistic polynomial-time (BPP) algorithm for clustering in this setting that asks $O\big(k^2\log k + k\log n)$ same-cluster queries and runs with time complexity $O\big(kn\log n)$ (where $k$ is the number of clusters and $n$ is the number of instances). The success of the algorithm is guaranteed for data satisfying the margin condition under which, without queries, we show that the problem is NP hard. We also prove a lower bound on the number of queries needed to have a computationally efficient clustering algorithm in this setting.

MFCS Conference 2016 Invited Paper

How Far Are We From Having a Satisfactory Theory of Clustering?

• Shai Ben-David

This is an overview of the invited talk delivered at the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016).

JMLR Journal 2015 Journal Article

Multiclass Learnability and the ERM Principle

• Amit Daniely
• Sivan Sabato
• Shai Ben-David
• Shai Shalev-Shwartz

We study the sample complexity of multiclass prediction in several learning settings. For the PAC setting our analysis reveals a surprising phenomenon: In sharp contrast to binary classification, we show that there exist multiclass hypothesis classes for which some Empirical Risk Minimizers (ERM learners) have lower sample complexity than others. Furthermore, there are classes that are learnable by some ERM learners, while other ERM learners will fail to learn them. We propose a principle for designing good ERM learners, and use this principle to prove tight bounds on the sample complexity of learning symmetric multiclass hypothesis classes---classes that are invariant under permutations of label names. We further provide a characterization of mistake and regret bounds for multiclass learning in the online setting and the bandit setting, using new generalizations of Littlestone's dimension. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

UAI Conference 2015 Conference Paper

Representation Learning for Clustering: A Statistical Framework

• Hassan Ashtiani
• Shai Ben-David

We address the problem of communicating domain knowledge from a user to the designer of a clustering algorithm. We propose a protocol in which the user provides a clustering of a relatively small random sample of a data set. The algorithm designer then uses that sample to come up with a data representation under which kmeans clustering results in a clustering (of the full data set) that is aligned with the user’s clustering. We provide a formal statistical model for analyzing the sample complexity of learning a clustering representation with this paradigm. We then introduce a notion of capacity of a class of possible representations, in the spirit of the VCdimension, showing that classes of representations that have finite such dimension can be successfully learned with sample size error bounds, and end our discussion with an analysis of that dimension for classes of representations induced by linear embeddings.

ICML Conference 2014 Conference Paper

Clustering in the Presence of Background Noise

• Shai Ben-David
• Nika Haghtalab

We address the problem of noise management in clustering algorithms. Namely, issues that arise when on top of some cluster structure the data also contains an unstructured set of points. We consider how clustering algorithms can be “robustified" so that they recover the cluster structure in spite of the unstructured part of the input. We introduce some quantitative measures of such robustness that take into account the strength of the embedded cluster structure as well was the mildness of the noise subset. We propose a simple and efficient method to turn any centroid-based clustering algorithm into a noise-robust one, and prove robustness guarantees for our method with respect to these measures. We also prove that more straightforward ways of “robustifying” clustering algorithms fail to achieve similar guarantees.

ICML Conference 2013 Conference Paper

Monochromatic Bi-Clustering

• Sharon Wulff
• Ruth Urner
• Shai Ben-David

We propose a natural cost function for the bi-clustering task, the monochromatic cost. This cost function is suitable for detecting meaningful homogeneous bi-clusters based on categorical valued input matrices. Such tasks arise in many applications, such as the analysis of social networks and in systems-biology where researchers try to infer functional grouping of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problem. We present a polynomial time approximation algorithm for this bi-clustering task and complement this result by showing that finding (exact) optimal solutions is NP-hard. As far as we know, these are the first positive approximation guarantees and formal NP-hardness results for any bi-clustering optimization problem. In addition, we show that our optimization problem can be efficiently solved by deterministic annealing, yielding a promising heuristic for large problem instances.

ICML Conference 2012 Conference Paper

Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss

• Shai Ben-David
• David Loker
• Nathan Srebro
• Karthik Sridharan

AAAI Conference 2012 Conference Paper

Weighted Clustering

• Margareta Ackerman
• Shai Ben-David
• Simina Brânzei
• David Loker

We investigate a natural generalization of the classical clustering problem, considering clustering tasks in which different instances may have different weights. We conduct the first extensive theoretical analysis on the influence of weighted data on standard clustering algorithms in both the partitional and hierarchical settings, characterizing the conditions under which algorithms react to weights. Extending a recent framework for clustering algorithm selection, we propose intuitive properties that would allow users to choose between clustering algorithms in the weighted setting and classify algorithms accordingly.

ICML Conference 2011 Conference Paper

Access to Unlabeled Data can Speed up Prediction Time

• Ruth Urner
• Shai Shalev-Shwartz
• Shai Ben-David

IJCAI Conference 2011 Conference Paper

Discerning Linkage-Based Algorithms among Hierarchical Clustering Methods

• Margareta Ackerman
• Shai Ben-David

Selecting a clustering algorithm is a perplexing task. Yet since different algorithms may yield dramatically different outputs on the same data, the choice of algorithm is crucial. When selecting a clustering algorithm, users tend to focus on cost-related considerations (software purchasing costs, running times, etc). Differences concerning the output of the algorithms are not usually considered. Recently, a formal approach for selecting a clustering algorithm has been proposed (Ackerman, Ben-David, and Loker, NIPS 2010). The approach involves distilling abstract properties of the input-output behavior of different clustering paradigms and classifying algorithms based on these properties. In this paper, we extend this approach into the hierarchical setting. The class of linkage-based algorithms is perhaps the most popular class of hierarchical algorithms. We identify two properties of hierarchical algorithms, and prove that linkage-based algorithms are the only ones that satisfy both of these properties. Our characterization clearly delineates the difference between linkage-based algorithms and other hierarchical algorithms. We formulate an intuitive notion of locality of a hierarchical algorithm that distinguishes between linkage-based and "global" hierarchical algorithms like bisecting k-means, and prove that popular divisive hierarchical algorithms produce clusterings that cannot be produced by any linkage-based algorithm.

NeurIPS Conference 2010 Conference Paper

Towards Property-Based Classification of Clustering Paradigms

• Margareta Ackerman
• Shai Ben-David
• David Loker

Clustering is a basic data mining task with a wide variety of applications. Not surprisingly, there exist many clustering algorithms. However, clustering is an ill defined problem - given a data set, it is not clear what a “correct” clustering for that set is. Indeed, different algorithms may yield dramatically different outputs for the same input sets. Faced with a concrete clustering task, a user needs to choose an appropriate clustering algorithm. Currently, such decisions are often made in a very ad hoc, if not completely random, manner. Given the crucial effect of the choice of a clustering algorithm on the resulting clustering, this state of affairs is truly regrettable. In this paper we address the major research challenge of developing tools for helping users make more informed decisions when they come to pick a clustering tool for their data. This is, of course, a very ambitious endeavor, and in this paper, we make some first steps towards this goal. We propose to address this problem by distilling abstract properties of the input-output behavior of different clustering paradigms. In this paper, we demonstrate how abstract, intuitive properties of clustering functions can be used to taxonomize a set of popular clustering algorithmic paradigms. On top of addressing deterministic clustering algorithms, we also propose similar properties for randomized algorithms and use them to highlight functional differences between different common implementations of k-means clustering. We also study relationships between the properties, independent of any particular algorithm. In particular, we strengthen Kleinbergs famous impossibility result, while providing a simpler proof.

UAI Conference 2009 Conference Paper

A Uniqueness Theorem for Clustering

• Reza 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 data partitioning? ”, “Are there any principles governing all clustering paradigms? ”, “How should a user choose an appropriate clustering algorithm for a particular task? ”, etc. are almost completely unanswered by the existing body of clustering literature. We consider an axiomatic approach to the theory of Clustering. We adopt the framework of Kleinberg, [Kle03]. By relaxing one of Kleinberg’s clustering axioms, we sidestep his impossibility result and arrive at a consistent set of axioms. We suggest to extend these axioms, aiming to provide an axiomatic taxonomy of clustering paradigms. Such a taxonomy should provide users some guidance concerning the choice of the appropriate clustering paradigm for a given task. The main result of this paper is a set of abstract properties that characterize the Single-Linkage clustering function. This characterization result provides new insight into the properties of desired data groupings that make SingleLinkage the appropriate choice. We conclude by considering a taxonomy of clustering functions based on abstract properties that each satisfies.

NeurIPS Conference 2008 Conference Paper

Measures of Clustering Quality: A Working Set of Axioms for Clustering

• Shai Ben-David
• Margareta Ackerman

Aiming towards the development of a general clustering theory, we discuss abstract axiomatization for clustering. In this respect, we follow up on the work of Kelinberg, (Kleinberg) that showed an impossibility result for such axiomatization. We argue that an impossibility result is not an inherent feature of clustering, but rather, to a large extent, it is an artifact of the specific formalism used in Kleinberg. As opposed to previous work focusing on clustering functions, we propose to address clustering quality measures as the primitive object to be axiomatized. We show that principles like those formulated in Kleinberg's axioms can be readily expressed in the latter framework without leading to inconsistency. A clustering-quality measure is a function that, given a data set and its partition into clusters, returns a non-negative real number representing how strong' or conclusive' the clustering is. We analyze what clustering-quality measures should look like and introduce a set of requirements (`axioms') that express these requirement and extend the translation of Kleinberg's axioms to our framework. We propose several natural clustering quality measures, all satisfying the proposed axioms. In addition, we show that the proposed clustering quality can be computed in polynomial time.

TCS Journal 2007 Journal Article

Foreword

• Shai Ben-David
• John Case
• Thomas Zeugmann

NeurIPS Conference 2006 Conference Paper

Analysis of Representations for Domain Adaptation

• Shai Ben-David
• John Blitzer
• Koby Crammer
• Fernando Pereira

Discriminative learning methods for classification perform well when training and test data are drawn from the same distribution. In many situations, though, we have labeled training data for a source domain, and we wish to learn a classifier which performs well on a target domain with a different distribution. Under what conditions can we adapt a classifier trained on the source domain for use in the target domain? Intuitively, a good feature representation is a crucial factor in the success of domain adaptation. We formalize this intuition theoretically with a generalization bound for domain adaption. Our theory illustrates the tradeoffs inherent in designing a representation for domain adaptation and gives a new justification for a recently proposed model. It also points toward a promising new model for domain adaptation: one which explicitly minimizes the difference between the source and target domains, while at the same time maximizing the margin of the training set.

TCS Journal 2002 Journal Article

Hardness results for neural network approximation problems

• Peter L. Bartlett
• Shai Ben-David

We consider the problem of efficiently learning in two-layer neural networks. We investigate the computational complexity of agnostically learning with simple families of neural networks as the hypothesis classes. We show that it is NP-hard to find a linear threshold network of a fixed size that approximately minimizes the proportion of misclassified examples in a training set, even if there is a network that correctly classifies all of the training examples. In particular, for a training set that is correctly classified by some two-layer linear threshold network with k hidden units, it is NP-hard to find such a network that makes mistakes on a proportion smaller than c/k 2 of the examples, for some constant c. We prove a similar result for the problem of approximately minimizing the quadratic loss of a two-layer network with a sigmoid output unit.

JMLR Journal 2002 Journal Article

Limitations of Learning Via Embeddings in Euclidean Half Spaces

• Shai Ben-David
• Nadav Eiron
• Hans Ulrich Simon

The notion of embedding a class of dichotomies in a class of linear half spaces is central to the support vector machines paradigm. We examine the question of determining the minimal Euclidean dimension and the maximal margin that can be obtained when the embedded class has a finite VC dimension. We show that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in low-dimensional half spaces. (In fact, we show that the Euclidean dimension must be almost as high as the size of the instance space.) We strengthen this result even further by showing that an overwhelming majority of the family of finite concept classes of any constant VC dimension cannot be embedded in half spaces (of arbitrarily high Euclidean dimension) with a large margin. (In fact, the margin cannot be substantially larger than the margin achieved by the trivial embedding.) Furthermore, these bounds are robust in the sense that allowing each image half space to err on a small fraction of the instances does not imply a significant weakening of these dimension and margin bounds. Our results indicate that any universal learning machine, which transforms data into the Euclidean space and then applies linear (or large margin) classification, cannot enjoy any meaningful generalization guarantees that are based on either VC dimension or margins considerations. This failure of generalization bounds applies even to classes for which "straight forward" empirical risk minimization does enjoy meaningful generalization guarantees.

AIJ Journal 2000 Journal Article

A modal logic for subjective default reasoning

• Shai Ben-David
• Rachel Ben-Eliyahu-Zohary

In this paper we introduce DML: Default Modal Logic. DML is a logic endowed with a two-place modal connective that has the intended meaning of “If α, then normally β”. On top of providing a well-defined tool for analyzing common default reasoning, DML allows nesting of the default operator. We present a semantic framework in which many of the known default proof systems can be naturally characterized, and prove soundness and completeness theorems for several such proof systems. Our semantics is a “neighborhood modal semantics”, and it allows for subjective defaults, that is, defaults may vary among different worlds within the same model. The semantics has an appealing intuitive interpretation and may be viewed as a set-theoretic generalization of the probabilistic interpretations of default reasoning. We show that our semantics is most general in the sense that any modal semantics that is sound for some basic axioms for default reasoning is a special case of our semantics. Such a generality result may serve to provide a semantical analysis of the relative strength of different proof systems and to show the nonexistence of semantics with certain properties.

NeurIPS Conference 2000 Conference Paper

Efficient Learning of Linear Perceptrons

• Shai Ben-David
• Hans-Ulrich Simon

We consider the existence of efficient algorithms for learning the class of half-spaces in ~n in the agnostic learning model (Le. , mak(cid: 173) ing no prior assumptions on the example-generating distribution). The resulting combinatorial problem - finding the best agreement half-space over an input sample - is NP hard to approximate to within some constant factor. We suggest a way to circumvent this theoretical bound by introducing a new measure of success for such algorithms. An algorithm is IL-margin successful if the agreement ratio of the half-space it outputs is as good as that of any half-space once training points that are inside the IL-margins of its separating hyper-plane are disregarded. We prove crisp computational com(cid: 173) plexity results with respect to this success measure: On one hand, for every positive IL, there exist efficient (poly-time) IL-margin suc(cid: 173) cessful learning algorithms. On the other hand, we prove that unless P=NP, there is no algorithm that runs in time polynomial in the sample size and in 1/ IL that is IL-margin successful for all IL> O.

STOC Conference 1997 Conference Paper

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

• Shai Ben-David
• Nader H. Bshouty
• Eyal Kushilevitz

FOCS Conference 1993 Conference Paper

Scale-sensitive Dimensions, Uniform Convergence, and Learnability

• Noga Alon
• Shai Ben-David
• Nicolò Cesa-Bianchi
• David Haussler

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Gliveako-Cantelli classes. In this paper we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class. >

STOC Conference 1992 Conference Paper

Can Finite Samples Detect Singularities of Real-Valued Functions?

• Shai Ben-David

STOC Conference 1990 Conference Paper

On the Power of Randomization in Online Algorithms (Extended Abstract)

• Shai Ben-David
• Allan Borodin
• Richard M. Karp
• Gábor Tardos
• Avi Wigderson

STOC Conference 1989 Conference Paper

On the Theory of Average Case Complexity

• Shai Ben-David
• Benny Chor
• Oded Goldreich 0001
• Michael Luby

This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: the equivalence of search and decision problems in the context of average case complexity; an initial analysis of the structure of distributional-NP under reductions which preserve average polynomial-time; a proof that if all distributional-NP is in average polynomial-time then non-deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy); definitions and basic theorems regarding other complexity classes such as average log-space.