In this work, we aim to characterize the statistical complexity of realizable regression both in
the PAC learning setting and the online learning setting. Previous work had established the …

A seminal result in learning theory characterizes the PAC learnability of binary classes
through the Vapnik-Chervonenkis dimension. Extending this characterization to the general …

We consider a model of robust learning in an adversarial environment. The learner gets
uncorrupted training data with access to possible corruptions that may be effected by the …

We present a minimax optimal learner for the problem of learning predictors robust to
adversarial examples at test-time. Interestingly, we find that this requires new algorithmic …

The equivalence of realizable and agnostic learnability is a fundamental phenomenon in
learning theory. With variants ranging from classical settings like PAC learning and …

In this work we initiate the study of regression in the universal rates framework of Bousquet
et al. Unlike the traditional uniform learning setting, we are interested in obtaining learning …

The notion of replicable algorithms was introduced by Impagliazzo, Lei, Pitassi, and Sorrell
(STOC'22) to describe randomized algorithms that are stable under the resampling of their …

We study the setting of multiclass boosting with a possibly large number of classes. A recent
work by Brukhim, Hazan, Moran, and Schapire, 2021, proved a hardness result for a large …

List learning is a variant of supervised classification where the learner outputs multiple
plausible labels for each instance rather than just one. We investigate classical principles …

The quintessential learning algorithm of empirical risk minimization (ERM) is known to fail in
various settings for which uniform convergence does not characterize learning. Relatedly …