b'Shay Moran'

research

∙ 07/05/2023

Universal Rates for Multiclass Learning

We study universal rates for multiclass classification, establishing the...

0 Steve Hanneke, et al. ∙

research

∙ 07/02/2023

Multiclass Boosting: Simple and Intuitive Weak Learning Criteria

We study a generalization of boosting to the multiclass setting. We intr...

0 Nataly Brukhim, et al. ∙

research

∙ 06/22/2023

Adversarial Resilience in Sequential Prediction via Abstention

We study the problem of sequential prediction in the stochastic setting ...

0 Surbhi Goel, et al. ∙

research

∙ 05/24/2023

Can Copyright be Reduced to Privacy?

There is an increasing concern that generative AI models may produce out...

0 Niva Elkin-Koren, et al. ∙

research

∙ 05/23/2023

Statistical Indistinguishability of Learning Algorithms

When two different parties use the same learning rule on their own data,...

0 Alkis Kalavasis, et al. ∙

research

∙ 04/08/2023

A Unified Characterization of Private Learnability via Graph Theory

We provide a unified framework for characterizing pure and approximate d...

0 Noga Alon, et al. ∙

research

∙ 04/07/2023

Replicability and stability in learning

Replicability is essential in science as it allows us to validate and ve...

0 Zachary Chase, et al. ∙

research

∙ 03/27/2023

List Online Classification

We study multiclass online prediction where the learner can predict usin...

0 Shay Moran, et al. ∙

research

∙ 02/27/2023

On Differentially Private Online Predictions

In this work we introduce an interactive variant of joint differential p...

0 Haim Kaplan, et al. ∙

research

∙ 02/27/2023

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

A classical result in online learning characterizes the optimal mistake ...

0 Yuval Filmus, et al. ∙

research

∙ 01/05/2023

Diagonalization Games

We study several variants of a combinatorial game which is based on Cant...

0 Noga Alon, et al. ∙

research

∙ 12/09/2022

The unstable formula theorem revisited

We first prove that Littlestone classes, those which model theorists cal...

0 Maryanthe Malliaris, et al. ∙

research

∙ 10/06/2022

On Optimal Learning Under Targeted Data Poisoning

Consider the task of learning a hypothesis class ℋ in the presence of an...

0 Steve Hanneke, et al. ∙

research

∙ 08/31/2022

Fine-Grained Distribution-Dependent Learning Curves

Learning curves plot the expected error of a learning algorithm as a fun...

0 Olivier Bousquet, et al. ∙

research

∙ 07/01/2022

Integral Probability Metrics PAC-Bayes Bounds

We present a PAC-Bayes-style generalization bound which enables the repl...

0 Ron Amit, et al. ∙

research

∙ 06/29/2022

Understanding Generalization via Leave-One-Out Conditional Mutual Information

We study the mutual information between (certain summaries of) the outpu...

0 Mahdi Haghifam, et al. ∙

research

∙ 06/09/2022

A Resilient Distributed Boosting Algorithm

Given a learning task where the data is distributed among several partie...

0 Yuval Filmus, et al. ∙

research

∙ 04/10/2022

Active Learning with Label Comparisons

Supervised learning typically relies on manual annotation of the true la...

0 Gal Yona, et al. ∙

research

∙ 03/21/2022

How Expressive Are Friendly School Partitions?

A natural procedure for assigning students to classes in the beginning o...

0 Josef Minařík, et al. ∙

research

∙ 03/03/2022

A Characterization of Multiclass Learnability

A seminal result in learning theory characterizes the PAC learnability o...

0 Nataly Brukhim, et al. ∙

research

∙ 02/10/2022

Monotone Learning

The amount of training-data is one of the key factors which determines t...

0 Olivier Bousquet, et al. ∙

research

∙ 11/19/2021

Uniform Brackets, Containers, and Combinatorial Macbeath Regions

We study the connections between three seemingly different combinatorial...

0 Kunal Dutta, et al. ∙

research

∙ 11/09/2021

Towards a Unified Information-Theoretic Framework for Generalization

In this work, we investigate the expressiveness of the "conditional mutu...

0 Mahdi Haghifam, et al. ∙

research

∙ 08/17/2021

Statistically Near-Optimal Hypothesis Selection

Hypothesis Selection is a fundamental distribution learning problem wher...

4 Olivier Bousquet, et al. ∙

research

∙ 08/12/2021

Agnostic Online Learning and Excellent Sets

We use algorithmic methods from online learning to revisit a key idea fr...

3 Maryanthe Malliaris, et al. ∙

research

∙ 07/18/2021

A Theory of PAC Learnability of Partial Concept Classes

We extend the theory of PAC learning in a way which allows to model a ri...

17 Noga Alon, et al. ∙

research

∙ 02/02/2021

Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games

Which classes can be learned properly in the online model? – that is, by...

0 Steve Hanneke, et al. ∙

research

∙ 01/22/2021

Adversarial Laws of Large Numbers and Optimal Regret in Online Classification

Laws of large numbers guarantee that given a large enough sample from so...

6 Noga Alon, et al. ∙

research

∙ 11/09/2020

A Theory of Universal Learning

How quickly can a given class of concepts be learned from examples? It i...

0 Olivier Bousquet, et al. ∙

research

∙ 11/05/2020

On the Information Complexity of Proper Learners for VC Classes in the Realizable Case

We provide a negative resolution to a conjecture of Steinke and Zakynthi...

0 Mahdi Haghifam, et al. ∙

research

∙ 08/01/2020

Learning from Mixtures of Private and Public Populations

We initiate the study of a new model of supervised learning under privac...

0 Raef Bassily, et al. ∙

research

∙ 06/24/2020

A Limitation of the PAC-Bayes Framework

PAC-Bayes is a useful framework for deriving generalization bounds which...

0 Roi Livni, et al. ∙

research

∙ 05/24/2020

Proper Learning, Helly Number, and an Optimal SVM Bound

The classical PAC sample complexity bounds are stated for any Empirical ...

0 Olivier Bousquet, et al. ∙

research

∙ 04/23/2020

Private Query Release Assisted by Public Data

We study the problem of differentially private query release assisted by...

0 Raef Bassily, et al. ∙

research

∙ 03/10/2020

Closure Properties for Private Classification and Online Prediction

Let H be a class of boolean functions and consider acomposed class H' th...

0 Noga Alon, et al. ∙

research

∙ 03/02/2020

Online Agnostic Boosting via Regret Minimization

Boosting is a widely used machine learning approach based on the idea of...

0 Nataly Brukhim, et al. ∙

research

∙ 03/01/2020

An Equivalence Between Private Classification and Online Prediction

We prove that every concept class with finite Littlestone dimension can ...

0 Mark Bun, et al. ∙

research

∙ 01/31/2020

Boosting Simple Learners

We consider boosting algorithms under the restriction that the weak lear...

6 Noga Alon, et al. ∙

research

∙ 10/25/2019

Limits of Private Learning with Access to Public Data

We consider learning problems where the training set consists of two typ...

10 Noga Alon, et al. ∙

research

∙ 09/08/2019

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility

We study the Convex Set Disjointness (CSD) problem, where two players ha...

0 Mark Braverman, et al. ∙

research

∙ 05/29/2019

An adaptive nearest neighbor rule for classification

We introduce a variant of the k-nearest neighbor classifier in which k i...

6 Akshay Balsubramani, et al. ∙

research

∙ 05/27/2019

Private Learning Implies Online Learning: An Efficient Reduction

We study the relationship between the notions of differentially private ...

0 Alon Gonen, et al. ∙

research

∙ 02/27/2019

Private Center Points and Learning of Halfspaces

We present a private learner for halfspaces over an arbitrary finite dom...

0 Amos Beimel, et al. ∙

research

∙ 02/13/2019

Learning and Generalization for Matching Problems

We study a classic algorithmic problem through the lens of statistical l...

0 Alon Cohen, et al. ∙

research

∙ 02/10/2019

The Optimal Approximation Factor in Density Estimation

Consider the following problem: given two arbitrary densities q_1,q_2 an...

16 Olivier Bousquet, et al. ∙

research

∙ 02/09/2019

Passing Tests without Memorizing: Two Models for Fooling Discriminators

We introduce two mathematical frameworks for foolability in the context ...

0 Olivier Bousquet, et al. ∙

research

∙ 12/05/2018

Unlabeled sample compression schemes and corner peelings for ample and maximum classes

We examine connections between combinatorial notions that arise in machi...

0 Jérémie Chalopin, et al. ∙

research

∙ 11/06/2018

The entropy of lies: playing twenty questions with a liar

`Twenty questions' is a guessing game played by two players: Bob thinks ...

0 Yuval Dagan, et al. ∙

research

∙ 06/14/2018

A Sauer-Shelah-Perles Lemma for Sumsets

We show that any family of subsets A⊆ 2^[n] satisfies A≤ O(n^d/2), wher...

0 Zeev Dvir, et al. ∙

research

∙ 06/14/2018

On the Perceptron's Compression

We study and provide exposition to several phenomena that are related to...

0 Shay Moran, et al. ∙

Shay Moran

Featured Co-authors