mlsanityData to 7 Oct 2026

Differentially Private Regression with Unbounded Covariates

arXiv 2202.11199 ↗First posted 19 Feb 2022cs.CR cs.DS cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

We provide computationally efficient, differentially private algorithms for the classical regression settings of Least Squares Fitting, Binary Regression and Linear Regression with unbounded covariates. Prior to our work, privacy constraints in such regression settings were studied under strong a priori bounds on covariates. We consider the case of Gaussian marginals and extend recent differentially private techniques on mean and covariance estimation (Kamath et al., 2019; Karwa and Vadhan, 2018) to the sub-gaussian regime. We provide a novel technical analysis yielding differentially private algorithms for the above classical regression settings. Through the case of Binary Regression, we capture the fundamental and widely-studied models of logistic regression and linearly-separable SVMs, learning an unbiased estimate of the true regression vector, up to a scaling factor.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 36 of its 65 references that are in the map. First posted on arXiv 19 Feb 2022.

Builds on

36 of 65 references.

References · 36

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  5. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  6. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  7. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  8. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  9. 2018Privately Learning High-Dimensional Distributionscited by 103
  10. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  11. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  12. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
24 more
  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2017Efficient Private ERM for Smooth Objectivescited by 61
  4. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  5. 2015Differentially Private Release and Learning of Threshold Functionscited by 58
  6. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  7. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  8. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  9. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  10. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  11. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  12. 2019More Data Can Hurt for Linear Regression: Sample-wise Double Descentcited by 37
  13. 2015Differentially Private Ordinary Least Squarescited by 36
  14. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  15. 2020Differentially Private Simple Linear Regressioncited by 33
  16. 2020Analytic Study of Double Descent in Binary Classification: The Impact of Losscited by 28
  17. 2019Differentially Private Bayesian Linear Regressioncited by 24
  18. 2020Differentially Private Bayesian Inference for Generalized Linear Modelscited by 16
  19. 2020The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Boundscited by 15
  20. 2020Truncated Linear Regression in High Dimensionscited by 13
  21. 2017Differentially private significance tests for regression coefficientscited by 12
  22. 2013Learning Mixtures of Linear Classifierscited by 8
  23. 2015Newton-Stein Method: An optimization method for GLMs via Stein's Lemmacited by 3
  24. 2021On the Sample Complexity of Rank Regression from Pairwise Comparisonscited by 1

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 4; 2024: 2; 2025: 2.

10 papers.

  1. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  2. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  3. 2022Easy Differentially Private Linear Regressioncited by 19
  4. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 11
  5. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  6. 2023Holistic Survey of Privacy and Fairness in Machine Learningcited by 4
  7. 2024Distributed Differentially Private Data Analytics via Secure Sketchingcited by 1
  8. 2025Differentially Private Linear Regression and Synthetic Data Generation with Statistical Guaranteescited by 1
  9. 2023PRIMO: Private Regression in Multiple Outcomescited by 0
  10. 2025Enhancing Differentially Private Linear Regression via Public Second-Momentcited by 0