mlsanityData to 7 Oct 2026

Near Optimal Private and Robust Linear Regression

arXiv 2301.13273 ↗First posted 30 Jan 2023cs.LG cs.CR math.STcited by 9

Not on the map. Why?

Abstract (arXiv)

We study the canonical statistical estimation problem of linear regression from n i.i.d.~examples under (varepsilon,δ)-differential privacy when some response variables are adversarially corrupted. We propose a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. When there is no adversarial corruption, this algorithm improves upon the existing state-of-the-art approach and achieves a near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm to guarantee both (varepsilon,δ)-DP and robustness. Synthetic experiments confirm the superiority of our approach.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 60 of its 94 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

60 of 94 references.

References · 60

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2017Renyi Differential Privacycited by 643
  3. 2013The Composition Theorem for Differential Privacycited by 290
  4. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  5. 2018Subsampled R'enyi Differential Privacy and Analytical Moments Accountantcited by 234
  6. 2019Differentially Private Learning with Adaptive Clippingcited by 218
  7. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  8. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  9. 2021Numerical Composition of Differential Privacycited by 174
  10. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  11. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  12. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
38 more
  1. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  2. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  3. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  4. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  5. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  6. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  7. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  8. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  9. 2021Robust and Differentially Private Mean Estimationcited by 66
  10. 2021Differential privacy and robust statistics in high dimensionscited by 64
  11. 2015Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlocited by 61
  12. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  13. 2017Learning From Noisy Singly-labeled Datacited by 50
  14. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  15. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  16. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  17. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  18. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  19. 2017Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12cited by 42
  20. 2018Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regressioncited by 42
  21. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  22. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  23. 2015Robust Regression via Hard Thresholdingcited by 39
  24. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  25. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  26. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  27. 2019Generalized Resilience and Robust Statisticscited by 37
  28. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  29. 2016On the Theory and Practice of Privacy-Preserving Bayesian Data Analysiscited by 34
  30. 2020Differentially Private Simple Linear Regressioncited by 33
  31. 2019Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimatorcited by 31
  32. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 31
  33. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  34. 2018Robustness of Conditional GANs to Noisy Labelscited by 27
  35. 2019On Robustness of Principal Component Regressioncited by 27
  36. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  37. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  38. 2019Adaptive Hard Thresholding for Near-optimal Consistent Robust Regressioncited by 23

50 most cited of 60 All 60 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

9 papers.

  1. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  2. 2023Correlated Noise Provably Beats Independent Noise for Differentially Private Learningcited by 23
  3. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 11
  4. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  5. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  6. 2026Near-Optimal Private Linear Regression via Iterative Hessian Mixingcited by 1
  7. 2023The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learningcited by 0
  8. 2025Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regressioncited by 0
  9. 2025Privately Estimating Black-Box Statisticscited by 0