# Are there any non-asymptotic bounds for the minimum empirical risk vs theoretical risk?

I'm trying to see if there's any bounds on the difference between $f_{ERM}$ and $f^{*}$. For now, define $\mathcal{F}$ to be a function class.

Let $P$ be a probability measure and $\hat{P_n}$ be the empirical measure on a set $S\subset \mathbb{R}^2$.

Let $$f^{*} = \arg \min_{f\in \mathcal{F}} R_P(f)$$ and

$$\hat{f^{*}} = \arg \min_{f\in \mathcal{F}} R_{\hat{P_n}}(f)$$ where $R_P$ denotes the classification risk with respect to the measure $P$ (and similarly for $\hat{P_n}$). So $R_P(f)=E_{(x,y)\sim P}[L(f(x),y)]$ and $R_\hat{P_n}(f)=\frac{1}{n}\sum_{i=1}^n L(f(x_i),y_i)$ where $x_i,y_i$ are iid samples drawn from distribution $P$.

Is there anything we know about $\| R_{\hat{P_n}} (\hat{f^{*}}) - R_{P}(f^{*}) \|$?

I thought this was related to ERM stability bounds except those bounds are for $\| R_{P} (\hat{f^{*}}) - R_{P}(f^{*}) \|$

• This seems like a straightforward application of the triangle inequality and a uniform LLN argument. But maybe I missed something... – JohnA Jul 6 '18 at 17:08