Symmetrization and Rademacher processes

Let X_i be iid with law P, and let F be a nonempty finite or countable class of measurable real functions dominated in absolute value by a nonnegative measurable envelope U with EU(X)<infinity. These assumptions make the relevant suprema measurable and integrable. Define P_n f as the sample average and Pf as its expectation. For more general uncountable classes one needs a separability or outer-expectation framework; the displayed ordinary-expectation statement does not silently assume those issues disappear.

Let ε_i be independent symmetric signs, also independent of the sample. Our conditional Rademacher average is E_ε sup_f |n inverse Σ ε_i f(X_i)|, with the absolute value inside the supremum and no extra factor two. Its expectation over the sample is R_n(F). Some references use a nonabsolute supremum or multiply by two in the definition, so their theorem constants must be translated. A bound on this expected signed process measures the class collectively rather than testing one function fixed in advance.

Introduce an independent sample X_i' with the same law. Conditional Jensen bounds the population-centered expected supremum by the expected supremum of n inverse Σ(f(X_i)−f(X_i')). Each pair has an exchangeable distribution. Swapping its two entries when ε_i is negative therefore leaves the joint law unchanged and inserts independent signs in front of these differences. This randomization step requires paired iid structure; signs do not magically make an arbitrary dependent sample independent.

Apply the triangle inequality to split the signed original and ghost sums inside the supremum. Their expectations are identical, yielding two copies of the expected conditional Rademacher average. The factor two comes from this splitting rather than a claim that the empirical process exactly equals twice a signed one. The resulting inequality is in expectation. To obtain a high-probability uniform guarantee, an additional concentration step may control the supremum's fluctuation, with appropriate boundedness or tail assumptions and its own probability term.

For a class of M functions uniformly bounded by B, condition on the sample. Each signed sum has a quadratic mgf controlled by the sum of its squared evaluations. Apply an exponential maximum bound to the M functions and their negatives, optimize the exponential parameter, and divide by n. This gives a conditional Rademacher bound B sqrt(2 log(2M)/n). A sharper data-dependent version can use the largest Euclidean norm of the evaluation vectors instead of B sqrt(n). Neither expression requires the functions to have zero population mean.

The logarithm counts alternatives, while the sample size reduces their collective fluctuation. The bound can be loose for redundant functions: if two functions are negatives, the absolute supremum does not gain another distinct shape. Exact small-class calculations expose that looseness and verify normalization. In larger learning problems, entropy or chaining methods refine crude cardinality counts, but the first question remains the same: how large is the signed process under a precisely defined class and an admissible envelope?