Adversarially Robust PAC Learning with Optimal VC Rates

Steve Hanneke; Amirreza Shaeiri

IA y aprendizaje automáticoTeoría del aprendizaje y optimización

Adversarially Robust PAC Learning with Optimal VC Rates

Steve Hanneke, Amirreza Shaeiri

Preprint

En palabras de los autores

We study the problem of adversarially robust PAC learning. In this framework, the learner observes independent samples from an unknown distribution over $X \times {0, 1}$ , as in classical PAC learning. However, given a perturbation map $U : X \to 2^{X}$ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies every perturbation $z \in U (x)$ of most future examples $(x, y)$ drawn from the same underlying distribution. We determine the optimal $U$ -independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class $H$ of $VC$ dimension $d$ , we prove upper bounds of $O (d / ϵ + lo g (1/ δ) / ϵ)$ in the realizable setting and $O (d / ϵ^{2} + lo g (1/ δ) / ϵ^{2})$ in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs no additional distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call binomial-bagging. We believe that binomial-bagging and its analysis may be of independent interest.

Resultado principalEl resumen no menciona limitaciones.

Leer el paper PDF

Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 35 pages, 2 figures

IA y aprendizaje automático Teoría del aprendizaje y optimización 22 de sept de 2026
Toward a Unified Mathematics of Concepts
We propose an operation-based view that evaluates mathematical frameworks by the conceptual operations they support, identifying thirteen operations (including similarity, composition, generalization, and grounding) that recur across cognition, psychology, and AI.
Chen Shani — arXiv
Preprint
IA y aprendizaje automático Teoría del aprendizaje y optimización 22 de sept de 2026
Displacement Geometry Captures Platonic Shared Reality Across Models and Modalities
In this paper, we show that what models share is not the location of samples in representation space, but the directions (displacement vectors) between them.
Chenming Shang, Yujin Tang, Jun Jie Ou Yang y 3 más — arXiv
PreprintAfirmaciones fuertes, leer con cuidadoUso en el mundo real
IA y aprendizaje automático Teoría del aprendizaje y optimización 22 de sept de 2026
Conformal Robustness in Prediction-Driven Decision-Making
Overall, our work shows that conformal scores endow fixed black-box predictors with an interpretable uncertainty scale for downstream decision-making while enabling reliability guarantees, acceptable-target selection, and fragility analysis within a unified framework.
Lingjie Zhao, Hansheng Jiang, Wei Qi — arXiv
PreprintUso en el mundo real
IA y aprendizaje automático Teoría del aprendizaje y optimización 22 de sept de 2026
Whitening Inverts the Hierarchy: What the Norm of a Whitened Embedding Measures
These results indicate that the squared whitened norm is better interpreted as a Mahalanobis measure of semantic atypicality than as a log-likelihood.
Mohammed Ahnouch, Lotfi Elaachak — arXiv
Preprint
IA y aprendizaje automático Teoría del aprendizaje y optimización 22 de sept de 2026
The Price of Self-Calibration: Exact Evidence Budgets and Manufactured Blind Sets in Adaptive Monitoring
Third, any monitor required to tolerate a drift class $D$ is blind, at any horizon and for any rule, to every fault in $D - D$ ; the proof is a deliberately elementary two-point argument and the contribution is the object it identifies: for speed-bounded classes the blind set is exactly the doubled-speed class, and the tracker absorbs a speed class fixed by its own gain, so that under a certification regime declaring absorbed drift normal, the monitor manufactures $D$ .
Abdou-Raouf Atarmla — arXiv
Preprint

Todos los papers nuevos de Teoría del aprendizaje y optimización

Adversarially Robust PAC Learning with Optimal VC Rates

En palabras de los autores

Más de Teoría del aprendizaje y optimización ese día

Toward a Unified Mathematics of Concepts

Displacement Geometry Captures Platonic Shared Reality Across Models and Modalities

Conformal Robustness in Prediction-Driven Decision-Making

Whitening Inverts the Hierarchy: What the Norm of a Whitened Embedding Measures

The Price of Self-Calibration: Exact Evidence Budgets and Manufactured Blind Sets in Adaptive Monitoring