arXiv:2509.25135cs.LGstat.ML2025-09被引 5

研究自标注数据中错误循环放大问题,提出新学习框架与精确可学习性度量。

Learning in an Echo Chamber: Online Learning with Replay Adversary

  • 引入回放对抗学习模型,模拟自标注数据中的错误传播机制。
  • 提出扩展阈值维数(ExThD),作为该模型下可学习性的精确衡量标准。
  • 证明不恰当学习器会陷入灾难性错误,而新算法能实现最优错误率。

随着机器学习系统越来越多地依赖自标注数据,其可能不断强化错误,形成自我强化的回音室。本文提出在线学习的回放设置模型:在第 t 轮,学习者输出假设 $\hat{h}_t$;对手随后展示真实标签 $f^*(x_t)$ 或之前某轮 i < t 的回放标签 $$\hat{h}_i(x_t)$。仅当真实标签出现时才计为错误,但经典算法如 SOA 与减半法极易被回放错误误导。本文引入扩展阈值维数 $$\mathrm{ExThD}(\mathcal{H})$,证明其上下界匹配,是该模型中可学习性的精确度量。基于闭包的算法最多犯 $$\mathrm{ExThD}(\mathcal{H})$ 次错误,且无算法能更优。对于随机对手,所有交封闭类均满足类似界。回放设置严格难于经典错误界设置:某些类具有常数 Littlestone 维但 $$\mathrm{ExThD}(\mathcal{H})$ 可任意大。正规学习存在更显著分离:仅当类近乎交封闭时,正规学习才可实现回放下的可学习性;否则,所有正规学习器将遭遇 $Ω(T)$ 错误,而本文非正规算法仍保持 $$\mathrm{ExThD}(\mathcal{H})$ 界。这些结果首次对回放对抗学习提供紧致分析,基于新型闭包型算法成果。

原文摘要 · Abstract (English)

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 $\hat{h}_t$; the adversary then reveals either the true label $f^\ast(x_t)$ or a replayed label $\hat{h}_i(x_t)$ 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, $\mathrm{ExThD}(\mathcal{H})$, and prove matching upper and lower bounds that make $\mathrm{ExThD}(\mathcal{H})$ the exact measure of learnability in this model. A closure-based learner makes at most $\mathrm{ExThD}(\mathcal{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 $\mathrm{ExThD}(\mathcal{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 $Ω(T)$ errors, whereas our improper algorithm still achieves the $\mathrm{ExThD}(\mathcal{H})$ bound. These results give the first tight analysis of learning against replay adversaries, based on new results for closure-type algorithms.

在线学习回放对抗可学习性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。