提出新方法高效求解鲁棒回归中的最小截断平方问题
Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements
- 用超平面排列优化混合整数规划模型，强化最优解结构约束
- 固定特征数时，分支定界树规模为样本量的多项式级
- 实测在5000样本下1分钟内达1%精度，比现有方法快数十倍
我们研究鲁棒统计中的关键问题——惩罚最小截断平方（LTS）回归的计算挑战。该方法通过截断大残差来降低异常值影响，但其本身是NP难问题，现有混合整数优化（MIO）方法因松弛弱且随样本数呈指数增长而难以扩展。本文提出一种新MIO公式，将超平面排列逻辑嵌入视角重构中，显式强制最优解的结构性质。若特征数固定，所得分支定界树大小为样本量的多项式级。此外，开发了专用分支定界算法，采用一阶方法结合对偶界高效求解节点松弛。在合成与真实数据集上的实验表明，性能显著优于现有方法：在5000样本、20特征的合成数据上，本方法1分钟内达到1%差距，而对比方法一小时内仍无法达成。该提升使低维场景下的精确鲁棒回归可处理更大样本。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。