Wild Refitting for Model-Free Excess Risk Evaluation of Opaque Machine Learning Models under Bregman Loss —— Theoretical Analysis of Model Efficacy in the AI Era Haichen Hu CCSE, MIT huhc@mit.edu David Simchi-Levi IDSS, MIT dslevi@mit.edu Abstract We study the problem of evaluating the excess risk of classical penalized empirical risk minimization (ERM) with Bregman losses. We show that by leveraging the recently proposed wild refitting procedure ( Wainwright 2025 ) , one can efficiently upper bound the excess risk through the so-called “wild optimism,” without relying on the global structure of the underlying function class. This property makes our approach inherently model-free. Unlike conventional analyses, our framework operates with just one dataset and black-box access to the training procedure. The method involves randomized vector-valued symmetrization with an appropriate scaling of the prediction residues and constructing artificially modified outcomes, upon which we retrain a second predictor for excess risk estimation. We establish high-probability performance guarantees both under the fixed design setting and the random design setting, demonstrating that wild refitting under Bregman losses, with an appropriately chosen wild noise scale, yields a valid upper bound on the excess risk. This work thus is promising for theoretically evaluating modern opaque ML and AI models such as deep neural networks and large language models, where the model class is too complex for classical learning theory and empirical process techniques to apply. Key words: Statistical Learning, Artificial Intelligence, Excess Risk Evaluation, Wild Refitting 1 Introduction Deep Neural Networks, Generative AI, and Large Language Models (LLMs) have become central to modern industry, shaping applications across a wide range of domains, including business ( Chen et al. 2023 ; Liang et al. 2025 ) , public governance ( Androniceanu 2024 ; Acemoglu ) , transportation ( Zhang et al. 2024 ) , and healthcare ( Bordukova et al. 2024 ) . As these systems increasingly influence critical decision-making processes, the question of how to evaluate their performance has become both practically and scientifically important. On the empirical side, the evaluation of these often opaque and hardly interpretable machine learning models has been extensively studied ( Raschka 2018 ; Shankar et al. 2024 ; Mizrahi et al. 2024 ; Hendrycks et al. 2021 ) . Researchers typically assess the effectiveness of deep learning models by running them on established benchmarks across diverse datasets, thereby demonstrating improvements in dimensions such as predictive accuracy ( He et al. 2016 ) and robustness to perturbations or distribution shifts ( Liu et al. 2025 ) . Such benchmarks provide a standardized and reproducible way to measure progress, and they have played a central role in driving empirical advances. In contrast, the theoretical understanding of how to rigorously evaluate these complex deep learning models remains very limited. A major obstacle lies in the fact that the processes of training ( Shrestha and Mahmood 2019 ; Shen et al. 2024 ) , including pre-training ( Achiam et al. 2023 ) and fine-tuning ( VM et al. 2024 ) involve optimization over millions or even billions of parameters ( Brown et al. 2020 ) . This extreme scale and complexity place these models well beyond the reach of classical tools in learning theory, such as the VC dimension ( Abu-Mostafa 1989 ) , covering number arguments ( Zhou 2002 ) , or the eluder dimension ( Russo and Van Roy 2013 ) . While these theoretical measures have been foundational for understanding simpler hypothesis classes, they struggle to capture the behavior of highly overparameterized models trained with stochastic optimization at scale. In statistics, evaluating complex models often includes hold-out data splitting ( Reitermanova et al. 2010 ) and cross-validation ( Refaeilzadeh et al. 2009 ; Browne 2000 ) . However, a key limitation of these methods is that such estimates just reflect the averaged risk over new samples instead of probabilistic guarantees on the realized risk of the predictor on the training dataset ( Bates et al. 2024 ) . By contrast, applying these models in downstream decision-making often requires probabilistic guarantees, namely, bounds on the excess risk that hold with high probability, such as in bandits and reinforcement learning ( Lattimore and Szepesvári 2020 ; Foster and Rakhlin 2023 ) . Consequently, bridging these two gaps between empirical practice and theoretical guarantees is, therefore, an open and pressing challenge for the field. A central challenge is that: Can we rigorously provide high probability bounds on the excess risk of complex deep learning models in theory without restrictive assumptions on the underlying function classes? Our Contribution In this paper, we provide an affirmative answer to this question. Specifically, we study the most general empirical risk minimization (ERM) procedure under the Bregman loss as an abstraction of deep neural network training and develop an efficient algorithm for evaluating its excess risk. Our approach does not rely on structural assumptions about the underlying function family, which is why we call our method “model-free” in the title, but instead requires only black-box access to the training or optimization procedure, making it directly applicable to modern deep neural network training and LLM fine-tuning. We establish high-probability statistical guarantees in not only fixed design but also random design. To the best of our knowledge, this is the first work to achieve such results in the random design setting. Paper Structure The remainder of our paper is organized as follows. In Section 3 , we introduce the empirical risk minimization (ERM) framework with Bregman loss and carefully define the quantities that are central in our analysis. In Section 4 , we formally present our proposed method, Wild Refitting with Bregman Loss, and provide an intuitive explanation of the main ideas behind its construction. Building on this foundation, Section 5 and Section 6 develop the theoretical results, where we establish high-probability guarantees for our procedure and demonstrate the meaning of every component in these bounds. Together, these sections provide a comprehensive picture of both the algorithmic design and the statistical guarantees underlying our approach. Notations We use [n] to denote the set of positive integers \{1,2,\ldots,n\} . For a matrix A\in\mathbb{R}^{m\times n} , we let \|A\|_{F} denote its Frobenius norm, and define \|A\|_{\infty}:=\|\operatorname{vec}(A)\|_{\infty}=\max_{1\leq i\leq m,\,1\leq j\leq n}|a_{ij}|, where \operatorname{vec}(A) denotes the vectorization of A . Note that this definition differs from the conventional matrix infinity norm, as we simply treat A as an mn -dimensional vector under vectorization. We use \mathcal{X}^{\otimes m} to represent the product space of m identical spaces \mathcal{X} . For any convex function \phi , we denote its Bregman divergence by D_{\phi} . For two probability distributions P and Q , we write \text{KL}(P\,\|\,Q) for their Kullback–Leibler divergence and H^{2}(P,Q) for their squared Hellinger distance. For two vectors x and y , we use x\odot y to represent their Hadamard product. For any learning algorithm \mathcal{A} and dataset \mathcal{D} , \mathcal{A}(\mathcal{D}) represents the predictor trained on dataset \mathcal{D} through procedure \mathcal{A} . 2 Related Works Our work is primarily related to the following streams of research: statistical learning and excess risk evaluation;data-splitting and resampling; empirical model evaluation and benchmarking. Statistical learning ( Vapnik 2013 ) has long served as a cornerstone in the theoretical analysis of machine learning algorithms. A central and active line of research focuses on understanding the excess risk or generalization error of learning procedures. Classical approaches rely on empirical process theory to analyze ERM, with complexity measures such as the VC dimension ( Vapnik and Chervonenkis 2015 ; Blumer et al. 1989 ) , covering numbers ( Nickl and Pötscher 2007 ; van de Geer 2000 ) , Rademacher complexity ( Massart 2007 ; Bartlett et al. 2005 ) , and the fat-shattering dimension ( Bartlett et al. 1994 ) . More recently, new notions such as the eluder dimension ( Russo and Van Roy 2013 ) , eigendecay rate ( Goel and Klivans 2017 ; Li et al. 2024 ; Hu et al. 2025 ) , and sequential Rademacher complexity ( Rakhlin et al. 2012 ) have been developed to study generalization in online learning. Despite these advances, bounding these metrics fundamentally depends on the global structure of the underlying function class. When the hypothesis space is extremely rich—such as when covering numbers are infinite—these methods break down and fail to yield meaningful excess risk guarantees ( Adcock and Dexter 2021 ; Kurkova and Sanguineti 2025 ) . In contrast, our approach is function-class free and circumvents these structural limitations. Recently, Wainwright 2025 proposed the idea of wild refitting to evaluate the mean-square excess risk in the fixed design setting. Our work substantially extends this line of research by analyzing ERM with general Bregman losses and, moreover, by establishing model-free excess risk bounds in the random design setting. In asymptotic statistics, the quality of estimation procedures is often evaluated through hold-out or sample-splitting methods, where the dataset is divided into training and evaluation subsets. Examples include double machine learning ( Chernozhukov et al. 2017 ; Chen et al. 2025 ) and orthogonal statistical learning ( Foster and Syrgkanis 2023 ) . While effective, these approaches suffer from inefficient data usage. Related techniques such as cross-validation ( Berrar et al. 2019 ; Browne 2000 ; Gorriz et al. 2024 ) further increase the computational burden by repeatedly retraining the model. In contrast, our method only requires a single dataset and a small number of queries to the black-box procedure. An alternative is the use of resampling methods, including the bootstrap ( Hesterberg 2011 ; DiCiccio and Efron 1996 ; Davison and Hinkley 1997 ) and its variants such as the wild bootstrap ( Mammen 1993 ; Flachaire 2005 ; Davidson and MacKinnon 2010 ) . However, bootstrap methods are designed to approximate asymptotic properties for estimators such as CIs and variances, whereas our wild-refitting procedure provides high-probability, non-asymptotic upper bounds on excess risk by re-optimizing with randomized perturbations. In deep learning, empirical evaluation of trained models is typically conducted through benchmarking, that is, testing their accuracy on standard datasets or comparing their performance against well-established baseline algorithms ( Malaiya et al. 2019 ; He et al. 2016 ; Voloshin et al. ) . Recently, in the context of LLM research, thousands of such studies have been published. For instance, benchmarking on text tasks ( Wang et al. 2019 ; Zhang* et al. 2020 ) , on reasoning and mathematical deduction ( Tafjord et al. 2020 ; Amini et al. 2019 ; Clark et al. 2021 ) , and on applications in business analytics, finance, and operations research ( Huang et al. 2025 ; Xie et al. 2023 ; Liang et al. 2025 ) . However, these efforts are purely empirical without a theoretical understanding of how well post-trained models truly perform. Our task in this paper is to address this gap. 3 Model Setup: ERM with Bregman Loss In this section, we formally introduce the problem setup that serves as the foundation of our study. Throughout the discussion, we assume that the reader has a basic familiarity with standard concepts in convex analysis. For the sake of completeness, we also provide a concise overview of the mathematical background on convex analysis in Appendix A , which can be consulted as needed. We consider the following empirical risk minimization (ERM) setting. We have an input space \mathcal{X} , and an output space (prediction space) \mathcal{Y} , assuming that our prediction is vector-valued, i.e., \mathcal{Y}\subset\mathbb{R}^{d} for some d>0 . A predictor is defined as a mapping f:\mathcal{X}\mapsto\mathcal{Y} such that given any input \mathcal{X} , it returns a prediction vector f(x) . In the fixed design setting first, where we view \left\{x_{i}\right\}_{i=1}^{n} as fixed. The objective of our interest is f^{*}\in\mathop{\mathrm{argmin}}\left\{\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{y_{i}}[l(y_{i},f(x_{i}))]\right\}, where \left\{y_{i}\right\}_{i=1}^{n} is the true response sequence in the training dataset. Correspondingly, in the random setting, our task is that f^{*}\in\mathop{\mathrm{argmin}}\left\{\mathbb{E}_{X,Y}[l(Y,f(X))]\right\}. We focus on a Bregman loss function l:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R} , defined such that l(x,y) corresponds to the Bregman divergence generated by a differentiable convex potential \phi:\mathbb{R}^{d}\mapsto\mathbb{R} , i.e., l(x,y)=D_{\phi}(x,y). Intuitively, l(y,f(x)) serves as a measure of the discrepancy between the observed outcome and the prediction produced by a candidate function f . Directly optimizing over the space of all measurable functions is clearly infeasible. In practice, especially in deep learning, one typically restricts the search to an underlying function class, which we denote by \mathcal{F} and interpret as the underlying training architecture. Given a dataset \mathcal{D}=\left\{(x_{i},y_{i})\right\}_{i=1}^{n} , the learner invokes a black-box empirical risk minimization (ERM) procedure \texttt{Alg}_{\mathsf{Erm}} to approximately solve the following optimization problem: \widehat{f}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\left\{\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f(x_{i}))+\mathcal{R}(f)\right\}, The term \mathcal{R}(f) serves as a regularization penalty imposed on the function f . Classical examples include ridge regression, where \mathcal{R}(f) corresponds to the squared \ell_{2} norm, and Lasso, where it corresponds to the \ell_{1} norm. In this work, for the sake of technical clarity, we adopt a simplified viewpoint: we assume that the trainer has prior knowledge ensuring that all reasonable predictions must lie within a compact set \mathcal{C} . Accordingly, we model the regularizer \mathcal{R}(f) as the following: \displaystyle\mathcal{R}(f) \displaystyle=\left\{\begin{array}[]{ll}\text{0},&\text{if }f(x_{i})\in\mathcal{\mathcal{C}}\ \forall i,\\ \infty,&\text{otherwise.}\end{array}\right. To proceed with the analysis of the loss function, we introduce a structural assumption on the generating convex function \phi . Assumption 3.1 . The function \phi is \beta -smooth and \alpha -strongly convex with a unique minimizer. This regularity condition ensures well-behaved curvature properties of \phi , which in turn yield desirable stability and identifiability features for the induced Bregman loss. In particular, under 3.1 , the Bregman loss function satisfies the following four key properties. We defer their proofs to Appendix C . Proposition 3.2 . If \phi is \beta -smooth, then for any fixed y , D_{\phi}(\cdot,y) is \beta -smooth with respect to the first variable. Proposition 3.3 . If \phi satisfies 3.1 , then for any fixed y , D_{\phi}(\cdot,y) satisfies the Polyak–Łojasiewicz (PL) inequality with constant \frac{\alpha^{2}}{\beta} . Moreover, we also assume that the Bregman loss function satisfies the quasi-triangle inequality. Proposition 3.4 . Any function \phi(u) which is \alpha -strongly convex and \beta -smooth satisfies 3.1 . The corresponding D_{\phi}(x,y) satisfies that D_{\phi}(x,y)^{1/2}\leq C_{0}(D_{\phi}(x,z)^{1/2}+D_{\phi}(z,y)^{1/2}),\ C_{0}=\sqrt{\frac{\beta}{\alpha}}. It is worth emphasizing that 3.1 is not a restrictive condition. In fact, it is readily satisfied in a wide range of statistical and machine learning models. To illustrate this, we now present several representative examples where the assumption holds naturally. Example 3.5 . In regression, \phi(u)=\frac{1}{2}||u||_{2}^{2} satisfies 3.1 with \alpha=\beta=1 . Moreover, D_{\phi}(x,y)=\frac{1}{2}||x-y||_{2}^{2} satisfies Proposition 3.4 with C_{0}=1 . Example 3.6 . In the stochastic binary classification setting, denoting the 1 dimensional probability simplex as \Delta_{1}\subset\mathbb{R}^{2} , and \varepsilon_{0}\leq p\leq 1-\varepsilon_{0} , to be the probability of predicting 1 over 0 . For the convex function \phi(p)=-\sqrt{p}-\sqrt{1-p} , then we have that \sqrt{2}\leq\phi^{\prime\prime}(p)=\frac{1}{4p^{3/2}}+\frac{1}{4(1-p)^{3/2}}\leq\frac{1}{2\varepsilon_{0}^{3/2}}, and 3.1 is satisfied. Moreover, the Bregman divergence is D_{\phi}(p_{1},p_{2})=\frac{(\sqrt{p_{1}}-\sqrt{p_{2}})^{2}}{2\sqrt{p_{2}}}+\frac{(\sqrt{1-p_{1}}-\sqrt{1-p_{2}})^{2}}{2\sqrt{1-p_{2}}}. The squared Hellinger distance between two Bernoulli random variables H^{2}(p_{1},p_{2})=\frac{1}{2}\left((\sqrt{p_{1}}-\sqrt{p_{2}})^{2}+(\sqrt{1-p_{1}}-\sqrt{1-p_{2}})^{2}\right). Therefore, we have \frac{1}{\sqrt{1-\varepsilon_{0}}}H(p_{1},p_{2})\leq D^{1/2}_{\phi}(p_{1},p_{2})\leq\frac{1}{\sqrt{\varepsilon_{0}}}H(p_{1},p_{2}). By the fact that the Hellinger distance is a metric, we know that D_{\phi} satisfies Proposition 3.4 with C_{0}=\frac{\sqrt{1-\varepsilon_{0}}}{\sqrt{\varepsilon_{0}}} . Example 3.7 . In the density estimation setting, we consider the hypothesis class parametrized by \left\{p_{\theta}:\theta\in\Theta\right\} , \Theta\subset\mathbb{R}^{m} with loss function l(\theta_{1},\theta_{2})=D_{\phi}(p_{\theta_{1}},p_{\theta_{2}}) , where \phi(\theta)=\int\frac{1}{\log p_{\theta}(x)}p_{\theta}(x)dx , then D_{\phi}(p_{\theta_{1}},p_{\theta_{2}})=\text{KL}(p_{\theta_{1}}||p_{\theta_{2}}) . If we know that p_{\theta}\geq\eta_{0}>0,\ \forall\theta , then by Polyanskiy and Wu 2025 , we have \sqrt{\log_{2}e}H(p_{\theta_{1}}||p_{\theta_{2}})\leq\sqrt{\text{KL}(p_{\theta_{1}}||p_{\theta_{2}})}\leq\sqrt{\frac{\log(\frac{1}{\eta_{0}}-1)}{1-2\eta_{0}}}H(p_{\theta_{1}}||p_{\theta_{2}}). If for any x,\theta , the Hessian of the negative log-likelihood -\nabla^{2}\log(p_{\theta}(x))\preceq\beta I_{m} , then the loss \phi(\theta) is \beta -smooth. Moreover, we restrict our analysis to a sufficiently small neighborhood of \theta^{*} such that there exists a constant r_{0}>0 s.t. \|\theta-\theta^{*}\|\leq r_{0},\ \forall\ \theta\in\Theta . The Fisher information matrix I(\theta)=\mathbb{E}_{p_{\theta^{*}}}[s_{\theta}(X)s_{\theta}(X)^{\top}] is positive definite with eigenvalues \lambda_{\min}(I(\theta))\geq\alpha , then \phi(\theta) is \alpha -strongly convex and the loss l(\cdot,\cdot) satisfies 3.1 and Proposition 3.4 . Returning back to our analysis, we first provide a theoretical explicit formula about f^{*} . Proposition 3.8 . Under the fixed design setting, if \phi is strictly convex, then we have f^{*}(x_{i})=\mathbb{E}[y_{i}|x_{i}],\ \forall i=1,\cdots,n. Similarly, in the random design setting, if \phi is strictly convex, then we have f^{*}(x)=\mathbb{E}[Y|X=x],\ \forall x\in\mathcal{X}. With Proposition 3.8 , in the remaining part of the paper, we will write y=f^{*}(x)+w , where w is a zero-mean stochastic noise vector conditioned on x . Correspondingly, in fixed design, we write y_{i}=f^{*}(x_{i})+w_{i} . In this paper, for technical simplicity, we assume that every coordinate of w has a symmetric distribution. This is without loss of generality because otherwise we can always introduce an independent copy of the noise and apply the symmetrization lemma ( Vershynin 2018 , pp. 136–138) to resolve this. The performance metric of \texttt{Alg}_{\mathsf{Erm}} in the fixed design setting is defined by the empirical excess risk : \mathcal{E}_{\mathcal{D}}(\widehat{f}):=\left[\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f^{*}(x_{i}))\right]. In the random design setting, where we assume that (x_{i},y_{i})\sim\mathbb{P}_{X,Y} . The risk measure is its expectation counterpart, excess risk , which is defined as \mathcal{E}(\widehat{f}):=\mathbb{E}_{\mathcal{D}}[\mathcal{E}_{\mathcal{D}}(\widehat{f})]=\mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]-\mathbb{E}_{X,Y}[l(Y,f^{*}(X))] We first focus on the fixed design setting in Section 5.1 . Subsequently, in Section 5.2 , we present an upper bound on the excess risk in the random design setting. When there is no ambiguity between the two settings, we simply refer to the “empirical excess risk” as “excess risk.” First, by some algebra, we have that \displaystyle\mathcal{E}_{\mathcal{D}}(\widehat{f}) \displaystyle=\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f^{*}(x_{i})) \displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left(D_{\phi}(y_{i},\widehat{f}(x_{i}))-D_{\phi}(y_{i},f^{*}(x_{i}))\right) \displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left(D_{\phi}(f^{*}(x_{i}),\widehat{f}(x_{i}))+\left\langle\nabla\phi(f^{*}(x_{i}))-\nabla\phi(\widehat{f}(x_{i})),w_{i}\right\rangle\right). In the last inequality, we use the three-point equality of the Bregman divergence ( Lemma B.1 ). Define the proxy excess risk as L_{n}(f^{*},\widehat{f}):=\frac{1}{n}\sum_{i=1}^{n}l(f^{*}(x_{i}),\widehat{f}(x_{i}))=\frac{1}{n}\sum_{i=1}^{n}D_{\phi}(f^{*}(x_{i}),\widehat{f}(x_{i})). Then the true excess risk equals the proxy excess risk plus a stochastic perturbation term: \left\langle\nabla\phi(f^{*}(x_{i}))-\nabla\phi(\widehat{f}(x_{i})),w_{i}\right\rangle. We need to bound these two terms together tightly by the quantities that we know. The definition of the proxy excess risk is intuitive because L_{n}(f^{*},\widehat{f}) captures the aggregate point-wise output discrepancies between the true optimizer f^{*} and the estimator \widehat{f} with respect to the loss function. Generally, we also use L_{n}(f_{1},f_{2}) to denote \frac{1}{n}\sum_{i=1}^{n}l(f_{1}(x_{i}),f_{2}(x_{i})) . 4 Algorithm: Wild Refitting with Bregman Loss In this section, we provide a principled way to bound the excess risk in a function class-free way via wild refitting. Wild refitting is first studied by Wainwright 2025 in the mean square loss setting, where the trainer cares about the point-wise square discrepancy between two predictors. In this paper, we consider the more general smooth loss setting even without the convexity assumption. The key idea of wild refitting is to refit the trained predictor on a perturbed version of the original dataset, where the perturbation is constructed stochastically without assuming any structural knowledge about the underlying function class. Wild refitting treats the predictor as a black box and directly operates on its output, enabling statistically valid inference even when the training procedure is complex, while avoiding restrictive parametric assumptions on function classes. Specifically, the basic idea is that after we train the model \widehat{f} via the procedure \texttt{Alg}_{\mathsf{Erm}} based on the dataset \mathcal{D}=\left\{(x_{i},y_{i})\right\}_{i=1}^{n} , we compute the residue vector between the true outcome y_{i} and our predicted value \widehat{f}(x_{i}) , then we construct a sequence of d -dimensional random vectors \left\{\varepsilon_{i}\right\}_{i=1}^{n} and apply the Hadamard product of it to the residue vector sequence \left\{\widetilde{w}_{i}\right\}_{i=1}^{n}=\left\{y_{i}-\widehat{f}(x_{i})\right\}_{i=1}^{n} to get \left\{\varepsilon_{i}\odot\widetilde{w}_{i}\right\}_{i=1}^{n} . Subsequently, for some scale \rho>0 , we consider the wild responses sequence y^{\diamond}_{i}:=\widehat{f}(x_{i})-\rho\varepsilon_{i}\odot\widetilde{w}_{i},\ i\in[n] . Because \varepsilon_{i} is symmetric in distribution, the random variable -\rho,\varepsilon_{i}\odot\widetilde{w}_{i} has the same distribution as +\rho,\varepsilon_{i}\odot\widetilde{w}_{i} . Finally, we compute the refitted wild solution f^{\diamond}_{\rho} based on the artificially constructed dataset \left\{(x_{i},y^{\diamond}_{i})\right\}_{i=1}^{n} . The pseudo-code is provided below. Remark 4.1 . One could also additionally introduce a “recentering” function \widetilde{f} to construct the wild residuals \widetilde{w}_{i}=y_{i}-\widetilde{f}(x_{i}) , as discussed in Wainwright 2025 . In practice, however, it is common to take \widetilde{f}=\widehat{f} . For simplicity, we therefore adopt this convention throughout and define the wild responses directly using \widehat{f} , without introducing a separate recentering function. Algorithm 1 Wild-Refitting with Bregman Loss Procedure \texttt{Alg}_{\mathsf{Erm}} , training dataset \mathcal{D}_{0}=\left\{(x_{1},y_{1}),\cdots,(x_{n},y_{n})\right\} , noise scale \rho>0 , loss function l(x,y)=D_{\phi}(x,y) , and refitting dataset \mathcal{D}_{1}=\emptyset . Apply algorithm \texttt{Alg}_{\mathsf{Erm}} on the training dataset. Get predictor \widehat{f}=\texttt{Alg}_{\mathsf{Erm}}(\left\{(x_{i},y_{i})\right\}_{i=1}^{n}). for i=1:n do Compute residues \widetilde{w}_{i}=y_{i}-\widehat{f}(x_{i}) . Apply Hadamard product between d -dimensional Rademacher random vector \varepsilon_{i} and \widetilde{w}_{i} : \widetilde{w}^{\diamond}_{i}:=\varepsilon_{i}\odot\widetilde{w}_{i}. Construct wild responses y^{\diamond}_{i}=\widehat{f}(x_{i})-\rho\widetilde{w}^{\diamond}_{i} . Append (x_{i},y_{i}^{\diamond}) to \mathcal{D}_{1}: \mathcal{D}_{1}\leftarrow\mathcal{D}_{1}\cup\{(x_{i},y_{i}^{\diamond})\}. end for Compute the refitted wild solution f^{\diamond}_{\rho}=\texttt{Alg}_{\mathsf{Erm}}(\mathcal{D}_{1}) . Output \widehat{f} , f^{\diamond}_{\rho} , \mathcal{D}_{1} , \mathcal{D}_{0} . Intuitively, traditional generalization theory often requires taking the supremum over the entire model class, which is overly conservative since we only care about the data-dependent predictor \widehat{f} . When the model class is highly complex, even refined notions such as local Rademacher complexity may become extremely large, leading to vacuous bounds. In contrast, our wild-refitting approach circumvents the need to analyze the Rademacher complexity of the model class. Instead, we control this term through the wild optimism , which is given by the outputs of Algorithm 1 ; see Lemma 5.1 in Section 5 for details. In the next section, we will show that the excess risk could be efficiently upper bounded by the output of Algorithm 1 without prior knowledge on the function class \mathcal{F} . 5 Theoretical Excess Risk Guarantees In this section, we present our theoretical guarantees for Algorithm 1 . The analysis is carried out in two parts. In Section 5.1 , we establish an upper bound on the empirical excess risk under the fixed design. In Section 5.2 , we extend our theorem from fixed design to random design setting in a highly nontrivial way, which utilizes results from algorithm stability analysis. See Appendix D for the proof details. However, the two theorems in Section 5 cannot be directly applied because they depend on some unknown quantity \widehat{r}_{n} , which is intuitively the average discrepancy between the objective \widehat{f} and the “best” predictor f^{\dagger} that we can get through procedure \texttt{Alg}_{\mathsf{Erm}} . In the next Section 6 , we derive a theorem that bounds \widehat{r}_{n} , and further demonstrate a practical method for computing it. 5.1 Bounding the Excess Risk in Fixed Design To bound the empirical excess risk, we first need to specify the quantities we want. In this paper, we use \varepsilon and w to represent the matrices (\varepsilon_{1},\cdots,\varepsilon_{n}) and (w_{1},\cdots,w_{n}) . Recall that in Section 3 , we have \mathcal{E}_{\mathcal{D}}(\widehat{f})\leq L_{n}(f^{*},\widehat{f})+\left|\left\langle\nabla\phi(f^{*}(x_{i}))-\nabla\phi(\widehat{f}(x_{i})),w_{i}\right\rangle\right|. For the first term, by the convexity of the Bregman loss with respect to the first variable, we have \displaystyle\frac{1}{n}\sum_{i=1}^{n}l(f^{*}(x_{i}),\widehat{f}(x_{i})) \displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle \displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}D_{\phi}(y_{i},\widehat{f}(x_{i}))+\left|\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle\right|. Therefore, by the fact that \left|\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))\right|=\left|\nabla\phi(f^{*}(x_{i}))-\nabla\phi(\widehat{f}(x_{i}))\right| we have \mathcal{E}_{\mathcal{D}}(\widehat{f})\leq\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))+2\left|\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle\right|. The first term is the training error term, which is known to us. Our task is thus to bound the absolute value of the following quantity, which is defined as the true optimism complexity . \text{Opt}^{*}(\widehat{f}):=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle. Analyzing this term usually involves empirical process theory, where we try to bound the optimism term in terms of the sample size n and some number based on the assumptions about the training architecture and function family. In this paper, we define the following empirical process W_{n}(r) as wild noise complexity : W_{n}(r):r\mapsto\sup_{f\in\mathcal{B}_{r}(\widehat{f})}\left\{\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle\right\}, where for any g , the term \mathcal{B}_{r}(g) is defined as the empirical Bregman ball: \mathcal{B}_{r}(g):=\left\{f\in\mathcal{F}|L_{n}(g,f)\leq r^{2}\right\}=\left\{f\in\mathcal{F}|\sqrt{L_{n}(g,f)}\leq r\right\}. However, in many applications, the function class \mathcal{F} is too complicated such that analyzing the structure of it is intractable. To evaluate such models theoretically, we utilize the wild refitting procedure and define the following wild optimism in terms of quantities we learn from Algorithm 1 : \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}):=\frac{1}{n\rho}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho})-\frac{1}{n\rho}\sum_{i=1}^{n}l(y^{\diamond}_{i},f^{\diamond}_{\rho}(x_{i}))+\frac{1}{n}\sum_{i=1}^{n}\beta\rho||(\varepsilon_{i}\odot\widetilde{w}_{i})||^{2}_{2}. The power of the wild-refitting procedure is illustrated in the following lemma. Lemma 5.1 . We have W_{n}(\frac{1}{n}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i})))\leq\frac{1}{n\rho}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i}))-\frac{1}{n\rho}\sum_{i=1}^{n}l(y^{\diamond}_{i},f^{\diamond}_{\rho}(x_{i}))+\frac{1}{n}\sum_{i=1}^{n}\beta\rho||(\varepsilon_{i}\odot\widetilde{w}_{i})||^{2}_{2}, i.e., W_{n}(\sqrt{L_{n}(\widehat{f},f^{\diamond}_{\rho})})\leq\widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}). Lemma 5.1 shows that we could upper bound the supremum of the empirical process by the wild optimism term, which is something that we know from the outputs of Algorithm 1 . In fact, this lemma helps us to avoid analyzing the underlying function class directly and is vital for our analysis. We further define the noiseless optimization problem and its solution as follows: f^{\dagger}=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\left\{\frac{1}{n}\sum_{i=1}^{n}l(f^{*}(x_{i}),f(x_{i}))+\mathcal{R}(f)\right\}. Intuitively, f^{\dagger} is the “optimal” solution that we can get because its training dataset is the cleanest without noise. Then, we define intermediate noiseless optimism as \text{Opt}^{\dagger}(\widehat{f})=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle, and the empirical process: Z_{n}^{\varepsilon}(r):=\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\left[\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle\right]. Intuitively, f^{\dagger} is the predictor we get through procedure \texttt{Alg}_{\mathsf{Erm}} if there is no noise in our dataset \mathcal{D} . Defining \widehat{r}_{n}:=\sqrt{L_{n}(f^{\dagger},\widehat{f})} to be the empirical discrepancy between f^{\dagger} and \widehat{f} , we have the following theorem. Theorem 5.2 . Consider any radius r such that r\geq\sqrt{L_{n}(f^{\dagger},\widehat{f})} , and let \rho>0 be the noise scale for which \sqrt{L_{n}(\widehat{f},f^{\diamond}_{\rho})}=3(\beta/\alpha)^{1/2}r . Then for any 0<\delta<1 , with probability at least 1-8\delta , |\text{Opt}^{*}(\widehat{f})|\leq|\widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})|+A_{n}(\widehat{f})+\left[\sqrt{L_{n}(f^{*},f^{\dagger})}+5r\right]\cdot\frac{2||w||_{\infty}(\beta^{3/2}\vee\beta^{2})\sqrt{d\log(1/\delta)}}{(\alpha^{3/2}\wedge\alpha)\sqrt{n}}. Therefore, regarding the excess risk, with probability at least 1-8\delta , \mathcal{E}_{\mathcal{D}}(\widehat{f})\leq\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))+2\left\{|\widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})|+A_{n}(\widehat{f})+\left[\sqrt{L_{n}(f^{*},f^{\dagger})}+5r\right]\cdot\frac{2||w||_{\infty}(\beta^{3/2}\vee\beta^{2})\sqrt{d\log(1/\delta)}}{(\alpha^{3/2}\wedge\alpha)\sqrt{n}}\right\}. The term A_{n}(\widehat{f}) is called pilot error , which is given by A_{n}(\widehat{f}):=\sup_{f\in\mathcal{B}_{3r(\beta/\alpha)^{1/2}}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot(\widehat{f}(x_{i})-f^{*}(x_{i}))\right\rangle. Moreover, we name the probabilistic deviation term as B_{n}(t) . B_{n}(t):=\left\{\sqrt{L_{n}(f^{*},f^{\dagger})}+5r\right\}\frac{2||w||_{\infty}(\beta^{3/2}\vee\beta^{2})\sqrt{d}t}{(\alpha^{3/2}\wedge\alpha)\sqrt{n}}. See Section D.2 for the proof of this theorem. We now provide some intuition behind this theorem. In essence, it states that the absolute value of the true optimism, |\text{Opt}^{*}(\widehat{f})| , can be bounded from above by the sum of three components: the wild optimism term, the probability deviation term, and the pilot term. For the probability deviation term, we comment that it gradually vanishes as the sample size n\rightarrow\infty , the term \sqrt{L_{n}(f^{*},f^{\dagger})} represents the average discrepancy between f^{\dagger} and f^{*} , accounting for potential model mis-specification in the probability deviation term. For the pilot error term, we notice that by Lemma 5.1 , we can bound W_{n}(3(\beta/\alpha)^{1/2}r) by the wild optimism term \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}) , i.e., \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})\geq W_{n}(3(\beta/\alpha)^{1/2}r)=\sup_{f\in\mathcal{B}_{3r\sqrt{\beta/\alpha}}(\widehat{f})}\left\{\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle\right\}. Comparing the right-hand side with the definition of the pilot error term, we see that the only difference is that \widetilde{w}_{i} in W_{n}(3(\beta/\alpha)^{1/2}r) is replaced by (\widehat{f}(x_{i})-f^{*}(x_{i})) in A_{n}(\widehat{f}) . Intuitively, as long as the training procedure is well-behaved, the discrepancy between \widehat{f}(x_{i}) and f^{*}(x_{i}) is primarily approximation error and is expected to be smaller in magnitude than that plus the fluctuation generated by the additional stochastic noise term w_{i} . This observation suggests that the pilot error term can be controlled by W_{n}(3(\beta/\alpha)^{1/2}r) , which itself can be further bounded by \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}) . Such a comparison is natural as it reflects the intuition that the estimation error between \widehat{f} and f^{*} is typically less volatile than the combination of that error with random noise. Moreover, note that we do not require every coordinate of the noise to have the same distribution, which allows heteroskedasticity among the noises. Indeed, in our bound, the only term is the maximal value of the amplitude among noises. 5.2 Extension: From Fixed Design to Random Design In this section, we extend our analysis in Section 5 from the fixed design setting to the random design setting. Our analysis leverages established theorems and results from the machine learning subfield of algorithmic stability. Algorithmic stability characterizes how sensitive a learning algorithm is to perturbations of the training data, such as removing or replacing individual data points. Bousquet and Elisseeff 2002 first demonstrated that incorporating stability into the analysis allows one to bound the generalization gap without resorting to function class complexity measures. Building on this idea, we adopt the similar techniques from several subsequent works ( Charles and Papailiopoulos 2018 ; Elisseeff et al. 2005 ) to extend our guarantees from fixed design to random design, as presented in Theorem 5.3 . Theorem 5.3 . Under the same conditions of Theorem 5.2 , we further assume that the loss function l(y,u)=D_{\phi}(y,u) not only satisfies 3.1 , but also satisfies that ||\nabla\phi||_{2}\leq L , and that 0\leq D_{\phi}\leq M . If the training dataset \mathcal{D} is collected i.i.d., that is, (x_{i},y_{i})\overset{i.i.d}{\sim}\mathbb{P}_{X,Y} , then for our algorithm \texttt{Alg}_{\mathsf{Erm}} , we have that with probability at least 1-11\delta , \displaystyle\mathbb{E}_{X,Y}\left[l(Y,\widehat{f}(X))\right]-\mathbb{E}_{X,Y}\left[l(Y,f^{*}(X))\right] \displaystyle\leq \displaystyle\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))+2\left\{|\widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})|+A_{n}(\widehat{f})+\left[\sqrt{L_{n}(f^{*},f^{\dagger})}+5r\right]\cdot\frac{2||w||_{\infty}(\beta^{3/2}\vee\beta^{2})\sqrt{d\log(1/\delta)}}{(\alpha^{3/2}\wedge\alpha)\sqrt{n}}\right\} \displaystyle+\sqrt{\frac{M^{2}+36ML^{2}/\alpha}{2n\delta}}+M\sqrt{\frac{\log(2/\delta)}{2n}}, where A_{n}(\widehat{f})=\sup_{f\in\mathcal{B}_{3(\beta/\alpha)^{1/2}r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot(\widehat{f}(x_{i})-f^{*}(x_{i}))\right\rangle is again the pilot error term in Theorem 5.2 . In this way, we obtain an excess risk guarantee in the random design setting. Compared with the fixed design case, such a guarantee is significantly more relevant for sequential decision-making problems. This makes our theory better aligned with downstream tasks that incorporate pre-trained models, including settings with missing covariates ( Hu and Simchi-Levi 2025 ) , surrogate rewards ( Ji et al. 2025 ) , and partial dynamics knowledge ( Alharbi et al. 2024 ) . 6 Bounding the Noiseless Estimation Error From the assumptions in Theorem 5.2 and Theorem 5.3 , it is clear that the result becomes meaningful only if we can obtain an upper bound on \widehat{r}_{n}=\sqrt{L_{n}(f^{\dagger},\widehat{f})} . In this section, we present an explicit theorem for such bounds, under the condition that the training procedure \texttt{Alg}_{\mathsf{Erm}} satisfies the non-expansive property ( Definition 6.1 ). See Appendix E for the full proof. Definition 6.1 ( \phi -non-expansive) . We say the training procedure \texttt{Alg}_{\mathsf{Erm}} is \phi -non-expansive if for any noiseless dataset \mathcal{D}_{u}=\left\{(x_{i},f^{*}(x_{i}))\right\}_{i=1}^{n} and the noisy dataset \mathcal{D}_{n}=\left\{(x_{i},f^{*}(x_{i})+u_{i})\right\}_{i=1}^{n} , denoting f^{\dagger}=\mathcal{A}(\mathcal{D}_{u}) and \widetilde{f}=\mathcal{A}(\mathcal{D}_{n}) to be the predictors trained on the two datasets, then we have L_{n}(f^{\dagger},\widetilde{f})\leq\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),\widetilde{f}(x_{i})),u_{i}\right\rangle Theorem 6.2 . If our training procedure \texttt{Alg}_{\mathsf{Erm}} is \phi -non-expansive, then for any \delta\leq e^{-9} , we have that with probability at least 1-4\delta , \widehat{r}_{n}^{2}\leq\max\left\{\frac{\log^{2}(1/\delta)}{n},W_{n}\left((2+\frac{1}{\log(1/\delta)})\widehat{r}_{n}\right)\right\}+\widehat{r}_{n}^{2}\frac{6||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha\sqrt{\log(1/\delta)}}+A_{n}(\widehat{f}). Moreover, if the underlying function class \mathcal{F} is convex, then with probability at least 1-4\delta , for any noise scale \rho , \widehat{r}_{n}^{2}\leq\max\left\{(r^{\diamond}_{\rho})^{2},\frac{\log(1/\delta)^{2}}{n},\frac{\widehat{r}_{n}}{r^{\diamond}_{\rho}}W_{n}\left(\sqrt{\beta/\alpha}\left(2+\frac{1}{\sqrt{\log(1/\delta)}}\right)\widehat{r}_{n}\right)\right\}+\widehat{r}_{n}^{2}\frac{6||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha\sqrt{\log(1/\delta)}}+A_{n}(\widehat{f}). Illustration of Theorem 6.2 : The first bound in Theorem 6.2 involves several components, including the probability deviation terms and the pilot error term. The latter is dominated by the wild optimism term \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}) for a suitable choice of \rho>0 . When \delta is sufficiently small, the probability deviation term is expected to become negligibly small, leaving the main contribution as \max\left\{\tfrac{\log^{2}(1/\delta)}{n},\,W_{n}\left((2+\frac{1}{\log(1/\delta)})\widehat{r}_{n}\right)\right\}. Moreover, the term \log^{2}(1/\delta)/n is of lower order provided that \widehat{r}_{n}\gtrsim 1/\sqrt{n} ( Bartlett et al. 2005 ) , which corresponds to the simplest parametric function class setting. Consequently, our goal is, roughly speaking, to identify a smallest r satisfying r^{2}\geq W_{n}\left((2+\frac{1}{\log(1/\delta)})r\right), For the chosen value of t . For any q , evaluating W_{n}(q) is tractable since it only depends on the predictor \widehat{f} and the wild noises \left\{\widetilde{w}_{i}\right\}_{i=1}^{n} . Alternatively, by Lemma 5.1 , one can compute an upper bound of W_{n}(q) by varying the noise scale \rho until the corresponding wild predictor f^{\diamond}_{\rho} satisfies L_{n}(\widehat{f},f^{\diamond}_{\rho})=q^{2} . Computationally, we take a look at the expression of W_{n}(r) . By definition, equivalently, we just need to solve the optimization problem \min_{f\in\mathcal{B}_{r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla\phi(f(x_{i})),\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle. Denoting z_{i}:=\varepsilon_{i}\odot\widetilde{w}_{i} , one could notice that as long as the set \mathcal{B}_{r}(\widehat{f}) and \mathcal{U}=\left\{(f(x_{1}),\cdots,f(x_{n})):f\in\mathcal{B}_{r}(\widehat{f})\right\} is convex, then the set \mathcal{U}_{\phi}:=\left\{(\nabla\phi(f(x_{1})),\cdots,\nabla\phi(f(x_{n}))):f\in\mathcal{B}_{r}(\widehat{f})\right\} is also convex. Hence, the optimization problem is reduced to a linear optimization problem over a convex set, which can be solved efficiently ( Martin 2012 ; Applegate et al. 2021 ) . The second bound of Theorem 6.2 is a bit looser but more interpretable for convex function classes because we do not need to numerically solve r^{2}\geq W_{n}\left((2+\frac{1}{\log(1/\delta)})r\right) , which might require us to solve iteratively, and every iteration requires solving a linear programming problem. Instead, we have \widehat{r}_{n}\leq\max\left\{r^{\diamond}_{\rho},\frac{W_{n}\left(\sqrt{\beta/\alpha}\left(2+\frac{1}{\sqrt{\log(1/\delta)}}\right)r^{\diamond}_{\rho}\right)}{r^{\diamond}_{\rho}}\right\}. This bound is nicer as we could directly compute an upper bound for one single noise scale \rho to obtain an upper bound of \widehat{r}_{n} . Then we could adjust our noise scale accordingly and refine our estimation of \widehat{r}_{n} . Once we have obtained an upper bound on \widehat{r}_{n} , we can then return to Theorem 5.2 and Theorem 5.3 . They suggest that—apart from the higher-order and pilot terms—we can upper bound the true optimism \text{Opt}^{*}(\widehat{f}) via the wild optimism \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}) for the noise scale that we have chosen. Finally, we combine this upper bound on the optimism in Theorem 5.2 and Theorem 5.3 so as to upper bound the excess risk. 7 Discussion In this paper, we proposed a procedure for estimating the model excess risk under general Bregman losses based on the wild refitting procedure. Our framework greatly extends previous work ( Wainwright 2025 ) which only handles the mean square loss. We also give the first model-free excess risk evaluation under the random design setting. Our excess risk estimation bound does not rely on the global structure or prior knowledge of the underlying function class; instead, we just assume black-box access to the procedure, which makes it especially suitable for evaluating the performance of deep neural networks and fine-tuned LLMs, where the training architectures and the underlying function classes are too complicated to analyze. Finally, we emphasize that wild refitting remains a relatively new approach for excess risk evaluation, and several important open questions deserve further exploration. First, in our analysis, the excess risk bound remains dependent on the local structure around \widehat{f} specifically the ball \mathcal{B}_{r}(\widehat{f}) used in selecting the noise scale \rho . The possibility of getting rid of this term remains an open question. Second, it is natural to ask whether the wild refitting procedure can be extended to more general loss functions, such as the pinball loss used in quantile regression. An even more challenging scenario arises when the loss itself is non-convex, which is pervasive in modern deep learning models and poses additional difficulties for both analysis and computation. Theoretical analysis on other regularization penalties is also interesting. Moreover, a key computational bottleneck lies in evaluating W_{n}(\cdot) in Theorem 6.2 . Developing efficient algorithms to approximate or compute this quantity would significantly enhance the practical applicability of the method. Finally, beyond theoretical analysis, it would be highly valuable to conduct empirical studies that apply wild refitting to evaluate real-world trained AI models, thereby demonstrating its effectiveness in practice. We leave these directions to future research. Appendix A Preliminary Concepts in Convex Analysis Definition A.1 (Hadamard product) . For any two matrices A,B\in\mathbb{R}^{m\times n} , we define their Hadamard product as C=A\odot B\in\mathbb{R}^{m\times n} , where c_{ij}=a_{ij}\cdot b_{ij},\ i\in[m],\ j\in[n]. Definition A.2 ( \beta -smoothness) . A differentiable function f:\mathbb{R}^{d}\to\mathbb{R} is called \beta -smooth if its gradient is \beta -Lipschitz continuous, i.e., \|\nabla f(x)-\nabla f(y)\|\leq\beta\|x-y\|,\quad\forall x,y\in\mathbb{R}^{d}. This is equivalent to f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+\tfrac{\beta}{2}\|y-x\|^{2}. Definition A.3 ( \alpha -strong convexity) . A differentiable function f:\mathbb{R}^{d}\to\mathbb{R} is called \alpha -strongly convex if there exists \alpha>0 such that f(y)\geq f(x)+\langle\nabla f(x),y-x\rangle+\tfrac{\alpha}{2}\|y-x\|^{2},\quad\forall x,y\in\mathbb{R}^{d}. Definition A.4 (Polyak–Łojasiewicz (PL) inequality) . A differentiable function f:\mathbb{R}^{d}\to\mathbb{R} is said to satisfy the \mu -Polyak–Łojasiewicz (PL) inequality if there exists \mu>0 such that \frac{1}{2}\|\nabla f(x)\|^{2}\geq\mu\bigl(f(x)-f(x^{*})\bigr),\quad\forall x\in\mathbb{R}^{d}, where x^{*}\in\arg\min_{z\in\mathbb{R}^{d}}f(z) . Definition A.5 (Bregman divergence) . Let \phi:\mathbb{R}^{d}\to\mathbb{R} be a differentiable and convex function. The Bregman divergence associated with \phi is defined as D_{\phi}(x,y)\;=\;\phi(x)-\phi(y)-\langle\nabla\phi(y),\,x-y\rangle,\quad\forall x,y\in\mathbb{R}^{d}. Appendix B Supporting Lemmas Lemma B.1 (Three-point equality of Bregman loss) . For any differentiable function \phi , the corresponding Bregman divergence satisfies D_{\phi}(x,z)=D_{\phi}(x,y)+D_{\phi}(y,z)+\left\langle\nabla\phi(y)-\nabla\phi(z),x-y\right\rangle,\ \forall\ x,y,z. The proof of Lemma B.1 can be done simply by checking the definition of the Bregman divergence. Lemma B.2 . ( Chewi 2025 , Proposition 2.7, p. 14) Let f:\mathbb{R}^{d}\mapsto\mathbb{R} and \alpha>0 . The following implications hold. 1. f is \alpha strongly convex \Rightarrow f satisfies the Polyak-Łojasiewicz inequality with constant \alpha>0 . 2. If f satisfies PŁ inequality with constant \alpha>0 , then it satisfies that f(x)-f^{*}\geq\frac{\alpha}{2}\inf_{x^{*}\in\mathcal{X}^{*}}||x-x^{*}||_{2}^{2}, where \mathcal{X}^{*} denotes the set of minimizers of f . Lemma B.3 (Hoeffding Inequality) . If X_{1},\cdots,X_{n} are independent and satisfy X_{i}\in[a_{i},b_{i}] , then for any t>0 , \Pr\!\left(\left|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\mathbb{E}\!\left[\frac{1}{n}\sum_{i=1}^{n}X_{i}\right]\right|\geq t\right)\;\leq\;2\exp\!\left(-\frac{2n^{2}t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right). Lemma B.4 (Concentration Inequality about bounded r.v. with Lipschitz function) . ( Wainwright 2019 , Thm 3.24) Consider a vector of independent random variables (X_{1},\cdots,X_{n}) , each taking values in [0,1] , and let f:\mathbb{R}^{n}\mapsto\mathbb{R} be a convex, L -Lipschitz with respect to the Euclidean norm. Then for all t\geq 0 , we have \mathbb{P}(|f(X)-\mathbb{E}[f(X)]|\geq t)\leq 2e^{\frac{-t^{2}}{2L^{2}}}. Lemma B.5 . If the loss function l satisfies Proposition 3.4 , then the empirical divergence L_{n} , we have that for any function f,g,h , (L_{n}(f,g))^{1/2}\leq\sqrt{2}C_{0}\left(L_{n}^{1/2}(f,h)+L^{1/2}_{n}(h,g)\right). Proof of Lemma B.5 . By definition, we have \displaystyle L_{n}(f,g)= \displaystyle\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),g(x_{i})) \displaystyle\leq \displaystyle\frac{1}{n}\sum_{i=1}^{n}\left[C_{0}\left(\sqrt{l(f(x_{i}),h(x_{i}))}+\sqrt{l(h(x_{i}),g(x_{i}))}\right)\right]^{2} \displaystyle\leq \displaystyle 2C_{0}^{2}\left(\frac{1}{n}\sum_{i=1}^{n}l(f(x_{i}),h(x_{i}))+\frac{1}{n}\sum_{i=1}^{n}l(h(x_{i}),g(x_{i}))\right) \displaystyle= \displaystyle 2C_{0}^{2}(L_{n}(f,h)+L_{n}(h,g)). Taking the square root of both sides and noticing that \sqrt{a+b}\leq\sqrt{a}+\sqrt{b} , we finish the proof. ∎ Lemma B.6 . ( Elisseeff et al. 2005 ) Suppose some algorithm \mathcal{A} satisfies pointwise stability r in Definition D.4 with respect to loss function l . The loss function l(\cdot,\cdot) is bounded between 0 and M>0 . If we are given a dataset \mathcal{D}=\left\{(x_{i},y_{i})\right\}_{i=1}^{n} where (x_{i},y_{i})\overset{\text{i.i.d.}}{\sim}\mathbb{P}_{X,Y} , then for any 1>\delta>0 , with probability at least 1-\delta , \mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]\leq\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))+\sqrt{\frac{M^{2}+12Mn\beta}{2n\delta}}. The expectation is taken over the joint distribution \mathbb{P}_{X,Y} . Lemma B.7 . ( Charles and Papailiopoulos 2018 ) If for any u fixed, the function l(\cdot,u) is L -Lipschitz continuous, the functional T_{n}(g)=\frac{1}{n}\sum_{i=1}^{n}l(y_{i},g(x_{i})) satisfies the Polyak–Łojasiewicz (PL) inequality with parameter \mu . If the learning algorithm \mathcal{A} satisfies that \widehat{f}=\mathop{\mathrm{argmin}}_{g\in\mathcal{X}}T_{n}(g) for some set \mathcal{X} , where \widehat{f} is trained by \mathcal{A} on dataset \mathcal{D}=\left\{(x_{i},y_{i})\right\}_{i=1}^{n} . Then, \mathcal{A} has pointwise hypothesis stability with \epsilon_{sta}=\frac{2L^{2}}{\mu(n-1)} . Appendix C Proofs in Section 3 Proof of Proposition 3.2 . We prove this by direct calculation, for any y fixed, \nabla_{1}D_{\phi}(x,y)=\nabla\phi(x)-\nabla\phi(y). Therefore, ||\nabla_{1}D_{\phi}(x_{1},y)-\nabla_{1}D_{\phi}(x_{2},y)||=||\nabla\phi(x_{1})-\nabla\phi(x_{2})||\leq\beta||x_{1}-x_{2}||. So we finish the proof. ∎ Proof of Proposition 3.3 . Denoting x^{*} as the unique minimizer of \phi , from the \beta smoothness, we know that D_{\phi}(x,y)\leq\frac{\beta}{2}||x-y||_{2}^{2}. On the other hand, for g_{\phi,y}(x)=D_{\phi}(x,y) , \nabla g_{\phi,y}(x)=\nabla\phi(x)-\nabla\phi(y), The unique minimizer of g_{\phi,y}(x) is x^{*}=y , with g_{\phi,y}(y)=0 . By strong convexity, we know that \left\langle\nabla\phi(x)-\nabla\phi(y),x-y\right\rangle\geq\alpha||x-y||_{2}^{2}; then, we have ||\nabla\phi(x)-\nabla\phi(y)||_{2}\geq\alpha||x-y||_{2}. Combining all these parts together, we have \displaystyle||\nabla_{1}D_{\phi}(x,y)||_{2}^{2}=||\nabla\phi(x)-\nabla\phi(y)||_{2}^{2}\geq\mu^{2}||x-y||_{2}^{2}\geq\frac{2\alpha^{2}}{\beta}D_{\phi}(x,y)=\frac{2\alpha^{2}}{\beta}(D_{\phi}(x,y)-D_{\phi}(x^{*},y)). Setting the constant to \frac{\alpha^{2}}{\beta} , we finish the proof. ∎ Proof of Proposition 3.4 . By the definition of \beta -smoothness and \alpha -strong convexity, we know that \frac{\alpha}{2}||x-y||_{2}^{2}\leq D_{\phi}(x,y)\leq\frac{\beta}{2}||x-y||_{2}^{2}. Therefore, we know that \frac{\sqrt{\alpha}}{\sqrt{2}}||x-y||_{2}\leq\sqrt{D_{\phi}(x,y)}\leq\frac{\sqrt{\beta}}{\sqrt{2}}||x-y||_{2} . Hence, by the fact that l=D_{\phi} , \sqrt{l(x,y)}\leq\sqrt{\frac{\beta}{\alpha}}\left(l(x,z)+l(z,y)\right). ∎ Proof of Proposition 3.8 . By definition, for the optimal predictor f^{*} , we have f^{*}(x_{i})=\mathop{\mathrm{argmin}}_{z}\mathbb{E}_{y_{i}}[D_{\phi}(y_{i},z)|x_{i}]. Computing the gradient of RHS, we have that \nabla_{z}\mathbb{E}_{y_{i}}[D_{\phi}(y_{i},z)|x_{i}]=\mathbb{E}_{y_{i}}[\nabla_{z}D_{\phi}(y_{i},z)|x_{i}]=\mathbb{E}_{y_{i}}[\nabla^{2}\phi(z)(z-y_{i})|x_{i}]=\nabla^{2}\phi(z)\mathbb{E}_{y_{i}}[(z-y_{i})|x_{i}]. Since \nabla^{2}\phi is a positive definite matrix, by the first-order condition, the optimal predictor is z^{*}_{i}=f^{*}(x_{i})=\mathbb{E}[y_{i}|x_{i}]. In the random design setting, the claim can be proved similarly by replacing x_{i} with any x\in\mathcal{X} . ∎ Appendix D Proofs in Section 5 D.1 Proof of Lemma 5.1 In this subsection, we prove the key Lemma 5.1 . Proof of Lemma 5.1 . Recall the definition that f^{\diamond}_{\rho}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{C}}\frac{1}{n}\sum_{i=1}^{n}l(y^{\diamond}_{i},f(x_{i})). By some algebra and a shell argument, we have that \displaystyle\frac{1}{n}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i})),\rho(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle \displaystyle\geq \displaystyle\min_{f\in\mathcal{C}}\left\{\frac{1}{n}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\rho(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle\right\} \displaystyle= \displaystyle\min_{r\geq 0}\min_{f\in\mathcal{C}(r)}\left\{r^{2}-\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\rho(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle\right\} \displaystyle= \displaystyle\min_{r\geq 0}\left\{r^{2}-\sup_{f\in\mathcal{C}(r)}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\rho(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle\right\} \displaystyle= \displaystyle\min_{r\geq 0}\left\{r^{2}-\rho W_{n}(r)\right\} On the other hand, by the first-order Taylor expansion, we know that for any f\in\mathcal{F} , \displaystyle l(y_{i}^{\diamond},f(x_{i}))+\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\rho\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle \displaystyle= \displaystyle l(\widehat{f}(x_{i}),f(x_{i}))+\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i}))-\nabla_{1}l(\widehat{f}(x_{i})-\theta_{i}\rho\varepsilon_{i}\odot\widetilde{w}_{i},f(x_{i})),\rho\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle \displaystyle= \displaystyle l(\widehat{f}(x_{i}),f(x_{i}))+\left\langle\nabla\phi(\widehat{f}(x_{i}))-\nabla\phi(\widehat{f}(x_{i})-\theta_{i}\rho\varepsilon_{i}\odot\widetilde{w}_{i}),\rho\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle \displaystyle\leq \displaystyle l(\widehat{f}(x_{i}),f(x_{i}))+\beta||\rho\varepsilon_{i}\odot\widetilde{w}_{i}||_{2}^{2}. In the last inequality, we use the \beta -smoothness of \phi . Rearranging, we have that l(\widehat{f}(x_{i}),f(x_{i}))-\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\rho\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle+\beta||\rho\varepsilon_{i}\odot\widetilde{w}_{i}||_{2}^{2}\geq l(y_{i}^{\diamond},f(x_{i})). Therefore, \frac{1}{n}\sum_{i=1}^{n}\left(l(\widehat{f}(x_{i}),f(x_{i}))-\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\rho\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle\right)\geq\frac{1}{n}\sum_{i=1}^{n}\left(l(y_{i}^{\diamond},f(x_{i}))-\beta||\rho\varepsilon_{i}\odot\widetilde{w}_{i}||_{2}^{2}\right). Now we take the minimization of both sides over f\in\mathcal{C} and notice that f^{\diamond}_{\rho}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{C}}\frac{1}{n}\sum_{i=1}^{n}l(y^{\diamond}_{i},f(x_{i})) . Then we have \displaystyle\frac{1}{n}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i}))-\rho W_{n}(\frac{1}{n}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i}))) \displaystyle\geq \displaystyle\min_{r\geq 0}\left\{r^{2}-\rho W_{n}(r)\right\} \displaystyle\geq \displaystyle\frac{1}{n}\sum_{i=1}^{n}l(y^{\diamond}_{i},f^{\diamond}_{\rho}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}\beta||\rho(\varepsilon_{i}\odot\widetilde{w}_{i})||^{2}_{2}. Therefore, we have W_{n}(\frac{1}{n}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}))\leq\frac{1}{n\rho}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i}))-\frac{1}{n\rho}\sum_{i=1}^{n}l(y^{\diamond}_{i},f^{\diamond}_{\rho}(x_{i}))+\frac{\beta\rho}{n}\sum_{i=1}^{n}||(\varepsilon_{i}\odot\widetilde{w}_{i})||^{2}_{2}. So we finish the proof. ∎ D.2 Proof of Theorem 5.2 In this subsection, we provide proofs about the main theoretical guarantee. Our proof relies on the following lemmas, whose proofs are deferred to Appendix F . We first illustrate our target. We are trying to bound \frac{1}{n}\sum_{i=1}^{n}l(f^{*}(x_{i}),\widehat{f}(x_{i})) . By the convexity regarding the first variable, we have \frac{1}{n}\sum_{i=1}^{n}l(f^{*}(x_{i}),\widehat{f}(x_{i}))\leq\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle, where we use the fact that the true data generating process is y_{i}=f^{*}(x_{i})+w_{i}. Therefore, we only need to bound the term |\text{Opt}^{*}(\widehat{f})| , where \text{Opt}^{*}(\widehat{f}):=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle. Recall the quantities that we have defined in Section 5 : W_{n}(r)=\sup_{f\in\mathcal{B}_{r}(\widehat{f})}\left\{\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),(\varepsilon_{i}\odot\widetilde{w}_{i})\right\rangle\right\}; (D.1) \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})=\frac{1}{n\rho}\sum_{i=1}^{n}l(\widehat{f}(x_{i}),f^{\diamond}_{\rho}(x_{i}))-\frac{1}{n\rho}\sum_{i=1}^{n}l(y^{\diamond}_{i},f^{\diamond}_{\rho}(x_{i}))+\frac{1}{n}\sum_{i=1}^{n}\beta\rho||(\varepsilon_{i}\odot\widetilde{w}_{i})||^{2}_{2}; (D.2) f^{\dagger}=\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\left\{\frac{1}{n}\sum_{i=1}^{n}l(f^{*}(x_{i}),f(x_{i}))+\mathcal{R}(f)\right\}; (D.3) \text{Opt}^{\dagger}(\widehat{f})=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle; (D.4) and Z_{n}^{\varepsilon}(r):=\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\left[\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle\right]. (D.5) When we say \mathcal{B}_{r}(f_{0}) , we mean that the average empirical loss \frac{1}{n}\sum_{i=1}^{n}l(f_{0}(x_{i}),f(x_{i}))\leq r . We abbreviate loss \frac{1}{n}\sum_{i=1}^{n}l(f_{1}(x_{i}),f_{2}(x_{i})) as L_{n}(f_{1},f_{2}) . Moreover, we should notice that Z_{n}^{\varepsilon}(r)\geq 0 since f^{\dagger}\in\mathcal{B}_{r}(f^{\dagger}) . Lemma D.1 . For any t>0 , we have that with probability at least 1-2e^{-t^{2}} , |\text{Opt}^{*}(\widehat{f})|\leq|\text{Opt}^{\dagger}(\widehat{f})|+\sqrt{L_{n}(f^{*},f^{\dagger})}\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}t}{\alpha\sqrt{n}}. Furthermore, for any r\geq\sqrt{L_{n}(f^{*},f^{\dagger})} , and any t>0 , we have that with probability at least 1-4e^{-t^{2}} , \max\left\{|\text{Opt}^{\dagger}(\widehat{f})|,Z_{n}^{\varepsilon}(r)\right\}\leq\mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)]+r\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}t}{\alpha\sqrt{n}}. By Lemma D.1 , we could see that if r\geq\sqrt{L_{n}(f^{\dagger},\widehat{f})} , we have the upper bound that with probability at least 1-6e^{-t^{2}} , |\text{Opt}^{*}(\widehat{f})|\leq\mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)]+\left(r+\sqrt{L_{n}(f^{*},f^{\dagger})}\right)\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}t}{\alpha\sqrt{n}}. Our next goal is to connect the term \mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)] with the term \widetilde{\text{Opt}}^{\diamond}(\widehat{f}) defined in Lemma 5.1 . In order to do so, we define the following non-negative intermediate empirical process: \widetilde{W}_{n}(r):=\sup_{f\in\mathcal{B}_{r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle. Remember that noiseless estimation error as \widehat{r}_{n}:=\sqrt{\frac{1}{n}\sum_{i=1}^{n}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))}=\sqrt{L_{n}(f^{\dagger},\widehat{f})} . We have the following lemma. Lemma D.2 . For any r\geq\widehat{r}_{n} , we have the bound \mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)]\leq\mathbb{E}_{\varepsilon}[\widetilde{W}_{n}((2\beta/\alpha)^{1/2}(r+\widehat{r}_{n}))]\leq\mathbb{E}_{\varepsilon}[\widetilde{W}_{n}(2(2\beta/\alpha)^{1/2}r)]. Also, for the intermediate empirical process \widetilde{W}_{n}(r) , we have the bound with probability at least 1-2e^{-t^{2}} for any r , \left|\mathbb{E}_{\varepsilon}[\widetilde{W}_{n}(r)]-\widetilde{W}_{n}(r)\right|\leq r\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}t}{\alpha\sqrt{n}}. With Lemma D.2 , we know that for r\geq\widehat{r}_{n} , we have that with probability at least 1-2e^{-t^{2}} , \mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)]\leq\widetilde{W}_{n}(3(\beta/\alpha)^{1/2}r)+r\frac{6||w||_{\infty}\beta^{2}\sqrt{d}t}{\alpha^{3/2}\sqrt{n}}. Therefore, combining all these parts together, we have shown that with probability at least 1-8e^{-t^{2}} , \displaystyle\text{Opt}^{*}(\widehat{f})\leq\widetilde{W}_{n}(3(\beta/\alpha)^{1/2}r)+\left\{\sqrt{L_{n}(f^{*},f^{\dagger})}+5r\right\}\frac{2||w||_{\infty}(\beta^{3/2}\vee\beta^{2})\sqrt{d}t}{(\alpha^{3/2}\wedge\alpha)\sqrt{n}}. Finally, we give our lemma about linking \widetilde{W}_{n}(2r) with \widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho}) , whose proof relies on the key Lemma 5.1 . Lemma D.3 . For any radius r , we have \widetilde{W}_{n}(3(\beta/\alpha)^{1/2}r)\leq\widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})+A_{n}(\widehat{f}), where f^{\diamond}_{\rho} is the wild solution with L_{n}(\widehat{f},f^{\diamond}_{\rho})=3(\beta/\alpha)^{1/2}r . Plugging the inequality in Lemma D.3 back, we have that with probability at least 1-8e^{-t^{2}} , \text{Opt}^{*}(\widehat{f})\leq\widetilde{\text{Opt}}^{\diamond}(f^{\diamond}_{\rho})+A_{n}(\widehat{f})+\left\{\sqrt{L_{n}(f^{*},f^{\dagger})}+5r\right\}\frac{2||w||_{\infty}(\beta^{3/2}\vee\beta^{2})\sqrt{d}t}{(\alpha^{3/2}\wedge\alpha)\sqrt{n}}. By a change of variable \delta\leftarrow e^{-t^{2}} , we therefore finish the proof of Theorem 5.2 . D.3 Proofs of Theorem 5.3 In this subsection, we provide the proof of Theorem 5.3 in Section 5.2 . To proceed, we first need the following concept regarding algorithm stability. Definition D.4 . ( Bousquet and Elisseeff 2002 ) We have a learning algorithm \mathcal{A} , a loss function l and a dataset \mathcal{D}=\left\{(x_{i},y_{i})\right\}_{i=1}^{n} . Define \mathcal{D}^{i} to be the dataset with (x_{i},y_{i}) removed, i.e., \mathcal{D}^{i}=\left\{(x_{j},y_{j})\right\}_{j=1j\neq i}^{n}=\mathcal{D}\setminus\left\{(x_{i},y_{i})\right\}. Denote h_{0} to be the predictor trained on \mathcal{D} and h_{i} to be the predictor trained on \mathcal{D}^{i} . If \forall\ i\in[n] , we have \mathbb{E}_{\mathcal{D}}\left[\left|l(y_{i},h_{0}(x_{i}))-l(y_{i},h_{i}(x_{i}))\right|\right]\leq r, then, we say that the learning algorithm \mathcal{A} satisfies pointwise hypothesis stability r . With this definition, we could derive the random design bound with some regularity conditions on the loss function. First, recall that \phi is \alpha -strongly convex. Therefore, D_{\phi}(\cdot,\cdot) is also strongly convex with respect to the first variable. Therefore, the function T_{n}:(\mathbb{R}^{d})^{\otimes n}\mapsto\mathbb{R} such that T_{n}(g):=\frac{1}{n}\sum_{i=1}^{n}l(y_{i},g_{i}) is \alpha -strongly convex. Therefore, T_{n}(g) satisfies the Polyak–Łojasiewicz inequality with parameter \alpha>0 . Moreover, by the condition of Theorem 5.3 , ||\nabla\phi||\leq L , therefore T_{n}(g) is Lipschitz-continuous with constant L . We turn to our algorithm. \texttt{Alg}_{\mathsf{Erm}} outputs a predictor \widehat{f} such that \widehat{f}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{F}}\left\{\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f(x_{i}))+\mathcal{R}(f)\right\}. If we write f\in\mathcal{C} to abbreviate f(x_{i})\in\mathcal{C},\ \forall\ i=1,\cdots,n , then we equivalently write \widehat{f} to be \widehat{f}\in\mathop{\mathrm{argmin}}_{f\in\mathcal{C}}\left\{\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f(x_{i}))\right\}. Therefore, by Lemma B.7 , we know that the \texttt{Alg}_{\mathsf{Erm}} satisfies pointwise hypothesis stability Definition D.4 with constant \epsilon_{sta}=\frac{2L^{2}}{\alpha(n-1)} . Then, we apply Lemma B.6 to get that for any \delta>0 , with probability 1-\delta , we have \mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]\leq\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))+\sqrt{\frac{M^{2}+12Mn\epsilon_{sta}}{2n\delta}}. Return to bounding the expected excess risk, by definition, we have \displaystyle\mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]-\mathbb{E}_{X,Y}[l(Y,f^{*}(X))] \displaystyle= \displaystyle\left(\mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]-\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))\right)+\left(\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))-\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f^{*}(x_{i}))\right) \displaystyle+\left(\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f^{*}(x_{i}))-\mathbb{E}_{X,Y}[l(Y,f^{*}(X))]\right) \displaystyle=\left(\mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]-\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))\right)+\mathcal{E}_{\mathcal{D}}(\widehat{f})+\left(\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f^{*}(x_{i}))-\mathbb{E}_{X,Y}[l(Y,f^{*}(X))]\right). We have already bound the second term in Theorem 5.2 . Therefore, we only need to bound the remaining two terms. Applying the inequality above, we have that with probability at least 1-\delta , \displaystyle\mathbb{E}_{X,Y}[l(Y,\widehat{f}(X))]-\frac{1}{n}\sum_{i=1}^{n}l(y_{i},\widehat{f}(x_{i}))\leq\sqrt{\frac{M^{2}+12Mn\epsilon_{sta}}{2n\delta}}=\sqrt{\frac{M^{2}+12Mn\frac{2L^{2}}{\alpha(n-1)}}{2n\delta}}=\sqrt{\frac{M^{2}+36ML^{2}/\alpha}{2n\delta}}. For the third term, remember that f^{*} is some unknown fixed function; therefore, we could apply the Hoeffding Lemma B.3 with bounded random variables to get that with probability at least 1-2\delta , \left|\frac{1}{n}\sum_{i=1}^{n}l(y_{i},f^{*}(x_{i}))-\mathbb{E}_{X,Y}[l(Y,f^{*}(X))]\right|\leq M\sqrt{\frac{\log(2/\delta)}{2n}}. Combining these two inequalities with Theorem 5.2 , we shall finish the proof. Appendix E Proof in Section 6 In this section, we prove Theorem 6.2 . We first introduce the following three lemmas. Their proofs are deferred to Appendix G . Lemma E.1 . Given the procedure \texttt{Alg}_{\mathsf{Erm}} that is \phi -non-expansive around f^{*} , if \widehat{r}_{n}=\sqrt{L_{n}(f^{\dagger},\widehat{f})} , then we have \widehat{r}_{n}^{2}\leq Z_{n}(\widehat{r}_{n}), where Z_{n}(r):r\mapsto\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\left[\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i})),w_{i}\right\rangle\right] is an empirical process. The random variable Z_{n}(r) could be viewed as a realization of Z_{n}^{\varepsilon}(r) since we assume that the distribution of the noise is coordinate-wise symmetric and that the Hadamard product between two Rademacher random variables is still Rademacher. Then, we have the following second lemma. Lemma E.2 . For any t\geq 3 , with probability at least 1-2e^{-t^{2}} , Z_{n}(r)\leq\mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(1+\frac{1}{t})r]+r^{2}\frac{4||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}, uniformly for r\geq\frac{t^{2}}{\sqrt{n}} . We now proceed with our proof about Theorem 6.2 . Fixing any t\geq 3 , we either have \widehat{r}_{n}\leq\frac{t^{2}}{\sqrt{n}} where our claim already holds, or we have \widehat{r}_{n}>\frac{t^{2}}{\sqrt{n}} . Under the latter case, by Lemma E.1 and Lemma E.2 , we have \widehat{r}_{n}^{2}\leq Z_{n}(\widehat{r}_{n})\leq\mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(1+\frac{1}{t})\widehat{r}_{n}]+\frac{4||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}\widehat{r}_{n}^{2}. We apply the first claim from Lemma D.2 to get \widehat{r}_{n}^{2}\leq\mathbb{E}_{\varepsilon}\left[\widetilde{W}_{n}\left((2+\frac{1}{t})\widehat{r}_{n}\right)\right]+\frac{4||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}\widehat{r}_{n}^{2}. Moreover, by the second claim of Lemma D.2 , setting s=\frac{\widehat{r}_{n}\sqrt{n}}{t} , we have that with probability at least 1-2e^{-s^{2}} , \mathbb{E}_{\varepsilon}\left[\widetilde{W}_{n}(2+\frac{1}{t})\widehat{r}_{n}\right]\leq\widetilde{W}_{n}\left((2+\frac{1}{t})\widehat{r}_{n}\right)+\widehat{r}_{n}^{2}\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}. By some algebra, s^{2}=\frac{\widehat{r}_{n}^{2}n}{t^{2}}\geq t^{2} , where we use the assumption that \widehat{r}_{n}\geq\frac{s^{2}}{\sqrt{n}} . Consequently, with probability at least 1-2e^{-t^{2}} , \mathbb{E}_{\varepsilon}[\widetilde{W}_{n}(\left((2+1/t)\right)\widehat{r}_{n})]\leq\widetilde{W}_{n}((2+\frac{1}{t})\widehat{r}_{n})+\widehat{r}_{n}^{2}\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}. Combining these two parts together, with probability at least 1-4e^{-t^{2}} , \widehat{r}_{n}^{2}\leq\widetilde{W}_{n}((2+\frac{1}{t})\widehat{r}_{n})+\widehat{r}_{n}^{2}\frac{6||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}\leq W_{n}((2+1/t)\widehat{r}_{n})+\widehat{r}_{n}^{2}\frac{6||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}+A_{n}(\widehat{f}). The last inequality follows from the proof of Lemma D.3 . Combining the additional term of the case where \widehat{r}_{n}\leq\frac{t^{2}}{\sqrt{n}} , we finish the proof of the first claim. To prove the second claim, we first require the following lemma. Lemma E.3 . For any v\geq u>0 , when C_{0}=\sqrt{\beta/\alpha} , we have that \frac{W_{n}(v)}{v}\leq\frac{W_{n}(C_{0}u)}{u}. Now we prove the second bound of Theorem 6.2 . We either have \widehat{r}_{n}\leq r^{\diamond}_{\rho} or \widehat{r}_{n}>r^{\diamond}_{\rho} . In the latter case, we write \displaystyle W_{n}([2+1/t]\widehat{r}_{n})=[2+1/t]\widehat{r}_{n}\frac{W_{n}([2+1/t]\widehat{r}_{n})}{[2+1/t]\widehat{r}_{n}}\leq[2+1/t]\widehat{r}_{n}\frac{W_{n}(C_{0}[2+1/t]r^{\diamond}_{\rho})}{[2+1/t]r^{\diamond}_{\rho}}=\widehat{r}_{n}\frac{W_{n}(C_{0}[2+1/t]r^{\diamond}_{\rho})}{r^{\diamond}_{\rho}}. Plugging this back to the first claim of Theorem 6.2 and applying the change of variable \delta\leftarrow e^{-t^{2}} , we shall finish the proof. Appendix F Proofs in Section D.2 Proof of Lemma D.1 . By some algebra, we have that \displaystyle\text{Opt}^{*}(\widehat{f}) \displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{*}(x_{i})-f^{\dagger}(x_{i})+f^{\dagger}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle \displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle+\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right),w_{i}\right\rangle \displaystyle=\text{Opt}^{\dagger}(\widehat{f})+\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right),w_{i}\right\rangle. Now we analyze the term \frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right),w_{i}\right\rangle . We assume that w_{i}\in\mathbb{R}^{d} and every coordinate of w_{i} has an independent symmetric distribution, i.e., w_{ij}=\varepsilon_{ij}|w_{ij}|,\ w_{ij}\perp w_{ik},\ \forall\ i=1,\cdots,n;\ j,k=1,\cdots,d. We denote \bar{w}_{i} as the amplitude vector (|w_{i1}|,\cdots,|w_{id}|) , and \varepsilon_{i} as the random vector (\varepsilon_{i1},\cdots,\varepsilon_{id}) . Hence, we have that w_{i}=\varepsilon_{i}\odot\bar{w}_{i} . Moreover, we assume that the compact set \mathcal{C} has diameter D_{0} . By definition and the property of the Hadamard product, we have \displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right),w_{i}\right\rangle \displaystyle= \displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right),\varepsilon_{i}\odot\bar{w}_{i}\right\rangle \displaystyle= \displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right)\odot\bar{w}_{i},\varepsilon_{i}\right\rangle Conditioning on the amplitude vector \bar{w}_{i} , we define the function, (\varepsilon_{1},\cdots,\varepsilon_{n})\mapsto G(\varepsilon):=\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right)\odot\bar{w}_{i},\varepsilon_{i}\right\rangle, Then we have that, \displaystyle\left|G(\varepsilon)-G(\varepsilon^{\prime})\right| \displaystyle=\left|\frac{1}{n}\sum_{i=1}^{n}\left\langle\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right)\odot\bar{w}_{i},(\varepsilon_{i}-\varepsilon_{i}^{\prime})\right\rangle\right| \displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}||\left(\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))\right)\odot\bar{w}_{i}||_{2}||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2} \displaystyle\leq\frac{\sqrt{d}}{n}\sum_{i=1}^{n}||\bar{w}_{i}||_{\infty}||\nabla_{1}l(f^{*}(x_{i}),\widehat{f}(x_{i}))-\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i}))||_{2}||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2} \displaystyle\leq\frac{\sqrt{d}}{n}\sum_{i=1}^{n}||\bar{w}_{i}||_{\infty}\beta||f^{*}(x_{i})-f^{\dagger}(x_{i})||_{2}||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2} \displaystyle\leq\frac{||w||_{\infty}\sqrt{d}\beta}{n}\left(\sum_{i=1}^{n}||f^{*}(x_{i})-f^{\dagger}(x_{i})||_{2}^{2}\right)^{1/2}\left(\sum_{i=1}^{n}||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2}^{2}\right)^{1/2} Notice that (\sum_{i=1}^{n}||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2}^{2})^{1/2}=||\varepsilon-\varepsilon^{\prime}||_{F} . And now we focus on the coefficient term. By Proposition 3.3 and Lemma B.2 , we know that \displaystyle\sum_{i=1}^{n}||f^{*}(x_{i})-f^{\dagger}(x_{i})||_{2}^{2}\leq \displaystyle\sum_{i=1}^{n}\frac{2\beta}{\alpha^{2}}(D_{\phi}(f^{*}(x_{i}),f^{\dagger}(x_{i}))-D_{\phi}(f^{\dagger}(x_{i}),f^{\dagger}(x_{i}))) \displaystyle= \displaystyle\frac{2\beta}{\alpha^{2}}\sum_{i=1}^{n}D_{\phi}(f^{*}(x_{i}),f^{\dagger}(x_{i})). Therefore, we have that \left(\sum_{i=1}^{n}||f^{*}(x_{i})-f^{\dagger}(x_{i})||_{2}^{2}\right)^{1/2}\leq\frac{\sqrt{2\beta}}{\alpha}\left(\sum_{i=1}^{n}D_{\phi}(f^{*}(x_{i}),f^{\dagger}(x_{i}))\right)^{1/2}=\frac{\sqrt{2\beta}}{\alpha}\sqrt{n}\sqrt{L_{n}(f^{*},f^{\dagger})}. Plugging this back, we have that G(\varepsilon) is L -Lipschitz with constant \frac{\sqrt{2}||w||_{\infty}\beta^{3/2}d^{1/2}}{\alpha\sqrt{n}}\sqrt{L_{n}(f^{*},f^{\dagger})} . Then, we could apply Lemma B.4 to get that with probability at least 1-2e^{-t^{2}} , |G(\varepsilon)|\leq\sqrt{2}\frac{\sqrt{2}||w||_{\infty}\beta^{3/2}d^{1/2}}{\alpha\sqrt{n}}\sqrt{L_{n}(f^{*},f^{\dagger})}t=\frac{2||w||_{\infty}\beta^{3/2}t}{\alpha\sqrt{n}}\sqrt{L_{n}(f^{*},f^{\dagger})}. Now, for any r\geq\sqrt{L_{n}(f^{\dagger},f^{*})} , and any t>0 , we define the empirical process, conditioning on the amplitude vectors \left\{\bar{w}_{i}\right\}_{i=1}^{n} , H(\varepsilon):=Z_{n}^{\varepsilon}(r)=\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i})),\varepsilon_{i}\odot\bar{w}_{i}\right\rangle=\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i}))\odot\bar{w}_{i},\varepsilon_{i}\right\rangle. We show that H(\cdot) is also Lipschitz. \displaystyle H(\varepsilon)-H(\varepsilon^{\prime}) \displaystyle\leq \displaystyle\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i}))\odot\bar{w}_{i},\varepsilon_{i}-\varepsilon_{i}^{\prime}\right\rangle \displaystyle= \displaystyle||w||_{\infty}\sqrt{d}\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i}),\varepsilon_{i}-\varepsilon_{i}^{\prime}\right\rangle \displaystyle\leq \displaystyle||w||_{\infty}\sqrt{d}\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}\sum_{i=1}^{n}\left(||\nabla_{1}l(f(x_{i}),f(x_{i}))||_{2}+||\nabla_{1}l(f^{\dagger}(x_{i}),f(x_{i}))-\nabla_{1}l(f(x_{i}),f(x_{i}))||_{2}\right)\cdot||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2} \displaystyle\leq \displaystyle||w||_{\infty}\sqrt{d}\beta\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}\sum_{i=1}^{n}||f^{\dagger}(x_{i})-f(x_{i})||_{2}\cdot||\varepsilon_{i}-\varepsilon_{i}^{\prime}||_{2} \displaystyle\leq \displaystyle||w||_{\infty}\sqrt{d}\beta\sup_{f\in\mathcal{B}_{r}(f^{\dagger})}\frac{1}{n}(\sum_{i=1}^{n}||f^{\dagger}(x_{i})-f(x_{i})||_{2}^{2})^{1/2}\cdot||\varepsilon-\varepsilon^{\prime}||_{F}. By reversing the role of \varepsilon and \varepsilon^{\prime} , we know that H is Lipschitz. Then by the same argument, we know that the Lipschitz constant is \frac{\sqrt{2}||w||_{\infty}\sqrt{d}r}{\alpha\sqrt{n}} , thus with probability at least 1-2e^{-t^{2}} , \left|H(\varepsilon)-\mathbb{E}_{\varepsilon}[H(\varepsilon)]\right|\leq\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}t}{\alpha\sqrt{n}}r. Plugging this back and notice that when r\geq\sqrt{L_{n}(f^{\dagger},f^{*})} , we have \widehat{f}\in\mathcal{B}_{r}(f^{\dagger}) , we shall finish the proof. ∎ Proof of Lemma D.2 . Recall the definition of Z_{n}^{\varepsilon}(r) , let g be any function that achieves the supremum. Then, \displaystyle Z_{n}^{\varepsilon}(r) \displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),g(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle \displaystyle= \displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),g(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle+\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),g(x_{i}))-\nabla_{1}l(\widehat{f}(x_{i}),g(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle Taking the expectation on both sides, we analyze these two terms one by one. For the second term, we have that the expectation is 0 because we could condition on w_{i} and use the linearity of inner product and expectation to swap the order. The expectation of \varepsilon_{i} is 0 . For the first one, by the condition r\geq\widehat{r}_{n}=\sqrt{L_{n}(f^{\dagger},\widehat{f})} and Lemma B.5 , we have that L_{n}(g,\widehat{f})\leq\sqrt{\frac{2\beta}{\alpha}}\left(L_{n}(g,f^{\dagger})+L_{n}(f^{\dagger},\widehat{f})\right)\leq\sqrt{\frac{2\beta}{\alpha}}(r+\widehat{r}_{n})\leq 2\sqrt{\frac{2\beta}{\alpha}}r. This is by the fact that g\in\mathcal{B}_{r}(f^{\dagger}) and r\geq\widehat{r}_{n} . Then denoting c_{1} to be \sqrt{\frac{2\beta}{\alpha}} , we have \displaystyle\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),g(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle \displaystyle\leq\sup_{f\in\mathcal{B}_{c_{1}(r+\widehat{r}_{n})}(\widehat{f})}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle \displaystyle\leq\sup_{f\in\mathcal{B}_{2c_{1}r}(\widehat{f})}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle. Then we get the first bound of the lemma. \mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)]\leq\mathbb{E}_{\varepsilon}[\widetilde{W}_{n}(c_{1}(r+\widehat{r}_{n})]\leq\mathbb{E}_{\varepsilon}[\widetilde{W}_{n}(2c_{1}r)]. Moreover, similar to the process of analyzing G(\varepsilon) and H(\varepsilon) , we have that with probability at least 1-2e^{-t^{2}} , |\mathbb{E}_{\varepsilon}[\widetilde{W}_{n}(r)]-\widetilde{W}_{n}(r)|\leq r\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}t}{\alpha\sqrt{n}}. So we finish the proof. ∎ Proof of Lemma D.3 . By the definition of the wild noise \widetilde{w}_{i}=y_{i}-\widehat{f}(x_{i}) , we have that \varepsilon_{i}\odot w_{i}=\varepsilon_{i}\odot\widetilde{w}_{i}+\varepsilon_{i}\odot(\widehat{f}(x_{i})-f^{*}(x_{i})). Therefore, we have that \displaystyle\widetilde{W}_{n}(3(\beta/\alpha)^{1/2}r)= \displaystyle\sup_{f\in\mathcal{B}_{3(\beta/\alpha)^{1/2}r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot w_{i}\right\rangle \displaystyle= \displaystyle\sup_{f\in\mathcal{B}_{3(\beta/\alpha)^{1/2}r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot\widetilde{w}_{i}+\varepsilon_{i}\odot(\widehat{f}(x_{i})-f^{*}(x_{i}))\right\rangle \displaystyle\leq \displaystyle\sup_{f\in\mathcal{B}_{3(\beta/\alpha)^{1/2}r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle \displaystyle+ \displaystyle\sup_{f\in\mathcal{B}_{3(\beta/\alpha)^{1/2}r}(\widehat{f})}\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(\widehat{f}(x_{i}),f(x_{i})),\varepsilon_{i}\odot(\widehat{f}(x_{i})-f^{*}(x_{i}))\right\rangle \displaystyle= \displaystyle W_{n}(3(\beta/\alpha)^{1/2}r)+A_{n}(\widehat{f}). Finally, by Lemma 5.1 , we have that W_{n}(3(\beta/\alpha)^{1/2}r)\leq\widetilde{\text{Opt}}(f^{\diamond}_{\rho}) for the wild solution such that L_{n}(\widehat{f},f^{\diamond}_{\rho})=3(\beta/\alpha)^{1/2}r . ∎ Appendix G Proof of Appendix E Proof of Lemma E.1 . By definition 6.1 , we have that \displaystyle\widehat{r}_{n}^{2}=L_{n}(f^{\dagger},\widehat{f})\leq\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla_{1}l(f^{\dagger}(x_{i}),\widehat{f}(x_{i})),w_{i}\right\rangle\leq Z_{n}(\widehat{r}_{n}). So we finish the proof. ∎ Proof of Lemma E.2 . Recall the argument in the proof of Lemma D.1 such that Z_{n}^{\varepsilon}(r) is Lipschitz continuous in \varepsilon with constant \frac{\sqrt{2}||w||_{\infty}\sqrt{d}r}{\alpha\sqrt{n}} . Then, by Lemma B.4 , we have that for any t>0 , \mathbb{P}\left(Z_{n}(r))\geq\mathbb{E}_{\varepsilon}[Z_{n}^{\varepsilon}(r)]+r^{2}\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}\right)\leq 4e^{-\frac{nr^{2}}{t^{2}}}\leq e^{-t^{2}},\ r\geq t^{2}/\sqrt{n}. We define \mathcal{G} to be the event that this inequality is violated for some r\geq\frac{t^{2}}{\sqrt{n}} . Our method is a peeling argument, which could also be found in the proofs in other papers ( Xia and Wainwright 2024 ; Hu and Simchi-Levi 2025 ) . Specifically, we define the event: \mathcal{G}_{m}:=\left\{\exists r\in[(1+\frac{1}{t})^{m}\frac{t^{2}}{\sqrt{n}},(1+\frac{1}{t})^{m+1}\frac{t^{2}}{\sqrt{n}}),\ \text{the bound is violated}\right\}. Now, we provide an upper bound of \mathbb{P}(\mathcal{G}_{m}) . If the event \mathcal{G}_{m} is true, we denote p_{m} to be (1+\frac{1}{t})^{m}\frac{t^{2}}{\sqrt{n}} and then have that \displaystyle Z_{n}(p_{m+1})\geq Z_{n}(r) \displaystyle\geq\mathbb{E}_{\varepsilon}[Z_{n}((1+\frac{1}{t})r)]+r^{2}\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t} \displaystyle\geq\mathbb{E}_{\varepsilon}[Z_{n}(p_{m+1})]+p_{m}^{2}\frac{2||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t} \displaystyle\geq\mathbb{E}_{\varepsilon}[Z_{n}(p_{m+1})]+p_{m+1}^{2}\frac{||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}. Therefore, applying the same argument about Z_{n}^{\varepsilon}(r) in the proof of Lemma D.1 to get: \mathbb{P}\left(\mathcal{G}_{m}\right)\leq\mathbb{P}\left(Z_{n}(p_{m+1})\geq\mathbb{E}_{\varepsilon}[Z_{n}(p_{m+1})]+p_{m+1}^{2}\frac{||w||_{\infty}\beta^{3/2}\sqrt{d}}{\alpha t}\right)\leq 2e^{-\frac{n}{t^{2}}p_{m+1}^{2}}. Finally, by a union bound over m=0,1,\cdots, we have \mathbb{P}(\mathcal{G})=\mathbb{P}(\cup_{m=1}^{\infty}\mathcal{G}_{m})\leq\sum_{m=0}^{\infty}\mathbb{P}(\mathcal{G}_{m})\leq 2\sum_{m=0}^{\infty}e^{-\frac{n}{t^{2}}p_{m+1}^{2}}\leq 2e^{-s^{2}}. So we finish the proof. ∎ Proof of Lemma E.3 . For any s\geq t>0 denoting g_{s} and g_{t} as the functions in the definition of W_{n}(\cdot) that achieve the maxima of W_{n}(s) and W_{n}(t) . For any fixed a\in[0,1] , we set r:=as+(1-a)t and define g_{r}:=ag_{s}+(1-a)g_{t} . By the convexity of \mathcal{F} , g_{r}\in\mathcal{F} . Then we have \displaystyle\sqrt{L_{n}(\widehat{f},ag_{s}+(1-a)g_{t})} \displaystyle\leq \displaystyle\sqrt{\beta\frac{1}{n}\sum_{i=1}^{n}\left(\widehat{f}(x_{i})-(ag_{s}+(1-a)g_{t}(x_{i}))\right)^{2}} \displaystyle= \displaystyle\sqrt{\beta}\left(a||\widehat{f}-g_{s}||_{n}+(1-a)||\widehat{f}-g_{t}||_{n}\right) \displaystyle\leq \displaystyle\sqrt{\frac{\beta}{\alpha}}\left(a\sqrt{L_{n}(\widehat{f},g_{s})}+\sqrt{L_{n}(\widehat{f},g_{t})}\right) \displaystyle= \displaystyle\sqrt{\frac{\beta}{\alpha}}(as+(1-a)t) \displaystyle= \displaystyle\sqrt{\frac{\beta}{\alpha}}r. Consequently, g_{r} is feasible for the supremum in W_{n}(\sqrt{\frac{\beta}{\alpha}}r) , so we have \displaystyle aW_{n}(s)+(1-a)W_{n}(t) \displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left\langle\nabla\phi(\widehat{f}(x_{i}))-\left(a\nabla\phi(g_{s}(x_{i}))+(1-a)\nabla\phi(g_{t}(x_{i}))\right),\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle \displaystyle\leq \displaystyle\sup_{\mathcal{B}_{(\beta/\alpha)^{1/2}r}(\widehat{f})}\left\langle\nabla\phi(\widehat{f}(x_{i}))-\nabla\phi(f(x_{i})),\varepsilon_{i}\odot\widetilde{w}_{i}\right\rangle \displaystyle= \displaystyle W_{n}((\beta/\alpha)^{1/2}r). In brief, we have proved that aW_{n}(s)+(1-a)W_{n}(t)\leq W_{n}((\beta/\alpha)^{1/2}(as+(1-a)t)) , \forall\ a\in[0,1] . Notice that W_{n}(0)=0 , and denote (\beta/\alpha)^{1/2} as C_{0} . Then, for any 0