Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization
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 ideas and approaches to adversarially robust learning. In particular, we show, in a strong negative sense, the suboptimality of the robust learner proposed by Montasser, Hanneke, and Srebro (2019) and a broader family of learners we identify as local learners. Our results are enabled by adopting a global perspective, specifically, through a key technical contribution: the global one-inclusion graph, which may be of independent interest, that generalizes the classical one-inclusion graph due to Haussler, Littlestone, and Warmuth (1994). Finally, as a byproduct, we identify a dimension characterizing qualitatively and quantitatively what classes of predictors $\mathcal{H}$ are robustly learnable. This resolves an open problem due to Montasser et al. (2019), and closes a (potentially) infinite gap between the established upper and lower bounds on the sample complexity of adversarially robust learning.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
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 sufficiency of finiteness of th…
PAC learningregressionCorruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
In linear bandits, how can a learner effectively learn when facing corrupted rewards? While significant work has explored this question, a holistic understanding across different adversarial models and corruption measure…
Inference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds
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 sufficiency of finiteness of th…
Gaussian ProcessesPAC learningregressionInference for Gaussian Processes with Matern Covariogram on Compact Riemannian Manifolds
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 sufficiency of finiteness of th…
Gaussian ProcessesPAC learningregressionCorruption-Robust Offline Two-Player Zero-Sum Markov Games
We study data corruption robustness in offline two-player zero-sum Markov games. Given a dataset of realized trajectories of two players, an adversary is allowed to modify an $\epsilon$-fraction of it. The learner's goal…