The Large Margin Mechanism for Differentially Private Maximization
Authors: Kamalika Chaudhuri, Daniel J. Hsu, Shuang Song
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. ... Our algorithm, which we call the large margin mechanism, automatically exploits large margins when they exist to simultaneously (i) satisfy approximate differential privacy (Theorem 2), as well as (ii) provide a utility guarantee that depends (logarithmically) only on the number of near maximizers, rather than the universe size (Theorem 3). We complement our algorithm with a lower bound, showing that the utility of any approximate differentially private algorithm must deteriorate with the number of near maximizers (Theorem 1). A consequence of our lower bound is that rangeindependence cannot be achieved with pure differential privacy (Proposition 1). |
| Researcher Affiliation | Academia | Kamalika Chaudhuri UC San Diego La Jolla, CA kamalika@cs.ucsd.edu Daniel Hsu Columbia University New York, NY djhsu@cs.columbia.edu Shuang Song UC San Diego La Jolla, CA shs037@eng.ucsd.edu |
| Pseudocode | Yes | Algorithm 1 The large margin mechanism LMM(α, δ, D) input Privacy parameters α > 0 and δ (0, 1), database D X n. output Item I U. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper refers to a 'sensitive dataset D' and applies theoretical analysis to problems like 'Frequent Itemset Mining' and 'Private PAC Learning', but it does not specify any particular publicly available datasets with access information that were used for empirical training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe specific dataset splits (training, validation, test) for empirical reproduction. |
| Hardware Specification | No | The paper does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper does not provide specific experimental setup details, hyperparameters, or training configurations. |