Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916776185430016 |
|---|---|
| author | Chornomaz, Bogdan Koren, Yonatan Moran, Shay Waknine, Tom |
| author_facet | Chornomaz, Bogdan Koren, Yonatan Moran, Shay Waknine, Tom |
| contents | We study the problem of learning in the presence of an adversary that can corrupt an $η$ fraction of the training examples with the goal of causing failure on a specific test point. In the realizable setting, prior work established that the optimal error under such instance-targeted poisoning attacks scales as $Θ(dη)$, where $d$ is the VC dimension of the hypothesis class arXiv:2210.02713. In this work, we resolve the corresponding question in the agnostic setting. We show that the optimal excess error is $\tildeΘ(\sqrt{dη})$, answering one of the main open problems left by Hanneke et al. To achieve this rate, it is necessary to use randomized learners: Hanneke et al. showed that deterministic learners can be forced to suffer error close to 1, even under small amounts of poisoning. Perhaps surprisingly, our upper bound remains valid even when the learner's random bits are fully visible to the adversary . In the other direction, our lower bound is stronger than standard PAC-style bounds: instead of tailoring a hard distribution separately for each sample size, we exhibit a single fixed distribution under which the adversary can enforce an excess error of $Ω(\sqrt{dη})$ infinitely often. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03075 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness Chornomaz, Bogdan Koren, Yonatan Moran, Shay Waknine, Tom Machine Learning Probability 68Q32 I.2.6 We study the problem of learning in the presence of an adversary that can corrupt an $η$ fraction of the training examples with the goal of causing failure on a specific test point. In the realizable setting, prior work established that the optimal error under such instance-targeted poisoning attacks scales as $Θ(dη)$, where $d$ is the VC dimension of the hypothesis class arXiv:2210.02713. In this work, we resolve the corresponding question in the agnostic setting. We show that the optimal excess error is $\tildeΘ(\sqrt{dη})$, answering one of the main open problems left by Hanneke et al. To achieve this rate, it is necessary to use randomized learners: Hanneke et al. showed that deterministic learners can be forced to suffer error close to 1, even under small amounts of poisoning. Perhaps surprisingly, our upper bound remains valid even when the learner's random bits are fully visible to the adversary . In the other direction, our lower bound is stronger than standard PAC-style bounds: instead of tailoring a hard distribution separately for each sample size, we exhibit a single fixed distribution under which the adversary can enforce an excess error of $Ω(\sqrt{dη})$ infinitely often. |
| title | Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness |
| topic | Machine Learning Probability 68Q32 I.2.6 |
| url | https://arxiv.org/abs/2506.03075 |