conftrace_

2019 COLT COLT 2019

VC Classes are Adversarially Robustly Learnable, but Only Improperly

Abstract

We study the question of learning an adversarially robust predictor. We show that any hypothesis class $\mathcal{H}$ with finite VC dimension is robustly PAC learnable with an \emph{improper} learning rule. The requirement of being improper is necessary as we exhibit examples of hypothesis classes $\mathcal{H}$ with finite VC dimension that are \emph{not} robustly PAC learnable with any \emph{proper} learning rule.

🐣 Hot Topic Early Bird - vc dimension

Authors

Omar Montasser, Steve Hanneke, Nathan Srebro

Topics

Artificial Intelligence > Core AI > AI Safety Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning Deep Learning > Learning Types > Adversarial Learning Deep Learning > Learning Types > Robustness

Keywords

adversarial robustness pac learning vc dimension robust generalization improper learning

More from COLT 2019

All COLT 2019 papers →

Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit

Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem

Lipschitz Adaptivity with Multiple Learning Rates in Online Learning

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Stochastic Gradient Descent Learns State Equations with Nonlinear Activations

A Theory of Selective Prediction