{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:16:26Z","timestamp":1767140186233,"version":"build-2238731810"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T00:00:00Z","timestamp":1701907200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T00:00:00Z","timestamp":1701907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"publisher","award":["1602\/19"],"award-info":[{"award-number":["1602\/19"]}],"id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s10107-023-02023-6","type":"journal-article","created":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T14:02:01Z","timestamp":1701957721000},"page":"617-642","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Kirszbraun extension with applications to regression"],"prefix":"10.1007","volume":"207","author":[{"given":"Hananel","family":"Zaichyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"Biess","sequence":"additional","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":"Yury","family":"Makarychev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,7]]},"reference":[{"key":"2023_CR1","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the Symposium on Discrete Algorithms, pp. 522\u2013539. SIAM (2021)","DOI":"10.1137\/1.9781611976465.32"},{"issue":"1","key":"2023_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"2023_CR3","unstructured":"Arya, S., Mount, D.M., Netanyahu, N., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In: Symposium on Discrete Algorithms, pp. 573\u2013582 (1994)"},{"key":"2023_CR4","unstructured":"Ashlagi, Y., Gottlieb, L., Kontorovich, A.: Functions with average smoothness: structure, algorithms, and learning. In: Belkin, M., Kpotufe, S. (eds.) Conference on Learning Theory, COLT 2021, 15\u201319 August 2021, Boulder, Colorado, USA, PMLR, Proceedings of Machine Learning Research, vol. 134, pp. 186\u2013236. http:\/\/proceedings.mlr.press\/v134\/ashlagi21a.html (2021)"},{"issue":"5","key":"2023_CR5","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/widm.1157","volume":"5","author":"H Borchani","year":"2015","unstructured":"Borchani, H., Varando, G., Bielza, C., Larra\u00f1aga, P.: A survey on multi-output regression. Wiley Interdiscip Rev Data Min Knowl Discov 5(5), 216\u2013233 (2015)","journal-title":"Wiley Interdiscip Rev Data Min Knowl Discov"},{"key":"2023_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization. Information Science and Statistics","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Information Science and Statistics. Cambridge University Press, Cambridge (2004)"},{"key":"2023_CR7","volume-title":"Introductory Combinatorics","author":"RA Brualdi","year":"2010","unstructured":"Brualdi, R.A.: Introductory Combinatorics, 5th edn. Pearson Prentice Hall, Upper Saddle River (2010)","edition":"5"},{"key":"2023_CR8","doi-asserted-by":"crossref","unstructured":"Brudnak, M.: Vector-valued support vector regression. In: The 2006 IEEE International Joint Conference on Neural Network Proceedings, pp. 1562\u20131569. IEEE (2006)","DOI":"10.1109\/IJCNN.2006.246619"},{"issue":"125","key":"2023_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"JR Bunch","year":"1974","unstructured":"Bunch, J.R., Hopcroft, J.E.: Triangular factorization and inversion by fast matrix multiplication. Math. Comput. 28(125), 231\u2013236 (1974)","journal-title":"Math. Comput."},{"issue":"1","key":"2023_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1023\/A:1007379606734","volume":"28","author":"R Caruana","year":"1997","unstructured":"Caruana, R.: Multitask learning. Mach. Learn. 28(1), 41\u201375 (1997)","journal-title":"Mach. Learn."},{"key":"2023_CR11","unstructured":"Chen, S., Banerjee, A.: An improved analysis of alternating minimization for structured multi-response regression. In: Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS\u201918, pp. 6617\u20136628. Curran Associates Inc., USA (2018). http:\/\/dl.acm.org\/citation.cfm?id=3327757.3327768"},{"key":"2023_CR12","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of Symposium on Theory of Computing, pp. 273\u2013282 (2011)","DOI":"10.1145\/1993636.1993674"},{"key":"2023_CR13","unstructured":"Cohen, D.T., Kontorovich, A.: Learning with metric losses. In: Loh, P., Raginsky, M. (eds.) Conference on Learning Theory, 2\u20135 July 2022, London, UK, PMLR, Proceedings of Machine Learning Research, vol. 178, pp. 662\u2013700 (2022). https:\/\/proceedings.mlr.press\/v178\/cohen22a.html"},{"key":"2023_CR14","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: Proceedings of the Symposium on Theory of Computing, pp. 574\u2013583 (2006)","DOI":"10.1145\/1132516.1132599"},{"key":"2023_CR15","unstructured":"Davidson, R., MacKinnon, J.G., et\u00a0al.: Estimation and Inference in Econometrics. OUP Catalogue (1993)"},{"key":"2023_CR16","doi-asserted-by":"crossref","unstructured":"Gottlieb, L.A., Kontorovich, A., Krauthgamer, R.: Adaptive metric dimensionality reduction (extended abstract: ALT 2013). Theoretical Computer Science, pp. 105\u2013118 (2016)","DOI":"10.1016\/j.tcs.2015.10.040"},{"issue":"8","key":"2023_CR17","doi-asserted-by":"publisher","first-page":"4838","DOI":"10.1109\/TIT.2017.2713820","volume":"63","author":"LA Gottlieb","year":"2017","unstructured":"Gottlieb, L.A., Kontorovich, A., Krauthgamer, R.: Efficient regression in metric spaces via approximate Lipschitz extension. IEEE Trans. Inf. Theory 63(8), 4838\u20134849 (2017)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2023_CR18","unstructured":"Greene, W.H.: Econometric Analysis. Pearson Education India (2003)"},{"key":"2023_CR19","unstructured":"Greene, W.H.: Econometric Analysis. William H. Greene (2012)"},{"key":"2023_CR20","volume-title":"A Distribution-Free Theory of Nonparametric Regression","author":"L Gy\u00f6rfi","year":"2006","unstructured":"Gy\u00f6rfi, L., Kohler, M., Krzyzak, A., Walk, H.: A Distribution-Free Theory of Nonparametric Regression. Springer, Cham (2006)"},{"key":"2023_CR21","unstructured":"Hanneke, S., Kontorovich, A., Kornowski, G.: Near-optimal learning with average H\u00f6lder smoothness. CoRR arXiv:2302.06005 (2023)"},{"issue":"5","key":"2023_CR22","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 J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"2023_CR23","unstructured":"Jain, P., Tewari, A.: Alternating minimization for regression problems with vector-valued outputs. In: Cortes, C., Lawrence, N.D., Lee, D.D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28, pp. 1126\u20131134. Curran Associates, Inc. (2015). http:\/\/papers.nips.cc\/paper\/5820-alternating-minimization-for-regression-problems-with-vector-valued-outputs.pdf"},{"key":"2023_CR24","unstructured":"Kakade, S., Tewari, A.: Dudley\u2019s theorem, fat shattering dimension, packing numbers. Lecture 15, Toyota Technological Institute at Chicago (2008). http:\/\/ttic.uchicago.edu\/~tewari\/lectures\/lecture15.pdf"},{"issue":"2","key":"2023_CR25","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1214\/aoms\/1177697089","volume":"41","author":"GS Kimeldorf","year":"1970","unstructured":"Kimeldorf, G.S., Wahba, G.: A correspondence between Bayesian estimation on stochastic processes and smoothing by splines. Ann. Math. Stat. 41(2), 495\u2013502 (1970). https:\/\/doi.org\/10.1214\/aoms\/1177697089","journal-title":"Ann. Math. Stat."},{"issue":"1","key":"2023_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.4064\/fm-22-1-77-108","volume":"22","author":"M Kirszbraun","year":"1934","unstructured":"Kirszbraun, M.: \u00dcber die zusammenziehende und Lipschitzsche transformationen. Fundam. Math. 22(1), 77\u2013108 (1934)","journal-title":"Fundam. Math."},{"issue":"10","key":"2023_CR27","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/2347736.2347759","volume":"55","author":"I Koutis","year":"2012","unstructured":"Koutis, I., Miller, G.L., Peng, R.: A fast solver for a class of linear systems. Commun. ACM 55(10), 99\u2013107 (2012)","journal-title":"Commun. ACM"},{"key":"2023_CR28","doi-asserted-by":"crossref","unstructured":"Mahabadi, S., Makarychev, K., Makarychev, Y., Razenshteyn, I.: Nonlinear dimension reduction via outer bi-lipschitz extensions. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1088\u20131101. ACM (2018)","DOI":"10.1145\/3188745.3188828"},{"key":"2023_CR29","doi-asserted-by":"crossref","unstructured":"McShane, E.J.: Extension of range of functions. Bull. Am. Math. Soc. 40(12), 837\u2013842 (1934). https:\/\/projecteuclid.org:443\/euclid.bams\/1183497871","DOI":"10.1090\/S0002-9904-1934-05978-0"},{"key":"2023_CR30","volume-title":"Foundations Of Machine Learning","author":"M Mohri","year":"2012","unstructured":"Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations Of Machine Learning. The MIT Press, Cambridge (2012)"},{"key":"2023_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-2583-0","volume-title":"Nonparametric Estimation of Probability Densities and Regression Curves","author":"EA Nadaraya","year":"1989","unstructured":"Nadaraya, E.A.: Nonparametric Estimation of Probability Densities and Regression Curves. Springer, Cham (1989)"},{"key":"2023_CR32","unstructured":"Naor, A.: Metric embeddings and Lipschitz extensions (2015)"},{"key":"2023_CR33","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-Point Polynomial Algorithms in Convex Programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)"},{"key":"2023_CR34","series-title":"International Series in Pure and Applied Mathematics","volume-title":"Principles of Mathematical Analysis","author":"W Rudin","year":"1976","unstructured":"Rudin, W.: Principles of Mathematical Analysis. International Series in Pure and Applied Mathematics, 3rd edn. McGraw-Hill Book Co., New York (1976)","edition":"3"},{"key":"2023_CR35","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the Symposium on Theory of Computing, vol. 4 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"2023_CR36","doi-asserted-by":"crossref","unstructured":"Whitney, H.: Analytic extensions of differentiable functions defined in closed sets. Trans. Am. Math. Soc. 36(1), 63\u201389 (1934). http:\/\/www.jstor.org\/stable\/1989708","DOI":"10.1090\/S0002-9947-1934-1501735-3"}],"updated-by":[{"DOI":"10.1007\/s10107-024-02056-5","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T00:00:00Z","timestamp":1705708800000}}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02023-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02023-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02023-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T11:09:31Z","timestamp":1723028971000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02023-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,7]]},"references-count":36,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2023"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02023-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,7]]},"assertion":[{"value":"1 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2024","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10107-024-02056-5","URL":"https:\/\/doi.org\/10.1007\/s10107-024-02056-5","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}