[2603.14218] Interleaved Resampling and Refitting: Data and Compute-Efficient Evaluation of Black-Box Predictors

Computer Science > Machine Learning arXiv:2603.14218 (cs) [Submitted on 15 Mar 2026 (v1), last revised 2 Apr 2026 (this version, v2)] Title:Interleaved Resampling and Refitting: Data and Compute-Efficient Evaluation of Black-Box Predictors Authors:Haichen Hu, David Simchi-Levi View a PDF of the paper titled Interleaved Resampling and Refitting: Data and Compute-Efficient Evaluation of Black-Box Predictors, by Haichen Hu and 1 other authors View PDF HTML (experimental) Abstract:We study the problem of evaluating the excess risk of large-scale empirical risk minimization under the square loss. Leveraging the idea of wild refitting and resampling, we assume only black-box access to the training algorithm and develop an efficient procedure for estimating the excess risk. Our evaluation algorithm is both computationally and data efficient. In particular, it requires access to only a single dataset and does not rely on any additional validation data. Computationally, it only requires refitting the model on several much smaller datasets obtained through sequential resampling, in contrast to previous wild refitting methods that require full-scale retraining and might therefore be unsuitable for large-scale trained predictors. Our algorithm has an interleaved sequential resampling-and-refitting structure. We first construct pseudo-responses through a randomized residual symmetrization procedure. At each round, we thus resample two sub-datasets from the resulting covariate pseudo-re...