Distribution Learnability and Robustness
We examine the relationship between learnability and robust (or agnostic) learnability for the problem of distribution learning. We show that, contrary to other learning settings (e.g., PAC learning of function classes), realizable learnability of a class of probability distributions does not imply its agnostic learnability. We go on to examine what type of data corruption can disrupt the learnability of a distribution class and what is such learnability robust against. We show that realizable learnability of a class of distributions implies its robust learnability with respect to only additive corruption, but not against subtractive corruption. We also explore related implications in the context of compression schemes and differentially private learnability.
Code (0)
등록된 구현이 없습니다.
Tasks
PAC learningSimilar Papers 제목 키워드 기반
On the Learnability of Distribution Classes with Adaptive Adversaries
We consider the question of learnability of distribution classes in the presence of adaptive adversaries -- that is, adversaries capable of intercepting the samples requested by a learner and applying manipulations with …
Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem
We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniq…
Multi-Item Mechanisms without Item-Independence: Learnability via Robustness
We study the sample complexity of learning revenue-optimal multi-item auctions. We obtain the first set of positive results that go beyond the standard but unrealistic setting of item-independence. In particular, we cons…
Interpreting the Robustness of Neural NLP Models to Textual Perturbations
Modern Natural Language Processing (NLP) models are known to be sensitive to input perturbations and their performance can decrease when applied to real-world, noisy data. However, it is still unclear why models are less…
Data AugmentationInterpreting the Robustness of Neural NLP Models to Textual Perturbations
Modern Natural Language Processing (NLP) models are known to be sensitive to input perturbations and their performance can decrease when applied to real-world, noisy data. However, it is still unclear why models are les…