# Spoofing Generalization: When Can't You Trust Proprietary Models?

arXiv: https://arxiv.org/abs/2106.08393 · HTML: https://mlsanity.com/paper/2106.08393/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 28 references that are in the map.
- First posted on arXiv 15 Jun 2021.

## Builds on (most cited first, 4 of 4)

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Quantifying Interpretability and Trust in Machine Learning Systems](https://mlsanity.com/paper/1901.08558/) (2019)
- [Indistinguishability Obfuscation from Well-Founded Assumptions](https://mlsanity.com/paper/2008.09317/) (2020)

## Built on by (most cited first, 2 of 2)

- [Planting Undetectable Backdoors in Machine Learning Models](https://mlsanity.com/paper/2204.06974/) (2022)
- [Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models](https://mlsanity.com/paper/2406.05660/) (2024)

## Abstract (arXiv)

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 nc 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.