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 ρ=SSβ/Δf for which our smooth-sensitivity mechanism attains a c -times tighter error bound than the global-sensitivity baseline at confidence 1−α ; 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−α>0.8 and measured against Δ2f .
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, δ=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, δ=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 ϵ=ϵ1+ϵ2 under (ϵ,10−5) -DP (left), a pure-DP head (middle), and the private set size N at ϵ=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×103 training points, under pure DP. MAE against the number of shards T at fixed dataset size, one line per budget ϵ∈[0.1,10] , for PATE-R (Laplace noise on global sensitivity), PATE-AGT-R (Cauchy noise on the shard-wise smooth sensitivity, β=ϵ/2 ) and AGT-R on a single shard of N/T points with the amplified budget ϵ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 Aˉ(x,k) averaged over test inputs; solid, right axis: the smooth-sensitivity bound at β=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 ( δ=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 (ϵ,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 ϵ0 each release receives under optimal composition (solid) against the basic split ϵ/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 / γ
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 (GS/(Tϵ)) (Gaussian in approximate DP) to the shard mean; PATE-AGT-R calibrates to T1maxiSSiβ .
Blobs
MNIST 0–4
IMDB
Data
Private / public / test
200 / – / 4k
28.6k / 2k / 5.1k
20k / 5k / 25k
Features
R8 , 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 ℓ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.
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.
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.
Christoph H. Lampert, Max Cairney-Leeming, Hossein Zakerinia
Institute of Science and Technology Austria (ISTA) Klosterneuburg, Austria
We present the first theoretical convergence analysis of machine learning training under fully homomorphic encryption (FHE), combined with a differentially private (DP) training algorithm tailored to encrypted computation. Our approach improves computational efficiency over standard differentially private gradient descent (DP-GD) while achieving comparable utility. In particular, we prove convergence of approximate gradient descent using polynomial approximations of activation and loss functions, which are required for FHE compatibility. To preserve privacy in downstream tasks, we integrate differential privacy without relying on costly per-sample gradient clipping, enabling scalable encrypted learning. We also provide data-independent hyperparameter selection and theoretically grounded strategies for polynomial approximation which can be of independent interest. Together, these contributions advance the feasibility of efficient, private, and secure machine learning on sensitive data.
Yvonne Zhou, Mingyu Liang, Ivan Brugere +5
University of Maryland, College Park, MD 20742 · J.P. Morgan AI Research, New York, NY, 10017 · AlgoCRYPT CoE
This paper explores the use of linear aggregation to protect the privacy of sensitive training labels through the concept of \emph{label differential privacy} (label-DP) while maintaining regression task utility. Our key finding is that weighted linear aggregation of training instances with i.i.d. N(0,1) weights can achieve (ε,δ)-label-DP with m=O(n/(log(1/δ))). Unlike prior methods, our approach relies on the minimum linear regression loss rather than the minimum singular value of the data matrix, resulting in better practical bounds on real datasets. We also examine real-world mechanisms involving disjoint sets or \textit{bags} of instances. We demonstrate that aggregating labels from sub-sampled disjoint k-sized bags using i.i.d. N(0,1) weights achieves (ε,δ)-label-DP with k≥Ω(((1/ε)log(1/δ))2). In both scenarios, the optimal linear mse-regressor on the aggregated data approximates the original dataset's optimum with high probability, without needing additive label noise. Furthermore, we show that adding N(0,1) noise to any constant fraction of labels allows for similar label-DP guarantees when aggregating labels over random disjoint bags, while preserving the utility of Lipschitz-bounded neural mse-regression tasks.