The Large Margin Mechanism for Differentially Private Maximization
This work addresses a key bottleneck in privacy-preserving algorithms for statistics and machine learning by providing a more versatile solution compared to previous range-dependent or restricted methods.
The paper tackles the private maximization problem in differential privacy, which involves selecting an item that maximizes a data-dependent function while ensuring privacy, and introduces a general-purpose, range-independent algorithm that guarantees approximate differential privacy, demonstrating its applicability on fundamental tasks in data mining and machine learning.
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.