Privacy Preserving Machine Learning (NeurIPS 2018 Workshop)

Schedule

8:30	Welcome and Introduction
8:50	Invited talk: Ian Goodfellow — Scalable PATE and the Secret Sharer [slides] [keynote]
Coming soon
9:40	Invited talk: Shafi Goldwasser — Machine Learning and Cryptography: Challenges and Opportunities
At the mid eighties researchers in computational learning theory pointed the way to examples of hard learning tasks such as learning parity with noise (LPN) and learning with errors (LWE) which have been extremely useful for building sophisticated cryptographic primitives such as homomorphic encryption which are unbreakable if LPN and LWE are hard to learn. Today, with the rise of machine learning algorithms that use large amounts of data to come up with procedures which have the potential to replace human decision processes, cryptography, in turn, stands to provide machine learning, tools for keeping data private during both training and inference phases of ML and to provide methods to verify adherence of models with data. These promise to be important steps in ensuring the safe transition of power from human to algorithmic decision making.
10:30	Coffee break
11:00	Privacy Amplification by Iteration (contributed talk) Vitaly Feldman, Ilya Mironov, Kunal Talwar and Abhradeep Thakurta
Many commonly used learning algorithms work by iteratively updating an intermediate solution using one or a few data points in each iteration. Analysis of differential privacy for such algorithms often involves ensuring privacy of each step and then reasoning about the cumulative privacy cost of the algorithm. This is enabled by composition theorems for differential privacy that allow releasing of all the intermediate results. In this work, we demonstrate that for contractive iterations, not releasing the intermediate results strongly amplifies the privacy guarantees. We describe several applications of this new analysis technique to solving convex optimization problems via noisy stochastic gradient descent. For example, we demonstrate that a relatively small number of non-private data points from the same distribution can be used to close the gap between private and non-private convex optimization. In addition, we demonstrate that we can achieve guarantees similar to those obtainable using the privacy-amplification-by-sampling technique in several natural settings where that technique cannot be applied.
11:15	Subsampled Renyi Differential Privacy and Analytical Moments Accountant (contributed talk) [slides] Yu-Xiang Wang, Borja Balle and Shiva Kasiviswanathan
We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the Renyi Differential Privacy (RDP) parameters for algorithms that: (1) subsample the dataset, and then (2) applies a randomized mechanism M to the subsample, in terms of the RDP parameters of M and the subsampling probability parameter. Our results generalize the moments accounting technique, developed by Abadi et al. [CCS'16] for the Gaussian mechanism, to any subsampled RDP mechanism.
11:30	The Power of The Hybrid Model for Mean Estimation (contributed talk) Yatharth Dubey and Aleksandra Korolova
In this work we explore the power of the hybrid model of differential privacy (DP) proposed in~\cite{blender}, where some users desire the guarantees of the local model of DP and others are content with receiving the trusted curator model guarantees. In particular, we study the accuracy of mean estimation algorithms for arbitrary distributions in bounded support. We show that a hybrid mechanism which combines the sample mean estimates obtained from the two groups in an optimally weighted convex combination performs a constant factor better for a wide range of sample sizes than natural benchmarks. We analyze how this improvement factor is parameterized by the problem setting and how it varies with sample size.
11:45	Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (contributed talk) [slides] Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar and Abhradeep Thakurta
Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, when each user's value may change only a small number of times. We describe an algorithm whose privacy cost is polylogarithmic in the number of times the statistic is collected. More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general technique, that any permutation-invariant algorithm satisfying $\varepsilon$-local differential privacy will satisfy $(O(\varepsilon \sqrt{\log \frac 1 \delta} / \sqrt{n}), \delta)$-central differential privacy. In the process, we clarify how the high noise and $\sqrt{n}$ overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a final, practical corollary, our results also imply that industrial deployments of LDP mechanism may have much lower privacy cost than their advertised $\varepsilon$ would indicate---at least if reports are anonymized.
12:00	Lunch break
13:30	Invited talk: Kamalika Chaudhuri — Challenges in the Privacy-Preserving Analysis of Structured Data [slides]
Much data analysis today is done on sensitive data, and particular privacy challenges arise when this data is sensitive and structured. In this talk I will describe two such challenges in the privacy-preserving analysis of complex, structured data that we have been working on in my group. The first is continual release of graph statistics in an online manner from an expanding graph, which is motivated by a problem in HIV epidemiology. Even though node differentially private release of graph statistics is highly challenging, here we will describe how we can get a differentially private solution for this problem that performs better than the natural sequential composition baseline. Next, I will talk about analysis of sensitive structured, correlated data, while still preserving the privacy of events in the data. Differential privacy does not adequately address privacy issues in this kind of data, and hence will look at a form of inferential privacy, called Pufferfish, that is more appropriate. We will provide mechanisms, establish their composition properties, and finally evaluate them on real data on physical activity measurements across time.
14:20	Invited talk: Adam Smith — Models for private data analysis of distributed data [slides]
This talk will present a partial survey of the proposed (and implemented) models for private analysis of distributed data, together with some new results.
15:10	Coffee break
15:30	DP-MAC: The Differentially Private Method of Auxiliary Coordinates for Deep Learning (contributed talk) Frederik Harder, Jonas Köhler, Max Welling and Mijung Park
Developing a differentially private deep learning algorithm is challenging, due to the difficulty in analyzing the sensitivity of objective functions that are typically used to train deep neural networks. Many existing methods resort to the stochastic gradient descent algorithm and apply a pre-defined sensitivity to the gradients for privatizing weights. However, their slow convergence typically yields a high cumulative privacy loss. Here, we take a different route by employing the method of auxiliary coordinates, which allows us to independently update the weights per layer by optimizing a per-layer objective function. This objective function can be well approximated by a low-order Taylor's expansion, in which sensitivity analysis becomes tractable. We perturb the coefficients of the expansion for privacy, which we optimize using more advanced optimization routines than SGD for faster convergence. We empirically show that our algorithm provides a decent trained model quality under a modest privacy budget.
15:45	Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (contributed talk) Florian Tramer and Dan Boneh
As Machine Learning (ML) gets applied to security-critical or sensitive domains, there is a growing need for integrity and privacy for outsourced ML computations. A pragmatic solution comes from Trusted Execution Environments (TEEs), which use hardware and software protections to isolate sensitive computations from the untrusted software stack. However, these isolation guarantees come at a price in performance, compared to untrusted alternatives. This paper initiates the study of high performance execution of Deep Neural Networks (DNNs) in TEEs by efficiently partitioning DNN computations between trusted and untrusted devices. Building upon an efficient outsourcing scheme for matrix multiplication, we propose Slalom, a framework that securely delegates execution of all linear layers in a DNN from a TEE (e.g., Intel SGX or Sanctum) to a faster, yet untrusted, co-located processor. We evaluate Slalom by executing DNNs in an Intel SGX enclave, which selectively delegates work to an untrusted GPU. For two canonical DNNs, VGG16 and MobileNet, we obtain 20× and 6× increases in throughput for verifiable inference, and 11× and 4× for verifiable and private inference.
16:00	Secure Two Party Distribution Testing (contributed talk) [slides] Alexandr Andoni, Tal Malkin and Negev Shekel Nosatzki
We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have t samples from, respectively, distributions a and b over [n], and they need to test whether a=b or a,b are ε-far (in the ℓ1 distance) for some fixed ε>0. This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the two-party setting has evaded attention so far. We address two fundamental aspects of the two-party setting: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other's input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have t samples from distributions a and b respectively, which may be correlated; the question is whether a,b are independent of ε-far from being independent. Our contribution is three-fold: ∙ Communication: we show how to gain communication efficiency as we have more samples, beyond the information-theoretic bound on t. Furthermore, the gain is polynomially better than what one may obtain by adapting one-party algorithms. For the closeness testing, our protocol has communication s=Θ_ε(n^2/t^2) as long as t is at least the information-theoretic minimum number of samples. For the independence testing over domain [n]×[m], where n≥m, we obtain s=O_ε(n^2m/t^2+nm/t+m^1/2). ∙ Security: we define the concept of secure distribution testing and argue that it must leak at least some minimal information when the promise is not satisfied. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter. ∙ Lower bounds: we prove tightness of our trade-off for the closeness testing, as well as that the independence testing requires tight Ω(m^1/2) communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2-party communication lower bounds for testing problems, where the inputs represent a set of i.i.d. samples.
16:15	Private Machine Learning in TensorFlow using Secure Computation (contributed talk) [slides] Morten Dahl, Jason Mancuso, Yann Dupis, Ben DeCoste, Morgan Giraud, Ian Livingstone, Justin Patriquin and Gavin Uhma
We present a framework for experimenting with secure multi-party computation directly in TensorFlow. By doing so we benefit from several properties valuable to both researchers and practitioners, including tight integration with ordinary machine learning processes, existing optimizations for distributed computation in TensorFlow, high-level abstractions for expressing complex algorithms and protocols, and an expanded set of familiar tooling. We give an open source implementation of a state-of-the-art protocol and report on concrete benchmarks using typical models from private machine learning.
16:30	Spotlight talks
[Cynthia Dwork and Vitaly Feldman] Privacy-preserving Prediction (#05) [Garrett Bernstein and Daniel Sheldon] Differentially Private Bayesian Inference for Exponential Families (#03) [Di Wang, Adam Smith and Jinhui Xu] High Dimensional Sparse Linear Regression under Local Differential Privacy: Power and Limitations (#11) [Ashwin Machanavajjhala and Kamalika Chaudhuri] Capacity Bounded Differential Privacy (#25) [Aurélien Bellet, Rachid Guerraoui and Hadrien Hendrikx] Who started this gossip? Differentially private rumor spreading (#26) [Antti Koskela and Antti Honkela] Learning rate adaptation for differentially private stochastic gradient descent (#38) [Kareem Amin, Travis Dick, Alex Kulesza, Andres Medina and Sergei Vassilvitskii] Private Covariance Estimation via Iterative Eigenvector Sampling (#45) [Kareem Amin, Alex Kulesza, Andres Munoz Medina and Sergei Vassilvitskii] Bias Variance Trade-off in Differential Privacy (#53) [Nicolas Loizou, Peter Richtarik, Filip Hanzely, Jakub Konecny and Dmitry Grishchenko] A Privacy Preserving Randomized Gossip Algorithm via Controlled Noise Insertion (#57) [Brendan McMahan and Galen Andrew] A General Approach to Adding Differential Privacy to Iterative Training Procedures (#62) [Da Yu, Huishuai Zhang and Wei Chen] Improving the Gradient Perturbation Approach for Differentially Private Optimization (#70) [Alexandra Schofield, Aaron Schein, Zhiwei Steven Wu and Hanna Wallach] A Variational Inference Approach for Locally PrivateInference of Poisson Factorization Models (#63) [Judy Hoffman, Mehryar Mohri and Ningshan Zhang] Algorithms and Theory for Multiple-Source Adaptation (#52) [Martin Bertran, Natalia Martinez, Afroditi Papadaki, Qiang Qiu, Miguel Rodrigues and Guillermo Sapiro] Learning Representations for Utility and Privacy: An Information-Theoretic Based Approach (#15) [Fabrice Benhamouda and Marc Joye] How to Profile Privacy-Conscious Users in Recommender Systems (#32) [Koen Lennart van der Veen, Ruben Seggers, Peter Bloem and Giorgio Patrini] Three Tools for Practical Differential Privacy (#29) [Vasyl Pihur, Aleksandra Korolova, Frederick Liu, Subhash Sankuratripati, Moti Yung, Dachuan Huang and Ruogu Zeng] Differentially Private "Draw and Discard" Machine Learning (#60) [Hsin-Pai Cheng, Patrick Yu, Haojing Hu, Feng Yan, Shiyu Li, Hai Li and Yiran Chen] LEASGD: an Efficient and Privacy-Preserving Decentralized Algorithm for Distributed Learning (#01) [Joshua Allen, Bolin Ding, Janardhan Kulkarni, Harsha Nori, Olga Ohrimenko and Sergey Yekhanin] An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (#12) [Antoine Boutet, Théo Jourdan and Carole Frindel] Toward privacy in IoT mobile devices for activity recognition (#13) [Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi and Todd Mytkowicz] CHET: Compiler and Runtime for Homomorphic Evaluation of Tensor Programs (#14) [Theo Ryffel, Andrew Trask, Morten Dahl, Bobby Wagner, Jason Mancuso, Daniel Rueckert and Jonathan Passerat-Palmbach] A generic framework for privacy preserving deep learning (#43) [Valerie Chen, Valerio Pastro and Mariana Raykova] Secure Computation for Machine Learning With SPDZ (#44) [Phillipp Schoppmann, Adria Gascon, Mariana Raykova and Benny Pinkas] Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning (#51) [Siddharth Garg, Zahra Ghodsi, Carmit Hazay, Yuval Ishai, Antonio Marcedone and Muthuramakrishnan Venkitasubramaniam] Outsourcing Private Machine Learning via Lightweight Secure Arithmetic Computation (#66) [Hao Chen, Ilaria Chillotti, Oxana Poburinnaya, Ilya Razenshteyn and M. Sadegh Riazi] Scaling Up Secure Nearest Neighbor Search (#33) [Yunhui Long, Vincent Bindschaedler and Carl Gunter] Towards Measuring Membership Privacy (#09) [video]
17:15	Poster session
18:15	Wrap up

Accepted Papers

Links to pdfs as well as abstracts will be added soon.

Hsin-Pai Cheng, Patrick Yu, Haojing Hu, Feng Yan, Shiyu Li, Hai Li and Yiran Chen
LEASGD: an Efficient and Privacy-Preserving Decentralized Algorithm for Distributed Learning [arxiv]

Distributed learning systems have enabled training large-scale models over a large amount of data in significantly shorter time. In this paper, we focus on decentralized distributed deep learning systems and aim to achieve differential privacy with good convergence rate and low communication cost. To achieve this goal, we propose a new learning algorithm LEASGD (Leader-Follower Elastic Averaging Stochastic Gradient Descent), which is driven by a novel Leader-Follower topology and a differential privacy model. We provide a theoretical analysis of the convergence rate and the trade-off between the performance and privacy in the private setting. The experimental results show that LEASGD outperforms state-of-the-art decentralized learning algorithm DPSGD by achieving steadily lower loss within the same iterations and by reducing the communication cost by 30%. In addition, LEASGD spends less differential privacy budget and has higher final accuracy result than DPSGD under private setting.

Garrett Bernstein and Daniel Sheldon
Differentially Private Bayesian Inference for Exponential Families [arxiv]

The study of private inference has been sparked by growing concern regarding the analysis of data when it stems from sensitive sources. We present the first method for private Bayesian inference in exponential families that properly accounts for noise introduced by the privacy mechanism. It is efficient because it works only with sufficient statistics and not individual data. Unlike other methods, it gives properly calibrated posterior beliefs in the non-asymptotic data regime.

Cynthia Dwork and Vitaly Feldman
Privacy-preserving Prediction [arxiv]

Ensuring differential privacy of models learned from sensitive user data is an important goal that has been studied extensively in recent years. It is now known that for some basic learning problems, especially those involving high-dimensional data, producing an accurate private model requires much more data than learning without privacy. At the same time, in many applications it is not necessary to expose the model itself. Instead users may be allowed to query the prediction model on their inputs only through an appropriate interface. Here we formulate the problem of ensuring privacy of individual predictions and investigate the overheads required to achieve it in several standard models of classification and regression.
We first describe a simple baseline approach based on training several models on disjoint subsets of data and using standard private aggregation techniques to predict. We show that this approach has nearly optimal sample complexity for (realizable) PAC learning of any class of Boolean functions. At the same time, without strong assumptions on the data distribution, the aggregation step introduces a substantial overhead. We demonstrate that this overhead can be avoided for the well-studied class of thresholds on a line and for a number of standard settings of convex regression. The analysis of our algorithm for learning thresholds relies crucially on strong generalization guarantees that we establish for all differentially private prediction algorithms.

Bolin Ding, Janardhan Kulkarni and Sergey Yekhanin
A Distributed Algorithm For Differentially Private Heavy Hitters

In this paper we present a simple distributed algorithm for learning the heavy hitters in a stream of data in the local model of differential privacy. Our algorithm is efficient in the sense that its running time and communication complexity is polynomial in the input size. Furthermore, our algorithm achieves the optimal error guarantee for the frequency estimation.

Yunhui Long, Tanmay Gangwani, Haris Mughees and Carl Gunter
Distributed and Secure Machine Learning using Self-tallying Multi-party Aggregation [arxiv]

Privacy preserving multi-party computation has many applications in areas like medicine and online advertisements. In this work, we focus on distributed and secure machine learning. In such a scenario, multiple parties are in possession of sensitive data which cannot be made public. At the same time, if different parties contribute their individual data to a shared pool and run a machine learning algorithm on the combined data, then much richer representative information can be gleaned as compared to using only the individual data pieces. In this work, we propose a framework for distributed secure machine learning among untrusted individuals. The framework consists of two parts: a 2-step training protocol based on homomorphic addition and a zero knowledge proof for data validity. By combining these two techniques, our framework provides privacy of per-user data, prevents against a malicious user contributing corrupted data to the shared pool, enables each user to self-compute the results of the algorithm without relying on external trusted third parties, and requires no private channels between groups of users. We show how different ML algorithms such as Latent Dirichlet Allocation, Na\"ive Bayes, Decision Trees etc. fit our framework for distributed, secure computing. We implement our protocol using Elliptic-Curve ElGamal, and show overheads for generating and verifying the zero-knowledge proofs which we use.

Di Wang, Adam Smith and Jinhui Xu
High Dimensional Sparse Linear Regression under Local Differential Privacy: Power and Limitations

In this paper, we study high dimensional sparse linear regression under the Local Differential Privacy (LDP) model, and give both negative and positive results. On the negative side, we show that polynomial dependency on the dimensionality $p$ of the space is unavoidable in the estimation error under the non-interactive local model, if the privacy of the whole dataset needs to be preserved. Similar limitations also exist for other types of error measurements and in the (sequential) interactive local. This indicates that differential privacy in high dimensional space is unlikely achievable for the problem. On the positive side, we show that the optimal rate of the error estimation can be made logarithmically depending on $p$ (i.e., $\log p$) under the local model, if only the privacy of the responses (labels) is to be preserved, where the upper bound is obtained by a new method called Differentially Private Iterative Hard Thresholding (DP-IHT), which is interesting in its own right.

Joshua Allen, Bolin Ding, Janardhan Kulkarni, Harsha Nori, Olga Ohrimenko and Sergey Yekhanin
An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors [arxiv]

Differential privacy has emerged as the main definition for private big data analysis and machine learning. The {\em global} model of differential privacy, which assumes users trust the data collector, provides strong privacy guarantees and introduces small errors in the output. In contrast, applications of differential privacy in commercial systems by Apple, Google, and Microsoft, use the {\em local model}. Here users do not trust the data collector and hence randomize their data before sending it to the data collector. Unfortunately, local model is too strong for several important applications and hence is limited in its scope. In this work, we propose a framework based on trusted processors and a new definition of differential privacy called {\em Oblivious Differential Privacy}, which combines the best of both local and global models. The algorithms we design in this framework show interesting interplay of ideas from the streaming algorithms, oblivious algorithms, and differential privacy.

Antoine Boutet, Théo Jourdan and Carole Frindel
Toward privacy in IoT mobile devices for activity recognition [PDF]

Recent advances in wireless sensors for personal healthcare allow to recognise human real-time activities with mobile devices. While the analysis of those datas- tream can have many benefits from a health point of view, it can also lead to privacy threats by exposing highly sensitive information. In this paper, we propose a privacy-preserving framework for activity recognition. This framework relies on a machine learning technique to efficiently recognise the user activity pattern, useful for personal healthcare monitoring, while limiting the risk of re-identification of users from biometric patterns that characterizes each individual. To achieve that, we rely on a carefully features extraction scheme in both temporal and frequency domain and apply a generalisation-based approach on features leading to re-identify users. We extensively evaluate our framework with a reference dataset: results show an accurate activity recognition (87%) while limiting the re-identifation rate (33%). This represents a slightly decrease of utility (9%) against a large privacy improvement (53%) compared to state-of-the-art baselines.

Roshan Dathathri, Olli Saarikivi, Hao Chen, Kim Laine, Kristin Lauter, Saeed Maleki, Madanlal Musuvathi and Todd Mytkowicz
CHET: Compiler and Runtime for Homomorphic Evaluation of Tensor Programs [PDF]

Fully Homomorphic Encryption (FHE) provides the promise of performing arbitrary computations on encrypted data without requiring the decryption key. FHE can enable novel privacy-sensitive machine learning scenarios. However, programming FHE applications today is hard for non-FHE experts due to two challenges. First, achieving practical performance requires performing FHE-specific optimizations, including maximizing the vectorizing/batching capabilities of the underlying FHE scheme. Second, FHE schemes involve a careful choice of encryption parameters that tradeoff security for correctness, performance, and message bloat.
This paper proposes CHET, a compiler and runtime for homomorphically evaluating tensor programs. Given a neural network specified as a high-level tensor circuit, CHET optimizes and compiles this circuit to an interface called the Homomorphic Instruction Set Architecture (HISA), which can then be targetted to different encryption libraries. CHET automatically chooses the encryption parameters and layouts that maximize performance for a given security and precision requirements. As a result, CHET generated code is faster than expert-optimized implementations.

Martin Bertran, Natalia Martinez, Afroditi Papadaki, Qiang Qiu, Miguel Rodrigues and Guillermo Sapiro
Learning Representations for Utility and Privacy: An Information-Theoretic Based Approach [PDF]

Protecting a secret while disclosing related information (utility) is a well known challenge in privacy; both users and service providers can and should collaborate to protect privacy, and this paper addresses this paradigm. Here we analyze the limits of information-theoretic privacy, and use these to design a data-driven privacy-preserving representation of the disclosed data X that is maximally informative about the utility variable U and minimally informative about the secret variable S. We describe important use-case scenarios where the utility providers are willing to collaborate, at least partially, with the sanitization process. In this setting, we limit the possible sanitization functions to space-preserving transformations, where the same algorithm can be used to infer the utility variable on both sanitized and unsanitized data. We illustrate this approach though two use cases; subject-within-subject, where we tackle the problem of having an identity detector (from facial images) that works only on a consenting subset of users; and emotion-and-gender, where we tackle the issue of hiding independent variables, as is the case of hiding gender while preserving emotion detection.

Florian Tramer and Dan Boneh
Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware (contributed talk) [arxiv]

As Machine Learning (ML) gets applied to security-critical or sensitive domains, there is a growing need for integrity and privacy for outsourced ML computations. A pragmatic solution comes from Trusted Execution Environments (TEEs), which use hardware and software protections to isolate sensitive computations from the untrusted software stack. However, these isolation guarantees come at a price in performance, compared to untrusted alternatives. This paper initiates the study of high performance execution of Deep Neural Networks (DNNs) in TEEs by efficiently partitioning DNN computations between trusted and untrusted devices. Building upon an efficient outsourcing scheme for matrix multiplication, we propose Slalom, a framework that securely delegates execution of all linear layers in a DNN from a TEE (e.g., Intel SGX or Sanctum) to a faster, yet untrusted, co-located processor. We evaluate Slalom by executing DNNs in an Intel SGX enclave, which selectively delegates work to an untrusted GPU. For two canonical DNNs, VGG16 and MobileNet, we obtain 20× and 6× increases in throughput for verifiable inference, and 11× and 4× for verifiable and private inference.

Ashwin Machanavajjhala and Kamalika Chaudhuri
Capacity Bounded Differential Privacy

Differential privacy, a notion of algorithmic stability, is a gold standard for measuring the additional risk an algorithm's output poses to the privacy of any single record in the dataset. Differential privacy is defined as the distance between the output distribution of an algorithm on neighboring datasets that differ in one entry. In this work, we present a novel relaxation of differential privacy, called capacity bounded differential privacy, where the adversary that distinguishes output distributions is assumed to be capacity-bounded -- i.e. bounded not in computational power, but rather in terms of the function class from which their attack algorithm is drawn. We model adversaries in terms of restricted f-divergences between probability distributions, and study properties of the definition and algorithms that satisfy them.

Aurélien Bellet, Rachid Guerraoui and Hadrien Hendrikx
Who started this gossip? Differentially private rumor spreading

Gossip algorithms, also called rumor spreading or epidemic protocols, are widely used to disseminate information in massive peer-to-peer networks. These algorithms are often claimed to guarantee privacy because of the uncertainty they introduce on the node that started the dissemination. But is that claim really true? Can one indeed start a gossip and safely hide in the crowd?
This paper is the first to study gossip protocols using the mathematical tools of differential privacy to determine the extent to which the source of a gossip can be traceable. Considering the case of a complete graph in which a subset of the nodes are curious sensors, we derive tight lower bounds on the differential privacy of the gossip source. The key to ensure differential privacy is to allow nodes to stop gossiping after some time, which essentially boils down to reducing the dissemination speed. Yet, we show that we can devise a gossip algorithm achieving both logarithmic spreading time and near-optimal privacy.

Koen Lennart van der Veen, Ruben Seggers, Peter Bloem and Giorgio Patrini
Three Tools for Practical Differential Privacy [PDF]

Differentially private learning on real-world data poses challenges for standard machine learning practice: privacy guarantees are difficult to interpret, hyperparameter tuning on private data reduces the privacy budget, and ad-hoc privacy attacks are often required to test model privacy. We introduce three tools to make differentially private machine learning more practical: (1) simple sanity checks which can be carried out in a centralized manner before training, (2) an adaptive clipping bound to reduce the effective number of tuneable privacy parameters, and (3) we show that large-batch training improves model performance.

Fabrice Benhamouda and Marc Joye
How to Profile Privacy-Conscious Users in Recommender Systems [arxiv]

Matrix factorization is a popular method to build a recommender system. In such a system, existing users and items are associated to a low-dimension vector called a profile. The profiles of a user and of an item can be combined (via inner product) to predict the rating that the user would get on the item. One important issue of such a system is the so-called cold-start problem: how to allow a user to learn her profile, so that she can then get accurate recommendations?
While a profile can be computed if the user is willing to rate well-chosen items and/or provide supplemental attributes or demographics (such as gender), revealing this additional information is known to allow the analyst of the recommender system to infer many more personal sensitive information. We design a protocol to allow privacy-conscious users to benefit from matrix-factorization-based recommender systems while preserving their privacy. More precisely, our protocol enables a user to learn her profile, and from that to predict ratings without the user revealing any personal information. The protocol is secure in the standard model against semi-honest adversaries.

Hao Chen, Ilaria Chillotti, Oxana Poburinnaya, Ilya Razenshteyn and M. Sadegh Riazi
Scaling Up Secure Nearest Neighbor Search

We present a new secure protocol for approximate nearest neighbor search over the Euclidean distance tailored for massive datasets in the semi-honest model. At a high level, our protocol combines additively homomorphic encryption (for distance computation) and garbled circuits (for top-k selection). To achieve good performance, we utilize several algorithmic and implementational improvements. In particular, we show the existence of a linear-sized circuit for approximate top-k selection. As an example, for the SIFT dataset of image descriptors (1 000 000 data points, 128 dimensions), our algorithm when run on two standard Azure instances can retrieve IDs of the 10 nearest neighbors with accuracy 0.92 in less than 4 seconds. This improves by more than an order of magnitude when compared to the alternative approaches.

Vitaly Feldman, Ilya Mironov, Kunal Talwar and Abhradeep Thakurta
Privacy Amplification by Iteration (contributed talk) [arxiv]

Many commonly used learning algorithms work by iteratively updating an intermediate solution using one or a few data points in each iteration. Analysis of differential privacy for such algorithms often involves ensuring privacy of each step and then reasoning about the cumulative privacy cost of the algorithm. This is enabled by composition theorems for differential privacy that allow releasing of all the intermediate results. In this work, we demonstrate that for contractive iterations, not releasing the intermediate results strongly amplifies the privacy guarantees.
We describe several applications of this new analysis technique to solving convex optimization problems via noisy stochastic gradient descent. For example, we demonstrate that a relatively small number of non-private data points from the same distribution can be used to close the gap between private and non-private convex optimization. In addition, we demonstrate that we can achieve guarantees similar to those obtainable using the privacy-amplification-by-sampling technique in several natural settings where that technique cannot be applied.

Antti Koskela and Antti Honkela
Learning rate adaptation for differentially private stochastic gradient descent [arxiv]

Differentially private learning has recently emerged as the leading approach for privacy-preserving machine learning. Differential privacy can complicate learning procedures because each access to the data needs to be carefully designed and carries a privacy cost. For example, standard parameter tuning with a validation set cannot be easily applied. We propose a differentially private algorithm for the adaptation of the learning rate for differentially private stochastic gradient descent (SGD) that avoids the need for validation set use. The idea for the adaptiveness comes from the technique of extrapolation in numerical analysis: to get an estimate for the error against the gradient flow which underlies SGD, we compare the result obtained by one full step and two half-steps. We prove the privacy of the method using the moments accountant mechanism. Empirically we can show that our method is competitive with manually tuned commonly used optimisation methods.

Yu-Xiang Wang, Borja Balle and Shiva Kasiviswanathan
Subsampled Renyi Differential Privacy and Analytical Moments Accountant (contributed talk) [arxiv]

We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the Renyi Differential Privacy (RDP) parameters for algorithms that: (1) subsample the dataset, and then (2) applies a randomized mechanism M to the subsample, in terms of the RDP parameters of M and the subsampling probability parameter. Our results generalize the moments accounting technique, developed by Abadi et al. [CCS'16] for the Gaussian mechanism, to any subsampled RDP mechanism.

Theo Ryffel, Andrew Trask, Morten Dahl, Bobby Wagner, Jason Mancuso, Daniel Rueckert and Jonathan Passerat-Palmbach
A generic framework for privacy preserving deep learning [arxiv]

We detail a new framework for privacy preserving deep learning and discuss its assets. The framework puts a premium on ownership and secure processing of data and introduces a valuable representation based on chains of commands and tensors. This abstraction allows one to implement complex privacy preserving constructs such as Federated Learning, Secure Multiparty Computation, and Differential Privacy while still exposing a familiar deep learning API to the end-user. We report early results on the Boston Housing and Pima Indian Diabetes datasets. While the privacy features apart from Differential Privacy do not impact the prediction accuracy, the current implementation of the framework introduces a significant overhead in performance, which will be addressed at a later stage of the development. We believe this work is an important milestone introducing the first reliable, general framework for privacy preserving deep learning.

Valerie Chen, Valerio Pastro and Mariana Raykova
Secure Computation for Machine Learning With SPDZ [PDF]

Secure Multi-Party Computation (MPC) is an area of cryptography that enables computation on sensitive data from multiple sources while maintaining privacy guarantees. However, theoretical MPC protocols often do not scale efficiently to real-world data. This project investigates the efficiency of the SPDZ framework}, which provides an implementation of an MPC protocol with malicious security, in the context of popular machine learning (ML) algorithms. In particular, we chose applications such as linear regression and logistic regression, which have been implemented and evaluated using semi-honest MPC techniques. We demonstrate that the SPDZ framework outperforms these previous implementations while providing stronger security.

Kareem Amin, Travis Dick, Alex Kulesza, Andres Medina and Sergei Vassilvitskii
Private Covariance Estimation via Iterative Eigenvector Sampling [PDF]

We give a new method for computing a differentially private covariance matrix, suitable for use in a variety of regression settings, from a collection of user data. In contrast to previous methods, our approach has zero failure probability, and can be employed to compute the full matrix (not just the top k eigenvectors). As part of our analysis, we derive a precise expression for allocating the privacy budget epsilon among different components to minimize overall error. We then show empirically that our method outperforms previous state-of-the-art approaches, yielding lower error and better learning performance.

Alexandr Andoni, Tal Malkin and Negev Shekel Nosatzki
Secure Two Party Distribution Testing (contributed talk) [arxiv]

We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have t samples from, respectively, distributions a and b over [n], and they need to test whether a=b or a,b are ε-far (in the ℓ1 distance) for some fixed ε>0. This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the two-party setting has evaded attention so far.
We address two fundamental aspects of the two-party setting: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other's input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have t samples from distributions a and b respectively, which may be correlated; the question is whether a,b are independent of ε-far from being independent.

Our contribution is three-fold:
∙ Communication: we show how to gain communication efficiency as we have more samples, beyond the information-theoretic bound on t. Furthermore, the gain is polynomially better than what one may obtain by adapting one-party algorithms.
For the closeness testing, our protocol has communication s=Θ_ε(n^2/t^2) as long as t is at least the information-theoretic minimum number of samples. For the independence testing over domain [n]×[m], where n≥m, we obtain s=O_ε(n^2m/t^2+nm/t+m^1/2).
∙ Security: we define the concept of secure distribution testing and argue that it must leak at least some minimal information when the promise is not satisfied. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.
∙ Lower bounds: we prove tightness of our trade-off for the closeness testing, as well as that the independence testing requires tight Ω(m^1/2) communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2-party communication lower bounds for testing problems, where the inputs represent a set of i.i.d. samples.

Phillipp Schoppmann, Adria Gascon, Mariana Raykova and Benny Pinkas
Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning

Exploiting data sparsity is crucial for the scalability of many data analysis tasks. However, existing secure computation approaches for machine learning do not exploit sparsity, or do so in an implicit way in the context of custom protocols. In this work we mirror the development of the field of scientific computing and propose sparse data structures together with secure computation algorithms for common tasks that leverage sparsity for efficiency. We present several instantiations with different trade-offs for a Read-Only Oblivious Map (ROOM) primitive used to access elements in these structures. We build protocols for sparse matrix multiplication that use the ROOM functionality, which can be composed to implement secure variants of essential data analysis tasks such as similarity computation and gradient descent.
We use our constructions for basic operations on sparse data to build secure protocols for non-parametric ($k$-nearest neighbors and naive Bayes classification) and parametric (linear and logistic regression) models that enable secure analysis on high-dimensional datasets. The experimental evaluation of our protocol implementations demonstrates manyfold improvement in the efficiency over state of the art techniques across all applications.

Judy Hoffman, Mehryar Mohri and Ningshan Zhang
Algorithms and Theory for Multiple-Source Adaptation [PDF]

This work considers the multiple-source adaptation problem where the learner only has access to predictors and density estimations trained on source domains, but he has no access to all source data simultaneously. The goal is to combine source predictors to derive an accurate predictor for any unknown mixture target domain. We present the distribution-weighted combination solutions with strong theoretical guarantees for the general stochastic scenario under cross-entropy loss and other similar losses. Moreover, we give new algorithms for determining the solution for the cross-entropy loss and other losses. We report the results on a real-world dataset to show that our algorithm outperforms competing approaches by producing a single robust model that performs well on any target mixture distribution.

Kareem Amin, Alex Kulesza, Andres Munoz Medina and Sergei Vassilvitskii
Bias Variance Trade-off in Differential Privacy [PDF]

Differentially private learning algorithms protect individual participants in the training dataset by guaranteeing that their presence does not significantly change the resulting model. In order to make this promise, such algorithms need to know the maximum contribution that can be made by a single user: the more data an individual can contribute, the more noise will need to be added to protect them. While most existing analyses assume that the maximum contribution is known and fixed in advance we argue that in practice there is a meaningful choice to be made. On the one hand, if we allow users to contribute large amounts of data, we may end up adding excessive noise to protect a few outliers. On the other hand, limiting users to small contributions keeps noise levels low at the cost of potentially discarding significant amounts of excess data, thus introducing bias. Here, we characterize this tradeoff for an empirical risk minimization setting, showing that in general there is a “sweet spot” that depends on measurable properties of the dataset.

Sesh Kumar and Marc Deisenroth
Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms

Differential privacy is concerned about the prediction quality while measuring the privacy impact on individuals whose information is contained in the data.We consider differentially private risk minimization problems with regularizers that induce structured sparsity. These regularizers are known to be convex but are non-differentiable. We analyze the standard differentially private algorithms, such as output perturbation. Output perturbation is a differentially private algorithm that is known to perform well for minimizing risks that are strongly convex. Previous works have derived dimensionality independent excess risk bounds for these cases. In this paper, we assume a particular class of convex but non-smooth regularizers that induce structured sparsity and loss functions for generalized linear models. We derive excess risk bound for output perturbation that depends on the structure of the constraint set.

Morten Dahl, Jason Mancuso, Yann Dupis, Ben DeCoste, Morgan Giraud, Ian Livingstone, Justin Patriquin and Gavin Uhma
Private Machine Learning in TensorFlow using Secure Computation (contributed talk) [arxiv]

We present a framework for experimenting with secure multi-party computation directly in TensorFlow. By doing so we benefit from several properties valuable to both researchers and practitioners, including tight integration with ordinary machine learning processes, existing optimizations for distributed computation in TensorFlow, high-level abstractions for expressing complex algorithms and protocols, and an expanded set of familiar tooling. We give an open source implementation of a state-of-the-art protocol and report on concrete benchmarks using typical models from private machine learning.

Nicolas Loizou, Peter Richtarik, Filip Hanzely, Jakub Konecny and Dmitry Grishchenko
A Privacy Preserving Randomized Gossip Algorithm via Controlled Noise Insertion [PDF]

In this work we present a randomized gossip algorithm for solving the average consensus problem while at the same time protecting the information about the initial private values stored at the nodes. We give iteration complexity bounds for the method and perform extensive numerical experiments.

Yatharth Dubey and Aleksandra Korolova
The Power of The Hybrid Model for Mean Estimation (contributed talk) [arxiv]

In this work we explore the power of the hybrid model of differential privacy (DP) proposed in~\cite{blender}, where some users desire the guarantees of the local model of DP and others are content with receiving the trusted curator model guarantees. In particular, we study the accuracy of mean estimation algorithms for arbitrary distributions in bounded support. We show that a hybrid mechanism which combines the sample mean estimates obtained from the two groups in an optimally weighted convex combination performs a constant factor better for a wide range of sample sizes than natural benchmarks. We analyze how this improvement factor is parameterized by the problem setting and how it varies with sample size.

Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar and Abhradeep Thakurta
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (contributed talk) [arxiv]

Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, when each user's value may change only a small number of times. We describe an algorithm whose privacy cost is polylogarithmic in the number of times the statistic is collected.
More fundamentally---by building on anonymity of the users' reports---we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general technique, that any permutation-invariant algorithm satisfying $\varepsilon$-local differential privacy will satisfy $(O(\varepsilon \sqrt{\log \frac 1 \delta} / \sqrt{n}), \delta)$-central differential privacy. In the process, we clarify how the high noise and $\sqrt{n}$ overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a final, practical corollary, our results also imply that industrial deployments of LDP mechanism may have much lower privacy cost than their advertised $\varepsilon$ would indicate---at least if reports are anonymized.

Vasyl Pihur, Aleksandra Korolova, Frederick Liu, Subhash Sankuratripati, Moti Yung, Dachuan Huang and Ruogu Zeng
Differentially Private "Draw and Discard" Machine Learning [arxiv]

In this work, we propose a novel framework for privacy-preserving client-distributed machine learning. It is motivated by the desire to achieve differential privacy guarantees in the \emph{local} model of privacy in a way that satisfies all systems constraints using \emph{asynchronous} client-server communication and provides attractive model learning properties. We call it ``Draw and Discard'' because it relies on random sampling of models for load distribution (scalability), which also provides additional server-side privacy protections and improved model quality through averaging. We present the mechanics of client and server components of ``Draw and Discard" and demonstrate how the framework can be applied to learning Generalized Linear models. We then analyze the privacy guarantees provided by our approach against several types of adversaries and showcase experimental results that provide evidence for the framework's viability in practical deployments. We believe our framework is the first deployed distributed machine learning approach that operates in the local privacy model.

Brendan McMahan and Galen Andrew
A General Approach to Adding Differential Privacy to Iterative Training Procedures [PDF]

In this work we address the practical challenges of training machine learning models on privacy-sensitive datasets by introducing a modular approach that minimizes changes to training algorithms, provides a variety of configuration strategies for the privacy mechanism, and then isolates and simplifies the critical logic that computes the final privacy guarantees. A key challenge is that training algorithms often require estimating many different quantities (vectors) from the same set of examples --- for example, gradients of different layers in a deep learning architecture, as well as metrics and batch normalization parameters. Each of these may have different properties like dimensionality, approximate norm, and tolerance to noise. By extending previous work on the Moments Accountant for the subsampled Gaussian mechanism, we can provide privacy for such heterogeneous sets of vectors, while also structuring the approach to minimize software engineering challenges.

Alexandra Schofield, Aaron Schein, Zhiwei Steven Wu and Hanna Wallach
A Variational Inference Approach for Locally Private Inference of Poisson Factorization Models [PDF]

Recent work that introduces local privacy to Bayesian Poisson factorization model inference, but its proposed MCMC algorithm for inference suffers from significant performance issues. We derive a coordinate ascent variational inference algorithm to infer factorization models efficiently from private data. Our model relies on several new properties we prove about Bessel distributions. We demonstrate that this produces a factor of 20 speedup in a synthetic experiment for model inference.

Siddharth Garg, Zahra Ghodsi, Carmit Hazay, Yuval Ishai, Antonio Marcedone and Muthuramakrishnan Venkitasubramaniam
Outsourcing Private Machine Learning via Lightweight Secure Arithmetic Computation [arxiv]

In several settings of practical interest, two parties seek to collaboratively perform inference on their private data using a public machine learning model. For instance, several hospitals might wish to share patient medical records for enhanced diagnostics and disease prediction, but may not be able to share data in the clear because of privacy concerns. In this work, we propose an actively secure protocol for outsourcing secure and private machine learning computations. Recent works on the problem have mainly focused on passively secure protocols, whose security holds against passive (``semi-honest'') parties but may completely break down in the presence of active (``malicious'') parties who can deviate from the protocol. Secure NN based classification algorithms can be an seen as an instantiation of an arithmetic computation over integers. We showcase the efficiency of our protocol by applying it to real-world instances of arithmeticized neural network computations, including a network trained to perform collaborative disease prediction.

Frederik Harder, Jonas Köhler, Max Welling and Mijung Park
DP-MAC: The Differentially Private Method of Auxiliary Coordinates for Deep Learning (contributed talk) [PDF] [APPENDIX]

Developing a differentially private deep learning algorithm is challenging, due to the difficulty in analyzing the sensitivity of objective functions that are typically used to train deep neural networks. Many existing methods resort to the stochastic gradient descent algorithm and apply a pre-defined sensitivity to the gradients for privatizing weights. However, their slow convergence typically yields a high cumulative privacy loss. Here, we take a different route by employing the method of auxiliary coordinates, which allows us to independently update the weights per layer by optimizing a per-layer objective function. This objective function can be well approximated by a low-order Taylor's expansion, in which sensitivity analysis becomes tractable. We perturb the coefficients of the expansion for privacy, which we optimize using more advanced optimization routines than SGD for faster convergence. We empirically show that our algorithm provides a decent trained model quality under a modest privacy budget.

Da Yu, Huishuai Zhang and Wei Chen
Improving the Gradient Perturbation Approach for Differentially Private Optimization [PDF]

We investigate the gradient perturbation approach for differentially private (DP) optimization and improve its performance by utilizing the optimization properties of gradient descent. One property is that historical gradient are often used as a momentum to facilitate the convergence. However, momentum gradient descent with usual coefficient does not perform well in the DP case. Instead, we specifically choose a coefficient based on our analysis. Another property is that the gradient tends to zero as optimization algorithm converges. Inspired by this, we intentionally decrease the gradient norm clip bound, which corresponds to decrease the sensitivity in the differential privacy computation. This allows us to run more training steps while keeping the same privacy guarantee. Our approaches are applicable for both convex and non-convex optimizations with differential privacy constraint. We demonstrate that our approaches can significantly improve the training/test performance under a privacy budget via various experiments.

Privacy Preserving Machine Learning

Scope

Call For Papers & Important Dates

Submission Instructions

Invited Speakers

Schedule

Accepted Papers

Links to pdfs as well as abstracts will be added soon.

Travel Grants

Organization

Workshop organizers

Program Committee

Sponsors