Private Linear Regression via a Down-Sensitivity to Privacy Reduction

Ittai Rubinstein, Chris Ge, Samuel B. Hopkins
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5662-5720, 2026.

Abstract

We present a sample- and time-efficient $(\varepsilon,\delta)$-differentially private (DP) algorithm for $d$-dimensional linear regression with a sample complexity of \[ n_{\mathrm{STAR}} = \widetilde{O}\left(\frac{d}{\alpha^2} + \frac{d \log(1/\delta)}{\alpha \varepsilon} + \frac{d \log(1/\delta)}{\varepsilon}\right) + o(d). \]{This} improves upon prior polynomial-time algorithms whose sample complexity either depends on the condition number of the design matrix $\kappa$ (for DP-SGD with gradient clipping), scales quadratically with the dimension (for Sum-of-Squares algorithms) or with the inverse of the privacy parameter (for outlier removal algorithms such as insufficient statistics perturbation or ISSP), \[ n_{\mathrm{SoS}} = \widetilde{\Omega}\left(\frac{d^2}{\alpha^2}\right), \quad n_{\mathrm{DP\mbox{-}SGD}} = \widetilde{\Omega}\left(\frac{d \sqrt{\kappa}}{\varepsilon}\right), \quad n_{\mathrm{ISSP}} = \widetilde{\Omega}\left(\frac{d}{\varepsilon^2}\right). \]{Our} algorithm is based on a novel \emph{subsample-test-aggregate} (STA) approach for ensuring privacy given only bounded \emph{down-sensitivity} – robustness to removal, but not addition, of a small number of samples. The intuition that down-sensitivity should be related to privacy is not new, but STA formalizes this by providing an \emph{efficient black-box reduction from down-sensitivity to privacy} which we expect to be applicable beyond the setting of linear regression.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-rubinstein26a, title = {Private Linear Regression via a Down-Sensitivity to Privacy Reduction}, author = {Rubinstein, Ittai and Ge, Chris and Hopkins, Samuel B.}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {5662--5720}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/rubinstein26a/rubinstein26a.pdf}, url = {https://proceedings.mlr.press/v336/rubinstein26a.html}, abstract = {We present a sample- and time-efficient $(\varepsilon,\delta)$-differentially private (DP) algorithm for $d$-dimensional linear regression with a sample complexity of \[ n_{\mathrm{STAR}} = \widetilde{O}\left(\frac{d}{\alpha^2} + \frac{d \log(1/\delta)}{\alpha \varepsilon} + \frac{d \log(1/\delta)}{\varepsilon}\right) + o(d). \]{This} improves upon prior polynomial-time algorithms whose sample complexity either depends on the condition number of the design matrix $\kappa$ (for DP-SGD with gradient clipping), scales quadratically with the dimension (for Sum-of-Squares algorithms) or with the inverse of the privacy parameter (for outlier removal algorithms such as insufficient statistics perturbation or ISSP), \[ n_{\mathrm{SoS}} = \widetilde{\Omega}\left(\frac{d^2}{\alpha^2}\right), \quad n_{\mathrm{DP\mbox{-}SGD}} = \widetilde{\Omega}\left(\frac{d \sqrt{\kappa}}{\varepsilon}\right), \quad n_{\mathrm{ISSP}} = \widetilde{\Omega}\left(\frac{d}{\varepsilon^2}\right). \]{Our} algorithm is based on a novel \emph{subsample-test-aggregate} (STA) approach for ensuring privacy given only bounded \emph{down-sensitivity} – robustness to removal, but not addition, of a small number of samples. The intuition that down-sensitivity should be related to privacy is not new, but STA formalizes this by providing an \emph{efficient black-box reduction from down-sensitivity to privacy} which we expect to be applicable beyond the setting of linear regression.} }
Endnote
%0 Conference Paper %T Private Linear Regression via a Down-Sensitivity to Privacy Reduction %A Ittai Rubinstein %A Chris Ge %A Samuel B. Hopkins %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-rubinstein26a %I PMLR %P 5662--5720 %U https://proceedings.mlr.press/v336/rubinstein26a.html %V 336 %X We present a sample- and time-efficient $(\varepsilon,\delta)$-differentially private (DP) algorithm for $d$-dimensional linear regression with a sample complexity of \[ n_{\mathrm{STAR}} = \widetilde{O}\left(\frac{d}{\alpha^2} + \frac{d \log(1/\delta)}{\alpha \varepsilon} + \frac{d \log(1/\delta)}{\varepsilon}\right) + o(d). \]{This} improves upon prior polynomial-time algorithms whose sample complexity either depends on the condition number of the design matrix $\kappa$ (for DP-SGD with gradient clipping), scales quadratically with the dimension (for Sum-of-Squares algorithms) or with the inverse of the privacy parameter (for outlier removal algorithms such as insufficient statistics perturbation or ISSP), \[ n_{\mathrm{SoS}} = \widetilde{\Omega}\left(\frac{d^2}{\alpha^2}\right), \quad n_{\mathrm{DP\mbox{-}SGD}} = \widetilde{\Omega}\left(\frac{d \sqrt{\kappa}}{\varepsilon}\right), \quad n_{\mathrm{ISSP}} = \widetilde{\Omega}\left(\frac{d}{\varepsilon^2}\right). \]{Our} algorithm is based on a novel \emph{subsample-test-aggregate} (STA) approach for ensuring privacy given only bounded \emph{down-sensitivity} – robustness to removal, but not addition, of a small number of samples. The intuition that down-sensitivity should be related to privacy is not new, but STA formalizes this by providing an \emph{efficient black-box reduction from down-sensitivity to privacy} which we expect to be applicable beyond the setting of linear regression.
APA
Rubinstein, I., Ge, C. & Hopkins, S.B.. (2026). Private Linear Regression via a Down-Sensitivity to Privacy Reduction. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:5662-5720 Available from https://proceedings.mlr.press/v336/rubinstein26a.html.

Related Material