Robustly Reliable Learning for Regression

Abstract: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 $\Omega(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.

Machine Learning (cs.LG)

arXiv:2610.17381 [cs.LG]

(or arXiv:2610.17381v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.17381 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.