research
∙
07/05/2023
Universal Rates for Multiclass Learning
We study universal rates for multiclass classification, establishing the...
share
research
∙
07/02/2023
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
We study a generalization of boosting to the multiclass setting. We intr...
research
∙
06/22/2023
Adversarial Resilience in Sequential Prediction via Abstention
We study the problem of sequential prediction in the stochastic setting ...
research
∙
05/24/2023
Can Copyright be Reduced to Privacy?
There is an increasing concern that generative AI models may produce out...
research
∙
05/23/2023
Statistical Indistinguishability of Learning Algorithms
When two different parties use the same learning rule on their own data,...
research
∙
04/08/2023
A Unified Characterization of Private Learnability via Graph Theory
We provide a unified framework for characterizing pure and approximate d...
research
∙
04/07/2023
Replicability and stability in learning
Replicability is essential in science as it allows us to validate and ve...
research
∙
03/27/2023
List Online Classification
We study multiclass online prediction where the learner can predict usin...
research
∙
02/27/2023
On Differentially Private Online Predictions
In this work we introduce an interactive variant of joint differential p...
research
∙
02/27/2023
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
A classical result in online learning characterizes the optimal mistake ...
research
∙
01/05/2023
Diagonalization Games
We study several variants of a combinatorial game which is based on Cant...
research
∙
12/09/2022
The unstable formula theorem revisited
We first prove that Littlestone classes, those which model theorists cal...
research
∙
10/06/2022
On Optimal Learning Under Targeted Data Poisoning
Consider the task of learning a hypothesis class ℋ in the presence of an...
research
∙
08/31/2022
Fine-Grained Distribution-Dependent Learning Curves
Learning curves plot the expected error of a learning algorithm as a fun...
research
∙
07/01/2022
Integral Probability Metrics PAC-Bayes Bounds
We present a PAC-Bayes-style generalization bound which enables the repl...
research
∙
06/29/2022
Understanding Generalization via Leave-One-Out Conditional Mutual Information
We study the mutual information between (certain summaries of) the outpu...
research
∙
06/09/2022
A Resilient Distributed Boosting Algorithm
Given a learning task where the data is distributed among several partie...
research
∙
04/10/2022
Active Learning with Label Comparisons
Supervised learning typically relies on manual annotation of the true la...
research
∙
03/21/2022
How Expressive Are Friendly School Partitions?
A natural procedure for assigning students to classes in the beginning o...
research
∙
03/03/2022
A Characterization of Multiclass Learnability
A seminal result in learning theory characterizes the PAC learnability o...
research
∙
02/10/2022
Monotone Learning
The amount of training-data is one of the key factors which determines t...
research
∙
11/19/2021
Uniform Brackets, Containers, and Combinatorial Macbeath Regions
We study the connections between three seemingly different combinatorial...
research
∙
11/09/2021
Towards a Unified Information-Theoretic Framework for Generalization
In this work, we investigate the expressiveness of the "conditional mutu...
research
∙
08/17/2021
Statistically Near-Optimal Hypothesis Selection
Hypothesis Selection is a fundamental distribution learning problem wher...
research
∙
08/12/2021
Agnostic Online Learning and Excellent Sets
We use algorithmic methods from online learning to revisit a key idea fr...
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...
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...
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...
research
∙
11/09/2020
A Theory of Universal Learning
How quickly can a given class of concepts be learned from examples? It i...
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...
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...
research
∙
06/24/2020
A Limitation of the PAC-Bayes Framework
PAC-Bayes is a useful framework for deriving generalization bounds which...
research
∙
05/24/2020
Proper Learning, Helly Number, and an Optimal SVM Bound
The classical PAC sample complexity bounds are stated for any Empirical ...
research
∙
04/23/2020
Private Query Release Assisted by Public Data
We study the problem of differentially private query release assisted by...
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...
research
∙
03/02/2020
Online Agnostic Boosting via Regret Minimization
Boosting is a widely used machine learning approach based on the idea of...
research
∙
03/01/2020
An Equivalence Between Private Classification and Online Prediction
We prove that every concept class with finite Littlestone dimension can ...
research
∙
01/31/2020
Boosting Simple Learners
We consider boosting algorithms under the restriction that the weak lear...
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...
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...
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...
research
∙
05/27/2019
Private Learning Implies Online Learning: An Efficient Reduction
We study the relationship between the notions of differentially private ...
research
∙
02/27/2019
Private Center Points and Learning of Halfspaces
We present a private learner for halfspaces over an arbitrary finite dom...
research
∙
02/13/2019
Learning and Generalization for Matching Problems
We study a classic algorithmic problem through the lens of statistical l...
research
∙
02/10/2019
The Optimal Approximation Factor in Density Estimation
Consider the following problem: given two arbitrary densities q_1,q_2 an...
research
∙
02/09/2019
Passing Tests without Memorizing: Two Models for Fooling Discriminators
We introduce two mathematical frameworks for foolability in the context ...
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...
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 ...
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...
research
∙
06/14/2018