  Deep Neural Nets (DNNs) have become a pervasive tool for solving many
emerging problems. However, they tend to overfit to and memorize the training
set. Memorization is of keen interest since it is closely related to several
concepts such as generalization, noisy learning, and privacy. To study
memorization, Feldman (2019) proposed a formal score, however its computational
requirements limit its practical use. Recent research has shown empirical
evidence linking input loss curvature (measured by the trace of the loss
Hessian w.r.t inputs) and memorization. It was shown to be ~3 orders of
magnitude more efficient than calculating the memorization score. However,
there is a lack of theoretical understanding linking memorization with input
loss curvature. In this paper, we not only investigate this connection but also
extend our analysis to establish theoretical links between differential
privacy, memorization, and input loss curvature. First, we derive an upper
bound on memorization characterized by both differential privacy and input loss
curvature. Second, we present a novel insight showing that input loss curvature
is upper-bounded by the differential privacy parameter. Our theoretical
findings are further empirically validated using deep models on CIFAR and
ImageNet datasets, showing a strong correlation between our theoretical
predictions and results observed in practice.
