  Proper data stewardship requires that model owners protect the privacy of
individuals' data used during training. Whether through anonymization with
differential privacy or the use of unlearning in non-anonymized settings, the
gold-standard techniques for providing privacy guarantees can come with
significant performance penalties or be too weak to provide practical
assurances. In part, this is due to the fact that the guarantee provided by
differential privacy represents the worst-case privacy leakage for any
individual, while the true privacy leakage of releasing the prediction for a
given individual might be substantially smaller or even, as we show,
non-existent. This work provides a novel framework based on convex relaxations
and bounds propagation that can compute formal guarantees (certificates) that
releasing specific predictions satisfies $\epsilon=0$ privacy guarantees or do
not depend on data that is subject to an unlearning request. Our framework
offers a new verification-centric approach to privacy and unlearning
guarantees, that can be used to further engender user trust with tighter
privacy guarantees, provide formal proofs of robustness to certain membership
inference attacks, identify potentially vulnerable records, and enhance current
unlearning approaches. We validate the effectiveness of our approach on tasks
from financial services, medical imaging, and natural language processing.
