{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T15:50:17Z","timestamp":1775663417180,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The design of regression models that are not affected by outliers is an important task which has been subject of numerous papers within the statistics community for the last decades. Prominent examples of robust regression models are least trimmed squares (LTS), where the<jats:italic>k<\/jats:italic>largest squared deviations are ignored, and least trimmed absolute deviations (LTA) which ignores the<jats:italic>k<\/jats:italic>largest absolute deviations. The numerical complexity of both models is driven by the number of binary variables and by the value<jats:italic>k<\/jats:italic>of ignored deviations. We introduce leveraged least trimmed absolute deviations (LLTA) which exploits that LTA is already immune against<jats:italic>y<\/jats:italic>-outliers. Therefore, LLTA has only to be guarded against outlying values in<jats:italic>x<\/jats:italic>, so-called leverage points, which can be computed beforehand, in contrast to<jats:italic>y<\/jats:italic>-outliers. Thus, while the mixed-integer formulations of LTS and LTA have as many binary variables as data points, LLTA only needs one binary variable per leverage point, resulting in a significant reduction of binary variables. Based on 11 data sets from the literature, we demonstrate that (1) LLTA\u2019s prediction quality improves much faster than LTS and as fast as LTA for increasing values of<jats:italic>k<\/jats:italic>and (2) that LLTA solves the benchmark problems about 80 times faster than LTS and about five times faster than LTA, in median.<\/jats:p>","DOI":"10.1007\/s00291-021-00627-y","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T09:20:39Z","timestamp":1618478439000},"page":"809-834","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Leveraged least trimmed absolute deviations"],"prefix":"10.1007","volume":"43","author":[{"given":"Nathan","family":"Sudermann-Merx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8501-2785","authenticated-orcid":false,"given":"Steffen","family":"Rebennack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"627_CR1","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/3-540-44503-X_27","volume-title":"Database theory\u2014ICDT 2001","author":"CC Aggarwal","year":"2001","unstructured":"Aggarwal CC, Hinneburg A, Keim DA (2001) On the surprising behavior of distance metrics in high dimensional space. In: Van den Bussche J, Vianu V (eds) Database theory\u2014ICDT 2001. Springer, Berlin, pp 420\u2013434"},{"issue":"2","key":"627_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1080\/00031305.1991.10475787","volume":"45","author":"GW Bassett Jr","year":"1991","unstructured":"Bassett GW Jr (1991) Equivariant, monotonic, 50% breakdown estimators. Am Stat 45(2):135\u2013137","journal-title":"Am Stat"},{"key":"627_CR3","unstructured":"Bernholt T (2006) Robust estimators are hard to compute. Tech. rep"},{"key":"627_CR4","unstructured":"Bertsimas D, Dunn J (2019) Machine learning under a modern optimization lens. Dynamic Ideas LLC. https:\/\/books.google.de\/books?id=g3ZWygEACAAJ"},{"key":"627_CR5","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1214\/15-AOS1388","volume":"44","author":"D Bertsimas","year":"2016","unstructured":"Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann Stat 44:813\u2013852","journal-title":"Ann Stat"},{"key":"627_CR6","volume-title":"Pattern recognition and machine learning","author":"CM Bishop","year":"2006","unstructured":"Bishop CM (2006) Pattern recognition and machine learning. Springer, Berlin"},{"key":"627_CR7","first-page":"107","volume":"Extra vol.: Opt","author":"RE Bixby","year":"2012","unstructured":"Bixby RE (2012) A brief history of linear and mixed-integer programming computation. Doc Math Extra vol.: Optimization Stories:107\u2013121","journal-title":"Doc Math"},{"issue":"3","key":"627_CR8","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1214\/ss\/1009213726","volume":"16","author":"L Breiman","year":"2001","unstructured":"Breiman L (2001) Statistical modeling: the two cultures (with comments and a rejoinder by the author). Stat Sci 16(3):199\u2013231","journal-title":"Stat Sci"},{"issue":"4","key":"627_CR9","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1007\/s10878-015-9833-6","volume":"31","author":"C Chatzinakos","year":"2016","unstructured":"Chatzinakos C, Pitsoulis L, Zioutas G (2016) Optimization techniques for robust multivariate location and scatter estimation. J Comb Optim 31(4):1443\u20131460","journal-title":"J Comb Optim"},{"key":"627_CR10","doi-asserted-by":"crossref","unstructured":"Clark LA, Pregibon D (2017) Tree-based models. In: Statistical models in S. Routledge, pp 377\u2013419","DOI":"10.1201\/9780203738535-9"},{"issue":"5","key":"627_CR11","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1038\/scientificamerican0583-116","volume":"248","author":"P Diaconis","year":"1983","unstructured":"Diaconis P, Efron B (1983) Computer-intensive methods in statistics. Sci Am 248(5):116\u2013131","journal-title":"Sci Am"},{"issue":"1","key":"627_CR12","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1006\/jmva.1997.1666","volume":"61","author":"Y Dodge","year":"1997","unstructured":"Dodge Y (1997) Lad regression for detecting outliers in response and explanatory variables. J Multivar Anal 61(1):144\u2013158","journal-title":"J Multivar Anal"},{"key":"627_CR13","volume-title":"Methods of correlation and regression analysis: linear and curvilinear","author":"M Ezekiel","year":"1959","unstructured":"Ezekiel M, Fox KA (1959) Methods of correlation and regression analysis: linear and curvilinear. Wiley, Hoboken"},{"key":"627_CR14","unstructured":"Flores S (2011) Global optimization problems in robust statistics. Ph.D. thesis"},{"key":"627_CR15","doi-asserted-by":"crossref","unstructured":"Goldberg N, Rebennack S, Kim Y, Krasko V, Leyffer S (2021) MINLP formulations for continuous piecewise linear function fitting. Comput Optim Appl","DOI":"10.1007\/s10589-021-00268-5"},{"key":"627_CR17","unstructured":"Hastie T, Tibshirani R, Tibshirani RJ (2017) Extended comparisons of best subset selection, forward stepwise selection, and the lasso. ArXiv preprint arXiv:1707.08692"},{"issue":"2","key":"627_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0167-9473(99)00029-8","volume":"32","author":"DM Hawkins","year":"1999","unstructured":"Hawkins DM, Olive D (1999) Applications and algorithms for least trimmed sum of absolute deviations regression. Comput Stat Data Anal 32(2):119\u2013134","journal-title":"Comput Stat Data Anal"},{"issue":"3","key":"627_CR18","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1080\/00401706.1984.10487956","volume":"26","author":"DM Hawkins","year":"1984","unstructured":"Hawkins DM, Bradu D, Kass GV (1984) Location of several outliers in multiple-regression data using elemental sets. Technometrics 26(3):197\u2013208","journal-title":"Technometrics"},{"issue":"2","key":"627_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1023\/B:AIRE.0000045502.10941.a9","volume":"22","author":"V Hodge","year":"2004","unstructured":"Hodge V, Austin J (2004) A survey of outlier detection methodologies. Artif Intell Rev 22(2):85\u2013126","journal-title":"Artif Intell Rev"},{"key":"627_CR21","volume-title":"50 Years of integer programming 1958\u20132008: from the early years to the state-of-the-art","author":"M J\u00fcnger","year":"2009","unstructured":"J\u00fcnger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA (2009) 50 Years of integer programming 1958\u20132008: from the early years to the state-of-the-art. Springer, Berlin"},{"issue":"4","key":"627_CR22","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1214\/aos\/1176349759","volume":"13","author":"R Koenker","year":"1985","unstructured":"Koenker R, Bassett G et al (1985) On Boscovich\u2019s estimator. Ann Stat 13(4):1625\u20131628","journal-title":"Ann Stat"},{"issue":"4","key":"627_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1257\/jep.15.4.143","volume":"15","author":"R Koenker","year":"2001","unstructured":"Koenker R, Hallock KF (2001) Quantile regression. J Econ Perspect 15(4):143\u2013156","journal-title":"J Econ Perspect"},{"issue":"1","key":"627_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.ejor.2017.05.004","volume":"263","author":"V Krasko","year":"2017","unstructured":"Krasko V, Rebennack S (2017) Two-stage stochastic mixed-integer nonlinear programming model for post-wildfire debris flow hazard management: Mitigation and emergency evacuation. Eur J Oper Res 263(1):265\u2013282","journal-title":"Eur J Oper Res"},{"issue":"3","key":"627_CR25","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796\u2013817","journal-title":"SIAM J Optim"},{"issue":"435","key":"627_CR26","doi-asserted-by":"publisher","first-page":"1219","DOI":"10.1080\/01621459.1996.10476991","volume":"91","author":"C Liu","year":"1996","unstructured":"Liu C (1996) Bayesian robust multivariate linear regression with incomplete data. J Am Stat Assoc 91(435):1219\u20131227","journal-title":"J Am Stat Assoc"},{"key":"627_CR27","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10107-016-1030-6","volume":"162","author":"M Schmidt","year":"2017","unstructured":"Schmidt M, Le Roux N, Bach F (2017) Minimizing finite sums with the stochastic average gradient. Math Program 162:83\u2013112","journal-title":"Math Program"},{"key":"627_CR28","volume-title":"Machine learning: an algorithmic perspective","author":"S Marsland","year":"2015","unstructured":"Marsland S (2015) Machine learning: an algorithmic perspective. CRC Press, Boca Raton"},{"key":"627_CR29","volume-title":"Handbook of splines","author":"G Micula","year":"2012","unstructured":"Micula G, Micula S (2012) Handbook of splines, vol 462. Springer, Berlin"},{"key":"627_CR30","volume-title":"Introduction to linear regression analysis","author":"DC Montgomery","year":"1982","unstructured":"Montgomery DC, Peck EA (1982) Introduction to linear regression analysis. Wiley, Hoboken"},{"key":"627_CR31","volume-title":"Applied regression analysis","author":"R Norman","year":"1981","unstructured":"Norman R, Draper HS (1981) Applied regression analysis, 2nd edn. Wiley, Hoboken","edition":"2"},{"key":"627_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-99142-9","volume-title":"Open problems in optimization and data analysis","author":"PM Pardalos","year":"2018","unstructured":"Pardalos PM, Migdalas A (2018) Open problems in optimization and data analysis, vol 141. Springer, Berlin"},{"key":"627_CR33","unstructured":"Pelikan M, Goldberg DE, Cant\u00fa-Paz E et al (1999) Boa: the bayesian optimization algorithm. In: Proceedings of the genetic and evolutionary computation conference GECCO-99, vol 1. Citeseer, pp 525\u2013532"},{"issue":"2","key":"627_CR34","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/s10957-014-0687-3","volume":"167","author":"S Rebennack","year":"2015","unstructured":"Rebennack S, Kallrath J (2015) Continuous piecewise linear delta-approximations for univariate functions: computing minimal breakpoint systems. J Optim Theory Appl 167(2):617\u2013643","journal-title":"J Optim Theory Appl"},{"issue":"2","key":"627_CR35","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1287\/ijoc.2019.0890","volume":"32","author":"S Rebennack","year":"2020","unstructured":"Rebennack S, Krasko V (2020) Piecewise linear function fitting via mixed-integer linear programming. INFORMS J Comput 32(2):507\u2013530","journal-title":"INFORMS J Comput"},{"issue":"3","key":"627_CR36","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","volume":"22","author":"H Robbins","year":"1951","unstructured":"Robbins H, Monro S (1951) A stochastic approximation method. Ann Math Stat 22(3):400\u2013407","journal-title":"Ann Math Stat"},{"issue":"388","key":"627_CR37","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1080\/01621459.1984.10477105","volume":"79","author":"PJ Rousseeuw","year":"1984","unstructured":"Rousseeuw PJ (1984) Least median of squares regression. J Am Stat Assoc 79(388):871\u2013880","journal-title":"J Am Stat Assoc"},{"key":"627_CR38","doi-asserted-by":"publisher","DOI":"10.1002\/0471725382","volume-title":"Robust regression and outlier detection","author":"PJ Rousseeuw","year":"1987","unstructured":"Rousseeuw PJ, Leroy AM (1987) Robust regression and outlier detection. Wiley, Hoboken"},{"issue":"372","key":"627_CR39","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1080\/01621459.1980.10477560","volume":"75","author":"D Ruppert","year":"1980","unstructured":"Ruppert D, Carroll RJ (1980) Trimmed least squares estimation in the linear model. J Am Stat Assoc 75(372):828\u2013838","journal-title":"J Am Stat Assoc"},{"key":"627_CR40","unstructured":"Snoek J, Larochelle H, Adams RP (2012) Practical Bayesian optimization of machine learning algorithms. In: Advances in neural information processing systems, pp 2951\u20132959"},{"issue":"6","key":"627_CR41","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1109\/72.97934","volume":"2","author":"DF Specht","year":"1991","unstructured":"Specht DF (1991) A general regression neural network. IEEE Trans Neural Netw 2(6):568\u2013576","journal-title":"IEEE Trans Neural Netw"},{"issue":"3","key":"627_CR42","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1214\/aos\/1176345451","volume":"9","author":"SM Stigler","year":"1981","unstructured":"Stigler SM (1981) Gauss and the invention of least squares. Ann Stat 9(3):465\u2013474","journal-title":"Ann Stat"},{"issue":"5","key":"627_CR43","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/0167-7152(94)90007-8","volume":"19","author":"M Tableman","year":"1994","unstructured":"Tableman M (1994) The asymptotics of the least trimmed absolute deviations (LTAD) estimator. Stat Probab Lett 19(5):387\u2013398","journal-title":"Stat Probab Lett"},{"key":"627_CR44","doi-asserted-by":"publisher","first-page":"1981","DOI":"10.1016\/B978-0-12-823377-1.50331-1","volume-title":"30th European Symposium on computer aided process engineering, computer aided chemical engineering","author":"A Thebelt","year":"2020","unstructured":"Thebelt A, Kronqvist J, Lee RM, Sudermann-Merx N, Misener R (2020a) Global optimization with ensemble machine learning models. In: Pierucci S, Manenti F, Bozzano GL, Manca D (eds) 30th European Symposium on computer aided process engineering, computer aided chemical engineering, vol 48. Elsevier, Amsterdam, pp 1981\u20131986. https:\/\/doi.org\/10.1016\/B978-0-12-823377-1.50331-1"},{"key":"627_CR45","doi-asserted-by":"crossref","unstructured":"Thebelt A, Kronqvist J, Mistry M, Lee RM, Sudermann-Merx N, Misener R (2020b) ENTMOOT: a framework for optimization over ensemble tree models. arXiv:2003.04774","DOI":"10.1016\/j.compchemeng.2021.107343"},{"key":"627_CR46","volume-title":"Exploratory data analysis","author":"JW Tukey","year":"1977","unstructured":"Tukey JW (1977) Exploratory data analysis, vol 2. Addison-Wesley, Reading"},{"key":"627_CR16","doi-asserted-by":"crossref","unstructured":"van Handel R (2014) Probability in high dimension. Tech. rep., Princeton University NJ","DOI":"10.21236\/ADA623999"},{"key":"627_CR47","unstructured":"Vanhatalo J, Jyl\u00e4nki P, Vehtari A (2009) Gaussian process regression with student-t likelihood. In: Bengio Y, Schuurmans D, Lafferty JD, Williams CKI, Culotta A (eds.) Advances in Neural Information Processing Systems 22, pp. 1910\u20131918. Curran Associates, Inc. http:\/\/papers.nips.cc\/paper\/3806-gaussian-process-regression-with-student-t-likelihood.pdf"},{"key":"627_CR48","volume-title":"Applied linear regression","author":"S Weisberg","year":"1985","unstructured":"Weisberg S (1985) Applied linear regression, 2nd edn. Wiley, Hoboken","edition":"2"},{"key":"627_CR49","volume-title":"Integer and combinatorial optimization","author":"LA Wolsey","year":"1999","unstructured":"Wolsey LA, Nemhauser GL (1999) Integer and combinatorial optimization, vol 55. Wiley, Hoboken"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-021-00627-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-021-00627-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-021-00627-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T11:09:40Z","timestamp":1724843380000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-021-00627-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["627"],"URL":"https:\/\/doi.org\/10.1007\/s00291-021-00627-y","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"value":"0171-6468","type":"print"},{"value":"1436-6304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"assertion":[{"value":"25 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2021","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.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}