More Like this

1. Parameter-Free Locally Differentially Private Stochastic Subgradient Descent

   Jun, Kwang-Sung; Orabona, Francesco (January 2019, Workshop on Privacy in Machine Learning at NeurIPS'19)

   null (Ed.)

   We consider the problem of minimizing a convex risk with stochastic subgradients guaranteeing $$\epsilon$$-locally differentially private ($$\epsilon$$-LDP). While it has been shown that stochastic optimization is possible with $$\epsilon$$-LDP via the standard SGD, its convergence rate largely depends on the learning rate, which must be tuned via repeated runs. Further, tuning is detrimental to privacy loss since it significantly increases the number of gradient requests. In this work, we propose BANCO (Betting Algorithm for Noisy COins), the first $$\epsilon$$-LDP SGD algorithm that essentially matches the convergence rate of the tuned SGD without any learning rate parameter, reducing privacy loss and saving privacy budget. 

   more » « less
2. Differentially Private Federated Learning with Shuffling and Client Self-Sampling

   Girgis, Antonious M; Data, Deepesh; and Diggavi, Suhas. (July 2021, IEEE International Symposium on Information Theory (ISIT))

   This paper studies a distributed optimization problem in the federated learning (FL) framework under differential privacy constraints, whereby a set of clients having local samples are connected to an untrusted server, who wants to learn a global model while preserving the privacy of clients’ local datasets. We propose a new client sampling called self-sampling that reflects the random availability of clients in the learning process in FL. We analyze the differential privacy of the SGD with client self-sampling by composing amplification by sub-sampling along with amplification by shuffling. Furthermore, we analyze the convergence of the proposed SGD algorithm showing that we can get a reasonable learning performance while preserving the privacy of clients’ data even with client self-sampling. 

   more » « less
3. Renyi Differentially Private ERM for Smooth Objectives

   Chen, Chen; Lee, Jaewoo; Kifer, Daniel (January 2019, AISTATS)

   In this paper, we present a Renyi Differentially Private stochastic gradient descent (SGD) algorithm for convex empirical risk minimization. The algorithm uses output perturbation and leverages randomness inside SGD, which creates a “randomized sensitivity”, in order to reduce the amount of noise that is added. One of the benefits of output perturbation is that we can incorporate a periodic averaging step that serves to further reduce sensitivity while improving accuracy (reducing the well known oscillating behavior of SGD near the optimum). Renyi Differential Privacy can be used to provide (epsilon, delta)-differential privacy guarantees and hence provide a comparison with prior work. An empirical evaluation demonstrates that the proposed method outperforms prior methods on differentially private ERM. 

   more » « less
4. On the Rényi Differential Privacy of the Shuffle Model

   https://doi.org/10.1145/3460120.3484794  

   Girgis, Antonious M.; Data, Deepesh; Diggavi, Suhas; Suresh, Ananda Theertha; Kairouz, Peter (November 2021, ACM Symposium on Computer and Communication Security (CCS))

   The central question studied in this paper is Rényi Differential Privacy (RDP) guarantees for general discrete local randomizers in the shuffle privacy model. In the shuffle model, each of the 𝑛 clients randomizes its response using a local differentially private (LDP) mechanism and the untrusted server only receives a random permutation (shuffle) of the client responses without association to each client. The principal result in this paper is the first direct RDP bounds for general discrete local randomization in the shuffle pri- vacy model, and we develop new analysis techniques for deriving our results which could be of independent interest. In applications, such an RDP guarantee is most useful when we use it for composing several private interactions. We numerically demonstrate that, for important regimes, with composition our bound yields an improve- ment in privacy guarantee by a factor of 8× over the state-of-the-art approximate Differential Privacy (DP) guarantee (with standard composition) for shuffle models. Moreover, combining with Pois- son subsampling, our result leads to at least 10× improvement over subsampled approximate DP with standard composition. 

   more » « less
5. On the Convergence of Communication-Efficient Local SGD for Federated Learning

   Hongchang Gao, An Xu (February 2021, 35th AAAI Conference on Artificial Intelligence (AAAI 2021))

   Federated Learning (FL) has attracted increasing attention in recent years. A leading training algorithm in FL is local SGD, which updates the model parameter on each worker and averages model parameters across different workers only once in a while. Although it has fewer communication rounds than the classical parallel SGD, local SGD still has large communication overhead in each communication round for large machine learning models, such as deep neural networks. To address this issue, we propose a new communicationefficient distributed SGD method, which can significantly reduce the communication cost by the error-compensated double compression mechanism. Under the non-convex setting, our theoretical results show that our approach has better communication complexity than existing methods and enjoys the same linear speedup regarding the number of workers as the full-precision local SGD. Moreover, we propose a communication-efficient distributed SGD with momentum, which also has better communication complexity than existing methods and enjoys a linear speedup with respect to the number of workers. At last, extensive experiments are conducted to verify the performance of our proposed methods. 

   more » « less