43 citations · 66 across the 10 of their papers we have counts for
10 papers
Bagging Robustly Learns VC Classes with Linear Sample Complexity
Omar Montasser
We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity line…
Theoretical Foundations of Adversarially Robust Learning
Omar Montasser
Despite extraordinary progress, current machine learning systems have been shown to be brittle against adversarial examples: seemingly innocuous but carefully crafted perturbations…
Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization
Omar Montasser, Steve Hanneke, Nathan Srebro
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 i…
Transductive Robust Learning Guarantees
Omar Montasser, Steve Hanneke, Nathan Srebro
We study the problem of adversarially robust learning in the transductive setting. For classes of bounded VC dimension, we propose a simple transductive learner that…
Adversarially Robust Learning with Unknown Perturbation Sets
Omar Montasser, Steve Hanneke, Nathan Srebro
We study the problem of learning predictors that are robust to adversarial examples with respect to an unknown perturbation set, relying instead on interaction with an adversarial…
Reducing Adversarially Robust Learning to Non-Robust PAC Learning
Omar Montasser, Steve Hanneke, Nathan Srebro
We study the problem of reducing adversarially robust learning to standard PAC learning, i.e. the complexity of learning adversarially robust predictors using access to only a blac…
Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples
Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai +1
We present a transductive learning algorithm that takes as input training examples from a distribution and arbitrary (unlabeled) test examples, possibly chosen by an adversary.…
Efficiently Learning Adversarially Robust Halfspaces with Noise
Omar Montasser, Surbhi Goel, Ilias Diakonikolas +1
We study the problem of learning adversarially robust halfspaces in the distribution-independent setting. In the realizable setting, we provide necessary and sufficient conditions…
Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
Pritish Kamath, Omar Montasser, Nathan Srebro
We present and study approximate notions of dimensional and margin complexity, which correspond to the minimal dimension or norm of an embedding required to approximate, rather the…
VC Classes are Adversarially Robustly Learnable, but Only Improperly
Omar Montasser, Steve Hanneke, Nathan Srebro
We study the question of learning an adversarially robust predictor. We show that any hypothesis class with finite VC dimension is robustly PAC learnable with an impr…