# The Active and Noise-Tolerant Strategic Perceptron

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 1 Dec 2025.

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

- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [The Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (2020)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)

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

- [Revealing Positive and Negative Role Models to Help People Make Good Decisions](https://mlsanity.com/paper/2603.02495/) (2026)
- [Shaping Human-AI Interactions to Provide Improvement Pathways and Balance Competing Objectives](https://mlsanity.com/paper/2608.05710/) (2026)

## Abstract (arXiv)

We initiate the study of active learning algorithms for classifying strategic agents. Active learning is a well-established framework in machine learning in which the learner selectively queries labels, often achieving substantially higher accuracy and efficiency than classical supervised methods-especially in settings where labeling is costly or time-consuming, such as hiring, admissions, and loan decisions. Strategic classification, however, addresses scenarios where agents modify their features to obtain more favorable outcomes, resulting in observed data that is not truthful. Such manipulation introduces challenges beyond those in learning from clean data. Our goal is to design active and noise-tolerant algorithms that remain effective in strategic environments-algorithms that classify strategic agents accurately while issuing as few label requests as possible. The central difficulty is to simultaneously account for strategic manipulation and preserve the efficiency gains of active learning. Our main result is an algorithm for actively learning linear separators in the strategic setting that preserves the exponential improvement in label complexity over passive learning previously obtained only in the non-strategic case. Specifically, for data drawn uniformly from the unit sphere, we show that a modified version of the Active Perceptron algorithm [DKM05,YZ17] achieves excess error ε using only tildeO(d ln frac1ε) label queries and incurs at most tildeO(d ln frac1ε) additional mistakes relative to the optimal classifier, even in the nonrealizable case, when a tildeOmega(ε) fraction of inputs have inconsistent labels with the optimal classifier. The algorithm is computationally efficient and, under these distributional assumptions, requires substantially fewer label queries than prior work on strategic Perceptron [ABBN21].