The Cost of Shuffling in Private Gradient Based Optimization Article Swipe

PDF

Shuli Jiang , Pranay Sharma , Zhiwei Steven Wu , Gauri Joshi ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2502.03652

We consider the problem of differentially private (DP) convex empirical risk minimization (ERM). While the standard DP-SGD algorithm is theoretically well-established, practical implementations often rely on shuffled gradient methods that traverse the training data sequentially rather than sampling with replacement in each iteration. Despite their widespread use, the theoretical privacy-accuracy trade-offs of private shuffled gradient methods (\textit{DP-ShuffleG}) remain poorly understood, leading to a gap between theory and practice. In this work, we leverage privacy amplification by iteration (PABI) and a novel application of Stein's lemma to provide the first empirical excess risk bound of \textit{DP-ShuffleG}. Our result shows that data shuffling results in worse empirical excess risk for \textit{DP-ShuffleG} compared to DP-SGD. To address this limitation, we propose \textit{Interleaved-ShuffleG}, a hybrid approach that integrates public data samples in private optimization. By alternating optimization steps that use private and public samples, \textit{Interleaved-ShuffleG} effectively reduces empirical excess risk. Our analysis introduces a new optimization framework with surrogate objectives, adaptive noise injection, and a dissimilarity metric, which can be of independent interest. Our experiments on diverse datasets and tasks demonstrate the superiority of \textit{Interleaved-ShuffleG} over several baselines.

Related Topics

Concepts

Shuffling Mathematical optimization Computer science Business Mathematics Statistics

Metadata

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

All OpenAlex metadata

Raw OpenAlex JSON

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

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

Digital Object Identifier
Title: The Cost of Shuffling in Private Gradient Based Optimization

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-02-05

Full publication date if available
Authors: Shuli Jiang, Pranay Sharma, Zhiwei Steven Wu, Gauri Joshi

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

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

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/2502.03652

Direct OA link when available
Concepts: Shuffling, Mathematical optimization, Computer science, Business, Mathematics, Statistics

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/W4407244624
doi	https://doi.org/10.48550/arxiv.2502.03652
ids.doi	https://doi.org/10.48550/arxiv.2502.03652
ids.openalex	https://openalex.org/W4407244624
fwci
type	preprint
title	The Cost of Shuffling in Private Gradient Based Optimization
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11612
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9549999833106995
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	Stochastic Gradient Optimization Techniques
topics[1].id	https://openalex.org/T10963
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.902999997138977
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2612
topics[1].subfield.display_name	Numerical Analysis
topics[1].display_name	Advanced Optimization Algorithms Research
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C167927819
concepts[0].level	2
concepts[0].score	0.8955973386764526
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1930567
concepts[0].display_name	Shuffling
concepts[1].id	https://openalex.org/C126255220
concepts[1].level	1
concepts[1].score	0.4314211308956146
concepts[1].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[1].display_name	Mathematical optimization
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.3817407488822937
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C144133560
concepts[3].level	0
concepts[3].score	0.3296999931335449
concepts[3].wikidata	https://www.wikidata.org/wiki/Q4830453
concepts[3].display_name	Business
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.29472815990448
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C105795698
concepts[5].level	1
concepts[5].score	0.14523085951805115
concepts[5].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[5].display_name	Statistics
keywords[0].id	https://openalex.org/keywords/shuffling
keywords[0].score	0.8955973386764526
keywords[0].display_name	Shuffling
keywords[1].id	https://openalex.org/keywords/mathematical-optimization
keywords[1].score	0.4314211308956146
keywords[1].display_name	Mathematical optimization
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.3817407488822937
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/business
keywords[3].score	0.3296999931335449
keywords[3].display_name	Business
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.29472815990448
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/statistics
keywords[5].score	0.14523085951805115
keywords[5].display_name	Statistics
language	en
locations[0].id	pmh:oai:arXiv.org:2502.03652
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/2502.03652
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/2502.03652
locations[1].id	doi:10.48550/arxiv.2502.03652
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.2502.03652
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/A5028196076
authorships[1].author.orcid	https://orcid.org/0009-0007-8027-7913
authorships[1].author.display_name	Pranay Sharma
authorships[1].author_position	middle
authorships[1].raw_author_name	Sharma, Pranay
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5001070941
authorships[2].author.orcid	https://orcid.org/0000-0002-8125-8227
authorships[2].author.display_name	Zhiwei Steven Wu
authorships[2].author_position	middle
authorships[2].raw_author_name	Wu, Zhiwei Steven
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/2502.03652
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	The Cost of Shuffling in Private Gradient Based Optimization
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11612
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9549999833106995
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	Stochastic Gradient Optimization Techniques
related_works	https://openalex.org/W4391375266, https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4213239787, https://openalex.org/W2045745654, https://openalex.org/W2114337652, https://openalex.org/W4377131110, https://openalex.org/W4388857216, https://openalex.org/W4294559962, https://openalex.org/W2046590706
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2502.03652
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/2502.03652
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/2502.03652
primary_location.id	pmh:oai:arXiv.org:2502.03652
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/2502.03652
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/2502.03652
publication_date	2025-02-05
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	62, 79, 119, 149, 160
abstract_inverted_index.By	130
abstract_inverted_index.In	68
abstract_inverted_index.To	112
abstract_inverted_index.We	0
abstract_inverted_index.be	165
abstract_inverted_index.by	75
abstract_inverted_index.in	40, 102, 127
abstract_inverted_index.is	18
abstract_inverted_index.of	4, 51, 82, 93, 166, 179
abstract_inverted_index.on	25, 171
abstract_inverted_index.to	61, 85, 110
abstract_inverted_index.we	71, 116
abstract_inverted_index.Our	95, 146, 169
abstract_inverted_index.and	66, 78, 137, 159, 174
abstract_inverted_index.can	164
abstract_inverted_index.for	107
abstract_inverted_index.gap	63
abstract_inverted_index.new	150
abstract_inverted_index.the	2, 14, 31, 47, 87, 177
abstract_inverted_index.use	135
abstract_inverted_index.(DP)	7
abstract_inverted_index.data	33, 99, 125
abstract_inverted_index.each	41
abstract_inverted_index.over	181
abstract_inverted_index.rely	24
abstract_inverted_index.risk	10, 91, 106
abstract_inverted_index.than	36
abstract_inverted_index.that	29, 98, 122, 134
abstract_inverted_index.this	69, 114
abstract_inverted_index.use,	46
abstract_inverted_index.with	38, 153
abstract_inverted_index.While	13
abstract_inverted_index.bound	92
abstract_inverted_index.first	88
abstract_inverted_index.lemma	84
abstract_inverted_index.noise	157
abstract_inverted_index.novel	80
abstract_inverted_index.often	23
abstract_inverted_index.risk.	145
abstract_inverted_index.shows	97
abstract_inverted_index.steps	133
abstract_inverted_index.tasks	175
abstract_inverted_index.their	44
abstract_inverted_index.which	163
abstract_inverted_index.work,	70
abstract_inverted_index.worse	103
abstract_inverted_index.(ERM).	12
abstract_inverted_index.(PABI)	77
abstract_inverted_index.DP-SGD	16
abstract_inverted_index.convex	8
abstract_inverted_index.excess	90, 105, 144
abstract_inverted_index.hybrid	120
abstract_inverted_index.poorly	58
abstract_inverted_index.public	124, 138
abstract_inverted_index.rather	35
abstract_inverted_index.remain	57
abstract_inverted_index.result	96
abstract_inverted_index.theory	65
abstract_inverted_index.DP-SGD.	111
abstract_inverted_index.Despite	43
abstract_inverted_index.Stein's	83
abstract_inverted_index.address	113
abstract_inverted_index.between	64
abstract_inverted_index.diverse	172
abstract_inverted_index.leading	60
abstract_inverted_index.methods	28, 55
abstract_inverted_index.metric,	162
abstract_inverted_index.privacy	73
abstract_inverted_index.private	6, 52, 128, 136
abstract_inverted_index.problem	3
abstract_inverted_index.propose	117
abstract_inverted_index.provide	86
abstract_inverted_index.reduces	142
abstract_inverted_index.results	101
abstract_inverted_index.samples	126
abstract_inverted_index.several	182
abstract_inverted_index.adaptive	156
abstract_inverted_index.analysis	147
abstract_inverted_index.approach	121
abstract_inverted_index.compared	109
abstract_inverted_index.consider	1
abstract_inverted_index.datasets	173
abstract_inverted_index.gradient	27, 54
abstract_inverted_index.leverage	72
abstract_inverted_index.samples,	139
abstract_inverted_index.sampling	37
abstract_inverted_index.shuffled	26, 53
abstract_inverted_index.standard	15
abstract_inverted_index.training	32
abstract_inverted_index.traverse	30
abstract_inverted_index.algorithm	17
abstract_inverted_index.empirical	9, 89, 104, 143
abstract_inverted_index.framework	152
abstract_inverted_index.interest.	168
abstract_inverted_index.iteration	76
abstract_inverted_index.practical	21
abstract_inverted_index.practice.	67
abstract_inverted_index.shuffling	100
abstract_inverted_index.surrogate	154
abstract_inverted_index.baselines.	183
abstract_inverted_index.injection,	158
abstract_inverted_index.integrates	123
abstract_inverted_index.introduces	148
abstract_inverted_index.iteration.	42
abstract_inverted_index.trade-offs	50
abstract_inverted_index.widespread	45
abstract_inverted_index.alternating	131
abstract_inverted_index.application	81
abstract_inverted_index.demonstrate	176
abstract_inverted_index.effectively	141
abstract_inverted_index.experiments	170
abstract_inverted_index.independent	167
abstract_inverted_index.limitation,	115
abstract_inverted_index.objectives,	155
abstract_inverted_index.replacement	39
abstract_inverted_index.superiority	178
abstract_inverted_index.theoretical	48
abstract_inverted_index.understood,	59
abstract_inverted_index.minimization	11
abstract_inverted_index.optimization	132, 151
abstract_inverted_index.sequentially	34
abstract_inverted_index.amplification	74
abstract_inverted_index.dissimilarity	161
abstract_inverted_index.optimization.	129
abstract_inverted_index.theoretically	19
abstract_inverted_index.differentially	5
abstract_inverted_index.implementations	22
abstract_inverted_index.privacy-accuracy	49
abstract_inverted_index.well-established,	20
abstract_inverted_index.\textit{DP-ShuffleG}	108
abstract_inverted_index.\textit{DP-ShuffleG}.	94
abstract_inverted_index.(\textit{DP-ShuffleG})	56
abstract_inverted_index.\textit{Interleaved-ShuffleG}	140, 180
abstract_inverted_index.\textit{Interleaved-ShuffleG},	118
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile