Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy

# Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy
Source: [https://arxiv.org/html/2605.21780](https://arxiv.org/html/2605.21780)
Aman Saxena1,2,31,2,3, Jan Schuchardt44, Yan Scholten1,2,31,2,3, Stephan Günnemann1,2,31,2,3 \{a\.saxena, y\.scholten, s\.guennemann\}@tum\.de,jan\.a\.schuchardt@morganstanley\.com 11Department of Computer Science, Technical University of Munich 22Munich Data Science Institute33MCML 44Machine Learning Research, Morgan Stanley

###### Abstract

Randomized smoothing is a powerful tool for certifying robustness to adversarial perturbations, including poisoning attacks via randomized training and evasion attacks via randomized inference\. Extending these guarantees to backdoor attacks, where training and test data are jointly perturbed, remains challenging because training\- and test\-time randomized mechanisms must be analyzed within a single robustness certificate\. We address this by connecting randomized smoothing to the dual view of differential privacy through privacy profiles, which provide a numerical procedure for composing heterogeneous mechanisms\. The resulting framework enables tight, modular, end\-to\-end certification of complex, composed mechanisms while leveraging existing analyses of differentially private mechanisms\. We instantiate the framework for DP\-SGD and Deep Partition Aggregation with inference\-time smoothing, deriving joint robustness guarantees against both training\-time and inference\-time attacks\. Experiments on MNIST and CIFAR\-10 demonstrate the effectiveness of our framework\. Overall, we provide a principled and general framework for using composite mechanisms to certify robustness under complex threat models that better capture the capabilities of real\-world adversaries\.

## 1Introduction

Adversarial attacks on machine learning systems remain a major concern, particularly with the rapid deployment of large\-scale models such as large language models\[[64](https://arxiv.org/html/2605.21780#bib.bib19),[63](https://arxiv.org/html/2605.21780#bib.bib20),[22](https://arxiv.org/html/2605.21780#bib.bib21)\]\. These attacks extend beyond test\-time evasion\[[4](https://arxiv.org/html/2605.21780#bib.bib41),[68](https://arxiv.org/html/2605.21780#bib.bib42)\]to include data poisoning and backdoor attacks\[[44](https://arxiv.org/html/2605.21780#bib.bib46),[7](https://arxiv.org/html/2605.21780#bib.bib45)\], where adversaries manipulate training data to degrade performance or induce hidden behaviors at inference time, making robustness guarantees under such joint threat settings particularly challenging\. While formally verifying neural network robustness remains difficult\[[32](https://arxiv.org/html/2605.21780#bib.bib66)\], randomized smoothing \(RS\) has emerged as a powerful approach for certifying robustness against inference\-time attacks\[[38](https://arxiv.org/html/2605.21780#bib.bib44),[9](https://arxiv.org/html/2605.21780#bib.bib43),[66](https://arxiv.org/html/2605.21780#bib.bib67)\]\. It has been successfully applied across a range of domains, including image classification\[[9](https://arxiv.org/html/2605.21780#bib.bib43),[78](https://arxiv.org/html/2605.21780#bib.bib73)\], discrete data such as graphs\[[39](https://arxiv.org/html/2605.21780#bib.bib23),[5](https://arxiv.org/html/2605.21780#bib.bib22),[59](https://arxiv.org/html/2605.21780#bib.bib93)\], and quantum classifiers\[[15](https://arxiv.org/html/2605.21780#bib.bib24),[56](https://arxiv.org/html/2605.21780#bib.bib25)\]\. However, extending RS to certify robustness under joint training\- and inference\-time attacks remains largely unexplored, with existing approaches limited to specific threat models and discrete\-feature settings\[[79](https://arxiv.org/html/2605.21780#bib.bib2),[70](https://arxiv.org/html/2605.21780#bib.bib3)\]\.

To certify robustness to inference\-time attacks, RS samples from a distribution over perturbed inputs and bounds how adversarial perturbations affect the induced prediction distribution\. Viewing training as a mapping from datasets to test\-time predictions, the same idea extends to poisoning robustness by considering distributions induced by perturbations to the training algorithm or data\[[73](https://arxiv.org/html/2605.21780#bib.bib49),[29](https://arxiv.org/html/2605.21780#bib.bib13),[41](https://arxiv.org/html/2605.21780#bib.bib59)\]\. This perspective suggests a possible extension to joint perturbations of training and test data, but it remains unclear how to compose guarantees from training\-time and inference\-time randomization\.

![Refer to caption](https://arxiv.org/html/2605.21780v1/x1.png)Figure 1:Overview of our framework and novel perspective: The training and classification pipeline can be viewed as a composition of randomized mechanisms, each with its own privacy guarantee\. By leveraging the primal\-dual equivalence betweenff\-DP and privacy profiles, we can efficiently compose these guarantees to derive end\-to\-end robustness certificates against backdoor attacks\.Compositionality lies at the core of differential privacy \(DP\)\[[20](https://arxiv.org/html/2605.21780#bib.bib88),[81](https://arxiv.org/html/2605.21780#bib.bib78),[12](https://arxiv.org/html/2605.21780#bib.bib55)\], and prior work\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]has leveraged the formalism offf\-DP to tightly compose the adversarial robustness guarantees for specific randomized smoothing mechanisms such as Gaussian noise\. However, whileff\-DP provides a tight theoretical characterization of composition, it does not yield tractable procedures for composition of arbitrary mechanisms, and tractable analysis remains limited to homogeneous settings \(e\.g\., Gaussian or Laplace mechanisms\)\. In contrast, other works connect easily composable notions of DP, such as ADP\[[38](https://arxiv.org/html/2605.21780#bib.bib44),[74](https://arxiv.org/html/2605.21780#bib.bib8)\]and RDP\[[43](https://arxiv.org/html/2605.21780#bib.bib61)\], to randomized smoothing, yielding tractable composition but weaker guarantees thanff\-DP\[[53](https://arxiv.org/html/2605.21780#bib.bib17),[12](https://arxiv.org/html/2605.21780#bib.bib55)\]\. This raises a central question:

*How can we tractably compose arbitrary mechanisms while preserving a tight connection to randomized smoothing to certify robustness against complex threat models such as backdoor attacks?*

In this work, we answer this question by connecting randomized smoothing to the dual perspective of differential privacy, namely privacy profiles\. We derive this dual formulation of randomized smoothing by leveraging and extending the primal–dual equivalence betweenff\-DP and privacy profiles\. This enables us to draw on the extensive literature on tight analyses of commonly used differentially private mechanisms in machine learning\[[2](https://arxiv.org/html/2605.21780#bib.bib65),[61](https://arxiv.org/html/2605.21780#bib.bib30),[60](https://arxiv.org/html/2605.21780#bib.bib89)\], together with numerical composition techniques \(e\.g\., via PLDs\[[13](https://arxiv.org/html/2605.21780#bib.bib82),[47](https://arxiv.org/html/2605.21780#bib.bib86)\]\), thereby operationalizing the connection betweenff\-DP and RS\.

ContributionsWe introduce a general framework for provable robustness that enables a modular design of randomized smoothing\-based classifiers composed of simpler mechanisms\. We provide an overview of our framework in[Figure 1](https://arxiv.org/html/2605.21780#S1.F1)\. Our approach tracks the privacy of individual components under a given threat model and composes these guarantees to derive robustness certificates via the dual formulation of randomized smoothing\. This framework directly enables the evaluation of backdoor robustness under joint threat models\. We demonstrate certified backdoor robustness on MNIST and CIFAR\-10 for compositions of inference\-time Gaussian noise with training\-time randomization, including Deep Partition Aggregation \(DPA\)\[[41](https://arxiv.org/html/2605.21780#bib.bib59)\]and DP\-SGD\. This modularity further allows us to analyze complex training mechanisms in isolation\. In particular, we derive provably tight randomized smoothing guarantees for DP\-SGD\[[1](https://arxiv.org/html/2605.21780#bib.bib60)\]under additions and removals of training data, and empirically demonstrate improvements overLiuet al\.\[[43](https://arxiv.org/html/2605.21780#bib.bib61)\]\.

## 2Related Work

#### Certification Against Backdoor Attacks

Randomized smoothing has become a standard tool for certifiable robustness against evasion attacks\[[9](https://arxiv.org/html/2605.21780#bib.bib43),[38](https://arxiv.org/html/2605.21780#bib.bib44),[42](https://arxiv.org/html/2605.21780#bib.bib48)\]\. Building on this foundation, several works have explored joint certification using RS\[[79](https://arxiv.org/html/2605.21780#bib.bib2),[70](https://arxiv.org/html/2605.21780#bib.bib3),[80](https://arxiv.org/html/2605.21780#bib.bib4)\]\. Other works adopt notions of backdoor robustness that do not capture joint training\-time and inference\-time perturbations\[[73](https://arxiv.org/html/2605.21780#bib.bib49),[51](https://arxiv.org/html/2605.21780#bib.bib1),[30](https://arxiv.org/html/2605.21780#bib.bib5)\]\. In addition,\[[67](https://arxiv.org/html/2605.21780#bib.bib7)\]proposes an RS\-based approach tailored to language\-based tasks, whileLorenzet al\.\[[45](https://arxiv.org/html/2605.21780#bib.bib6)\]relies on bound\-propagation techniques applied to the unrolled training procedure\.

Overall, these approaches are limited to simple training procedures, specific model classes or tasks, and narrowly defined threat models that are easy to analyze and compose\. In contrast, we develop a general framework that enables the use of tools from differential privacy to analyze and compose more general randomized mechanisms\. As a result, randomized smoothing can be applied to general training and inference procedures under broad threat models\.

Certification Against Poisoning Attacks \(Without DP\)Beyond joint certification, a large body of work studies poisoning robustness in isolation\. Most RS\-based poisoning certification methods rely on aggregation\-based techniques, typically variants of DPA\[[41](https://arxiv.org/html/2605.21780#bib.bib59),[27](https://arxiv.org/html/2605.21780#bib.bib9),[71](https://arxiv.org/html/2605.21780#bib.bib10),[29](https://arxiv.org/html/2605.21780#bib.bib13),[52](https://arxiv.org/html/2605.21780#bib.bib14),[57](https://arxiv.org/html/2605.21780#bib.bib94),[26](https://arxiv.org/html/2605.21780#bib.bib92)\]\. Another line of work\[[54](https://arxiv.org/html/2605.21780#bib.bib12)\]uses randomized smoothing with a task\-specific smoothing mechanism for label\-flipping attacks\. While effective in specific settings, these approaches are tightly coupled to particular randomized training mechanisms and are therefore tied to specific threat models\. In contrast, our framework supports a broad class of randomized training procedures that admit a privacy\-profile characterization under a given threat model, along with their principled composition\.

Certification Against Poisoning Attacks \(With DP\)Several works exploit the connection between differential privacy and robustness certification\[[74](https://arxiv.org/html/2605.21780#bib.bib8),[6](https://arxiv.org/html/2605.21780#bib.bib11),[48](https://arxiv.org/html/2605.21780#bib.bib15),[43](https://arxiv.org/html/2605.21780#bib.bib61)\]\.Duet al\.\[[14](https://arxiv.org/html/2605.21780#bib.bib16)\]uses differential privacy for adversarial detection\. This connection has been similarly studied in the context of evasion robustness\[[38](https://arxiv.org/html/2605.21780#bib.bib44),[40](https://arxiv.org/html/2605.21780#bib.bib51),[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\. Existing approaches rely on a coarse characterization of differential privacy via ADP, or Rényi Differential Privacy\[[29](https://arxiv.org/html/2605.21780#bib.bib13)\], leading to suboptimal robustness bounds\. In contrast, our work uses a privacy\-profile–based formulation of differential privacy, which is equivalent to the hypothesis\-testing formulation underlying randomized smoothing\[[9](https://arxiv.org/html/2605.21780#bib.bib43),[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\.

Robustness and Differential PrivacyAdaptive randomized smoothing\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]connectsff\-DP to robustness certification\. However, this perspective does not provide an explicit composition rule, except for homogeneous composition of basic mechanisms such as the addition of Gaussian and Laplace noise\. We use the primal\-dual perspective of DP\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]to convert theff\-DP interpretation of randomized smoothing into a dual \(privacy profile\) formulation\. This enables tractable composition of randomized mechanisms and allows robustness certification to directly leverage privacy analyses from the DP literature, such as tight guarantees for subsampled Gaussian mechanisms\[[61](https://arxiv.org/html/2605.21780#bib.bib30)\]\.

The perspective that privacy profiles provide an optimal characterization of robustness has appeared implicitly in prior work\[[16](https://arxiv.org/html/2605.21780#bib.bib77),[78](https://arxiv.org/html/2605.21780#bib.bib73)\], which derive RS guarantees forℓp\\ell\_\{p\}\-norm evasion certification, that resembles our dual\-to\-primal conversion in[Theorem 4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3)\. However, these works do not establish any connection to differential privacy, and therefore cannot leverage existing tools and analyses from the DP literature\. This work expands upon the use of privacy accounting proposed in Dissertation\[[62](https://arxiv.org/html/2605.21780#bib.bib91)\]\.

## 3Background and Preliminaries

Joint Training\-Inference ProcedureLet each training/test sample𝒙\{\\bm\{x\}\}come from a space𝕏\\mathbb\{X\}and the associated labelyyfrom a set𝕐:=\{1,…,C\}\\mathbb\{Y\}:=\\\{1,\\ldots,C\\\}\. We represent a classifier as a functionf:𝕏→𝕐f:\\mathbb\{X\}\\to\\mathbb\{Y\}, and denote the space of all such classifiers by𝕐𝕏\\mathbb\{Y\}^\{\\mathbb\{X\}\}\. Fori∈ℕi\\in\\mathbb\{N\}, the setTi:=\(𝕏×𝕐\)iT\_\{i\}:=\(\\mathbb\{X\}\\times\\mathbb\{Y\}\)^\{i\}denotes the space of training datasets of sizeii\. A training algorithm𝒜\\mathcal\{A\}maps a training dataset of arbitrary size to a classifier, i\.e\.,𝒜:∪i=1∞Ti→𝕐𝕏\\mathcal\{A\}:\\cup\_\{i=1\}^\{\\infty\}T\_\{i\}\\to\\mathbb\{Y\}^\{\\mathbb\{X\}\}\. Finally, the joint training and inference procedure is a function𝒥:∪i=1∞Ti×𝕏↦𝕐\\mathcal\{J\}:\\cup\_\{i=1\}^\{\\infty\}T\_\{i\}\\times\\mathbb\{X\}\\mapsto\\mathbb\{Y\}that takes a training dataset𝐗train\\mathbf\{X\}\_\{\\text\{train\}\}, produces a classifierf=𝒜​\(𝐗train\)f=\\mathcal\{A\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\), and outputs the prediction for a test input𝒙test∈𝕏\{\\bm\{x\}\}\_\{\\text\{test\}\}\\in\\mathbb\{X\}, i\.e\.,𝒥:\(𝐗train,𝒙test\)↦𝒜​\(𝐗train\)​\(𝒙test\)\\mathcal\{J\}:\(\\mathbf\{X\}\_\{\\text\{train\}\},\{\\bm\{x\}\}\_\{\\text\{test\}\}\)\\mapsto\\mathcal\{A\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\)\(\{\\bm\{x\}\}\_\{\\text\{test\}\}\)\.

Backdoor Threat ModelLet the input space𝕏\\mathbb\{X\}be equipped with a distancedinputd\_\{\\text\{input\}\}and the space of training datasets∪i=1∞Ti\\cup\_\{i=1\}^\{\\infty\}T\_\{i\}with a distancedtraind\_\{\\text\{train\}\}\. Backdoor robustness requires that small perturbations to both the training data and the test input do not change the prediction of the joint training–inference procedure\. Specifically, for\(𝐗train,𝒙test\)\(\\mathbf\{X\}\_\{\\text\{train\}\},\{\\bm\{x\}\}\_\{\\text\{test\}\}\)and all\(𝐗′train,𝒙test′\)\(\\mathbf\{X^\{\\prime\}\}\_\{\\text\{train\}\},\{\\bm\{x\}\}^\{\\prime\}\_\{\\text\{test\}\}\)such thatdtrain​\(𝐗′train,𝐗train\)≤Rd\_\{\\text\{train\}\}\(\\mathbf\{X^\{\\prime\}\}\_\{\\text\{train\}\},\\mathbf\{X\}\_\{\\text\{train\}\}\)\\leq Randdinput​\(𝒙test′,𝒙test\)≤ρd\_\{\\text\{input\}\}\(\{\\bm\{x\}\}^\{\\prime\}\_\{\\text\{test\}\},\{\\bm\{x\}\}\_\{\\text\{test\}\}\)\\leq\\rho, we call a joint training\-inference procedure𝒥\\mathcal\{J\},\(R,ρ\)\(R,\\rho\)\-robust w\.r\.t\.\(dtrain,dinput\)\(d\_\{\\text\{train\}\},d\_\{\\text\{input\}\}\)at\(𝐗train,𝒙test\)\(\\mathbf\{X\}\_\{\\text\{train\}\},\{\\bm\{x\}\}\_\{\\text\{test\}\}\)if𝒥​\(𝐗′train,𝒙test′\)=𝒥​\(𝐗train,𝒙test\)\\mathcal\{J\}\(\\mathbf\{X^\{\\prime\}\}\_\{\\text\{train\}\},\{\\bm\{x\}\}^\{\\prime\}\_\{\\text\{test\}\}\)=\\mathcal\{J\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\{\\bm\{x\}\}\_\{\\text\{test\}\}\)\. We use “backdoor robustness” and “joint training–inference robustness” interchangeably, occasionally abbreviated as “joint robustness”\.

Randomized MechanismsThe notion of a randomized mechanism provides a common abstraction for randomized smoothing and differential privacy\. A*randomized mechanism*ℳ\\mathcal\{M\}is a random function that maps an inputXXto a distribution over a space𝒵\\mathcal\{Z\}, denoted asℳ\(⋅∣X\)\\mathcal\{M\}\(\\cdot\\mid X\)\. Examples include: \(i\) adding Gaussian noise, mapping𝒙↦𝒩​\(𝒙,σ2​I\)\{\\bm\{x\}\}\\mapsto\\mathcal\{N\}\(\{\\bm\{x\}\},\\sigma^\{2\}I\); \(ii\) stochastic training procedures such as DP\-SGD, which induce a distribution over model parameters given a dataset; and \(iii\) randomized subsampling, which defines a distribution over datasets\.

Randomized Smoothing:CC\-class Smooth ClassifierRandomized smoothing derives worst\-case, typically black\-box, robustness guarantees by applying a classifier to samples from a randomized mechanism and aggregating the resulting predictions\. Letℳ\\mathcal\{M\}be a randomized mechanism mapping an inputXXto an intermediate space𝒵\\mathcal\{Z\}\. Further, let\{ϕi\}i=1C\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{C\}be a collection of hypothesis tests111A*hypothesis test*is a randomized mechanismϕ:𝒵→\[0,1\]\\phi:\\mathcal\{Z\}\\to\[0,1\], whereϕ​\(z\)\\phi\(z\)denotes the probability of predicting11\.ϕi:𝒵→\(\{0,1\}\),i∈\{1,…,C\}\\phi\_\{i\}:\\mathcal\{Z\}\\to\(\\\{0,1\\\}\),\\quad i\\in\\\{1,\\dots,C\\\}with∑iϕi=1\\sum\_\{i\}\\phi\_\{i\}=1\. The corresponding smoothed class probabilities are defined aspi:=𝔼z∼ℳ\(⋅∣X\)​\[ϕi​\(z\)\],i∈\{1,…,C\}p\_\{i\}\\;:=\\;\\mathbb\{E\}\_\{z\\sim\\mathcal\{M\}\(\\cdot\\mid X\)\}\\bigl\[\\phi\_\{i\}\(z\)\\bigr\],\\quad i\\in\\\{1,\\dots,C\\\}\. The induced smoothed classifier predicts the labelargmaxi∈\{1,…,C\}⁡pi\\operatorname\{\\rm\{argmax\}\}\_\{i\\in\\\{1,\\dots,C\\\}\}\\;p\_\{i\}\. Here,XXmay represent either a test input, a training dataset, or a training–test pair, depending on the context\. For instance,ℳ\\mathcal\{M\}adds Gaussian noise to the test input, while a neural network represents the collection of hypothesis tests\{ϕi\}i=1C\\\{\\mathcal\{\\phi\}\_\{i\}\\\}\_\{i=1\}^\{C\}\.

Differential PrivacyDifferential privacy\[[18](https://arxiv.org/html/2605.21780#bib.bib52),[19](https://arxiv.org/html/2605.21780#bib.bib53)\]studies the closeness of the output distributionsℳ\(⋅∣X\)\\mathcal\{M\}\(\\cdot\\mid X\)andℳ\(⋅∣X′\)\\mathcal\{M\}\(\\cdot\\mid X^\{\\prime\}\)induced by a randomized mechanismℳ\\mathcal\{M\}on neighboring inputsX≈X′X\\approx X^\{\\prime\}, where≈\\approxdenotes a relation on𝒳\\mathcal\{X\}\. This closeness is typically quantified either through hypothesis–testing–based notions\[[72](https://arxiv.org/html/2605.21780#bib.bib62),[31](https://arxiv.org/html/2605.21780#bib.bib63),[12](https://arxiv.org/html/2605.21780#bib.bib55)\]or through divergence\-based measures\[[3](https://arxiv.org/html/2605.21780#bib.bib64),[2](https://arxiv.org/html/2605.21780#bib.bib65)\]\. The two equivalent characterizations,ff\-DP and privacy profiles, are respectively grounded in these perspectives\. We briefly discuss this equivalence in Section[4](https://arxiv.org/html/2605.21780#S4), with details in Appendix[C](https://arxiv.org/html/2605.21780#A3)\.

Privacy Profiles: The Dual Perspective of DPClassically, differential privacy is defined via a pair\(ε,δ\)\(\\varepsilon,\\delta\), known as*\(ε,δ\)\(\\varepsilon,\\delta\)\-differential privacy*\[[17](https://arxiv.org/html/2605.21780#bib.bib54)\], also referred to as approximate differential privacy \(ADP\)\. A randomized mechanismℳ\\mathcal\{M\}is said to be\(ε,δ\)\(\\varepsilon,\\delta\)\-DP if, for all neighboring inputsX≈X′X\\approx X^\{\\prime\}and all eventsBB,ℳ​\(B∣X\)≤eε​ℳ​\(B∣X′\)\+δ\\mathcal\{M\}\(B\\mid X\)\\leq e^\{\\varepsilon\}\\mathcal\{M\}\(B\\mid X^\{\\prime\}\)\+\\delta\. While this definition captures privacy guarantees at a fixed pair\(ε,δ\)\(\\varepsilon,\\delta\), the trade\-off between\(ε,δ\)\(\\varepsilon,\\delta\)values is needed to tightly characterize composition\. Privacy profiles address this limitation by characterizing, for eachε\\varepsilon, the smallestδ\\deltasuch that the mechanism satisfies\(ε,δ\)\(\\varepsilon,\\delta\)\-DP\. This refinement can be expressed via hockey\-stick divergences\[[3](https://arxiv.org/html/2605.21780#bib.bib64)\], defined asDαHS​\(P∥Q\)=∫\(p​\(y\)−α​q​\(y\)\)\+​𝑑yD^\{\\mathrm\{HS\}\}\_\{\\alpha\}\(P\\,\\\|\\,Q\)=\\int\(p\(y\)\-\\alpha q\(y\)\)\_\{\+\}\\,dy, for the respective densitiespp, andqq\. The*privacy profile*ofℳ\\mathcal\{M\}w\.r\.t\.≈\\approxis a functionδ:ℝ→\[0,1\]\\delta:\\mathbb\{R\}\\to\[0,1\]defined by

δ\(ε\)=supX≈X′DeεHS\(ℳ\(X\)∥ℳ\(X′\)\)\.\\delta\(\\varepsilon\)\\;=\\;\\sup\_\{X\\approx X^\{\\prime\}\}D^\{\\mathrm\{HS\}\}\_\{e^\{\\varepsilon\}\}\\\!\\left\(\\mathcal\{M\}\(X\)\\,\\middle\\\|\\,\\mathcal\{M\}\(X^\{\\prime\}\)\\right\)\.
Dominating PairsGiven a mechanismℳ\\mathcal\{M\}with privacy profileδ​\(ε\)\\delta\(\\varepsilon\)for the neighboring relation≈\\approx, any pair of distributions\(P,Q\)\(P,Q\)satisfyingδ\(ε\)≤DeεHS\(P∥Q\)for everyε∈ℝ\\delta\(\\varepsilon\)\\leq D^\{\\mathrm\{HS\}\}\_\{e^\{\\varepsilon\}\}\\\!\\left\(P\\,\\middle\\\|\\,Q\\right\)\\quad\\text\{for every \}\\varepsilon\\in\\mathbb\{R\}is called a*dominating pair*of\(ℳ,≈\)\(\\mathcal\{M\},\\approx\)\. If equality holds for everyε∈ℝ\\varepsilon\\in\\mathbb\{R\}, then\(P,Q\)\(P,Q\)is called a*tight dominating pair*\.

f−f\-DP: The Primal Perspective of DPThe notion off−f\-DP exploits a hypothesis\-testing perspective to compare the distributions induced by neighboring inputs\. Distinguishing two distributionsPPandQQis characterized by the trade\-off between Type I and Type II errors, formalized by the tradeoff functionΛ​\(P∥Q\)\\Lambda\(P\\,\\\|\\,Q\)\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]\. It evaluates the minimal Type II error at a given Type I error level, over all hypothesis testsϕ∈ℋ\\phi\\in\\mathcal\{H\}:

Λ​\(P∥Q\)​\(α\)=infϕ∈ℋ𝔼z∼Q​\[1−h​\(z\)\]s\.t\.𝔼z∼P​\[h​\(z\)\]=α\.\\Lambda\(P\\,\\\|\\,Q\)\(\\alpha\)\\;=\\;\\inf\_\{\\phi\\in\\mathcal\{H\}\}\\;\\mathbb\{E\}\_\{z\\sim Q\}\[1\-h\(z\)\]\\quad\\text\{s\.t\.\}\\quad\\mathbb\{E\}\_\{z\\sim P\}\[h\(z\)\]=\\alpha\.A functionf:\[0,1\]→\[0,1\]f:\[0,1\]\\to\[0,1\]is a tradeoff function iff it is convex, continuous, non\-increasing, andf​\(α\)≤1−αf\(\\alpha\)\\leq 1\-\\alphafor allα\\alpha\. Given a tradeoff functionff, a mechanismℳ\\mathcal\{M\}is said to satisfy*ff\-differential privacy*if, for allX≈X′X\\approx X^\{\\prime\},Λ\(ℳ\(X\)∥ℳ\(X′\)\)≥f\\;\\Lambda\\\!\\left\(\\mathcal\{M\}\(X\)\\,\\middle\\\|\\,\\mathcal\{M\}\(X^\{\\prime\}\)\\right\)\\;\\geq\\;f\.

Randomized Smoothing from the Primal Perspective of DPCertification of theC−C\-class smooth classifier as defined above reduces to bounding worst\-case changes in the class probabilitiespip\_\{i\}under perturbationsX′X^\{\\prime\}satisfyingd​\(X,X′\)≤δd\(X,X^\{\\prime\}\)\\leq\\deltafor an appropriate distancedd\. As detailed in Appendix[E](https://arxiv.org/html/2605.21780#A5), this leads to the following optimization problem, which closely resembles theff\-DP formulation:

Opt​\(α\):=infϕinfd​\(X,X′\)≤δ𝔼Z∼ℳ\(⋅∣X′\)​\[ϕ​\(Z\)\]s\.t\.𝔼Z∼ℳ\(⋅∣X\)​\[ϕ​\(Z\)\]=α\.\\displaystyle\\text\{Opt\}\(\\alpha\)=\\inf\_\{\\phi\}\\inf\_\{d\(X,X^\{\\prime\}\)\\leq\\delta\}\\;\\mathbb\{E\}\_\{Z\\sim\\mathcal\{M\}\(\\cdot\\mid X^\{\\prime\}\)\}\[\\phi\(Z\)\]\\quad\\text\{s\.t\.\}\\quad\\mathbb\{E\}\_\{Z\\sim\\mathcal\{M\}\(\\cdot\\mid X\)\}\[\\phi\(Z\)\]=\\alpha\.\(1\)The connection betweenf−f\-DP and the above optimization problem is formalized inLyuet al\.\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\], and we restate it in Lemma[3\.1](https://arxiv.org/html/2605.21780#S3.Thmtheorem1)\.

###### Lemma 3\.1\.

Let≈δ\\approx\_\{\\delta\}be the relation defined byX≈δX′X\\approx\_\{\\delta\}X^\{\\prime\}if and only ifd​\(X,X′\)≤δd\(X,X^\{\\prime\}\)\\leq\\delta\. If the mechanismℳ\\mathcal\{M\}satisfiesff\-differential privacy with respect to≈δ\\approx\_\{\\delta\}, thenOpt​\(α\)≥f​\(1−α\)\\text\{Opt\}\(\\alpha\)\\geq f\(1\-\\alpha\)\.

However, the primal perspective \(Lemma[3\.1](https://arxiv.org/html/2605.21780#S3.Thmtheorem1)\) mainly provides a reformulation of the original optimization problem\. To obtain the trade\-off functionff, one must still solve Equation[1](https://arxiv.org/html/2605.21780#S3.E1), e\.g\., via the Neyman–Pearson Lemma[E\.2](https://arxiv.org/html/2605.21780#A5.Thmtheorem2)\.In section[4](https://arxiv.org/html/2605.21780#S4), we discuss further limitations of this perspective and connect randomized smoothing to the dual perspective of DP via privacy profiles\.

## 4Randomized Smoothing from the Dual Perspective of DP

Our goal is to derive robustness guarantees under the joint training–inference threat model introduced in Section[3](https://arxiv.org/html/2605.21780#S3)\. We randomize the training and inference procedures separately, yielding the composed mechanismℳI∘ℳT\\mathcal\{M\}\_\{I\}\\circ\\mathcal\{M\}\_\{T\}, which samples a modelm∼ℳT\(⋅∣Xtrain\)m\\sim\\mathcal\{M\}\_\{T\}\(\\cdot\\mid X\_\{\\text\{train\}\}\)followed by sampling fromℳI\(⋅∣m,xtest\)\\mathcal\{M\}\_\{I\}\(\\cdot\\mid m,x\_\{\\text\{test\}\}\)\. The composed mechanism finally defines a robust classifier on the joint training – test space \(Definition[E\.4](https://arxiv.org/html/2605.21780#A5.Thmtheorem4)\)\. However, as discussed in Appendix[D\.2](https://arxiv.org/html/2605.21780#A4.SS2), the primal perspective handles composition tightly at the theoretical level; it does not provide a tractable way to compose general compositions\. To address this, we introduce the*dual*formulation of randomized smoothing\.

#### Basic Setup

Denote≈ρ\\approx\_\{\\rho\}as the neighboring relation for the threat model\{X′:d​\(X′,X\)≤Δ\}\\\{\{X^\{\\prime\}\}:\\;\\;d\(\{X^\{\\prime\}\},X\)\\leq\\Delta\\\}, i\.e\., we representX′\{X^\{\\prime\}\}as an adversary within the radiusΔ\\DeltaofXXbyX′≈ΔX\{X^\{\\prime\}\}\\approx\_\{\\Delta\}X\. For all suchX′\{X^\{\\prime\}\}, we want to show that aC−C\-class smooth classifierg​\(⋅\)g\(\\cdot\)induced by\(ℳ,\{ϕi\}i=1C\)\(\\mathcal\{M\},\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{C\}\)\(as defined in Section[3](https://arxiv.org/html/2605.21780#S3)\) satisfiesg​\(X′\)=g​\(X\)g\(\{X^\{\\prime\}\}\)=g\(X\)\. Suppose that this relation decomposes into a collection of relations\{≈ρi\}i=1N\\\{\\approx\{\\rho\_\{i\}\}\\\}\_\{i=1\}^\{N\}, i\.e\.,X≈ρX′X\\approx\_\{\\rho\}X^\{\{\}^\{\\prime\}\}iff there is someiisuch thatX≈ρiX′X\\approx\_\{\\rho\_\{i\}\}X^\{\{\}^\{\\prime\}\}, and that the randomized mechanismℳ\\mathcal\{M\}admits privacy profilesδi​\(ε\)\\delta\_\{i\}\(\\varepsilon\)with respect to≈ρi\\approx\_\{\\rho\_\{i\}\}\. The following theorem establishes robustness guarantees under the threat model induced by\{≈ρi\}i=1N\\\{\\approx\_\{\\rho\_\{i\}\}\\\}\_\{i=1\}^\{N\}via the privacy profiles\{δi​\(ε\)\}i=1N\\\{\\delta\_\{i\}\(\\varepsilon\)\\\}\_\{i=1\}^\{N\}\.

###### Theorem 4\.1\.

For the unperturbed inputXX, letc1c\_\{1\}andc2c\_\{2\}denote the majority and second\-majority classes, respectively, and letp1,p2∈\[0,1\]p\_\{1\},p\_\{2\}\\in\[0,1\]satisfy𝔼ℳ​\(𝐗\)​\[ϕc1​\(z\)\]≥p1\>p2≥𝔼z∼ℳ​\(𝐗\)​\[ϕc2​\(z\)\]\\mathbb\{E\}\_\{\\mathcal\{M\}\(\\mathbf\{X\}\)\}\\bigl\[\\phi\_\{c\_\{1\}\}\(z\)\\bigr\]\\;\\geq\\;p\_\{1\}\\;\>\\;p\_\{2\}\\;\\geq\\;\\mathbb\{E\}\_\{z\\sim\\mathcal\{M\}\(\\mathbf\{X\}\)\}\\bigl\[\\phi\_\{c\_\{2\}\}\(z\)\\bigr\]\. Then the classifierg​\(⋅\)g\(\\cdot\)isρ\\rho\-robust atXX, i\.e\., for allX′≈ρXX^\{\{\}^\{\\prime\}\}\\approx\_\{\\rho\}X,g​\(X′\)=g​\(X\)g\(X^\{\{\}^\{\\prime\}\}\)=g\(X\)if

mini∈\{1,…,N\}⁡\[maxε∈ℝ⁡e−ε​\(p1−δi​\(ε\)\)\+maxε∈ℝ⁡e−ε​\(1−p2−δi​\(ε\)\)\]\>1\\min\_\{i\\in\\\{1,\.\.\.,N\\\}\}\\bigl\[\\max\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\\bigl\(p\_\{1\}\-\\delta\_\{i\}\(\\varepsilon\)\\bigr\)\+\\max\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\\bigl\(1\-p\_\{2\}\-\\delta\_\{i\}\(\\varepsilon\)\\bigr\)\\bigr\]\\;\>\\;1

Intuitively, Theorem[4\.1](https://arxiv.org/html/2605.21780#S4.Thmtheorem1)certifies robustness by checking each decomposed neighboring relation≈i\\approx\_\{i\}separately\. This relies on the connection betweenf−f\-DP and randomized smoothing \(Lemma[3\.1](https://arxiv.org/html/2605.21780#S3.Thmtheorem1)\) together with the primal–dual equivalence of DP \(Theorem[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3)\)\. We defer the proof to Appendix[D](https://arxiv.org/html/2605.21780#A4)\.

#### Connection tof−f\-DP

For brevity, we interpret the above result in the binary classification setting\. Letc1c\_\{1\}be the majority class for the unperturbed sampleXX, and letp1p\_\{1\}denote the lower bound on the smooth probability𝔼ℳ​\(X\)​\[ϕc1​\(z\)\]\\mathbb\{E\}\_\{\\mathcal\{M\}\(X\)\}\\bigl\[\\phi\_\{c\_\{1\}\}\(z\)\\bigr\]\. Deriving robustness guarantees then amounts to solving the optimization problem in Equation[1](https://arxiv.org/html/2605.21780#S3.E1)and checking whetherOpt​\(p1\)\>0\.5\\mathrm\{Opt\}\(p\_\{1\}\)\>0\.5\. This can be rewritten as the infimum of the tradeoff functionsΛ​\(ℳ​\(X\)∥ℳ​\(X′\)\)​\(1−p1\)\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\\prime\}\)\)\(1\-p\_\{1\}\)over perturbed inputsX′X^\{\\prime\}such thatX′≈ρXX^\{\\prime\}\\approx\_\{\\rho\}X\.Lyuet al\.\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]lower bound this infimum using thef−f\-DP characterization ofℳ\\mathcal\{M\}with respect to the relation≈ρ\\approx\_\{\\rho\}\. We strengthen this bound by decomposing the space of perturbed inputs using the relations\{≈ρi\}i=1N\\\{\\approx\_\{\\rho\_\{i\}\}\\\}\_\{i=1\}^\{N\}, when the correspondingδi​\(⋅\)\\delta\_\{i\}\(\\cdot\)are tractable to obtain\. To utilize these privacy profiles, we leverage the primal – dual connection of DP\.

#### Exploiting the Primal–Dual Equivalence

Donget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]establish the equivalence betweenf−f\-DP and privacy profiles for symmetric neighboring relations\. We extend this equivalence to general, potentially asymmetric, relations\. This is useful even when≈ρ\\approx\_\{\\rho\}is symmetric, since decomposing it into asymmetric sub\-relations can yield tighter guarantees\. For instance, as discussed later, the symmetric relation ofRRadditions/deletions on training datasets can be decomposed into asymmetric relations with exactlyr\+r\_\{\+\}additions andr−r\_\{\-\}deletions, yielding provably stronger guarantees \(Figure[2](https://arxiv.org/html/2605.21780#S4.F2)\)\. Essentially, we show that the privacy profileδ​\(⋅\)\\delta\(\\cdot\)of a mechanismℳ\\mathcal\{M\}with respect to a relation≈\\approxis equivalent to the convex biconjugate of the infimum over tradeoff functionsΛ\(ℳ\(X\),\|,ℳ\(X′\)\)\\Lambda\(\\mathcal\{M\}\(X\),\|,\\mathcal\{M\}\(X^\{\\prime\}\)\)\. We formalize this via the Optimal Tradeoff Function \(Definition[4\.2](https://arxiv.org/html/2605.21780#S4.Thmtheorem2), Theorem[C\.8](https://arxiv.org/html/2605.21780#A3.Thmtheorem8)\) and state the equivalence in Theorem[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3), with details and proofs deferred to Appendix[C](https://arxiv.org/html/2605.21780#A3)\.

###### Definition 4\.2\.

\(Optimal Tradeoff Function\) Given a mechanismℳ\\mathcal\{M\}, and neighboring relation≈\\approx, we say that a tradeoff functionffis the optimal tradeoff function ifℳ\\mathcal\{M\}isf−f\-DP w\.r\.t\.,≈\\approx, and for any tradeoff functionf′f\{\{\}^\{\\prime\}\}ifℳ\\mathcal\{M\}isf′−f^\{\{\}^\{\\prime\}\}\-DP w\.r\.t\.,≈\\approx, thenf′≤ff^\{\{\}^\{\\prime\}\}\\leq f\.

###### Theorem 4\.3\.

Letℳ\\mathcal\{M\}be a randomized mechanism with optimal tradeoff functionffand privacy profileδ\\deltafor the neighboring relation≈\\approx\. The following equivalent conversions hold:

\(Primal to Dual\)δ​\(ε\)\\displaystyle\\text\{\(Primal to Dual\)\}\\quad\\delta\(\\varepsilon\)=1\+\(f−1\)∗​\(−eε\),\\displaystyle=1\+\(f^\{\-1\}\)^\{\*\}\(\-e^\{\\varepsilon\}\),\(Dual to Primal\)f​\(α\)\\displaystyle\\text\{\(Dual to Primal\)\}\\quad f\(\\alpha\)=supε∈ℝe−ε​\(1−δ​\(ε\)−α\)\.\\displaystyle=\\sup\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(1\-\\delta\(\\varepsilon\)\-\\alpha\)\.Here,f−1f^\{\-1\}represents the left continuous inverse of a non\-decreasing function, andf∗f^\{\*\}represents the convex conjugate offf\.

#### Why decompose≈ρ\\approx\_\{\\rho\}further?

The*Dual to Primal*part of Theorem[4\.1](https://arxiv.org/html/2605.21780#S4.Thmtheorem1)suggests that taking the maximum overδi​\(⋅\)\\delta\_\{i\}\(\\cdot\)and then converting toffyields a lower bound on first converting eachδi\\delta\_\{i\}tofif\_\{i\}and then taking the minimum\. As discussed above, we need the latter for robustness certification\. We illustrate this using a subsampled Gaussian mechanism under100100changes \(≈100\\approx\_\{100\}\) in Figure[2](https://arxiv.org/html/2605.21780#S4.F2)\. The pointwise minimum over the decomposed tradeoff functions lies strictly above the tradeoff function for the non\-decomposed relation≈100\\approx\_\{100\}\.

#### Advantages of the Dual Perspective

![Refer to caption](https://arxiv.org/html/2605.21780v1/x2.png)Figure 2:Minimum over decomposed tradeoff functions vs\. the tradeoff function for the non\-decomposed relation\(≈100\\approx\_\{100\}\)\.Λr\+,r−\\Lambda\_\{r\_\{\+\},r\_\{\-\}\}: subsampled Gaussian \(γ=0\.00256\\gamma=0\.00256,σ=0\.05\\sigma=0\.05\)\.*Numerical composition and leveraging the DP literature:*In contrast to the primal perspective, representing mechanisms via their privacy profiles enables efficient, algorithm\-agnostic numerical accounting, e\.g\., through convolution of privacy\-loss distributions\[[65](https://arxiv.org/html/2605.21780#bib.bib58),[34](https://arxiv.org/html/2605.21780#bib.bib57)\], thereby yielding tight privacy guarantees for complex, heterogeneous mechanisms\. Moreover, the dual perspective allows us to directly leverage existing analyses of mechanisms relevant to machine learning\. For example,Schuchardtet al\.\[[61](https://arxiv.org/html/2605.21780#bib.bib30)\]derive tight dominating pairs for the subsampled Gaussian mechanism underlying DP\-SGD under additions/removals\.*Tightness\.*For a collection of tradeoff functionsΛi\\Lambda\_\{i\}corresponding toδi​\(⋅\)\\delta\_\{i\}\(\\cdot\), any tradeoff functionffsuch thatℳ\\mathcal\{M\}isf−f\-DP for≈ρ\\approx\_\{\\rho\}satisfiesf≤mini⁡Λif\\leq\\min\_\{i\}\\Lambda\_\{i\}, with strict inequality in general \(Figure[2](https://arxiv.org/html/2605.21780#S4.F2)\)\. Therefore, the primal perspective ofLyuet al\.\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]yields provably weaker guarantees than decomposition\-based analysis in Theorem[4\.1](https://arxiv.org/html/2605.21780#S4.Thmtheorem1)\. Moreover, if eachδi​\(⋅\)\\delta\_\{i\}\(\\cdot\)is attained by a pair of datasets, the resulting guarantees are black\-box tight \(Lemma[D\.2](https://arxiv.org/html/2605.21780#A4.Thmtheorem2)\)\.

These properties enable a modular design of provably robust classifiers from simpler components without losing the guarantees of RS\. The next section describes how to operationalize this framework and instantiate it in different settings\.

## 5Designing Robust Training–Test Procedures

We adopt a modular pipeline separating*threat modeling*,*mechanism design*, and*privacy accounting*\. Given a threat model, we \(i\) represent the mechanism as a stack of simpler randomized components with tractable dominating pairs with respect to the neighboring relation induced by the threat model, \(ii\) discretize and \(iii\) compose the dominating pairs to obtain a discrete dominating pair for the overall mechanism, and \(iv\) derive privacy profiles to certify robustness via Theorem[4\.1](https://arxiv.org/html/2605.21780#S4.Thmtheorem1)\(see[Figure 1](https://arxiv.org/html/2605.21780#S1.F1)\)\. As discussed in Section 4, we decompose the neighboring relation into subsets when needed for tighter analysis\. Numerical privacy accounting, i\.e\., step \(ii\), has been studied extensively\[[8](https://arxiv.org/html/2605.21780#bib.bib79),[21](https://arxiv.org/html/2605.21780#bib.bib80),[23](https://arxiv.org/html/2605.21780#bib.bib81),[13](https://arxiv.org/html/2605.21780#bib.bib82),[35](https://arxiv.org/html/2605.21780#bib.bib83),[33](https://arxiv.org/html/2605.21780#bib.bib84),[25](https://arxiv.org/html/2605.21780#bib.bib85),[81](https://arxiv.org/html/2605.21780#bib.bib78),[34](https://arxiv.org/html/2605.21780#bib.bib57),[65](https://arxiv.org/html/2605.21780#bib.bib58),[47](https://arxiv.org/html/2605.21780#bib.bib86)\]\. In our implementation, we use the method ofDoroshenkoet al\.\[[13](https://arxiv.org/html/2605.21780#bib.bib82)\], as implemented in the Google Differential Privacy library\[[24](https://arxiv.org/html/2605.21780#bib.bib87)\], to obtain an upper bound on the composed privacy profile\. We illustrate these steps through the following examples\.

#### Example 1: Poisoning Certification using DP\-SGD

*\(a\) Threat model and mechanism:*To certify against poisoning attacks where an adversary can add or remove up toRRtraining examples from𝐗train\\mathbf\{X\}\_\{\\text\{train\}\}, we employ DP\-SGD training\. Each iteration of DP\-SGD involves applying Poisson subsampling with rateγ\\gammato get a minibatch, i\.e\., including each training record i\.i\.d\. with probabilityγ\\gamma\. This is followed by adding Gaussian noisez∼𝒩​\(0,C2​σ2\)z\\sim\\mathcal\{N\}\(0,C^\{2\}\\sigma^\{2\}\)to the gradients evaluated on the minibatch and clipped inℓ2\\ell\_\{2\}norm toCC\. Letℳi\\mathcal\{M\}\_\{i\}denote the randomized mechanism at iterationii\. AfterIIiterations, the composed mechanismℳtrain:=ℳI∘⋯∘ℳ1\\mathcal\{M\}\_\{\\text\{train\}\}:=\\mathcal\{M\}\_\{I\}\\circ\\cdots\\circ\\mathcal\{M\}\_\{1\}induces a distributionℳtrain​\(𝐗train\)\\mathcal\{M\}\_\{\\text\{train\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\)over learned parametersww\.*\(b\) Decomposition of the neighboring relation:*We decompose the relation≈R\\approx\_\{R\}into\{≈r\+,r−\}r\+\+r−=R\\\{\\approx\_\{r\_\{\+\},r\_\{\-\}\}\\\}\_\{r\_\{\+\}\+r\_\{\-\}=R\}corresponding tor\+r\_\{\+\}additions andr−r\_\{\-\}removals\. This decomposition is advantageous as it admits tractable\[[61](https://arxiv.org/html/2605.21780#bib.bib30), Theorem 3\.8\]and tight dominating pairs in the black\-box sense\[[61](https://arxiv.org/html/2605.21780#bib.bib30), Theorem M\.4\]\. Specifically, latter implies that[Theorem 4\.1](https://arxiv.org/html/2605.21780#S4.Thmtheorem1)achieves a tight certificate for DP\-SGD in the black\-box sense \(see Lemma[D\.2](https://arxiv.org/html/2605.21780#A4.Thmtheorem2)\)*\(c\) Dominating pairs:*For each mechanismℳi\\mathcal\{M\}\_\{i\}, the dominating pair\(Pr\+,r−,Qr\+,r−\)\(P\_\{r\_\{\+\},r\_\{\-\}\},Q\_\{r\_\{\+\},r\_\{\-\}\}\)is given by

Pr\+,r−=∑i=0r−\(r−i\)​γi​\(1−γ\)r−−i​𝒩​\(i,σ2\),Qr\+,r−=∑j=0r\+\(r\+j\)​γj​\(1−γ\)r\+−j​𝒩​\(−j,σ2\)\.P\_\{r\_\{\+\},r\_\{\-\}\}=\\sum\_\{i=0\}^\{r\_\{\-\}\}\\binom\{r\_\{\-\}\}\{i\}\\gamma^\{i\}\(1\-\\gamma\)^\{r\_\{\-\}\-i\}\\mathcal\{N\}\(i,\\sigma^\{2\}\),\\quad Q\_\{r\_\{\+\},r\_\{\-\}\}=\\sum\_\{j=0\}^\{r\_\{\+\}\}\\binom\{r\_\{\+\}\}\{j\}\\gamma^\{j\}\(1\-\\gamma\)^\{r\_\{\+\}\-j\}\\mathcal\{N\}\(\-j,\\sigma^\{2\}\)\.

#### Example 2: Joint Certification using DP\-SGD and Inference\-time Gaussian Noise

*\(a\) Threat model and mechanism:*We consider a joint threat model where an adversary can add or remove up toRRtraining examples and perturb the test input by at mostδ\\deltainℓ2\\ell\_\{2\}norm\. Building on the DP\-SGD training mechanismℳtrain\\mathcal\{M\}\_\{\\text\{train\}\}defined above, we apply an additional Gaussian mechanism at inference time,𝒢σ​\(𝐱test\):=𝒩​\(𝐱test,σ2​𝕀\)\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\_\{\\text\{test\}\}\):=\\mathcal\{N\}\(\\mathbf\{x\}\_\{\\text\{test\}\},\\sigma^\{2\}\\mathbb\{I\}\), resulting inℳ​\(𝐗train,𝐱test\)=\(w∼ℳtrain​\(𝐗train\),𝐱~∼𝒢σ​\(𝐱test\)\)\\mathcal\{M\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)=\\bigl\(w\\sim\\mathcal\{M\}\_\{\\text\{train\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\),\\;\\tilde\{\\mathbf\{x\}\}\\sim\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\_\{\\text\{test\}\}\)\\bigr\)\.*\(b\) Decomposition of the neighboring relation:*We extend the decomposition to the joint relation≈R,δ\\approx\_\{R,\\delta\}as\{≈r\+,r−,δ\}r\+\+r−=R\\\{\\approx\_\{r\_\{\+\},r\_\{\-\},\\delta\}\\\}\_\{r\_\{\+\}\+r\_\{\-\}=R\}, where the training component is handled as before, while theℓ2\\ell\_\{2\}perturbation is handled directly without further decomposition, as the worst\-case HS divergence is attained by a pair of inputs at distanceδ\\delta\.*\(c\) Dominating pairs:*The training component uses\(Pr\+,r−,Qr\+,r−\)\(P\_\{r\_\{\+\},r\_\{\-\}\},Q\_\{r\_\{\+\},r\_\{\-\}\}\)as defined above, while the Gaussian mechanism admits the dominating pair\(𝒩​\(0,σ2\),𝒩​\(δ,σ2\)\)\(\\mathcal\{N\}\(0,\\sigma^\{2\}\),\\mathcal\{N\}\(\\delta,\\sigma^\{2\}\)\)\. These are composed to obtain a dominating pair for the joint mechanism\.

#### Example 3: Composing DPA with an arbitrary Mechanism

We reinterpret DPA\[[41](https://arxiv.org/html/2605.21780#bib.bib59)\]as a randomized training mechanism, derive its privacy profile, and an analytical tradeoff function for a neighboring relation induced by up toRRchanges to the dataset \(deletion, insertion, or substitution\)\. We further extend this characterization to the composition of DPA with an arbitrary base mechanism, such as inference\-time Gaussian noise\. We formalize these in Theorem[5\.1](https://arxiv.org/html/2605.21780#S5.Thmtheorem1), and discuss proofs and details in[subsection D\.1](https://arxiv.org/html/2605.21780#A4.SS1)\.

###### Theorem 5\.1\.

Let𝒟N\\mathcal\{D\}\_\{N\}denote the DPA mechanism withNNpartitions, and letℬ\\mathcal\{B\}be any inference\-time mechanism on𝕏\\mathbb\{X\}that isfbf\_\{b\}\-DP with privacy profileδb​\(ϵ\)\\delta\_\{b\}\(\\epsilon\)for a neighboring relation≈b\\approx\_\{b\}\. Let≈R\\approx\_\{R\}be the relation corresponding to uptoRRchanges in the dataset, define the combined relation as≈c\\approx\_\{c\}as\(𝐗train,𝐱test\)≈c\(𝐗train′,𝐱′test\)⇔𝐗train≈R𝐗′train∧𝐱test≈b𝐱′test\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)\\approx\_\{c\}\(\\mathbf\{X^\{\{\}^\{\\prime\}\}\_\{\\text\{train\}\}\},\\mathbf\{x^\{\{\}^\{\\prime\}\}\}\_\{\\text\{test\}\}\)\\iff\\mathbf\{X\}\_\{\\text\{train\}\}\\approx\_\{R\}\\mathbf\{X^\{\{\}^\{\\prime\}\}\}\_\{\\text\{train\}\}\\;\\;\\land\\;\\;\\mathbf\{x\}\_\{\\text\{test\}\}\\approx\_\{b\}\\mathbf\{x^\{\{\}^\{\\prime\}\}\}\_\{\\text\{test\}\}\. Then the composed mechanismℬ∘𝒟N\\mathcal\{B\}\\circ\\mathcal\{D\}\_\{N\}, defined on⋃i=1NTi×𝕏\\mathcal\{\\bigcup\}\_\{i=1\}^\{N\}T\_\{i\}\\times\\mathbb\{X\}isfcf\_\{c\}\-DP with privacy profileδc​\(ϵ\)\\delta\_\{c\}\(\\epsilon\)for the neighboring relation≈c\\approx\_\{c\}, whereδc​\(ϵ\)=RN\+\(1−RN\)​δb​\(ϵ\)\\delta\_\{c\}\(\\epsilon\)=\\frac\{R\}\{N\}\+\(1\-\\frac\{R\}\{N\}\)\\,\\delta\_\{b\}\(\\epsilon\), and

fc​\(α\)=\{\(1−RN\)​fb​\(α1−RN\),if​α≤1−RN,0,otherwise\.f\_\{c\}\(\\alpha\)=\\begin\{dcases\}\\Bigl\(1\-\\frac\{R\}\{N\}\\Bigr\)\\,f\_\{b\}\\\!\\left\(\\frac\{\\alpha\}\{1\-\\frac\{R\}\{N\}\}\\right\),&\\text\{if \}\\alpha\\leq 1\-\\frac\{R\}\{N\},\\\\\[6\.0pt\] 0,&\\text\{otherwise\}\.\\end\{dcases\}

These instantiations demonstrate how our framework systematically reduces joint training–test robustness certification to privacy accounting of composable randomized mechanisms\.

## 6Experimental Evaluation

We evaluate two settings:*\(i\) certification against poisoning attacks*and*\(ii\) joint training–test certification against backdoor attacks*\. Our training procedures combine selected components from sub\-sampling \(batching\), additive Gaussian noise on training examples, DP\-SGD, and DPA\. We instantiate our framework on image classification for CIFAR10\[[36](https://arxiv.org/html/2605.21780#bib.bib27)\]and MNIST\[[37](https://arxiv.org/html/2605.21780#bib.bib28)\]\. In*\(i\)*, we show improved adversarial accuracy for our analysis of DP\-SGD compared to prior work\[[43](https://arxiv.org/html/2605.21780#bib.bib61)\]\. In*\(ii\)*, we show the utility of our framework for certifying novel threat models\. We provide experiment setup details in[Appendix B](https://arxiv.org/html/2605.21780#A2)\.

### 6\.1Poisoning Certification

We consider the training\-perturbation threat model that allowsRRchanges in the training data, as discussed in Section[5](https://arxiv.org/html/2605.21780#S5)\. We compare against DPA and RDP\-based accounting for DP\-SGD\. However, the group\-privacy analysis ofLiuet al\.\[[43](https://arxiv.org/html/2605.21780#bib.bib61)\]does not account for the increase in sensitivity with the radiusRR\. We therefore also compare against a "corrected" RDP\-based accounting that we derive in[Appendix F](https://arxiv.org/html/2605.21780#A6)\. We report results for88epochs of DP\-SGD and indicate the number of DPA partitions in Figures[4](https://arxiv.org/html/2605.21780#S6.F4),[4](https://arxiv.org/html/2605.21780#S6.F4)\. The degradation in certification with the number of epochs is shown in[Appendix H](https://arxiv.org/html/2605.21780#A8)\. We also observe that, for the largeσγ\\frac\{\\sigma\}\{\\gamma\}values considered here, the subsampled Gaussian behaves closely to a Gaussian with effective standard deviationσγ\\frac\{\\sigma\}\{\\gamma\}; we denote this as the Gaussian approximation in the figures\.

![Refer to caption](https://arxiv.org/html/2605.21780v1/x3.png)Figure 3:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 8, with RDP\-based accounting and DPA using100100partitions for CIFAR\-10\.
![Refer to caption](https://arxiv.org/html/2605.21780v1/x4.png)Figure 4:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 8, with RDP\-based accounting and DPA using100,150,200100,150,200partitions for the MNIST dataset\.

### 6\.2Joint Robustness Certification

We consider two training threat models:*\(i\)*poisoning via up toRRtraining\-example additions or deletions, and*\(ii\)*perturbations of up toδtrain\\delta\_\{\\text\{train\}\}inℓ2\\ell\_\{2\}norm applied to at mostRRtraining examples\. Each is combined with anℓ2\\ell\_\{2\}perturbation of sizeδtest\\delta\_\{\\text\{test\}\}applied to the test image at inference time\. To certify against*\(ii\)*, we add noise to the training samples and use Theorem[G\.1](https://arxiv.org/html/2605.21780#A7.Thmtheorem1)to upper bound the privacy profile\. We show results for the first threat model in Figures[5](https://arxiv.org/html/2605.21780#S6.F5),[7](https://arxiv.org/html/2605.21780#S6.F7), and for the second in Figure[6](https://arxiv.org/html/2605.21780#S6.F6)\.

![Refer to caption](https://arxiv.org/html/2605.21780v1/x5.png)Figure 5:Certified accuracy vs\. number of additions/deletions in the training dataset \(*Radius*\) for different inference perturbationsδ\\deltafor the CIFAR\-10 dataset\. We compare DPA trained on100100partitions with1010epochs of DPSGD\.![Refer to caption](https://arxiv.org/html/2605.21780v1/x6.png)Figure 6:Certified accuracy vs\. the number of training examples that can be perturbed up toℓ2\\ell\_\{2\}magnitudeδ\\delta, together with an inference perturbation of sizeδtest=0\.2\\delta\_\{\\text\{test\}\}=0\.2\. The plots are for MNIST models trained with DP\-SGD and input Gaussian noiseσ=0\.2\\sigma=0\.2for88epochs\. Each plot corresponds to a single choice ofδ/σ\\delta/\\sigma\.![Refer to caption](https://arxiv.org/html/2605.21780v1/x7.png)Figure 7:Certified accuracy vs\. number of additions/deletions in the training dataset \(*Radius*\) for different inference perturbationsδ\\deltafor the MNIST dataset\. We compare DPA trained on100100, and130130partitions with88epochs of DPSGD\.

## 7Conclusion

We establish a unified framework for certifying robustness against poisoning and backdoor attacks by leveraging the primal–dual perspective on differential privacy\. Our key insight is that, while the primal \(hypothesis\-testing\) view naturally connects differential privacy to randomized smoothing, the dual view, expressed through privacy profiles and hockey\-stick divergences, enables efficient numerical composition of heterogeneous mechanisms\. This dual perspective allows us to decompose complex joint training–test procedures into simpler randomized components and compose them to obtain end\-to\-end robustness guarantees\. We demonstrate the practical utility of our framework by deriving joint robustness certificates for novel threat models and tight poisoning certificates for DP\-SGD\. We further provide an analytical characterization of composing DPA with any base mechanism\.

#### Limitations\.

Our approach has several limitations\. First, certifying DP\-SGD requires sampling many models to estimate the relevant expectations, which introduces a non\-trivial computational overhead\. However, certification is performed offline and can often be parallelized, making the cost manageable in many practical settings\. Second, certification via decomposition scales asO​\(R\)O\(R\); for example, for the subsampled Gaussian mechanism underRRadditions/deletions, one must certifyR\+1R\+1distinct cases\. While this introduces additional complexity, the resulting guarantees remain tractable for moderate threat sizes and provide a level of flexibility not supported by prior approaches\. Third, robustness guarantees can come at the cost of utility, a trade\-off that is not specific to our approach but rather common in certified robustness and privacy\-preserving learning more broadly\. Nevertheless, we believe this trade\-off can be mitigated through improved training procedures and optimization techniques, making certifiable robustness increasingly practical at scale in the long run\.

## Acknowledgments

We would like to thank Arthur Kosmala for proofreading this manuscript\. This work has been funded by the DAAD program Konrad Zuse Schools of Excellence in Artificial Intelligence \(sponsored by the Federal Ministry of Education and Research\)\. The authors of this work take full responsibility for its content\.

## References

- \[1\]\(2016\)Deep learning with differential privacy\.InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,CCS ’16,New York, NY, USA,pp\. 308–318\.External Links:ISBN 9781450341394Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p6.1)\.
- \[2\]B\. Balle, G\. Barthe, and M\. Gaboardi\(2018\)Privacy amplification by subsampling: tight analyses via couplings and divergences\.InAdvances in Neural Information Processing Systems,S\. Bengio, H\. Wallach, H\. Larochelle, K\. Grauman, N\. Cesa\-Bianchi, and R\. Garnett \(Eds\.\),Vol\.31,pp\.\.Cited by:[Appendix G](https://arxiv.org/html/2605.21780#A7.1.p1.7),[Appendix G](https://arxiv.org/html/2605.21780#A7.2.p2.9),[§1](https://arxiv.org/html/2605.21780#S1.p5.2),[§3](https://arxiv.org/html/2605.21780#S3.p5.7)\.
- \[3\]G\. Barthe and F\. Olmedo\(2013\)Beyond differential privacy: composition theorems and relational logic for f\-divergences between probabilistic programs\.InInternational Colloquium on Automata, Languages, and Programming,pp\. 49–60\.Cited by:[§3](https://arxiv.org/html/2605.21780#S3.p5.7),[§3](https://arxiv.org/html/2605.21780#S3.p6.18)\.
- \[4\]B\. Biggio, I\. Corona, D\. Maiorca, B\. Nelson, N\. Šrndić, P\. Laskov, G\. Giacinto, and F\. Roli\(2013\)Evasion attacks against machine learning at test time\.InMachine Learning and Knowledge Discovery in Databases,H\. Blockeel, K\. Kersting, S\. Nijssen, and F\. Železný \(Eds\.\),Berlin, Heidelberg,pp\. 387–402\.External Links:ISBN 978\-3\-642\-40994\-3Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[5\]A\. Bojchevski, J\. Gasteiger, and S\. Günnemann\(2023\)Efficient robustness certificates for discrete data: sparsity\-aware randomized smoothing for graphs, images and more\.External Links:2008\.12952Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[6\]E\. Borgnia, J\. Geiping, V\. Cherepanova, L\. Fowl, A\. Gupta, A\. Ghiasi, F\. Huang, M\. Goldblum, and T\. Goldstein\(2021\)DP\-instahide: provably defusing poisoning and backdoor attacks with differentially private data augmentations\.External Links:2103\.02079Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[7\]X\. Chen, C\. Liu, B\. Li, K\. Lu, and D\. Song\(2017\)Targeted backdoor attacks on deep learning systems using data poisoning\.arXiv preprint arXiv:1712\.05526\.Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[8\]C\. A\. Choquette\-Choo, A\. Ganesh, T\. Steinke, and A\. Thakurta\(2024\)Privacy amplification for matrix mechanisms\.External Links:2310\.15526,[Link](https://arxiv.org/abs/2310.15526)Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[9\]J\. Cohen, E\. Rosenfeld, and Z\. Kolter\(2019\-09–15 Jun\)Certified adversarial robustness via randomized smoothing\.InProceedings of the 36th International Conference on Machine Learning,K\. Chaudhuri and R\. Salakhutdinov \(Eds\.\),Proceedings of Machine Learning Research, Vol\.97,pp\. 1310–1320\.Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p1.7),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px2.p1.1),[Appendix E](https://arxiv.org/html/2605.21780#A5.p1.3),[Appendix E](https://arxiv.org/html/2605.21780#A5.p2.4),[§1](https://arxiv.org/html/2605.21780#S1.p1.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[10\]S\. De, L\. Berrada, J\. Hayes, S\. L\. Smith, and B\. Balle\(2022\)Unlocking high\-accuracy differentially private image classification through scale\.External Links:2204\.13650Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p1.7)\.
- \[11\]J\. Deng, W\. Dong, R\. Socher, L\. Li, K\. Li, and L\. Fei\-Fei\(2009\)ImageNet: a large\-scale hierarchical image database\.InCVPR,Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p1.7)\.
- \[12\]J\. Dong, A\. Roth, and W\. J\. Su\(2019\)Gaussian differential privacy\.arXiv preprint arXiv:1905\.02383\.Cited by:[2nd item](https://arxiv.org/html/2605.21780#A3.I1.i2.p1.4),[Appendix C](https://arxiv.org/html/2605.21780#A3.SS0.SSS0.Px3.p5.2),[Appendix C](https://arxiv.org/html/2605.21780#A3.SS0.SSS0.Px4.p1.2),[§C\.2](https://arxiv.org/html/2605.21780#A3.SS2.9.p1.14),[§C\.2](https://arxiv.org/html/2605.21780#A3.SS2.SSS0.Px1.p2.1),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px1.p1.4),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px2.p1.1),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.p1.4),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.p2.1),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.p3.6),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.p5.8),[§1](https://arxiv.org/html/2605.21780#S1.p3.3),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p5.2),[§3](https://arxiv.org/html/2605.21780#S3.p5.7),[§3](https://arxiv.org/html/2605.21780#S3.p8.6),[§4](https://arxiv.org/html/2605.21780#S4.SS0.SSS0.Px3.p1.9)\.
- \[13\]V\. Doroshenko, B\. Ghazi, P\. Kamath, R\. Kumar, and P\. Manurangsi\(2022\)Connect the dots: tighter discrete approximations of privacy loss distributions\.External Links:2207\.04380,[Link](https://arxiv.org/abs/2207.04380)Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p5.2),[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[14\]M\. Du, R\. Jia, and D\. Song\(2019\)Robust anomaly detection and backdoor attack detection via differential privacy\.External Links:1911\.07116Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[15\]Y\. Du, M\. Hsieh, T\. Liu, D\. Tao, and N\. Liu\(2021\-05\)Quantum noise protects quantum classifiers against adversaries\.Physical Review Research3\(2\)\.External Links:ISSN 2643\-1564Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[16\]K\. D\. Dvijotham, J\. Hayes, B\. Balle, Z\. Kolter, C\. Qin, A\. Gyorgy, K\. Xiao, S\. Gowal, and P\. Kohli\(2020\)A framework for robustness certification of smoothed classifiers using f\-divergences\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p6.1)\.
- \[17\]C\. Dwork, K\. Kenthapadi, F\. McSherry, I\. Mironov, and M\. Naor\(2006\)Our data, ourselves: privacy via distributed noise generation\.InAdvances in Cryptology \- EUROCRYPT 2006,S\. Vaudenay \(Ed\.\),Berlin, Heidelberg,pp\. 486–503\.External Links:ISBN 978\-3\-540\-34547\-3Cited by:[§3](https://arxiv.org/html/2605.21780#S3.p6.18)\.
- \[18\]C\. Dwork, F\. McSherry, K\. Nissim, and A\. Smith\(2006\)Calibrating noise to sensitivity in private data analysis\.InTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4\-7, 2006\. Proceedings 3,pp\. 265–284\.Cited by:[§3](https://arxiv.org/html/2605.21780#S3.p5.7)\.
- \[19\]C\. Dwork and A\. Roth\(2014\)The algorithmic foundations of differential privacy\.Foundations and Trends® in Theoretical Computer Science9\(3–4\),pp\. 211–407\.External Links:ISSN 1551\-305XCited by:[§3](https://arxiv.org/html/2605.21780#S3.p5.7)\.
- \[20\]C\. Dwork, G\. N\. Rothblum, and S\. P\. Vadhan\(2010\)Boosting and differential privacy\.2010 IEEE 51st Annual Symposium on Foundations of Computer Science,pp\. 51–60\.External Links:[Link](https://api.semanticscholar.org/CorpusID:9132611)Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p3.3)\.
- \[21\]V\. Feldman and M\. Shenfeld\(2026\)Efficient privacy loss accounting for subsampling and random allocation\.External Links:2602\.17284,[Link](https://arxiv.org/abs/2602.17284)Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[22\]S\. Geisler, T\. Wollschläger, M\. H\. I\. Abdalla, J\. Gasteiger, and S\. Günnemann\(2025\)Attacking large language models with projected gradient descent\.External Links:2402\.09154Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[23\]B\. Ghazi, P\. Kamath, R\. Kumar, and P\. Manurangsi\(2022\)Faster privacy accounting via evolving discretization\.External Links:2207\.04381,[Link](https://arxiv.org/abs/2207.04381)Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[24\]Google\(2023\)Google differential privacy library\.Note:[https://github\.com/google/differential\-privacy](https://github.com/google/differential-privacy)Accessed: 2026\-04Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[25\]S\. Gopi, Y\. T\. Lee, and L\. Wutschitz\(2021\)Numerical composition of differential privacy\.External Links:2106\.02848,[Link](https://arxiv.org/abs/2106.02848)Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[26\]L\. Gosch, X\. Chen, Y\. Scholten, and S\. Günnemann\(2026\)Certifying graph neural networks against label and structure poisoning\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1)\.
- \[27\]Z\. Hammoudeh and D\. Lowd\(2024\-03\)Provable robustness against a union ofL0L\_\{0\}adversarial attacks\.Proceedings of the AAAI Conference on Artificial Intelligence38\(19\),pp\. 21134–21142\.External Links:ISSN 2159\-5399Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1)\.
- \[28\]K\. He, X\. Zhang, S\. Ren, and J\. Sun\(2016\)Deep residual learning for image recognition\.InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p1.7)\.
- \[29\]J\. Jia, X\. Cao, and N\. Z\. Gong\(2020\)Intrinsic certified robustness of bagging against data poisoning attacks\.External Links:2008\.04495Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p2.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[30\]J\. Jia, Y\. Liu, X\. Cao, and N\. Z\. Gong\(2021\)Certified robustness of nearest neighbors against data poisoning and backdoor attacks\.External Links:2012\.03765Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[31\]P\. Kairouz, S\. Oh, and P\. Viswanath\(2015\)The composition theorem for differential privacy\.InInternational conference on machine learning,pp\. 1376–1385\.Cited by:[§3](https://arxiv.org/html/2605.21780#S3.p5.7)\.
- \[32\]G\. Katz, C\. Barrett, D\. L\. Dill, K\. Julian, and M\. J\. Kochenderfer\(2017\)Reluplex: an efficient smt solver for verifying deep neural networks\.InComputer Aided Verification,R\. Majumdar and V\. Kunčak \(Eds\.\),Cham,pp\. 97–117\.External Links:ISBN 978\-3\-319\-63387\-9Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[33\]A\. Koskela and A\. Honkela\(2021\)Computing differential privacy guarantees for heterogeneous compositions using fft\.External Links:2102\.12412,[Link](https://arxiv.org/abs/2102.12412)Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[34\]A\. Koskela, J\. Jälkö, and A\. Honkela\(2020\-26–28 Aug\)Computing tight differential privacy guarantees using fft\.InProceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics,S\. Chiappa and R\. Calandra \(Eds\.\),Proceedings of Machine Learning Research, Vol\.108,pp\. 2560–2569\.Cited by:[§4](https://arxiv.org/html/2605.21780#S4.SS0.SSS0.Px5.p1.8),[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[35\]A\. Koskela, J\. Jälkö, L\. Prediger, and A\. Honkela\(2021\)Tight differential privacy for discrete\-valued mechanisms and for the subsampled gaussian mechanism using fft\.External Links:2006\.07134,[Link](https://arxiv.org/abs/2006.07134)Cited by:[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[36\]A\. Krizhevsky and G\. Hinton\(2009\)Learning multiple layers of features from tiny images\.Technical reportUniversity of Toronto\.Cited by:[§6](https://arxiv.org/html/2605.21780#S6.p1.1)\.
- \[37\]Y\. LeCun, L\. Bottou, Y\. Bengio, and P\. Haffner\(1998\)Gradient\-based learning applied to document recognition\.Proceedings of the IEEE86\(11\),pp\. 2278–2324\.Cited by:[§6](https://arxiv.org/html/2605.21780#S6.p1.1)\.
- \[38\]M\. Lecuyer, V\. Atlidakis, R\. Geambasu, D\. Hsu, and S\. Jana\(2019\)Certified robustness to adversarial examples with differential privacy\.In2019 IEEE Symposium on Security and Privacy \(SP\),Vol\.,pp\. 656–672\.Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1),[§1](https://arxiv.org/html/2605.21780#S1.p3.3),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[39\]G\. Lee, Y\. Yuan, S\. Chang, and T\. S\. Jaakkola\(2020\)Tight certificates of adversarial robustness for randomly smoothed classifiers\.External Links:1906\.04948Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[40\]G\. Lee, Y\. Yuan, S\. Chang, and T\. Jaakkola\(2019\)Tight certificates of adversarial robustness for randomly smoothed classifiers\.InAdvances in Neural Information Processing Systems,H\. Wallach, H\. Larochelle, A\. Beygelzimer, F\. d'Alché\-Buc, E\. Fox, and R\. Garnett \(Eds\.\),Vol\.32,pp\.\.Cited by:[Appendix E](https://arxiv.org/html/2605.21780#A5.p1.3),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[41\]A\. Levine and S\. Feizi\(2021\)Deep partition aggregation: provable defenses against general poisoning attacks\.InInternational Conference on Learning Representations,Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p2.7),[§1](https://arxiv.org/html/2605.21780#S1.p2.1),[§1](https://arxiv.org/html/2605.21780#S1.p6.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1),[§5](https://arxiv.org/html/2605.21780#S5.SS0.SSS0.Px3.p1.1)\.
- \[42\]L\. Li, T\. Xie, and B\. Li\(2023\)Sok: certified robustness for deep neural networks\.In2023 IEEE symposium on security and privacy \(SP\),pp\. 1289–1310\.Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[43\]S\. Liu, A\. C\. Cullen, P\. Montague, S\. M\. Erfani, and B\. I\. P\. Rubinstein\(2023\)Enhancing the antidote: improved pointwise certifications against poisoning attacks\.InProceedings of the Thirty\-Seventh AAAI Conference on Artificial Intelligence and Thirty\-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence,AAAI’23/IAAI’23/EAAI’23\.External Links:ISBN 978\-1\-57735\-880\-0Cited by:[Appendix F](https://arxiv.org/html/2605.21780#A6.1.p1.3),[Appendix F](https://arxiv.org/html/2605.21780#A6.3.p3.3),[Appendix F](https://arxiv.org/html/2605.21780#A6.p1.12),[§1](https://arxiv.org/html/2605.21780#S1.p3.3),[§1](https://arxiv.org/html/2605.21780#S1.p6.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1),[§6\.1](https://arxiv.org/html/2605.21780#S6.SS1.p1.5),[§6](https://arxiv.org/html/2605.21780#S6.p1.1)\.
- \[44\]Y\. Liu, S\. Ma, Y\. Aafer, W\. Lee, J\. Zhai, W\. Wang, and X\. Zhang\(2018\)Trojaning attack on neural networks\.In25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18\-221, 2018,Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[45\]T\. Lorenz, M\. Kwiatkowska, and M\. Fritz\(2024\)FullCert: deterministic end\-to\-end certification for training and inference of neural networks\.External Links:2406\.11522Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[46\]S\. Lyu, S\. Shaikh, F\. Shpilevskiy, E\. Shelhamer, and M\. Lécuyer\(2024\)Adaptive randomized smoothing: certified adversarial robustness for multi\-step defences\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 134043–134074\.Cited by:[Appendix D](https://arxiv.org/html/2605.21780#A4.1.p1.7),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px1.p1.4),[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.p5.8),[Lemma E\.3](https://arxiv.org/html/2605.21780#A5.Thmtheorem3),[Appendix E](https://arxiv.org/html/2605.21780#A5.p1.3),[§1](https://arxiv.org/html/2605.21780#S1.p3.3),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p5.2),[§3](https://arxiv.org/html/2605.21780#S3.p9.7),[§4](https://arxiv.org/html/2605.21780#S4.SS0.SSS0.Px2.p1.13),[§4](https://arxiv.org/html/2605.21780#S4.SS0.SSS0.Px5.p1.8)\.
- \[47\]S\. Meiser and E\. Mohammadi\(2018\)Tight on budget?: tight bounds for r\-fold approximate differential privacy\.Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security\.External Links:[Link](https://api.semanticscholar.org/CorpusID:52504941)Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p5.2),[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[48\]M\. Naseri, J\. Hayes, and E\. D\. Cristofaro\(2022\)Local and central differential privacy for robustness and privacy in federated learning\.External Links:2009\.03561Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[49\]J\. Neyman and E\. S\. Pearson\(1933\)IX\. on the problem of the most efficient tests of statistical hypotheses\.Philosophical Transactions of the Royal Society of London\. Series A, Containing Papers of a Mathematical or Physical Character231\(694\-706\),pp\. 289–337\.Cited by:[Appendix E](https://arxiv.org/html/2605.21780#A5.SS0.SSS0.Px1.p2.7),[Lemma E\.2](https://arxiv.org/html/2605.21780#A5.Thmtheorem2)\.
- \[50\]A\. Paszke, S\. Gross, F\. Massa, A\. Lerer, J\. Bradbury,et al\.\(2019\)PyTorch: an imperative style, high\-performance deep learning library\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p1.7)\.
- \[51\]T\. Qiao, Y\. Wang, X\. Liu, S\. Wu, J\. Li, and Y\. Li\(2025\)Cert\-ssbd: certified backdoor defense with sample\-specific smoothing noises\.IEEE Transactions on Information Forensics and Security21,pp\. 2446–2461\.Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[52\]K\. Rezaei, K\. Banihashem, A\. Chegini, and S\. Feizi\(2023\)Run\-off election: improved provable defense against data poisoning attacks\.External Links:2302\.02300Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1)\.
- \[53\]A\. Riess, J\. F\. Gomez, F\. du Pin Calmon, J\. A\. Schnabel, and G\. Kaissis\(2026\)Optimal conversion from rényi differential privacy toff\-differential privacy\.External Links:2602\.04562Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p3.3)\.
- \[54\]E\. Rosenfeld, E\. Winston, P\. Ravikumar, and J\. Z\. Kolter\(2020\)Certified robustness to label\-flipping attacks via randomized smoothing\.External Links:2002\.03018Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1)\.
- \[55\]H\. Salman, J\. Li, I\. Razenshteyn, P\. Zhang, H\. Zhang, S\. Bubeck, and G\. Yang\(2019\)Provably robust deep learning via adversarially trained smoothed classifiers\.Advances in neural information processing systems32\.Cited by:[Appendix E](https://arxiv.org/html/2605.21780#A5.p2.4)\.
- \[56\]A\. Saxena, T\. Wollschläger, N\. Franco, J\. M\. Lorenz, and S\. Günnemann\(2024\)Certifiably robust encoding schemes\.External Links:2408\.01200Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[57\]Y\. Scholten and S\. Günnemann\(2025\)Provably reliable conformal prediction sets in the presence of data poisoning\.InICLR,Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1)\.
- \[58\]Y\. Scholten, J\. Schuchardt, A\. Bojchevski, and S\. Günnemann\(2023\)Hierarchical randomized smoothing\.InNeurIPS,Cited by:[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px3.p1.1)\.
- \[59\]Y\. Scholten, J\. Schuchardt, S\. Geisler, A\. Bojchevski, and S\. Günnemann\(2022\)Randomized message\-interception smoothing: gray\-box certificates for graph neural networks\.InNeurIPS,Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[60\]J\. Schuchardt, M\. Dalirrooyfard, J\. Guzelkabaagac, A\. Schneider, Y\. Nevmyvaka, and S\. Günnemann\(2025\)Privacy amplification by structured subsampling for deep differentially private time series forecasting\.External Links:2502\.02410,[Link](https://arxiv.org/abs/2502.02410)Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p5.2)\.
- \[61\]J\. Schuchardt, M\. Stoian, A\. Kosmala, and S\. Günnemann\(2024\)Unified mechanism\-specific amplification by subsampling and group privacy amplification\.External Links:2403\.04867Cited by:[Appendix D](https://arxiv.org/html/2605.21780#A4.5.p2.1),[§1](https://arxiv.org/html/2605.21780#S1.p5.2),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p5.2),[§4](https://arxiv.org/html/2605.21780#S4.SS0.SSS0.Px5.p1.8),[§5](https://arxiv.org/html/2605.21780#S5.SS0.SSS0.Px1.p1.19)\.
- \[62\]J\. Schuchardt\(2026\)Probabilistic gray\-box robustness certification for graph neural networks\.Ph\.D\. Thesis,Technische Universität München\.External Links:[Link](https://mediatum.ub.tum.de/node?id=1797198)Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p6.1)\.
- \[63\]L\. Schwinn, D\. Dobre, S\. Günnemann, and G\. Gidel\(2023\)Adversarial attacks and defenses in large language models: old and new threats\.External Links:2310\.19737Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[64\]E\. Shayegani, M\. A\. A\. Mamun, Y\. Fu, P\. Zaree, Y\. Dong, and N\. Abu\-Ghazaleh\(2023\)Survey of vulnerabilities in large language models revealed by adversarial attacks\.External Links:2310\.10844Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[65\]D\. Sommer, S\. Meiser, and E\. Mohammadi\(2018\)Privacy loss classes: the central limit theorem in differential privacy\.Cryptology ePrint Archive\.Cited by:[§4](https://arxiv.org/html/2605.21780#S4.SS0.SSS0.Px5.p1.8),[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.
- \[66\]P\. Sosnin, M\. N\. Mueller, M\. Baader, C\. Tsay, and M\. R\. Wicker\(2025\)Certified robustness to data poisoning in gradient\-based training\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[67\]S\. Sun, P\. Sen, and W\. Ruan\(2024\-11\)CROWD: certified robustness via weight distribution for smoothed classifiers against backdoor attack\.InFindings of the Association for Computational Linguistics: EMNLP 2024,Y\. Al\-Onaizan, M\. Bansal, and Y\. Chen \(Eds\.\),Miami, Florida, USA,pp\. 17056–17070\.Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[68\]C\. Szegedy, W\. Zaremba, I\. Sutskever, J\. Bruna, D\. Erhan, I\. Goodfellow, and R\. Fergus\(2014\)Intriguing properties of neural networks\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1)\.
- \[69\]J\. Teng, G\. Lee, and Y\. Yuan\(2020\)$\\ell\_1$ adversarial robustness certificates: a randomized smoothing approach\.External Links:[Link](https://openreview.net/forum?id=H1lQIgrFDS)Cited by:[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px2.p1.1)\.
- \[70\]B\. Wang, X\. Cao, J\. Jia, and N\. Z\. Gong\(2020\)On certifying robustness against backdoor attacks via randomized smoothing\.ArXivabs/2002\.11750\.Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[71\]W\. Wang, A\. Levine, and S\. Feizi\(2022\)Improved certified defenses against data poisoning with \(deterministic\) finite aggregation\.External Links:2202\.02628Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p3.1)\.
- \[72\]L\. Wasserman and S\. Zhou\(2010\)A statistical framework for differential privacy\.Journal of the American Statistical Association105\(489\),pp\. 375–389\.Cited by:[§3](https://arxiv.org/html/2605.21780#S3.p5.7)\.
- \[73\]M\. Weber, X\. Xu, B\. Karlaš, C\. Zhang, and B\. Li\(2023\)RAB: provable robustness against backdoor attacks\.In2023 IEEE Symposium on Security and Privacy \(SP\),Vol\.,pp\. 1311–1328\.Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p2.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[74\]C\. Xie, Y\. Long, P\. Chen, Q\. Li, A\. Nourian, S\. Koyejo, and B\. Li\(2023\)Unraveling the connections between privacy and certified robustness in federated learning against poisoning attacks\.External Links:2209\.04030Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p3.3),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p4.1)\.
- \[75\]G\. Yang, T\. Duan, J\. E\. Hu, H\. Salman, I\. Razenshteyn, and J\. Li\(2020\)Randomized smoothing of all shapes and sizes\.External Links:2002\.08118,[Link](https://arxiv.org/abs/2002.08118)Cited by:[§D\.2](https://arxiv.org/html/2605.21780#A4.SS2.SSS0.Px2.p1.1)\.
- \[76\]A\. Yousefpour, I\. Shilov, A\. Sablayrolles, D\. Testuggine, K\. Prasad, M\. Malek, J\. Nguyen, S\. Ghosh, A\. Bharadwaj, J\. Zhao, G\. Cormode, and I\. Mironov\(2021\)Opacus: User\-friendly differential privacy library in PyTorch\.arXiv preprint arXiv:2109\.12298\.Cited by:[Appendix B](https://arxiv.org/html/2605.21780#A2.SS0.SSS0.Px1.p1.7)\.
- \[77\]R\. Zhai, C\. Dan, D\. He, H\. Zhang, B\. Gong, P\. Ravikumar, C\. Hsieh, and L\. Wang\(2020\)Macer: attack\-free and scalable robust training via maximizing certified radius\.arXiv preprint arXiv:2001\.02378\.Cited by:[Appendix E](https://arxiv.org/html/2605.21780#A5.p2.4)\.
- \[78\]D\. Zhang, M\. Ye, C\. Gong, Z\. Zhu, and Q\. Liu\(2020\)Black\-box certification with randomized smoothing: a functional optimization based framework\.External Links:2002\.09169,[Link](https://arxiv.org/abs/2002.09169)Cited by:[Appendix E](https://arxiv.org/html/2605.21780#A5.SS0.SSS0.Px1.p1.3),[§1](https://arxiv.org/html/2605.21780#S1.p1.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p6.1)\.
- \[79\]Y\. Zhang, A\. Albarghouthi, and L\. D’antoni\(2022\)BagFlip: a certified defense against data poisoning\.ArXivabs/2205\.13634\.Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p1.1),[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[80\]Y\. Zhang, A\. Albarghouthi, and L\. D’antoni\(2023\)PECAN: a deterministic certified defense against backdoor attacks\.ArXivabs/2301\.11824\.Cited by:[§2](https://arxiv.org/html/2605.21780#S2.SS0.SSS0.Px1.p1.1)\.
- \[81\]Y\. Zhu, J\. Dong, and Y\. Wang\(2021\)Optimal accounting of differential privacy via characteristic function\.CoRRabs/2106\.08567\.External Links:[Link](https://arxiv.org/abs/2106.08567),2106\.08567Cited by:[§1](https://arxiv.org/html/2605.21780#S1.p3.3),[§5](https://arxiv.org/html/2605.21780#S5.p1.1)\.

## Appendix ABroader impacts

This work advances theoretical foundations for certifying robustness against backdoor attacks in machine learning systems\. By establishing provable guarantees against joint training\-time poisoning and inference\-time perturbations, our framework enables safer deployment of ML models in security\-critical applications\. While provable robustness may reduce model accuracy or increase computational costs, we believe these trade\-offs can be mitigated long\-term\. Overall, our work contributes to the development of more secure and trustworthy AI systems in the long\-term\.

## Appendix BExperimental details

#### Models and Training\.

For both DPA\- and DP\-SGD\-based training, we use a ResNet18\[[28](https://arxiv.org/html/2605.21780#bib.bib31)\]pretrained on ImageNet1K\[[11](https://arxiv.org/html/2605.21780#bib.bib32)\]and available in PyTorch\[[50](https://arxiv.org/html/2605.21780#bib.bib33)\]\. We used Opacus\[[76](https://arxiv.org/html/2605.21780#bib.bib90)\]for private training\. To use the same pretrained model on MNIST, we replicate the single channel across three channels\. To improve the utility of DP\-SGD\-trained models, we adopt the data\-augmentation strategy with multiplicity5050proposed byDeet al\.\[[10](https://arxiv.org/html/2605.21780#bib.bib29)\]\. For all DP\-SGD training, we use Gaussian noise withσ=3\\sigma=3, clipping norm11, and batch size128128, and correspondingly to sub\-sampling rates \(γ\\gamma\) of12850000\\frac\{128\}\{50000\}for CIFAR\-10 and12860000\\frac\{128\}\{60000\}for MNIST\. We do not replace the BatchNorm layer with alternatives commonly used in the differential privacy literature, such as GroupNorm\. Instead, we freeze the BatchNorm layers so that normalization uses the statistics obtained during pre\-training\. This approach correctly accounts for privacy while preserving utility\. In our experiments, it significantly outperforms GroupNorm in terms of model accuracy\. All models are trained on a single NVIDIA A100 GPU\. We compute a probabilistic lower/upper bound on class probabilities using Clopper\-Pearson intervals for Binomials as done inCohenet al\.\[[9](https://arxiv.org/html/2605.21780#bib.bib43)\]\.

DPA training details\.We train ResNet18 using Adam with a learning rate of0\.010\.01, momentum0\.90\.9, and weight decay5×10−45\\times 10^\{\-4\}\. The training batch size is128128, while the inference batch size is300300\. Models are trained for a maximum of400400epochs with early stopping after100100epochs without improvement on the training accuracy\. We use a cosine learning rate scheduler and initialize models from pretrained weights\. During training the individual classifiers, we add the same amount of Gaussian noise to the images that we use to smooth the classifier at inference\. The training procedure itself is deterministic and follows the instructions described in\[[41](https://arxiv.org/html/2605.21780#bib.bib59)\]\.

## Appendix CEquivalence offf\-DP and Privacy Profiles

In this section, we describe the equivalence between the primal \(ff\-DP\) and dual \(privacy profile\) formulations of differential privacy\. We adopt a hypothesis testing viewpoint, which makes the shared geometric structure of the two formulations explicit\.

#### Hypothesis Testing Viewpoint\.

LetPPandQQbe probability distributions on a space𝒴\\mathcal\{Y\}\. A \(possibly randomized\) hypothesis test

H:𝒴→\{0,1\}H:\\mathcal\{Y\}\\to\\\{0,1\\\}aims to distinguish whether a sampley∈𝒴y\\in\\mathcal\{Y\}is drawn fromPPorQQ\. We interpretH​\(y\)=1H\(y\)=1as decidingQQ, andH​\(y\)=0H\(y\)=0as decidingPP\.

The performance of a testHHis characterized by its*Type I*and*Type II*errors:

α​\(H\):=ℙy∼P​\[H​\(y\)=1\],β​\(H\):=ℙy∼Q​\[H​\(y\)=0\]\.\\alpha\(H\):=\\mathbb\{P\}\_\{y\\sim P\}\[H\(y\)=1\],\\qquad\\beta\(H\):=\\mathbb\{P\}\_\{y\\sim Q\}\[H\(y\)=0\]\.

#### The Error Region\.

AsHHranges over all hypothesis tests, the set of achievable error pairs

ℰ​\(P,Q\):=\{\(α​\(H\),β​\(H\)\):H​is a hypothesis test\}⊆\[0,1\]2\\mathcal\{E\}\(P,Q\)\\;:=\\;\\bigl\\\{\(\\alpha\(H\),\\beta\(H\)\):H\\text\{ is a hypothesis test\}\\bigr\\\}\\subseteq\[0,1\]^\{2\}forms a convex subset of the unit square\. This follows because any convex combination of Type I and Type II error pairs can be realized by a corresponding convex combination of hypothesis tests, which is itself a valid hypothesis test\.

#### Two Equivalent Descriptions\.

The regionℰ​\(P,Q\)\\mathcal\{E\}\(P,Q\)admits two equivalent descriptions\.

- •*Primal \(boundary\) description\.*The lower boundary ofℰ​\(P,Q\)\\mathcal\{E\}\(P,Q\)gives the smallest achievable Type II error for each Type I error\. This defines the*tradeoff function* Λ​\(P∥Q\)​\(α\)=infH:α​\(H\)=αβ​\(H\),\\Lambda\(P\\,\\\|\\,Q\)\(\\alpha\)\\;=\\;\\inf\_\{H:\\,\\alpha\(H\)=\\alpha\}\\beta\(H\),which underliesff\-differential privacy\.
- •*Dual \(supporting hyperplane\) description\.*Alternatively,ℰ​\(P,Q\)\\mathcal\{E\}\(P,Q\)can be characterized via the supporting hyperplanes of its lower boundary\. In particular, for a slope−eϵ\-e^\{\\epsilon\}, the supporting hyperplane has intercept 1−δ​\(ϵ\)=−f∗​\(−eϵ\),1\-\\delta\(\\epsilon\)=\-f^\{\*\}\(\-e^\{\\epsilon\}\),wheref∗f^\{\*\}denotes the convex conjugate of the tradeoff functionff\. As shown in\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\], this characterization coincides with the privacy profile when the neighboring relation is*symmetric*\.

In this work, we relax this assumption and extend this perspective to general*asymmetric*neighboring relations\. We first define the notion of optimal tradeoff function for a given mechanismℳ\\mathcal\{M\}with respect to a neighboring relation∼\\sim\. Following, we show that it’s an equivalent description of privacy to the privacy profile ofℳ\\mathcal\{M\}for the opposite relation∼o​p\\sim\_\{op\}defined byX∼opX′X\\sim\_\{\\mathrm\{op\}\}X^\{\\prime\}if and only ifX′∼XX^\{\\prime\}\\sim X\. Alternatively, the privacy profile of the mechanismℳ\\mathcal\{M\}for∼\\simis related tof−1f^\{\-1\}, via convex conjugation\. Heref−1f^\{\-1\}is left\-continuous inverse of a non\-increasing functionff,

f−1​\(α\):=inf\{t∈\[0,1\]:f​\(t\)≤α\},f^\{\-1\}\(\\alpha\):=\\inf\\bigl\\\{t\\in\[0,1\]:f\(t\)\\leq\\alpha\\bigr\\\},\(2\)
Finally, we show that if the underlying neighboring relation∼\\simis symmetric, the conversion betweenf−f\-DP and privacy profile reduces to the one presented in theDonget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]\. We restate this equivalence as Corollary[C\.12](https://arxiv.org/html/2605.21780#A3.Thmtheorem12)\.

#### Optimal Tradeoff Function:

Letℱ\\mathcal\{F\}be the space of tradeoff functions, i\.e\., by Proposition2\.22\.2in\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\],

ℱ:=\{f:\[0,1\]→\[0,1\]\|f​is convex, continuous, non\-increasing, and​f​\(x\)≤1−x\}\\mathcal\{F\}:=\\\{f:\[0,1\]\\to\[0,1\]\\;\|\\;f\\text\{ is convex, continuous, non\-increasing, and \}f\(x\)\\leq 1\-x\\\}
###### Definition C\.1\.

\(Optimal Tradeoff Function\) Given a mechanismℳ\\mathcal\{M\}, and neighboring relation∼\\sim, we say thatf∈ℱf\\in\\mathcal\{F\}is the optimal tradeoff function ifℳ\\mathcal\{M\}isf−f\-DP w\.r\.t\.,∼\\sim, and for anyf∈′ℱf\{\{\}^\{\\prime\}\}\\in\\mathcal\{F\}ifℳ\\mathcal\{M\}isf′−f^\{\{\}^\{\\prime\}\}\-DP w\.r\.t\.,∼\\sim, thenf′≤ff^\{\{\}^\{\\prime\}\}\\leq f\.

We characterize the optimal tradeoff function via Theorem[C\.8](https://arxiv.org/html/2605.21780#A3.Thmtheorem8)and finally establish its connection to privacy profile in Theorem[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3)\. We first state the supporting lemmas needed to prove the main results, then state and prove the main results, and finally prove the supporting lemmas\.

### C\.1Auxiliary Lemmas

#### Convention:

For all the results that follow, whenever we writef∗f^\{\*\}, orf∗∗f^\{\*\*\}, it is implicitly implied that the convex conjugation is applied to the∞−\\infty\-extension of the functionff\.

###### Lemma C\.2\.

Let𝕏⊆ℝ\\mathbb\{X\}\\subseteq\\mathbb\{R\}andf:𝕏→ℝf:\\mathbb\{X\}\\to\\mathbb\{R\}\. Define the property\(𝒫𝕏\)\(\\mathcal\{P\}\_\{\\mathbb\{X\}\}\)for a setA⊆𝕏×ℝA\\subseteq\\mathbb\{X\}\\times\\mathbb\{R\}by

\(𝒫𝕏\)∀\(x,t\)∈A,∀x^∈𝕏withx^≥x:\(x^,t\)∈A\.\(\\mathcal\{P\}\_\{\\mathbb\{X\}\}\)\\qquad\\forall\(x,t\)\\in A,\\ \\forall\\hat\{x\}\\in\\mathbb\{X\}\\text\{ with \}\\hat\{x\}\\geq x:\\ \(\\hat\{x\},t\)\\in A\.\(3\)Thenffis monotonically non\-increasing if and only ifepi⁡\(f\)\\operatorname\{epi\}\(f\)satisfies\(𝒫𝕏\)\(\\mathcal\{P\}\_\{\\mathbb\{X\}\}\)\.

###### Lemma C\.3\.

Let𝕏⊆ℝ\\mathbb\{X\}\\subseteq\\mathbb\{R\}be a closed interval and letf:𝕏→ℝf:\\mathbb\{X\}\\to\\mathbb\{R\}\. Ifepi⁡\(f\)\\operatorname\{epi\}\(f\)satisfies\(𝒫𝕏\)\(\\mathcal\{P\}\_\{\\mathbb\{X\}\}\), thencl⁡\(conv⁡\(epi⁡\(f\)\)\)\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(f\)\)\)also satisfies\(𝒫𝕏\)\(\\mathcal\{P\}\_\{\\mathbb\{X\}\}\)\.

###### Lemma C\.4\.

Let𝕏⊆ℝ\\mathbb\{X\}\\subseteq\\mathbb\{R\}be a closed interval and letf:𝕏→ℝf:\\mathbb\{X\}\\to\\mathbb\{R\}be monotonically non\-increasing\. Consider the biconjugate of the\+∞\+\\infty\-extension offftoℝ\\mathbb\{R\}, and denote its restriction to𝕏\\mathbb\{X\}byf∗∗∣𝕏f^\{\*\*\}\\\!\\mid\_\{\\mathbb\{X\}\}\. Thenf∗∗∣𝕏:𝕏→ℝf^\{\*\*\}\\\!\\mid\_\{\\mathbb\{X\}\}:\\mathbb\{X\}\\to\\mathbb\{R\}is monotonically non\-increasing\.

###### Lemma C\.5\.

LetPPandQQbe distributions onYY, andℋ\\mathcal\{H\}be the space of randomized hypothesis tests onYY\. Then the HS divergence betweenPPandQQcan be written as the following supremum overℋ\\mathcal\{H\}\.

DαHS=supϕ∈ℋ\(𝔼P​\(ϕ\)−eε​𝔼Q​\(ϕ\)\)D\_\{\\alpha\}^\{\\text\{HS\}\}=\\sup\_\{\\phi\\in\\mathcal\{H\}\}\\bigl\(\\mathbb\{E\}\_\{P\}\(\\phi\)\-e^\{\\varepsilon\}\\mathbb\{E\}\_\{Q\}\(\\phi\)\\bigr\)

###### Lemma C\.6\.

Letff,ggbe two tradeoff functions, i\.e\.,f,g∈ℱf,g\\in\\mathcal\{F\}, such thatf≤gf\\leq g\. Then the left continuous inverse of a non\-increasing function preserves this order, i\.e\.,

###### Lemma C\.7\.

Letf:ℝ→ℝ¯f:\\mathbb\{R\}\\to\\overline\{\\mathbb\{R\}\}be a proper function with a global lower boundLL, i\.e\.,−∞<L≤f\-\\infty<L\\leq f\. Then, its biconjugate also hasLLas a global lower bound, i\.e\.,L≤f∗∗L\\leq f^\{\*\*\}\.

### C\.2Optimal Tradeoff Function And Primal\-Dual Conversion

###### Theorem C\.8\.

The optimal tradeoff function for a mechanismℳ\\mathcal\{M\}w\.r\.t\. a relation∼\\simcan be expressed as the convex bi\-conjugate of the\+∞−\+\\infty\-extension of the pointwise infimum of the tradeoff functions over all neighboring pairs, restricted to\[0,1\]\[0,1\]\.

f=\(infX∼X′Λ​\(ℳ​\(X\)∥ℳ​\(X′\)\)\)∗∗\|\[0,1\]f=\\left\(\\inf\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\)\\right\)^\{\*\*\}\\bigg\|\_\{\[0,1\]\}\(4\)

###### Proof\.

We first show thatffin equation[4](https://arxiv.org/html/2605.21780#A3.E4)is a tradeoff function\. Definef^\\hat\{f\}as,

f^:=infX∼X′Λ​\(ℳ​\(X\)∥ℳ​\(X′\)\)\\hat\{f\}:=\\inf\_\{X\\sim X^\{\\prime\}\}\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\\prime\}\)\)\. This impliesf=f^∗∗\|\[0,1\]f=\\hat\{f\}^\{\*\*\}\|\_\{\[0,1\]\}\. Since\[0,1\]\[0,1\]is convex and closed,cl⁡\(conv⁡\(epi⁡\(f^\)\)\)⊆X×ℝ\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(\\hat\{f\}\)\)\)\\subseteq X\\times\\mathbb\{R\}, hencef^∗∗​\(x\)=\+∞\\hat\{f\}^\{\*\*\}\(x\)=\+\\inftyforx∉Xx\\notin X\. From now on, whenever we writef^∗∗\\hat\{f\}^\{\*\*\}, it is inherently implied that its domain is restricted to where it is finite, i\.e\.,\[0,1\]\[0,1\]\.

\(Convex\) Holds trivially, asffis a convex conjugate off^∗\\hat\{f\}^\{\*\}\.

\(Monotonically non\-increasing\) For every pairX∼X′X\\sim X^\{\{\}^\{\\prime\}\}, the tradeoff functionΛ​\(ℳ​\(X\)∥ℳ​\(X′\)\)\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\)is monotonically non\-increasing and takinginf\\infpreserves that, makingf^\\hat\{f\}monotonically non\-increasing\. Thus by Lemma[C\.4](https://arxiv.org/html/2605.21780#A3.Thmtheorem4),f=f^∗∗f=\\hat\{f\}^\{\*\*\}is also monotonically non\-increasing\.

\(Less than1−α1\-\\alpha\) The tradeoff function corresponding to every pairX∼X′X\\sim X^\{\{\}^\{\\prime\}\}has an upper bound1−α1\-\\alpha\. Therefore,f=f^∗∗≤f^≤Λ​\(ℳ​\(X\)∥ℳ​\(X′\)\)≤1−αf=\\hat\{f\}^\{\*\*\}\\leq\\hat\{f\}\\leq\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\)\\leq 1\-\\alpha\.

\(Greater than0\) Since for every neighboring pair the tradeoff function is non\-negative, it implies thatf^≥0\\hat\{f\}\\geq 0\. Therefore, using Lemma[C\.7](https://arxiv.org/html/2605.21780#A3.Thmtheorem7),f=f^∗∗≥0f=\\hat\{f\}^\{\*\*\}\\geq 0\.

\(Continuous\) Sinceffis convex, it is continuous in the interior\(0,1\)\(0,1\)and at11, since0≤f​\(α\)≤1−α0\\leq f\(\\alpha\)\\leq 1\-\\alpha\. Moreover, since it’s the bi\-conjugate off^\\hat\{f\}, it is lower semi\-continuous\. Further,ffis bounded above and convex, therefore it is upper semi\-continuous at0, implying continuity at0\.

Thus,ffis a valid tradeoff function\. Now we show that it is also optimal in the sense of Definition[4\.2](https://arxiv.org/html/2605.21780#S4.Thmtheorem2)\.

Sincef≤f^≤Λ\(ℳ\(X\)∥ℳ\(X′\)f\\leq\\hat\{f\}\\leq\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\), for all neighboring pairsX∼X′X\\sim X^\{\{\}^\{\\prime\}\},ℳ\\mathcal\{M\}isf−f\-DP w\.r\.t\. the relation∼\\sim\. Assume that there exist a tradeoff functionf′∈ℱf^\{\{\}^\{\\prime\}\}\\in\\mathcal\{F\}, such thatℳ\\mathcal\{M\}isf′−f^\{\{\}^\{\\prime\}\}\-DP w\.r\.t\.∼\\sim\. Clearly,f′≤Λ\(ℳ\(X\)∥ℳ\(X′\)f^\{\{\}^\{\\prime\}\}\\leq\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\), implying thatf′≤f^f^\{\{\}^\{\\prime\}\}\\leq\\hat\{f\}, sincef^\\hat\{f\}is the point\-wiseinf\\inf\. Therefore,f′≤ff^\{\{\}^\{\\prime\}\}\\leq f, sinceffis the largest convex lower semi\-continuous function smaller thanf^\\hat\{f\}\. Thus showing thatffis the optimal tradeoff function for the mechanismℳ\\mathcal\{M\}, w\.r\.t\., the neighboring relation∼\\sim\. ∎

###### Lemma C\.9\.

Given a mechanismℳ\\mathcal\{M\}, a neighboring relation∼\\sim, and its opposite relation∼o​p\\sim^\{op\}, defined asX∼X′X\\sim X^\{\{\}^\{\\prime\}\}if and only ifX′∼o​pXX^\{\{\}^\{\\prime\}\}\\sim^\{op\}X\. Letffandfo​pf^\{op\}be the optimal tradeoff functions corresponding to the relations∼\\simand∼o​p\\sim^\{op\}, respectively\. Thenfo​pf^\{op\}is the left continuous inverse of the non\-increasing functionff, i\.e\.,

###### Proof\.

Sincefo​pf^\{op\}is a tradeoff function, there exist some distributionsPPandQQon some space𝕐\\mathbb\{Y\}, such thatfo​p=Λ​\(P∥Q\)f^\{op\}=\\Lambda\(P\\,\\\|\\,Q\)\. For allX∼o​pX′X\\sim^\{op\}X^\{\{\}^\{\\prime\}\},Λ​\(P∥Q\)≤Λ​\(ℳ​\(X\)∥ℳ​\(X′\)\)\\Lambda\(P\\,\\\|\\,Q\)\\leq\\Lambda\(\\mathcal\{M\}\(X\)\\,\\\|\\,\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\)with distributionsℳ​\(X\)\\mathcal\{M\}\(X\), andℳ​\(X′\)\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)defined onℤ\\mathbb\{Z\}\. Using Theorem2\.102\.10inDonget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\], there exist a randomized map𝒜:𝕐→ℤ\\operatorname\{\\mathcal\{A\}\}:\\mathbb\{Y\}\\to\\mathbb\{Z\}, such thatℳ​\(X\)=𝒜​\(P\)\\mathcal\{M\}\(X\)=\\mathcal\{A\}\(P\), andℳ​\(X′\)=𝒜​\(Q\)\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)=\\mathcal\{A\}\(Q\)\.

We now write\(fo​p\)−1=Λ​\(Q,P\)≤Λ​\(ℳ​\(X′\)∥ℳ​\(X\)\)\(f^\{op\}\)^\{\-1\}=\\Lambda\(Q,P\)\\leq\\Lambda\(\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\\,\\\|\\,\\mathcal\{M\}\(X\)\), due to post\-processing inequality\. Since this holds for allX′∼XX^\{\{\}^\{\\prime\}\}\\sim X, we get\(fo​p\)−1≤f\(f^\{op\}\)^\{\-1\}\\leq f\. Using the same set of arguments starting withff, leads tof−1≤fo​pf^\{\-1\}\\leq f^\{op\}\. Further, using Lemma[C\.6](https://arxiv.org/html/2605.21780#A3.Thmtheorem6)givesf≤\(fo​p\)−1f\\leq\(f^\{op\}\)^\{\-1\}\. Thus showingf=\(fo​p\)−1f=\(f^\{op\}\)^\{\-1\}, orfo​p=f−1f^\{op\}=f^\{\-1\}\. ∎

###### Theorem C\.10\.

Letℳ\\mathcal\{M\}be a randomized mechanism with the optimal tradeoff functionff, and privacy profileδ\\delta, for the neighboring relation∼\\sim\. The following \(equivalent\) conversions hold,

- •\(Primal to Dual\) δ​\(ϵ\)=1\+\(f−1\)∗​\(−eϵ\)\\delta\(\\epsilon\)=1\+\(f^\{\-1\}\)^\{\*\}\(\-e^\{\\epsilon\}\)
- •\(Dual to Primal\) f​\(α\)=supϵ∈ℝe−ϵ​\(1−δ​\(ϵ\)−α\)\\displaystyle f\(\\alpha\)=\\sup\_\{\\epsilon\\in\\mathbb\{R\}\}e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\)

###### Proof\.

- •\(Primal to Dual\) LetX∼X′X\\sim X^\{\{\}^\{\\prime\}\}, denoteP:=ℳ​\(X\)P:=\\mathcal\{M\}\(X\), andQ:=ℳ​\(X′\)Q:=\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\. Further letℋ\\mathcal\{H\}be the space of randomized hypothesis tests, i\.e\.,ϕ∈ℋ\\phi\\in\\mathcal\{H\}mapping to\[0,1\]\[0,1\] δ​\(ε\)\\displaystyle\\delta\(\\varepsilon\)=supX∼X′supA\(P​\(A\)−eε​Q​\(A\)\)\\displaystyle=\\sup\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}\\sup\_\{A\}\\bigl\(P\(A\)\-e^\{\\varepsilon\}Q\(A\)\\bigr\)=supX∼X′supϕ∈ℋ\(𝔼P​\(ϕ\)−eε​𝔼Q​\(ϕ\)\)\(using Lemma[C\.5](https://arxiv.org/html/2605.21780#A3.Thmtheorem5)\)\\displaystyle=\\sup\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}\\sup\_\{\\phi\\in\\mathcal\{H\}\}\\bigl\(\\mathbb\{E\}\_\{P\}\(\\phi\)\-e^\{\\varepsilon\}\\mathbb\{E\}\_\{Q\}\(\\phi\)\\bigr\)\\qquad\\text\{\(using Lemma \\ref\{lemma:HS\-Div\-via\-HT\} \)\}=supX∼X′supα∈\[0,1\]\(sup𝔼Q​\[ϕ\]=α𝔼P​\[ϕ\]−eε​α\)\\displaystyle=\\sup\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}\\sup\_\{\\alpha\\in\[0,1\]\}\\left\(\\sup\_\{\\mathbb\{E\}\_\{Q\}\[\\phi\]=\\alpha\}\\mathbb\{E\}\_\{P\}\[\\phi\]\-e^\{\\varepsilon\}\\alpha\\right\)=1\+supα∈\[0,1\]\(−infX∼X′Λ\(Q\|\|P\)\(α\)−eεα\)\\displaystyle=1\+\\sup\_\{\\alpha\\in\[0,1\]\}\\left\(\-\\inf\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}\\Lambda\(Q\|\|P\)\(\\alpha\)\-e^\{\\varepsilon\}\\alpha\\right\)=1\+supα∈\[0,1\]\(−eεα−infX′∼o​pXΛ\(Q\|\|P\)\(α\)\)\\displaystyle=1\+\\sup\_\{\\alpha\\in\[0,1\]\}\\left\(\-e^\{\\varepsilon\}\\alpha\-\\inf\_\{X^\{\\prime\}\\sim^\{op\}X\}\\Lambda\(Q\|\|P\)\(\\alpha\)\\right\)=1\+\(infX′∼o​pXΛ\(Q\|\|P\)\)∗\(−eε\)\\displaystyle=1\+\(\\inf\_\{X^\{\\prime\}\\sim^\{op\}X\}\\Lambda\(Q\|\|P\)\)^\{\*\}\(\-e^\{\\varepsilon\}\)=1\+\(\(infX′∼o​pXΛ\(Q\|\|P\)\)∗∗\)∗\(−eε\)\\displaystyle=1\+\(\(\\inf\_\{X^\{\\prime\}\\sim^\{op\}X\}\\Lambda\(Q\|\|P\)\)^\{\*\*\}\)^\{\*\}\(\-e^\{\\varepsilon\}\)=1\+\(fo​p\)∗​\(−eε\)\\displaystyle=1\+\(f^\{op\}\)^\{\*\}\(\-e^\{\\varepsilon\}\)=1\+\(f−1\)∗​\(−eε\)\(using Lemma[C\.9](https://arxiv.org/html/2605.21780#A3.Thmtheorem9)\)\\displaystyle=1\+\(f^\{\-1\}\)^\{\*\}\(\-e^\{\\varepsilon\}\)\\qquad\\text\{\(using Lemma \\ref\{lemma:relating\_f\_to\_f\_inv\}\)\} which proves the claim\.
- •\(Dual to Primal\) Writeffas inverse off−1f^\{\-1\}, forα\>0\\alpha\>0 f​\(α\)\\displaystyle f\(\\alpha\)=infy∈\[0,1\]ys\.t\.f−1​\(y\)−α≤0\\displaystyle=\\inf\_\{y\\in\[0,1\]\}y\\qquad\\text\{s\.t\.\}\\qquad f^\{\-1\}\(y\)\-\\alpha\\leq 0=supλ≥0infy∈\[0,1\]y\+λ​f−1​\(y\)−λ​α\(forα\>0,f−1​\(1\)−α<0; strong duality holds\)\\displaystyle=\\sup\_\{\\lambda\\geq 0\}\\inf\_\{y\\in\[0,1\]\}y\+\\lambda f^\{\-1\}\(y\)\-\\lambda\\alpha\\qquad\\text\{\(for $\\alpha\>0$, $f^\{\-1\}\(1\)\-\\alpha<0$; strong duality holds\)\}=supλ\>0infy∈\[0,1\]y\+λ​f−1​\(y\)−λ​α\(since forλ=0;infy∈\[0,1\]y=0\)\\displaystyle=\\sup\_\{\\lambda\>0\}\\inf\_\{y\\in\[0,1\]\}y\+\\lambda f^\{\-1\}\(y\)\-\\lambda\\alpha\\qquad\\text\{\(since for $\\lambda=0$; $\\inf\_\{y\\in\[0,1\]\}y=0$\)\}=supλ\>0−λ​\(supy∈\[0,1\]y​\(−1λ\)−f−1​\(y\)\)−λ​α\\displaystyle=\\sup\_\{\\lambda\>0\}\-\\lambda\(\\sup\_\{y\\in\[0,1\]\}y\(\\frac\{\-1\}\{\\lambda\}\)\-f^\{\-1\}\(y\)\)\-\\lambda\\alpha=supε∈ℝe−ε​\(−\(f−1\)∗​\(−eε\)−α\)\\displaystyle=\\sup\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(\-\(f^\{\-1\}\)^\{\*\}\(\-e^\{\\varepsilon\}\)\-\\alpha\)=supε∈ℝe−ε​\(1−δ​\(ε\)−α\)\(Using Primal to Dual connection\)\\displaystyle=\\sup\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(1\-\\delta\(\\varepsilon\)\-\\alpha\)\\qquad\\text\{\(Using Primal to Dual connection\)\} Denotef^​\(α\)=supϵ∈ℝe−ε​\(1−δ​\(ε\)−α\)\\hat\{f\}\(\\alpha\)=\\sup\_\{\\epsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(1\-\\delta\(\\varepsilon\)\-\\alpha\)\. To show that the above equality holds atα=0\\alpha=0, i\.e\.,f​\(0\)=f^​\(0\)f\(0\)=\\hat\{f\}\(0\)we use the continuity argument as follows\. Firstly, f​\(0\)\\displaystyle f\(0\)=f​\(limn→∞1n\)\\displaystyle=f\(\\lim\_\{n\\to\\infty\}\\frac\{1\}\{n\}\)=limn→∞f​\(1n\)\(fis continuous\)\\displaystyle=\\lim\_\{n\\to\\infty\}f\(\\frac\{1\}\{n\}\)\\qquad\\text\{\($f$ is continuous\)\}=limn→∞f^​\(1n\)\(for positiveα,f​\(α\)=f^​\(α\)\)\\displaystyle=\\lim\_\{n\\to\\infty\}\\hat\{f\}\(\\frac\{1\}\{n\}\)\\qquad\\text\{\(for positive $\\alpha$, $f\(\\alpha\)=\\hat\{f\}\(\\alpha\)$\)\}≥limn→∞e−ε​\(1−δ​\(ε\)−1n\)\(for allε∈ℝ\)\\displaystyle\\geq\\lim\_\{n\\to\\infty\}e^\{\-\\varepsilon\}\(1\-\\delta\(\\varepsilon\)\-\\frac\{1\}\{n\}\)\\qquad\\text\{\(for all $\\varepsilon\\in\\mathbb\{R\}$\)\}=e−ε​\(1−δ​\(ε\)\)\(for allε∈ℝ\)\\displaystyle=e^\{\-\\varepsilon\}\(1\-\\delta\(\\varepsilon\)\)\\qquad\\text\{\(for all $\\varepsilon\\in\\mathbb\{R\}$\)\}Takingsup\\supon both sides gives, f​\(0\)≥f^​\(0\)f\(0\)\\geq\\hat\{f\}\(0\) Now, to show the other side of the inequality, observe thatf^\\hat\{f\}is non\-increasing, sincesup\\suppreserves inequalities\. Therefore,f^​\(1n\)≤f^​\(0\)\\hat\{f\}\(\\frac\{1\}\{n\}\)\\leq\\hat\{f\}\(0\), and f​\(0\)=limn→∞f^​\(1n\)≤limn→∞f^​\(0\)=f^​\(0\)f\(0\)=\\lim\_\{n\\to\\infty\}\\hat\{f\}\(\\frac\{1\}\{n\}\)\\leq\\lim\_\{n\\to\\infty\}\\hat\{f\}\(0\)=\\hat\{f\}\(0\) This finally proves the dual\-to\-primal conversion\.

∎

#### Asymmetric to Symmetric Case

The primal\-dual relationship presented in Theorem[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3)holds even for the symmetric case\. It’s immediately evident in the primal\-to\-dual conversion asf−1=ff^\{\-1\}=f, if the underlying relation∼\\simis symmetric\. For the dual\-to\-primal case, we relate the privacy profiles of the opposite relations\.

###### Lemma C\.11\.

Let∼o​p\\sim\_\{op\}be defined as,X∼o​pX′⇔X′∼XX\\sim\_\{op\}X^\{\{\}^\{\\prime\}\}\\;\\iff\\;X^\{\{\}^\{\\prime\}\}\\sim X, andδo​p​\(ϵ\),δ​\(ϵ\)\\delta^\{op\}\(\\epsilon\),\\delta\(\\epsilon\), be the the privacy profiles corresponding to∼o​p,∼\\sim\_\{op\},\\sim, respectively\.

δo​p​\(ϵ\)=1−eϵ​\(1−δ​\(−ϵ\)\)\\delta^\{op\}\(\\epsilon\)=1\-e^\{\\epsilon\}\(1\-\\delta\(\-\\epsilon\)\)

###### Proof\.

For every pair of distributions denoted asP=ℳ​\(X\),Q=ℳ​\(X′\)P=\\mathcal\{M\}\(X\),Q=\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\), define the region

ℛP,Q​\(ϵ\):=\{y:d​Pd​Q​\(y\)\>eϵ\}\\mathcal\{R\}\_\{P,Q\}\(\\epsilon\):=\\\{y:\\frac\{dP\}\{dQ\}\(y\)\>e^\{\\epsilon\}\\\}
δo​p​\(ε\)=\\displaystyle\\delta^\{op\}\(\\varepsilon\)=supX∼o​pX′P​\[ℛP,Q​\(ε\)\]−eε​Q​\[ℛP,Q​\(ε\)\]\\displaystyle\\sup\_\{X\\sim^\{op\}X\{\{\}^\{\\prime\}\}\}P\[\\mathcal\{R\}\_\{P,Q\}\(\\varepsilon\)\]\-e^\{\\varepsilon\}Q\[\\mathcal\{R\}\_\{P,Q\}\(\\varepsilon\)\]=\\displaystyle=supX∼X′P​\[ℛQ,P​\(−ε\)c\]−eε​ℳ​\(X′\)​\[ℛQ,P​\(−ε\)c\]\\displaystyle\\sup\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}P\[\\mathcal\{R\}\_\{Q,P\}\(\-\\varepsilon\)^\{c\}\]\-e^\{\\varepsilon\}\\mathcal\{M\}\(X^\{\{\}^\{\\prime\}\}\)\[\\mathcal\{R\}\_\{Q,P\}\(\-\\varepsilon\)^\{c\}\]=\\displaystyle=eε​\(supX∼X′Q​\[ℛQ,P​\(−ε\)\]−e−ε​P​\[ℛQ,P​\(−ε\)\]\+e−ε−1\)\\displaystyle e^\{\\varepsilon\}\(\\sup\_\{X\\sim X^\{\{\}^\{\\prime\}\}\}Q\[\\mathcal\{R\}\_\{Q,P\}\(\-\\varepsilon\)\]\-e^\{\-\\varepsilon\}P\[\\mathcal\{R\}\_\{Q,P\}\(\-\\varepsilon\)\]\+e^\{\-\\varepsilon\}\-1\)=\\displaystyle=1−eϵ​\(1−δ​\(−ϵ\)\)\\displaystyle 1\-e^\{\\epsilon\}\(1\-\\delta\(\-\\epsilon\)\)∎

Finally, we restate the primal\-dual relationship for a symmetric neighboring relation and show that the general result from Theorem[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3)reduces to the one presented inDonget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]\.

###### Corollary C\.12\.

Letℳ\\mathcal\{M\}be a randomized mechanism with the optimal tradeoff functionff, and privacy profileδ\\delta, for the symmetric neighboring relation≈\\approx\. The following \(equivalent\) conversions hold,

- •\(Primal to Dual\) δ​\(ϵ\)=1\+f∗​\(−eϵ\)\\delta\(\\epsilon\)=1\+f^\{\*\}\(\-e^\{\\epsilon\}\)
- •\(Dual to Primal\) f​\(α\)=supϵ≥0max⁡\{\(1−δ​\(ϵ\)−eϵ​α\),e−ϵ​\(1−δ​\(ϵ\)−α\)\}\\displaystyle f\(\\alpha\)=\\sup\_\{\\epsilon\\geq 0\}\\max\\\{\(1\-\\delta\(\\epsilon\)\-e^\{\\epsilon\}\\alpha\),e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\)\\\}

###### Proof\.

To show the dual to primal conversion, use Lemma[C\.11](https://arxiv.org/html/2605.21780#A3.Thmtheorem11)to writef​\(α\)f\(\\alpha\)as

f​\(α\)=\\displaystyle f\(\\alpha\)=supϵ∈ℝe−ϵ​\(1−δ​\(ϵ\)−α\)\\displaystyle\\sup\_\{\\epsilon\\in\\mathbb\{R\}\}e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\)=\\displaystyle=max⁡\{supϵ≥0e−ϵ​\(1−δ​\(ϵ\)−α\),supϵ≤0e−ϵ​\(1−δ​\(ϵ\)−α\)\}\\displaystyle\\max\\\{\\sup\_\{\\epsilon\\geq 0\}e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\),\\sup\_\{\\epsilon\\leq 0\}e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\)\\\}=\\displaystyle=max⁡\{supϵ≥0e−ϵ​\(1−δ​\(ϵ\)−α\),supϵ≥0eϵ​\(1−δ​\(−ϵ\)−α\)\}\\displaystyle\\max\\\{\\sup\_\{\\epsilon\\geq 0\}e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\),\\sup\_\{\\epsilon\\geq 0\}e^\{\\epsilon\}\(1\-\\delta\(\-\\epsilon\)\-\\alpha\)\\\}=\\displaystyle=max⁡\{supϵ≥0e−ϵ​\(1−δ​\(ϵ\)−α\),supϵ≥01−δ​\(ϵ\)−eϵ​α\}\(Lemma[C\.11](https://arxiv.org/html/2605.21780#A3.Thmtheorem11), andδo​p=δ\)\\displaystyle\\max\\\{\\sup\_\{\\epsilon\\geq 0\}e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\),\\sup\_\{\\epsilon\\geq 0\}1\-\\delta\(\\epsilon\)\-e^\{\\epsilon\}\\alpha\\\}\\qquad\\text\{\(Lemma \\ref\{lemma:privacy\_opposite\}, and $\\delta^\{op\}=\\delta$\)\}=\\displaystyle=supϵ≥0max⁡\{e−ϵ​\(1−δ​\(ϵ\)−α\),1−δ​\(ϵ\)−eϵ​α\}\\displaystyle\\sup\_\{\\epsilon\\geq 0\}\\max\\\{e^\{\-\\epsilon\}\(1\-\\delta\(\\epsilon\)\-\\alpha\),1\-\\delta\(\\epsilon\)\-e^\{\\epsilon\}\\alpha\\\}∎

### C\.3Auxiliary Lemmas: Proofs

###### Lemma C\.13\.

LetX⊆ℝX\\subseteq\\mathbb\{R\}andf:X→ℝf:X\\to\\mathbb\{R\}\. Define the property\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\)for a setA⊆X×ℝA\\subseteq X\\times\\mathbb\{R\}by

\(𝒫X\)∀\(x,t\)∈A,∀x^∈Xwithx^≥x:\(x^,t\)∈A\.\(\\mathcal\{P\}\_\{X\}\)\\qquad\\forall\(x,t\)\\in A,\\ \\forall\\hat\{x\}\\in X\\text\{ with \}\\hat\{x\}\\geq x:\\ \(\\hat\{x\},t\)\\in A\.\(5\)Thenffis monotonically non\-increasing if and only ifepi⁡\(f\)\\operatorname\{epi\}\(f\)satisfies\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\)\.

###### Proof\.

Recall that the epigraph offfis

epi⁡\(f\)=\{\(x,t\)∈X×ℝ:t≥f​\(x\)\}\.\\operatorname\{epi\}\(f\)=\\\{\(x,t\)\\in X\\times\\mathbb\{R\}:t\\geq f\(x\)\\\}\.
\(⇒\\Rightarrow\) Assume thatffis monotonically non\-increasing onXX\. Letx,x^∈Xx,\\hat\{x\}\\in Xwithx≤x^x\\leq\\hat\{x\}and lett∈ℝt\\in\\mathbb\{R\}be such that\(x,t\)∈epi⁡\(f\)\(x,t\)\\in\\operatorname\{epi\}\(f\)\. Thent≥f​\(x\)≥f​\(x^\)t\\geq f\(x\)\\geq f\(\\hat\{x\}\), sinceffis non\-increasing andx≤x^x\\leq\\hat\{x\}, which implies\(x^,t\)∈epi⁡\(f\)\(\\hat\{x\},t\)\\in\\operatorname\{epi\}\(f\)\.

\(⇐\\Leftarrow\) Conversely, assume that property[3](https://arxiv.org/html/2605.21780#A3.E3)holds\. Choose any arbitraryx,x^∈Xx,\\hat\{x\}\\in Xwithx≤x^x\\leq\\hat\{x\}\. Then\(x,f​\(x\)\)∈epi⁡\(f\)\(x,f\(x\)\)\\in\\operatorname\{epi\}\(f\), therefore by property[3](https://arxiv.org/html/2605.21780#A3.E3), it follows that\(x^,f​\(x\)\)∈epi⁡\(f\)\(\\hat\{x\},f\(x\)\)\\in\\operatorname\{epi\}\(f\), i\.e\.,f​\(x\)≥f​\(x^\)f\(x\)\\geq f\(\\hat\{x\}\)\. ∎

###### Lemma C\.14\.

LetX⊆ℝX\\subseteq\\mathbb\{R\}be a closed interval and letf:X→ℝf:X\\to\\mathbb\{R\}\. Ifepi⁡\(f\)\\operatorname\{epi\}\(f\)satisfies\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\), thencl⁡\(conv⁡\(epi⁡\(f\)\)\)\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(f\)\)\)also satisfies\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\)\.

###### Proof\.

LetA:=epi⁡\(f\)A:=\\operatorname\{epi\}\(f\)\. SinceA⊆X×ℝA\\subseteq X\\times\\mathbb\{R\}andXXis a closed interval, convex combinations and limits preserve the first coordinate inXX, hence

cl⁡\(conv⁡\(A\)\)⊆X×ℝ\.\\operatorname\{cl\}\(\\operatorname\{conv\}\(A\)\)\\subseteq X\\times\\mathbb\{R\}\.We show that\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\)is preserved first by convex hull, then by closure\.

*\(Convex hull\.\)*Take\(x,t\)∈conv⁡\(A\)\(x,t\)\\in\\operatorname\{conv\}\(A\)\. Then

\(x,t\)=∑i=1nλi​\(xi,ti\),λi≥0,∑i=1nλi=1,\(xi,ti\)∈A\.\(x,t\)=\\sum\_\{i=1\}^\{n\}\\lambda\_\{i\}\(x\_\{i\},t\_\{i\}\),\\qquad\\lambda\_\{i\}\\geq 0,\\ \\sum\_\{i=1\}^\{n\}\\lambda\_\{i\}=1,\\ \(x\_\{i\},t\_\{i\}\)\\in A\.Letx^∈X\\hat\{x\}\\in Xwithx^≥x\\hat\{x\}\\geq x\. Sincexxis the convex combination of\{xi\}i=1n\\\{x\_\{i\}\\\}\_\{i=1\}^\{n\}, there existsj∈\{1,⋯​n\}j\\in\\\{1,\\cdots n\\\}such thatxj≤xx\_\{j\}\\leq x, consequently,xj\+x^−x∈\[xj,x^\]⊆Xx\_\{j\}\+\\hat\{x\}\-x\\in\[x\_\{j\},\\hat\{x\}\]\\subseteq X\. Definex^i=xi\\hat\{x\}\_\{i\}=x\_\{i\}ifi≠ji\\neq j, andx^j=xj\+x^−x\\hat\{x\}\_\{j\}=x\_\{j\}\+\\hat\{x\}\-x\. We havex^i∈X\\hat\{x\}\_\{i\}\\in Xandx^i≥xi\\hat\{x\}\_\{i\}\\geq x\_\{i\}for allii\. SinceAAsatisfies\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\), it follows that\(x^i,ti\)∈A\(\\hat\{x\}\_\{i\},t\_\{i\}\)\\in A\. Therefore

\(x^,t\)=∑i=1nλi​\(x^i,ti\)∈conv⁡\(A\),\(\\hat\{x\},t\)=\\sum\_\{i=1\}^\{n\}\\lambda\_\{i\}\(\\hat\{x\}\_\{i\},t\_\{i\}\)\\in\\operatorname\{conv\}\(A\),soconv⁡\(A\)\\operatorname\{conv\}\(A\)satisfies\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\)\.

*\(Closure\.\)*Now let\(x,t\)∈cl⁡\(conv⁡\(A\)\)\(x,t\)\\in\\operatorname\{cl\}\(\\operatorname\{conv\}\(A\)\)andx^∈X\\hat\{x\}\\in Xwithx^\>x\\hat\{x\}\>x\. We assume strict inequality, because the case wherex^=x\\hat\{x\}=xis trivial\. There exist a sequence\(xk,tk\)∈conv⁡\(A\)\(x\_\{k\},t\_\{k\}\)\\in\\operatorname\{conv\}\(A\)with\(xk,tk\)​⟶k→∞​\(x,t\)\(x\_\{k\},t\_\{k\}\)\\overset\{k\\to\\infty\}\{\\longrightarrow\}\(x,t\)\. Defineδ\\deltaasδ:=x^−x\>0\\delta:=\\hat\{x\}\-x\>0, sincexk→xx\_\{k\}\\to x, there existN∈ℕN\\in\\mathbb\{N\}, such that for allk\>Nk\>N,\|x−xk\|<δ2\|x\-x\_\{k\}\|<\\frac\{\\delta\}\{2\}, orxk<x^x\_\{k\}<\\hat\{x\}\. This implies for allk\>Nk\>N, since\(xk,tk\)∈conv⁡\(A\)\(x\_\{k\},t\_\{k\}\)\\in\\operatorname\{conv\}\(A\),\(x^,tk\)∈conv⁡\(A\)\(\\hat\{x\},t\_\{k\}\)\\in\\operatorname\{conv\}\(A\)\. Therefore,limk→∞\(x^,tk\)=\(x^,t\)∈cl⁡\(conv⁡\(A\)\)\\lim\_\{k\\to\\infty\}\(\\hat\{x\},t\_\{k\}\)=\(\\hat\{x\},t\)\\in\\operatorname\{cl\}\(\\operatorname\{conv\}\(A\)\)\. Thuscl⁡\(conv⁡\(epi⁡\(f\)\)\)\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(f\)\)\)satisfies\(𝒫X\)\(\\mathcal\{P\}\_\{X\}\)\. ∎

###### Lemma C\.15\.

LetX⊆ℝX\\subseteq\\mathbb\{R\}be a closed interval and letf:X→ℝf:X\\to\\mathbb\{R\}be monotonically non\-increasing\. Consider the biconjugate of the\+∞\+\\infty\-extension offftoℝ\\mathbb\{R\}, and denote its restriction toXXbyf∗∗∣Xf^\{\*\*\}\\\!\\mid\_\{X\}\. Thenf∗∗∣X:X→ℝf^\{\*\*\}\\\!\\mid\_\{X\}:X\\to\\mathbb\{R\}is monotonically non\-increasing\.

###### Proof\.

SinceXXis closed and convex,cl⁡\(conv⁡\(epi⁡\(f\)\)\)⊆X×ℝ\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(f\)\)\)\\subseteq X\\times\\mathbb\{R\}\. Sinceepi⁡\(f∗∗\)=cl⁡\(conv⁡\(epi⁡\(f\)\)\)\\operatorname\{epi\}\(f^\{\*\*\}\)=\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(f\)\)\), and sinceffis non\-increasing on X, implies thatcl⁡\(conv⁡\(epi⁡\(f\)\)\)\\operatorname\{cl\}\(\\operatorname\{conv\}\(\\operatorname\{epi\}\(f\)\)\)satisfies𝒫X\\mathcal\{P\}\_\{X\}\(lemma[C\.2](https://arxiv.org/html/2605.21780#A3.Thmtheorem2)\), thereforeepi⁡\(f∗∗\)\\operatorname\{epi\}\(f^\{\*\*\}\)satisfies𝒫X\\mathcal\{P\}\_\{X\}\(lemma[C\.3](https://arxiv.org/html/2605.21780#A3.Thmtheorem3)\)\. Again, by Lemma[C\.2](https://arxiv.org/html/2605.21780#A3.Thmtheorem2),f∗∗f^\{\*\*\}is monotonically non\-increasing on X\. ∎

###### Lemma C\.16\.

LetPPandQQbe distributions onYY, andℋ\\mathcal\{H\}be the space of hypothesis tests onYY\. Then the HS divergence betweenPPandQQcan be written as the following supremum overℋ\\mathcal\{H\}\.

DαHS=supϕ∈ℋ\(𝔼P​\(ϕ\)−eε​𝔼Q​\(ϕ\)\)D\_\{\\alpha\}^\{\\text\{HS\}\}=\\sup\_\{\\phi\\in\\mathcal\{H\}\}\\bigl\(\\mathbb\{E\}\_\{P\}\(\\phi\)\-e^\{\\varepsilon\}\\mathbb\{E\}\_\{Q\}\(\\phi\)\\bigr\)

###### Proof\.

For allϕ∈ℋb\\phi\\in\\mathcal\{H\}\_\{b\}, defineAϕ:=\{a\|ϕ​\(a\)=1\}A\_\{\\phi\}:=\\\{a\|\\phi\(a\)=1\\\}\. Denote the measureP\+Q2\\frac\{P\+Q\}\{2\}asDD, thenP≪DP\\ll D, andQ≪DQ\\ll D, henced​Pd​D\\frac\{dP\}\{dD\}andd​Qd​D\\frac\{dQ\}\{dD\}exist\. By the definition of the HS divergence,

δ​\(ε\)=supA\(P​\(A\)−eε​Q​\(A\)\)\.\\delta\(\\varepsilon\)=\\sup\_\{A\}\\bigl\(P\(A\)\-e^\{\\varepsilon\}Q\(A\)\\bigr\)\.
supA\(P​\(A\)−eε​Q​\(A\)\)\\displaystyle\\sup\_\{A\}\\bigl\(P\(A\)\-e^\{\\varepsilon\}Q\(A\)\\bigr\)=supA\(𝔼P​\(𝟙A\)−eε​𝔼Q​\(𝟙A\)\)\\displaystyle=\\sup\_\{A\}\\bigl\(\\mathbb\{E\}\_\{P\}\(\\mathbbm\{1\}\_\{A\}\)\-e^\{\\varepsilon\}\\mathbb\{E\}\_\{Q\}\(\\mathbbm\{1\}\_\{A\}\)\\bigr\)≤supϕ∈ℋ\(𝔼P​\(ϕ\)−eε​𝔼Q​\(ϕ\)\)\\displaystyle\\leq\\sup\_\{\\phi\\in\\mathcal\{H\}\}\\bigl\(\\mathbb\{E\}\_\{P\}\(\\phi\)\-e^\{\\varepsilon\}\\mathbb\{E\}\_\{Q\}\(\\phi\)\\bigr\)=supϕ∈ℋ\(𝔼D\(ϕ\(d​Pd​D−eεd​Qd​D\)\)\\displaystyle=\\sup\_\{\\phi\\in\\mathcal\{H\}\}\\bigl\(\\mathbb\{E\}\_\{D\}\(\\phi\(\\frac\{dP\}\{dD\}\-e^\{\\varepsilon\}\\frac\{dQ\}\{dD\}\)\\bigr\)=P​\(Aϕ\)−eε​Q​\(Aϕ\)\\displaystyle=P\(A\_\{\\phi\}\)\-e^\{\\varepsilon\}Q\(A\_\{\\phi\}\)\(sup is attained by a binary HTϕ\\phi, based on the Likelihood ratios\)≤supA\(P​\(A\)−eε​Q​\(A\)\)\\displaystyle\\leq\\sup\_\{A\}\\bigl\(P\(A\)\-e^\{\\varepsilon\}Q\(A\)\\bigr\)
∎

###### Lemma C\.17\.

Letff,ggbe two tradeoff functions, i\.e\.,f,g∈ℱf,g\\in\\mathcal\{F\}, such thatf≤gf\\leq g\. Then the left continuous inverse of a non\-increasing function preserves this order, i\.e\.,

###### Proof\.

f≤g\\displaystyle f\\leq g⟹\\displaystyle\\implies\{t\|g​\(t\)≤α\}⊆\{t\|f​\(t\)≤α\}\(for allα∈\[0,1\]\)\\displaystyle\\\{t\\,\|\\,g\(t\)\\leq\\alpha\\\}\\subseteq\\\{t\\,\|\\,f\(t\)\\leq\\alpha\\\}\\qquad\\text\{\(for all $\\alpha\\in\[0,1\]$\)\}⟹\\displaystyle\\impliesinft\{t\|f​\(t\)≤α\}≤inft\{t\|g​\(t\)≤α\}\(for allα∈\[0,1\]\)\\displaystyle\\inf\_\{t\}\\\{t\\,\|\\,f\(t\)\\leq\\alpha\\\}\\leq\\inf\_\{t\}\\\{t\\,\|\\,g\(t\)\\leq\\alpha\\\}\\qquad\\text\{\(for all $\\alpha\\in\[0,1\]$\)\}⟹\\displaystyle\\impliesf−1≤g−1\\displaystyle f^\{\-1\}\\leq g^\{\-1\}∎

###### Lemma C\.18\.

Letf:ℝ→ℝ¯f:\\mathbb\{R\}\\to\\overline\{\\mathbb\{R\}\}be a proper function with a global lower boundLL, i\.e\.,−∞<L≤f\-\\infty<L\\leq f\. Then, its biconjugate also hasLLas a global lower bound, i\.e\.,L≤f∗∗L\\leq f^\{\*\*\}\.

###### Proof\.

f∗∗​\(x\)\\displaystyle f^\{\*\*\}\(x\)=supαinfβα​x−β​α\+f​\(β\)\\displaystyle=\\sup\_\{\\alpha\}\\inf\_\{\\beta\}\\alpha x\-\\beta\\alpha\+f\(\\beta\)≥infβf​\(β\)\(chooseα=0\)\\displaystyle\\geq\\inf\_\{\\beta\}f\(\\beta\)\\qquad\\text\{\(choose $\\alpha=0$\)\}≥L\\displaystyle\\geq L
∎

## Appendix DCertifying Robustness via Primal\-Dual Characterization of DP

###### Theorem D\.1\(Certification via the dual formulation of privacy\)\.

For the unperturbed input𝐗\\mathbf\{X\}, letc1c\_\{1\}andc2c\_\{2\}denote the majority and second\-majority classes, respectively, and letp1,p2∈\[0,1\]p\_\{1\},p\_\{2\}\\in\[0,1\]satisfy𝔼ℳ​\(𝐗\)​\[ϕc1​\(z\)\]≥p1\>p2≥𝔼z∼ℳ​\(𝐗\)​\[ϕc2​\(z\)\]\\mathbb\{E\}\_\{\\mathcal\{M\}\(\\mathbf\{X\}\)\}\\bigl\[\\phi\_\{c\_\{1\}\}\(z\)\\bigr\]\\;\\geq\\;p\_\{1\}\\;\>\\;p\_\{2\}\\;\\geq\\;\\mathbb\{E\}\_\{z\\sim\\mathcal\{M\}\(\\mathbf\{X\}\)\}\\bigl\[\\phi\_\{c\_\{2\}\}\(z\)\\bigr\]\. Then the classifierg​\(⋅\)g\(\\cdot\)isρ\\rho\-robust at𝐗\\mathbf\{X\}, i\.e\., for all𝐗′≈ρ𝐗\\mathbf\{X\}^\{\{\}^\{\\prime\}\}\\approx\_\{\\rho\}\\mathbf\{X\},g​\(𝐗′\)=g​\(𝐗\)g\(\\mathbf\{X\}^\{\{\}^\{\\prime\}\}\)=g\(\\mathbf\{X\}\)if

mini∈\{1,…,N\}⁡\[maxε∈ℝ⁡e−ε​\(p1−δi​\(ε\)\)\+maxε∈ℝ⁡e−ε​\(1−p2−δi​\(ε\)\)\]\>1\\min\_\{i\\in\\\{1,\.\.\.,N\\\}\}\\bigl\[\\max\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\\bigl\(p\_\{1\}\-\\delta\_\{i\}\(\\varepsilon\)\\bigr\)\+\\max\_\{\\varepsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\\bigl\(1\-p\_\{2\}\-\\delta\_\{i\}\(\\varepsilon\)\\bigr\)\\bigr\]\\;\>\\;1

###### Proof\.

We verify robustness for each neighboring relation≈ρi\\approx\_\{\\rho\_\{i\}\}Letfif\_\{i\}be the optimal tradeoff function corresponding to the privacy profileδi​\(ε\)\\delta\_\{i\}\(\\varepsilon\)\. This result directly follows from Theorem[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3), and Proposition2\.12\.1inLyuet al\.\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\. Using the latter,g\(\.\)g\(\.\)isρ−\\rho\-robust at𝐗\\mathbf\{X\}, if

fi​\(1−pi\)\>1−fi​\(p2\)\\displaystyle f\_\{i\}\(1\-p\_\{i\}\)\>1\-f\_\{i\}\(p\_\{2\}\)⇔\\displaystyle\\iffmaxϵ1∈ℝ⁡e−ϵ1​\(p1−δi​\(ϵ1\)\)\>minϵ2∈ℝ⁡\(1−e−ϵ2​\(1−p2−δi​\(ϵ2\)\)\)\\displaystyle\\max\_\{\\epsilon\_\{1\}\\in\\mathbb\{R\}\}e^\{\-\\epsilon\_\{1\}\}\\bigl\(p\_\{1\}\-\\delta\_\{i\}\(\\epsilon\_\{1\}\)\\bigr\)\\;\>\\;\\min\_\{\\epsilon\_\{2\}\\in\\mathbb\{R\}\}\(1\-e^\{\-\\epsilon\_\{2\}\}\\bigl\(1\-p\_\{2\}\-\\delta\_\{i\}\(\\epsilon\_\{2\}\)\\bigr\)\)
∎

###### Lemma D\.2\.

Letδi​\(⋅\)\\delta\_\{i\}\(\\cdot\), andfif\_\{i\}be the privacy profile and optimal tradeoff function for the decomposed relations≈ρi\\approx\_\{\\rho\_\{i\}\}, withδ​\(⋅\)=maxi⁡δi​\(⋅\)\\delta\(\\cdot\)=\\max\_\{i\}\\delta\_\{i\}\(\{\\cdot\}\)the privacy profile of≈ρ\\approx\_\{\\rho\}\. If there exists a pair of data\(𝐗,𝐗′\)\(\\mathbf\{X\},\\mathbf\{X\}^\{\\prime\}\)such thatδ​\(ε\)=DeεHS​\(ℳ​\(𝐗\),ℳ​\(𝐗′\)\)\\delta\(\\varepsilon\)=D\_\{e^\{\\varepsilon\}\}^\{\\text\{HS\}\}\(\\mathcal\{M\}\(\\mathbf\{X\}\),\\mathcal\{M\}\(\\mathbf\{X\}^\{\\prime\}\)\), thenmini⁡fi=f\\min\_\{i\}f\_\{i\}=f, the dual to primal conversion ofδ​\(⋅\)\\delta\(\\cdot\)

###### Proof\.

Denote the dual to primal function as𝒢\\mathcal\{G\}\.f=𝒢​\(δ\)=𝒢​\(De\(⋅\)HS​\(ℳ​\(𝐗\),ℳ​\(𝐗′\)\)\)=Λ​\(ℳ​\(𝐗\)∥ℳ​\(𝐗′\)\)≥mini⁡fi≥ff=\\mathcal\{G\}\(\\delta\)=\\mathcal\{G\}\(D\_\{e^\{\(\\cdot\)\}\}^\{\\text\{HS\}\}\(\\mathcal\{M\}\(\\mathbf\{X\}\),\\mathcal\{M\}\(\\mathbf\{X\}^\{\\prime\}\)\)\)=\\Lambda\(\\mathcal\{M\}\(\\mathbf\{X\}\)\\;\\\|\\;\\mathcal\{M\}\(\\mathbf\{X\}^\{\\prime\}\)\)\\geq\\min\_\{i\}f\_\{i\}\\geq f\.

Therefore, no further decomposition is needed for tighter guarantees\. Specifically, in the black\-box sense, this holds for the sub\-sampled Gaussian with respect to addition/removal\[[61](https://arxiv.org/html/2605.21780#bib.bib30), Theorem M\.4\]\.\. ∎

### D\.1DP analysis of DPA and its composition with arbitrary mechanism

We split the proof of[Theorem 5\.1](https://arxiv.org/html/2605.21780#S5.Thmtheorem1)into two parts\. In[Theorem D\.3](https://arxiv.org/html/2605.21780#A4.Thmtheorem3), we interpret DPA as a randomized mechanism and derive itsf−f\-DP characteristic\. We then use the Privacy Loss Distribution of DPA, discussed in[Theorem D\.3](https://arxiv.org/html/2605.21780#A4.Thmtheorem3), to derive the privacy accounting of DPA combined with an arbitrary base mechanism\.

###### Theorem D\.3\(Tradeoff function for randomized DPA partition sampling\)\.

Fix an integerN≥1N\\geq 1and a deterministic partitioning map

H:⋃i=1N𝒯i→\(⋃i=1N𝒯i,𝒞\),H​\(X\)=\(Y1,…,YN\),H:\\bigcup\_\{i=1\}^\{N\}\\mathcal\{T\}\_\{i\}\\to\(\\bigcup\_\{i=1\}^\{N\}\\mathcal\{T\}\_\{i\},\\mathcal\{C\}\),\\qquad H\(X\)=\(Y\_\{1\},\\dots,Y\_\{N\}\),where eachYiY\_\{i\}is itself a dataset, and𝒞\\mathcal\{C\}is the sigma algebra generated by the singleton sets\. The randomized mechanismℳ\\mathcal\{M\}mapsXt​r​a​i​nX\_\{train\}to the distribution over\(⋃i=1N𝒯i,𝒞\)\(\\bigcup\_\{i=1\}^\{N\}\\mathcal\{T\}\_\{i\},\\mathcal\{C\}\), assigning eachH​\(Xt​r​a​i​n\)iH\(X\_\{train\}\)\_\{i\}as probability mass of1/N1/N\. Let the adjacency relation be

X∼RX′⟺dtrain​\(X,X′\)≤R,X\\sim\_\{R\}X^\{\\prime\}\\quad\\Longleftrightarrow\\quad d\_\{\\mathrm\{train\}\}\(X,X^\{\\prime\}\)\\leq R,wheredtraind\_\{\\mathrm\{train\}\}counts the number of modified datapoints\.

Thenℳ\\mathcal\{M\}isff–DP \(with respect to∼R\\sim\_\{R\}\) with tradeoff function

f​\(α\)=max⁡\{1−RN−α,0\},α∈\[0,1\]\.f\(\\alpha\)\\;=\\;\\max\\Bigl\\\{1\-\\frac\{R\}\{N\}\-\\alpha,\\,0\\Bigr\\\},\\qquad\\alpha\\in\[0,1\]\.

###### Proof\.

FixX∼RX′X\\sim\_\{R\}X^\{\\prime\}and writeH​\(X\)=\(Y1,…,YN\)H\(X\)=\(Y\_\{1\},\\dots,Y\_\{N\}\)andH​\(X′\)=\(Y1′,…,YN′\)H\(X^\{\\prime\}\)=\(Y^\{\\prime\}\_\{1\},\\dots,Y^\{\\prime\}\_\{N\}\)\. DefinePPandQQasℳ​\(X\)\\mathcal\{M\}\(X\)andℳ​\(X′\)\\mathcal\{M\}\(X^\{\\prime\}\)\. By construction,PPandQQare uniform measures supported on

S:=\{Y1,…,YN\},S′:=\{Y1′,…,YN′\},S:=\\\{Y\_\{1\},\\dots,Y\_\{N\}\\\},\\qquad S^\{\\prime\}:=\\\{Y^\{\\prime\}\_\{1\},\\dots,Y^\{\\prime\}\_\{N\}\\\},withP​\(\{y\}\)=1NP\(\\\{y\\\}\)=\\frac\{1\}\{N\}fory∈Sy\\in Sand0otherwise \(and similarly forQQwithS′S^\{\\prime\}\)\.

We derive the HS divergence assumingrrpartitions are changed, then to get the privacy profile, we takesup\\supoverr≤Rr\\leq R\. If we sampleyyfromy∼Py\\sim P,Q​\(y\)=0Q\(y\)=0, with probabilityrN\\frac\{r\}\{N\}\. Therefore, the privacy loss distribution underPPis

PLDP/Q\(r\)=log⁡\(d​Pd​Q\)=\{0,with prob\.​1−rN,\+∞,with prob\.​rN\.\\mathrm\{PLD\}\_\{P/Q\}^\{\(r\)\}=\\log\\Bigl\(\\frac\{dP\}\{dQ\}\\Bigr\)=\\begin\{cases\}0,&\\text\{with prob\. \}1\-\\frac\{r\}\{N\},\\\\ \+\\infty,&\\text\{with prob\. \}\\frac\{r\}\{N\}\.\\end\{cases\}
Using,

δ\(r\)​\(ε\)=𝒟eε​\(P∥Q\)=𝔼Y∼PLDP/Q\(r\)​\[\(1−eε−Y\)\+\],\(t\)\+:=max⁡\{t,0\}\.\\delta^\{\(r\)\}\(\\varepsilon\)=\\mathcal\{D\}\_\{e^\{\\varepsilon\}\}\(P\\\|Q\)=\\mathbb\{E\}\_\{Y\\sim\\mathrm\{PLD\}\_\{P/Q\}^\{\(r\)\}\}\\\!\\bigl\[\\,\\bigl\(1\-e^\{\\varepsilon\-Y\}\\bigr\)\_\{\+\}\\,\\bigr\],\\qquad\(t\)\_\{\+\}:=\\max\\\{t,0\\\}\.
δ\(r\)​\(ε\)=\(1−rN\)​\(1−eε−0\)\+\+rN​\(1−eε−∞\)\+\.\\delta^\{\(r\)\}\(\\varepsilon\)=\\Bigl\(1\-\\frac\{r\}\{N\}\\Bigr\)\\bigl\(1\-e^\{\\varepsilon\-0\}\\bigr\)\_\{\+\}\+\\frac\{r\}\{N\}\\bigl\(1\-e^\{\\varepsilon\-\\infty\}\\bigr\)\_\{\+\}\.Forε≥0\\varepsilon\\geq 0,\(1−eε\)\+=0\(1\-e^\{\\varepsilon\}\)\_\{\+\}=0andeε−∞=0e^\{\\varepsilon\-\\infty\}=0, hence

δ​\(ε\)=supr≤Rδ\(r\)​\(ε\)=supr≤RrN=RN\.\\delta\(\\varepsilon\)=\\sup\_\{r\\leq R\}\\delta^\{\(r\)\}\(\\varepsilon\)=\\sup\_\{r\\leq R\}\\frac\{r\}\{N\}=\\frac\{R\}\{N\}\.
f​\(α\)=supε≥0e−ε​\(1−δ​\(ε\)−α\)=supε≥0e−ε​\(1−RN−α\)=max⁡\{1−RN−α,0\}\.f\(\\alpha\)=\\sup\_\{\\varepsilon\\geq 0\}e^\{\-\\varepsilon\}\\bigl\(1\-\\delta\(\\varepsilon\)\-\\alpha\\bigr\)=\\sup\_\{\\varepsilon\\geq 0\}e^\{\-\\varepsilon\}\\Bigl\(1\-\\frac\{R\}\{N\}\-\\alpha\\Bigr\)=\\max\\Bigl\\\{1\-\\frac\{R\}\{N\}\-\\alpha,\\,0\\Bigr\\\}\.
Forε<0\\varepsilon<0,\(1−eε\)\+=1−eε\(1\-e^\{\\varepsilon\}\)\_\{\+\}=1\-e^\{\\varepsilon\}andeε−∞=0e^\{\\varepsilon\-\\infty\}=0, hence

δ​\(ε\)=supr≤Rδ\(r\)​\(ε\)=supr≤R\(1−rN\)​\(1−eε\)\+rN=supr≤R1−\(1−rN\)​eε=1−\(1−RN\)​eε\.\\delta\(\\varepsilon\)=\\sup\_\{r\\leq R\}\\delta^\{\(r\)\}\(\\varepsilon\)=\\sup\_\{r\\leq R\}\\Bigl\(1\-\\frac\{r\}\{N\}\\Bigr\)\(1\-e^\{\\varepsilon\}\)\+\\frac\{r\}\{N\}=\\sup\_\{r\\leq R\}1\-\\Bigl\(1\-\\frac\{r\}\{N\}\\Bigr\)e^\{\\varepsilon\}=1\-\\Bigl\(1\-\\frac\{R\}\{N\}\\Bigr\)e^\{\\varepsilon\}\.
e−ε​\(1−δ​\(ε\)−α\)=e−ε​\(\(1−RN\)​eε−α\)=\(1−RN\)−α​e−ε\.e^\{\-\\varepsilon\}\\bigl\(1\-\\delta\(\\varepsilon\)\-\\alpha\\bigr\)=e^\{\-\\varepsilon\}\\Bigl\(\\bigl\(1\-\\tfrac\{R\}\{N\}\\bigr\)e^\{\\varepsilon\}\-\\alpha\\Bigr\)=\\Bigl\(1\-\\tfrac\{R\}\{N\}\\Bigr\)\-\\alpha e^\{\-\\varepsilon\}\.the supremum overε<0\\varepsilon<0is attained atε↑0\\varepsilon\\uparrow 0and equals1−RN−α1\-\\frac\{R\}\{N\}\-\\alpha\. Taking the max over both cases proves the claim\. ∎

###### Theorem D\.4\(Composing DPA with another mechanism\)\.

Let𝒟N\\mathcal\{D\}\_\{N\}denote the DPA mechanism withNNpartitions, and letℬ\\mathcal\{B\}be any inference\-time mechanism on𝕏\\mathbb\{X\}that isfbf\_\{b\}\-DP with privacy profileδb​\(ϵ\)\\delta\_\{b\}\(\\epsilon\)for a neighboring relation∼b\\sim\_\{b\}\. Define the combined relation as∼c\\sim\_\{c\}as\(𝐗,𝐱\)∼c\(𝐗′,𝐱′\)⇔dtrain​\(𝐗,𝐗′\)∧𝐱∼b𝐱′\(\\mathbf\{X\},\\mathbf\{x\}\)\\sim\_\{c\}\(\\mathbf\{X^\{\{\}^\{\\prime\}\}\},\\mathbf\{x^\{\{\}^\{\\prime\}\}\}\)\\iff d\_\{\\text\{train\}\}\(\\mathbf\{X\},\\mathbf\{X^\{\{\}^\{\\prime\}\}\}\)\\;\\;\\land\\;\\;\\mathbf\{x\}\\sim\_\{b\}\\mathbf\{x^\{\{\}^\{\\prime\}\}\}\. Then the composed mechanismℬ∘𝒟N\\mathcal\{B\}\\circ\\mathcal\{D\}\_\{N\}, defined on⋃i=1NTi×𝕏\\mathcal\{\\bigcup\}\_\{i=1\}^\{N\}T\_\{i\}\\times\\mathbb\{X\}isfcf\_\{c\}\-DP with privacy profileδc​\(ϵ\)\\delta\_\{c\}\(\\epsilon\)for the neighboring relation∼c\\sim\_\{c\},, where

fc​\(α\)=\{\(1−RN\)​fb​\(α1−RN\),if​α≤1−RN,0,otherwise,f\_\{c\}\(\\alpha\)=\\begin\{dcases\}\\Bigl\(1\-\\frac\{R\}\{N\}\\Bigr\)\\,f\_\{b\}\\\!\\left\(\\frac\{\\alpha\}\{1\-\\frac\{R\}\{N\}\}\\right\),&\\text\{if \}\\alpha\\leq 1\-\\frac\{R\}\{N\},\\\\\[6\.0pt\] 0,&\\text\{otherwise\},\\end\{dcases\}and

δc​\(ϵ\)=RN\+\(1−RN\)​δb​\(ϵ\)\.\\delta\_\{c\}\(\\epsilon\)=\\frac\{R\}\{N\}\+\(1\-\\frac\{R\}\{N\}\)\\,\\delta\_\{b\}\(\\epsilon\)\.

###### Proof\.

LetZdZ\_\{d\},ZbZ\_\{b\}be the PLD of DPA and the base mechanism, respectively\. The PLD of the composed mechanism is given byZc=Zd\+ZbZ\_\{c\}=Z\_\{d\}\+Z\_\{b\}\. AssumingZdZ\_\{d\}andZbZ\_\{b\}to be independent, we can evaluate the CDF of the composed PLDΦc​\(z\)\\Phi\_\{c\}\(z\)for somez∈ℝz\\in\\mathbb\{R\}as

Φc​\(z\)\\displaystyle\\Phi\_\{c\}\(z\)=ℙ​\[Zc≤z\]\\displaystyle=\\mathbb\{P\}\[Z\_\{c\}\\leq z\]=ℙ​\[Zd\+Zb≤z\]\\displaystyle=\\mathbb\{P\}\[Z\_\{d\}\+Z\_\{b\}\\leq z\]=𝔼zd∈\{0,\+∞\}​\[ℙ​\[Zb≤z−zd\]\]\\displaystyle=\\mathbb\{E\}\_\{z\_\{d\}\\in\\\{0,\+\\infty\\\}\}\[\\mathbb\{P\}\[Z\_\{b\}\\leq z\-z\_\{d\}\]\]=\(1−RN\)​Φb​\(z\)\\displaystyle=\(1\-\\frac\{R\}\{N\}\)\\Phi\_\{b\}\(z\)
This allows us to evaluate the mass at\+∞\+\\inftyas

ℙ​\[Zc=\+∞\]\\displaystyle\\mathbb\{P\}\[Z\_\{c\}=\+\\infty\]=1−supzΦc​\(z\)\\displaystyle=1\-\\sup\_\{z\}\\Phi\_\{c\}\(z\)=1−\(1−RN\)​\(1−ℙ​\[Zb=\+∞\]\)\\displaystyle=1\-\(1\-\\frac\{R\}\{N\}\)\(1\-\\mathbb\{P\}\[Z\_\{b\}=\+\\infty\]\)=RN\+\(1−RN\)​ℙ​\[Zb=\+∞\]\\displaystyle=\\frac\{R\}\{N\}\+\(1\-\\frac\{R\}\{N\}\)\\mathbb\{P\}\[Z\_\{b\}=\+\\infty\]
Finally, we get the privacy profile from the PLD as,

δc​\(ε\)\\displaystyle\\delta\_\{c\}\(\\varepsilon\)=𝔼z∼Zc​\[\(1−eε−z\)\+\]\\displaystyle=\\mathbb\{E\}\_\{z\\sim Z\_\{c\}\}\\\!\\bigl\[\\,\\bigl\(1\-e^\{\\varepsilon\-z\}\\bigr\)\_\{\+\}\\,\\bigr\]=ℙ​\[Zc=\+∞\]\+𝔼Zd<∞​\[𝔼Zb<∞​\[\(1−eε−zd−zb\)\+\]\]\\displaystyle=\\mathbb\{P\}\[Z\_\{c\}=\+\\infty\]\+\\mathbb\{E\}\_\{Z\_\{d\}<\\infty\}\[\\mathbb\{E\}\_\{Z\_\{b\}<\\infty\}\[\(1\-e^\{\\varepsilon\-z\_\{d\}\-z\_\{b\}\}\\bigr\)\_\{\+\}\]\]=RN\+\(1−RN\)​ℙ​\[Zb=\+∞\]\+\(1−RN\)​𝔼Zb<∞​\[\(1−eε−zb\)\+\]\\displaystyle=\\frac\{R\}\{N\}\+\(1\-\\frac\{R\}\{N\}\)\\mathbb\{P\}\[Z\_\{b\}=\+\\infty\]\+\(1\-\\frac\{R\}\{N\}\)\\mathbb\{E\}\_\{Z\_\{b\}<\\infty\}\[\(1\-e^\{\\varepsilon\-z\_\{b\}\}\\bigr\)\_\{\+\}\]=RN\+\(1−RN\)​\(P​\[Zb=\+∞\]\+𝔼Zb<∞​\[\(1−eε−zb\)\+\]\)\\displaystyle=\\frac\{R\}\{N\}\+\(1\-\\frac\{R\}\{N\}\)\\mathbb\{\(\}P\[Z\_\{b\}=\+\\infty\]\+\\mathbb\{E\}\_\{Z\_\{b\}<\\infty\}\[\(1\-e^\{\\varepsilon\-z\_\{b\}\}\\bigr\)\_\{\+\}\]\)=RN\+\(1−RN\)​δb​\(ε\)\\displaystyle=\\frac\{R\}\{N\}\+\(1\-\\frac\{R\}\{N\}\)\\delta\_\{b\}\(\\varepsilon\)
Notice thatδb​\(ε\)≤1\\delta\_\{b\}\(\\varepsilon\)\\leq 1, this implies that the composed privacy profileδc​\(ε\)=δb​\(ε\)\+\(1−δb​\(ε\)\)​RN\\delta\_\{c\}\(\\varepsilon\)=\\delta\_\{b\}\(\\varepsilon\)\+\(1\-\\delta\_\{b\}\(\\varepsilon\)\)\\frac\{R\}\{N\}, is monotonically increasing with respect toRR\. Therefore, the supremum over the neighboring relations is achieved at the maximum radius of perturbationRRin the training data\.

Now, to derive the optimal tradeoff function, use the result from[4\.3](https://arxiv.org/html/2605.21780#S4.Thmtheorem3)\.

fc​\(α\)\\displaystyle f\_\{c\}\(\\alpha\)=supϵ∈ℝe−ε​\(1−δc​\(ε\)−α\)\\displaystyle=\\sup\_\{\\epsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(1\-\\delta\_\{c\}\(\\varepsilon\)\-\\alpha\)=supϵ∈ℝe−ε​\(1−RN−\(1−RN\)​δb​\(ε\)−α\)\\displaystyle=\\sup\_\{\\epsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(1\-\\frac\{R\}\{N\}\-\(1\-\\frac\{R\}\{N\}\)\\delta\_\{b\}\(\\varepsilon\)\-\\alpha\)=\(1−RN\)​supϵ∈ℝe−ε​\(1−δb​\(ε\)−α1−RN\)\\displaystyle=\(1\-\\frac\{R\}\{N\}\)\\sup\_\{\\epsilon\\in\\mathbb\{R\}\}e^\{\-\\varepsilon\}\(1\-\\delta\_\{b\}\(\\varepsilon\)\-\\frac\{\\alpha\}\{1\-\\frac\{R\}\{N\}\}\)
Clearly, forα≤1−RN\\alpha\\leq 1\-\\frac\{R\}\{N\},fc​\(α\)=\(1−RN\)​fb​\(α1−RN\)f\_\{c\}\(\\alpha\)=\(1\-\\frac\{R\}\{N\}\)f\_\{b\}\(\\frac\{\\alpha\}\{1\-\\frac\{R\}\{N\}\}\), and wheneverα\>1−RN\\alpha\>1\-\\frac\{R\}\{N\},1−α1−RN−δ​\(ε\)<01\-\\frac\{\\alpha\}\{1\-\\frac\{R\}\{N\}\}\-\\delta\(\\varepsilon\)<0for everyε\\varepsilon\. Therefore, the supremum is taken asε→∞\\varepsilon\\to\\inftyand is0\. ∎

### D\.2Limitations of the Primal Perspective

Primal DP \(ff\-DP\)\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]offers an expressive framework for reasoning about tight composition of randomized mechanisms, including asymptotic behavior under composition\. Precisely, iff1=Λ​\(P1∥Q1\)f\_\{1\}=\\Lambda\(P\_\{1\}\\,\\\|\\,Q\_\{1\}\)andf2=Λ​\(P2∥Q2\)f\_\{2\}=\\Lambda\(P\_\{2\}\\,\\\|\\,Q\_\{2\}\)are tradeoff functions, then their composition corresponds to the tradeoff functionΛ​\(P1×P2∥Q1×Q2\)\\Lambda\(P\_\{1\}\\times P\_\{2\}\\,\\\|\\,Q\_\{1\}\\times Q\_\{2\}\)\. However, this characterization does not provide a practical method for computing such compositions\. Obtaining an analytic expression for the tradeoff function of a composition of mechanisms is possible only when the convolutions of the corresponding Privacy Loss Distributions \(PLDs\) can be computed analytically\. We make this limitation explicit by rewriting the Neyman–Pearson Lemma in terms of PLDs in Theorem[D\.5](https://arxiv.org/html/2605.21780#A4.Thmtheorem5)\.

We then revisit the tight characterization of the composition of randomized mechanisms from theff\-DP perspective\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]\. Finally, we argue that evaluating the tradeoff function for a composition reduces to computing the convolution of the corresponding PLDs\.

###### Theorem D\.5\(Neyman–Pearson characterization via the PLRV\)\.

Assume thatℳ​\(X\)\\mathcal\{M\}\(X\)andℳ​\(X′\)\\mathcal\{M\}\(X^\{\\prime\}\)admit densitiesPPandQQ\. Define the privacy–loss random variables

L1:=log⁡P​\(y\)Q​\(y\)for​y∼P,L2:=log⁡P​\(y\)Q​\(y\)for​y∼Q\.L\_\{1\}:=\\log\\frac\{P\(y\)\}\{Q\(y\)\}\\quad\\text\{for \}y\\sim P,\\qquad L\_\{2\}:=\\log\\frac\{P\(y\)\}\{Q\(y\)\}\\quad\\text\{for \}y\\sim Q\.LetF1F\_\{1\}andF2F\_\{2\}denote the cumulative distribution functions ofL1L\_\{1\}andL2L\_\{2\}\.

Then for everyα∈\[0,1\]\\alpha\\in\[0,1\], the infimum overϕ∈ℋ\\phi\\in\\mathcal\{H\}in Equation equation[1](https://arxiv.org/html/2605.21780#S3.E1)is attained by a likelihood–ratio test, and the optimal value can be written in terms of the CDFs of the privacy–loss random variables as

Opt​\(α\)=F2​\(−F1−1​\(1−α\)\),\\mathrm\{Opt\}\(\\alpha\)=F\_\{2\}\\\!\\left\(\-F\_\{1\}^\{\-1\}\(1\-\\alpha\)\\right\),whereF1−1F\_\{1\}^\{\-1\}denotes the generalized inverse

F1−1​\(u\):=inf\{t∈ℝ:F1​\(t\)≥u\}\.F\_\{1\}^\{\-1\}\(u\):=\\inf\\\{t\\in\\mathbb\{R\}:F\_\{1\}\(t\)\\geq u\\\}\.

###### Proof\.

LetPPandQQdenote the densities ofℳ​\(X\)\\mathcal\{M\}\(X\)andℳ​\(X′\)\\mathcal\{M\}\(X^\{\\prime\}\), respectively\. By Lemma[E\.2](https://arxiv.org/html/2605.21780#A5.Thmtheorem2), the infimum overϕ∈ℋ\\phi\\in\\mathcal\{H\}in Equation equation[1](https://arxiv.org/html/2605.21780#S3.E1)is attained by a likelihood–ratio test\. Hence, there exists a thresholdκ≥0\\kappa\\geq 0such that the optimal test is

ϕ⋆​\(z\)=𝟙​\{P​\(z\)Q​\(z\)≥κ\},\\phi^\{\\star\}\(z\)=\\mathbbm\{1\}\\\!\\left\\\{\\frac\{P\(z\)\}\{Q\(z\)\}\\geq\\kappa\\right\\\},whereκ\\kappais chosen so that𝔼z∼P​\[ϕ⋆​\(z\)\]=α\\mathbb\{E\}\_\{z\\sim P\}\[\\phi^\{\\star\}\(z\)\]=\\alpha\.

Define the privacy\-loss random variablesL1:=log⁡P​\(y\)Q​\(y\)L\_\{1\}:=\\log\\frac\{P\(y\)\}\{Q\(y\)\}fory∼Py\\sim PandL2:=log⁡Q​\(y\)P​\(y\)L\_\{2\}:=\\log\\frac\{Q\(y\)\}\{P\(y\)\}fory∼Qy\\sim Q, and letF1F\_\{1\}andF2F\_\{2\}denote their cumulative distribution functions\.

Taking logarithms in the definition ofϕ⋆\\phi^\{\\star\}givesϕ⋆​\(y\)=𝟙​\{L1​\(y\)≥τ\}\\phi^\{\\star\}\(y\)=\\mathbbm\{1\}\\\{L\_\{1\}\(y\)\\geq\\tau\\\}, whereτ:=log⁡κ\\tau:=\\log\\kappa\. The constraint𝔼y∼P​\[ϕ⋆​\(y\)\]=α\\mathbb\{E\}\_\{y\\sim P\}\[\\phi^\{\\star\}\(y\)\]=\\alphatherefore becomesℙy∼P​\[L1​\(y\)≥τ\]=α\\mathbb\{P\}\_\{y\\sim P\}\[L\_\{1\}\(y\)\\geq\\tau\]=\\alpha, which is equivalent toF1​\(τ\)=1−αF\_\{1\}\(\\tau\)=1\-\\alpha\. By definition of the generalized inverse,τ=F1−1​\(1−α\)\\tau=F\_\{1\}^\{\-1\}\(1\-\\alpha\)\.

It remains to express the optimal value\. By Lemma[E\.2](https://arxiv.org/html/2605.21780#A5.Thmtheorem2),

Opt​\(α\)=ℙy∼Q​\[P​\(y\)Q​\(y\)≥κ\]=ℙy∼Q​\[L2​\(y\)≤−τ\]\.\\mathrm\{Opt\}\(\\alpha\)=\\mathbb\{P\}\_\{y\\sim Q\}\\\!\\left\[\\frac\{P\(y\)\}\{Q\(y\)\}\\geq\\kappa\\right\]=\\mathbb\{P\}\_\{y\\sim Q\}\[L\_\{2\}\(y\)\\leq\-\\tau\]\.Substitutingτ=F1−1​\(1−α\)\\tau=F\_\{1\}^\{\-1\}\(1\-\\alpha\)and using the definition of the CDFF2F\_\{2\}yields

Opt​\(α\)=F2​\(−F1−1​\(1−α\)\),\\mathrm\{Opt\}\(\\alpha\)=F\_\{2\}\\\!\\left\(\-F\_\{1\}^\{\-1\}\(1\-\\alpha\)\\right\),which proves the claim\.

∎

We now recall the tight characterization of the composition of randomized mechanisms from theff\-DP perspective\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]and express it in terms of privacy–loss distributions\. Letℳ1\\mathcal\{M\}\_\{1\}andℳ2\\mathcal\{M\}\_\{2\}be two randomized mechanisms with dominating pairs\(P1,Q1\)\(P\_\{1\},Q\_\{1\}\)and\(P2,Q2\)\(P\_\{2\},Q\_\{2\}\), respectively\. It is shown in\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]that the composed mechanismℳ2∘ℳ1\\mathcal\{M\}\_\{2\}\\circ\\mathcal\{M\}\_\{1\}admits the product pair

\(P1×P2,Q1×Q2\)\(P\_\{1\}\\times P\_\{2\},\\;Q\_\{1\}\\times Q\_\{2\}\)as a dominating pair, where×\\timesdenotes the product \(independent\) distribution\.\.

We now express the tradeoff function of the composition using Theorem[D\.5](https://arxiv.org/html/2605.21780#A4.Thmtheorem5)\. Let

L1:=log⁡P1​\(y1\)Q1​\(y1\),y1∼P1,L\_\{1\}:=\\log\\frac\{P\_\{1\}\(y\_\{1\}\)\}\{Q\_\{1\}\(y\_\{1\}\)\},\\qquad y\_\{1\}\\sim P\_\{1\},and

L2:=log⁡P2​\(y2\)Q2​\(y2\),y2∼P2,L\_\{2\}:=\\log\\frac\{P\_\{2\}\(y\_\{2\}\)\}\{Q\_\{2\}\(y\_\{2\}\)\},\\qquad y\_\{2\}\\sim P\_\{2\},denote the privacy\-loss random variables of the two mechanisms, and letF1F\_\{1\}andF2F\_\{2\}be their cumulative distribution functions\.

For the composed mechanism, the privacy\-loss random variable becomes

L​\(y1,y2\)\\displaystyle L\(y\_\{1\},y\_\{2\}\)=log⁡P1​\(y1\)​P2​\(y2\)Q1​\(y1\)​Q2​\(y2\),y1∼P1,y2∼P2\\displaystyle=\\log\\frac\{P\_\{1\}\(y\_\{1\}\)P\_\{2\}\(y\_\{2\}\)\}\{Q\_\{1\}\(y\_\{1\}\)Q\_\{2\}\(y\_\{2\}\)\},\\qquad y\_\{1\}\\sim P\_\{1\},\\;y\_\{2\}\\sim P\_\{2\}=L1​\(y1\)\+L2​\(y2\)\.\\displaystyle=L\_\{1\}\(y\_\{1\}\)\+L\_\{2\}\(y\_\{2\}\)\.Hence, the PLD of the composition is the distribution of the sumL1\+L2L\_\{1\}\+L\_\{2\}\. Applying Theorem[D\.5](https://arxiv.org/html/2605.21780#A4.Thmtheorem5)to the product pair\(P1×P2,Q1×Q2\)\(P\_\{1\}\\times P\_\{2\},\\;Q\_\{1\}\\times Q\_\{2\}\)yields that the tradeoff function of the composed mechanism is

Optℳ2∘ℳ1​\(α\)=FL1\+L2\(Q\)​\(−\(FL1\+L2\(P\)\)−1​\(1−α\)\),\\mathrm\{Opt\}\_\{\\mathcal\{M\}\_\{2\}\\circ\\mathcal\{M\}\_\{1\}\}\(\\alpha\)=F^\{\(Q\)\}\_\{L\_\{1\}\+L\_\{2\}\}\\\!\\left\(\-\\left\(F^\{\(P\)\}\_\{L\_\{1\}\+L\_\{2\}\}\\right\)^\{\-1\}\(1\-\\alpha\)\\right\),whereFL1\+L2\(P\)F^\{\(P\)\}\_\{L\_\{1\}\+L\_\{2\}\}andFL1\+L2\(Q\)F^\{\(Q\)\}\_\{L\_\{1\}\+L\_\{2\}\}denote the CDFs ofL1\+L2L\_\{1\}\+L\_\{2\}underP1×P2P\_\{1\}\\times P\_\{2\}andQ1×Q2Q\_\{1\}\\times Q\_\{2\}, respectively\. In particular, evaluating the tradeoff function for the composition reduces to computing the cumulative distribution function of the sumL1\+L2L\_\{1\}\+L\_\{2\}, that is, the convolution of the two privacy\-loss distributions\. Therefore, to obtain an analytic expression for the tradeoff function of a composition, it is important that the convolution of the Privacy\-loss distributions can be computed explicitly\. For a general mechanism, this may be intractable, but it works for the Gaussian mechanism, as shown inDonget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\], Lyuet al\.\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\.

#### Example: Gaussian mechanisms\.

Letℳ\\mathcal\{M\}be a Gaussian mechanism with standard deviationσ\\sigma, consider the dominating pair

P=𝒩​\(Δ,σ2\),Q=𝒩​\(0,σ2\)\.P=\\mathcal\{N\}\(\\Delta,\\sigma^\{2\}\),\\qquad Q=\\mathcal\{N\}\(0,\\sigma^\{2\}\)\.The log\-likelihood ratio is

L​\(y\)=log⁡d​Pd​Q​\(y\)=Δ22​σ2−Δσ2​y,L\(y\)=\\log\\frac\{dP\}\{dQ\}\(y\)=\\frac\{\\Delta^\{2\}\}\{2\\sigma^\{2\}\}\-\\frac\{\\Delta\}\{\\sigma^\{2\}\}y,which is Gaussian undery∼Py\\sim P\. Therefore, the PLD of each mechanism is Gaussian, and the PLD of a composition, given by the sumL1\+L2L\_\{1\}\+L\_\{2\}of independent Gaussian PLDs, is also Gaussian\. Computing the convolution then reduces to simple addition of means and variances, which makes analytic computation of the tradeoff function straightforward, as done inDonget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\], Lyuet al\.\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\.

We next outline the settings in which the primal perspective works and those in which it does not\.

#### Simple Mechanisms

Various mechanisms, such as Gaussian, Laplacian, and Uniform, have been extensively analyzed using the Neyman–Pearson lemma for evasion robustness\[[9](https://arxiv.org/html/2605.21780#bib.bib43),[69](https://arxiv.org/html/2605.21780#bib.bib75),[75](https://arxiv.org/html/2605.21780#bib.bib76)\]\. While the composition of Gaussian mechanisms has been analyzed inDonget al\.\[[12](https://arxiv.org/html/2605.21780#bib.bib55)\]\.

#### Subsampled Gaussian Mechanisms

Analyzing subsampled Gaussian mechanisms using the Neyman–Pearson lemma is challenging\[[58](https://arxiv.org/html/2605.21780#bib.bib74)\]\. However, we need compositions of such mechanisms to obtain poisoning and joint robustness guarantees while using DP\-SGD for training\.

#### Heterogeneous Composition

In general, the primal DP characterization of heterogeneous compositions is not tractable\. However, we need such compositions to combine mechanisms such as DP\-SGD with Gaussian mechanisms or DPA with DP\-SGD\. In contrast, we show in Theorem[5\.1](https://arxiv.org/html/2605.21780#S5.Thmtheorem1)that DPA can be analytically composed with a base mechanism that admits a tractable primal characterization\.

## Appendix ERandomized Smoothing\-based Certification

We first introduce standard randomized smoothing through a Neyman\-Pearson hypothesis testing formulation\[[9](https://arxiv.org/html/2605.21780#bib.bib43),[40](https://arxiv.org/html/2605.21780#bib.bib51)\]\. We then present its reinterpretation through the lens offf\-differential privacy, following\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\. We begin by defining a smoothed classifier induced by a randomized mechanismℳ\\mathcal\{M\}together with a collection of hypothesis tests\{ϕi\}i=1C\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{C\}\.

###### Definition E\.1\(CC\-Class Smoothed Classifier\)\.

Letℳ\\mathcal\{M\}be a randomized mechanism mapping an input𝐗∈𝕏\\mathbf\{X\}\\in\\mathbb\{X\}to an intermediate space𝕐\\mathbb\{Y\}\. Let\{ϕi\}i=1C\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{C\}be a collection of hypothesis tests

ϕi:𝕐→\(\{0,1\}\),i∈\{1,…,C\},\\phi\_\{i\}:\\mathbb\{Y\}\\to\(\\\{0,1\\\}\),\\quad i\\in\\\{1,\\dots,C\\\},withϕC=1−∑i≠Cϕi\\phi\_\{C\}=1\-\\sum\_\{i\\neq C\}\\phi\_\{i\}\. The corresponding smoothed class probabilities are defined as

pi:=𝔼y∼ℳ\(⋅∣𝐗\)​\[ϕi​\(y\)\],i∈\{1,…,C\}\.p\_\{i\}\\;:=\\;\\mathbb\{E\}\_\{y\\sim\\mathcal\{M\}\(\\cdot\\mid\\mathbf\{X\}\)\}\\bigl\[\\phi\_\{i\}\(y\)\\bigr\],\\quad i\\in\\\{1,\\dots,C\\\}\.The induced smoothed classifier predicts the label

argmaxi∈\{1,…,C\}⁡pi\.\\operatorname\{\\rm\{argmax\}\}\_\{i\\in\\\{1,\\dots,C\\\}\}\\;p\_\{i\}\.

For example, in Gaussian smoothing\[[55](https://arxiv.org/html/2605.21780#bib.bib68),[9](https://arxiv.org/html/2605.21780#bib.bib43),[77](https://arxiv.org/html/2605.21780#bib.bib69)\], a Gaussian randomized mechanism𝒢σ:ℝD→ℝD\\mathcal\{G\}\_\{\\sigma\}:\\mathbb\{R\}^\{D\}\\to\\mathbb\{R\}^\{D\}is applied to an input𝐱∈ℝD\\mathbf\{x\}\\in\\mathbb\{R\}^\{D\}, producing a Gaussian distribution𝒢σ​\(𝐱\):=𝒩​\(𝐱,σ2​𝕀D\)\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\):=\\mathcal\{N\}\(\\mathbf\{x\},\\sigma^\{2\}\\mathbb\{I\}\_\{D\}\)overℝD\\mathbb\{R\}^\{D\}\. A neural network is then applied as a hypothesis test, and the expectation over the Gaussian noise yields the smoothed prediction\.

#### Certification as an Optimization Problem

Certifying the robustness of smoothed classifiers at an input pointXXcan be reduced to solving optimization problems of the form

Opt​\(α\):=infϕ∈ℋinfd​\(X,X′\)≤δ\\displaystyle\\text\{Opt\}\(\\alpha\)=\\inf\_\{\\phi\\in\\mathcal\{H\}\}\\inf\_\{d\(X,X^\{\\prime\}\)\\leq\\delta\}𝔼x∼ℳ​\(X′\)​\[ϕ​\(x\)\]\\displaystyle\\;\\mathbb\{E\}\_\{x\\sim\\mathcal\{M\}\(X^\{\\prime\}\)\}\[\\phi\(x\)\]\(6\)s\.t\.𝔼x∼ℳ​\(X\)​\[ϕ​\(x\)\]=α\.\\displaystyle\\;\\mathbb\{E\}\_\{x\\sim\\mathcal\{M\}\(X\)\}\[\\phi\(x\)\]=\\alpha\.whereℋ\\mathcal\{H\}denotes a class of hypothesis tests andd​\(⋅,⋅\)d\(\\cdot,\\cdot\)measures the distance between inputs\[[78](https://arxiv.org/html/2605.21780#bib.bib73)\]\.

In the multiclass setting, we consider a collection of class\-wise hypothesis tests\. Letpmp\_\{m\}denote the expected value of the hypothesis test corresponding to the predicted \(majority\) class, and letpip\_\{i\}denote the expected value of the test corresponding to any other classi≠mi\\neq m\. To certify robustness, we must compare the worst\-case value of the predicted class with the worst\-case value of any competing class\. In particular, we compute the worst\-case lower bound for the predicted class,OPT​\(pm\)\\mathrm\{OPT\}\(p\_\{m\}\), and the worst\-case upper bound for every other class, which can be written as1−OPT​\(1−pi\)1\-\\mathrm\{OPT\}\(1\-p\_\{i\}\)\. Robustness is certified whenever

OPT​\(pm\)\>maxi≠m⁡\(1−OPT​\(1−pi\)\)\.\\mathrm\{OPT\}\(p\_\{m\}\)\>\\max\_\{i\\neq m\}\\left\(1\-\\mathrm\{OPT\}\(1\-p\_\{i\}\)\\right\)\.We now state the Neyman–Pearson lemma\[[49](https://arxiv.org/html/2605.21780#bib.bib70)\]and anff\-DP–based reformulation to characterize the optimization overℋ\\mathcal\{H\}in Equation[1](https://arxiv.org/html/2605.21780#S3.E1)\.

###### Lemma E\.2\(Neyman–Pearson Characterization\[[49](https://arxiv.org/html/2605.21780#bib.bib70)\]\)\.

For fixX,X′X,X^\{\\prime\}andα∈\[0,1\]\\alpha\\in\[0,1\], the infimum overϕ∈ℋ\\phi\\in\\mathcal\{H\}in Equation equation[1](https://arxiv.org/html/2605.21780#S3.E1)is attained by a likelihood–ratio test\. In particular, there exists a thresholdκ≥0\\kappa\\geq 0such that the optimal hypothesis testϕ⋆∈ℋ\\phi^\{\\star\}\\in\\mathcal\{H\}is given by

ϕ⋆​\(z\)=1​\{d​ℳ​\(X\)d​ℳ​\(X′\)​\(z\)≥κ\},\\phi^\{\\star\}\(z\)\\;=\\;\\mathbbm\{1\}\\\!\\left\\\{\\frac\{d\\mathcal\{M\}\(X\)\}\{d\\mathcal\{M\}\(X^\{\\prime\}\)\}\(z\)\\geq\\kappa\\right\\\},whereκ\\kappais chosen to satisfy

𝔼z∼ℳ​\(X\)​\[ϕ⋆​\(z\)\]=α\.\\mathbb\{E\}\_\{z\\sim\\mathcal\{M\}\(X\)\}\[\\phi^\{\\star\}\(z\)\]=\\alpha\.The corresponding optimal value is

Opt​\(α\)=ℙz∼ℳ​\(X′\)​\[d​ℳ​\(X\)d​ℳ​\(X′\)​\(z\)≥κ\]\.\\text\{Opt\}\(\\alpha\)=\\mathbb\{P\}\_\{z\\sim\\mathcal\{M\}\(X^\{\\prime\}\)\}\\\!\\left\[\\frac\{d\\mathcal\{M\}\(X\)\}\{d\\mathcal\{M\}\(X^\{\\prime\}\)\}\(z\)\\geq\\kappa\\right\]\.

###### Lemma E\.3\(ff\-DP Reformulation of Robustness Certification\[[46](https://arxiv.org/html/2605.21780#bib.bib56)\]\)\.

Let∼δ\\sim\_\{\\delta\}be the relation defined by

X∼δX′if and only ifd​\(X,X′\)≤δ\.X\\sim\_\{\\delta\}X^\{\\prime\}\\quad\\text\{if and only if\}\\quad d\(X,X^\{\\prime\}\)\\leq\\delta\.If the mechanismℳ\\mathcal\{M\}satisfiesff\-differential privacy with respect to∼δ\\sim\_\{\\delta\}, then

Opt​\(α\)≥f​\(1−α\)\.\\text\{Opt\}\(\\alpha\)\\;\\geq\\;f\(1\-\\alpha\)\.

#### Smooth Joint Training\-Test Procedure

We introduce the randomized smoothing framework for a joint training–test procedure\. This formulation subsumes robustness guarantees for the training algorithm alone and inference\-time robustness as special cases\.

###### Definition E\.4\(Randomized Joint Training–Test Procedure\)\.

A randomized joint training–test procedure𝒥\\mathcal\{J\}forCC\-class classification operates as follows\. Given an input\(𝐗train,𝐱test\)∈⋃i=1∞Ti×𝕏\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)\\;\\in\\;\\bigcup\_\{i=1\}^\{\\infty\}T\_\{i\}\\times\\mathbb\{X\}, the procedure first applies a randomized mechanism

ℳ:⋃i=1∞Ti×𝕏→𝕐,\\mathcal\{M\}:\\bigcup\_\{i=1\}^\{\\infty\}T\_\{i\}\\times\\mathbb\{X\}\\;\\to\\;\\mathbb\{Y\},mapping the input to an intermediate space𝕐\\mathbb\{Y\}\. This is followed by a collection ofCChypothesis tests

ϕi:𝕐→\{0,1\},i∈\{1,…,C\},\\phi\_\{i\}:\\mathbb\{Y\}\\to\\\{0,1\\\},\\qquad i\\in\\\{1,\\dots,C\\\},withϕC=1−∑i≠Cϕi\\phi\_\{C\}\\;=\\;1\-\\sum\_\{i\\neq C\}\\phi\_\{i\}\. For eachi∈\{1,…,C\}i\\in\\\{1,\\dots,C\\\}, the corresponding expected value

𝔼y∼ℳ​\(𝐗train,𝐱test\)​\[ϕi​\(y\)\]\\mathbb\{E\}\_\{y\\sim\\mathcal\{M\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)\}\\bigl\[\\phi\_\{i\}\(y\)\\bigr\]defines the \(smoothed\) probability of predicting classii\. The final prediction of the procedure is given by

argmaxi∈\{1,…,C\}⁡𝔼y∼ℳ​\(𝐗train,𝐱test\)​\[ϕi​\(y\)\]\.\\operatorname\{\\rm\{argmax\}\}\_\{i\\in\\\{1,\\dots,C\\\}\}\\mathbb\{E\}\_\{y\\sim\\mathcal\{M\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)\}\\bigl\[\\phi\_\{i\}\(y\)\\bigr\]\.

#### Example: DPSGD and Inference\-Time Gaussian Noise

Letℳi\\mathcal\{M\}\_\{i\}denote the randomized mechanism corresponding to theii\-th iteration of DP\-SGD\. AfterIIiterations, the composed training\-time mechanism\.

ℳtrain:=ℳI∘ℳI−1∘⋯∘ℳ1\\mathcal\{M\}\_\{\\text\{train\}\}\\;:=\\;\\mathcal\{M\}\_\{I\}\\circ\\mathcal\{M\}\_\{I\-1\}\\circ\\cdots\\circ\\mathcal\{M\}\_\{1\}is applied to the training dataset𝐗train\\mathbf\{X\}\_\{\\text\{train\}\}, inducing a distributionℳtrain​\(𝐗train\)\\mathcal\{M\}\_\{\\text\{train\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\)over the learned network parametersww\. At inference time, an additional Gaussian randomized mechanism𝒢σ​\(𝐱test\):=𝒩​\(𝐱test,σ2​𝕀\)\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\_\{\\text\{test\}\}\):=\\mathcal\{N\}\(\\mathbf\{x\}\_\{\\text\{test\}\},\\sigma^\{2\}\\mathbb\{I\}\)is applied to the test input\. The overall randomized joint training–test mechanism is thus given by

ℳ​\(𝐗train,𝐱test\)=\(w∼ℳtrain​\(𝐗train\),𝐱~∼𝒢σ​\(𝐱test\)\)\.\\mathcal\{M\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)\\;=\\;\\bigl\(w\\sim\\mathcal\{M\}\_\{\\text\{train\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\),\\;\\tilde\{\\mathbf\{x\}\}\\sim\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\_\{\\text\{test\}\}\)\\bigr\)\.A collection of hypothesis tests\{ϕi\}i=1C\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{C\}, typically implemented as the components of a neural network’s softmax output, maps the pair\(w,𝐱~\)\(w,\\tilde\{\\mathbf\{x\}\}\)to class\-wise predictions\. The smoothed probability of predicting classiiis given by

pi=𝔼\(w,𝐱~\)∼ℳ​\(𝐗train,𝐱test\)​\[ϕi​\(w,𝐱~\)\],i∈\{1,…,C\}\.p\_\{i\}\\;=\\;\\mathbb\{E\}\_\{\(w,\\tilde\{\\mathbf\{x\}\}\)\\sim\\mathcal\{M\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)\}\\bigl\[\\phi\_\{i\}\(w,\\tilde\{\\mathbf\{x\}\}\)\\bigr\],\\qquad i\\in\\\{1,\\dots,C\\\}\.

#### Example: DPA and Inference\-Time Noise

DPA applies a deterministic partitioning functionHHand maps the training dataset𝐗train∈⋃i=1∞Ti\\mathbf\{X\}\_\{\\text\{train\}\}\\in\\bigcup\_\{i=1\}^\{\\infty\}T\_\{i\}to a collection ofNNdisjoint subsets𝐘:=\{Y1,…,YN\},\\mathbf\{Y\}:=\\\{Y\_\{1\},\\dots,Y\_\{N\}\\\},where each partitionYi∈⋃i=1∞TiY\_\{i\}\\in\\bigcup\_\{i=1\}^\{\\infty\}T\_\{i\}is itself a dataset\. The mechanismℳDPA\\mathcal\{M\}\_\{\\text\{DPA\}\}samples a partitionYiY\_\{i\}to get a distributionℳDPA​\(𝐗train\)\\mathcal\{M\_\{\\text\{DPA\}\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\), over the partitions \(training datasets\)\. Finally, a model is trained on the sampled dataset, and at inference time𝒢σ\\mathcal\{G\}\_\{\\sigma\}is applied to the test data, yielding a joint training–test mechanismℳ​\(𝐗train,𝐱test\)=\(Yi∼ℳtrain​\(𝐗train\),𝐱~∼𝒢σ​\(𝐱test\)\)\\mathcal\{M\}\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)=\\bigl\(Y\_\{i\}\\sim\\mathcal\{M\}\_\{\\text\{train\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\),\\;\\tilde\{\\mathbf\{x\}\}\\sim\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\_\{\\text\{test\}\}\)\\bigr\)\. The process of training a model and evaluation class prediction at the noisy test sample is modeled by a collection of hypothesis tests\{ϕi\}i=1C\\\{\\phi\_\{i\}\\\}\_\{i=1\}^\{C\}, leading to class probabilities as for a given\(𝐗train,𝐱test\)\(\\mathbf\{X\}\_\{\\text\{train\}\},\\mathbf\{x\}\_\{\\text\{test\}\}\)pair,

pi=𝔼Y∼ℳtrain​\(𝐗train\),𝐱~∼𝒢σ​\(𝐱test\)​\[ϕi​\(Y,𝐱~\)\]\.p\_\{i\}=\\mathbb\{E\}\_\{Y\\sim\\mathcal\{M\}\_\{\\text\{train\}\}\(\\mathbf\{X\}\_\{\\text\{train\}\}\),\\tilde\{\\mathbf\{x\}\}\\sim\\mathcal\{G\}\_\{\\sigma\}\(\\mathbf\{x\}\_\{\\text\{test\}\}\)\}\[\\phi\_\{i\}\(Y,\\tilde\{\\mathbf\{x\}\}\)\]\.

## Appendix FCorrected group privacy analysis of Sub\-sampled Gaussian using Rényi\-DP

This section presents a corrected version of the group privacy guarantee for the Sub\-sampled Gaussian Mechanism \(SGM\) derived in\[[43](https://arxiv.org/html/2605.21780#bib.bib61), Theorem 8\]\. The issue is that the supporting theorem used in the original argument assumes that the underlying functionffhasℓ2\\ell\_\{2\}\-sensitivity at most11with respect to datasets differing in up torrexamples\. However, in the application to Theorem88, the assumption is thatffhasℓ2\\ell\_\{2\}\-sensitivity at most11for datasets differing in one example\. Consequently, for datasets differing in up torrexamples, the worst\-caseℓ2\\ell\_\{2\}\-sensitivity is at mostrr, not11\.

###### Theorem F\.1\(Corrected improved Rényi\-DP group privacy for SGM\)\.

Letℳ\\mathcal\{M\}be the Sub\-sampled Gaussian Mechanism \(SGM\) with sampling probabilityqqand Gaussian noise varianceσ2​Id\\sigma^\{2\}I\_\{d\}\. Suppose that the underlying functionffhas single\-exampleℓ2\\ell\_\{2\}\-sensitivity at most11, i\.e\., for any pair of datasetsD,D′D,D^\{\\prime\}differing in one example,

‖f​\(D\)−f​\(D′\)‖2≤1\.\\\|f\(D\)\-f\(D^\{\\prime\}\)\\\|\_\{2\}\\leq 1\.LetD1D\_\{1\}andD3D\_\{3\}be two datasets such that

D3∈ℬ​\(D1,r\),D\_\{3\}\\in\\mathcal\{B\}\(D\_\{1\},r\),i\.e\.,D1D\_\{1\}andD3D\_\{3\}differ in at mostrrexamples\. Then, for any orderα\>1\\alpha\>1,

Dα​\(ℳ​\(D1\)∥ℳ​\(D3\)\)≤SG​\(α,1−\(1−q\)r,σr\),D\_\{\\alpha\}\\bigl\(\\mathcal\{M\}\(D\_\{1\}\)\\,\\\|\\,\\mathcal\{M\}\(D\_\{3\}\)\\bigr\)\\leq\\mathrm\{SG\}\\\!\\left\(\\alpha,1\-\(1\-q\)^\{r\},\\frac\{\\sigma\}\{r\}\\right\),and similarly,

Dα​\(ℳ​\(D3\)∥ℳ​\(D1\)\)≤SG​\(α,1−\(1−q\)r,σr\)\.D\_\{\\alpha\}\\bigl\(\\mathcal\{M\}\(D\_\{3\}\)\\,\\\|\\,\\mathcal\{M\}\(D\_\{1\}\)\\bigr\)\\leq\\mathrm\{SG\}\\\!\\left\(\\alpha,1\-\(1\-q\)^\{r\},\\frac\{\\sigma\}\{r\}\\right\)\.
Here, for sampling probabilityq¯\\bar\{q\}and noise levelσ¯\\bar\{\\sigma\},SG​\(α,q¯,σ¯\)\\mathrm\{SG\}\(\\alpha,\\bar\{q\},\\bar\{\\sigma\}\)denotes the standard Rényi\-DP bound for the unit\-sensitivity Sub\-sampled Gaussian Mechanism:

SG\(α,q¯,σ¯\):=max\{Dα\(𝒩\(0,σ¯2\)∥\(1−q¯\)𝒩\(0,σ¯2\)\+q¯𝒩\(1,σ¯2\)\),\\mathrm\{SG\}\(\\alpha,\\bar\{q\},\\bar\{\\sigma\}\):=\\max\\left\\\{D\_\{\\alpha\}\\\!\\left\(\\mathcal\{N\}\(0,\\bar\{\\sigma\}^\{2\}\)\\;\\middle\\\|\\;\(1\-\\bar\{q\}\)\\mathcal\{N\}\(0,\\bar\{\\sigma\}^\{2\}\)\+\\bar\{q\}\\,\\mathcal\{N\}\(1,\\bar\{\\sigma\}^\{2\}\)\\right\),\\right\.Dα\(\(1−q¯\)𝒩\(0,σ¯2\)\+q¯𝒩\(1,σ¯2\)∥𝒩\(0,σ¯2\)\)\}\.\\left\.D\_\{\\alpha\}\\\!\\left\(\(1\-\\bar\{q\}\)\\mathcal\{N\}\(0,\\bar\{\\sigma\}^\{2\}\)\+\\bar\{q\}\\,\\mathcal\{N\}\(1,\\bar\{\\sigma\}^\{2\}\)\\;\\middle\\\|\\;\\mathcal\{N\}\(0,\\bar\{\\sigma\}^\{2\}\)\\right\)\\right\\\}\.

###### Proof\.

LetS,S′S,S^\{\\prime\}be a pair of datasets that differ inrrexamples, and write

S′=S∪\{x1,…,xr\}\.S^\{\\prime\}=S\\cup\\\{x\_\{1\},\\ldots,x\_\{r\}\\\}\.Following the argument of\[[43](https://arxiv.org/html/2605.21780#bib.bib61), Theorem 10\], using quasi\-convexity of Rényi divergence, we obtain

Dα​\(ℳ​\(S\)∥ℳ​\(S′\)\)\\displaystyle D\_\{\\alpha\}\(\\mathcal\{M\}\(S\)\\\|\\mathcal\{M\}\(S^\{\\prime\}\)\)≤supTDα\(𝒩\(0,σ2Id\)∥∑V⊆\{x1,…,xr\}q\|V\|​\(1−q\)r−\|V\|⋅𝒩​\(f​\(T∪V\)−f​\(T\),σ2​Id\)\)\.\\displaystyle\\leq\\sup\_\{T\}D\_\{\\alpha\}\\left\(\\mathcal\{N\}\(0,\\sigma^\{2\}I\_\{d\}\)\\;\\middle\\\|\\;\\begin\{aligned\} &\\sum\_\{V\\subseteq\\\{x\_\{1\},\\ldots,x\_\{r\}\\\}\}q^\{\|V\|\}\(1\-q\)^\{r\-\|V\|\}\\\\ &\\qquad\\qquad\\cdot\\mathcal\{N\}\(f\(T\\cup V\)\-f\(T\),\\sigma^\{2\}I\_\{d\}\)\\end\{aligned\}\\right\)\.
Correction:The key correction is the following sensitivity bound\. Sinceffhas single\-exampleℓ2\\ell\_\{2\}\-sensitivity at most11, for everyV⊆\{x1,…,xr\}V\\subseteq\\\{x\_\{1\},\\ldots,x\_\{r\}\\\},

‖f​\(T∪V\)−f​\(T\)‖2≤\|V\|≤r\.\\\|f\(T\\cup V\)\-f\(T\)\\\|\_\{2\}\\leq\|V\|\\leq r\.Using the rotational symmetry of the Gaussian noise and the additivity of Rényi divergence for product distributions, the above is bounded by the one\-dimensional worst case

Dα\(ℳ\(S\)∥ℳ\(S′\)\)≤supc≤rDα\(𝒩\(0,σ2\)∥\(1−q\)r𝒩\(0,σ2\)\+\(1−\(1−q\)r\)𝒩\(c,σ2\)\)\.D\_\{\\alpha\}\(\\mathcal\{M\}\(S\)\\\|\\mathcal\{M\}\(S^\{\\prime\}\)\)\\leq\\sup\_\{c\\leq r\}D\_\{\\alpha\}\\left\(\\mathcal\{N\}\(0,\\sigma^\{2\}\)\\;\\middle\\\|\\;\(1\-q\)^\{r\}\\mathcal\{N\}\(0,\\sigma^\{2\}\)\+\\bigl\(1\-\(1\-q\)^\{r\}\\bigr\)\\mathcal\{N\}\(c,\\sigma^\{2\}\)\\right\)\.Equivalently,

Dα​\(ℳ​\(S\)∥ℳ​\(S′\)\)\\displaystyle D\_\{\\alpha\}\(\\mathcal\{M\}\(S\)\\\|\\mathcal\{M\}\(S^\{\\prime\}\)\)≤supc′≤1Dα\(𝒩\(0,\(σ/\(rc′\)\)2\)∥\(1−q\)r​𝒩​\(0,\(σ/\(r​c′\)\)2\)\+\(1−\(1−q\)r\)​𝒩​\(1,\(σ/\(r​c′\)\)2\)\)\.\\displaystyle\\leq\\sup\_\{c^\{\\prime\}\\leq 1\}D\_\{\\alpha\}\\left\(\\mathcal\{N\}\(0,\(\\sigma/\(rc^\{\\prime\}\)\)^\{2\}\)\\;\\middle\\\|\\;\\begin\{aligned\} &\(1\-q\)^\{r\}\\mathcal\{N\}\(0,\(\\sigma/\(rc^\{\\prime\}\)\)^\{2\}\)\\\\ &\\quad\+\\bigl\(1\-\(1\-q\)^\{r\}\\bigr\)\\mathcal\{N\}\(1,\(\\sigma/\(rc^\{\\prime\}\)\)^\{2\}\)\\end\{aligned\}\\right\)\.
Follow the rest of the arguments of\[[43](https://arxiv.org/html/2605.21780#bib.bib61), Theorem 10\], to conclude:

Dα\(ℳ\(S\)∥ℳ\(S′\)\)≤Dα\(𝒩\(0,\(σ/r\)2\)∥\(1−q′\)𝒩\(0,\(σ/r\)2\)\+q′𝒩\(1,\(σ/r\)2\)\),D\_\{\\alpha\}\(\\mathcal\{M\}\(S\)\\\|\\mathcal\{M\}\(S^\{\\prime\}\)\)\\leq D\_\{\\alpha\}\\left\(\\mathcal\{N\}\(0,\(\\sigma/r\)^\{2\}\)\\;\\middle\\\|\\;\(1\-q^\{\\prime\}\)\\mathcal\{N\}\(0,\(\\sigma/r\)^\{2\}\)\+q^\{\\prime\}\\mathcal\{N\}\(1,\(\\sigma/r\)^\{2\}\)\\right\),where

q′=1−\(1−q\)r\.q^\{\\prime\}=1\-\(1\-q\)^\{r\}\.The reverse direction is identical and gives

Dα\(ℳ\(S′\)∥ℳ\(S\)\)≤Dα\(\(1−q′\)𝒩\(0,\(σ/r\)2\)\+q′𝒩\(1,\(σ/r\)2\)∥𝒩\(0,\(σ/r\)2\)\)\.D\_\{\\alpha\}\(\\mathcal\{M\}\(S^\{\\prime\}\)\\\|\\mathcal\{M\}\(S\)\)\\leq D\_\{\\alpha\}\\left\(\(1\-q^\{\\prime\}\)\\mathcal\{N\}\(0,\(\\sigma/r\)^\{2\}\)\+q^\{\\prime\}\\mathcal\{N\}\(1,\(\\sigma/r\)^\{2\}\)\\;\\middle\\\|\\;\\mathcal\{N\}\(0,\(\\sigma/r\)^\{2\}\)\\right\)\.Thus the sampled Gaussian mechanism satisfies the claimed bound with effective sampling probabilityq′=1−\(1−q\)rq^\{\\prime\}=1\-\(1\-q\)^\{r\}and effective noise levelσ/r\\sigma/r\. ∎

## Appendix GAmplification by random preprocessing

###### Theorem G\.1\.

LetXXandX′X^\{\\prime\}be datasets ofNNdd\-dimensional real\-valued vectors\. Assume that they are related via substitution ofKKrecords with bounded normrr, i\.e\., additive perturbation ofKKrecords withℓ2\\ell\_\{2\}\-normrr\. Consider the mechanismM​\(y∣X\)=∑𝐲∈\{0,1\}N∫B​\(y∣X~,𝐲\)​G​\(X~∣X\)⋅S​\(𝐲\)​dX~M\(y\\mid X\)=\\sum\_\{\{\\bm\{y\}\}\\in\\\{0,1\\\}^\{N\}\}\\int B\(y\\mid\\tilde\{X\},\{\\bm\{y\}\}\)G\(\\tilde\{X\}\\mid X\)\\cdot S\(\{\\bm\{y\}\}\)\\mathrm\{d\}\\tilde\{X\}, whereS​\(𝐲\)S\(\{\\bm\{y\}\}\)is a distribution over Poisson subsampling indicator vectors,G​\(X~∣X\)G\(\\tilde\{X\}\\mid X\)adds additive Gaussian noise with scaleσin\\sigma\_\{\\mathrm\{in\}\}to all samples and base mechanismB​\(y∣X~,𝐲\)B\(y\\mid\\tilde\{X\},\{\\bm\{y\}\}\)releases noisy clipped gradients only for samples withy=1y=1, i\.e\., DP\-SGD\. LetP,QP,Qbe a dominating pair ofBBunder insertion ofKKrecords and removal ofKKrecords inX~\\tilde\{X\}\. Then the additive noise subsampled mechanismMMadmits the following bound on its privacy profile for all neighboringX≃X′X\\simeq X^\{\\prime\}:

ℋα\(M\(⋅∣X\)\|\|M\(⋅∣X′\)\)≤TVD\(𝒩\(0,σin\)\|\|𝒩\(r,σin\)\)⋅ℋα\(P\|\|Q\),\\mathcal\{H\}\_\{\\alpha\}\(M\(\\cdot\\mid X\)\|\|M\(\\cdot\\mid X^\{\\prime\}\)\)\\leq\\mathrm\{TVD\}\(\\mathcal\{N\}\(0,\\sigma\_\{\\mathrm\{in\}\}\)\|\|\\mathcal\{N\}\(r,\\sigma\_\{\\mathrm\{in\}\}\)\)\\cdot\\mathcal\{H\}\_\{\\alpha\}\(P\|\|Q\),where TVD is the total variation distance of univariate Gaussians with scaleσin\\sigma\_\{\\mathrm\{in\}\}\.

###### Proof\.

Via post\-processing property of differential privacy, the mechanism is at least as private as a mechanismM′M^\{\\prime\}that releases all records but the substituted ones without any subsampling or additive noise\. This mechanismM′M^\{\\prime\}is equally private as only applying our original mechanismMMto theKKsubstituted records, i\.e\., we can analyze w\.l\.o\.g\. the setting whereN=KN=K, i\.e\., there are no non\-substituted records inSSandS′S^\{\\prime\}\. A standard result from optimal transport theory is that any pair of distributions admits a maximal coupling \(see\[[2](https://arxiv.org/html/2605.21780#bib.bib65)\]\) for a discussion in the context of differential privacy\. Via projection of this maximal coupling onto its marginals\[[2](https://arxiv.org/html/2605.21780#bib.bib65)\], we can show

G​\(X~∣X\)=\(1−w\)⋅G0\+w⋅G1\\displaystyle G\(\\tilde\{X\}\\mid X\)=\(1\-w\)\\cdot G\_\{0\}\+w\\cdot G\_\{1\}G​\(X~∣X′\)=\(1−w\)⋅G0\+w⋅G1′\\displaystyle G\(\\tilde\{X\}\\mid X^\{\\prime\}\)=\(1\-w\)\\cdot G\_\{0\}\+w\\cdot G\_\{1\}^\{\\prime\}with

w=TVD\(𝒩\(0,σin2𝐈\)\|\|𝒩\(r,σin2𝐈\)\)=TVD\(𝒩\(0,σin\)\|\|𝒩\(r,σin\)\)w=\\mathrm\{TVD\}\(\\mathcal\{N\}\(0,\\sigma\_\{\\mathrm\{in\}\}^\{2\}\\mathbf\{I\}\)\|\|\\mathcal\{N\}\(r,\\sigma\_\{\\mathrm\{in\}\}^\{2\}\\mathbf\{I\}\)\)=\\mathrm\{TVD\}\(\\mathcal\{N\}\(0,\\sigma\_\{\\mathrm\{in\}\}\)\|\|\\mathcal\{N\}\(r,\\sigma\_\{\\mathrm\{in\}\}\)\)where the last result follows from translation\-invariance of Gaussian f\-divergences\.

Define mechanisms

M0=M​\(y∣X\)=∑𝒚∈\{0,1\}N∫B​\(y∣X~,𝒚\)​G0​\(X~\)⋅S​\(𝒚\)​dX~\\displaystyle M\_\{0\}=M\(y\\mid X\)=\\sum\_\{\{\\bm\{y\}\}\\in\\\{0,1\\\}^\{N\}\}\\int B\(y\\mid\\tilde\{X\},\{\\bm\{y\}\}\)G\_\{0\}\(\\tilde\{X\}\)\\cdot S\(\{\\bm\{y\}\}\)\\mathrm\{d\}\\tilde\{X\}M1=M​\(y∣X\)=∑𝒚∈\{0,1\}N∫B​\(y∣X~,𝒚\)​G1​\(X~\)⋅S​\(𝒚\)​dX~\\displaystyle M\_\{1\}=M\(y\\mid X\)=\\sum\_\{\{\\bm\{y\}\}\\in\\\{0,1\\\}^\{N\}\}\\int B\(y\\mid\\tilde\{X\},\{\\bm\{y\}\}\)G\_\{1\}\(\\tilde\{X\}\)\\cdot S\(\{\\bm\{y\}\}\)\\mathrm\{d\}\\tilde\{X\}M1′=M​\(y∣X\)=∑𝒚∈\{0,1\}N∫B​\(y∣X~,𝒚\)​G1​\(X~\)⋅S​\(𝒚\)​dX~\\displaystyle M\_\{1\}^\{\\prime\}=M\(y\\mid X\)=\\sum\_\{\{\\bm\{y\}\}\\in\\\{0,1\\\}^\{N\}\}\\int B\(y\\mid\\tilde\{X\},\{\\bm\{y\}\}\)G\_\{1\}\(\\tilde\{X\}\)\\cdot S\(\{\\bm\{y\}\}\)\\mathrm\{d\}\\tilde\{X\}The hockey\-stick divergence is jointly convex in the space of distributions\[[2](https://arxiv.org/html/2605.21780#bib.bib65)\]and thus quasi\-convex\. It thus follows immediately that

ℋα\(M\(⋅∣X\)\|\|M\(⋅∣X′\)\)\\displaystyle\\mathcal\{H\}\_\{\\alpha\}\(M\(\\cdot\\mid X\)\|\|M\(\\cdot\\mid X^\{\\prime\}\)\)w≤Hα\(M1\(⋅\)\|\|M1′\(⋅\)\)\+\(1−w\)⋅Hα\(M0\(⋅\)\|\|M0′\(⋅\)\)\\displaystyle w\\leq H\_\{\\alpha\}\(M\_\{1\}\(\\cdot\)\|\|M^\{\\prime\}\_\{1\}\(\\cdot\)\)\+\(1\-w\)\\cdot H\_\{\\alpha\}\(M\_\{0\}\(\\cdot\)\|\|M^\{\\prime\}\_\{0\}\(\\cdot\)\)≤wHα\(M1\(⋅\)\|\|M1′\(⋅\)\)\\displaystyle\\leq wH\_\{\\alpha\}\(M\_\{1\}\(\\cdot\)\|\|M^\{\\prime\}\_\{1\}\(\\cdot\)\)≤wHα\(∑𝒚∈\{0,1\}NB\(y∣X~,𝒚\)⋅S\(𝒚\)\|\|∑𝒚∈\{0,1\}NB\(y∣X′~,𝒚\)⋅S\(𝒚\)\)\\displaystyle\\leq wH\_\{\\alpha\}\(\\sum\_\{\{\\bm\{y\}\}\\in\\\{0,1\\\}^\{N\}\}B\(y\\mid\\tilde\{X\},\{\\bm\{y\}\}\)\\cdot S\(\{\\bm\{y\}\}\)\|\|\\sum\_\{\{\\bm\{y\}\}\\in\\\{0,1\\\}^\{N\}\}B\(y\\mid\\tilde\{X^\{\\prime\}\},\{\\bm\{y\}\}\)\\cdot S\(\{\\bm\{y\}\}\)\)where the last step is due to quasi\-convexity applied to the additive noise distribution, andXXandX′X^\{\\prime\}are two arbitrary datasets withKKrecords\. By definition, any two datasets of sizeKKare related byKKinsertions andKKremovals\. The result then immediately follows from our assumption about dominance of\(P,Q\)\(P,Q\)\. ∎

## Appendix HAdditional experiments

![Refer to caption](https://arxiv.org/html/2605.21780v1/x8.png)Figure 8:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 10, with RDP\-based accounting and DPA using100100partitions for CIFAR\-10\.
![Refer to caption](https://arxiv.org/html/2605.21780v1/x9.png)Figure 9:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 12, with RDP\-based accounting and DPA using100100partitions for CIFAR\-10\.

![Refer to caption](https://arxiv.org/html/2605.21780v1/x10.png)Figure 10:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 15, with RDP\-based accounting and DPA using100100partitions for CIFAR\-10\.
![Refer to caption](https://arxiv.org/html/2605.21780v1/x11.png)Figure 11:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 10, with RDP\-based accounting and DPA using100,150,200100,150,200partitions for MNIST\.

![Refer to caption](https://arxiv.org/html/2605.21780v1/x12.png)Figure 12:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 12, with RDP\-based accounting and DPA using100,150,200100,150,200partitions for MNIST\.
![Refer to caption](https://arxiv.org/html/2605.21780v1/x13.png)Figure 13:Comparison of certified accuracies of our method \(Privacy Profile – Numerical\) for DP\-SGD with epoch 15, with RDP\-based accounting and DPA using100,150,200100,150,200partitions for MNIST\.