Shai Ben-David

Nicholas J. A. Harvey

Christopher Liaw

Gintare Karolina Dziugaite

Yaniv Plan

J. ACM, 2020

Enforcing Interpretability and its Statistical Impacts: Trade-offs between Accuracy and Interpretability.

[BibT_eX]

[DOI]

Daniel M. Roy

CoRR, 2020

On Learnability wih Computable Learners.

[BibT_eX]

[DOI]

Sushant Agarwal

Nivasini Ananthakrishnan

Tosca Lechner

Proceedings of the Algorithmic Learning Theory, 2020

2019

Author Correction: Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

A Semi-Supervised Framework of Clustering Selection for De-Duplication.

[BibT_eX]

[DOI]

Proceedings of the 35th IEEE International Conference on Data Engineering, 2019

When can unlabeled data improve the learning rate?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Semi-supervised clustering for de-duplication.

[BibT_eX]

[DOI]

Ihab F. Ilyas

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Empirical Risk Minimization Under Fairness Constraints.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

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

[BibT_eX]

[DOI]

Nicholas J. A. Harvey

Christopher Liaw

Yaniv Plan

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Multi-task {K}ernel {L}earning Based on {P}robabilistic {L}ipschitzness.

[BibT_eX]

[DOI]

Anastasia Pentina

Proceedings of the Algorithmic Learning Theory, 2018

Clustering - What Both Theoreticians and Practitioners Are Doing Wrong.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

Sample-Efficient Learning of Mixtures.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

Provably noise-robust, regularised k-means clustering.

[BibT_eX]

[DOI]

CoRR, 2017

A learning problem that is independent of the set theory ZFC axioms.

[BibT_eX]

[DOI]

CoRR, 2017

Agnostic Distribution Learning via Compression.

[BibT_eX]

[DOI]

CoRR, 2017

2016

A Characterization of Linkage-Based Hierarchical Clustering.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2016

Foundations of Unsupervised Learning (Dagstuhl Seminar 16382).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

Clustering with Same-Cluster Queries.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

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

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Finding Meaningful Cluster Structure Amidst Background Noise.

[BibT_eX]

[DOI]

Samira Samadi

Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

On Version Space Compression.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2015

Clustering is Easy When ....What?

[BibT_eX]

[DOI]

CoRR, 2015

2 Notes on Classes with Vapnik-Chervonenkis Dimension 1.

[BibT_eX]

[DOI]

CoRR, 2015

Computational Feasibility of Clustering under Clusterability Assumptions.

[BibT_eX]

[DOI]

CoRR, 2015

Representation Learning for Clustering: A Statistical Framework.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015

Hierarchical Label Queries with Data-Dependent Partitions.

[BibT_eX]

[DOI]

Samory Kpotufe

Proceedings of The 28th Conference on Learning Theory, 2015

Multi-task and Lifelong Learning of Kernels.

[BibT_eX]

[DOI]

Anastasia Pentina

Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

Information Preserving Dimensionality Reduction.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory - 26th International Conference, 2015

2014

Domain adaptation-can quantity compensate for quality?

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2014

The sample complexity of agnostic learning with deterministic labels.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2014

Clustering in the Presence of Background Noise.

[BibT_eX]

[DOI]

Nika Haghtalab

Proceedings of the 31th International Conference on Machine Learning, 2014

The sample complexity of agnostic learning under deterministic labels.

[BibT_eX]

[DOI]

Proceedings of The 27th Conference on Learning Theory, 2014

Understanding Machine Learning - From Theory to Algorithms.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 978-1-10-705713-5, 2014

2013

A theoretical approach to the clustering selection problem.

[BibT_eX]

[DOI]

Proceedings of the 4th MultiClust Workshop on Multiple Clusterings, 2013

Monochromatic Bi-Clustering.

[BibT_eX]

[DOI]

Sharon Wulff

Proceedings of the 30th International Conference on Machine Learning, 2013

PLAL: Cluster-based active learning.

[BibT_eX]

[DOI]

Sharon Wulff

Proceedings of the COLT 2013, 2013

Clustering Oligarchies.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, 2013

2012

Learning from Weak Teachers.

[BibT_eX]

[DOI]

Ohad Shamir

Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012

Theoretical analysis of domain adaptation - current state of the art.

[BibT_eX]

[DOI]

Proceedings of the 2012 Symposium on Machine Learning in Speech and Language Processing, 2012

Domain Adaptation--Can Quantity compensate for Quality?.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2012

Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss.

[BibT_eX]

[DOI]

Proceedings of the 29th International Conference on Machine Learning, 2012

On the Hardness of Domain Adaptation and the Utility of Unlabeled Target Samples.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

Weighted Clustering.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011

Multiclass Learnability and the ERM principle.

[BibT_eX]

[DOI]

Proceedings of the COLT 2011, 2011

Discerning Linkage-Based Algorithms among Hierarchical Clustering Methods.

[BibT_eX]

[DOI]

Proceedings of the IJCAI 2011, 2011

Access to Unlabeled Data can Speed up Prediction Time.

[BibT_eX]

[DOI]

Proceedings of the 28th International Conference on Machine Learning, 2011

Learning a Classifier when the Labeling Is Known.

[BibT_eX]

[DOI]

Shalev Ben-David

Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010

A theory of learning from different domains.

[BibT_eX]

[DOI]

Jennifer Wortman Vaughan

Mach. Learn., 2010

Impossibility Theorems for Domain Adaptation.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, 2010

Towards Property-Based Classification of Clustering Paradigms.

[BibT_eX]

[DOI]

David Loker

Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

ProbClean: A probabilistic duplicate detection system.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on Data Engineering, 2010

Characterization of Linkage-based Clustering.

[BibT_eX]

[DOI]

David Loker

Proceedings of the COLT 2010, 2010

2009

Modeling and Querying Possible Repairs in Duplicate Detection.

[BibT_eX]

[DOI]

Proc. VLDB Endow., 2009

Learning Low Density Separators.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009

Clusterability: A Theoretical Study.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009

A Uniqueness Theorem for Clustering.

[BibT_eX]

[DOI]

Reza Zadeh

Proceedings of the UAI 2009, 2009

Theory-Practice Interplay in Machine Learning - Emerging Theoretical Challenges.

[BibT_eX]

[DOI]

Proceedings of the Machine Learning and Knowledge Discovery in Databases, 2009

RTTS: towards enterprise-level real-time speech transcription and translation services.

[BibT_eX]

[DOI]

Proceedings of the 10th Annual Conference of the International Speech Communication Association, 2009

Agnostic Online Learning.

[BibT_eX]

[DOI]

Proceedings of the COLT 2009, 2009

2008

A notion of task relatedness yielding provable multiple-task learning guarantees.

[BibT_eX]

[DOI]

Reba Schuller Borbely

Mach. Learn., 2008

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Does Unlabeled Data Provably Help? Worst-case Analysis of the Sample Complexity of Semi-Supervised Learning.

[BibT_eX]

[DOI]

Tyler Lu

Proceedings of the 21st Annual Conference on Learning Theory, 2008

Relating Clustering Stability to Properties of Cluster Boundaries.

[BibT_eX]

[DOI]

Ulrike von Luxburg

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

Foreword.

[BibT_eX]

[DOI]

John Case

Thomas Zeugmann

Theor. Comput. Sci., 2007

A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering.

[BibT_eX]

[DOI]

Mach. Learn., 2007

Stability of k -Means Clustering.

[BibT_eX]

[DOI]

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Nonparametric change detection and estimation in large-scale sensor networks.

[BibT_eX]

[DOI]

Ting He

Lang Tong

IEEE Trans. Signal Process., 2006

Estimation of the number of operating sensors in large-scale sensor networks with mobile access.

[BibT_eX]

[DOI]

Cristian Budianu

Lang Tong

IEEE Trans. Signal Process., 2006

Alternative Measures of Computational Complexity with Applications to Agnostic Learning.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2006

Analysis of Representations for Domain Adaptation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 19, 2006

Learning Bounds for Support Vector Machines with Learned Kernels.

[BibT_eX]

[DOI]

Nathan Srebro

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

A Sober Look at Clustering Stability.

[BibT_eX]

[DOI]

Ulrike von Luxburg

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005

Nonparametric change detection in 2D random sensor field.

[BibT_eX]

[DOI]

Ting He

Lang Tong

Proceedings of the 2005 IEEE International Conference on Acoustics, 2005

2004

Detecting Change in Data Streams.

[BibT_eX]

[DOI]

Daniel Kifer

Johannes Gehrke

Proceedings of the (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, Toronto, Canada, August 31, 2004

A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering.

[BibT_eX]

[DOI]

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

On the difficulty of approximately maximizing agreements.

[BibT_eX]

[DOI]

Philip M. Long

J. Comput. Syst. Sci., 2003

Exploiting Task Relatedness for Mulitple Task Learning.

[BibT_eX]

[DOI]

Reba Schuller

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Hardness results for neural network approximation problems.

[BibT_eX]

[DOI]

Peter L. Bartlett

Theor. Comput. Sci., 2002

Limitations of Learning Via Embeddings in Euclidean Half Spaces.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2002

The Computational Complexity of Densest Region Detection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

A theoretical framework for learning from a pool of disparate data sources.

[BibT_eX]

[DOI]

Johannes Gehrke

Reba Schuller

Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002

2001

Agnostic Boosting.

[BibT_eX]

[DOI]

Philip M. Long

Proceedings of the Computational Learning Theory, 2001

2000

Learning Changing Concepts by Exploiting the Structure of Change.

[BibT_eX]

[DOI]

Peter L. Bartlett

Sanjeev R. Kulkarni

Mach. Learn., 2000

A Note on Non-complete Problems in NPImage.

[BibT_eX]

[DOI]

Klaus Meer

Christian Michaux

J. Complex., 2000

A Note On Vc-Dimension And Measure Of Sets Of Reals.

[BibT_eX]

[DOI]

Leonid Gurvits

Comb. Probab. Comput., 2000

A modal logic for subjective default reasoning.

[BibT_eX]

[DOI]

Rachel Ben-Eliyahu-Zohary

Artif. Intell., 2000

Efficient Learning of Linear Perceptrons.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 13, 2000

Localized Boosting.

[BibT_eX]

Ron Meir

Ran El-Yaniv

Proceedings of the Thirteenth Annual Conference on Computational Learning Theory (COLT 2000), June 28, 2000

1999

VC-Dimension Analysis of Object Recognition Tasks.

[BibT_eX]

[DOI]

J. Math. Imaging Vis., 1999

1998

Localization vs. Identification of Semi-Algebraic Sets.

[BibT_eX]

[DOI]

Mach. Learn., 1998

Self-Directed Learning and Its Relation to the VC-Dimension and to Teacher-Directed Learning.

[BibT_eX]

[DOI]

Mach. Learn., 1998

Learning with Restricted Focus of Attention.

[BibT_eX]

[DOI]

Eli Dichterman

J. Comput. Syst. Sci., 1998

On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

[BibT_eX]

[DOI]

Anna Gringauze

Electron. Colloquium Comput. Complex., 1998

Combinatorial Variability of Vapnik-chervonenkis Classes with Applications to Sample Compression Schemes.

[BibT_eX]

[DOI]

Ami Litman

Discret. Appl. Math., 1998

Can Finite Samples Detect Singularities of Reao-Valued Functions?

[BibT_eX]

[DOI]

Algorithmica, 1998

1997

Online Learning versus Offline Learning.

[BibT_eX]

[DOI]

Mach. Learn., 1997

Learning Distributions by Their Density Levels: A Paradigm for Learning without a Teacher.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

Scale-sensitive dimensions, uniform convergence, and learnability.

[BibT_eX]

[DOI]

J. ACM, 1997

1996

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

[BibT_eX]

[DOI]

Nader H. Bshouty

Electron. Colloquium Comput. Complex., 1996

1995

A Parametrization Scheme for Classifying Models of PAC Learnability

[BibT_eX]

[DOI]

Gyora M. Benedek

Inf. Comput., July, 1995

Learning by Distances

[BibT_eX]

[DOI]

Alon Itai

Inf. Comput., March, 1995

Characterizations of Learnability for Classes of {0, ..., n}-Valued Functions.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1995

A Note on VC-Dimension and Measures of Sets of Reals.

[BibT_eX]

[DOI]

Leonid Gurvits

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

On Self-Directed Learning.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

On the Power of Randomization in On-Line Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 1994

A New Measure for the Study of On-Line Algorithms.

[BibT_eX]

[DOI]

Allan Borodin

Algorithmica, 1994

Applying VC-dimension Analysis To Object Recognition.

[BibT_eX]

[DOI]

Proceedings of the Computer Vision, 1994

On Ultrafilters and NP.

[BibT_eX]

[DOI]

Mauricio Karchmer

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

Learnability with Restricted Focus of Attention guarantees Noise-Tolerance.

[BibT_eX]

[DOI]

Eli Dichterman

Proceedings of the Algorithmic Learning Theory, 1994

Applying VC-Dimension Analysis To 3D Object Recognition from Perspective Projections.

[BibT_eX]

[DOI]

Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31, 1994

1993

On Learning in the Limit and Non-Uniform (epsilon, delta)-Learning.

[BibT_eX]

[DOI]

Michal Jacovi

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992

On the Theory of Average Case Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Can Finite Samples Detect Singularities of Real-Valued Functions?

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Characterizations of Learnability for Classes of {O, ..., n}-Valued Functions.

[BibT_eX]

[DOI]

Nicolò Cesa-Bianchi

Philip M. Long

Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991

On the Limitation of the Global Time Assumption in Distributed Systems (Extended Abstract).

[BibT_eX]

[DOI]

Uri Abraham

Shlomo Moran

Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

1990

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

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

1989

A Parametrization Scheme for Classifying Models of Learnability.

[BibT_eX]

[DOI]

Gyora M. Benedek

Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

On the Theory of Average Case Complexity (abstract).

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

The Global Time Assumption and Semantics for Concurrent Systems.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

1986

תכונות קומבינטוריות של מונים עוקבים לסינגולריים (Combinatorial properties of successors of singular Cardinals.).

[BibT_eX]

[DOI]

PhD thesis, 1986

The Weak □* is Really Weaker than the Full □.

[BibT_eX]

[DOI]

Menachem Magidor

J. Symb. Log., 1986

Souslin trees and successors of singular cardinals.

[BibT_eX]

[DOI]