Differentially Private Regression with Unbounded Covariates

Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, Stratis Ioannidis
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:3242-3273, 2022.

Abstract

We provide computationally efficient, differentially private algorithms for the classical regression settings of Least Squares Fitting, Binary Regression and Linear Regression with unbounded covariates. Prior to our work, privacy constraints in such regression settings were studied under strong a priori bounds on covariates. We consider the case of Gaussian marginals and extend recent differentially private techniques on mean and covariance estimation (Kamath et al., 2019; Karwa and Vadhan, 2018) to the sub-gaussian regime. We provide a novel technical analysis yielding differentially private algorithms for the above classical regression settings. Through the case of Binary Regression, we capture the fundamental and widely-studied models of logistic regression and linearly-separable SVMs, learning an unbiased estimate of the true regression vector, up to a scaling factor.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-milionis22a, title = { Differentially Private Regression with Unbounded Covariates }, author = {Milionis, Jason and Kalavasis, Alkis and Fotakis, Dimitris and Ioannidis, Stratis}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {3242--3273}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/milionis22a/milionis22a.pdf}, url = {https://proceedings.mlr.press/v151/milionis22a.html}, abstract = { We provide computationally efficient, differentially private algorithms for the classical regression settings of Least Squares Fitting, Binary Regression and Linear Regression with unbounded covariates. Prior to our work, privacy constraints in such regression settings were studied under strong a priori bounds on covariates. We consider the case of Gaussian marginals and extend recent differentially private techniques on mean and covariance estimation (Kamath et al., 2019; Karwa and Vadhan, 2018) to the sub-gaussian regime. We provide a novel technical analysis yielding differentially private algorithms for the above classical regression settings. Through the case of Binary Regression, we capture the fundamental and widely-studied models of logistic regression and linearly-separable SVMs, learning an unbiased estimate of the true regression vector, up to a scaling factor. } }
Endnote
%0 Conference Paper %T Differentially Private Regression with Unbounded Covariates %A Jason Milionis %A Alkis Kalavasis %A Dimitris Fotakis %A Stratis Ioannidis %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-milionis22a %I PMLR %P 3242--3273 %U https://proceedings.mlr.press/v151/milionis22a.html %V 151 %X We provide computationally efficient, differentially private algorithms for the classical regression settings of Least Squares Fitting, Binary Regression and Linear Regression with unbounded covariates. Prior to our work, privacy constraints in such regression settings were studied under strong a priori bounds on covariates. We consider the case of Gaussian marginals and extend recent differentially private techniques on mean and covariance estimation (Kamath et al., 2019; Karwa and Vadhan, 2018) to the sub-gaussian regime. We provide a novel technical analysis yielding differentially private algorithms for the above classical regression settings. Through the case of Binary Regression, we capture the fundamental and widely-studied models of logistic regression and linearly-separable SVMs, learning an unbiased estimate of the true regression vector, up to a scaling factor.
APA
Milionis, J., Kalavasis, A., Fotakis, D. & Ioannidis, S.. (2022). Differentially Private Regression with Unbounded Covariates . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:3242-3273 Available from https://proceedings.mlr.press/v151/milionis22a.html.

Related Material