Robust Regression via Heuristic Hard Thresholding

Robust Regression via Heuristic Hard Thresholding

Xuchao Zhang, Liang Zhao, Arnold P. Boedihardjo, Chang-Tien Lu

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 3434-3440. https://doi.org/10.24963/ijcai.2017/480

The presence of data noise and corruptions recently invokes increasing attention on Robust Least Squares Regression (RLSR), which addresses the fundamental problem that learns reliable regression coefficients when response variables can be arbitrarily corrupted. Until now, several important challenges still cannot be handled concurrently: 1) exact recovery guarantee of regression coefficients 2) difficulty in estimating the corruption ratio parameter; and 3) scalability to massive dataset. This paper proposes a novel Robust Least squares regression algorithm via Heuristic Hard thresholding (RLHH), that concurrently addresses all the above challenges. Specifically, the algorithm alternately optimizes the regression coefficients and estimates the optimal uncorrupted set via heuristic hard thresholding without corruption ratio parameter until it converges. We also prove that our algorithm benefits from strong guarantees analogous to those of state-of-the-art methods in terms of convergence rates and recovery guarantees. We provide empirical evidence to demonstrate that the effectiveness of our new method is superior to that of existing methods in the recovery of both regression coefficients and uncorrupted sets, with very competitive efficiency.
Keywords:
Machine Learning: Machine Learning
Constraints and Satisfiability: Constraint Optimisation
Combinatorial & Heuristic Search: Combinatorial search/optimisation