×

A class of optimization problems motivated by rank estimators in robust regression. (English) Zbl 1492.90122

Summary: A rank estimator in robust regression is a minimizer of a function which depends (in addition to other factors) on the ordering of residuals but not on their values. Here we focus on the optimization aspects of rank estimators. We distinguish two classes of functions: a class with a continuous and convex objective function (CCC), which covers the class of rank estimators known from statistics, and also another class (GEN), which is far more general. We propose efficient algorithms for both classes. For GEN we propose an enumerative algorithm that works in polynomial time as long as the number of regressors is \(O(1)\). The proposed algorithm utilizes the special structure of arrangements of hyperplanes that occur in our problem and is superior to other known algorithms in this area. For the continuous and convex case, we propose an unconditionally polynomial algorithm finding the exact minimizer, unlike the heuristic or approximate methods implemented in statistical packages.

MSC:

90C25 Convex programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Hettmansperger, T.; McKean, J., Robust nonparametric statistical methods (2010), CRC Press
[2] Jurečková, J., Nonparametric estimate of regression coefficients, Ann Math Statist, 42, 1328-1338 (1971) · Zbl 0225.62052 · doi:10.1214/aoms/1177693245
[3] Jaeckel, LA., Estimating regression coefficients by minimizing the dispersion of the residuals, Ann Math Statist, 43, 1449-1458 (1972) · Zbl 0277.62049 · doi:10.1214/aoms/1177692377
[4] Hettmansperger, TP; McKean, JW., A robust alternative based on ranks to least squares in analysing linear models, Technometrics, 19, 3, 275-284 (1977) · Zbl 0369.62052 · doi:10.1080/00401706.1977.10489549
[5] Hallin, M.; Oja, H.; Paindaveine, D., Semiparametrically efficient rank-based inference for shape. II. Optimal R-estimation of shape, Ann Statist, 34, 6, 2757-2789 (2006) · Zbl 1115.62059 · doi:10.1214/009053606000000948
[6] Kloke, JD; McKean, JW; Rashid, MM., Rank-based estimation and associated inferences for linear models with cluster correlated errors, J Am Stat Assoc, 104, 485, 384-390 (2009) · Zbl 1388.62081 · doi:10.1198/jasa.2009.0116
[7] Hallin, M.; Swan, Y.; Verdebout, T., One-step R-estimation in linear models with stable errors, J Econometrics, 172, 2, 195-204 (2013) · Zbl 1443.62058 · doi:10.1016/j.jeconom.2012.08.016
[8] Hallin, M.; Paindaveine, D.; Verdebout, T., Efficient R-estimation of principal and common principal components, J Am Stat Assoc, 109, 507, 1071-1083 (2014) · Zbl 1368.62160 · doi:10.1080/01621459.2014.880057
[9] Hallin, M.; Mehta, C., R-estimation for asymmetric independent component analysis, J Am Stat Assoc, 110, 509, 218-232 (2015) · Zbl 1381.62145 · doi:10.1080/01621459.2014.909316
[10] Hallin, M.; La Vecchia, D., R-estimation in semiparametric dynamic location-scale models, J Econometrics, 196, 2, 233-247 (2017) · Zbl 1403.91274 · doi:10.1016/j.jeconom.2016.08.002
[11] Dutta, S.; Datta, S., Rank-based inference for covariate and group effects in clustered data in presence of informative intra-cluster group size, Stat Med, 37, 30, 4807-4822 (2018) · doi:10
[12] Jurečková, J.; Koul, HL; Navrátil, R., Behavior of R-estimators under measurement errors, Bernoulli, 22, 2, 1093-1112 (2016) · Zbl 1388.62207 · doi:10.3150/14-BEJ687
[13] Louhichi, S.; Miura, R.; Volný, D., On the asymptotic normality of the R-estimators of the slope parameters of simple linear regression models with associated errors, Statistics, 51, 1, 167-187 (2017) · Zbl 1369.62110 · doi:10.1080/02331888.2016.1261912
[14] Saleh, AKME; Picek, J.; Kalina, J., R-estimation of the parameters of a multiple regression model with measurement errors, Metrika, 75, 3, 311-328 (2012) · Zbl 1239.62081 · doi:10.1007/s00184-010-0328-2
[15] Jurečková, J., Averaged extreme regression quantile, Extremes, 19, 1, 41-49 (2016) · Zbl 1382.60079 · doi:10.1007/s10687-015-0232-2
[16] Kloke, JD; McKean, JW., Rfit: rank-based estimation for linear models, R J, 4, 2, 57-64 (2012) · doi:10.32614/RJ-2012-014
[17] Buck, RC., Partition of space, Am Math Mon, 50, 9, 541-544 (1943) · Zbl 0061.30609 · doi:10.1080/00029890.1943.11991447
[18] Zaslavsky, T., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes (1975), American Mathematical Society · Zbl 0296.50010
[19] Rada, M.; Černý, M., A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukuda’s reverse search, SIAM J Discrete Math, 32, 1, 455-473 (2018) · Zbl 1383.52021 · doi:10
[20] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl Math, 65, 1-3, 21-46 (1996) · Zbl 0854.68070 · doi:10.1016/0166-218X(95)00026-N
[21] Sleumer, N.Output-sensitive cell enumeration in hyperplane arrangements. In: Algorithm theory - SWAT’98. Berlin: Springer; 1998. p. 300-309 [cited 2020 Aug 26]. Available from:http://link.springer.com/chapter/10 .1007/BFb0054377. · Zbl 0978.68791
[22] Ferrez, JA; Fukuda, K.; Liebling, TM., Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, Eur J Oper Res, 166, 1, 35-50 (2005) · Zbl 1066.90101 · doi:10.1016/j.ejor.2003.04.011
[23] Schrijver, A., Theory of linear and integer programming (2000), New York (NY): John Wiley & Sons, Inc., New York (NY)
[24] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization (1993), Berlin: Springer-Verlag, Berlin · Zbl 0837.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.