Differential Privacy via Distributionally Robust Optimization

Privacy-Accuracy Trade-off from an Optimization Lens: Fix a Desired Level of Privacy, Then Maximize Accuracy In differential privacy, the de facto standard for safeguarding individual information in data analysis, noise is added to statistics to limit the disclosure of sensitive information. Greater privacy requires more noise, creating a trade-off as the added noise reduces the accuracy of the resulting statistics. Historically, researchers have addressed this by restricting themselves to families of noise mechanisms that are sufficient for a predefined privacy level and proving their performance under specific conditions. Selvi, Liu, and Wiesemann propose a novel approach that guarantees optimal accuracy for any specified privacy level. They formulate the design of privacy mechanisms as an optimization problem that minimizes the expected loss associated with the random noise mechanism while encoding differential privacy as constraints. Through detailed analyses and by leveraging tools from distributionally robust optimization, they develop an efficient optimization algorithm and derive implementable solutions with provable guarantees to solve the problem within seconds.