Timezone: »

The Large Margin Mechanism for Differentially Private Maximization
Kamalika Chaudhuri · Daniel Hsu · Shuang Song

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D #None

A basic problem in the design of privacy-preserving algorithms is the \emph{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.

Author Information

Kamalika Chaudhuri (UCSD)
Daniel Hsu (Columbia University)
Shuang Song (UC San Diego)

More from the Same Authors