Optimized Tradeoffs for Private Prediction with Majority Ensembling Article Swipe

PDF

Shuli Jiang , Qiuyi , Ying Zhang , Gauri Joshi ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2411.17965

We study a classical problem in private prediction, the problem of computing an $(mε, δ)$-differentially private majority of $K$ $(ε, Δ)$-differentially private algorithms for $1 \leq m \leq K$ and $1 > δ\geq Δ\geq 0$. Standard methods such as subsampling or randomized response are widely used, but do they provide optimal privacy-utility tradeoffs? To answer this, we introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. It is parameterized by a data-dependent noise function $γ$, and enables efficient utility optimization over the class of all private algorithms, encompassing those standard methods. We show that maximizing the utility of an $(mε, δ)$-private majority algorithm can be computed tractably through an optimization problem for any $m \leq K$ by a novel structural result that reduces the infinitely many privacy constraints into a polynomial set. In some settings, we show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility. Lastly, we demonstrate the strong empirical effectiveness of our first-of-its-kind privacy-constrained utility optimization for ensembling labels for private prediction from private teachers in image classification. Notably, our DaRRM framework with an optimized $γ$ exhibits substantial utility gains when compared against several baselines.

Related Topics

Computer Science

Concepts

Computer science

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2411.17965
PDF: https://arxiv.org/pdf/2411.17965
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4404990226

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4404990226

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2411.17965

Digital Object Identifier
Title: Optimized Tradeoffs for Private Prediction with Majority Ensembling

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-11-27

Full publication date if available
Authors: Shuli Jiang, Qiuyi, Ying Zhang, Gauri Joshi

List of authors in order
Landing page: https://arxiv.org/abs/2411.17965

Publisher landing page
PDF URL: https://arxiv.org/pdf/2411.17965

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2411.17965

Direct OA link when available
Concepts: Computer science

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4404990226
doi	https://doi.org/10.48550/arxiv.2411.17965
ids.doi	https://doi.org/10.48550/arxiv.2411.17965
ids.openalex	https://openalex.org/W4404990226
fwci
type	preprint
title	Optimized Tradeoffs for Private Prediction with Majority Ensembling
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	0.9879000186920166
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/T11182
topics[1].field.id	https://openalex.org/fields/18
topics[1].field.display_name	Decision Sciences
topics[1].score	0.9585000276565552
topics[1].domain.id	https://openalex.org/domains/2
topics[1].domain.display_name	Social Sciences
topics[1].subfield.id	https://openalex.org/subfields/1803
topics[1].subfield.display_name	Management Science and Operations Research
topics[1].display_name	Auction Theory and Applications
topics[2].id	https://openalex.org/T10237
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9383000135421753
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	Cryptography and Data Security
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.4060790538787842
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.4060790538787842
keywords[0].display_name	Computer science
language	en
locations[0].id	pmh:oai:arXiv.org:2411.17965
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/2411.17965
locations[0].version	submittedVersion
locations[0].raw_type	text
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/2411.17965
locations[1].id	doi:10.48550/arxiv.2411.17965
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
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
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.2411.17965
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5013215630
authorships[0].author.orcid
authorships[0].author.display_name	Shuli Jiang
authorships[0].author_position	first
authorships[0].raw_author_name	Jiang, Shuli
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5025538636
authorships[1].author.orcid
authorships[1].author.display_name	Qiuyi
authorships[1].author_position	middle
authorships[1].raw_author_name	Qiuyi
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5108046728
authorships[2].author.orcid	https://orcid.org/0000-0002-2451-5354
authorships[2].author.display_name	Ying Zhang
authorships[2].author_position	middle
authorships[2].raw_author_name	Zhang
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5067441201
authorships[3].author.orcid	https://orcid.org/0000-0002-6372-9697
authorships[3].author.display_name	Gauri Joshi
authorships[3].author_position	last
authorships[3].raw_author_name	Joshi, Gauri
authorships[3].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/2411.17965
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Optimized Tradeoffs for Private Prediction with Majority Ensembling
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	0.9879000186920166
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/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W4391913857, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W4396696052
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2411.17965
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/2411.17965
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
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/2411.17965
primary_location.id	pmh:oai:arXiv.org:2411.17965
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/2411.17965
primary_location.version	submittedVersion
primary_location.raw_type	text
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/2411.17965
publication_date	2024-11-27
publication_year	2024
referenced_works_count	0
abstract_inverted_index.2	147
abstract_inverted_index.a	2, 69, 116, 128, 140, 144
abstract_inverted_index.m	26
abstract_inverted_index.$1	24, 30
abstract_inverted_index.$m	112
abstract_inverted_index.In	131
abstract_inverted_index.It	65
abstract_inverted_index.K$	28, 114
abstract_inverted_index.To	53
abstract_inverted_index.We	0, 90
abstract_inverted_index.an	12, 97, 107, 184
abstract_inverted_index.as	38
abstract_inverted_index.be	103
abstract_inverted_index.by	68, 115
abstract_inverted_index.do	47
abstract_inverted_index.in	5, 176
abstract_inverted_index.is	66
abstract_inverted_index.of	10, 17, 82, 96, 143, 146, 161
abstract_inverted_index.or	40
abstract_inverted_index.we	56, 134, 155
abstract_inverted_index.$K$	18
abstract_inverted_index.0$.	34
abstract_inverted_index.all	83
abstract_inverted_index.and	29, 74
abstract_inverted_index.any	111
abstract_inverted_index.are	43
abstract_inverted_index.but	46
abstract_inverted_index.can	102
abstract_inverted_index.for	23, 110, 167, 170
abstract_inverted_index.our	162, 180
abstract_inverted_index.the	8, 58, 80, 94, 122, 157
abstract_inverted_index.$γ$	186
abstract_inverted_index.>	31
abstract_inverted_index.\leq	25, 27, 113
abstract_inverted_index.from	173
abstract_inverted_index.gain	142
abstract_inverted_index.into	127
abstract_inverted_index.many	124
abstract_inverted_index.over	79, 148
abstract_inverted_index.set.	130
abstract_inverted_index.show	91, 135
abstract_inverted_index.some	132
abstract_inverted_index.such	37
abstract_inverted_index.that	92, 120, 136
abstract_inverted_index.they	48
abstract_inverted_index.when	191
abstract_inverted_index.with	151, 183
abstract_inverted_index.$(ε,	19
abstract_inverted_index.$γ$,	73
abstract_inverted_index.DaRRM	137, 181
abstract_inverted_index.class	81
abstract_inverted_index.fixed	152
abstract_inverted_index.gains	190
abstract_inverted_index.image	177
abstract_inverted_index.noise	71
abstract_inverted_index.novel	117
abstract_inverted_index.study	1
abstract_inverted_index.this,	55
abstract_inverted_index.those	87
abstract_inverted_index.used,	45
abstract_inverted_index.$(mε,	13, 98
abstract_inverted_index.answer	54
abstract_inverted_index.common	149
abstract_inverted_index.enjoys	139
abstract_inverted_index.factor	145
abstract_inverted_index.labels	169
abstract_inverted_index.result	119
abstract_inverted_index.strong	158
abstract_inverted_index.widely	44
abstract_inverted_index.Δ\geq	33
abstract_inverted_index.δ\geq	32
abstract_inverted_index.(DaRRM)	63
abstract_inverted_index.Lastly,	154
abstract_inverted_index.against	193
abstract_inverted_index.enables	75
abstract_inverted_index.methods	36
abstract_inverted_index.optimal	50
abstract_inverted_index.privacy	125, 141
abstract_inverted_index.private	6, 15, 21, 84, 171, 174
abstract_inverted_index.problem	4, 9, 109
abstract_inverted_index.provide	49
abstract_inverted_index.reduces	121
abstract_inverted_index.several	194
abstract_inverted_index.through	106
abstract_inverted_index.utility	77, 95, 165, 189
abstract_inverted_index.Majority	62
abstract_inverted_index.Notably,	179
abstract_inverted_index.Response	61
abstract_inverted_index.Standard	35
abstract_inverted_index.compared	192
abstract_inverted_index.computed	104
abstract_inverted_index.exhibits	187
abstract_inverted_index.function	72
abstract_inverted_index.majority	16, 100
abstract_inverted_index.methods.	89
abstract_inverted_index.provably	138
abstract_inverted_index.response	42
abstract_inverted_index.standard	88
abstract_inverted_index.teachers	175
abstract_inverted_index.utility.	153
abstract_inverted_index.algorithm	101
abstract_inverted_index.classical	3
abstract_inverted_index.computing	11
abstract_inverted_index.efficient	76
abstract_inverted_index.empirical	159
abstract_inverted_index.framework	182
abstract_inverted_index.introduce	57
abstract_inverted_index.optimized	185
abstract_inverted_index.settings,	133
abstract_inverted_index.tractably	105
abstract_inverted_index.Randomized	60
abstract_inverted_index.algorithm.	64
abstract_inverted_index.algorithms	22
abstract_inverted_index.baselines,	150
abstract_inverted_index.baselines.	195
abstract_inverted_index.ensembling	168
abstract_inverted_index.infinitely	123
abstract_inverted_index.maximizing	93
abstract_inverted_index.polynomial	129
abstract_inverted_index.prediction	172
abstract_inverted_index.randomized	41
abstract_inverted_index.structural	118
abstract_inverted_index.tradeoffs?	52
abstract_inverted_index.algorithms,	85
abstract_inverted_index.constraints	126
abstract_inverted_index.demonstrate	156
abstract_inverted_index.prediction,	7
abstract_inverted_index.subsampling	39
abstract_inverted_index.substantial	188
abstract_inverted_index.encompassing	86
abstract_inverted_index.optimization	78, 108, 166
abstract_inverted_index.δ)$-private	99
abstract_inverted_index.effectiveness	160
abstract_inverted_index.parameterized	67
abstract_inverted_index.Data-dependent	59
abstract_inverted_index.data-dependent	70
abstract_inverted_index.classification.	178
abstract_inverted_index.privacy-utility	51
abstract_inverted_index.first-of-its-kind	163
abstract_inverted_index.privacy-constrained	164
abstract_inverted_index.Δ)$-differentially	20
abstract_inverted_index.δ)$-differentially	14
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile