Statistical Limits of Learning Rules from Exceptions

Learning systems that encounter repeated deviations from an established regularity must decide whether they reflect transient noise, stable but idiosyncratic exceptions, or a reusable secondary rule. We formalize this decision through grouped observations, where each type may be observed through multiple noisy tokens, and study how a fixed observation budget should be divided between repetition and type diversity. For a finite separated rule class, we prove minimax token complexity $\Theta ((\log |\mathcal{G}|+\log (1/\delta ))/(\alpha (1-2\eta {)}^2))$. A rate-optimal design heavily repeats one type to establish persistence and uses singleton observations for structural learning, while under balanced acquisition the information-optimal repetition count is $\Theta ((1-2\eta {)}^{-2})$. Controlled simulations support both allocation laws. On CLINC150, persistent unstructured residuals are recoverable on observed intents but do not transfer to unseen intents, whereas structured residuals transfer and benefit from broader supporting-type coverage in all ten domains. On Omniglot, global character count is a poor proxy for relevant diversity, as directly increasing target-alphabet support at a fixed positive-token budget raises structured novel-type AUC from $0.722$ to $0.792$ (paired gain $0.069$, 90% CI $[0.063,0.076]$), while unstructured controls remain at chance.