  Reconstruction attacks and defenses are essential in understanding the data
leakage problem in machine learning. However, prior work has centered around
empirical observations of gradient inversion attacks, lacks theoretical
justifications, and cannot disentangle the usefulness of defending methods from
the computational limitation of attacking methods. In this work, we propose to
view the problem as an inverse problem, enabling us to theoretically,
quantitatively, and systematically evaluate the data reconstruction problem. On
various defense methods, we derived the algorithmic upper bound and the
matching (in feature dimension and model width) information-theoretical lower
bound on the reconstruction error for two-layer neural networks. To complement
the theoretical results and investigate the utility-privacy trade-off, we
defined a natural evaluation metric of the defense methods with similar utility
loss among the strongest attacks. We further propose a strong reconstruction
attack that helps update some previous understanding of the strength of defense
methods under our proposed evaluation metric.
