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

We introduce the problem of robustly reliable learning for the regression setting in adversarial environments. Given a test point $x_{test}$, a training dataset $S$ of $n$ data points, a corruption budget $b \ll n$, and a real-valued hypothesis class $\mathcal H$, our goal is to output the optimal prediction range $I^*_{x_{test}}(S, b)$, such that any $L$-Lipschitz predictor consistent with all but at most $b$ points in $S$ must predict a value $h(x_{test}) \in I$. We then instantiate the analysis for $L$-Lipschitz hypothesis classes, a natural and widely studied class in the regression setting, focusing on two key scenarios. First, for the restricted case where the corrupted dataset is guaranteed to be $L$-Lipschitz consistent, we propose a simple and efficient $b^{th}$-best heuristic algorithm and prove its correctness in computing the tightest possible range $I^*_{x_{test}}(S, b)$. We then establish its computational complexity of $O(n)$ and show that it is computationally optimal in this scenario. Building on this foundation, we address the general scenario where the dataset $S$ is no longer $L$-Lipschitz consistent. We demonstrate that computing the optimal range in this setting reduces to analyzing a violation graph, which models the pairwise $L$-Lipschitz violations among data points. By leveraging the structural properties of this graph's kernel, we propose a Fixed-Parameter Tractable (FPT) algorithm that computes the exact optimal range in $O(n^2 + b^4)$ time. Furthermore, under the Strong Exponential Time Hypothesis (SETH), we establish a computational lower bound of $Ω(n^{2 - o(1)})$, proving that our algorithm is computationally optimal. Finally, we discuss open directions for the problem of robustly reliable learning for regression.

Linear models with an $L_1$-norm penalty remain state-of-the-art for high-dimensional ($d > 1,000,000$) tasks, offering a straightforward method for solving real-world industry problems. Despite their widespread use in industry and utility, many $L_1$ solvers are not effective for general use, are prohibitively slow, and are ineffective in parallelization. This makes them difficult to train in an MLOps pipeline on large industry-scale corpora. In this work, we test several proposed ``state-of-the-art'' solutions from the literature and find that older methods are currently far superior for general use. We also identify several recommendations for academics to perform research that avoids erroneously overconfident results, which can prevent the transition to production use. Equally surprising, we find that a new and simple baseline, using LBFGS on a sub-gradient, is highly effective with minor tweaks, despite being dismissed in the literature for theoretical non-convergence. In practice, we find it is an easier-to-support and easier-to-scale method for production use.

To achieve outlier-robust geometric estimation, robust objective functions are generally employed to mitigate the influence of outliers. The widely used consensus maximization(CM) is highly robust when paired with global branch-and-bound(BnB) search. However, CM relies solely on inlier counts and is sensitive to the inlier threshold. Besides, the discrete nature of CM leads to loose bounds, necessitating extensive BnB iterations and computation cost. Truncated losses(TL), another continuous alternative, leverage residual information more effectively and could potentially overcome these issues. But to our knowledge, no prior work has systematically explored globally minimizing TL with BnB and its potential for enhanced threshold resilience or search efficiency. In this work, we propose GTM, the first unified BnB-based framework for globally-optimal TL loss minimization across diverse geometric problems. GTM involves a hybrid solving design: given an n-dimensional problem, it performs BnB search over an (n-1)-dimensional subspace while the remaining 1D variable is solved by bounding the objective function. Our hybrid design not only reduces the search space, but also enables us to derive Lipschitz-continuous bounding functions that are general, tight, and can be efficiently solved by a classic global Lipschitz solver named DIRECT, which brings further acceleration. We conduct a systematic evaluation on various BnB-based methods for CM and TL on the robust linear regression problem, showing that GTM enjoys remarkable threshold resilience and the highest efficiency compared to baseline methods. Furthermore, we apply GTM on different geometric estimation problems with diverse residual forms. Extensive experiments demonstrate that GTM achieves state-of-the-art outlier-robustness and threshold-resilience while maintaining high efficiency across these estimation tasks.