NON-ASYMPTOTIC ESTIMATES OF THE MINIMAL RISK IN STATISTICAL LEARNING

In statistical learning, the Empirical Risk Principle (ERP) aims to approximate the theoretical minimal risk by minimizing empirical risk over a parameter set. While asymptotic results like the Law of Large Numbers are well-understood, modern machine learning models—often featuring massive parameter counts and high-dimensional inputs—require non-asymptotic bounds that do not rely on the assumption that the sample size $n$ is infinite. This paper addresses the need for quantitative, non-asymptotic estimates of the deviation between the minimal empirical risk and the true minimal risk.

To move beyond classical bounds that often assume bounded risk functions, the authors utilize Talagrand’s concentration inequalities (specifically the sharp versions by Bousquet and Klein-Rio) and transport-entropy inequalities. They relax the standard boundedness condition to allow for Gaussian or exponential integrability, which is essential for handling common scenarios like log-likelihood estimation or regression with unbounded noise. The authors employ a risk-level localization (peeling argument) to derive upper bounds on the error probabilities, replacing traditional VC dimension measures with distribution-dependent metric entropy.

The paper establishes two primary results. First, it provides a dimension-free Bernstein-type concentration inequality for the lower bound of the minimal risk. This allows researchers to verify the deficiency of a learning machine using a sample size $n$ that is independent of the number of parameters $N$ and the input dimension $d$. Second, it provides an upper bound for the minimal risk, ensuring the efficiency of the learning machine, provided the sample size $n$ is sufficiently large relative to the box dimension of the parameter set in the Orlicz metric $d_{\psi_1}$. These results provide a rigorous framework for understanding generalization in settings where classical VC-dimension bounds may be uninformative.