research
∙
07/07/2023
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
In this work, we aim to characterize the statistical complexity of reali...
share
research
∙
07/05/2023
Universal Rates for Multiclass Learning
We study universal rates for multiclass classification, establishing the...
research
∙
06/22/2023
Adversarial Resilience in Sequential Prediction via Abstention
We study the problem of sequential prediction in the stochastic setting ...
research
∙
04/29/2023
Limits of Model Selection under Transfer Learning
Theoretical studies on transfer learning or domain adaptation have so fa...
research
∙
04/06/2023
Reliable Learning for Test-time Attacks and Distribution Shift
Machine learning algorithms are often used in environments which are not...
research
∙
02/27/2023
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
A classical result in online learning characterizes the optimal mistake ...
research
∙
02/14/2023
Non-stationary Contextual Bandits and Universal Learning
We study the fundamental limits of learning in contextual bandits, where...
research
∙
12/31/2022
Contextual Bandits and Optimistically Universal Learning
We consider the contextual bandit problem on general action and context ...
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
∙
09/15/2022
Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization
We present a minimax optimal learner for the problem of learning predict...
research
∙
08/31/2022
Fine-Grained Distribution-Dependent Learning Curves
Learning curves plot the expected error of a learning algorithm as a fun...
research
∙
06/26/2022
Adversarially Robust Learning of Real-Valued Functions
We study robustness to test-time adversarial attacks in the regression s...
research
∙
03/11/2022
Universally Consistent Online Learning with Arbitrarily Dependent Responses
This work provides an online learning rule that is universally consisten...
research
∙
03/08/2022
Robustly-reliable learners under poisoning attacks
Data poisoning attacks, in which an adversary corrupts a training set wi...
research
∙
02/11/2022
A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability
We study the problem of semi-supervised learning of an adversarially-rob...
research
∙
01/21/2022
Universal Online Learning with Unbounded Losses: Memory Is All You Need
We resolve an open problem of Hanneke on the subject of universally cons...
research
∙
10/20/2021
Transductive Robust Learning Guarantees
We study the problem of adversarially robust learning in the transductiv...
research
∙
07/20/2021
Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?
This open problem asks whether there exists an online learning algorithm...
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
∙
03/01/2021
Robust learning under clean-label attack
We study the problem of robust learning under clean-label data-poisoning...
research
∙
02/03/2021
Adversarially Robust Learning with Unknown Perturbation Sets
We study the problem of learning predictors that are robust to adversari...
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
∙
11/09/2020
A Theory of Universal Learning
How quickly can a given class of concepts be learned from examples? It i...
research
∙
10/22/2020
Reducing Adversarially Robust Learning to Non-Robust PAC Learning
We study the problem of reducing adversarially robust learning to standa...
research
∙
06/29/2020
A No-Free-Lunch Theorem for MultiTask Learning
Multitask learning and related areas such as multi-source domain adaptat...
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
∙
02/12/2020
On the Value of Target Data in Transfer Learning
We aim to understand the value of additional labeled or unlabeled target...
research
∙
06/24/2019
Universal Bayes consistency in metric spaces
We show that a recently proposed 1-nearest-neighbor-based multiclass lea...
research
∙
02/12/2019
VC Classes are Adversarially Robustly Learnable, but Only Improperly
We study the question of learning an adversarially robust predictor. We ...
research
∙
10/03/2018
Agnostic Sample Compression for Linear Regression
We obtain the first positive results for bounded sample compression in t...
research
∙
05/21/2018
Sample Compression for Real-Valued Learners
We give an algorithmically efficient version of the learner-to-compressi...
research
∙
05/21/2018
A New Lower Bound for Agnostic Learning with Sample Compression Schemes
We establish a tight characterization of the worst-case rates for the ex...
research
∙
02/20/2018
Actively Avoiding Nonsense in Generative Models
A generative model may generate utter nonsense when it is fit to maximiz...
research
∙
06/05/2017
Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes
This work initiates a general study of learning and generalization witho...
research
∙
04/29/2017
Learning with Changing Features
In this paper we study the setting where features are added or change in...
research
∙
12/26/2015
Statistical Learning under Nonstationary Mixing Processes
We study a special case of the problem of statistical learning without t...
research
∙
12/22/2015
Refined Error Bounds for Several Learning Algorithms
This article studies the achievable guarantees on the error rates of cer...
research
∙
07/02/2015
The Optimal Sample Complexity of PAC Learning
This work establishes a new upper bound on the number of samples suffici...
research
∙
10/03/2014
Minimax Analysis of Active Learning
This work establishes distribution-free upper and lower bounds on the mi...
research
∙
04/05/2014
A Compression Technique for Analyzing Disagreement-Based Active Learning
We introduce a new and improved characterization of the label complexity...
research
∙
07/16/2012
Surrogate Losses in Passive and Active Learning
Active learning is a type of sequential design for supervised machine le...
research
∙
08/08/2011