Private Protocols for U-Statistics in the Local Model and Beyond

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorBell, Jamesen_US
dc.contributor.authorBellet, Aurelienen_US
dc.contributor.authorGascon, Adriaen_US
dc.contributor.authorKulkarni, Tejasen_US
dc.contributor.departmentAlan Turing Instituteen_US
dc.contributor.departmentINRIA Bordeauxen_US
dc.contributor.departmentGoogle, USAen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.contributor.editorChiappa, Sen_US
dc.contributor.editorCalandra, Ren_US
dc.date.accessioned2020-11-06T11:40:13Z
dc.date.available2020-11-06T11:40:13Z
dc.date.issued2020en_US
dc.description.abstractIn this paper, we study the problem of computing U-statistics of degree 2, i.e., quantities that come in the form of averages over pairs of data points, in the local model of differential privacy (LDP). The class of U-statistics covers many statistical estimates of interest, including Gini mean difference, Kendall's tau coefficient and Area under the ROC Curve (AUC), as well as empirical risk measures for machine learning problems such as ranking, clustering and metric learning. We first introduce an LDP protocol based on quantizing the data into bins and applying randomized response, which guarantees an epsilon-LDP estimate with a Mean Squared Error (MSE) of O(1/root n epsilon) under regularity assumptions on the U-statistic or the data distribution. We then propose a specialized protocol for AUC based on a novel use of hierarchical histograms that achieves MSE of O (alpha(3)/n epsilon(2)) for arbitrary data distribution. We also show that 2-party secure computation allows to design a protocol with MSE of O(1/n epsilon(2)), without any assumption on the kernel function or data distribution and with total communication linear in the number of users n. Finally, we evaluate the performance of our protocols through experiments on synthetic and real datasets.en
dc.description.versionPeer revieweden
dc.format.extent10
dc.format.extent1573-1582
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationBell , J , Bellet , A , Gascon , A & Kulkarni , T 2020 , Private Protocols for U-Statistics in the Local Model and Beyond . in S Chiappa & R Calandra (eds) , INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 108 . Proceedings of Machine Learning Research , vol. 108 , Addison-Wesley , pp. 1573-1582 , International Conference on Artificial Intelligence and Statistics , Palermo , Italy , 03/06/2020 . < http://proceedings.mlr.press/v108/bell20a.html >en
dc.identifier.issn2640-3498
dc.identifier.otherPURE UUID: c2ad5836-8331-4227-af2c-a38b14c1356den_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/c2ad5836-8331-4227-af2c-a38b14c1356den_US
dc.identifier.otherPURE LINK: http://proceedings.mlr.press/v108/bell20a.htmlen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/52650334/Bell_Private.20a.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/47479
dc.identifier.urnURN:NBN:fi:aalto-202011066371
dc.language.isoenen
dc.publisherADDISON-WESLEY PUBL CO
dc.relation.ispartofInternational Conference on Artificial Intelligence and Statisticsen
dc.relation.ispartofseriesINTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 108en
dc.relation.ispartofseriesProceedings of Machine Learning Researchen
dc.relation.ispartofseriesVolume 108en
dc.rightsopenAccessen
dc.titlePrivate Protocols for U-Statistics in the Local Model and Beyonden
dc.typeConference article in proceedingsfi
dc.type.versionpublishedVersion
Files