This guide provides a reference for high-probability regret bounds in empirical risk minimization (ERM). The presentation is modular: we begin with intuition and general proof strategies, then state broadly applicable guarantees under high-level conditions and provide tools for verifying them for specific losses and function classes. We emphasize that many ERM rate derivations can be organized around a three-step recipe -- a basic inequality, a uniform local concentration bound, and a fixed-point argument -- which yields regret bounds in terms of a critical radius, defined via localized Rademacher complexity, under a mild Bernstein-type variance-risk condition. To make these bounds concrete, we upper bound the critical radius using local maximal inequalities and metric-entropy integrals, thereby recovering familiar rates for VC-subgraph, Sobolev/Hölder, and bounded-variation classes. We also study ERM with nuisance components -- including weighted ERM and Neyman-orthogonal losses -- as they arise in causal inference, missing data, and domain adaptation. Following the orthogonal statistical learning framework, we highlight that these problems often admit regret-transfer bounds linking regret under an estimated loss to population regret under the target loss. These bounds typically decompose the regret into (i) statistical error under the estimated loss and (ii) approximation error due to nuisance estimation. Under sample splitting or cross-fitting, the first term can be controlled using standard fixed-loss ERM regret bounds, while the second depends only on nuisance-estimation accuracy. As a novel contribution, we also treat the in-sample regime, in which the nuisances and the ERM are fit on the same data, deriving regret bounds and showing that fast oracle rates remain attainable under suitable smoothness and Donsker-type conditions.
Figures & tables
Function class G
Local scaling
Critical radius δn
Star hull of single function star({f})
n−1/2δ
n−1/2
s -sparse linear predictors in Rp
n−1/2δslog(ep/s)
slog(ep/s)/n
VC-subgraph of dimension V
n−1/2δVlog(1/δ)
Vlog(n/V)/n
Hölder/Sobolev with smoothness s in dimension d<2s
n−1/2δ1−d/(2s)
n−s/(2s+d)
Bounded Hardy–Krause variation
n−1/2δ1/2(log(1/δ))d−1
n−1/3(logn)2(d−1)/3
RKHS with eigenvalue decay σj≍j−2α,α>1/2
n−1/2δ1−1/(2α)
n−α/(2α+1)
Table 1: Examples of localized Rademacher complexity scalings Rn(G,δ) and critical radii δn for common function classes. The reported local complexities are upper bounds, and the displayed scaling may hold only for δ larger than the critical radius δn . See Appendix A.1 for references.
Function class G
Entropy bound
Hölder/Sobolev (smoothness s>d/2 in dimension d )
J∞(δ,G)≲δ1−d/2s ;
Monotone functions on [0,1]
J2(δ,G)≲δ1/2
Bounded Hardy–Krause variation (dimension d )
J2(δ,G)≲δ1/2{log(1/δ)}d−1
s -sparse linear predictors in Rp (support size ≤s )
J2(δ,G)≲δslog(ep/(sδ))
VC-subgraph (VC dimension V )
J2(δ,G)≲δVlog(1/δ)
Table 2: Examples of uniform entropy bounds for common function classes.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Function class G
Critical radius δn
Reference
Star hull of single function star({f})
n−1/2
Wainwright (2019)
s -sparse linear predictors in Rp
slog(ep/s)/n
Wainwright (2019)
VC-subgraph of dimension V
Vlog(n/V)/n
Van Der Vaart and Wellner (1996)
Hölder/Sobolev with smoothness s in dimension d
n−s/(2s+d)
Nickl and Pötscher (2007)
Bounded Hardy–Krause variation
n−1/3(logn)2(d−1)/3
Bibaut and van der Laan (2019)
RKHS with eigenvalue decay σj≍j−2α,α>1/2
n−α/(2α+1)
Mendelson and Neeman (2010)
Appendix
Table 3: Examples of critical radii for common function classes.
We derive the asymptotic risk function of regularized empirical risk minimization (ERM) estimators tuned by n-fold cross-validation (CV). The out-of-sample prediction loss of such estimators converges in distribution to the squared-error loss (risk function) of shrinkage estimators in the normal means model, tuned by Stein's unbiased risk estimate (SURE). This risk function provides a more fine-grained picture of predictive performance than uniform bounds on worst-case regret, which are common in learning theory: it quantifies how risk varies with the true parameter. As key intermediate steps, we show that (i) n-fold CV converges uniformly to SURE, and (ii) while SURE typically has multiple local minima, its global minimum is generically well separated. Well-separation ensures that uniform convergence of CV to SURE translates into convergence of the tuning parameter chosen by CV to that chosen by SURE.
Karun Adusumilli, Maximilian Kasy, Ashia Wilson
Department of Economics, University of Pennsylvania. · Department of Economics, University of Oxford. · Department of Electrical Engineering and Computer Science, MIT.
In this paper we prove some concentration inequalities for two types of error probabilities in the Empirical Risk Principle (ERP) in statistical learning, which provide a lower bound and an upper bound for the minimal risk (in terms of the minimal empirical risk) with non-asymptotic high confidence. The usual boundedness condition of the empirical risk function is relaxed to the Gaussian or exponential integrability condition. The confidence of the lower bound of the minimal risk is shown to be independent of the number of training parameters and the dimension of the input vectors, allowing one to detect the deficiency of a learning machine efficiently; and the confidence of the upper bound of the minimal risk is proved to be high provided that the sample size n is much greater than the box dimension of the parameter set Θ in the Orlicz metric dψ1 associated with the risk functions. Our work is based on Talagrand's concentration inequalities (the sharp versions by Bousquet and Klein-Rio), transport-entropy inequalities and the recent progress in the theory of empirical processes and statistical learning.
Liming Wu, Sen Yang
Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont Auvergne · IASM, Harbin Institute of Technology
While globally optimal empirical risk minimization (ERM) decision trees have become computationally feasible and empirically successful, rigorous theoretical guarantees for their statistical performance remain limited. In this work, we develop a comprehensive statistical theory for ERM trees under random design in both high-dimensional regression and classification. We first establish sharp oracle inequalities that bound the excess risk of the ERM estimator relative to the best possible approximation achievable by any tree with at most L leaves, thereby characterizing the interpretability-accuracy trade-off. We derive these results using a novel uniform concentration framework based on empirically localized Rademacher complexity. Furthermore, we derive minimax optimal rates over a novel function class: the piecewise sparse heterogeneous anisotropic Besov (PSHAB) space. This space explicitly captures three key structural features encountered in practice: sparsity, anisotropic smoothness, and spatial heterogeneity. While our main results are established under sub-Gaussianity, we also provide robust guarantees that hold under heavy-tailed noise settings. Together, these findings provide a principled foundation for the optimality of ERM trees and introduce empirical process tools broadly applicable to other highly adaptive, data-driven procedures.
Zineng Xu, Subhro Ghosh, Yan Shuo Tan
Department of Statistics and Data Science, National University of Singapore · Department of Mathematics, National University of Singapore