{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T08:57:36Z","timestamp":1774515456256,"version":"3.50.1"},"reference-count":32,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"2","license":[{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,4,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Economics and social science research often require analyzing datasets of sensitive personal information at fine granularity, with models fit to small subsets of the data. Unfortunately, such fine-grained analysis can easily reveal sensitive individual information. We study regression algorithms that satisfy <jats:italic>differential privacy<\/jats:italic>, a constraint which guarantees that an algorithm\u2019s output reveals little about any individual input data record, even to an attacker with side information about the dataset. Motivated by the <jats:italic>Opportunity Atlas<\/jats:italic>, a high-profile, small-area analysis tool in economics research, we perform a thorough experimental evaluation of differentially private algorithms for simple linear regression on small datasets with tens to hundreds of records\u2014a particularly challenging regime for differential privacy. In contrast, prior work on differentially private linear regression focused on multivariate linear regression on large datasets or asymptotic analysis. Through a range of experiments, we identify key factors that affect the relative performance of the algorithms. We find that algorithms based on robust estimators\u2014in particular, the median-based estimator of Theil and Sen\u2014perform best on small datasets (e.g., hundreds of datapoints), while algorithms based on Ordinary Least Squares or Gradient Descent perform better for large datasets. However, we also discuss regimes in which this general finding does not hold. Notably, the differentially private analogues of Theil\u2013Sen (one of which was suggested in a theoretical work of Dwork and Lei) have not been studied in any prior experimental work on differentially private linear regression.<\/jats:p>","DOI":"10.2478\/popets-2022-0041","type":"journal-article","created":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T04:26:49Z","timestamp":1646454409000},"page":"184-204","source":"Crossref","is-referenced-by-count":7,"title":["Differentially Private Simple Linear Regression"],"prefix":"10.56553","volume":"2022","author":[{"given":"Daniel","family":"Alabi","sequence":"first","affiliation":[{"name":"Harvard John A. Paulson School of Engineering and Applied Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Audra","family":"McMillan","sequence":"additional","affiliation":[{"name":"Khoury College of Computer Sciences , Northeastern University and Department of Computer Science, Boston University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayshree","family":"Sarathy","sequence":"additional","affiliation":[{"name":"Harvard John A. Paulson School of Engineering and Applied Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Smith","sequence":"additional","affiliation":[{"name":"Department of Computer Science , Boston University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[{"name":"Harvard John A. Paulson School of Engineering and Applied Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"35752","published-online":{"date-parts":[[2022,3,3]]},"reference":[{"key":"2022060207223125687_j_popets-2022-0041_ref_001","unstructured":"[1] Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. 2016. Perturbation techniques in online learning and optimization. Perturbations, Optimization, and Statistics (2016), 233."},{"key":"2022060207223125687_j_popets-2022-0041_ref_002","doi-asserted-by":"crossref","unstructured":"[2] Oguz Akbiligic, Hamparsum Bozdogan, and M. Erdal Balaban. 2013. A novel Hybrid RBF Neural Networks model as a forecaster. Statistics and Computing (2013). This dataset was collected from imkb.gov.tr and finance.yahoo.com.","DOI":"10.1007\/s11222-013-9375-7"},{"key":"2022060207223125687_j_popets-2022-0041_ref_003","unstructured":"[3] Hilal Asi and John C Duchi. 2020. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in Neural Information Processing Systems 33 (2020)."},{"key":"2022060207223125687_j_popets-2022-0041_ref_004","unstructured":"[4] Jordan Awan and Aleksandra Slavkovi\u0107. 2020. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. J. Amer. Statist. Assoc. just-accepted (2020), 1\u201356."},{"key":"2022060207223125687_j_popets-2022-0041_ref_005","unstructured":"[5] Emily Badger and Quoctrung Bui. 2020. Detailed Maps Show How Neighborhoods Shape Children for Life. https:\/\/www.nytimes.com\/2018\/10\/01\/upshot\/maps-neighborhoods-shape-child-poverty.html. Online; accessed 15 October 2020."},{"key":"2022060207223125687_j_popets-2022-0041_ref_006","doi-asserted-by":"crossref","unstructured":"[6] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. 2014. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. 464\u2013473.","DOI":"10.1109\/FOCS.2014.56"},{"key":"2022060207223125687_j_popets-2022-0041_ref_007","unstructured":"[7] Garrett Bernstein and Daniel R Sheldon. 2019. Differentially Private Bayesian Linear Regression. In Advances in Neural Information Processing Systems 32. 523\u2013533."},{"key":"2022060207223125687_j_popets-2022-0041_ref_008","doi-asserted-by":"crossref","unstructured":"[8] Mark Bun and Thomas Steinke. 2016. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference. Springer, 635\u2013658.","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"2022060207223125687_j_popets-2022-0041_ref_009","unstructured":"[9] Mark Bun and Thomas Steinke. 2019. Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. In Advances in Neural Information Processing Systems 32. 181\u2013191."},{"key":"2022060207223125687_j_popets-2022-0041_ref_010","unstructured":"[10] Tony Cai, Yichen Wang, and Linjun Zhang. 2019. The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy. CoRR abs\/1902.04495 (2019). http:\/\/arxiv.org\/abs\/1902.04495"},{"key":"2022060207223125687_j_popets-2022-0041_ref_011","unstructured":"[11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. 2011. Differentially Private Empirical Risk Minimization. Journal of Machine Learning Research 12 (2011), 1069\u20131109."},{"key":"2022060207223125687_j_popets-2022-0041_ref_012","doi-asserted-by":"crossref","unstructured":"[12] Raj Chetty, John N Friedman, Nathaniel Hendren, Maggie R Jones, and Sonya R Porter. 2018. The opportunity atlas: Mapping the childhood roots of social mobility. Technical Report. National Bureau of Economic Research.10.3386\/w25147","DOI":"10.3386\/w25147"},{"key":"2022060207223125687_j_popets-2022-0041_ref_013","doi-asserted-by":"crossref","unstructured":"[13] Raj Chetty, Nathaniel Hendren, Patrick Kline, and Emmanuel Saez. 2014. Where is the land of opportunity? The geography of intergenerational mobility in the United States. The Quarterly Journal of Economics 129, 4 (2014), 1553\u20131623.","DOI":"10.1093\/qje\/qju022"},{"key":"2022060207223125687_j_popets-2022-0041_ref_014","unstructured":"[14] Graham Cormode. [n. d.]. Building Blocks of Privacy: Differentially Private Mechanisms. ([n. d.]), 18\u201319."},{"key":"2022060207223125687_j_popets-2022-0041_ref_015","doi-asserted-by":"crossref","unstructured":"[15] Simon Couch, Zeki Kazan, Kaiyan Shi, Andrew Bray, and Adam Groce. 2019. Differentially Private Nonparametric Hypothesis Testing. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS \u201919). 737\u2013751.10.1145\/3319535.3339821","DOI":"10.1145\/3319535.3339821"},{"key":"2022060207223125687_j_popets-2022-0041_ref_016","doi-asserted-by":"crossref","unstructured":"[16] Alfred DeMaris. 2004. Regression with social data : modeling continuous and limited response variables. Wiley-Interscience, Hoboken, NJ.10.1002\/0471677566","DOI":"10.1002\/0471677566"},{"key":"2022060207223125687_j_popets-2022-0041_ref_017","doi-asserted-by":"crossref","unstructured":"[17] Irit Dinur and Kobbi Nissim. 2003. Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 202\u2013210.10.1145\/773153.773173","DOI":"10.1145\/773153.773173"},{"key":"2022060207223125687_j_popets-2022-0041_ref_018","doi-asserted-by":"crossref","unstructured":"[18] Cynthia Dwork and Jing Lei. 2009. Differential privacy and robust statistics.. In STOC, Vol. 9. 371\u2013380.","DOI":"10.1145\/1536414.1536466"},{"key":"2022060207223125687_j_popets-2022-0041_ref_019","doi-asserted-by":"crossref","unstructured":"[19] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings. 265\u2013284.","DOI":"10.1007\/11681878_14"},{"key":"2022060207223125687_j_popets-2022-0041_ref_020","doi-asserted-by":"crossref","unstructured":"[20] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. 2014. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In STOC. 11\u201320.10.1145\/2591796.2591883","DOI":"10.1145\/2591796.2591883"},{"key":"2022060207223125687_j_popets-2022-0041_ref_021","doi-asserted-by":"crossref","unstructured":"[21] Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings. 94\u2013103.","DOI":"10.1109\/FOCS.2007.66"},{"key":"2022060207223125687_j_popets-2022-0041_ref_022","doi-asserted-by":"crossref","unstructured":"[22] Frank D McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. 19\u201330.10.1145\/1559845.1559850","DOI":"10.1145\/1559845.1559850"},{"key":"2022060207223125687_j_popets-2022-0041_ref_023","unstructured":"[23] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. 75\u201384."},{"key":"2022060207223125687_j_popets-2022-0041_ref_024","doi-asserted-by":"crossref","unstructured":"[24] Pranab Kumar Sen. 1968. Estimates of the regression coefficient based on Kendall\u2019s tau. Journal of the American statistical association 63, 324 (1968), 1379\u20131389.","DOI":"10.1080\/01621459.1968.10480934"},{"key":"2022060207223125687_j_popets-2022-0041_ref_025","unstructured":"[25] Or Sheffet. 2017. Differentially Private Ordinary Least Squares. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. 3105\u20133114. http:\/\/proceedings.mlr.press\/v70\/sheffet17a.html"},{"key":"2022060207223125687_j_popets-2022-0041_ref_026","doi-asserted-by":"crossref","unstructured":"[26] Adam Smith. 2011. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium on Theory of computing. 813\u2013822.10.1145\/1993636.1993743","DOI":"10.1145\/1993636.1993743"},{"key":"2022060207223125687_j_popets-2022-0041_ref_027","doi-asserted-by":"crossref","unstructured":"[27] Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. 2013. Stochastic gradient descent with differentially private updates. In IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013, Austin, TX, USA, December 3-5, 2013. 245\u2013248.","DOI":"10.1109\/GlobalSIP.2013.6736861"},{"key":"#cr-split#-2022060207223125687_j_popets-2022-0041_ref_028.1","unstructured":"[28] Henri Theil. 1950. A rank-invariant method of linear and polynomial regression analysis, 3"},{"key":"#cr-split#-2022060207223125687_j_popets-2022-0041_ref_028.2","unstructured":"confidence regions for the parameters of polynomial regression equations. Indagationes Mathematicae 1, 2 (1950), 467-482."},{"key":"2022060207223125687_j_popets-2022-0041_ref_029","unstructured":"[29] Yu-Xiang Wang. 2018. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018. 93\u2013103."},{"key":"2022060207223125687_j_popets-2022-0041_ref_030","unstructured":"[30] Xin Yan and Xiao Gang Su. 2009. Linear Regression Analysis: Theory and Computing. World Scientific Publishing Co., Inc., USA.10.1142\/6986"},{"key":"2022060207223125687_j_popets-2022-0041_ref_031","doi-asserted-by":"crossref","unstructured":"[31] Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. 2012. Functional Mechanism: Regression Analysis under Differential Privacy. Proc. VLDB Endow. 5, 11 (2012), 1364\u20131375.10.14778\/2350229.2350253","DOI":"10.14778\/2350229.2350253"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2022-0041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:32:02Z","timestamp":1658334722000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2022\/popets-2022-0041.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,3]]},"references-count":32,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,3,3]]},"published-print":{"date-parts":[[2022,4,1]]}},"alternative-id":["10.2478\/popets-2022-0041"],"URL":"https:\/\/doi.org\/10.2478\/popets-2022-0041","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,3]]}}}