{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:55:19Z","timestamp":1770753319359,"version":"3.50.0"},"reference-count":54,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"8","license":[{"start":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T00:00:00Z","timestamp":1501545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1141\/12"],"award-info":[{"award-number":["1141\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Yahoo Faculty Award"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["452\/08"],"award-info":[{"award-number":["452\/08"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["897\/13"],"award-info":[{"award-number":["897\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Inerva Grant"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1109\/tit.2017.2713820","type":"journal-article","created":{"date-parts":[[2017,6,8]],"date-time":"2017-06-08T18:30:06Z","timestamp":1496946606000},"page":"4838-4849","source":"Crossref","is-referenced-by-count":17,"title":["Efficient Regression in Metric Spaces via Approximate Lipschitz Extension"],"prefix":"10.1109","volume":"63","author":[{"given":"Lee-Ad","family":"Gottlieb","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8038-8671","authenticated-orcid":false,"given":"Aryeh","family":"Kontorovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","article-title":"Sparse solutions for linear prediction problems","author":"neylon","year":"2006"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-2583-0"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1214\/009053607000000811"},{"key":"ref32","first-page":"1190","article-title":"Algorithms for Lipschitz learning on graphs","author":"kyng","year":"2015","journal-title":"Proc Conf Learning Theory (COLT)"},{"key":"ref31","first-page":"798","article-title":"Navigating nets: Simple algorithms for proximity search","author":"krauthgamer","year":"2004","journal-title":"Proc 15th Annu ACM-SIAM Symp Discrete Algorithms"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.01.002"},{"key":"ref37","author":"mohri","year":"2012","journal-title":"Foundations of Machine Learning"},{"key":"ref36","first-page":"839","article-title":"Generalization error bounds for Bayesian mixture algorithms","volume":"4","author":"meir","year":"2003","journal-title":"J Mach Learn Res"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1934-05978-0"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1109\/18.382014"},{"key":"ref28","first-page":"480","article-title":"A Bayes consistent 1-NN classifier","author":"kontorovich","year":"2015","journal-title":"Proc 14th Int Conf Artif Intell Statist (AISTATS)"},{"key":"ref27","first-page":"892","article-title":"Maximum margin multiclass nearest neighbors","author":"kontorovich","year":"2014","journal-title":"Proc ICML"},{"key":"ref29","first-page":"1024","article-title":"Fast, smooth and adaptive regression in metric spaces","volume":"22","author":"kpotufe","year":"2009","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1138-6"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"ref20","doi-asserted-by":"crossref","DOI":"10.1007\/b97848","author":"gy\u00f6rfi","year":"2002","journal-title":"A Distribution-Free Theory of Nonparametric Regression"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL0521382483"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"ref24","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1090\/trans2\/017\/10","article-title":"$\\epsilon $ -entropy and $\\epsilon $ -capacity of sets in functional space","volume":"17","author":"kolmogorov","year":"1961","journal-title":"Amer Math Soc Transl"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"ref26","first-page":"28","article-title":"Concentration in unbounded metric spaces and algorithmic stability","volume":"2","author":"kontorovich","year":"2014","journal-title":"Proc ICML"},{"key":"ref25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aos\/1015362182","article-title":"Empirical margin distributions and bounding the generalization error of combined classifiers","volume":"30","author":"koltchinskii","year":"2002","journal-title":"Ann Statist"},{"key":"ref50","first-page":"669","article-title":"Distance-based classification with Lipschitz functions","volume":"5","author":"von luxburg","year":"2004","journal-title":"J Mach Learn Res"},{"key":"ref51","author":"wasserman","year":"2006","journal-title":"All of Nonparametric Statistics"},{"key":"ref54","first-page":"912","article-title":"Semi-supervised learning using Gaussian fields and harmonic functions","author":"zhu","year":"2003","journal-title":"Proc 20th Int Conf Mach Learn (ICML)"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959930"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.2307\/1989708"},{"key":"ref10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.7551\/mitpress\/4908.003.0005","article-title":"Nearest-neighbor searching and metric space dimensions","author":"clarkson","year":"2006","journal-title":"Nearest-Neighbor Methods for Learning and Vision Theory and Practice"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132599"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"ref12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0711-5","volume":"31","author":"devroye","year":"1996","journal-title":"A Probabilistic Theory of Pattern Recognition"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488691"},{"key":"ref14","first-page":"469","article-title":"Automata, languages, and programming","author":"feldmann","year":"2015","journal-title":"Proc 42nd Int Colloq (ICALP)"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39140-8_3"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2339840"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.040"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_40"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"ref4","first-page":"463","article-title":"Rademacher and Gaussian complexities: Risk bounds and structural results","volume":"3","author":"bartlett","year":"2003","journal-title":"J Mach Learn Res"},{"key":"ref3","author":"bartlett","year":"2006","journal-title":"Covering Numbers Chaining & Dudley’s Entropy Integral (Lecture 24) Class Notes on Statistical Learning Theory"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1051\/ps:2005018"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"ref8","first-page":"762","article-title":"On hierarchical routing in doubling metrics","author":"chan","year":"2005","journal-title":"Proc 16th Annu ACM-SIAM Symp Discrete Algorithms"},{"key":"ref7","author":"breiman","year":"1984","journal-title":"Classification and Regression Trees"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1561\/0400000054"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591864"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2440-0"},{"key":"ref47","volume":"41","author":"tsybakov","year":"2004","journal-title":"Introduction à L’estimation Non-Paramétrique"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.3150\/14-BEJ679"},{"key":"ref41","author":"rao","year":"1983","journal-title":"Nonparametric Functional Estimation"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1109\/18.705570"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/7976396\/07944658.pdf?arnumber=7944658","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T23:41:37Z","timestamp":1692834097000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/7944658\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":54,"journal-issue":{"issue":"8"},"URL":"https:\/\/doi.org\/10.1109\/tit.2017.2713820","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}