Reconstructing Training Data from Model Gradient, Provably

Understanding when and to what extent a model's gradient leaks the information of the training samples is an essential question in privacy. In this paper, we present a surprising result. Even without training and memorizing the data, we can fully recover the training samples from the gradient at a randomly chosen neural network. We prove the identifiability of reconstructing the batches of training samples under general conditions -- with shallow or deep neural networks and broad choices of activation functions. We also present efficient algorithms based on tensor decomposition to reconstruct such training data. As an effective attack for revealing sensitive training data, our findings implicate severe problems in privacy, especially in federated learning.