We study the problem of excess risk evaluation for empirical risk minimization (ERM) under general convex loss functions. Our contribution is an efficient refitting procedure that computes the excess risk and provides high-probability upper bounds under the fixed-design setting. Assuming only black-box access to the training algorithm and a single dataset, we begin by generating two sets of artificially modified pseudo-outcomes termed wild response, created by stochastically perturbing the gradient vectors with carefully chosen scaling. Using these two pseudo-labeled datasets, we then refit the black-box procedure twice to obtain two corresponding wild predictors. Finally, leveraging the original predictor, the two wild predictors, and the constructed wild responses, we derive an efficient excess risk upper bound. A key feature of our analysis is that it requires no prior knowledge of the complexity of the underlying function class. As a result, the method is essentially model-free and holds significant promise for theoretically evaluating modern opaque machine learning system--such as deep nerral networks and generative model--where traditional capacity-based learning theory becomes infeasible due to the extreme complexity of the hypothesis class.

翻译：本文研究一般凸损失函数下经验风险最小化（ERM）的过剩风险评估问题。我们提出一种高效的重拟合方法，可在固定设计设定下计算过剩风险并提供高概率上界。仅假设对训练算法具有黑盒访问权限且仅使用单一数据集，我们首先通过以精心选择的缩放因子随机扰动梯度向量，生成两组人工修改的伪输出（称为野生响应）。利用这两组伪标记数据集，我们随后对黑盒过程进行两次重拟合，得到两个对应的野生预测器。最后，结合原始预测器、两个野生预测器及构建的野生响应，我们推导出一个高效的过剩风险上界。该方法分析的关键特征在于无需预先了解底层函数类的复杂度。因此，该方法本质上是模型无关的，对于理论评估现代不透明机器学习系统（如深度神经网络和生成模型）具有重要前景——这些系统的假设类极端复杂，使得传统的基于容量的学习理论难以适用。