mlsanityData to 7 Oct 2026

Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares

arXiv 2404.15409 ↗First posted 23 Apr 2024cs.LG cs.CR stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

We present a sample- and time-efficient differentially private algorithm for ordinary least squares, with error that depends linearly on the dimension and is independent of the condition number of X^top X, where X is the design matrix. All prior private algorithms for this task require either d3/2 examples, error growing polynomially with the condition number, or exponential time. Our near-optimal accuracy guarantee holds for any dataset with bounded statistical leverage and bounded residuals. Technically, we build on the approach of Brown et al. (2023) for private mean estimation, adding scaled noise to a carefully designed stable nonprivate estimator of the empirical regression vector.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 30 of its 56 references that are in the map. First posted on arXiv 23 Apr 2024.

Builds on

30 of 56 references.

References · 30

  1. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  2. 2018Privately Learning High-Dimensional Distributionscited by 103
  3. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  4. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  5. 2021Robust and Differentially Private Mean Estimationcited by 66
  6. 2021Differential privacy and robust statistics in high dimensionscited by 64
  7. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  8. 2019Private Hypothesis Selectioncited by 60
  9. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  10. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  11. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  12. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
18 more
  1. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  2. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  3. 2015Robust Regression via Hard Thresholdingcited by 39
  4. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  5. 2015Differentially Private Ordinary Least Squarescited by 36
  6. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  7. 2016On the Theory and Practice of Privacy-Preserving Bayesian Data Analysiscited by 34
  8. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  9. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  10. 2020Differentially Private Simple Linear Regressioncited by 33
  11. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  12. 2019Adaptive Hard Thresholding for Near-optimal Consistent Robust Regressioncited by 23
  13. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  14. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  15. 2013Bayesian Differential Privacy through Posterior Samplingcited by 17
  16. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  17. 2019Iterative Least Trimmed Squares for Mixed Linear Regressioncited by 13
  18. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 2.

7 papers.

  1. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  2. 2026Near-Optimal Private Linear Regression via Iterative Hessian Mixingcited by 1
  3. 2026Adaptive Power Iteration Method for Differentially Private PCAcited by 1
  4. 2024Privacy-Computation trade-offs in Private Repetition and Metaselectioncited by 0
  5. 2025Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regressioncited by 0
  6. 2025Private Sketches for Linear Regressioncited by 0
  7. 2025On the Accuracy of Newton Step and Influence Function Data Attributionscited by 0