How to Learn in an Echo Chamber

Based on Learning in an Echo Chamber: Online Learning with Replay Adversary by Daniil Dmitriev, Harald Eskelund Franck, Carolin Heinzler, and Amartya Sanyal (SODA2026, FORC2026)

Model collapse is just one of many puzzles researchers are still trying to understand when it comes to the training of Large Language Models (LLMs). It describes the catastrophic collapse in performance when training on data that has been generated by another LLM, rather than human-generated data.

A related phenomenon in society is the echo chamber. The Cambridge dictionary defines it as: a situation in which people only hear opinions of one type, or opinions that are similar to their own. In this sense, model collapse is to training LLMs what an echo chamber is to human beliefs: both describe a feedback loop in which one learns from its own outputs.

We turn this fundamental mechanism of training on one's own belief into a learning-theoretic framework and study what fundamentally breaks when learning or generation relies on self-labeled data. That question led to two papers from our group that introduce a novel framework for this setting: replay.

In this blog post part 1, Carolin explores how learning can adapt to replay, while Giorgio turns to language generation with replay in part 2.

Online Learning with Replay Adversary

To understand what happens when training relies on self-labeled data, we first introduce the classical framework of online learning, when labeled data arrives in a stream:

The learner’s goal is to minimize the number of mistakes up until time $T$: $M_T=\sum_{t=1}^T I\{h_t(x_t)\neq y_t\}$.

To simulate self-labeling using prior hypotheses, we introduce a replay adversary. This modifies only one part in the above protocol: the label shown to the learner need not always be the true label. Instead, the learner receives $(x_t,y_t)$, where $y_t$ is either the true label from $f^\ast$ or a replay label produced by some earlier hypothesis $h_i$ with $i<t$.

In the paper, we study the setting where samples $x_t$ are chosen adaptively throughout the game by an adversary, as well as the stochastic setting, where $x_t\overset{\mathrm{i.i.d.}}{\sim}\mathcal{D}$ for some unknown distribution $\mathcal{D}$. If the learner is restricted to predict with hypothesis $h_t$ from the hypothesis class $\mathcal{H}$ we call the learner proper, as opposed to improper.

Example: Thresholds

We give a simple example of learning a threshold function: consider the hypothesis class of thresholds $\mathcal{H}:=\{h_a:\mathcal{X}\rightarrow \{0,1\} \mid h_a=\mathrm{I}[\cdot \leq a], a\in [0,1]\}$. We first restrict ourselves to a finite domain $\mathcal{X}=\{1,\dots, N\}$.

In order to understand what can go wrong when we have a replay adversary, we study the Halving Algorithm: in every round, the learner predicts a threshold at exactly half-way between the largest 0 label and the smallest 1 label. This is the region where the learner is still uncertain, as there exist two potential targets in $\mathcal{H}$ that could give contradicting labels for every point in this region. When there is no replay, it is known that this strategy is indeed optimal to learn a threshold.

However, when there is replay, an issue can occur with this prediction strategy: as the learner might predict both zeros and ones over time in a region where it is still uncertain, this can create something that we denote a Trap Region. This is an interval of ambiguitiy the learner created, when there exist two past predictions which predict 0 and 1 in this interval, while still being uncertain, i.e. the learner has no way of knowing what the true label is.

An adaptive adversary can continue playing samples in this region, and the learner has no way of knowing whether they made a true mistake or not. This constitutes a strategy of the adversary to force linear in $T$ mistakes for the learner. We illustrate an example of this in Figure 2.

More generally, we show that for any learner that predicts with both zeroes and ones in a region where it is uncertain (like Halving), there will always be a Trap Region and thus the learner makes linear in $T$ mistakes. Only a learner that predicts exclusively always zero or always one when uncertain can avoid to be trapped. This is exactly the closure algorithm: the learner predicts with the intersection of all hypothesis which are consistent with the samples observed thus far. Because the learner can only incur one sided mistakes (e.g. only false negative), whenever a mistake occurs the learner can trust this label as it cannot be replay.

This gives the following characterisation of mistakes on thresholds for a domain of size $N$:

General Results

This principle generalises to more complex hypothesis classes: Any learner that does not predict 'conservatively' with the closure algorithm (i.e. consistently where the learner is uncertain) will create a Trap Region, which the adversary can exploit and enforces mistakes in $O(T)$ rounds. This makes the closure algorithm the optimal strategy for learning with a replay adversary.

Therefore, in order to characterize the mistakes, we need to understand the mistakes of the closure algorithm. For this we use the Threshold Dimension of a class:

For one dimensional thresholds, it is easy to see that the Threshold Dimension is the size of the class $N$. It is easy to see that for any intersection-closed hypothesis class, the Threshold Dimension exactly characterises the mistakes the learner can make in the worst-case.

To extend this to general non-intersection-closed hypothesis classes, we note two things:

• For general classes $\mathcal{H}$ the closure algorithm predicts with the intersection of all hypotheses in the class, which are consistent with the observed labels. Thus, also for general classes, this learner makes at most $\mathrm{ThDim}(\overline{\mathcal{H}})$ mistakes, where $\overline{\mathcal{H}}$ denotes the intersection-closure of $\mathcal{H}.$
• For some classes that are not intersection-closed, there may exist a bijective transformation to make them intersection-closed. As an example, take a union closed class: the naive closure algorithm would make $\mathrm{ThDim}(\overline{\mathcal{H}})$ mistakes but $\overline{\mathcal{H}}$ is a much bigger class than necessary and this causes a huge blowup. However, it is easy to see that flipping all labels $y_t'=1-y_t$ creates an intersection-closed class of the same size as $\mathcal{H}$ and learning in this transformed space leads to fewer mistakes.

This transformation of a class, is called $f$-representation (see Ben-David^[1]) for any function $f:\mathcal{X}\rightarrow\{0,1\}$. This is formally defined as $\mathcal{H}^{f}=\{h^f= h\bigoplus f\mid h\in\mathcal{H}\}$.

We show, that for functions of VCdim 1, there exists an $f$-representation to make the class intersection-closed. However, in general, we do not know of a characterisation of when such a transformation exists or how to find it efficiently and we leave this as a more general open question. Since publication, work by Manurangsi^[2] has resolved this question, we refer to his paper for details.

This leads us to the definition of the Extended Threshold Dimension which we find to characterise learnability for arbitrary hypothesis classes $\mathcal{H}$.

We include an animation in Figure 2 to illustrate how to determine the Threshold Dimension for a given function $f$ of $\overline{\mathcal{H}^f}$. The Extended Threshold Dimension is then obtained at the minimum $f$-representation.

We furthermore show an interesting result on the connection of proper learnability and intersection-closedness of a class:

We refer the interested reader to our full paper for proofs and also a similar characterisation for the stochastic adversarial setting, where samples $x_t$ are sampled i.i.d. from some unknown distribution and not adversarially chosen.

The Final Takeaway

The main finding from our work is that the closure algorithm is the optimal algorithm to learn $\mathcal{H}$ in the replay setting, as any other strategy can be exploited by the replay adversary to enforce linear in $T$ mistakes. This indicates that the replay adversary which can in any round choose to replay a label is quite powerful and limits quick progress when learning. An interesting question is to relax the power of the replay adversary , i.e. a stochastic label setting, replay only after $k$ times, or limiting the amount of replay labels. Furthermore, we have the unresolved open questions of characterising, when there exists an $f$-representation to transform a class into an intersection-closed class.

---

---

1. Reference: Shai Ben-David, 2 Notes on Classes with Vapnik-Chervonenkis Dimension 1, arxiv 2015 ↩︎

2. Reference: Pasin Manurangsi, On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index, arxiv 2026 ↩︎