{"data":{"id":"10.48550/arxiv.2102.03013","type":"dois","attributes":{"doi":"10.48550/arxiv.2102.03013","prefix":"10.48550","suffix":"arxiv.2102.03013","identifiers":[{"identifier":"2102.03013","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2102.03013"}],"creators":[{"name":"Bu, Zhiqi","nameType":"Personal","givenName":"Zhiqi","familyName":"Bu","affiliation":[],"nameIdentifiers":[]},{"name":"Gopi, Sivakanth","nameType":"Personal","givenName":"Sivakanth","familyName":"Gopi","affiliation":[],"nameIdentifiers":[]},{"name":"Kulkarni, Janardhan","nameType":"Personal","givenName":"Janardhan","familyName":"Kulkarni","affiliation":[],"nameIdentifiers":[]},{"name":"Lee, Yin Tat","nameType":"Personal","givenName":"Yin Tat","familyName":"Lee","affiliation":[],"nameIdentifiers":[]},{"name":"Shen, Judy Hanwen","nameType":"Personal","givenName":"Judy Hanwen","familyName":"Shen","affiliation":[],"nameIdentifiers":[]},{"name":"Tantipongpipat, Uthaipon","nameType":"Personal","givenName":"Uthaipon","familyName":"Tantipongpipat","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Fast and Memory Efficient Differentially Private-SGD via JL Projections"}],"publisher":"arXiv","container":{},"publicationYear":2021,"subjects":[{"lang":"en","subject":"Machine Learning (cs.LG)","subjectScheme":"arXiv"},{"lang":"en","subject":"Cryptography and Security (cs.CR)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2021-02-05T06:02:10Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2021-02-08T01:09:03Z","dateType":"Updated","dateInformation":"v1"},{"date":"2021-02","dateType":"Available","dateInformation":"v1"},{"date":"2021","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"Creative Commons Attribution Non Commercial Share Alike 4.0 International","rightsUri":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-nc-sa-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"Differentially Private-SGD (DP-SGD) of Abadi et al. (2016) and its variations are the only known algorithms for private training of large scale neural networks. This algorithm requires computation of per-sample gradients norms which is extremely slow and memory intensive in practice. In this paper, we present a new framework to design differentially private optimizers called DP-SGD-JL and DP-Adam-JL. Our approach uses Johnson-Lindenstrauss (JL) projections to quickly approximate the per-sample gradient norms without exactly computing them, thus making the training time and memory requirements of our optimizers closer to that of their non-DP versions. Unlike previous attempts to make DP-SGD faster which work only on a subset of network architectures or use compiler techniques, we propose an algorithmic solution which works for any network in a black-box manner which is the main contribution of this paper. To illustrate this, on IMDb dataset, we train a Recurrent Neural Network (RNN) to achieve good privacy-vs-accuracy tradeoff, while being significantly faster than DP-SGD and with a similar memory footprint as non-private SGD. The privacy analysis of our algorithms is more involved than DP-SGD, we use the recently proposed f-DP framework of Dong et al. (2019) to prove privacy.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMTAyLjAzMDEzPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjEwMi4wMzAxMzwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5CdSwgWmhpcWk8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlpoaXFpPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkJ1PC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkdvcGksIFNpdmFrYW50aDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+U2l2YWthbnRoPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkdvcGk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+S3Vsa2FybmksIEphbmFyZGhhbjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+SmFuYXJkaGFuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkt1bGthcm5pPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkxlZSwgWWluIFRhdDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+WWluIFRhdDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5MZWU8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+U2hlbiwgSnVkeSBIYW53ZW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkp1ZHkgSGFud2VuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlNoZW48L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+VGFudGlwb25ncGlwYXQsIFV0aGFpcG9uPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5VdGhhaXBvbjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5UYW50aXBvbmdwaXBhdDwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+RmFzdCBhbmQgTWVtb3J5IEVmZmljaWVudCBEaWZmZXJlbnRpYWxseSBQcml2YXRlLVNHRCB2aWEgSkwgUHJvamVjdGlvbnM8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMjE8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5NYWNoaW5lIExlYXJuaW5nIChjcy5MRyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5DcnlwdG9ncmFwaHkgYW5kIFNlY3VyaXR5IChjcy5DUik8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBDb21wdXRlciBhbmQgaW5mb3JtYXRpb24gc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIxLTAyLTA1VDA2OjAyOjEwWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDIxLTAyLTA4VDAxOjA5OjAzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMjEtMDI8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vY3JlYXRpdmVjb21tb25zLm9yZy9saWNlbnNlcy9ieS1uYy1zYS80LjAvIiByaWdodHNJZGVudGlmaWVyU2NoZW1lPSJTUERYIiByaWdodHNJZGVudGlmaWVyPSJDQy1CWS1OQy1TQS00LjAiPkNyZWF0aXZlIENvbW1vbnMgQXR0cmlidXRpb24gTm9uIENvbW1lcmNpYWwgU2hhcmUgQWxpa2UgNC4wIEludGVybmF0aW9uYWw8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5EaWZmZXJlbnRpYWxseSBQcml2YXRlLVNHRCAoRFAtU0dEKSBvZiBBYmFkaSBldCBhbC4gKDIwMTYpIGFuZCBpdHMgdmFyaWF0aW9ucyBhcmUgdGhlIG9ubHkga25vd24gYWxnb3JpdGhtcyBmb3IgcHJpdmF0ZSB0cmFpbmluZyBvZiBsYXJnZSBzY2FsZSBuZXVyYWwgbmV0d29ya3MuIFRoaXMgYWxnb3JpdGhtIHJlcXVpcmVzIGNvbXB1dGF0aW9uIG9mIHBlci1zYW1wbGUgZ3JhZGllbnRzIG5vcm1zIHdoaWNoIGlzIGV4dHJlbWVseSBzbG93IGFuZCBtZW1vcnkgaW50ZW5zaXZlIGluIHByYWN0aWNlLiBJbiB0aGlzIHBhcGVyLCB3ZSBwcmVzZW50IGEgbmV3IGZyYW1ld29yayB0byBkZXNpZ24gZGlmZmVyZW50aWFsbHkgcHJpdmF0ZSBvcHRpbWl6ZXJzIGNhbGxlZCBEUC1TR0QtSkwgYW5kIERQLUFkYW0tSkwuIE91ciBhcHByb2FjaCB1c2VzIEpvaG5zb24tTGluZGVuc3RyYXVzcyAoSkwpIHByb2plY3Rpb25zIHRvIHF1aWNrbHkgYXBwcm94aW1hdGUgdGhlIHBlci1zYW1wbGUgZ3JhZGllbnQgbm9ybXMgd2l0aG91dCBleGFjdGx5IGNvbXB1dGluZyB0aGVtLCB0aHVzIG1ha2luZyB0aGUgdHJhaW5pbmcgdGltZSBhbmQgbWVtb3J5IHJlcXVpcmVtZW50cyBvZiBvdXIgb3B0aW1pemVycyBjbG9zZXIgdG8gdGhhdCBvZiB0aGVpciBub24tRFAgdmVyc2lvbnMuCiAgVW5saWtlIHByZXZpb3VzIGF0dGVtcHRzIHRvIG1ha2UgRFAtU0dEIGZhc3RlciB3aGljaCB3b3JrIG9ubHkgb24gYSBzdWJzZXQgb2YgbmV0d29yayBhcmNoaXRlY3R1cmVzIG9yIHVzZSBjb21waWxlciB0ZWNobmlxdWVzLCB3ZSBwcm9wb3NlIGFuIGFsZ29yaXRobWljIHNvbHV0aW9uIHdoaWNoIHdvcmtzIGZvciBhbnkgbmV0d29yayBpbiBhIGJsYWNrLWJveCBtYW5uZXIgd2hpY2ggaXMgdGhlIG1haW4gY29udHJpYnV0aW9uIG9mIHRoaXMgcGFwZXIuIFRvIGlsbHVzdHJhdGUgdGhpcywgb24gSU1EYiBkYXRhc2V0LCB3ZSB0cmFpbiBhIFJlY3VycmVudCBOZXVyYWwgTmV0d29yayAoUk5OKSB0byBhY2hpZXZlIGdvb2QgcHJpdmFjeS12cy1hY2N1cmFjeSB0cmFkZW9mZiwgd2hpbGUgYmVpbmcgc2lnbmlmaWNhbnRseSBmYXN0ZXIgdGhhbiBEUC1TR0QgYW5kIHdpdGggYSBzaW1pbGFyIG1lbW9yeSBmb290cHJpbnQgYXMgbm9uLXByaXZhdGUgU0dELiBUaGUgcHJpdmFjeSBhbmFseXNpcyBvZiBvdXIgYWxnb3JpdGhtcyBpcyBtb3JlIGludm9sdmVkIHRoYW4gRFAtU0dELCB3ZSB1c2UgdGhlIHJlY2VudGx5IHByb3Bvc2VkIGYtRFAgZnJhbWV3b3JrIG9mIERvbmcgZXQgYWwuICgyMDE5KSB0byBwcm92ZSBwcml2YWN5LjwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/2102.03013","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-02-23T04:18:51.000Z","registered":"2022-02-23T04:18:52.000Z","published":"2021","updated":"2022-02-23T04:18:52.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2102.03013","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}