# Regularized Robustly Reliable Learners and Instance Targeted Attacks

arXiv: https://arxiv.org/abs/2410.10572 · HTML: https://mlsanity.com/paper/2410.10572/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 14 Oct 2024.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

## Builds on (most cited first, 11 of 11)

- [Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning](https://mlsanity.com/paper/1712.05526/) (2017)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks](https://mlsanity.com/paper/1803.06975/) (2018)
- [Maximum Flow and Minimum-Cost Flow in Almost-Linear Time](https://mlsanity.com/paper/2203.00671/) (2022)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [Noise in Classification](https://mlsanity.com/paper/2010.05080/) (2020)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Faster Min-Plus Product for Monotone Instances](https://mlsanity.com/paper/2204.04500/) (2022)

## Built on by (most cited first, 5 of 5)

- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [Shaping Human-AI Interactions to Provide Improvement Pathways and Balance Competing Objectives](https://mlsanity.com/paper/2608.05710/) (2026)
- [Robustly Reliable Learning for Regression](https://mlsanity.com/paper/2610.17381/) (2026)

## Abstract (arXiv)

Instance-targeted data poisoning attacks, where an adversary corrupts a training set to induce errors on specific test points, have raised significant concerns. Balcan et al (2022) proposed an approach to addressing this challenge by defining a notion of robustly-reliable learners that provide per-instance guarantees of correctness under well-defined assumptions, even in the presence of data poisoning attacks. They then give a generic optimal (but computationally inefficient) robustly reliable learner as well as a computationally efficient algorithm for the case of linear separators over log-concave distributions. In this work, we address two challenges left open by Balcan et al (2022). The first is that the definition of robustly-reliable learners in Balcan et al (2022) becomes vacuous for highly-flexible hypothesis classes: if there are two classifiers h0, h1 ∈ H both with zero error on the training set such that h0(x) neq h1(x), then a robustly-reliable learner must abstain on x. We address this problem by defining a modified notion of regularized robustly-reliable learners that allows for nontrivial statements in this case. The second is that the generic algorithm of Balcan et al (2022) requires re-running an ERM oracle (essentially, retraining the classifier) on each test point x, which is generally impractical even if ERM can be implemented efficiently. To tackle this problem, we show that at least in certain interesting cases we can design algorithms that can produce their outputs in time sublinear in training time, by using techniques from dynamic algorithm design.