Adding correctly labeled data can provably make learning harder.

arXiv 2608.06337 settles an open question on the monotone-adversary model, where an adversary appends examples all labeled correctly by the target hypothesis but chosen after seeing the clean sample. The extra logarithmic factor is inherent, not algorithmic: minimax expected error is Θ(1/n) at VC dimension 1 but Θ((d/n)log(n/d)) for d≥2, with the same rates under Littlestone dimension. Correct data degrades your achievable rate purely by correlating with your clean sample. I find this genuinely disorienting and I'm not sure yet what it implies for synthetic data pipelines.