mlsanityData to 7 Oct 2026

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

arXiv 2402.13531 ↗First posted 21 Feb 2024cs.LG cs.CRcited by 11

Not on the map. Why?

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.

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

Builds on

27 of 46 references.

References · 27

  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. 2016Concentrated Differential Privacycited by 139
  5. 2018Privately Learning High-Dimensional Distributionscited by 103
  6. 2022Toward Training at ImageNet Scale with Differential Privacycited by 87
  7. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  8. 2021Differential privacy and robust statistics in high dimensionscited by 64
  9. 2023Federated Learning of Gboard Language Models with Differential Privacycited by 64
  10. 2018Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domaincited by 60
  11. 2015Differentially Private Ordinary Least Squarescited by 36
  12. 2016On the Theory and Practice of Privacy-Preserving Bayesian Data Analysiscited by 34
15 more
  1. 2020Differentially Private Simple Linear Regressioncited by 33
  2. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  3. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  4. 2021Differentially private inference via noisy optimizationcited by 27
  5. 2020Parametric Bootstrap for Differentially Private Confidence Intervalscited by 19
  6. 2022Easy Differentially Private Linear Regressioncited by 19
  7. 2021Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacycited by 15
  8. 2018Differentially Private Confidence Intervals for Empirical Risk Minimizationcited by 11
  9. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  10. 2022Differentially Private Bootstrap: New Privacy Analysis and Inference Strategiescited by 9
  11. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  12. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  13. 2022Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regressioncited by 6
  14. 2023Improved Differentially Private Regression via Gradient Boostingcited by 6
  15. 2023Training Private Models That Know What They Don't Knowcited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

11 papers.

  1. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  2. 2024BadGD: A unified data-centric framework to identify gradient descent vulnerabilitiescited by 5
  3. 2024Private Regression via Data-Dependent Sufficient Statistic Perturbationcited by 4
  4. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  5. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  6. 2025The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketchescited by 2
  7. 2026Near-Optimal Private Linear Regression via Iterative Hessian Mixingcited by 1
  8. 2025Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regressioncited by 0
  9. 2026Privacy Amplification Persists under Unlimited Synthetic Data Releasecited by 0
  10. 2026Enhancing Differentially Private Mechanisms via Empirical Bayescited by 0
  11. 2026A Sharp Transition in Data Reconstruction under Differential Privacycited by 0