Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908630519906304 |
|---|---|
| author | Chen, Fan Li, Jiachun Rakhlin, Alexander Simchi-Levi, David |
| author_facet | Chen, Fan Li, Jiachun Rakhlin, Alexander Simchi-Levi, David |
| contents | 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 \emph{not} captured by the usual covariance matrix but rather its $L_1$ 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 $\sqrt{T}+\frac{1}α$ and $\sqrt{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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13115 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression Chen, Fan Li, Jiachun Rakhlin, Alexander Simchi-Levi, David Machine Learning Artificial Intelligence Cryptography and Security Statistics Theory 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 \emph{not} captured by the usual covariance matrix but rather its $L_1$ 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 $\sqrt{T}+\frac{1}α$ and $\sqrt{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). |
| title | Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression |
| topic | Machine Learning Artificial Intelligence Cryptography and Security Statistics Theory |
| url | https://arxiv.org/abs/2502.13115 |