# Differentially Private Regression with Unbounded Covariates

arXiv: https://arxiv.org/abs/2202.11199 · HTML: https://mlsanity.com/paper/2202.11199/

## Key facts

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

## Builds on (most cited first, 30 of 36)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [More Data Can Hurt for Linear Regression: Sample-wise Double Descent](https://mlsanity.com/paper/1912.07242/) (2019)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Analytic Study of Double Descent in Binary Classification: The Impact of Loss](https://mlsanity.com/paper/2001.11572/) (2020)
- [Differentially Private Bayesian Linear Regression](https://mlsanity.com/paper/1910.13153/) (2019)
- [Differentially Private Bayesian Inference for Generalized Linear Models](https://mlsanity.com/paper/2011.00467/) (2020)

## Built on by (most cited first, 10 of 10)

- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation](https://mlsanity.com/paper/2402.13531/) (2024)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Holistic Survey of Privacy and Fairness in Machine Learning](https://mlsanity.com/paper/2307.15838/) (2023)
- [Distributed Differentially Private Data Analytics via Secure Sketching](https://mlsanity.com/paper/2412.00497/) (2024)
- [Differentially Private Linear Regression and Synthetic Data Generation with Statistical Guarantees](https://mlsanity.com/paper/2510.16974/) (2025)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Enhancing Differentially Private Linear Regression via Public Second-Moment](https://mlsanity.com/paper/2508.18037/) (2025)

## 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.