Certification-Based Differentially Private Learning

Mihnea Ghitu; Matthew Wicker

cs.LGSep 30, 2026

Certification-Based Differentially Private Learning

Authors: Mihnea Ghitu, Matthew Wicker

Organizations: Department of Computing Imperial College London London, United Kingdom

Abstract

Differential privacy (DP) in machine learning is typically achieved by adding noise to model parameters (private learning) or to model outputs (private prediction). Recent work uses formal methods, namely abstract interpretation, to provide tighter privacy guarantees, but only for private prediction in classification settings. In this work, we investigate the use of formal methods as a general tool for tighter privacy analysis. First, we generalize the abstract gradient training (AGT) framework to private prediction in continuous, unbounded regression. Second, by reducing learning in parameterized models to a regression problem over the parameter space, we introduce Abstract Gradient Sampling (AGS), an algorithm that enables reachability-based analysis to provide guarantees for private learning. In both private prediction and private learning, we provide tightened privacy accounting for the AGT framework and a theoretical analysis demonstrating when our smooth sensitivity upper-bounds yield favourable privacy-utility trade-off. In practice, we validate that our regression bounds are tighter than global-sensitivity baselines on regression benchmarks, and, notably, yield the first finite privacy guarantees in settings where global prediction sensitivity is a priori unbounded. We also find that under matched conditions, our private learning algorithm can outperform standard private learners.

Figures & tables

Figure 1 : Feasibility of smooth-sensitivity privatization. Each curve gives the largest sensitivity ratio $\rho=\mathrm{SS}^{\beta}/\Delta f$ for which our smooth-sensitivity mechanism attains a $c$ -times tighter error bound than the global-sensitivity baseline at confidence $1-\alpha$ ; the region below each curve is feasible. (a) Pure-DP (Thm. IV.3 ), Cauchy vs. Laplace; black dots mark the peak ratio. (b) Approx-DP (Thm. IV.4 ), Laplace vs. Gaussian, for $1-\alpha>0.8$ and measured against $\Delta_{2}f$ .

Panel of Figure 2 — Figure 2 : AGT-R on Linear and California under pure (left of each pair) and approximate (right) DP.

Figure 3 : Privacy–utility trade-offs of AGS for 5-class MNIST (left pair) and IMDB (right pair). AGS releases the trained parameters once (Cauchy mechanism under pure DP, Laplace under approximate DP, $\delta=10^{-5}$ ). Matched DP-SGD is accounted by basic composition or, under approximate DP, by exact composition of the Gaussian mechanism; optimized DP-SGD is tuned on a public selection set. On IMDB, the hidden-layer arms replace the logistic head with one hidden layer.

Figure 4 : Privacy–utility trade-offs of AGS on blobs. AGS certifies the parameter envelope with an exact MILP solved every $F$ training steps and releases the trained parameters once (Cauchy mechanism under pure DP, Laplace under approximate DP, $\delta=10^{-5}$ ). DP-SGD (matched) uses the same hyperparameters with basic composition. The dotted line marks the non-private accuracy. Medians over 100 noise draws.

Figure 5 : Hybrid approach on SST-2: a DP-LoRA fine-tuned encoder with an AGS head against end-to-end DP-LoRA fine-tuning and a frozen encoder with an AGS or a DP-SGD head. Test accuracy against the total budget $\epsilon=\epsilon_{1}+\epsilon_{2}$ under $(\epsilon,10^{-5})$ -DP (left), a pure-DP head (middle), and the private set size $N$ at $\epsilon=3$ effect on accuracy (right).

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6 : Shard ablation on the linear regression task with $4\!\times\!10^{3}$ training points, under pure DP. MAE against the number of shards $T$ at fixed dataset size, one line per budget $\epsilon\in[0.1,10]$ , for PATE-R (Laplace noise on global sensitivity), PATE-AGT-R (Cauchy noise on the shard-wise smooth sensitivity, $\beta=\epsilon/2$ ) and AGT-R on a single shard of $N/T$ points with the amplified budget $\epsilon_{b}$ ; dashed: the noise-free PATE mean.

Figure 7 : Cross-radius certificates of the AGT-R ablations (left: concretization frequency on linear regression; right: batch size on California Housing). Dashed, left axis: the certified local-sensitivity bound $\bar{A}(x,k)$ averaged over test inputs; solid, right axis: the smooth-sensitivity bound at $\beta=1/2$ , with its maximum starred; dotted: the global-sensitivity ceiling.

Figure 8 : The comparison of Figure 2(a) on the raw scale with global sensitivity (grey, dotted). MAE under pure DP and test MSE under approximate DP ( $\delta=10^{-5}$ ), each point the mean over 200 noise draws.

Figure 9 : Ablation of the number of releases (i.e., sampling steps) at different, fixed total privacy budgets on the UCI Census Income Dataset [ 53 ] . Left panel: test accuracy against the number of releases $n$ under $(\epsilon,10^{-5})$ -DP, with the per-release budget set by optimal composition (filled) or basic composition (hollow), against the non-private accuracy (band) and the majority-class rate (dashed). Middle: the budget $\epsilon_{0}$ each release receives under optimal composition (solid) against the basic split $\epsilon/n$ (dashed). Right: the ratio of the two, i.e. the gain from accounting.

	Linear	California
Data
Train / test points	40,000 / 2,000	16,512 / 4,128
Output range (GS)	$[-6,6]$	$10$ std. units
Baselines (Fig. 2(a) )
Model	$y=wx+b$	8-64-1 ReLU
Steps / lr / $\gamma$	20 / 0.3 / 1	330 / 0.01 / 0.1

Appendix

Table I : AGT-R settings for Figure 2 . Training is full-batch (full-shard) clipped gradient descent. PATE-R adds Laplace

(\mathrm{GS}/(T\epsilon))

(Gaussian in approximate DP) to the shard mean; PATE-AGT-R calibrates to

\frac{1}{T}\max_{i}\mathrm{SS}^{\beta}_{i}

	Blobs	MNIST 0–4	IMDB
Data
Private / public / test	200 / – / 4k	28.6k / 2k / 5.1k	20k / 5k / 25k
Features	$\mathbb{R}^{8}$ , 2 Gaussians	PCA-8 (pixels)	PCA-8 (mpnet)
Model and training
Head ( $P$ )	linear (9)	logistic (45)	logistic (18)
Training	clipped SGD	contractive clipped GD, full batch

Appendix

Table II : AGS settings for Figures 4 and 3 .

P

is the number of released parameters and

u

the smooth sensitivity of the

\ell_{1}

cross-radius certificate. Public sets: MNIST 1,000 PATE pool and 1,000 selection; IMDB 2,500 and 2,500. Baselines are tuned on the same public sets.

	SST-2 (hybrid)
Data
Private / public / test	62,349 / 872 (GLUE validation) / 5,000
Features	PCA-8 of the DP-LoRA all-mpnet-base-v2 embedding
Encoder (DP-LoRA, $(\epsilon_{1},5\cdot 10^{-6})$ -DP)
Adapter	rank 16 on the q, v projections of every layer
DP-SGD (Opacus)	batch 1,024, 3 epochs, clip 1, lr $10^{-3}$ , PRV accountant

Appendix

Table III : Settings of the SST-2 hybrid (Figure 5 ). The end-to-end arm is the DP-LoRA model scored with its own head; the frozen-encoder arms use the same head on the un-adapted embedding.

Explore similar work

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
May 25, 2026Christoph H. Lampert, Max Cairney-Leeming, Hossein ZakeriniaStandard Differential-Privacy Generalization Bounds
Institute of Science and Technology Austria (ISTA) Klosterneuburg, Austria
Revisiting ML Training under Fully Homomorphic Encryption: Convergence Guarantees, Differential Privacy, and Efficient Algorithms
May 27, 2026Yvonne Zhou, Mingyu Liang, Ivan Brugere +5Homomorphic Encryption Convergence
University of Maryland, College Park, MD 20742 · J.P. Morgan AI Research, New York, NY, 10017 · AlgoCRYPT CoE
Label Differential Privacy via Aggregation
Date pendingAnand Brahmbhatt, Rishi Saket, Shreyas Havaldar +3Standard Differential-Privacy Δ)$-Differential Privacy
Google Research India.

May 25, 2026, cs.LGJ/K move · Enter open · S save

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms

Christoph H. Lampert, Max Cairney-Leeming, Hossein Zakerinia

Institute of Science and Technology Austria (ISTA) Klosterneuburg, Austria

Standard Differential-Privacy Generalization Bounds Stochastic Gradient Descent Optimal Sample Complexity Privacy Information-Theoretic Limits+1

Open paper AskPDF arXiv

Understanding the relationship between generalization and privacy remains a challenge in modern machine learning theory, particularly for deep networks that are trained by variants of differentially private stochastic gradient descent (DP- SGD). In this work we make progress on this persistent open problem. First, we derive explicit upper bounds on the approximate max-information of any algorithm that fulfills

(ε, δ)

-differential privacy or Rényi differential privacy, thereby going beyond the classical results for pure

ε

-differential privacy. Subsequently, we show even stronger guarantees for two common private learning algorithms, output perturbation with the Gaussian mechanism, and streaming DP-SGD, by exploiting the structure of their internal randomization. As an application of our results, we demonstrate how to obtain non-vacuous PAC-Bayes generalization bounds for deep networks, in which the prior distribution is learned by DP-SGD instead of the classical way of choosing it in a data-independent way.

Abstract

Explore similar work

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms

Revisiting ML Training under Fully Homomorphic Encryption: Convergence Guarantees, Differential Privacy, and Efficient Algorithms

Label Differential Privacy via Aggregation