Data-driven Error Estimation: Excess Risk Bounds without Class Complexity as Input

arXiv:2405.04636v4 Announce Type: replace-cross
Abstract: Constructing confidence intervals that are simultaneously valid across a class of estimates is central to tasks such as multiple mean estimation, generalization guarantees, and adaptive experimental design. We frame this as an “error estimation problem,” where the goal is to determine a high-probability upper bound on the maximum error for a class of estimates. We propose an entirely data-driven approach that derives such bounds for both finite and infinite class settings, naturally adapting to a potentially unknown correlation structure of random errors. Notably, our method does not require class complexity as an input, overcoming a major limitation of existing approaches. We present our simple yet general solution and demonstrate applications to simultaneous confidence intervals, excess-risk control and optimizing exploration in contextual bandit algorithms.