Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning Article Swipe
Antonious M. Girgis
,
Deepesh Data
,
Suhas Diggavi
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2107.08763
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2107.08763
We study privacy in a distributed learning framework, where clients collaboratively build a learning model iteratively through interactions with a server from whom we need privacy. Motivated by stochastic optimization and the federated learning (FL) paradigm, we focus on the case where a small fraction of data samples are randomly sub-sampled in each round to participate in the learning process, which also enables privacy amplification. To obtain even stronger local privacy guarantees, we study this in the shuffle privacy model, where each client randomizes its response using a local differentially private (LDP) mechanism and the server only receives a random permutation (shuffle) of the clients' responses without their association to each client. The principal result of this paper is a privacy-optimization performance trade-off for discrete randomization mechanisms in this sub-sampled shuffle privacy model. This is enabled through a new theoretical technique to analyze the Renyi Differential Privacy (RDP) of the sub-sampled shuffle model. We numerically demonstrate that, for important regimes, with composition our bound yields significant improvement in privacy guarantee over the state-of-the-art approximate Differential Privacy (DP) guarantee (with strong composition) for sub-sampled shuffled models. We also demonstrate numerically significant improvement in privacy-learning performance operating point using real data sets.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2107.08763
- https://arxiv.org/pdf/2107.08763
- OA Status
- green
- Cited By
- 5
- References
- 38
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3184209750
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3184209750Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2107.08763Digital Object Identifier
- Title
-
Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed LearningWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-07-19Full publication date if available
- Authors
-
Antonious M. Girgis, Deepesh Data, Suhas DiggaviList of authors in order
- Landing page
-
https://arxiv.org/abs/2107.08763Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2107.08763Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2107.08763Direct OA link when available
- Concepts
-
Differential privacy, Computer science, Differential (mechanical device), Internet privacy, Data mining, Engineering, Aerospace engineeringTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
5Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 1, 2023: 3, 2022: 1Per-year citation counts (last 5 years)
- References (count)
-
38Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3184209750 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2107.08763 |
| ids.doi | https://doi.org/10.48550/arxiv.2107.08763 |
| ids.mag | 3184209750 |
| ids.openalex | https://openalex.org/W3184209750 |
| fwci | |
| type | preprint |
| title | Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10764 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 1.0 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Privacy-Preserving Technologies in Data |
| topics[1].id | https://openalex.org/T10237 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9991000294685364 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Cryptography and Data Security |
| topics[2].id | https://openalex.org/T11612 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.996999979019165 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Stochastic Gradient Optimization Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C23130292 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7968897223472595 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q5275358 |
| concepts[0].display_name | Differential privacy |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5730506181716919 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C93226319 |
| concepts[2].level | 2 |
| concepts[2].score | 0.4852714240550995 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q193137 |
| concepts[2].display_name | Differential (mechanical device) |
| concepts[3].id | https://openalex.org/C108827166 |
| concepts[3].level | 1 |
| concepts[3].score | 0.33460432291030884 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q175975 |
| concepts[3].display_name | Internet privacy |
| concepts[4].id | https://openalex.org/C124101348 |
| concepts[4].level | 1 |
| concepts[4].score | 0.17960655689239502 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q172491 |
| concepts[4].display_name | Data mining |
| concepts[5].id | https://openalex.org/C127413603 |
| concepts[5].level | 0 |
| concepts[5].score | 0.0893126130104065 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[5].display_name | Engineering |
| concepts[6].id | https://openalex.org/C146978453 |
| concepts[6].level | 1 |
| concepts[6].score | 0.0 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q3798668 |
| concepts[6].display_name | Aerospace engineering |
| keywords[0].id | https://openalex.org/keywords/differential-privacy |
| keywords[0].score | 0.7968897223472595 |
| keywords[0].display_name | Differential privacy |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5730506181716919 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/differential |
| keywords[2].score | 0.4852714240550995 |
| keywords[2].display_name | Differential (mechanical device) |
| keywords[3].id | https://openalex.org/keywords/internet-privacy |
| keywords[3].score | 0.33460432291030884 |
| keywords[3].display_name | Internet privacy |
| keywords[4].id | https://openalex.org/keywords/data-mining |
| keywords[4].score | 0.17960655689239502 |
| keywords[4].display_name | Data mining |
| keywords[5].id | https://openalex.org/keywords/engineering |
| keywords[5].score | 0.0893126130104065 |
| keywords[5].display_name | Engineering |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2107.08763 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2107.08763 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2107.08763 |
| locations[1].id | doi:10.48550/arxiv.2107.08763 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | public-domain |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/public-domain |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2107.08763 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5057824853 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-9828-6534 |
| authorships[0].author.display_name | Antonious M. Girgis |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Antonious M. Girgis |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5023777978 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-3544-8414 |
| authorships[1].author.display_name | Deepesh Data |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Deepesh Data |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5083980887 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-7313-9861 |
| authorships[2].author.display_name | Suhas Diggavi |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Suhas Diggavi |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2107.08763 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2021-08-02T00:00:00 |
| display_name | Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10764 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 1.0 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Privacy-Preserving Technologies in Data |
| related_works | https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W3038283795, https://openalex.org/W2604501336, https://openalex.org/W2734500670, https://openalex.org/W2558166297, https://openalex.org/W2315671126, https://openalex.org/W798507144, https://openalex.org/W2964481303, https://openalex.org/W1751413323 |
| cited_by_count | 5 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2023 |
| counts_by_year[1].cited_by_count | 3 |
| counts_by_year[2].year | 2022 |
| counts_by_year[2].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2107.08763 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2107.08763 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2107.08763 |
| primary_location.id | pmh:oai:arXiv.org:2107.08763 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2107.08763 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2107.08763 |
| publication_date | 2021-07-19 |
| publication_year | 2021 |
| referenced_works | https://openalex.org/W3159560790, https://openalex.org/W3102407811, https://openalex.org/W2975431245, https://openalex.org/W2902964282, https://openalex.org/W3176917011, https://openalex.org/W2951475234, https://openalex.org/W3037538088, https://openalex.org/W2995022099, https://openalex.org/W1992926795, https://openalex.org/W2954257087, https://openalex.org/W2621140322, https://openalex.org/W2077723394, https://openalex.org/W2594311007, https://openalex.org/W1516903196, https://openalex.org/W2970055833, https://openalex.org/W2027595342, https://openalex.org/W3099185500, https://openalex.org/W3162164066, https://openalex.org/W1873763122, https://openalex.org/W2167372639, https://openalex.org/W2963612912, https://openalex.org/W2053801139, https://openalex.org/W2535838896, https://openalex.org/W2963559079, https://openalex.org/W2949275988, https://openalex.org/W2119874464, https://openalex.org/W2912213068, https://openalex.org/W3103312471, https://openalex.org/W3121148053, https://openalex.org/W3113714175, https://openalex.org/W2964074929, https://openalex.org/W2998982695, https://openalex.org/W2967889168, https://openalex.org/W2473418344, https://openalex.org/W2245160765, https://openalex.org/W2902114605, https://openalex.org/W2963189173, https://openalex.org/W114517082 |
| referenced_works_count | 38 |
| abstract_inverted_index.a | 4, 12, 19, 42, 87, 98, 119, 137 |
| abstract_inverted_index.To | 65 |
| abstract_inverted_index.We | 0, 153, 185 |
| abstract_inverted_index.by | 27 |
| abstract_inverted_index.in | 3, 51, 56, 75, 127, 167, 191 |
| abstract_inverted_index.is | 118, 134 |
| abstract_inverted_index.of | 45, 102, 115, 148 |
| abstract_inverted_index.on | 38 |
| abstract_inverted_index.to | 54, 109, 141 |
| abstract_inverted_index.we | 23, 36, 72 |
| abstract_inverted_index.The | 112 |
| abstract_inverted_index.and | 30, 93 |
| abstract_inverted_index.are | 48 |
| abstract_inverted_index.for | 123, 157, 181 |
| abstract_inverted_index.its | 84 |
| abstract_inverted_index.new | 138 |
| abstract_inverted_index.our | 162 |
| abstract_inverted_index.the | 31, 39, 57, 76, 94, 103, 143, 149, 171 |
| abstract_inverted_index.(DP) | 176 |
| abstract_inverted_index.(FL) | 34 |
| abstract_inverted_index.This | 133 |
| abstract_inverted_index.also | 61, 186 |
| abstract_inverted_index.case | 40 |
| abstract_inverted_index.data | 46, 198 |
| abstract_inverted_index.each | 52, 81, 110 |
| abstract_inverted_index.even | 67 |
| abstract_inverted_index.from | 21 |
| abstract_inverted_index.need | 24 |
| abstract_inverted_index.only | 96 |
| abstract_inverted_index.over | 170 |
| abstract_inverted_index.real | 197 |
| abstract_inverted_index.this | 74, 116, 128 |
| abstract_inverted_index.whom | 22 |
| abstract_inverted_index.with | 18, 160 |
| abstract_inverted_index.(LDP) | 91 |
| abstract_inverted_index.(RDP) | 147 |
| abstract_inverted_index.(with | 178 |
| abstract_inverted_index.Renyi | 144 |
| abstract_inverted_index.bound | 163 |
| abstract_inverted_index.build | 11 |
| abstract_inverted_index.focus | 37 |
| abstract_inverted_index.local | 69, 88 |
| abstract_inverted_index.model | 14 |
| abstract_inverted_index.paper | 117 |
| abstract_inverted_index.point | 195 |
| abstract_inverted_index.round | 53 |
| abstract_inverted_index.sets. | 199 |
| abstract_inverted_index.small | 43 |
| abstract_inverted_index.study | 1, 73 |
| abstract_inverted_index.that, | 156 |
| abstract_inverted_index.their | 107 |
| abstract_inverted_index.using | 86, 196 |
| abstract_inverted_index.where | 8, 41, 80 |
| abstract_inverted_index.which | 60 |
| abstract_inverted_index.client | 82 |
| abstract_inverted_index.model, | 79 |
| abstract_inverted_index.model. | 132, 152 |
| abstract_inverted_index.obtain | 66 |
| abstract_inverted_index.random | 99 |
| abstract_inverted_index.result | 114 |
| abstract_inverted_index.server | 20, 95 |
| abstract_inverted_index.strong | 179 |
| abstract_inverted_index.yields | 164 |
| abstract_inverted_index.Privacy | 146, 175 |
| abstract_inverted_index.analyze | 142 |
| abstract_inverted_index.client. | 111 |
| abstract_inverted_index.clients | 9 |
| abstract_inverted_index.enabled | 135 |
| abstract_inverted_index.enables | 62 |
| abstract_inverted_index.models. | 184 |
| abstract_inverted_index.privacy | 2, 63, 70, 78, 131, 168 |
| abstract_inverted_index.private | 90 |
| abstract_inverted_index.samples | 47 |
| abstract_inverted_index.shuffle | 77, 130, 151 |
| abstract_inverted_index.through | 16, 136 |
| abstract_inverted_index.without | 106 |
| abstract_inverted_index.clients' | 104 |
| abstract_inverted_index.discrete | 124 |
| abstract_inverted_index.fraction | 44 |
| abstract_inverted_index.learning | 6, 13, 33, 58 |
| abstract_inverted_index.privacy. | 25 |
| abstract_inverted_index.process, | 59 |
| abstract_inverted_index.randomly | 49 |
| abstract_inverted_index.receives | 97 |
| abstract_inverted_index.regimes, | 159 |
| abstract_inverted_index.response | 85 |
| abstract_inverted_index.shuffled | 183 |
| abstract_inverted_index.stronger | 68 |
| abstract_inverted_index.(shuffle) | 101 |
| abstract_inverted_index.Motivated | 26 |
| abstract_inverted_index.federated | 32 |
| abstract_inverted_index.guarantee | 169, 177 |
| abstract_inverted_index.important | 158 |
| abstract_inverted_index.mechanism | 92 |
| abstract_inverted_index.operating | 194 |
| abstract_inverted_index.paradigm, | 35 |
| abstract_inverted_index.principal | 113 |
| abstract_inverted_index.responses | 105 |
| abstract_inverted_index.technique | 140 |
| abstract_inverted_index.trade-off | 122 |
| abstract_inverted_index.framework, | 7 |
| abstract_inverted_index.mechanisms | 126 |
| abstract_inverted_index.randomizes | 83 |
| abstract_inverted_index.stochastic | 28 |
| abstract_inverted_index.approximate | 173 |
| abstract_inverted_index.association | 108 |
| abstract_inverted_index.composition | 161 |
| abstract_inverted_index.demonstrate | 155, 187 |
| abstract_inverted_index.distributed | 5 |
| abstract_inverted_index.guarantees, | 71 |
| abstract_inverted_index.improvement | 166, 190 |
| abstract_inverted_index.iteratively | 15 |
| abstract_inverted_index.numerically | 154, 188 |
| abstract_inverted_index.participate | 55 |
| abstract_inverted_index.performance | 121, 193 |
| abstract_inverted_index.permutation | 100 |
| abstract_inverted_index.significant | 165, 189 |
| abstract_inverted_index.sub-sampled | 50, 129, 150, 182 |
| abstract_inverted_index.theoretical | 139 |
| abstract_inverted_index.Differential | 145, 174 |
| abstract_inverted_index.composition) | 180 |
| abstract_inverted_index.interactions | 17 |
| abstract_inverted_index.optimization | 29 |
| abstract_inverted_index.randomization | 125 |
| abstract_inverted_index.amplification. | 64 |
| abstract_inverted_index.differentially | 89 |
| abstract_inverted_index.collaboratively | 10 |
| abstract_inverted_index.privacy-learning | 192 |
| abstract_inverted_index.state-of-the-art | 172 |
| abstract_inverted_index.privacy-optimization | 120 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |