Least quantile regression via modern optimization

Abstract

We address the Least Quantile of Squares (LQS) (and in particular the Least Median of Squares) regression problem using modern optimization methods. We propose a Mixed Integer Optimization (MIO) formulation of the LQS problem which allows us to find a provably global optimal solution for the LQS problem. Our MIO framework has the appealing characteristic that if we terminate the algorithm early, we obtain a solution with a guarantee on its sub-optimality. We also propose continuous optimization methods based on first-order subdifferential methods, sequential linear optimization and hybrid combinations of them to obtain near optimal solutions to the LQS problem. The MIO algorithm is found to benefit significantly from high quality solutions delivered by our continuous optimization based methods. We further show that the MIO approach leads to (a) an optimal solution for any dataset, where the data-points $(y_i,{\mathbf{x}}_i)$'s are not necessarily in general position, (b) a simple proof of the breakdown point of the LQS objective value that holds for any dataset and (c) an extension to situations where there are polyhedral constraints on the regression coefficient vector. We report computational results with both synthetic and real-world datasets showing that the MIO algorithm with warm starts from the continuous optimization methods solve small ($n=100$) and medium ($n=500$) size problems to provable optimality in under two hours, and outperform all publicly available methods for large-scale ($n=$10,000) LQS problems.

Published in at http://dx.doi.org/10.1214/14-AOS1223 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• High-Breakdown Robust Multivariate Methods

Cited by in corpus (13)

• Cost-sensitive Feature Selection for Support Vector Machines
• Optimal randomized classification trees
• A general framework for locating hyperplanes to fitting set of points
• Simultaneous Feature Selection and Outlier Detection with Optimality Guarantees
• The Trimmed Lasso: Sparsity and Robustness
• Robust subset selection
• Certifiably Optimal Sparse Inverse Covariance Estimation
• Quantile Inverse Optimization: Improving Stability in Inverse Linear Programming
• Learning non-smooth models: instrumental variable quantile regressions and related problems
• Learning Structure in Nested Logit Models
• SOCP relaxation bounds for the optimal subset selection problem applied to robust linear regression
• Doubly Robust Feature Selection with Mean and Variance Outlier Detection and Oracle Properties
• Robust Learning of Trimmed Estimators via Manifold Sampling