{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T19:40:13Z","timestamp":1725738013865},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642391392"},{"type":"electronic","value":"9783642391408"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39140-8_3","type":"book-chapter","created":{"date-parts":[[2013,6,28]],"date-time":"2013-06-28T00:50:23Z","timestamp":1372380623000},"page":"43-58","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Regression in Metric Spaces via Approximate Lipschitz Extension"],"prefix":"10.1007","author":[{"given":"Lee-Ad","family":"Gottlieb","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":"297","reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/263867.263927","volume":"44","author":"N. Alon","year":"1997","unstructured":"Alon, N., Ben-David, S., Cesa-Bianchi, N., Haussler, D.: Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM\u00a044(4), 615\u2013631 (1997)","journal-title":"Journal of the ACM"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1051\/ps:2005018","volume":"9","author":"S. Boucheron","year":"2005","unstructured":"Boucheron, S., Bousquet, O., Lugosi, G.: Theory of classification: A survey of recent advances. ESAIM Probab. Statist.\u00a09, 323\u2013375 (2005)","journal-title":"ESAIM Probab. Statist."},{"key":"3_CR3","series-title":"Wadsworth Statistics\/Probability Series","volume-title":"Classification and regression trees","author":"L. Breiman","year":"1984","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and regression trees. Wadsworth Statistics\/Probability Series. Wadsworth Advanced Books and Software, Belmont (1984)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: 23rd International Conference on Machine Learning, pp. 97\u2013104. ACM (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: 38th Annual ACM Symposium on Theory of Computing, pp. 574\u2013583 (2006)","DOI":"10.1145\/1132516.1132599"},{"issue":"1","key":"3_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"K.L. Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete Comput. Geom.\u00a022(1), 63\u201393 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Clarkson, K.: Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich, G., Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pp. 15\u201359. MIT Press (2006)","DOI":"10.7551\/mitpress\/4908.003.0005"},{"key":"3_CR8","series-title":"Applications of Mathematics (New York)","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0711-5","volume-title":"A probabilistic theory of pattern recognition","author":"L. Devroye","year":"1996","unstructured":"Devroye, L., Gy\u00f6rfi, L., Lugosi, G.: A probabilistic theory of pattern recognition. Applications of Mathematics (New York), vol.\u00a031. Springer, New York (1996)"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-642-15369-3_15","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"L.-A. Gottlieb","year":"2010","unstructured":"Gottlieb, L.-A., Krauthgamer, R.: Proximity algorithms for nearly-doubling spaces. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010. LNCS, vol.\u00a06302, pp. 192\u2013204. Springer, Heidelberg (2010)"},{"key":"3_CR10","unstructured":"Gottlieb, L.-A., Kontorovich, L., Krauthgamer, R.: Efficient classification for metric data. In: COLT, pp. 433\u2013440 (2010)"},{"key":"3_CR11","unstructured":"Gottlieb, L.-A., Kontorovich, A., Krauthgamer, R.: Efficient regression in metric spaces via approximate Lipschitz extension (2011), http:\/\/arxiv.org\/abs\/1111.4470"},{"key":"3_CR12","unstructured":"Gottlieb, L.-A., Kontorovich, A., Krauthgamer, R.: Adaptive metric dimensionality reduction (2013), http:\/\/arxiv.org\/abs\/1302.2752"},{"key":"3_CR13","series-title":"Springer Series in Statistics","doi-asserted-by":"publisher","DOI":"10.1007\/b97848","volume-title":"A distribution-free theory of nonparametric regression","author":"L. Gy\u00f6rfi","year":"2002","unstructured":"Gy\u00f6rfi, L., Kohler, M., Krzy\u017cak, A., Walk, H.: A distribution-free theory of nonparametric regression. Springer Series in Statistics. Springer, New York (2002)"},{"key":"3_CR14","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS, pp. 534\u2013543 (2003)"},{"issue":"5","key":"3_CR15","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing\u00a035(5), 1148\u20131184 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Kpotufe, S., Dasgupta, S.: A tree-based regressor that adapts to intrinsic dimension. Journal of Computer and System Sciences (2011) (to appear)","DOI":"10.1016\/j.jcss.2012.01.002"},{"key":"3_CR17","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: Simple algorithms for proximity search. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 791\u2013801 (January 2004), http:\/\/dl.acm.org\/citation.cfm?id=982792.982913"},{"key":"3_CR18","unstructured":"Kpotufe, S.: Fast, smooth and adaptive regression in metric spaces. In: Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C.K.I., Culotta, A. (eds.) Advances in Neural Information Processing Systems 22, pp. 1024\u20131032 (2009)"},{"key":"3_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1568318.1568322","volume":"56","author":"J. Kleinberg","year":"2009","unstructured":"Kleinberg, J., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. J. ACM\u00a056, 32:1\u201332:37 (2009)","journal-title":"J. ACM"},{"issue":"1","key":"3_CR20","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1214\/009053607000000811","volume":"36","author":"J. Lafferty","year":"2008","unstructured":"Lafferty, J., Wasserman, L.: Rodeo: Sparse, greedy nonparametric regression. Ann. Stat.\u00a036(1), 28\u201363 (2008)","journal-title":"Ann. Stat."},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/18.382014","volume":"41","author":"G. Lugosi","year":"1995","unstructured":"Lugosi, G., Zeger, K.: Nonparametric estimation via empirical risk minimization. IEEE Transactions on Information Theory\u00a041(3), 677\u2013687 (1995)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"12","key":"3_CR22","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1090\/S0002-9904-1934-05978-0","volume":"40","author":"E.J. McShane","year":"1934","unstructured":"McShane, E.J.: Extension of range of functions. Bull. Amer. Math. Soc.\u00a040(12), 837\u2013842 (1934)","journal-title":"Bull. Amer. Math. Soc."},{"key":"3_CR23","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-540-27819-1_17","volume-title":"Learning Theory","author":"H.Q. Minh","year":"2004","unstructured":"Minh, H.Q., Hofmann, T.: Learning over compact metric spaces. In: Shawe-Taylor, J., Singer, Y. (eds.) COLT 2004. LNCS (LNAI), vol.\u00a03120, pp. 239\u2013254. Springer, Heidelberg (2004)"},{"key":"3_CR24","series-title":"Mathematics and its Applications (Soviet Series)","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-2583-0","volume-title":"Nonparametric estimation of probability densities and regression curves","author":"\u00c8.A.. Nadaraya","year":"1989","unstructured":"Nadaraya, \u00c8.A.: Nonparametric estimation of probability densities and regression curves. Mathematics and its Applications (Soviet Series), vol.\u00a020. Kluwer Academic Publishers Group, Dordrecht (1989); Translated from the Russian by Samuel Kotz"},{"key":"3_CR25","unstructured":"Neylon, T.: Sparse solutions for linear prediction problems. PhD thesis, New York University (2006)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Pollard, D.: Convergence of Stochastic Processes. Springer (1984)","DOI":"10.1007\/978-1-4612-5254-2"},{"issue":"5","key":"3_CR27","doi-asserted-by":"publisher","first-page":"1926","DOI":"10.1109\/18.705570","volume":"44","author":"J. Shawe-Taylor","year":"1998","unstructured":"Shawe-Taylor, J., Bartlett, P.L., Williamson, R.C., Anthony, M.: Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory\u00a044(5), 1926\u20131940 (1998)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR28","series-title":"Math\u00e9matiques & Applications (Berlin)","volume-title":"Introduction \u00e0 l\u2019estimation non-param\u00e9trique","author":"A.B. Tsybakov","year":"2004","unstructured":"Tsybakov, A.B.: Introduction \u00e0 l\u2019estimation non-param\u00e9trique. Math\u00e9matiques & Applications (Berlin), vol.\u00a041. Springer, Berlin (2004)"},{"key":"3_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2440-0","volume-title":"The nature of statistical learning theory","author":"V.N. Vapnik","year":"1995","unstructured":"Vapnik, V.N.: The nature of statistical learning theory. Springer, New York (1995)"},{"key":"3_CR30","first-page":"669","volume":"5","author":"U. Luxburg von","year":"2004","unstructured":"von Luxburg, U., Bousquet, O.: Distance-based classification with Lipschitz functions. Journal of Machine Learning Research\u00a05, 669\u2013695 (2004)","journal-title":"Journal of Machine Learning Research"},{"key":"3_CR31","series-title":"Springer Texts in Statistics","volume-title":"All of nonparametric statistics","author":"L. Wasserman","year":"2006","unstructured":"Wasserman, L.: All of nonparametric statistics. Springer Texts in Statistics. Springer, New York (2006)"},{"issue":"1","key":"3_CR32","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1090\/S0002-9947-1934-1501735-3","volume":"36","author":"H. Whitney","year":"1934","unstructured":"Whitney, H.: Analytic extensions of differentiable functions defined in closed sets. Transactions of the American Mathematical Society\u00a036(1), 63\u201389 (1934)","journal-title":"Transactions of the American Mathematical Society"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 538\u2013546 (2001)","DOI":"10.1109\/SFCS.2001.959930"}],"container-title":["Lecture Notes in Computer Science","Similarity-Based Pattern Recognition"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39140-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T05:25:18Z","timestamp":1715577918000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39140-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642391392","9783642391408"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39140-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}