mlsanityData to 7 Oct 2026

Nearly Optimal Differentially Private ReLU Regression

arXiv 2503.06009 ↗First posted 8 Mar 2025cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate one of the most fundamental nonconvex learning problems, ReLU regression, in the Differential Privacy (DP) model. Previous studies on private ReLU regression heavily rely on stringent assumptions, such as constant bounded norms for feature vectors and labels. We relax these assumptions to a more standard setting, where data can be i.i.d. sampled from O(1)-sub-Gaussian distributions. We first show that when varepsilon = tildeO(√frac1N) and there is some public data, it is possible to achieve an upper bound of tildeO(fracd2N2 varepsilon2) for the excess population risk in (ε, δ)-DP, where d is the dimension and N is the number of data samples. Moreover, we relax the requirement of ε and public data by proposing and analyzing a one-pass mini-batch Generalized Linear Model Perceptron algorithm (DP-MBGLMtron). Additionally, using the tracing attack argument technique, we demonstrate that the minimax rate of the estimation error for (varepsilon, δ)-DP algorithms is lower bounded by Omega(fracd2N2 varepsilon2). This shows that DP-MBGLMtron achieves the optimal utility bound up to logarithmic factors. Experiments further support our theoretical results.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 30 of its 65 references that are in the map. First posted on arXiv 8 Mar 2025.

Builds on

30 of 65 references.

References · 30

  1. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  3. 2019Differentially Private Learning with Adaptive Clippingcited by 218
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  5. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  6. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  7. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  8. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  9. 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 88
  10. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  11. 2017Efficient Private ERM for Smooth Objectivescited by 61
  12. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
18 more
  1. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  2. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  3. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  4. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  5. 2019Efficient Privacy-Preserving Stochastic Nonconvex Optimizationcited by 27
  6. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  7. 2024Understanding Forgetting in Continual Learning with Linear Regressioncited by 26
  8. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  9. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  10. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21
  11. 2023Differentially Private Non-convex Learning for Multi-layer Neural Networkscited by 10
  12. 2019Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Datacited by 9
  13. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  14. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  15. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  16. 2022(Nearly) Optimal Private Linear Regression via Adaptive Clippingcited by 6
  17. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  18. 2024Truthful High Dimensional Sparse Linear Regressioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  2. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  3. 2026Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Datacited by 0