---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22102'
abstract:
- lang: eng
text: 'Differential privacy (DP) has established itself as one of the standards
for ensuring privacy of individual data. However, reasoning about DP is a challenging
and error-prone task, hence methods for formal verification and refutation of
DP properties have received significant interest in recent years. In this work,
we present a novel method for automated formal refutation of є-DP. Our method
refutes є-DP by searching for a pair of inputs together with a non-negative function
over outputs whose expected value on these two inputs differs by a significant
amount. The two inputs and the non-negative function over outputs are computed
simultaneously, by utilizing upper expectation supermartingales and lower expectation
submartingales from probabilistic program analysis, which we leverage to introduce
a sound and complete proof rule for є-DP refutation. To the best of our knowledge,
our method is the first method for є-DP refutation to offer the following four
desirable features: (1) it is fully automated, (2) it is applicable to stochastic
mechanisms with sampling instructions from both discrete and continuous distributions,
(3) it provides soundness guarantees, and (4) it provides semi-completeness guarantees.
Our experiments show that our prototype tool SuperDP achieves superior performance
compared to the state of the art and manages to refute є-DP for a number of challenging
examples collected from the literature, including ones that were out of the reach
of prior methods.'
acknowledgement: "The authors would like to thank Petr Novotný for valuable discussions
that helped shape this work.\r\nThis research was supported by the Singapore Ministry
of Education (MOE) Academic Research\r\nFund (AcRF) Tier 1 grant (Proposal ID: 25-SIS-SMU-009),
Vienna Science and Technology Fund\r\n(WWTF), State of Lower Austria [Grant ID 10.47379/ICT25017],
ERC CoG 863818 (ForM-SMArt),\r\nand Austrian Science Fund (FWF) 10.55776/COE12."
article_number: '218'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ehsan
full_name: Kafshdar Goharshadi, Ehsan
id: 103b4fa0-896a-11ed-bdf8-87b697bef40d
last_name: Kafshdar Goharshadi
orcid: 0000-0002-8595-0587
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Chatterjee K, Goharshady E, Zikelic D. SuperDP: Differential privacy refutation
via supermartingales. Proceedings of the ACM on Programming Languages.
2026;10(PLDI). doi:10.1145/3808296'
apa: 'Chatterjee, K., Goharshady, E., & Zikelic, D. (2026). SuperDP: Differential
privacy refutation via supermartingales. Proceedings of the ACM on Programming
Languages. Association for Computing Machinery. https://doi.org/10.1145/3808296'
chicago: 'Chatterjee, Krishnendu, Ehsan Goharshady, and Dorde Zikelic. “SuperDP:
Differential Privacy Refutation via Supermartingales.” Proceedings of the ACM
on Programming Languages. Association for Computing Machinery, 2026. https://doi.org/10.1145/3808296.'
ieee: 'K. Chatterjee, E. Goharshady, and D. Zikelic, “SuperDP: Differential privacy
refutation via supermartingales,” Proceedings of the ACM on Programming Languages,
vol. 10, no. PLDI. Association for Computing Machinery, 2026.'
ista: 'Chatterjee K, Goharshady E, Zikelic D. 2026. SuperDP: Differential privacy
refutation via supermartingales. Proceedings of the ACM on Programming Languages.
10(PLDI), 218.'
mla: 'Chatterjee, Krishnendu, et al. “SuperDP: Differential Privacy Refutation via
Supermartingales.” Proceedings of the ACM on Programming Languages, vol.
10, no. PLDI, 218, Association for Computing Machinery, 2026, doi:10.1145/3808296.'
short: K. Chatterjee, E. Goharshady, D. Zikelic, Proceedings of the ACM on Programming
Languages 10 (2026).
corr_author: '1'
das_tickbox: '1'
dataavailabilitystatement: "The artifact supporting the findings of this study, which
includes the underlying datasets, software\r\ncode, and experiments, is publicly
available in Zenodo https://zenodo.org/records/19399862."
date_created: 2026-06-21T22:02:59Z
date_published: 2026-06-08T00:00:00Z
date_updated: 2026-06-24T06:39:37Z
day: '08'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1145/3808296
ec_funded: 1
external_id:
arxiv:
- '2603.26215'
file:
- access_level: open_access
checksum: 994bf21d6269dabccf1e1091e02962c5
content_type: application/pdf
creator: dernst
date_created: 2026-06-24T06:19:56Z
date_updated: 2026-06-24T06:19:56Z
file_id: '22135'
file_name: 2026_ProcACMProgrammingLanguages_Chatterjee.pdf
file_size: 858595
relation: main_file
success: 1
file_date_updated: 2026-06-24T06:19:56Z
has_accepted_license: '1'
intvolume: ' 10'
issue: PLDI
keyword:
- Static Program Analysis
- Differential Privacy
- Probabilistic Programming
- Martingales
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '22134'
relation: research_data
status: public
researchdata_availability: yes
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'SuperDP: Differential privacy refutation via supermartingales'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22146'
abstract:
- lang: eng
text: We study differentially private model training with stochastic gradient descent
under learning rate scheduling and correlated noise. Although correlated noise,
in particular via matrix factorizations, has been shown to improve accuracy, prior
theoretical work focused primarily on the prefix-sum workload. That workload assumes
a constant learning rate, whereas in practice learning rate schedules are widely
used to accelerate training and improve convergence. We close this gap by deriving
general upper and lower bounds for a broad class of learning rate schedules in
both single- and multi-epoch settings. Building on these results, we propose a
learning-rate-aware factorization that achieves improvements over prefix-sum factorizations
under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient
constructions suitable for practical deployment, and experiments on CIFAR-10 and
IMDB datasets confirm that schedule-aware factorizations improve accuracy in private
training.
acknowledgement: "We thank Rasmus Pagh, Christoph Lampert and Jalaj Upadhyay for valuable\r\ncomments
on an early draft. We thank Ryan Mckenna for a fruitful discussion on the experiment\r\ndesign.
We thank Antti Honkela for sharing insights on learning rate scheduling and DP.\r\nNikita
P. Kalinin: Funded in part by the Austrian Science Fund (FWF) [10.55776/COE12].\r\nJoel
Daniel Andersson: Funded by the European Union. Views and opinions expressed are
however\r\nthose of the author(s) only and do not necessarily reflect those of the
European Union or the European\r\nResearch Council Executive Agency. Neither the
European Union nor the granting authority can be\r\nheld responsible for them. This
project has received funding from the European Research Council\r\n(ERC) under the
European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo.
101019564). Additional funding by Providentia, a Data Science Distinguished Investigator
grant\r\nfrom Novo Nordisk Fonden, with additional support from VILLUM Investigator
grant 54451.\r\n"
alternative_title:
- LIPIcs
article_number: 2:1-2:21
article_processing_charge: No
arxiv: 1
author:
- first_name: Nikita
full_name: Kalinin, Nikita
id: 4b14526e-14d2-11ed-ba64-c14c9553d137
last_name: Kalinin
- first_name: Joel D
full_name: Andersson, Joel D
id: 4a893819-d954-11f0-89b1-e360bad9ccc5
last_name: Andersson
citation:
ama: 'Kalinin N, Andersson JD. Learning rate scheduling with matrix factorization
for private training. In: 7th Symposium on Foundations of Responsible Computing.
Vol 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.FORC.2026.2'
apa: 'Kalinin, N., & Andersson, J. D. (2026). Learning rate scheduling with
matrix factorization for private training. In 7th Symposium on Foundations
of Responsible Computing (Vol. 368). Cambridge, MA; United States: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FORC.2026.2'
chicago: Kalinin, Nikita, and Joel D Andersson. “Learning Rate Scheduling with Matrix
Factorization for Private Training.” In 7th Symposium on Foundations of Responsible
Computing, Vol. 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
https://doi.org/10.4230/LIPIcs.FORC.2026.2.
ieee: N. Kalinin and J. D. Andersson, “Learning rate scheduling with matrix factorization
for private training,” in 7th Symposium on Foundations of Responsible Computing,
Cambridge, MA; United States, 2026, vol. 368.
ista: 'Kalinin N, Andersson JD. 2026. Learning rate scheduling with matrix factorization
for private training. 7th Symposium on Foundations of Responsible Computing. FORC:
Symposium on Foundations of Responsible Computing, LIPIcs, vol. 368, 2:1-2:21.'
mla: Kalinin, Nikita, and Joel D. Andersson. “Learning Rate Scheduling with Matrix
Factorization for Private Training.” 7th Symposium on Foundations of Responsible
Computing, vol. 368, 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026, doi:10.4230/LIPIcs.FORC.2026.2.
short: N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible
Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-06-05
location: Cambridge, MA; United States
name: 'FORC: Symposium on Foundations of Responsible Computing'
start_date: 2026-06-03
corr_author: '1'
das_tickbox: '0'
date_created: 2026-06-28T22:01:34Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-06-29T06:56:34Z
day: '01'
ddc:
- '000'
department:
- _id: ChLa
- _id: GradSch
- _id: MoHe
doi: 10.4230/LIPIcs.FORC.2026.2
ec_funded: 1
external_id:
arxiv:
- '2511.17994'
file:
- access_level: open_access
checksum: c661f016d3861a1c1b590b87a744d087
content_type: application/pdf
creator: dernst
date_created: 2026-06-29T06:55:23Z
date_updated: 2026-06-29T06:55:23Z
file_id: '22149'
file_name: 2026_LIPIcsFORC_Kalinin.pdf
file_size: 1231914
relation: main_file
success: 1
file_date_updated: 2026-06-29T06:55:23Z
has_accepted_license: '1'
intvolume: ' 368'
keyword:
- differential privacy
- machine learning
- matrix factorization
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
publication: 7th Symposium on Foundations of Responsible Computing
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774192'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Learning rate scheduling with matrix factorization for private training
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 368
year: '2026'
...
---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22318'
abstract:
- lang: eng
text: "Many intended uses of differential privacy involve a continual mechanism
that is set up to run continuously\r\nover a long period of time, making more
statistical releases as either queries come in or the dataset is updated.\r\nIn
this paper, we give the first general treatment of privacy against adaptive adversaries
for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily
interleaved. It also models a very general notion\r\nof neighboring, that includes
both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems
for continual mechanisms, which ensure privacy even when an adversary can interleave
its queries\r\nand dataset updates to the different composed mechanisms. Previous
concurrent composition theorems for\r\ndifferential privacy were only for the
case when the dataset is static, with no adaptive updates. We also give\r\nthe
first interactive and continual generalizations of the “parallel composition theorem”
for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue
of the noninteractive parallel composition theorem\r\nholds if either there are
no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential
privacy, but it fails to hold for composing approximately differentially private
mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem
for this case. In addition, we prove concurrent\r\nfilter compositions theorems
for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend
these results to other measures of differential privacy, including Rényi DP and
\U0001D453 -DP.\r\nWe then formalize a set of general conditions on a continual
mechanism M that runs multiple continual submechanisms such that the privacy guarantees
of M follow directly using the above concurrent composition\r\ntheorems on the
sub-mechanisms, without further privacy loss. This enables us to give a simpler
and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger,
Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof
that shows that its privacy holds against adaptive adversaries.\r\nWe also provide
a framework that simplifies the analysis of local differential privacy when the
protocol\r\nincludes multi-round server-user interactions. Using this result,
we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala,
Henzinger, Li, Liu, Sricharan, and Zhu [5]."
acknowledgement: "1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from
the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting
Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported
by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi
were supported by the European Research Council (ERC)\r\nunder the European Union’s
Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564),
and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982,
and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic
copyright license to any author-accepted manuscript version arising from this submission.\r\nViews
and opinions expressed are however those of the author(s)\r\nonly and do not necessarily
reflect those of the European Union\r\nor the European Research Council Executive
Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible
for them."
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Salil
full_name: Vadhan, Salil
last_name: Vadhan
citation:
ama: Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially
private continual mechanisms. Proceedings of the ACM on Management of Data.
2026;4(2):1-26. doi:10.1145/3801895
apa: Henzinger, M., Safavi Hemami, R., & Vadhan, S. (2026). Concurrent composition
for differentially private continual mechanisms. Proceedings of the ACM on
Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801895
chicago: Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent
Composition for Differentially Private Continual Mechanisms.” Proceedings of
the ACM on Management of Data. Association for Computing Machinery, 2026.
https://doi.org/10.1145/3801895.
ieee: M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for
differentially private continual mechanisms,” Proceedings of the ACM on Management
of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026.
ista: Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially
private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2),
1–26.
mla: Henzinger, Monika, et al. “Concurrent Composition for Differentially Private
Continual Mechanisms.” Proceedings of the ACM on Management of Data, vol.
4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:10.1145/3801895.
short: M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management
of Data 4 (2026) 1–26.
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-13T14:59:14Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-07-16T09:14:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3801895
ec_funded: 1
external_id:
arxiv:
- '2411.03299'
file:
- access_level: open_access
checksum: c6c5e256d02b90682c0690c3bee94040
content_type: application/pdf
creator: dernst
date_created: 2026-07-16T09:09:53Z
date_updated: 2026-07-16T09:09:53Z
file_id: '22345'
file_name: 2026_ACMMgmtData_Henzinger.pdf
file_size: 655405
relation: main_file
success: 1
file_date_updated: 2026-07-16T09:09:53Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '2'
keyword:
- differential privacy
- concurrent composition
- continual release
- continual observation
- data streaming
- continual mechanisms
- concurrent parallel composition
- concurrent filter composition
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1-26
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
publication: Proceedings of the ACM on Management of Data
publication_identifier:
issn:
- 2836-6573
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Concurrent composition for differentially private continual mechanisms
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2026'
...