Least quantile regression via modern optimization

By Dimitris J. Bertsimas, Rahul Mazumder. 2013

69 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Statistics and Probability

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, background): “The evidence in this paper as well as in Bertsimas and Mazumder (2014) suggests that MIO methods are tractable and lead to desirable properties (improved accuracy and sparsity among others) at the expense of higher, but still reasonable, computational times.”
Optimal classification trees (2017, unknown): “Coupled with the increase in computer hardware during this same period, a factor of approximately 570,000 (Top500 Supercomputer Sites 2015), the overall speedup factor is approximately 800 billion! This astonishing increase in MIO solver performance has enabled many recent successes when applying mo”
The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization (2015, methodology): “We illustrate that our approach can handle problem instances with p = 10,000 features with certifiable optimality making it a highly scalable combinatorial variable selection approach in sparse linear modeling.”
Optimal trees for prediction and prescription (2018, background): “Coupled with the increase in computer hardware during this same period as shown in Figure 1-7, a factor of approximately 1,560,000 [113], the overall speedup factor is approximately 2 trillion! This astonishing increase in MIO solver performance has enabled many recent successes when applying modern”
Robust Classification (2019, methodology): “…have explored using modern mixed-integer optimization (MIO) methods to solve problems in classical statistics, such as the least quantile squares (Bertsimas and Mazumder 2014) and best subset selection problems (Bertsimas et al. 2016), and to create algorithmic approaches for fitting regression…”
Linear regression with sparsely permuted data (2017, background): “Due to recent advances in integer programming that have meanwhile been taken advantage of for a series of other statistical problems [8, 9], it turns out that problem (18) is practically feasible at least for n in the order of a few thousands.”