Spoofing Generalization: When Can't You Trust Proprietary Models?
This highlights inherent difficulties in trusting large proprietary models or data, which is a foundational problem for the ML/AI community, though it is an incremental theoretical analysis.
The paper tackles the problem of determining whether a machine learning model that fits training data will generalize to unseen data, showing that under cryptographic assumptions, strong spoofing is possible, and for any fixed time bound, weak spoofing is possible unconditionally.
In this work, we study the computational complexity of determining whether a machine learning model that perfectly fits the training data will generalizes to unseen data. In particular, we study the power of a malicious agent whose goal is to construct a model g that fits its training data and nothing else, but is indistinguishable from an accurate model f. We say that g strongly spoofs f if no polynomial-time algorithm can tell them apart. If instead we restrict to algorithms that run in $n^c$ time for some fixed $c$, we say that g c-weakly spoofs f. Our main results are 1. Under cryptographic assumptions, strong spoofing is possible and 2. For any c> 0, c-weak spoofing is possible unconditionally While the assumption of a malicious agent is an extreme scenario (hopefully companies training large models are not malicious), we believe that it sheds light on the inherent difficulties of blindly trusting large proprietary models or data.