Sample-Optimal Private Regression in Polynomial Time

• URL: http://arxiv.org/abs/2503.24321v1
• Date: Mon, 31 Mar 2025 17:08:12 GMT
• Title: Sample-Optimal Private Regression in Polynomial Time
• Authors: Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, Stefan Tiegel,
• Abstract summary: 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.
• Score: 3.3748750222488657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure). We provide the first sample-optimal polynomial time algorithm for this task under both pure and approximate differential privacy. We show that any improvement to the sample complexity of our algorithm would violate either statistical-query or information-theoretic lower bounds. Additionally, our algorithm is robust to a small fraction of arbitrary outliers and achieves optimal error rates as a function of the fraction of outliers. In contrast, all prior efficient algorithms either incurred sample complexities with sub-optimal dimension dependence, scaling with the condition number of the covariates, or obtained a polynomially worse dependence on the privacy parameters. Our technical contributions are two-fold: first, we leverage resilience guarantees of Gaussians within the sum-of-squares framework. As a consequence, we obtain efficient sum-of-squares algorithms for regression with optimal robustness rates and sample complexity. Second, we generalize the recent robustness-to-privacy framework [HKMN23, (arXiv:2212.05015)] to account for the geometry induced by the covariance of the input samples. This framework crucially relies on the robust estimators to be sum-of-squares algorithms, and combining the two steps yields a sample-optimal private regression algorithm. We believe our techniques are of independent interest, and we demonstrate this by obtaining an efficient algorithm for covariance-aware mean estimation, with an optimal dependence on the privacy parameters.

Related papers

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Robustness Implies Privacy in Statistical Estimation [16.061651295129302]
  We study the relationship between adversarial and differential privacy in high-dimensional statistics. We give the first blackbox reduction from privacy to robustness which can produce private estimators with optimal tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.
  arXiv  Detail & Related papers  (2022-12-09T18:07:30Z)
• 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)
• Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
  $(epsilon, delta)$-differentially private (DP) $(epsilon, delta)$-differentially private (DP) $(epsilon, delta)$-differentially private (DP)
  arXiv  Detail & Related papers  (2021-12-07T07:47:37Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  We study efficient algorithms for Sparse PCA in standard statistical models. Our goal is to achieve optimal recovery guarantees while being resilient to small perturbations.
  arXiv  Detail & Related papers  (2020-11-12T18:58:51Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. We provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. We also propose the first algorithm for linear bandits in the the fixed budget setting.
  arXiv  Detail & Related papers  (2020-06-21T00:56:33Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)

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.