mlsanityData to 14 Oct 2026

(Nearly) Optimal Private Linear Regression via Adaptive Clipping

arXiv 2207.04686 ↗First posted 11 Jul 2022cs.LG cs.CR math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the problem of differentially private linear regression where each data point is sampled from a fixed sub-Gaussian style distribution. We propose and analyze a one-pass mini-batch stochastic gradient descent method (DP-AMBSSGD) where points in each iteration are sampled without replacement. Noise is added for DP but the noise standard deviation is estimated online. Compared to existing (ε, δ)-DP techniques which have sub-optimal error bounds, DP-AMBSSGD is able to provide nearly optimal error bounds in terms of key parameters like dimensionality d, number of points N, and the standard deviation σ of the noise in observations. For example, when the d-dimensional covariates are sampled i.i.d. from the normal distribution, then the excess error of DP-AMBSSGD due to privacy is fracσ2 dN(1+fracdε2 N), i.e., the error is meaningful when number of samples N= Omega(d log d) which is the standard operative regime for linear regression. In contrast, error bounds for existing efficient methods in this setting are: Obig(fracd3ε2 N2big), even for σ=0. That is, for constant ε, the existing techniques require N=Omega(d√d) to provide a non-trivial result.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 20 of its 43 references that are in the map. First posted on arXiv 11 Jul 2022.

Builds on

20 of 43 references.

References · 20

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2017Renyi Differential Privacycited by 650
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  4. 2019Differentially Private Learning with Adaptive Clippingcited by 220
  5. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  8. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 107
  9. 2018Privately Learning High-Dimensional Distributionscited by 104
  10. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  11. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  12. 2019AdaCliP: Adaptive Clipping for Private SGDcited by 77
8 more
  1. 2018Private Selection from Private Candidatescited by 75
  2. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  3. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  4. 2021Differential privacy and robust statistics in high dimensionscited by 64
  5. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  6. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  7. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 26
  8. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 3.

6 papers.

  1. 2024Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimationcited by 12
  2. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  3. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  4. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  5. 2025Differentially Private Two-Stage Gradient Descent for Instrumental Variable Regressioncited by 0
  6. 2025Differentially Private High-dimensional Variable Selection via Integer Programmingcited by 0