Private Multiplicative Weights Beyond Linear Queries

By Jonathan Ullman. 2014

61 citations recorded by the source corpus.

A wide variety of fundamental data analyses in machine learning, such as linear and logistic regression, require minimizing a convex function defined by the data. Since the data may contain sensitive information about individuals, and these analyses can leak that sensitive information, it is important to be able to solve convex minimization in a privacy-preserving way. A series of recent results show how to accurately solve a single convex minimization problem in a differentially private manner. However, the same data is often analyzed repeatedly, and little is known about solving multiple convex minimization problems with differential privacy. For simpler data analyses, such as linear queries, there are remarkable differentially private algorithms such as the private multiplicative weights mechanism (Hardt and Rothblum, FOCS 2010) that accurately answer exponentially many distinct queries. In this work, we extend these results to the case of convex minimization and show how to give accurate and differentially private solutions to exponentially many convex minimization problems on a sensitive dataset.

Subfields: Artificial Intelligence, Computer Science Applications, Privacy & Security

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

In Privacy & Security

Citations in the corpus

Privacy Amplification by Iteration (2018, background): “The question of optimizing multiple loss functions was also studied in [21], [40].”
Tight Lower Bounds for Differentially Private Selection (2017, background): “Selection problems appear in many natural statistical problems, including private multiple hypothesis testing [1], sparse linear regression [2], [3], finding frequent itemsets [4], and as subroutines in algorithms for answering exponentially many statistical queries [5], [6], [7], [8], [9], approxim”
Algorithmic stability for adaptive data analysis (2015, methodology): “ential Mechanism [MT07]. For the special case of convex minimization queries over an inﬁnite domain, we use the optimal algorithm of [BST14] when kis small, and when kis large, we use an algorithm of [Ull15] that accurately answers exponentially many such queries. Other Notions of Stability Our tech”
Calibration for the (Computationally-Identifiable) Masses (2017, methodology): “This implementation borrows ideas from the literature on diﬀerentially private query release and optimization [HR10, Ull15, HRRU14].”
Private Stochastic Convex Optimization with Optimal Rates (2019, background): “The problem of ERM with differential privacy (DP-ERM) has been well-studied and asymptotically tight upper and lower bounds on excess loss 1 are known [CM08, CMS11, JKT12, KST12, ST13, SCS13, DJW13, Ull15, JT14, BST14, TTZ15, STU17, WLK + 17, WYX17, INS + 19].”
More General Queries and Less Generalization Error in Adaptive Data Analysis (2015, methodology): “When k is large, we can use an algorithm of [Ull15] that accurately answers exponentially many such queries.”
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (2015, unknown): “Finally, we give corollaries for two problems in differential privacy: (a) new algorithms for solving convex programs with the stringent local differential privacy; (b) strengthening and generalization of algorithms for answering sequences of convex minimization queries differentially privately give”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, background): “…studied extensively for over a decade (see, e.g., (Chaudhuri and Monteleoni, 2008; Chaudhuri et al., 2011; Jain et al., 2012; Kifer et al., 2012; Smith and Thakurta, 2013; Bassily et al., 2014; Ullman, 2015; Jain and Thakurta, 2014; Talwar et al., 2015; Bassily et al., 2019; Feldman et al., 2020)).”
Differentially Private Data Publishing and Analysis: A Survey (2017, unknown): “Ullman [73] considered the regression problem as”
Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data (2019, result): “Previous results are either for linear queries (Blasiok et al., 2019; Bassily, 2018), or in the central DP model (Ullman, 2015).”