# Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements

arXiv: https://arxiv.org/abs/2604.11584 · HTML: https://mlsanity.com/paper/2604.11584/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 13 Apr 2026.

## Builds on (most cited first, 11 of 11)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Iterative Least Trimmed Squares for Mixed Linear Regression](https://mlsanity.com/paper/1902.03653/) (2019)
- [A geometric way to build strong mixed-integer programming formulations](https://mlsanity.com/paper/1811.10409/) (2018)
- [Simultaneous Feature Selection and Outlier Detection with Optimality Guarantees](https://mlsanity.com/paper/2007.06114/) (2020)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Walks on hyperplane arrangements and optimization of piecewise linear functions](https://mlsanity.com/paper/1912.12750/) (2019)
- [Adaptive Capped Least Squares](https://mlsanity.com/paper/2107.00109/) (2021)

## Built on by (most cited first, 1 of 1)

- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

We study computational aspects of a key problem in robust statistics -- the penalized least trimmed squares (LTS) regression problem, a robust estimator that mitigates the influence of outliers in data by capping residuals with large magnitudes. Although statistically attractive, penalized LTS is NP-hard, and existing mixed-integer optimization (MIO) formulations scale poorly due to weak relaxations and exponential worst-case complexity in the number of observations. We propose a new MIO formulation that embeds hyperplane arrangement logic into a perspective reformulation, explicitly enforcing structural properties of optimal solutions. We show that, if the number of features is fixed, the resulting branch-and-bound tree is of polynomial size in the sample size. Moreover, we develop a tailored branch-and-bound algorithm that uses first-order methods with dual bounds to solve node relaxations efficiently. Computational experiments on synthetic and real datasets demonstrate substantial improvements over existing MIO approaches: on synthetic instances with 5000 samples and 20 features, our tailored solver reaches a 1% gap in 1 minute while competing approaches fail to do so within one hour. These gains enable exact robust regression at significantly larger sample sizes in low-dimensional settings.