{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T05:30:57Z","timestamp":1744349457913,"version":"3.37.3"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T00:00:00Z","timestamp":1725148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T00:00:00Z","timestamp":1725148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P004245\/1"],"award-info":[{"award-number":["EP\/P004245\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>High dimensional learning is a perennial problem due to challenges posed by the \u201ccurse of dimensionality\u201d; learning typically demands more computing resources as well as more training data. In differentially private (DP) settings, this is further exacerbated by noise that needs adding to each dimension to achieve the required privacy. In this paper, we present a surprisingly simple approach to address all of these concerns at once, based on histograms constructed on a low-dimensional random projection (RP) of the data. Our approach exploits RP to take advantage of hidden low-dimensional structures in the data, yielding both computational efficiency, and improved error convergence with respect to the sample size\u2014whereby less training data suffice for learning. We also propose a variant for efficient differentially private (DP) classification that further exploits the data-oblivious nature of both the histogram construction and the RP based dimensionality reduction, resulting in an efficient management of the privacy budget. We present a detailed and rigorous theoretical analysis of generalisation of our algorithms in several settings, showing that our approach is able to exploit low-dimensional structure of the data, ameliorates the ill-effects of noise required for privacy, and has good generalisation under minimal conditions. We also corroborate our findings experimentally, and demonstrate that our algorithms achieve competitive classification accuracy in both non-private and private settings.<\/jats:p>","DOI":"10.1007\/s10618-024-01063-6","type":"journal-article","created":{"date-parts":[[2024,9,1]],"date-time":"2024-09-01T07:01:51Z","timestamp":1725174111000},"page":"3948-4000","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient learning with projected histograms"],"prefix":"10.1007","volume":"38","author":[{"given":"Zhanliang","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3733-7064","authenticated-orcid":false,"given":"Ata","family":"Kab\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"Reeve","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,1]]},"reference":[{"key":"1063_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding machine learning: from theory to algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz S, Ben-David S (2014) Understanding machine learning: from theory to algorithms. Cambridge University Press, Cambridge"},{"key":"1063_CR2","unstructured":"Mahoney M (2009) The Johnson-Lindenstrauss lemma. Lecture notes on Alg orithms for Modern Massive Data Set Analysis"},{"key":"1063_CR3","doi-asserted-by":"crossref","unstructured":"Blocki J, Blum A, Datta A, Sheffet O (2012) The johnson-lindenstrauss transform itself preserves differential privacy. In: 2012 IEEE 53rd annual symposium on foundations of computer science, 410\u2013419. IEEE","DOI":"10.1109\/FOCS.2012.67"},{"key":"1063_CR4","doi-asserted-by":"crossref","unstructured":"Liaw C, Mehrabian A, Plan Y, Vershynin R (2017) A simple tool for bounding the deviation of random matrices on geometric sets, 277\u2013299","DOI":"10.1007\/978-3-319-45282-1_18"},{"key":"1063_CR5","unstructured":"Papadimitriou CH, Vempala SS (2019) Random projection in the brain and computation with assemblies of neurons. In: information technology convergence and services"},{"key":"1063_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-024-06531-0","author":"A Kab\u00e1n","year":"2024","unstructured":"Kab\u00e1n A, Reeve HWJ (2024) Structure discovery in PAC-learning by random projections. Mach Learn. https:\/\/doi.org\/10.1007\/s10994-024-06531-0","journal-title":"Mach Learn"},{"key":"1063_CR7","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1098\/rsta.1895.0010","volume":"186","author":"K Pearson","year":"1895","unstructured":"Pearson K (1895) Contributions to the mathematical theory of evolution. ii. skew variation in homogeneous material. Philos Trans Royal Soc London A 186:343\u2013414","journal-title":"Philos Trans Royal Soc London A"},{"issue":"4","key":"1063_CR8","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01025868","volume":"57","author":"D Freedman","year":"1981","unstructured":"Freedman D, Diaconis P (1981) On the histogram as a density estimator: L2 theory. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Geb 57(4):453\u2013476","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Geb"},{"issue":"6","key":"1063_CR9","first-page":"493","volume":"2","author":"J Van Ryzin","year":"1973","unstructured":"Van Ryzin J (1973) A histogram method of density estimation. Commun Stat Theory Methods 2(6):493\u2013506","journal-title":"Commun Stat Theory Methods"},{"key":"1063_CR10","unstructured":"Kontkanen, P., Myllym\u00e4ki, P (2007) MDL histogram density estimation. In: Artificial Intelligence and Statistics, 219\u2013226. PMLR"},{"key":"1063_CR11","first-page":"95","volume":"22","author":"H Hang","year":"2021","unstructured":"Hang H, Lin Z, Liu X, Wen H (2021) Histogram transform ensembles for large-scale regression. J Mach Learn Res 22:95\u20131","journal-title":"J Mach Learn Res"},{"issue":"3","key":"1063_CR12","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1214\/aos\/1032526958","volume":"24","author":"A Nobel","year":"1996","unstructured":"Nobel A (1996) Histogram regression estimation using data-dependent partitions. Ann Stat 24(3):1084\u20131105","journal-title":"Ann Stat"},{"key":"1063_CR13","first-page":"2935","volume":"11","author":"F Chang","year":"2010","unstructured":"Chang F, Guo C-Y, Lin X-R, Lu C-J (2010) Tree decomposition for large-scale svm problems. J Mach Learn Res 11:2935\u20132972","journal-title":"J Mach Learn Res"},{"key":"1063_CR14","unstructured":"Wu D, Bennett KP, Cristianini N, Shawe-Taylor J (1999) Large margin trees for induction and transduction. In: ICML, 474\u2013483"},{"key":"1063_CR15","doi-asserted-by":"crossref","unstructured":"Devroye L, Gy\u00f6rfi L, Lugosi G (1996) A probabilistic theory of pattern recognition. In: Stochastic Modelling and Applied Probability","DOI":"10.1007\/978-1-4612-0711-5"},{"issue":"24","key":"1063_CR16","first-page":"665","volume":"7","author":"CD Scott","year":"2006","unstructured":"Scott CD, Nowak RD (2006) Learning minimum volume sets. J Mach Learn Res 7(24):665\u2013704","journal-title":"J Mach Learn Res"},{"issue":"5","key":"1063_CR17","doi-asserted-by":"publisher","first-page":"1544","DOI":"10.1007\/s10618-017-0532-z","volume":"31","author":"ME Gursoy","year":"2017","unstructured":"Gursoy ME, Inan A, Nergiz ME, Saygin Y (2017) Differentially private nearest neighbor classification. Data Min Knowl Disc 31(5):1544\u20131575","journal-title":"Data Min Knowl Disc"},{"key":"1063_CR18","unstructured":"Bhatia N, et al (2010) Survey of nearest neighbor techniques. arXiv preprint arXiv:1007.0085"},{"issue":"4","key":"1063_CR19","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.21275\/v5i4.NOV162954","volume":"5","author":"H Sharma","year":"2016","unstructured":"Sharma H, Kumar S (2016) A survey on decision tree algorithms of classification in data mining. Int J Sci Res (IJSR) 5(4):2094\u20132097","journal-title":"Int J Sci Res (IJSR)"},{"key":"1063_CR20","doi-asserted-by":"crossref","unstructured":"Chatel S, Pyrgelis A, Troncoso-Pastoriza JR, Hubaux J-P (2021) Sok: Privacy-preserving collaborative tree-based model learning. In: proceedings on privacy enhancing technologies","DOI":"10.2478\/popets-2021-0043"},{"issue":"1","key":"1063_CR21","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta S, Gupta A (2003) An elementary proof of a theorem of johnson and lindenstrauss. Random Struct Algorithms 22(1):60\u201365","journal-title":"Random Struct Algorithms"},{"issue":"1","key":"1063_CR22","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.jfa.2004.10.009","volume":"225","author":"B Klartag","year":"2005","unstructured":"Klartag B, Mendelson S (2005) Empirical processes and random projections. J Funct Anal 225(1):229\u2013245","journal-title":"J Funct Anal"},{"issue":"2","key":"1063_CR23","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1002\/rsa.20218","volume":"33","author":"J Matou\u0161ek","year":"2008","unstructured":"Matou\u0161ek J (2008) On variants of the johnson-lindenstrauss lemma. Random Struct Algorithms 33(2):142\u2013156","journal-title":"Random Struct Algorithms"},{"key":"1063_CR24","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Nelson, J (2017) Optimality of the Johnson-Lindenstrauss lemma. In: 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), 633\u2013638. IEEE","DOI":"10.1109\/FOCS.2017.64"},{"issue":"5","key":"1063_CR25","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1007\/s10208-015-9280-x","volume":"16","author":"S Dirksen","year":"2016","unstructured":"Dirksen S (2016) Dimensionality reduction with subgaussian matrices: a unified theory. Found Comput Math 16(5):1367\u20131396","journal-title":"Found Comput Math"},{"issue":"3","key":"1063_CR26","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1273340.1273347","volume":"3","author":"P Indyk","year":"2007","unstructured":"Indyk P, Naor A (2007) Nearest-neighbor-preserving embeddings. ACM Trans Algorithms 3(3):31","journal-title":"ACM Trans Algorithms"},{"key":"1063_CR27","unstructured":"Kab\u00e1n A (2016) A new look at nearest neighbours: Identifying benign input geometries via random projections. In: Asian conference on machine learning, 65\u201380. PMLR"},{"key":"1063_CR28","doi-asserted-by":"crossref","unstructured":"Clarkson KL (2008) Tighter bounds for random projections of manifolds. In: proceedings of the twenty-fourth annual symposium on computational geometry, 39\u201348","DOI":"10.1145\/1377676.1377685"},{"issue":"1","key":"1063_CR29","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10208-007-9011-z","volume":"9","author":"RG Baraniuk","year":"2009","unstructured":"Baraniuk RG, Wakin MB (2009) Random projections of smooth manifolds. Found Comput Math 9(1):51\u201377","journal-title":"Found Comput Math"},{"issue":"489","key":"1063_CR30","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1198\/jasa.2009.tm08651","volume":"105","author":"L Wasserman","year":"2010","unstructured":"Wasserman L, Zhou S (2010) A statistical framework for differential privacy. J Am Stat Assoc 105(489):375\u2013389","journal-title":"J Am Stat Assoc"},{"key":"1063_CR31","unstructured":"Hay, M., Rastogi, V., Miklau, G., Suciu, D (2009) Boosting the accuracy of differentially-private histograms through consistency. arXiv preprint arXiv:0904.0942"},{"key":"1063_CR32","unstructured":"Berrett T, Butucea C (2019) Classification under local differential privacy. arXiv preprint arXiv:1912.04629"},{"key":"1063_CR33","unstructured":"Rauch J, Olatunji IE, Khosla M (2021) Achieving differential privacy for $$k$$-nearest neighbors based outlier detection by data partitioning. arXiv preprint arXiv:2104.07938"},{"key":"1063_CR34","doi-asserted-by":"crossref","unstructured":"Zhu Y, Yu X, Chandraker M, Wang Y-X (2020) Private-knn: Practical differential privacy for computer vision. In: proceedings of the IEEE\/CVF conference on computer vision and pattern recognition, 11854\u201311862","DOI":"10.1109\/CVPR42600.2020.01187"},{"key":"1063_CR35","doi-asserted-by":"crossref","unstructured":"Jagannathan G, Pillaipakkamnatt K, Wright RN (2009) A practical differentially private random decision tree classifier. In: 2009 IEEE international conference on data mining workshops, 114\u2013121. IEEE","DOI":"10.1109\/ICDMW.2009.93"},{"key":"1063_CR36","unstructured":"Fletcher S, Islam MZ (2015) A differentially private decision forest. In: proceedings of the 13-th Australasian data mining conference, 1:99\u2013108"},{"key":"1063_CR37","doi-asserted-by":"crossref","unstructured":"Kenthapadi K, Korolova A, Mironov I, Mishra N (2012) Privacy via the johnson-lindenstrauss transform. arXiv preprint arXiv:1204.2606","DOI":"10.29012\/jpc.v5i1.625"},{"issue":"2","key":"1063_CR38","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00778-017-0492-3","volume":"27","author":"D Su","year":"2018","unstructured":"Su D, Cao J, Li N, Lyu M (2018) Privpfc: differentially private data publication for classification. VLDB J 27(2):201\u2013223","journal-title":"VLDB J"},{"key":"1063_CR39","unstructured":"Xiao Y, Xiong L, Fan L, Goryczka S (2012) Dpcube: Differentially private histogram release through multidimensional partitioning. arXiv preprint arXiv:1202.5358"},{"key":"1063_CR40","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-319-23633-9_3","volume":"96","author":"H Li","year":"2015","unstructured":"Li H, Xiong L, Jiang X (2015) Differentially private histogram and synthetic data publication. Med Data Priv Handb 96:35\u201358","journal-title":"Med Data Priv Handb"},{"key":"1063_CR41","first-page":"2635","volume":"11","author":"S Shalev-Shwartz","year":"2010","unstructured":"Shalev-Shwartz S, Shamir O, Srebro N, Sridharan K (2010) Learnability, stability and uniform convergence. J Mach Learn Res 11:2635\u20132670","journal-title":"J Mach Learn Res"},{"issue":"2","key":"1063_CR42","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1214\/009053606000001217","volume":"35","author":"J-Y Audibert","year":"2007","unstructured":"Audibert J-Y, Tsybakov AB (2007) Fast learning rates for plug-in classifiers. Ann Stat 35(2):608\u2013633","journal-title":"Ann Stat"},{"key":"1063_CR43","unstructured":"Kasiviswanathan SP (2021) Sgd with low-dimensional gradients with applications to private and distributed learning. In: uncertainty in artificial intelligence, 1905\u20131915. PMLR"},{"key":"1063_CR44","doi-asserted-by":"crossref","unstructured":"Bingham E, Mannila H (2001) Random projection in dimensionality reduction: applications to image and text data. In: proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining, 245\u2013250","DOI":"10.1145\/502512.502546"},{"key":"1063_CR45","first-page":"1","volume":"96","author":"C Dwork","year":"2006","unstructured":"Dwork C (2006) Differential privacy. Autom Lang Program 96:1\u201312","journal-title":"Autom Lang Program"},{"issue":"3\u20134","key":"1063_CR46","first-page":"211","volume":"9","author":"C Dwork","year":"2014","unstructured":"Dwork C, Roth A (2014) The algorithmic foundations of differential privacy. Found Trends Theor Comput Sci 9(3\u20134):211\u2013407","journal-title":"Found Trends Theor Comput Sci"},{"key":"1063_CR47","doi-asserted-by":"crossref","unstructured":"McSherry FD (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, pp. 19\u201330","DOI":"10.1145\/1559845.1559850"},{"issue":"3","key":"1063_CR48","first-page":"96","volume":"12","author":"K Chaudhuri","year":"2011","unstructured":"Chaudhuri K, Monteleoni C, Sarwate AD (2011) Differentially private empirical risk minimization. J Mach Learn Res 12(3):96","journal-title":"J Mach Learn Res"},{"key":"1063_CR49","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P Niyogi","year":"2008","unstructured":"Niyogi P, Smale S, Weinberger S (2008) Finding the homology of submanifolds with high confidence from random samples. Discrete Comput Geom 39:419\u2013441","journal-title":"Discrete Comput Geom"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-024-01063-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-024-01063-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-024-01063-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T09:13:37Z","timestamp":1730106817000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-024-01063-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,1]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1063"],"URL":"https:\/\/doi.org\/10.1007\/s10618-024-01063-6","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"type":"print","value":"1384-5810"},{"type":"electronic","value":"1573-756X"}],"subject":[],"published":{"date-parts":[[2024,9,1]]},"assertion":[{"value":"26 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest or Conflict of interest relating to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}}]}}