Robustly Reliable Learning for Regression

Avrim Blum, Anh Tuan Nguyen

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…