The Large Margin Mechanism for Differentially Private Maximization

Abstract

A basic problem in the design of privacy-preserving algorithms is the private maximization problem: the goal is to pick an item from a universe that (approximately) maximizes a data-dependent function, all under the constraint of differential privacy. This problem has been used as a sub-routine in many privacy-preserving algorithms for statistics and machine-learning. Previous algorithms for this problem are either range-dependent---i.e., their utility diminishes with the size of the universe---or only apply to very restricted function classes. This work provides the first general-purpose, range-independent algorithm for private maximization that guarantees approximate differential privacy. Its applicability is demonstrated on two fundamental tasks in data mining and machine learning.

References in corpus (2)

• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• Privacy-Preserving Data Sharing for Genome-Wide Association Studies

Cited by in corpus (5)

• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Advanced Probabilistic Couplings for Differential Privacy
• Permute-and-Flip: A new mechanism for differentially private selection
• Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
• Pufferfish Privacy Mechanisms for Correlated Data