Timezone: »

 
Poster
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
in Poster Session »

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.

[ PDF] 

Author Information

Kamalika Chaudhuri (UCSD)
Daniel Hsu (Columbia University)

See <https://www.cs.columbia.edu/~djhsu/>

Shuang Song (Google)

More from the Same Authors