The Large Margin Mechanism for Differentially Private Maximization

By Kamalika Chaudhuri, Daniel J. Hsu, Shuang Song. 2014

39 citations recorded by the source corpus.

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. 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.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

Advanced Probabilistic Couplings for Differential Privacy (2016, neutral): “One interesting example combining accuracy and privacy is the large margin mechanism [15].”
The Price of Selection in Differential Privacy (2017, background): “It is especially desirable to ensure differential privacy Dwork et al. (2006), which ensures that no individual’s information has a significant influence on the information released about the dataset.”
Private selection from private candidates (2018, background): “Several other mechanisms for the private selection problem have been proposed, that improve the utility guarantee under stronger assumptions [3, 6, 28, 29, 32, 34].”
Automatic Discovery of Privacy–Utility Pareto Fronts (2019, background): “The final related question revolves around the differentially private “selection” or “maximization” problem [11], which asks: how can an item be chosen (from a predefined universe) to maximize a data-dependent function while still protecting the privacy of that data? Here, Liu et al.”
Differentially Private Release and Learning of Threshold Functions (2015, background): “[11] gave sample complexity upper bounds based on properties of the data distribution that do not depend explicitly on |X|.”
Privacy-preserving Analysis of Correlated Data (2016, background): “Recent work has developed a large number of general privacy mechanisms (Dwork et al., 2006; McSherry and Talwar, 2007; Chaudhuri et al., 2011; Nissim et al., 2007; Dwork and Lei, 2009; Chaudhuri et al., 2014) that guarantee differential privacy under different conditions.”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, methodology): “Loss modification methods work by perturbing the loss function with noise, which is subsequently optimized normally using SGD or other optimizers Chaudhuri et al. (2011); Kifer et al. (2012); Phan et al. (2016). For example, Chaudhuri & Monteleoni (2008) introduced a modified regression loss, simila”
Differentially private distributed convex optimization via objective perturbation (2016, background): “The problem considered in [14] is different in the sense that the total space of parameters for optimization is finite, which makes it possible to use the exponential mechanism of [15] to achieve differential privacy.”
Differentially Private Distributed Convex Optimization via Functional Perturbation (2015, background): “, [10]–[16], as an intermediate, usually centralized step for solving other learning or statistical tasks.”
Renyi Differential Privacy Mechanisms for Posterior Sampling (2017, background): “The most popular relaxation is approximate DP [6], and a number of uniquely approximate DP mechanisms have been designed by [7, 16, 3, 1] among others.”