# Learning in an Echo Chamber: Online Learning with Replay Adversary

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 29 Sep 2025.

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

- [Deep Clustering for Unsupervised Learning of Visual Features](https://mlsanity.com/paper/1807.05520/) (2018)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Self-labelling via simultaneous clustering and representation learning](https://mlsanity.com/paper/1911.05371/) (2019)
- [The Curse of Recursion: Training on Generated Data Makes Models Forget](https://mlsanity.com/paper/2305.17493/) (2023)
- [Self-Consuming Generative Models Go MAD](https://mlsanity.com/paper/2307.01850/) (2023)
- [Artificial Artificial Artificial Intelligence: Crowd Workers Widely Use Large Language Models for Text Production Tasks](https://mlsanity.com/paper/2306.07899/) (2023)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Visual Program Distillation: Distilling Tools and Programmatic Reasoning into Vision-Language Models](https://mlsanity.com/paper/2312.03052/) (2023)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Are We in the AI-Generated Text World Already? Quantifying and Monitoring AIGT on Social Media](https://mlsanity.com/paper/2412.18148/) (2024)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [2 Notes on Classes with Vapnik-Chervonenkis Dimension 1](https://mlsanity.com/paper/1507.05307/) (2015)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficient](https://mlsanity.com/paper/1703.06536/) (2017)
- [Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes](https://mlsanity.com/paper/2210.05455/) (2022)
- [An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1](https://mlsanity.com/paper/2505.06581/) (2025)

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

- [Language Generation with Replay: A Learning-Theoretic View of Model Collapse](https://mlsanity.com/paper/2603.11784/) (2026)
- [Optimal Rates for Learning with Monotone Adversaries](https://mlsanity.com/paper/2608.06337/) (2026)
- [When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory](https://mlsanity.com/paper/2608.14020/) (2026)

## Abstract (arXiv)

As machine learning systems increasingly train on self-annotated data, they risk reinforcing errors and becoming echo chambers of their own beliefs. We model this phenomenon by introducing a learning-theoretic framework: Online Learning in the Replay Setting. In round t, the learner outputs a hypothesis hatht; the adversary then reveals either the true label f^ast(xt) or a replayed label hathi(xt) from an earlier round i < t. A mistake is counted only when the true label is shown, yet classical algorithms such as the SOA or the halving algorithm are easily misled by the replayed errors. We introduce the Extended Threshold dimension, ExThD(H), and prove matching upper and lower bounds that make ExThD(H) the exact measure of learnability in this model. A closure-based learner makes at most ExThD(H) mistakes against any adaptive adversary, and no algorithm can perform better. For stochastic adversaries, we prove a similar bound for every intersection-closed class. The replay setting is provably harder than the classical mistake bound setting: some classes have constant Littlestone dimension but arbitrarily large ExThD(H). Proper learning exhibits an even sharper separation: a class is properly learnable under replay if and only if it is (almost) intersection-closed. Otherwise, every proper learner suffers Omega(T) errors, whereas our improper algorithm still achieves the ExThD(H) bound. These results give the first tight analysis of learning against replay adversaries, based on new results for closure-type algorithms.