Infinitely Divisible Noise in the Low Privacy Regime

Rasmus Pagh; Nina Mesing Stausholm

Infinitely Divisible Noise in the Low Privacy Regime

Rasmus Pagh, Nina Mesing Stausholm

Algorithms and Complexity

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

1 Citationer (Scopus)

8 Downloads (Pure)

Abstract

Federated learning, in which training data is distributed among users and never shared, has emerged as a popular approach to privacy-preserving machine learning. Cryptographic techniques such as secure aggregation are used to aggregate contributions, like a model update, from all users. A robust technique for making such aggregates differentially private is to exploit \emph{infinite divisibility} of the Laplace distribution, namely, that a Laplace distribution can be expressed as a sum of i.i.d. noise shares from a Gamma distribution, one share added by each user. However, Laplace noise is known to have suboptimal error in the low privacy regime for ε
-differential privacy, where ε>1
is a large constant. In this paper we present the first infinitely divisible noise distribution for real-valued data that achieves ε
-differential privacy and has expected error that decreases exponentially with ε
.

Originalsprog	Engelsk
Titel	Proceedings of The 33rd International Conference on Algorithmic Learning Theory
Forlag	PMLR
Publikationsdato	2022
Sider	881-909
Status	Udgivet - 2022
Begivenhed	33rd International Conference on Algorithmic Learning Theory (ALT 2022) - Paris, Frankrig Varighed: 29 mar. 2022 → 1 apr. 2022

Konference

Konference	33rd International Conference on Algorithmic Learning Theory (ALT 2022)
Land/Område	Frankrig
By	Paris
Periode	29/03/2022 → 01/04/2022

Navn	Proceedings of Machine Learning Research
Vol/bind	167
ISSN	2640-3498

Adgang til dokumentet

FulltextForlagets udgivne version, 467 KBLicens: Andet

https://proceedings.mlr.press/v167/pagh22a.htmlLicens: Andet

Citationsformater

Pagh, R & Stausholm, NM 2022, Infinitely Divisible Noise in the Low Privacy Regime. i Proceedings of The 33rd International Conference on Algorithmic Learning Theory. PMLR, Proceedings of Machine Learning Research, bind 167, s. 881-909, 33rd International Conference on Algorithmic Learning Theory (ALT 2022), Paris, Frankrig, 29/03/2022. <https://proceedings.mlr.press/v167/pagh22a.html>

@inproceedings{89255e5b1d9a43bf9d1803f0553a5853,

title = "Infinitely Divisible Noise in the Low Privacy Regime",

abstract = "Federated learning, in which training data is distributed among users and never shared, has emerged as a popular approach to privacy-preserving machine learning. Cryptographic techniques such as secure aggregation are used to aggregate contributions, like a model update, from all users. A robust technique for making such aggregates differentially private is to exploit \emph{infinite divisibility} of the Laplace distribution, namely, that a Laplace distribution can be expressed as a sum of i.i.d. noise shares from a Gamma distribution, one share added by each user. However, Laplace noise is known to have suboptimal error in the low privacy regime for ε-differential privacy, where ε>1 is a large constant. In this paper we present the first infinitely divisible noise distribution for real-valued data that achieves ε-differential privacy and has expected error that decreases exponentially with ε.",

author = "Rasmus Pagh and Stausholm, {Nina Mesing}",

year = "2022",

language = "English",

series = "Proceedings of Machine Learning Research",

publisher = "PMLR",

pages = "881--909",

booktitle = "Proceedings of The 33rd International Conference on Algorithmic Learning Theory",

note = "33rd International Conference on Algorithmic Learning Theory (ALT 2022) ; Conference date: 29-03-2022 Through 01-04-2022",

}

TY - GEN

T1 - Infinitely Divisible Noise in the Low Privacy Regime

AU - Pagh, Rasmus

AU - Stausholm, Nina Mesing

PY - 2022

Y1 - 2022

N2 - Federated learning, in which training data is distributed among users and never shared, has emerged as a popular approach to privacy-preserving machine learning. Cryptographic techniques such as secure aggregation are used to aggregate contributions, like a model update, from all users. A robust technique for making such aggregates differentially private is to exploit \emph{infinite divisibility} of the Laplace distribution, namely, that a Laplace distribution can be expressed as a sum of i.i.d. noise shares from a Gamma distribution, one share added by each user. However, Laplace noise is known to have suboptimal error in the low privacy regime for ε-differential privacy, where ε>1 is a large constant. In this paper we present the first infinitely divisible noise distribution for real-valued data that achieves ε-differential privacy and has expected error that decreases exponentially with ε.

AB - Federated learning, in which training data is distributed among users and never shared, has emerged as a popular approach to privacy-preserving machine learning. Cryptographic techniques such as secure aggregation are used to aggregate contributions, like a model update, from all users. A robust technique for making such aggregates differentially private is to exploit \emph{infinite divisibility} of the Laplace distribution, namely, that a Laplace distribution can be expressed as a sum of i.i.d. noise shares from a Gamma distribution, one share added by each user. However, Laplace noise is known to have suboptimal error in the low privacy regime for ε-differential privacy, where ε>1 is a large constant. In this paper we present the first infinitely divisible noise distribution for real-valued data that achieves ε-differential privacy and has expected error that decreases exponentially with ε.

M3 - Article in proceedings

T3 - Proceedings of Machine Learning Research

SP - 881

EP - 909

BT - Proceedings of The 33rd International Conference on Algorithmic Learning Theory

PB - PMLR

T2 - 33rd International Conference on Algorithmic Learning Theory (ALT 2022)

Y2 - 29 March 2022 through 1 April 2022

ER -