# Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2025.

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

- [Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2602.00417/) (2026)
- [Locally Private Nonparametric Contextual Multi-armed Bandits](https://mlsanity.com/paper/2503.08098/) (2025)
- [Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits](https://mlsanity.com/paper/2609.33888/) (2026)

## Abstract (arXiv)

We study the statistical complexity of private linear regression under an unknown, potentially ill-conditioned covariate distribution. Somewhat surprisingly, under privacy constraints the intrinsic complexity is not captured by the usual covariance matrix but rather its L1 analogues. Building on this insight, we establish minimax convergence rates for both the central and local privacy models and introduce an Information-Weighted Regression method that attains the optimal rates. As application, in private linear contextual bandits, we propose an efficient algorithm that achieves rate-optimal regret bounds of order √T+frac1α and √T/α under joint and local α-privacy models, respectively. Notably, our results demonstrate that joint privacy comes at almost no additional cost, addressing the open problems posed by Azize and Basu (2024).