Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization

• URL: http://arxiv.org/abs/2204.01585v4
• Date: Mon, 28 Aug 2023 23:24:59 GMT
• Title: Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
• Authors: Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
• Abstract summary: We provide an algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity and which can be stopped at anytime without compromising privacy. We obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP) The framework allows us to design a DP uniform sampler from the Rashomon set.
• Score: 15.404265455635587
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from the Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.

Related papers

• KL-regularization Itself is Differentially Private in Bandits and RLHF [19.463863037999054]
  Differential Privacy (DP) provides a rigorous framework for privacy, ensuring the outputs of data-driven algorithms remain statistically indistinguishable across datasets that differ in a single entry.<n>While guaranteeing DP generally requires explicitly injecting noise either to the algorithm itself or to its outputs, the intrinsic randomness of existing algorithms presents an opportunity to achieve DP for free''
  arXiv  Detail & Related papers  (2025-05-23T22:22:02Z)
• Decomposition-Based Optimal Bounds for Privacy Amplification via Shuffling [6.702635586444281]
  Shuffling has been shown to amplify differential privacy guarantees, enabling a more favorable privacy-utility trade-off.<n>We introduce a unified analytical framework--the general clone paradigm--which subsumes all possible decompositions.<n>We develop a simple and efficient algorithm based on the Fast Fourier Transform (FFT) to compute optimal privacy amplification bounds.
  arXiv  Detail & Related papers  (2025-04-10T03:11:17Z)
• The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
  We show that data shuffling results in worse empirical excess risk for textitDP-ShuffleG compared to DP-SGD. We propose textitInterleaved-ShuffleG, a hybrid approach that integrates public data samples in private optimization.
  arXiv  Detail & Related papers  (2025-02-05T22:30:00Z)
• Differentially Private Random Block Coordinate Descent [51.62669821275571]
  We propose a differentially private random coordinate descent method that selects multiple coordinates with varying probabilities in each iteration using sketch matrices. Our algorithm generalizes both DP-CD and the classical DP-SGD (Differentially Private Descent), while preserving the same utility guarantees.
  arXiv  Detail & Related papers  (2024-12-22T15:06:56Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines. We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence [25.717501580080846]
  This paper revisits the convergence of gradient Forward Mirror (SMD) in the contemporary non optimization setting. For the training, we develop provably convergent algorithms for the problem of linear networks.
  arXiv  Detail & Related papers  (2024-02-27T17:56:49Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Unified Enhancement of Privacy Bounds for Mixture Mechanisms via $f$-Differential Privacy [41.51051636162107]
  This paper focuses on improving privacy bounds for shuffling models and one-iteration differentially private gradient descent. We derive a closed-form expression of the trade-off function for shuffling models that outperforms the most up-to-date results. We also study an $f$-DP analog of the advanced joint convexity of the hockey-stick divergence related to $(epsilon,delta)$-DP.
  arXiv  Detail & Related papers  (2023-10-30T19:37:51Z)
• GFlowNet-EM for learning compositional latent variable models [115.96660869630227]
  A key tradeoff in modeling the posteriors over latents is between expressivity and tractable optimization. We propose the use of GFlowNets, algorithms for sampling from an unnormalized density. By training GFlowNets to sample from the posterior over latents, we take advantage of their strengths as amortized variational algorithms.
  arXiv  Detail & Related papers  (2023-02-13T18:24:21Z)
• On the Privacy-Robustness-Utility Trilemma in Distributed Learning [7.778461949427662]
  We present the first tight analysis of the error incurred by any algorithm ensuring robustness against a fraction of adversarial machines. Our analysis exhibits a fundamental trade-off between privacy, robustness, and utility.
  arXiv  Detail & Related papers  (2023-02-09T17:24:18Z)
• The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
  We introduce a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism.
  arXiv  Detail & Related papers  (2022-07-09T05:46:28Z)
• Differential Privacy of Dirichlet Posterior Sampling [0.0]
  We study the inherent privacy of releasing a single draw from a Dirichlet posterior distribution. With the notion of truncated concentrated differential privacy (tCDP), we are able to derive a simple privacy guarantee of the Dirichlet posterior sampling.
  arXiv  Detail & Related papers  (2021-10-03T07:41:19Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Differentially Private Federated Learning with Laplacian Smoothing [72.85272874099644]
  Federated learning aims to protect data privacy by collaboratively learning a model without sharing private data among users. An adversary may still be able to infer the private training data by attacking the released model. Differential privacy provides a statistical protection against such attacks at the price of significantly degrading the accuracy or utility of the trained models.
  arXiv  Detail & Related papers  (2020-05-01T04:28:38Z)
• Distributionally Robust Bayesian Optimization [121.71766171427433]
  We present a novel distributionally robust Bayesian optimization algorithm (DRBO) for zeroth-order, noisy optimization. Our algorithm provably obtains sub-linear robust regret in various settings. We demonstrate the robust performance of our method on both synthetic and real-world benchmarks.
  arXiv  Detail & Related papers  (2020-02-20T22:04:30Z)

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.