assumptions on local rademacher complexities

Question

A lot of the work on Local Rademacher complexities of Koltchinskii, and Bartlett for fast rates of convergence is based on Bousquet's version of Talagrand's inequality [1] (Theorem 2.11). However the assumption used by Bousquet is that the space of functions used is countable. Nevertheless, all the results by Koltchinskii and Bartlett ignore this assumption and claim that it holds for arbitrary function spaces.

My question is does the general inequality follows from the countable inequality? I have been trying to show this but it is not immediate without some continuity assumptions on the empirical process.

The proof of Bousquet also uses the fact that the set can be approximated with finite sets so I do believe it is necessary to have a countable space of functions.

[1] Concentration inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms. Olivier Bousquet, 2002.

Answer 1

I do not think the general inequality holds without further qualifications. Separability of the function class is one assumption which enables application of Bousquet's version of Talagrand's inequality, since separability implies that the function admits a countable dense subset.

I recommend looking at "General nonexact oracle inequalities for classes with a subexponential envelope" by Lecué and Mendelson, which can be found here:

http://projecteuclid.org/download/pdfview_1/euclid.aos/1338515139

Specifically, look at at sentence after equation (2.1) on page 843, which mentions that the version of Theorem 2.1 stated there (which is a version of Talagrand's inequality) can be extended from countable classes to those satisfying a separability condition. They go on to mention that one such condition is condition (M) in the paper "Risk bounds for statistical learning" by Massart and Nédélec.

Also, note that Koltchinskii mentions "measurable" when he mentions function classes, which might already impose some restrictions making things go through. Also, Bartlett, Bousquet, and Mendelson discuss measurability of the supremum as a condition in the context of how to treat the sup (search for "measurability" in the journal version their paper on local Rademacher complexities).

You might also get clarification by looking in Talagrand's book "Upper and Lower Bounds for Stochastic Processes" (which entirely subsumes his book "The Generic Chaining"). On page 13, Talagrand comments "A side issue (in particular when $T$ is uncountable) is that what is meant by the quantity $\mathsf{E} \sup_{t \in T} X_t$ is not obvious." He then offers one patch-up, which is to define it as follows:

$\mathsf{E} \sup_{t \in T} = \sup \left\{ \mathsf{E} \sup_{t \in F} X_t ; F \subset T , F \text{ finite} \right\}$.

This is a very good question, and it is hard to get answers, because as explained by Talagrand, issues like this were covered all the time in the pre-1950's era, to the point where people who are well-versed in it no longer have the patience to continue mentioning these issues in papers in any detail.