PaperlayerView exact revision on arXiv

Source-linked AI summary

Certification-Based Differentially Private Learning

Mihnea Ghitu, Matthew Wicker

arXiv:2609.39629v1cs.LG

TL;DR

Prior certification-based privacy methods were limited to classification, leaving continuous, unbounded regression outside their bounds. The paper extends AGT to regression and introduces AGS for private learning; AGT-R provides finite pure-DP prediction guarantees without a known global-sensitivity bound, and AGS outperforms DP-SGD under matched conditions.

  • Problem

    Prior certification-based privacy analysis covered classification, while its bounds fail for continuous, unbounded regression; global-sensitivity bounds can be overly conservative, causing excessive noise and worse utility.

    Source: §I · p. 1, A. AGT-R · p. 4

  • Method

    The paper generalizes AGT’s smooth-sensitivity analysis to continuous regression and frames private learning as parameter-space regression, introducing AGS to privatize learning parameters through sampling.

    Source: A. AGT-R · p. 4, §V · p. 6, B. Abstract Gradient Sampling (AGS) · p. 7

  • Results

    AGT-R provides the first finite pure-DP prediction guarantees without a known global-sensitivity bound; regression benchmarks beat PATE [16] by several orders of magnitude, and AGS significantly outperforms DP-SGD under matched conditions.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    Formal methods provide composition-like privacy-accounting bounds for pure-DP algorithms without resorting to approximate DP.

    Source: §I · p. 1

    AGS is best suited to compact models or trainable parts of pre-trained models, since noise grows with released parameters and nonlinear layers make deep models harder to certify tightly.

    Source: D. Limitations and Future Work · p. 9

Abstract

from arXiv · show

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.

I. INTRODUCTION … 2) Private Prediction:

The paper extends certification-based privacy analysis from classification to continuous regression and parameterized-model learning, using formal methods to tighten privacy guarantees. It reports improved benchmark results and theoretical conditions for tighter privacy accounting.

I. INTRODUCTION

  • The work extends AGT to continuous-valued regression and introduces AGS, which treats learning in parameterized models as continuous regression and uses abstract interpretation to bound update sensitivity.AGS is described as the first differentially private learning algorithm based on formal methods.Source: §I · pp. 1–2
  • The analysis gives conditions for certification-based noise to dominate global-sensitivity noise and reports finite pure-DP prediction guarantees without a known global sensitivity bound.It also gives composition-like privacy tightening without approximate DP.Source: §I · pp. 1–2
  • AGT-R beats global-sensitivity PATE by several orders of magnitude on regression benchmarks, while AGS significantly outperforms DP-SGD for small ϵ under matched conditions.The regression benchmarks include toy linear regression and California housing; AGS is evaluated on MNIST and IMDB sentiment classification.Source: §I · p. 2

II. RELATED WORK

  • Prior formal-methods privacy analysis was limited to classification prediction; this work extends smooth-sensitivity-based certification to private learners and continuous regression prediction.For non-quantized regression without a known global-sensitivity bound, the related-work section reports no prior finite privacy guarantee.Source: §II · p. 2

III. PRELIMINARIES

  • The paper studies supervised learning with parameterized models mapping inputs to outputs, using a continuous metric space for regression outputs.The model is denoted f_θ, with θ ∈ R^p.Source: §III · p. 2

A. Privacy

  • Differential privacy requires outputs on adjacent datasets to be statistically indistinguishable, with pure ϵ-DP arising as the special case δ = 0.The paper distinguishes private prediction from private learning as two approaches to machine-learning privacy.Source: A. Privacy · p. 2

1) Private Learning:

  • Private learning privatizes the learned parameters; DP-SGD clips gradients and adds noise, while alternatives include DP-ERM and PATE.Advanced composition and the moments accountant are among techniques that improve DP-SGD privacy analysis.Source: 1) Private Learning · p. 3

2) Private Prediction:

  • Private prediction adds noise to outputs of an unprivately trained model, but global sensitivity can impose utility costs; smooth sensitivity enables data-adaptive noise, and the paper limits its analysis to specified mechanisms.The section describes smooth sensitivity as an upper bound on local sensitivity and focuses on the mechanisms introduced there, leaving combinations with other mechanisms to future work.Source: 2) Private Prediction · p. 3

B. Valid Parameter Space Bounds … A. AGT-R

The paper extends abstract gradient training from classification to regression by using sound-bounding functions over certified parameter-space envelopes. It also introduces Abstract Gradient Sampling for private learning and reports finite smooth-sensitivity bounds for unbounded output domains.

B. Valid Parameter Space Bounds

  • A valid parameter-space bound is an envelope containing every model parameter reachable by training on datasets within k additions, removals, or substitutions of the nominal dataset.Sosnin et al., [13] frame local sensitivity as reachability and use abstract interpretation to compute such envelopes without optimizing over all possible datasets.Source: B. Valid Parameter Space Bounds · pp. 3–4
  • AGT constructs axis-aligned parameter envelopes by propagating bounds, aggregating b−k nominal gradients, and treating k differing gradients as γ-sized and adversarially directed.These parameter bounds can then be propagated to output space as a proxy for prediction-space local sensitivity.Source: B. Valid Parameter Space Bounds · p. 4

Shortcomings of Prior Approaches:

  • Prior AGT bounds applied only to private prediction in classification, leaving regression, amplification compatibility, and formal-methods-based private learning unresolved.The paper addresses these limitations by extending AGT to regression, discussing amplification, and introducing bound-propagation algorithms for private learning.Source: Shortcomings of Prior Approaches · p. 4

IV. METHODOLOGY

  • The paper introduces Abstract Gradient Sampling (AGS) as a private-learning method and says it can be superior to existing approaches under its theoretical analysis.The methodology also sets out to analyze when AGT-R outperforms global sensitivity.Source: §IV · p. 4

A. AGT-R

  • AGT-R generalizes the classification analysis by replacing its indicator-based bound with a sound-bounding function for continuous, unbounded regression outputs.The prior indicator function is sound only when distinct outputs have distance 1; the proposed function uses lower and upper output bounds propagated from valid parameter-space envelopes.Source: A. AGT-R · p. 4
  • Applying Nissim et al. ’s construction to an AGT sound-bounding function gives a β-smooth upper bound on smooth sensitivity and supports (ϵ, 0)- and (ϵ, δ)-DP mechanisms.The analysis strictly generalizes prior work and recovers its binary-classification result when the indicator function is used.Source: A. AGT-R · p. 5
  • AGT-R yields finite smooth-sensitivity bounds and finite noise for unbounded output domains, including cases where global sensitivity is infinite.The bound is finite when the reachable-parameter envelope at distance N gives a finite bound on output variation.Source: A. AGT-R · p. 5

1) Amplification of Generalized AGT Mechanisms:

Sampling without replacement gives an amplified privacy guarantee for an AGT mechanism run on a size-m subsample, relative to the original size-N dataset. The result allows AGT-R to use one persistent subsample while retaining a privacy guarantee for the full dataset.

1) Amplification of Generalized AGT Mechanisms:

2) Tractable Computation via AGT: · 3) Improving Utility of Private Prediction: · Pure (ϵ, 0)-DP:

The sections develop tractable smooth-sensitivity computation for AGT and analyze when AGT-R can improve private-prediction utility over global-sensitivity privatization. They give a sound sampling trade-off, a probabilistic certificate for pure-DP improvement, and a limited modification for approximate DP.

2) Tractable Computation via AGT:

  • Algorithm 1 first trains via AGT to obtain nominal parameters θ and parameter envelopes indexed by the symmetric-difference cardinality k.Here, k parameterizes the neighboring-dataset distance considered by AGT.Source: 2) Tractable Computation via AGT · p. 5
  • Arbitrary K containing N yields a sound smooth-sensitivity bound by back-filling missing radii with the next larger sampled radius, trading fewer AGT runs for potentially looser bounds.Denser K values progressively tighten the bound at greater computational cost.Source: 2) Tractable Computation via AGT · p. 5
  • The cited passage states β ≤ ϵ 2 ln(2/δ).Source: 2) Tractable Computation via AGT · p. 6

3) Improving Utility of Private Prediction:

  • AGT-R is analyzed for probabilistic improvement over global-sensitivity privatization in regression, with closed-form privacy-utility trade-offs for pure and approximate DP.The analysis establishes conditions under which AGT-R can outperform global-sensitivity-based privatization.Source: 3) Improving Utility of Private… · p. 6

Pure (ϵ, 0)-DP:

  • Theorem IV.3 certifies c-tighter error bounds from Cauchy noise than Laplace noise at confidence 1 − α when β < ϵ/6 and the theorem’s condition holds.The noise parameters are γ = 6SSβ(f, x)/ϵ and b = ∆f/ϵ, respectively.Source: Pure (ϵ, 0)-DP · p. 6
  • AGT upper-bounds smooth sensitivity conservatively, and as α approaches zero the critical sensitivity vanishes, precluding deterministic guarantees.The certificate can fail when AGT bounds are too large, c is unrealistic, or the desired guarantee approaches determinism; the authors propose simulating over α and c and using AGT-R only below the resulting critical ratio.Source: Pure (ϵ, 0)-DP · p. 6

Approximate (ϵ, δ)-DP: · V. ABSTRACT GRADIENT SAMPLING · A. Post-Training Privatization

The paper derives a condition under which smooth-sensitivity Laplace noise gives tighter approximate-DP error bounds than Gaussian noise, then extends smooth-sensitivity privatization from predictions to model parameters. It applies AGT to private learning and introduces Abstract Gradient Sampling as a broader parameter-space approach.

Approximate (ϵ, δ)-DP:

  • As confidence increases, both quantiles grow at a logarithmic rate, while smaller δ favors the smooth-sensitivity condition because Gaussian noise must increase.The condition remains satisfiable at confidence levels where Theorem IV.3 fails; Figure 1(b) plots feasible sensitivity ratios for approximate DP.Source: Approximate (ϵ, δ)-DP · p. 6, Figure 1 · p. 7

V. ABSTRACT GRADIENT SAMPLING

  • The paper introduces Abstract Gradient Sampling by viewing learning as multidimensional regression over parameters, where valid parameter-space bounds yield AGT-R’s local sensitivities.It first applies AGT-R directly to a learning algorithm’s output, then generalizes the approach into AGS.Source: §V · p. 6

A. Post-Training Privatization

  • AGT parameter envelopes bound the parameters trained on datasets within k changes, allowing neighboring-parameter bounds to support local-sensitivity analysis.The passages describe the valid parameter-space bound for k = 1 and envelopes for any k ≥ 1.Source: A. Post-Training Privatization · pp. 6–7
  • For post-training privatization, adding coordinate-wise noise calibrated to smooth sensitivity releases model parameters with pure-DP guarantees for Cauchy noise and approximate-DP guarantees for Laplace noise.The single-release corollary applies to parameters obtained after ns training steps.Source: A. Post-Training Privatization · p. 7
  • The section also considers advanced composition for n repeated trajectory releases, each made at budget (ϵ0, δ0), with a chosen δac.The supplied passage introduces the joint-release result but does not include its guarantee.Source: A. Post-Training Privatization · p. 7

Advanced Composition for Repeated Release: … 3) Statement of the AGS Algorithm:

Abstract Gradient Sampling (AGS) extends AGT-R privatization to intermediate training steps. It uses smooth-sensitivity bounds and composition to provide a privacy guarantee for the released parameters.

Advanced Composition for Repeated Release:

  • Advanced composition gives tighter privacy guarantees than basic composition for n releases along one trajectory [31, Thm. III.3].Each release is (ϵ0, δ0)-DP, and the releases are adaptively composed.Source: Advanced Composition for Repeated… · p. 7

B. Abstract Gradient Sampling (AGS)

  • AGS generalizes post-training AGT-R privatization by sampling and privatizing parameters at chosen intermediate training steps.At step i, it adds noise scaled by an upper bound on the β-smooth sensitivity.Source: B. Abstract Gradient Sampling (AGS) · p. 7

1) Multiple Release and AGT Semantics:

  • After a DP release, sampling collapses certified parameter envelopes to the released point while preserving valid AGT semantics.The proof establishes that the release accounts for privacy and that sensitivity is zero at the released point.Source: 1) Multiple Release and AGT Semantics · p. 8

2) Tighter Privacy Accounting for AGS:

  • AGS composes the privacy guarantees of releases across training windows to bound the privacy cost of the final parameter release.Each window is certified from the release preceding it.Source: 2) Tighter Privacy Accounting for AGS · p. 8
  • Sequential composition is looser than state-of-the-art numerical composition, which can optimize each AGS mechanism’s privacy curve.The paper proposes using numerical accounting techniques to improve the privacy guarantee.Source: 2) Tighter Privacy Accounting for AGS · p. 8

3) Statement of the AGS Algorithm:

  • AGS runs AGT within each training window, adds noise to privatize its parameters, resets bounds after sampling, and composes budgets for its final release.It returns a private set of parameters with a total privacy guarantee.Source: 3) Statement of the AGS Algorithm · p. 8

C. Analysis of AGS … VI. EXPERIMENTS

AGS’s controllable release timing supports theoretical conditions for outperforming DP-SGD, while the analysis also identifies computational and model-scope limitations. The experiments section introduces a systematic validation across toy and real-world settings, but the supplied passage gives no results.

C. Analysis of AGS

  • AGS can release parameters only when smooth-sensitivity-calibrated noise is lower than DP-SGD’s accumulated noise over the same steps, with closed-form conditions for preferring AGS.The analysis leverages AGS’s control over when privatization occurs.Source: C. Analysis of AGS · p. 8

Utility Analysis - Pure DP:

  • For a 1D μ-strongly convex, L-smooth loss with locally constant Hessian across the sp-step window and η≤1/L, one AGS update with Cauchy scale γ=6 SSβ(f)/ϵ and β<ϵ/6 yields a strictly tighter parameter space error bound than Laplace DP-SGD.The theorem considers DP-SGD parameter updates over sp steps with i.i.d. mean-zero Laplace gradient noise of scale (spΔf)/ϵ and confidence level α∈(0,1).Source: Utility Analysis - Pure DP · p. 8

Utility Analysis - Approximate DP:

  • Under the stated loss and step-size assumptions, Laplace noise b = 2 SSβ(f)/ϵ with β < ϵ/(2 ln(2/δ)) (AGS) yields tighter error bounds than Gaussian DP-SGD, with EL < EG.The assumptions are µ-strong convexity, L-smoothness, a locally constant Hessian across the sp-step window, and η ≤ 1/L.Source: Utility Analysis - Approximate DP · p. 9
  • Per-parameter error bounds can be extended to total parameter error with the triangle inequality or Matrix Bernstein, and bound propagation can empirically measure performance degradation.The passage names Matrix Bernstein, IBP [40], and AGT [13] as approaches.Source: Utility Analysis - Approximate DP · p. 9

D. Limitations and Future Work

  • AGS is among few formal-methods approaches to private learning and first uses parameter envelopes to frame learning as regression, but is best suited to compact or pretrained models.Noise grows with the number of released parameters, and envelopes loosen through nonlinear layers, making deep models harder to certify tightly. Smooth sensitivity benefits less from δ than data-independent Gaussian noise, and separately accounting for each release can overstate privacy loss when only the final model is published; the authors identify tighter trajectory accounting as a promising direction.Source: D. Limitations and Future Work · p. 9
  • AGS’s guarantees cost roughly 4× a nominal training run, while smooth-sensitivity release requires a pass per staircase radius and typically <10 values, yielding an order-of-magnitude complexity increase.Larger batches can tighten parameter envelopes; more exact LP, MILP, or MIQCP optimization can also help, but increases cost.Source: D. Limitations and Future Work · p. 9

VI. EXPERIMENTS

  • The experiments section sets out to systematically validate AGT-R and AGS across toy and real-world settings.Source: §VI · p. 9

A. AGT-R … VII. CONCLUSION

AGT-R applies formal verification to private regression, while AGS uses the resulting bounds to privately release learned parameters. Experiments show improved utility over global-sensitivity prediction and strong performance against private-learning baselines, with benefits depending on the task, privacy regime, and certificate tightness.

A. AGT-R — 1) Condition Simulations:

  • For pure DP, smooth-sensitivity Cauchy predictions can beat Laplace global-sensitivity predictions in the best case at confidence ≈0.4 only when ρ < 0.117, though this condition always holds for unbounded output spaces.The utility condition therefore requires AGT-based smooth-sensitivity bounds at least ten times smaller than global sensitivity.Source: 1) Condition Simulations · p. 9
  • In high-confidence approximate DP, the admissible sensitivity ratio peaks near 1.9 at c = 1, so Laplace-calibrated smooth sensitivity is preferable across essentially the full range except beyond confidence ≈0.995.A ratio above 1 means the bound need not improve on global sensitivity to yield better utility.Source: 1) Condition Simulations · p. 9

A. AGT-R — 2) Real-World Datasets:

  • On California Housing, PATE-AGT-R achieves test MSE within 0.06 of the non-private 0.94 at ϵ ≥2; across datasets, AGT-R variants outperform global-sensitivity prediction.At ϵ = 1, the best arm’s error is 57 times lower on linear regression and 6 times lower on California Housing in pure DP, and five and three orders of magnitude lower, respectively, in approximate DP. AGT-R on California has error 4.5 times lower in pure DP and over 30 times lower in approximate DP than data-independent prediction.Source: Figure 2 · p. 10, 2) Real-World Datasets · pp. 10–11
  • Tighter AGT certificates improve utility: raising concretization frequency from interval bound propagation to a MILP every 16 steps lowers smooth sensitivity from about 0.25 to 0.015, yielding four- to six-fold improvement.On California Housing, smooth sensitivity decreases as batch size rises: it peaks near 6 at batch size 250, is near 0.4 at 4,000, and is nearly zero at full batch size 16,512. AGT dominates global sensitivity in approximate DP across tested budgets, frequencies, and batch sizes, with up to two orders of magnitude lower MSE; in pure DP, dominance requires F ≥8 on linear regression from ϵ = 0.2 or batch size ≥1000 on California from ϵ = 1.Source: 2) Real-World Datasets · p. 11

B. AGS — 1) Utility:

  • On blobs, approximate-DP AGS leads PATE and matched DP-SGD from ϵ = 5, exceeds both by more than 0.2 accuracy at ϵ = 20, and approaches 0.90 at ϵ = 100.In pure DP, increasing the MILP interval from every step to every 10 steps raises accuracy at ϵ = 30 from 0.59 to 0.86.Source: 1) Utility · p. 11, Figure 4 · p. 12
  • On 5-class MNIST and IMDB, AGS reaches non-private-level accuracy at ϵ = 15 and ϵ = 5 in pure DP, respectively, and generally outperforms PATE and matched DP-SGD.On approximate-DP IMDB, AGS gains more than 0.1 accuracy over PATE for 1.5 ≤ϵ ≤7; the evaluation uses a linear head on PCA-8 features and an IMDB encoder frozen from all-mpnet-base-v2.Source: Figure 3 · p. 11, B. AGS · p. 11, 1) Utility · p. 12

C. Hybrid Approach

  • On SST-2, hybrid DP-LoRA+AGS can outperform DP-LoRA and AGS alone at 10k sentences, while the approach reaches performance within 4 points of the 94.3% non-private fine-tuning result.The AGS head is released once, composing its budget with DP-LoRA’s to obtain (ϵ1 + ϵ2, 10−5)-DP.Source: C. Hybrid Approach · p. 12, Figure 5 · p. 12

VII. CONCLUSION

  • The paper introduces AGT-R for differentially private regression without output-space assumptions and AGS for private learning via parameter-space regression, with theoretical privacy and utility analyses and experimental validation.AGS samples at predefined user-chosen steps from an appropriate noise distribution; both methods use AGT-derived smooth-sensitivity bounds.Source: §VII · p. 12

APPENDIX A THEORETICAL DERIVATION OF PARAMETER-SPACE … C. Proof of Corollary V.1

The appendix derives a reachable-parameter envelope for regression sensitivity and supplies proofs for noise-tail bounds and smooth-sensitivity noise admissibility.

APPENDIX A THEORETICAL DERIVATION OF PARAMETER-SPACE

  • AGT-R bounds each perturbed update using IBP or optimization, accounts for k differing points at clipping threshold γ, then propagates updates into an output-variation bound used for (ϵ, δ)-privacy.The test query is propagated over the final parameter envelope Tk, and the maximum output variation bounds smooth sensitivity.Source: Appendix A · p. 15

A. Proof of Theorem IV.3

  • The proof derives worst-case error tails for Laplace and Cauchy noise, then uses the condition EC < 1/cEL to establish the stated result.The Laplace tail is bounded by exp(−EL/b), while the Cauchy tail is expressed using arctan(EC/γ).Source: A. Proof of Theorem IV.3 · p. 15

B. Proof of Theorem IV.4

  • The proof bounds Gaussian error by σΦ^-1(1 − α/2), derives a Laplace error bound, and requires EL < EG for the final result.The Gaussian bound follows by standardizing the noise; the Laplace tail is handled by symmetry.Source: B. Proof of Theorem IV.4 · p. 15

C. Proof of Corollary V.1

  • Using [12], the proof reduces indistinguishability to showing that a product of Cauchy and Laplace coordinate densities is admissible, with scales 6u/ϵ and 2u/ϵ.Here u(β) is a β-smooth upper bound on the ℓ1 local sensitivity of θns.Source: C. Proof of Corollary V.1 · p. 15
  • For sliding, the product-density log ratio is bounded by the sum of coordinate shifts, yielding a bound of ∥∆∥1 ≤ α ≤ ϵ/2.This establishes the sliding admissibility inequality for every z.Source: C. Proof of Corollary V.1 · p. 15
  • For dilation, the Cauchy log-ratio sum is bounded by 3pβ = ϵ/2; the Laplace case achieves the bound on a high-probability set using a union bound.The set is B = {maxj |zj| ≤ ln(2p/δ)}, whose complement has probability at most δ/2.Source: C. Proof of Corollary V.1 · p. 15

D. Proof of Theorem V.2

The proof bounds Laplace DP-SGD’s error using a weighted subexponential Bernstein inequality under a locally constant-curvature assumption, then identifies conditions under which AGS dominates Laplace DP-SGD. It also states that the Cauchy-case error bound matches Theorem IV.3.

D. Proof of Theorem V.2

  • The weighted subexponential Bernstein inequality applies when curvature is locally constant across the sp-window, making the error coefficients deterministic and independent of the Laplace noise.The proof treats the Laplace variables as i.i.d. with mean 0 and scale b = (sp∆f)/ϵ.Source: D. Proof of Theorem V.2 · p. 16
  • Under µ-strong convexity, L-smoothness, and η ≤ 1/L, the proof bounds the coefficient norms using |as| ≤ η(1 − ηµ)^(sp−s) and ∥a∥∞ ≤ η.It computes ∥a∥2^2 from a geometric progression with ratio (1 − ηµ)^2.Source: D. Proof of Theorem V.2 · p. 16
  • The α-quantile worst-case error is the larger of EL,1 and EL,2, the smallest errors satisfying the two Bernstein-bound constraints.The proof first requires min(A, B) ≥ the threshold derived from 2 exp(−c min(A, B)) ≤ α.Source: D. Proof of Theorem V.2 · pp. 16–17
  • Enforcing EC < EL gives the conditions under which AGS dominates Laplace DP-SGD.The Cauchy-case error term is exactly as in the proof of Theorem IV.3.Source: D. Proof of Theorem V.2 · p. 17

E. Proof of Theorem V.3

The proof bounds Gaussian-noise error over an sp-step window using subgaussian concentration, then gives conditions under which smooth-sensitivity Laplace AGS has lower error than Gaussian DP-SGD.

E. Proof of Theorem V.3

  • At per-step budget (ϵ/sp, δ/sp), basic composition makes the sp-step Gaussian window cost (ϵ, δ), matching a single AGS release.The proof uses Gaussian noise for the clean update and compares it with one Laplace-noise addition calibrated to smooth sensitivity.Source: E. Proof of Theorem V.3 · p. 17
  • Assuming locally constant curvature h across the window makes the weights deterministic and independent of the noise, as required for concentration.The proof analyzes the sp-window error under this assumption.Source: E. Proof of Theorem V.3 · p. 17
  • Because Gaussian noise is subgaussian, the proof applies the general Hoeffding inequality to the weighted, centered Gaussian terms.Scaling a Gaussian by a constant preserves Gaussianity, with its mean scaled by that constant and its variance by the constant squared.Source: E. Proof of Theorem V.3 · p. 17
  • The weighted-noise norm uses ∥a∥₂² ≤ ηµ(2−ηµ), under µ-strong convexity, L-smoothness, and step size η ≤ 1/L.The proof substitutes this bound and the computed Gaussian subgaussian norm into the concentration inequality.Source: E. Proof of Theorem V.3 · p. 17
  • Enforcing E_L < E_G yields conditions on smooth sensitivity under which Laplace AGS dominates Gaussian DP-SGD.The Laplace noise is calibrated to β-smooth sensitivity, with β < ϵ/(2 ln(2/δ)) ensuring approximate (ϵ, δ)-DP.Source: E. Proof of Theorem V.3 · p. 17

APPENDIX C AGT-R ABLATIONS · A. Condition Simulations: Further Analysis

Appendix C extends AGT-R certificate validation with shard and other ablations, while the condition simulations show favorable pure-DP utility ratios and more restrictive, optimistic approximate-DP bounds. The supplied passages describe the shard-ablation setup but do not report its outcomes.

APPENDIX C AGT-R ABLATIONS

  • Appendix C validates the AGT-R certificate independently and extends feasibility-condition analysis alongside ablations of concretization frequency and batch size.It also introduces shard-count ablations and a raw-error-scale comparison with global-sensitivity baselines.Source: Appendix C · pp. 17–18
  • The shard ablation studies linear regression with 4×10^3 training points under pure DP, varying shard count T at fixed dataset size across budgets ϵ ∈ [0.1, 10].Figure 6 compares PATE-R, PATE-AGT-R, single-shard AGT-R with amplified budget ϵb, and the noise-free PATE mean; the supplied passages give no outcome values.Source: Figure 6 · p. 18, Appendix C · p. 18
  • Appendix C repeats the Figure 2a comparison on the raw error scale alongside global-sensitivity baselines, linking it to the main experiments.The supplied passage describes this comparison but does not state its results.Source: Appendix C · p. 18

A. Condition Simulations: Further Analysis

  • With pure (ϵ, 0)-DP, ratios ρ ≈ 0.01 consistently yield utility multipliers greater than 1 with confidence above 90%.As c increases, the gaps between consecutive c values shrink, so a smaller ratio consistently achieves c ≫ 1 better utility.Source: A. Condition Simulations: Further… · p. 18
  • For approximate (ϵ, δ)-DP with c = 1, admissible ratios peak near ρ ≈ 1.9 at 1 − α ≈ 0.8, but fall to 1.12–1.44 at 1 − α = 0.98.The larger peak occurs at an operating point described as having little practical interest.Source: A. Condition Simulations: Further… · p. 18
  • Approximate-DP conditions constrain β more strictly: Cauchy requires β < ϵ/6, while Laplace requires β ≤ ϵ 2 ln(2/δ), roughly four times tighter at δ = 10^-5.The stricter Laplace constraint is compared with the pure-DP case.Source: A. Condition Simulations: Further… · p. 18
  • Because AGT-R strictly upper-bounds local sensitivity and is over-approximate, a practically larger SSβ—or larger ϵ to remain valid—is needed, making displayed curves optimistic theoretical ceilings.These conditions qualify the approximate-DP utility curves as not practically attainable as shown.Source: A. Condition Simulations: Further… · p. 18
  • Under approximate DP, diminishing returns recur: c = 2 and c = 3 stay below unity throughout the window, peaking at ρ ≈ 0.96 and 0.64, respectively.The stated peak ratios correspond to c = 2 and c = 3, respectively.Source: A. Condition Simulations: Further… · p. 18

B. Certificates of the AGT-R Ablations … Blobs MNIST 0–4 IMDB

The supplied ablations explain how certificate tightness drives lower smooth-sensitivity bounds and show how sampling steps and composition affect utility. They also describe shard comparisons, global-sensitivity baselines, and AGT-R/AGS experimental settings.

B. Certificates of the AGT-R Ablations

  • For large F or full batch, certificates stay below the ceiling through k ≤20 and SSβ peaks at k=2 an order of magnitude lower, explaining reductions 0.25→0.015 and 6→0.08.Looser certificates saturate at the ceiling within a few substitutions, with SSβ peaking at k=1 close to the ceiling.Source: B. Certificates of the AGT-R Ablations · pp. 18–19, Figure 7 · p. 18

C. Number of shards (T)

  • The shard ablation compares PATE-R, PATE-AGT-R, and one-shard AGT-R on 4×10^3 Linear training points across shard counts and ϵ from 0.1 to 10.It uses the same model and hyperparameters as §VI-A except for training-set size.Source: C. Number of shards (T) · p. 19

D. Private Prediction Baselines with Global Sensitivity

  • On the excess-error scale, the global-sensitivity arm sits one to five orders of magnitude above every other arm, so Figure 8 reports full MAE and MSE instead.The AGT-based arms flatten at the non-private floors: 0.079 MAE and 0.0098 MSE on linear regression, and 0.72 MAE and 0.94 MSE on California Housing.Source: D. Private Prediction Baselines with… · p. 19, Figure 8 · p. 19

A. Sampling Ablation

  • At ϵ=10, 50, and 150, accuracy falls below ≈78% after 4, 16, and 64 releases, respectively; at ϵ=150, 32 releases still reach 80.9%.The number of releases within one point of non-private accuracy doubles from 8 at ϵ=50 to 16 at ϵ=150.Source: Figure 9 · p. 19, A. Sampling Ablation · p. 20
  • Optimal composition yields up to 3.5× more per-step privacy budget at ϵ=5 and n=28, with gains beginning at n≥32 for ϵ≤20 and n≥27 for ϵ≥100.At ϵ∈{100, 150} and n=27, accuracy is 75.0% versus 74.8% and 75.3% versus 74.8%, respectively; both remain near the 74.6% majority-class rate.Source: Figure 9 · p. 19, A. Sampling Ablation · p. 20

A. AGT-R

  • For Figure 2, AGT-R uses full-batch clipped gradient descent; PATE-R adds noise calibrated to global sensitivity, while PATE-AGT-R calibrates to smooth sensitivity.PATE-R uses Laplace noise under pure DP and Gaussian noise under approximate DP.Source: Table I · p. 20

Blobs MNIST 0–4 IMDB

  • AGS settings cover Blobs, MNIST 0–4, and IMDB, with dataset sizes, feature choices, model heads, training procedures, substitution ranges, and release mechanisms specified.The AGS settings table covers Figures 4 and 3; its public sets are 1,000 PATE pool and 1,000 selection examples for MNIST, and 2,500 of each for IMDB.Source: Blobs MNIST 0–4 IMDB · p. 20, Table II · p. 20
  • For the SST-2 hybrid, the end-to-end DP-LoRA arm uses its own head, while frozen-encoder arms use the same head on un-adapted embeddings.Table III gives the settings for Figure 5.Source: Table III · p. 20

Related papers

Loading 2609.39629v1…