# Easy Differentially Private Linear Regression

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 41 references that are in the map.
- First posted on arXiv 15 Aug 2022.

## Builds on (most cited first, 15 of 15)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Private Selection from Private Candidates](https://mlsanity.com/paper/1811.07971/) (2018)
- [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)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Differentially private depth functions and their associated medians](https://mlsanity.com/paper/2101.02800/) (2021)
- [Duff: A Dataset-Distance-Based Utility Function Family for the Exponential Mechanism](https://mlsanity.com/paper/2010.04235/) (2020)
- [How to Find a Point in the Convex Hull Privately](https://mlsanity.com/paper/2003.13192/) (2020)
- [Differentially Private Estimation via Statistical Depth](https://mlsanity.com/paper/2207.12602/) (2022)

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

- [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)
- [Improved Differentially Private Regression via Gradient Boosting](https://mlsanity.com/paper/2303.03451/) (2023)
- [Better Private Linear Regression Through Better Private Feature Selection](https://mlsanity.com/paper/2306.00920/) (2023)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Label Differential Privacy via Aggregation](https://mlsanity.com/paper/2310.10092/) (2023)
- [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024)
- [Improved subsample-and-aggregate via the private modified winsorized mean](https://mlsanity.com/paper/2501.14095/) (2025)
- [Differentially Private Linear Regression and Synthetic Data Generation with Statistical Guarantees](https://mlsanity.com/paper/2510.16974/) (2025)
- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)
- [The Normal Distributions Indistinguishability Spectrum and its Application to Privacy-Preserving Machine Learning](https://mlsanity.com/paper/2309.01243/) (2023)
- [DP-KAN: Differentially Private Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2407.12569/) (2024)
- [Testing Credibility of Public and Private Surveys through the Lens of Regression](https://mlsanity.com/paper/2410.05458/) (2024)
- [Private Linear Regression with Differential Privacy and PAC Privacy](https://mlsanity.com/paper/2412.02578/) (2024)
- [Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression](https://mlsanity.com/paper/2509.22794/) (2025)
- [Refined Differentially Private Linear Regression via Extension of a Free Lunch Result](https://mlsanity.com/paper/2604.11820/) (2026)
- [Enhancing Differentially Private Mechanisms via Empirical Bayes](https://mlsanity.com/paper/2606.21107/) (2026)

## Abstract (arXiv)

Linear regression is a fundamental tool for statistical analysis. This has motivated the development of linear regression methods that also satisfy differential privacy and thus guarantee that the learned model reveals little about any one data point used to construct it. However, existing differentially private solutions assume that the end user can easily specify good data bounds and hyperparameters. Both present significant practical obstacles. In this paper, we study an algorithm which uses the exponential mechanism to select a model with high Tukey depth from a collection of non-private regression models. Given n samples of d-dimensional data used to train m models, we construct an efficient analogue using an approximate Tukey depth that runs in time O(d2n + dmlog(m)). We find that this algorithm obtains strong empirical performance in the data-rich setting with no data bounds or hyperparameter selection required.