Least quantile regression via modern optimization

DOI10.1214/14-AOS1223zbMATH Open1302.62154arXiv1310.8625MaRDI QIDQ482902FDOQ482902

Rahul Mazumder, Dimitris Bertsimas

Publication date: 6 January 2015

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1310.8625

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

zbMATH Keywords

algorithmscontinuous optimizationglobal optimizationrobust statisticsmixed integer programmingleast median of squaresleast quantile regression

Mathematics Subject Classification ID

Nonparametric robustness (62G35) Linear regression; mixed models (62J05) Nonconvex programming, global optimization (90C26) Mixed integer programming (90C11)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust regression: Asymptotics, conjectures and Monte Carlo
• Introductory lectures on convex optimization. A basic course.
• Least Median of Squares Regression
• Robust regression using repeated medians
• Title not available (Why is that?)
• A General Qualitative Definition of Robustness
• High-breakdown robust multivariate methods
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex Analysis
• Algorithms and complexity for least median of squares regression
• The feasible set algorithm for least median of squares regression
• Time- and Space-Efficient Algorithms for Least Median of Squares Regression
• Title not available (Why is that?)
• One-Step Huber Estimates in the Linear Model
• A practical approximation algorithm for the LMS line estimator
• On the least median square problem
• An approximation algorithm for least median of squares regression
• Least trimmed squares regression, least median squares regression, and mathematical program\-ming
• Computing the Exact Least Median of Squares Estimate and Stability Diagnostics in Multiple Linear Regression
• Robust Parameter Estimation in Computer Vision
• An evolutionary algorithm for robust regression
• Quantile approximation for robust statistical estimation and \(k\)-enclosing problems
• Least median of squares and regression through the origin

Cited In (21)

• Simultaneous feature selection and outlier detection with optimality guarantees
• The ordered \(k\)-median problem: surrogate models and approximation algorithms
• Cost-sensitive feature selection for support vector machines
• Quantile Inverse Optimization: Improving Stability in Inverse Linear Programming
• Optimal randomized classification trees
• Title not available (Why is that?)
• Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions
• Piecewise Linear Function Fitting via Mixed-Integer Linear Programming
• Locating hyperplanes to fitting set of points: a general framework
• Certifiably optimal sparse inverse covariance estimation
• SOCP relaxation bounds for the optimal subset selection problem applied to robust linear regression
• Time series modeling and forecasting by mathematical programming
• Sparse Convex Regression
• OR forum: An algorithmic approach to linear regression
• Discrete optimization methods to fit piecewise affine models to data points
• Best subset selection via a modern optimization lens
• A unified framework for bivariate clustering and regression problems via mixed-integer linear programming
• Robust subset selection
• Linear regression with sparsely permuted data
• Outlier Detection in Time Series via Mixed-Integer Conic Quadratic Optimization
• Optimal classification trees

Uses Software

• robustbase
• Gurobi
• rrcov
• PROGRESS

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)