Least quantile regression via modern optimization
From MaRDI portal
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 '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 () and medium () size problems to provable optimality in under two hours, and outperform all publicly available methods for large-scale (10,000) LQS problems.
Recommendations
- Least trimmed squares regression, least median squares regression, and mathematical program\-ming
- On Computing the Least Quantile of Squares Estimate
- The determination of a ``least quantile of squares regression line for all quantiles
- Least Median of Squares Regression
- The feasible solution algorithm for least trimmed squares regression
Cites work
- scientific article; zbMATH DE number 3829050 (Why is no real title available?)
- scientific article; zbMATH DE number 46303 (Why is no real title available?)
- scientific article; zbMATH DE number 3545027 (Why is no real title available?)
- scientific article; zbMATH DE number 1124626 (Why is no real title available?)
- scientific article; zbMATH DE number 194744 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- A General Qualitative Definition of Robustness
- A practical approximation algorithm for the LMS line estimator
- Algorithms and complexity for least median of squares regression
- An approximation algorithm for least median of squares regression
- An evolutionary algorithm for robust regression
- Computing the Exact Least Median of Squares Estimate and Stability Diagnostics in Multiple Linear Regression
- Convex Analysis
- High-breakdown robust multivariate methods
- Introductory lectures on convex optimization. A basic course.
- Least Median of Squares Regression
- Least median of squares and regression through the origin
- Least trimmed squares regression, least median squares regression, and mathematical program\-ming
- On the least median square problem
- One-Step Huber Estimates in the Linear Model
- Quantile approximation for robust statistical estimation and \(k\)-enclosing problems
- Robust Parameter Estimation in Computer Vision
- Robust regression using repeated medians
- Robust regression: Asymptotics, conjectures and Monte Carlo
- The feasible set algorithm for least median of squares regression
- Time- and Space-Efficient Algorithms for Least Median of Squares Regression
Cited in
(21)- Locating hyperplanes to fitting set of points: a general framework
- From predictive methods to missing data imputation: an optimization approach
- Discrete optimization methods to fit piecewise affine models to data points
- Optimal randomized classification trees
- Quantile inverse optimization: improving stability in inverse linear programming
- Time series modeling and forecasting by mathematical programming
- Best subset selection via a modern optimization lens
- A unified framework for bivariate clustering and regression problems via mixed-integer linear programming
- Certifiably optimal sparse inverse covariance estimation
- The ordered \(k\)-median problem: surrogate models and approximation algorithms
- Linear regression with sparsely permuted data
- Robust subset selection
- Outlier detection in time series via mixed-integer conic quadratic optimization
- SOCP relaxation bounds for the optimal subset selection problem applied to robust linear regression
- Simultaneous feature selection and outlier detection with optimality guarantees
- Sparse Convex Regression
- Cost-sensitive feature selection for support vector machines
- Optimal classification trees
- Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions
- OR forum: An algorithmic approach to linear regression
- Piecewise Linear Function Fitting via Mixed-Integer Linear Programming
This page was built for publication: Least quantile regression via modern optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482902)
