The Large Margin Mechanism for Differentially Private Maximization

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. Thisproblem has been used as a subroutine 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 forprivate maximization that guarantees approximate differential privacy. Its applicability is demonstrated on two fundamental tasks in data mining and machine learning.