# High-Dimensional Private Linear Regression with Optimal Rates

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2025.

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

- [High-Dimensional Privacy-Utility Dynamics of Noisy Stochastic Gradient Descent on Least Squares](https://mlsanity.com/paper/2510.16687/) (2025)
- [Privately Estimating Monotone Statistics in Polynomial Time](https://mlsanity.com/paper/2605.27912/) (2026)
- [A Sharp Transition in Data Reconstruction under Differential Privacy](https://mlsanity.com/paper/2609.37344/) (2026)
- [High-Dimensional Asymptotics and Dataset Selection for Private Transfer Learning](https://mlsanity.com/paper/2610.02578/) (2026)

## Abstract (arXiv)

Differentially private (DP) linear regression has received significant attention in the recent theoretical literature, with several approaches proposed to improve error rates. Our work considers the popular high-dimensional regime with random data, where the number of training samples n and the input dimension d grow at a proportional rate d / n → γ, and it studies a family of one-pass DP gradient descent (DP-GD) algorithms satisfying ρ2 / 2 zero concentrated DP. In this setting, we establish a deterministic equivalent for the DP-GD trajectory in terms of a system of ordinary differential equations. This allows to analyze the effect of gradient clipping constants that are smaller than the typical norm of the per-sample gradients - a setup shown to improve performance in practice. For well-conditioned data, we show that DP-GD, upon properly choosing clipping constant and learning rate, achieves the non-asymptotic risk of O(γ + γ2 / ρ2), and we establish that this rate is minimax optimal. Then, we consider the ill-conditioned case where the data covariance spectrum follows a power-law distribution, and we show that the risk displays a power-like scaling law in γ, highlighting the change in the exponent as a function of the privacy parameter ρ. Overall, our analysis demonstrates the benefits of practical algorithmic design choices, including aggressive gradient clipping and decaying learning rate schedules.