Computation-Utility-Privacy Tradeoffs in Bayesian Estimation

• URL: http://arxiv.org/abs/2603.18254v1
• Date: Wed, 18 Mar 2026 20:20:58 GMT
• Title: Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
• Abstract summary: We give the first efficient algorithms for both of these problems that achieve mean-squared error.<n>We draw upon the privacy-to-robustness framework of arXiv:2212.05 to achieve private Bayes-optimal estimation.<n>We also add to the sum-of-squares toolkit a new kind of constraint based on short-flat decompositions.
• Score: 14.293470686822305
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Bayesian methods lie at the heart of modern data science and provide a powerful scaffolding for estimation in data-constrained settings and principled quantification and propagation of uncertainty. Yet in many real-world use cases where these methods are deployed, there is a natural need to preserve the privacy of the individuals whose data is being scrutinized. While a number of works have attempted to approach the problem of differentially private Bayesian estimation through either reasoning about the inherent privacy of the posterior distribution or privatizing off-the-shelf Bayesian methods, these works generally do not come with rigorous utility guarantees beyond low-dimensional settings. In fact, even for the prototypical tasks of Gaussian mean estimation and linear regression, it was unknown how close one could get to the Bayes-optimal error with a private algorithm, even in the simplest case where the unknown parameter comes from a Gaussian prior. In this work, we give the first efficient algorithms for both of these problems that achieve mean-squared error $(1+o(1))\mathrm{OPT}$ and additionally show that both tasks exhibit an intriguing computational-statistical gap. For Bayesian mean estimation, we prove that the excess risk achieved by our method is optimal among all efficient algorithms within the low-degree framework, yet is provably worse than what is achievable by an exponential-time algorithm. For linear regression, we prove a qualitatively similar lower bound. Our algorithms draw upon the privacy-to-robustness framework of arXiv:2212.05015, but with the curious twist that to achieve private Bayes-optimal estimation, we need to design sum-of-squares-based robust estimators for inherently non-robust objects like the empirical mean and OLS estimator. Along the way we also add to the sum-of-squares toolkit a new kind of constraint based on short-flat decompositions.

Related papers

• RPWithPrior: Label Differential Privacy in Regression [0.0]
  In this paper, we focus on regression tasks under $$-label differential privacy guarantees.<n>We model both original and randomized responses as continuous random variables, avoiding discretization entirely.<n>We prove that our algorithm, RPWithPrior, guarantees $$-label differential privacy.
  arXiv  Detail & Related papers  (2026-01-30T06:27:13Z)
• Approximate Algorithms for Verifying Differential Privacy with Gaussian Distributions [2.9748898344267776]
  We introduce a novel approach to approximating probability distributions of loop-free programs that sample from both discrete and continuous distributions.<n>Our verification algorithm is based on computing probabilities to any desired precision by combining integral approximations, and tail probability bounds.
  arXiv  Detail & Related papers  (2025-09-10T17:37:56Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Sample-Optimal Private Regression in Polynomial Time [3.3748750222488657]
  We show that any improvement to the sample complexity of our algorithm would violate either statistical-query or information-theoretic lower bounds.<n>Our algorithm is robust to a small fraction of arbitrary outliers and achieves optimal error rates as a function of the fraction of outliers.
  arXiv  Detail & Related papers  (2025-03-31T17:08:12Z)
• 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)
• Differentially Private Domain Adaptation with Theoretical Guarantees [46.37771025567305]
  In many applications, the labeled data at the labeled data's disposal is subject to privacy constraints and is relatively limited. This is the modern problem of supervised domain adaptation from a public source to a private target domain. We make use of a general learner to benefit from favorable theoretical learning guarantees.
  arXiv  Detail & Related papers  (2023-06-15T04:03:06Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball. We propose a new algorithmic framework, ProjUnit, for private mean estimation. Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace, normalizes the result, and then runs an optimal algorithm.
  arXiv  Detail & Related papers  (2023-06-07T14:07:35Z)
• Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation [8.9598796481325]
  We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. We establish an information-computation gap for private sparse mean estimation. We also give evidence for privacy-induced information-computation gaps for several other statistics and learning problems.
  arXiv  Detail & Related papers  (2022-11-01T20:03:41Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• Robust and Differentially Private Mean Estimation [40.323756738056616]
  Differential privacy has emerged as a standard requirement in a variety of applications ranging from the U.S. Census to data collected in commercial devices. An increasing number of such databases consist of data from multiple sources, not all of which can be trusted. This leaves existing private analyses vulnerable to attacks by an adversary who injects corrupted data.
  arXiv  Detail & Related papers  (2021-02-18T05:02:49Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)

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.