Abstract

Vector embeddings of raw records, while not human-readable, do not preserve privacy of records: an adversary can reconstruct training records from a released model even when that model is a simple convex classifier. Differential privacy (DP) is the principled defense, but its noise is calibrated to the worst-case indistinguishability; hiding arbitrary single-record substitutions, including those far outside the set of plausible alternatives relevant to a reconstruction adversary. The result is noise far larger than what reconstruction robustness requires, degrading accuracy without a corresponding security benefit. We propose _Ball-DP_ : enforcing ( _, _ ) indistinguishability over single-record substitutions restricted to a ball of radius _r_ as per a distance metric _d_ in the embedding space. A deployment facing only local reconstruction threat can choose a small _r_ , thereby reduce noise and recover accuracy. The radius makes the scope of the privacy claim explicit against reconstruction attacks; standard DP is recovered when _r_ covers the entire admissible record domain. We provide noise calibrations for regularized convex learning problems for Ball-DP, and derive the corresponding reconstruction-robustness certificates (named _Ball-ReRo_ ) upper-bound on an attackers reconstruction success. By deriving the optimal finite-prior MAP reconstruction attack, we present empirical auditing of Ball-ReRo certificates for seven benchmark learning tasks. Our experiments show that calibrating noise to Ball-DP yields improvement in utility, considerably exceeding the dilution of reconstruction robustness in high privacy regimes, i.e., when __ is small.