SOMA: A Novel Sampler for Bayesian Inference from Privatized Data

2025/05/01 by Yifei Xiong, Xiong, Yifei, Nianqiao Ju +1
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Methodology (stat.ME) #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2505.00635

openalex publication_date 2025/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

Abstract

Making valid statistical inferences from privatized data is a key challenge in modern analysis. In Bayesian settings, data augmentation MCMC (DAMCMC) methods impute unobserved confidential data given noisy privatized summaries, enabling principled uncertainty quantification. However, standard DAMCMC often suffers from slow mixing due to component-wise Metropolis-within-Gibbs updates. We propose the Single-Offer-Multiple-Attempts (SOMA) sampler. This novel algorithm improves acceptance rates by generating a single proposal and simultaneously evaluating its suitability to replace all components. By sharing proposals across components, SOMA rejects fewer proposal points. We prove lower bounds on SOMA's acceptance probability and establish convergence rates in the two-component case. Experiments on synthetic and real census data with linear regression and other models confirm SOMA's efficiency gains.

Citations

• On the fundamental limitations of multiproposal Markov chain Monte Carlo algorithms
• Statistical Inference for Privatized Data with Unknown Sample Size
• Spectral gap bounds for reversible hybrid Gibbs chains
• Simulation-based Bayesian Inference from Privacy Protected Data
• Lower bounds on the rate of convergence for accept-reject-based Markov chains in Wasserstein and total variation distances
• Differentially Private Methods for Compositional Data
• Data Augmentation MCMC for Bayesian Inference from Privatized Data
• Convergence Rate of Multiple-try Metropolis Independent sampler
• On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
• Exact Convergence Rate Analysis of the Independent Metropolis-Hastings Algorithms
• Convergence Rates of Two-Component MCMC Samplers
• Differentially Private Bayesian Linear Regression
• Optimal scaling of the independence sampler: Theory and Practice
• Uniform Ergodicity of the Iterated Conditional SMC and Geometric Ergodicity of Particle Gibbs samplers
• A statistical framework for differential privacy
• Differential Privacy
• On the Markov chain central limit theorem
• Improving Asymptotic Variance of MCMC Estimators: Non-reversible Chains are Better
• Slice Sampling

Related

• Data Augmentation MCMC for Bayesian Inference from Privatized Data
• Best Linear Unbiased Estimate from Privatized Contingency Tables
• Statistical Inference for Privatized Data with Unknown Sample Size
• Optimal proposals for Approximate Bayesian Computation
• An Approximate Monte Carlo Simulation Method for Estimating Uncertainty and Constructing Confidence Intervals for 2020 Census Statistics