# Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 21 Feb 2024.

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

- [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)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [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)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent](https://mlsanity.com/paper/2006.06783/) (2020)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [Parametric Bootstrap for Differentially Private Confidence Intervals](https://mlsanity.com/paper/2006.07749/) (2020)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacy](https://mlsanity.com/paper/2110.14465/) (2021)
- [Differentially Private Confidence Intervals for Empirical Risk Minimization](https://mlsanity.com/paper/1804.03794/) (2018)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Differentially Private Bootstrap: New Privacy Analysis and Inference Strategies](https://mlsanity.com/paper/2210.06140/) (2022)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [(Nearly) Optimal Private Linear Regression via Adaptive Clipping](https://mlsanity.com/paper/2207.04686/) (2022)
- [Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression](https://mlsanity.com/paper/2207.13289/) (2022)
- [Improved Differentially Private Regression via Gradient Boosting](https://mlsanity.com/paper/2303.03451/) (2023)
- [Training Private Models That Know What They Don't Know](https://mlsanity.com/paper/2305.18393/) (2023)

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

- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [BadGD: A unified data-centric framework to identify gradient descent vulnerabilities](https://mlsanity.com/paper/2405.15979/) (2024)
- [Private Regression via Data-Dependent Sufficient Statistic Perturbation](https://mlsanity.com/paper/2405.15002/) (2024)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacy](https://mlsanity.com/paper/2407.04884/) (2024)
- [The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches](https://mlsanity.com/paper/2505.24603/) (2025)
- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)
- [Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regression](https://mlsanity.com/paper/2509.22794/) (2025)
- [Privacy Amplification Persists under Unlimited Synthetic Data Release](https://mlsanity.com/paper/2602.04895/) (2026)
- [Enhancing Differentially Private Mechanisms via Empirical Bayes](https://mlsanity.com/paper/2606.21107/) (2026)
- [A Sharp Transition in Data Reconstruction under Differential Privacy](https://mlsanity.com/paper/2609.37344/) (2026)
- [Differential Privacy of Gradient Descent on Perturbed Objectives](https://mlsanity.com/paper/2610.02716/) (2026)

## Abstract (arXiv)

We provide an improved analysis of standard differentially private gradient descent for linear regression under the squared error loss. Under modest assumptions on the input, we characterize the distribution of the iterate at each time step. Our analysis leads to new results on the algorithm's accuracy: for a proper fixed choice of hyperparameters, the sample complexity depends only linearly on the dimension of the data. This matches the dimension-dependence of the (non-private) ordinary least squares estimator as well as that of recent private algorithms that rely on sophisticated adaptive gradient-clipping schemes (Varshney et al., 2022; Liu et al., 2023). Our analysis of the iterates' distribution also allows us to construct confidence intervals for the empirical optimizer which adapt automatically to the variance of the algorithm on a particular data set. We validate our theorems through experiments on synthetic data.