← Back to papers
2022 NIPS NeurIPS 2022

On Robust Multiclass Learnability

Abstract

This work analyzes the robust learning problem in the multiclass setting. Under the framework of Probably Approximately Correct (PAC) learning, we first show that the graph dimension and the Natarajan dimension, which characterize the standard multiclass learnability, are no longer applicable in robust learning problem. We then generalize these notions to the robust learning setting, denoted as the adversarial graph dimension (AG-dimension) and the adversarial Natarajan dimension (AN-dimension). Upper and lower bounds of the sample complexity of robust multiclass learning are rigorously derived based on the AG-dimension and AN-dimension, respectively. Moreover, we calculate the AG-dimension and AN-dimension of the class of linear multiclass predictors, and show that the graph (Natarajan) dimension is of the same order as the AG(AN)-dimension. Finally, we prove that the AG-dimension and AN-dimension are not equivalent.

🧭 Keyword Pioneer — adversarial dimension
🐣 Hot Topic Early Bird — multiclass classification
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Jingyuan Xu , Weiwei Liu

Topics

Machine Learning > Core Methods > Classification Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Theory Machine Learning > Learning Types > Classification Machine Learning > Learning Types > Robustness

Keywords

learning theory adversarial robustness sample complexity pac learning multiclass classification robust learning multiclass learning adversarial dimension
Download PDF

Related papers

Transferring Pre-trained Multimodal Representations with Cross-modal Similarity Matching 2022
A Theoretical View on Sparsely Activated Networks 2022
Prune and distill: similar reformatting of image information along rat visual cortex and deep neural networks 2022
Matryoshka Representation Learning 2022
Off-Policy Evaluation with Deficient Support Using Side Information 2022