22 citations · 59 across the 12 of their papers we have counts for
6 papers · 1 filter
Multiclass versus Binary Differentially Private PAC Learning
Mark Bun, Marco Gaboardi, Satchit Sivakumar
We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning. We apply this transformation to a recently proposed binary private P…
Differentially Private Correlation Clustering
Mark Bun, Marek Eliáš, Janardhan Kulkarni
Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differ…
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Gavin Brown, Mark Bun, Vitaly Feldman +2
Modern machine learning models are complex and frequently encode surprising amounts of information about individual inputs. In extreme cases, complex models appear to memorize enti…
A Computational Separation between Private Learning and Online Learning
Mark Bun
A recent line of work has shown a qualitative equivalence between differentially private PAC learning and online learning: A concept class is privately learnable if and only if it…
New Oracle-Efficient Algorithms for Private Synthetic Data Release
Giuseppe Vietri, Grace Tian, Mark Bun +2
We present three new algorithms for constructing differentially private synthetic data---a sanitized version of a sensitive dataset that approximately preserves the answers to a la…
Efficient, Noise-Tolerant, and Private Learning via Boosting
Mark Bun, Marco Leandro Carmosino, Jessica Sorrell
We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-…