Sliced Rényi Pufferfish Privacy: Directional Additive Noise Mechanism and Private Learning with Gradient Clipping

• URL: http://arxiv.org/abs/2512.01115v2
• Date: Tue, 02 Dec 2025 19:44:01 GMT
• Title: Sliced Rényi Pufferfish Privacy: Directional Additive Noise Mechanism and Private Learning with Gradient Clipping
• Authors: Tao Zhang, Yevgeniy Vorobeychik,
• Abstract summary: We study privatization mechanism design and privacy accounting in the Pufferfish family.<n>We introduce Sliced Renyi Pufferfish Privacy (SRPP), which replaces high-dimensional comparisons by directional ones over a set of unit vectors.<n>Our experiments indicate that the proposed SRPP-based methods achieve favorable privacy-utility trade-offs in both static and iterative settings.
• Score: 27.430637970345433
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study privatization mechanism design and privacy accounting in the Pufferfish family, addressing two practical gaps of Renyi Pufferfish Privacy (RPP): high-dimensional optimal transport (OT) calibration and the absence of a general, mechanism-agnostic composition rule for iterative learning. We introduce Sliced Renyi Pufferfish Privacy (SRPP), which replaces high-dimensional comparisons by directional ones over a set of unit vectors, enabling geometry-aware and tractable guarantees. To calibrate noise without high-dimensional OT, we propose sliced Wasserstein mechanisms that compute per-direction (1-D) sensitivities, yielding closed-form, statistically stable, and anisotropic calibrations. We further define SRPP Envelope (SRPE) as computable upper bounds that are tightly implementable by these sliced Wasserstein mechanisms. For iterative deep learning algorithms, we develop a decompose-then-compose SRPP-SGD scheme with gradient clipping based on a History-Uniform Cap (HUC), a pathwise bound on one-step directional changes that is uniform over optimization history, and a mean-square variant (ms-HUC) that leverages subsampling randomness to obtain on-average SRPP guarantees with improved utility. The resulting HUC and ms-HUC accountants aggregate per-iteration, per-direction Renyi costs and integrate naturally with moments-accountant style analyses. Finally, when multiple mechanisms are trained and privatized independently under a common slicing geometry, our analysis yields graceful additive composition in both worst-case and mean-square regimes. Our experiments indicate that the proposed SRPP-based methods achieve favorable privacy-utility trade-offs in both static and iterative settings.

Related papers

• Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression [22.733602577854825]
  We study instrumental variable regression (IVaR) under differential privacy constraints.<n>We propose a noisy two-state gradient descent algorithm that ensures differential privacy by injecting carefully calibrated noise into the gradient updates.
  arXiv  Detail & Related papers  (2025-09-26T18:02:58Z)
• Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization [27.430637970345433]
  We show that the upper bound obtained by PAC Privacy algorithms is tight if and only if the perturbed mechanism output is jointly Gaussian with independent noise.<n>We introduce Residual-PAC (R-PAC) Privacy, an f-divergence-based measure to quantify privacy that remains after adversarial inference.<n>Our approach achieves efficient privacy budget utilization for arbitrary data distributions and naturally composes when multiple mechanisms access the dataset.
  arXiv  Detail & Related papers  (2025-06-06T20:52:47Z)
• Second-Order Convergence in Private Stochastic Non-Convex Optimization [28.00987194971941]
  We investigate the problem of finding second-order stationary points (SOS) in differentially private (DP) non-dimensional identification optimization.<n>Existing methods suffer from inaccurate convergence error due to gradient variance in the saddle point escape analysis.<n>We develop a new DP algorithm that rectifies the convergence error reported in prior work.
  arXiv  Detail & Related papers  (2025-05-21T15:25:23Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• On the Convergence of DP-SGD with Adaptive Clipping [56.24689348875711]
  Gradient Descent with gradient clipping is a powerful technique for enabling differentially private optimization.<n>This paper provides the first comprehensive convergence analysis of SGD with quantile clipping (QC-SGD)<n>We show how QC-SGD suffers from a bias problem similar to constant-threshold clipped SGD but can be mitigated through a carefully designed quantile and step size schedule.
  arXiv  Detail & Related papers  (2024-12-27T20:29:47Z)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy [47.997934291881414]
  Existing mean estimation schemes are usually optimized for $L_infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L$ geometry. We introduce a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP. Unlike previous approaches, our accounting algorithm directly operates in $L$ geometry, yielding MSEs that fast converge to those of the Gaussian mechanism.
  arXiv  Detail & Related papers  (2024-05-02T03:48:47Z)
• Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior [51.60683890503293]
  We propose a theoretical framework for studying behavior cloning of complex expert demonstrations using generative modeling. We show that pure supervised cloning can generate trajectories matching the per-time step distribution of arbitrary expert trajectories.
  arXiv  Detail & Related papers  (2023-07-27T04:27:26Z)
• Differentially Private Learning with Per-Sample Adaptive Clipping [8.401653565794353]
  We propose a Differentially Private Per-Sample Adaptive Clipping (DP-PSAC) algorithm based on a non-monotonic adaptive weight function. We show that DP-PSAC outperforms or matches the state-of-the-art methods on multiple main-stream vision and language tasks.
  arXiv  Detail & Related papers  (2022-12-01T07:26:49Z)
• On Private Online Convex Optimization: Optimal Algorithms in $\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
  We study the Differentially private (DP) convex optimization problem with streaming data sampled from a distribution and arrives sequentially. We also consider the continual release model where parameters related to private information are updated and released upon each new data, often known as the online algorithms. Our algorithm achieves in linear time the optimal excess risk when $1pleq 2$ and the state-of-the-art excess risk meeting the non-private lower ones when $2pleqinfty$.
  arXiv  Detail & Related papers  (2022-06-16T12:09:47Z)
• An automatic differentiation system for the age of differential privacy [65.35244647521989]
  Tritium is an automatic differentiation-based sensitivity analysis framework for differentially private (DP) machine learning (ML) We introduce Tritium, an automatic differentiation-based sensitivity analysis framework for differentially private (DP) machine learning (ML)
  arXiv  Detail & Related papers  (2021-09-22T08:07:42Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.