Abstract:
|
We study a class of problems where sum of truncated convex functions is minimized. In statistics it is often encountered when L0-penalized models are fitted. While in general they often leads to NP-hard non-convex optimization problems, we show that there is a polynomial-time algorithm in low-dimensional settings by partitioning the domain of the function. Our algorithm shows superior performance when compared with other global optimization algorithms, especially in cases where the objective function has a complex landscape. We also demonstrate the utility of our algorithm for outlier detection in robust simple linear regression, and we find that it outperforms state-of-the-art methods when a large amount of outliers are present.
|