mlsanityData to 7 Oct 2026

Adversarially Robust PAC Learnability of Real-Valued Functions

arXiv 2206.12977 ↗First posted 26 Jun 2022cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We study robustness to test-time adversarial attacks in the regression setting with ℓp losses and arbitrary perturbation sets. We address the question of which function classes are PAC learnable in this setting. We show that classes of finite fat-shattering dimension are learnable in both realizable and agnostic settings. Moreover, for convex function classes, they are even properly learnable. In contrast, some non-convex function classes provably require improper learning algorithms. Our main technique is based on a construction of an adversarially robust sample compression scheme of a size determined by the fat-shattering dimension. Along the way, we introduce a novel agnostic sample compression scheme for real-valued functions, which may be of independent interest.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 30 of its 72 references that are in the map. First posted on arXiv 26 Jun 2022.

Builds on

30 of 72 references.

References · 30

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  5. 2018Adversarially Robust Generalization Requires More Datacited by 318
  6. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  7. 2019Online Control with Adversarial Disturbancescited by 92
  8. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  9. 2018Adversarial examples from computational constraintscited by 79
  10. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  11. 2014Optimal Learners for Multiclass Problemscited by 65
  12. 2020Adversarial Learning Guarantees for Linear Hypotheses and Neural Networkscited by 47
18 more
  1. 2021Calibration and Consistency of Adversarial Surrogate Lossescited by 47
  2. 2013Online Learning for Time Series Predictioncited by 33
  3. 2018Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distributioncited by 32
  4. 2020Reducing Adversarially Robust Learning to Non-Robust PAC Learningcited by 28
  5. 2020Sharp Statistical Guarantees for Adversarially Robust Gaussian Classificationcited by 27
  6. 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)cited by 25
  7. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  8. 2019On the Hardness of Robust Classificationcited by 23
  9. 2020Efficiently Learning Adversarially Robust Halfspaces with Noisecited by 22
  10. 2020Adversarially Robust Estimate and Risk Analysis in Linear Regressioncited by 22
  11. 2018Sample Compression for Real-Valued Learnerscited by 19
  12. 2020Black-box Certification and Learning under Adversarial Perturbationscited by 13
  13. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  14. 2021Transductive Robust Learning Guaranteescited by 10
  15. 2015Classification with Low Rank and Missing Datacited by 9
  16. 2021Primal and Dual Combinatorial Dimensionscited by 6
  17. 2016A Non-generative Framework and Convex Relaxations for Unsupervised Learningcited by 5
  18. 2017An optimal unrestricted learning procedurecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 0; 2024: 1; 2025: 1; 2026: 5.

8 papers.

  1. 2025PAC Learning with Improvementscited by 6
  2. 2022On Proper Learnability between Average- and Worst-case Robustnesscited by 5
  3. 2024Sample Compression Scheme Reductionscited by 2
  4. 2026On damage of interpolation to adversarial robustness in regressioncited by 1
  5. 2026Bagging Robustly Learns VC Classes with Linear Sample Complexitycited by 1
  6. 2026Robust Online Learningcited by 0
  7. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0
  8. 2026An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimensioncited by 0