---
OA_place: repository
_id: '21401'
abstract:
- lang: eng
text: "Runtime verification offers scalable solutions to improve the safety and
reliability of systems. However, systems that require verification or monitoring
by a third party to ensure compliance with a specification might contain sensitive
information, causing privacy concerns when usual runtime verification approaches
are used. Privacy is compromised if protected information about the system, or
sensitive data that is processed by the system, is revealed. In addition, revealing
the specification being monitored may undermine the essence of third-party verification.\r\n\r\nIn
this thesis, we propose a protocol for privacy-preserving runtime verification
of systems against formal sequential specifications. We develop the protocol in
two steps. In the first step, the monitor verifies whether the system satisfies
the specification without learning anything else, though both parties are aware
of the specification. In the second step, we extend the protocol to ensure that
the system remains oblivious to the monitored specification, while the monitor
learns only whether the system satisfies the specification and nothing more. Our
protocol adapts and improves existing techniques used in cryptography, and more
specifically, multi-party computation.\r\n\r\nThe sequential specification defines
the observation step of the monitor, whose granularity depends on the situation
(e.g., banks may be monitored on a daily basis). Our protocol exchanges a single
message per observation step, after an initialization phase. This design minimizes
communication overhead, enabling relatively lightweight privacy-preserving monitoring.
We implement our approach for monitoring specifications described by register
automata and evaluate it experimentally.\r\n"
acknowledgement: "This work is part of the project VAMOS, which has received funding
from the European\r\nResearch Council (ERC) under grant agreement No. 101020093,
and the Austrian Science\r\nFund (FWF) SFB project SpyCoDe F8502.\r\n"
alternative_title:
- ISTA Master’s Thesis
article_processing_charge: No
author:
- first_name: Mahyar
full_name: Karimi, Mahyar
id: 6e5417ba-5355-11ee-ae5a-94c2e510b26b
last_name: Karimi
orcid: 0009-0005-0820-1696
citation:
ama: Karimi M. Privacy-preserving runtime verification. 2026. doi:10.15479/AT-ISTA-21401
apa: Karimi, M. (2026). Privacy-preserving runtime verification. Institute
of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-21401
chicago: Karimi, Mahyar. “Privacy-Preserving Runtime Verification.” Institute of
Science and Technology Austria, 2026. https://doi.org/10.15479/AT-ISTA-21401.
ieee: M. Karimi, “Privacy-preserving runtime verification,” Institute of Science
and Technology Austria, 2026.
ista: Karimi M. 2026. Privacy-preserving runtime verification. Institute of Science
and Technology Austria.
mla: Karimi, Mahyar. Privacy-Preserving Runtime Verification. Institute of
Science and Technology Austria, 2026, doi:10.15479/AT-ISTA-21401.
short: M. Karimi, Privacy-Preserving Runtime Verification, Institute of Science
and Technology Austria, 2026.
corr_author: '1'
date_created: 2026-03-05T15:20:47Z
date_published: 2026-03-05T00:00:00Z
date_updated: 2026-03-13T13:37:20Z
day: '05'
ddc:
- '000'
degree_awarded: MS
department:
- _id: GradSch
- _id: ToHe
doi: 10.15479/AT-ISTA-21401
ec_funded: 1
file:
- access_level: open_access
checksum: 3f49f05c9d123e14d7adb73d3bc50fe2
content_type: application/pdf
creator: mkarimi
date_created: 2026-03-06T14:06:25Z
date_updated: 2026-03-10T15:20:09Z
file_id: '21404'
file_name: 2026_Karimi_Mahyar_Thesis.pdf
file_size: 766048
relation: main_file
- access_level: closed
checksum: 8fb9db4b4187e26443369a993427a5ff
content_type: application/zip
creator: mkarimi
date_created: 2026-03-06T14:06:25Z
date_updated: 2026-03-06T14:06:25Z
file_id: '21405'
file_name: 2026_Karimi_Mahyar_Thesis_src.zip
file_size: 1243394
relation: source_file
file_date_updated: 2026-03-10T15:20:09Z
fulldoi: https://doi.org/10.15479/AT-ISTA-21401
has_accepted_license: '1'
keyword:
- Privacy-preserving verification
- Runtime verification
- Monitoring
- Reactive functionalities
- Cryptographic protocols
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '60'
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Security and Privacy by Design for Complex Systems
publication_identifier:
issn:
- 2791-4585
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '21020'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
title: Privacy-preserving runtime verification
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
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
fulldoi: https://doi.org/10.1145/3801895
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
license: https://creativecommons.org/licenses/by/4.0/
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'
...
---
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-09-16T07:37:21Z
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
fulldoi: https://doi.org/10.4230/LIPIcs.FORC.2026.2
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
- _id: d8f03aaa-b035-11f1-8588-d5147fa879e0
grant_number: COE12
name: Bilateral Artificial Intelligence (Lampert)
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: '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. ACM. 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. ACM, 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. ACM, 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, ACM, 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-09-16T07:36:14Z
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
fulldoi: https://doi.org/10.1145/3808296
has_accepted_license: '1'
intvolume: ' 10'
issue: PLDI
keyword:
- Static Program Analysis
- Differential Privacy
- Probabilistic Programming
- Martingales
language:
- iso: eng
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'
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
grant_number: COE12
name: Bilateral Artificial Intelligence (Chatterjee)
publication: Proceedings of the ACM on Programming Languages
publication_identifier:
eissn:
- 2475-1421
publication_status: published
publisher: ACM
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
_id: '22857'
abstract:
- lang: eng
text: "Artificial intelligence and machine learning have undergone an unprecedented
evolution in the past decade, motivating a research effort toward a theory able
to capture the qualitative behavior of large-scale neural systems. A central puzzle
has been the clear benefit of scaling architecture size and overfitting the training
set in supervised learning tasks. This evidence, in apparent contradiction with
classical statistical learning theory, pushed researchers to develop a new theory
capturing the interplay between the algorithmic and architectural bias of training
and the specific target function, differently from previous methods rooted in
uniform stability.\r\nThis approach has enabled a grounded understanding of novel
learning regimes, typically through formal limits where the number of training
samples $n$, data dimensions $d$, and model parameters $p$ grow to infinity at
different rates. \\\\\r\nIn this thesis, we follow this approach, focusing on
the trustworthiness of high-dimensional models: properties that are difficult
to control during training or deployment and often emerge under unpredictable
or adversarial conditions. In such settings, it is crucial to formally ensure
a priori the reliability of machine learning systems.\r\nFirst, we study data
memorization, both as label fitting and as the storage of private information
about training samples in trained parameters. We prove that $p = \\Omega(n)$ parameters
are sufficient for a deep neural network to memorize a generic set of labels,
and for a model to memorize spurious features across training data. We then give
evidence that $p = \\Omega(dn)$ parameters are instead necessary for an adversary
to reconstruct the full training set from the trained parameters.\r\nSecond, we
study robustness, both to adversarial perturbations and to distribution shift.
We first prove that $p = \\Omega(dn)$ parameters can be sufficient for a class
of neural networks to overfit the training data while guaranteeing robustness
to adversarial perturbations. Then, we focus on spurious correlations learning
in high-dimensional regression, studying the effect of the ridge regularization
parameter in the proportional regime $n = \\Theta(d)$, and connecting it via an
equivalence argument to the role of over-parameterization $p = \\Omega(n)$ in
neural networks. We also investigate the architectural bias of attention-based
networks, showing that they are sensitive to the replacement of individual words
in an embedded sentence, allowing them to generalize on sentences where the contextual
meaning depends on one or few words.\r\nFinally, we study differentially private
optimization in high-dimensional regimes. We prove that standard private gradient
methods do not suffer in the over-parameterized regime $p = \\Omega(n)$, challenging
the current wisdom based on stability-derived generalization bounds. We then consider
linear regression in the proportional regime $n = \\Theta(d)$, showing that standard
private gradient descent can achieve optimal rates under appropriate hyper-parameter
scaling, such as sufficiently small gradient clipping constants, whose role is
still debated in practice."
acknowledged_ssus:
- _id: ScienComp
acknowledgement: "This project was partially supported by the 2019 Lopez-Loreta prize,\r\nthe
European Union (ERC, INF2\r\n, project number 101161364), the Austrian Science Fund\r\n(FWF)
10.55776/COE12, and a Google PhD fellowship in machine intelligence. Furthermore,\r\nthe
candidate acknowledges the support from the Scientific Service Units of the Institute
of\r\nScience and Technology Austria through resources provided by Scientific Computing."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Simone
full_name: Bombari, Simone
id: ca726dda-de17-11ea-bc14-f9da834f63aa
last_name: Bombari
citation:
ama: Bombari S. Trustworthy machine learning in high dimensions. 2026. doi:10.15479/AT-ISTA-22857
apa: Bombari, S. (2026). Trustworthy machine learning in high dimensions.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-22857
chicago: Bombari, Simone. “Trustworthy Machine Learning in High Dimensions.” Institute
of Science and Technology Austria, 2026. https://doi.org/10.15479/AT-ISTA-22857.
ieee: S. Bombari, “Trustworthy machine learning in high dimensions,” Institute of
Science and Technology Austria, 2026.
ista: Bombari S. 2026. Trustworthy machine learning in high dimensions. Institute
of Science and Technology Austria.
mla: Bombari, Simone. Trustworthy Machine Learning in High Dimensions. Institute
of Science and Technology Austria, 2026, doi:10.15479/AT-ISTA-22857.
short: S. Bombari, Trustworthy Machine Learning in High Dimensions, Institute of
Science and Technology Austria, 2026.
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-08T13:40:08Z
date_published: 2026-09-08T00:00:00Z
date_updated: 2026-09-21T13:07:01Z
day: '08'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: MaMo
doi: 10.15479/AT-ISTA-22857
doi_confirm: '1'
file:
- access_level: closed
checksum: 8eab99d6dc6e4476826bdfc7c00fdebb
content_type: application/zip
creator: sbombari
date_created: 2026-09-08T13:28:38Z
date_updated: 2026-09-08T13:28:38Z
file_id: '22859'
file_name: Thesis copy.zip
file_size: 99154325
relation: source_file
- access_level: open_access
checksum: 007033bafe4622ff4c2e758301354df1
content_type: application/pdf
creator: sbombari
date_created: 2026-09-10T10:03:48Z
date_updated: 2026-09-10T10:03:48Z
file_id: '22898'
file_name: 2026_Bombari_Simone_Thesis.pdf
file_size: 12856211
relation: main_file
success: 1
file_date_updated: 2026-09-10T10:03:48Z
fulldoi: https://doi.org/10.15479/AT-ISTA-22857
has_accepted_license: '1'
keyword:
- machine learning
- high-dimensional statistics
- deep learning theory
- privacy
- memorization
- robustness
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '446'
project:
- _id: 92099302-16d5-11f0-9cad-f9a785f54fbd
name: 'Trustworthy Deep Learning Theory: Private Over-Parameterized Models and Robust
LLMs'
- _id: 911e6d1f-16d5-11f0-9cad-c5c68c6a1cdf
grant_number: '101161364'
name: 'Inference in High Dimensions: Light-speed Algorithms and Information Limits'
- _id: 74caaef7-b034-11f1-8f2d-e0e993bb422e
grant_number: COE12
name: Bilateral Artificial Intelligence (Mondelli)
publication_identifier:
isbn:
- 978-3-99078-091-6
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '12537'
relation: part_of_dissertation
status: public
- id: '18972'
relation: part_of_dissertation
status: public
- id: '18973'
relation: part_of_dissertation
status: public
- id: '21324'
relation: part_of_dissertation
status: public
- id: '22894'
relation: part_of_dissertation
status: public
- id: '19627'
relation: part_of_dissertation
status: public
- id: '12859'
relation: part_of_dissertation
status: public
researchdata_availability: no
status: public
supervisor:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
supplementarymaterial: no
title: Trustworthy machine learning in high dimensions
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...