# Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy](https://mlsanity.com/paper/2106.13673/) (2021)
- [Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping](https://mlsanity.com/paper/2212.01539/) (2022)
- [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://mlsanity.com/paper/2306.08153/) (2023)
- [When Does Differentially Private Learning Not Suffer in High Dimensions?](https://mlsanity.com/paper/2207.00160/) (2022)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Dynamic Differential-Privacy Preserving SGD](https://mlsanity.com/paper/2111.00173/) (2021)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach](https://mlsanity.com/paper/2311.14632/) (2023)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation](https://mlsanity.com/paper/2402.13531/) (2024)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Differentially Private Image Classification from Features](https://mlsanity.com/paper/2211.13403/) (2022)
- [(Nearly) Optimal Private Linear Regression via Adaptive Clipping](https://mlsanity.com/paper/2207.04686/) (2022)
- [DC-SGD: Differentially Private SGD with Dynamic Clipping through Gradient Norm Distribution Estimation](https://mlsanity.com/paper/2503.22988/) (2025)
- [Differentially Private Deep Learning with ModelMix](https://mlsanity.com/paper/2210.03843/) (2022)
- [Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization](https://mlsanity.com/paper/2204.01585/) (2022)
- [Personalized Differential Privacy for Ridge Regression](https://mlsanity.com/paper/2401.17127/) (2024)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)
- [Understanding Private Learning From Feature Perspective](https://mlsanity.com/paper/2511.18006/) (2025)
- [High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees](https://mlsanity.com/paper/2104.00245/) (2021)
- [The importance of feature preprocessing for differentially private linear optimization](https://mlsanity.com/paper/2307.11106/) (2023)
- [Bias-Aware Minimisation: Understanding and Mitigating Estimator Bias in Private SGD](https://mlsanity.com/paper/2308.12018/) (2023)
- [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024)

## Abstract (arXiv)

We revisit the well-studied problem of differentially private empirical risk minimization (ERM). We show that for unconstrained convex generalized linear models (GLMs), one can obtain an excess empirical risk of tilde Oleft(√textttrank/ε nright), where textttrank is the rank of the feature matrix in the GLM problem, n is the number of data samples, and ε is the privacy parameter. This bound is attained via differentially private gradient descent (DP-GD). Furthermore, via the first lower bound for unconstrained private ERM, we show that our upper bound is tight. In sharp contrast to the constrained ERM setting, there is no dependence on the dimensionality of the ambient model space (p). (Notice that textttrank≤ minn, p.) Besides, we obtain an analogous excess population risk bound which depends on textttrank instead of p. For the smooth non-convex GLM setting (i.e., where the objective function is non-convex but preserves the GLM structure), we further show that DP-GD attains a dimension-independent convergence of tilde Oleft(√textttrank/ε nright) to a first-order-stationary-point of the underlying objective. Finally, we show that for convex GLMs, a variant of DP-GD commonly used in practice (which involves clipping the individual gradients) also exhibits the same dimension-independent convergence to the minimum of a well-defined objective. To that end, we provide a structural lemma that characterizes the effect of clipping on the optimization profile of DP-GD.