# Does a generalization bound that holds with high probability imply a bound that holds in expectation?

I am interested in generalization bounds, for example PAC bounds (Probably Approximately Correct). In particular, I wonder if a high probability bound implies a bound in expectation (or vice versa).

For example, a PAC bound may say that with probability $$1-\delta$$ (with respect to the sample $$S_n$$), a learning algorithm $$A$$ run on a sample $$S_n$$, has an error rate $$R(A(S_n)) \leq C \frac{\log{\frac{1}{\delta}} + d}{n}$$, where $$C$$ is a universal constant, $$n$$ is the sample size and $$d$$ is the VC dimension. (This bound is for the realizeable setting, but, that doesn't really matter to me).

Does that imply that there is a bound that holds in expectation? For example, does it now hold that $$E_{S_n} R(A(S_n)) \leq D?$$ where $$E_{S_n}$$ is the expectation with respect to the sample $$S_n$$, for some $$D$$ (perhaps depending on $$C$$, $$n$$, $$d$$, etc.).

And does the reverse also hold?

When I was studying bandits using Bubeck I came across in chapter 3.2 that the Exponential Weights algorithm's bound holds in expectation but not in high probability. It needs to be adapted with importance weighting for it to have a bound that holds with high probability (to control the variance). This seems to suggest that in this case, that the expected bound is weaker. Is this always the case?

It turns out that bounds in expectation can be translated to bounds in high probability and vice versa. However, translating the bounds may change the dependence on $$n$$.