Empirical Localized Rademacher Complexity

Why Localization Changes the Complexity

A global complexity measure describes how richly an entire class of functions can vary on a sample. For risk minimization, however, the most relevant candidates are often those whose excess risk is already small. Restricting attention to such candidates can produce a smaller, more informative complexity. The restriction itself matters: a population-risk restriction defines a fixed class, while an empirical-risk restriction selects functions using the observed data.

That difference leads to two distinct sources of randomness. The observed sample determines the function values in a Rademacher sum. Under empirical localization, it also determines which functions are allowed in the supremum. Conditional on the sample, the Rademacher complexity averages only over auxiliary random signs; its expectation over samples is a separate quantity.

Excess Losses and Two Localized Classes

Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\), and let \(P_n f=n^{-1}\sum_{i=1}^n f(Z_i)\) denote the empirical average of a measurable function \(f\). Suppose a predictor \(h\) has loss \(\ell_h(Z)\), and let \(h_*\) be a risk minimizer in the comparison class. Its excess-loss function is \(f_h(Z)=\ell_h(Z)-\ell_{h_*}(Z)\). Thus \(P f_h\) is the excess risk of \(h\), and \(P f_h\geq 0\) when \(h_*\) truly minimizes population risk over that class. The values \(f_h(Z)\) need not be nonnegative for each observation.

Definition: Write \(\mathcal F=\{f_h:h\in\mathcal H\}\) for an excess-loss class, including the zero function \(f_{h_*}=0\). For a radius \(r\geq 0\), its population-localized class is \(\mathcal F^{P}(r)=\{f\in\mathcal F: P f\leq r\}\). Its empirically localized class is \(\mathcal F^{P_n}(r)=\{f\in\mathcal F: P_n f\leq r\}\). The first is fixed once \(P\), \(\mathcal F\), and \(r\) are fixed. The second is a random class because it depends on the observed sample.

The radii here restrict mean excess risk. Other localization conventions, such as restrictions on a second moment, are also used in statistical learning, but they define different localized classes. A radius always has to be interpreted relative to its stated restriction.

Let \(\sigma_1,\ldots,\sigma_n\) be independent Rademacher signs, independent of the data: each sign equals \(1\) or \(-1\), each with probability \(1/2\). For a fixed observed sample, the conditional Rademacher complexity averages over these signs only.

Definition: For a class \(\mathcal G\), its conditional empirical Rademacher complexity on the observed sample is \(\widehat{\mathfrak R}_n(\mathcal G)=E_{\sigma}[\sup_{f\in\mathcal G} n^{-1}\sum_{i=1}^n \sigma_i f(Z_i)\mid Z_1,\ldots,Z_n]\). For empirical localization, set \(\widehat{\mathfrak R}_n(\mathcal F^{P_n}(r))=E_{\sigma}[\sup_{f\in\mathcal F^{P_n}(r)} n^{-1}\sum_{i=1}^n \sigma_i f(Z_i)\mid Z_1,\ldots,Z_n]\). This is a random variable through both the observed function values and, for empirical localization, the selected class.

For population localization, \(\widehat{\mathfrak R}_n(\mathcal F^{P}(r))\) is still random: the class is fixed, but its function values on the sample vary. In either case, the expected localized complexity is the outer expectation over the data, \(E[\widehat{\mathfrak R}_n(\cdot)]\). It is not the conditional quantity for a particular sample. Including the zero function ensures that the supremum, and hence the conditional complexity, is nonnegative.

For precision, assume the classes are countable, or that a suitable separability condition makes the displayed suprema measurable. In the examples below all classes are finite. Any result that also uses expectations of function values assumes the relevant functions are integrable; bounded functions are sufficient.

Calculating the Conditional Quantity

Worked Example: A One-Observation Empirical Restriction

Let \(n=1\), let \(Z\) take values \(a\) and \(b\) with equal probability, and let \(\mathcal F=\{0,f\}\), where \(f(a)=1\) and \(f(b)=-1\). Then \(P f=0\). Take radius \(r=0\).

If the observed value is \(a\), then \(P_n f=1\), so \(f\) is excluded from \(\mathcal F^{P_n}(0)\). The localized class is \(\{0\}\), and its conditional complexity is \(0\).

If the observed value is \(b\), then \(P_n f=-1\leq 0\), so the localized class is \(\{0,f\}\). Its signed supremum is \(\max(0,\sigma_1(-1))\). This equals \(1\) when \(\sigma_1=-1\) and \(0\) when \(\sigma_1=1\), giving conditional complexity \(1/2\).

Consequently, the empirical-localized conditional complexity is \(0\) with probability \(1/2\) and \(1/2\) with probability \(1/2\). Its expectation over the sample is \(1/4\). By contrast, \(P f=0\), so population localization at radius zero always includes \(f\). Its conditional complexity is \(1/2\) on either possible sample, and its expectation is \(1/2\). The two localization rules do not give interchangeable quantities.

Worked Example: Computing a Supremum Over Two Functions

Fix \(n=2\) and a sample on which two functions have values \(f_1(Z_1)=1,\ f_1(Z_2)=0\), and \(f_2(Z_1)=0,\ f_2(Z_2)=1\). Include the zero function and suppose the radius admits both \(f_1\) and \(f_2\). For any sign pair, the supremum is \(\max(0,\sigma_1/2,\sigma_2/2)\).

Of the four equally likely sign pairs, \((1,1)\), \((1,-1)\), and \((-1,1)\) each give a supremum of \(1/2\). The pair \((-1,-1)\) gives \(0\). Therefore the conditional complexity is \((3(1/2)+0)/4=3/8\).

This calculation conditions on the displayed sample. It does not average over other possible datasets. If the sample changes, the values in the signed sums—and possibly the empirically localized class—can change too.

Worked Example: How a Radius Changes the Empirical Class

On a fixed sample of size two, suppose \(\mathcal F=\{0,f,g\}\), with observed values \(f(Z_1)=f(Z_2)=1\) and \(g(Z_1)=1,\ g(Z_2)=-1\). Their empirical means are \(P_n f=1\) and \(P_n g=0\).

At radius \(r=0\), empirical localization includes \(0\) and \(g\), but excludes \(f\). The signed supremum is \(\max(0,(\sigma_1-\sigma_2)/2)\). It is \(1\) for the sign pair \((1,-1)\) and \(0\) for the other three pairs, so the conditional complexity is \(1/4\).

At radius \(r=1\), both nonzero functions are admitted. The supremum becomes \(\max(0,(\sigma_1+\sigma_2)/2,(\sigma_1-\sigma_2)/2)\). It equals \(1\) for \((1,1)\) and \((1,-1)\), and \(0\) for the other pairs. The complexity is \(1/2\). Increasing the radius has enlarged the class and increased its conditional complexity in this calculation.

Two Properties and Their Proofs

Proposition: For either population or empirical localization, the conditional localized Rademacher complexity is nondecreasing in the radius. For empirical localization this statement holds for every fixed sample.

Proof. If \(0\leq r_1\leq r_2\), then \(P f\leq r_1\) implies \(P f\leq r_2\), so \(\mathcal F^{P}(r_1)\subseteq\mathcal F^{P}(r_2)\). For a fixed sample, \(P_n f\leq r_1\) likewise implies \(P_n f\leq r_2\), giving \(\mathcal F^{P_n}(r_1)\subseteq\mathcal F^{P_n}(r_2)\). For each realization of the signs, the supremum over a subset cannot exceed the supremum over its superset. Taking the conditional expectation over signs preserves the inequality. \(\square\)

For a fixed population-localized class, expected conditional complexity also controls a one-sided uniform deviation. This is the standard symmetrization bound. It does not by itself establish the same bound for a class selected by empirical localization.

Theorem: Let \(\mathcal G\) be a fixed, countable class of integrable functions, and suppose the suprema below are measurable and their expectations exist. For independent observations from \(P\), \(E[\sup_{f\in\mathcal G}(P f-P_n f)]\leq 2E[\widehat{\mathfrak R}_n(\mathcal G)]\). In particular, this applies to the fixed class \(\mathcal F^{P}(r)\) under these conditions.

Proof. Let \(Z'_1,\ldots,Z'_n\) be an independent sample from \(P\), and let \(P'_n f=n^{-1}\sum_i f(Z'_i)\). Conditional on the original sample, \(P f=E[P'_n f\mid Z_1,\ldots,Z_n]\). The supremum of expectations is no greater than the expectation of the supremum, so

E\sup_{f\in\mathcal G}(P f-P_n f) \leq E\sup_{f\in\mathcal G}(P'_n f-P_n f).

For each \(i\), swapping \(Z_i\) and \(Z'_i\) leaves their joint distribution unchanged. Introducing independent signs to represent these swaps therefore leaves the right-hand expectation unchanged. It becomes

E\sup_{f\in\mathcal G}\frac{1}{n}\sum_{i=1}^n \sigma_i\bigl(f(Z'_i)-f(Z_i)\bigr).

For any two indexed collections \(A_f,B_f\), \(\sup_f(A_f+B_f)\leq\sup_f A_f+\sup_f B_f\). Applying this inequality to the two signed sums bounds the last display by

E\sup_{f\in\mathcal G}\frac{1}{n}\sum_{i=1}^n \sigma_i f(Z'_i) + E\sup_{f\in\mathcal G}\frac{1}{n}\sum_{i=1}^n (-\sigma_i) f(Z_i).

The first term is \(E[\widehat{\mathfrak R}_n(\mathcal G)]\), since the primed sample has the same distribution as the original sample. The signs \(-\sigma_i\) have the same joint distribution as \(\sigma_i\), so the second term has the same value. Adding the two terms proves the bound. \(\square\)

What the Distinction Means in Practice

The theorem concerns a fixed class, such as \(\mathcal F^{P}(r)\): the data are used to evaluate its functions, not to choose membership in the class. With \(\mathcal F^{P_n}(r)\), the same sample determines both the membership restriction and the signed sums. One cannot treat that random class as though it had been fixed independently of the sample and invoke the theorem without additional justification. The one-observation example shows concretely that even the expected complexity can differ between the two restrictions.

A conditional complexity answers: given these observed data, how large is the average signed supremum? An expected complexity answers: how large is that conditional quantity on average over repeated datasets? Both are useful, but they answer different questions. The distinction is essential when a later argument uses a random, empirically chosen localized class.

Mistake: Calling a conditional complexity “the expected complexity” because it already averages over Rademacher signs. Correction: It is conditional on the data; the expectation over the data is an additional outer expectation.
Mistake: Assuming empirical and population localization select the same functions at the same radius. Correction: \(P_n f\) varies with the sample, and may be below \(r\) even when \(P f\) is not, or above \(r\) when \(P f\) is below it.
Mistake: Applying a fixed-class symmetrization bound directly to an empirically selected class. Correction: First account for the class’s dependence on the sample; the fixed-class theorem alone does not do so.

Check Your Understanding

Use the definitions and calculations above to check your understanding.

Which source of randomness remains in a conditional Rademacher complexity after the sample is fixed?
Why can an excess-loss function be negative at an individual observation even when its population excess risk is nonnegative?
For \(r_1\leq r_2\), why does the conditional complexity for empirical localization not decrease as the radius grows?
In the one-observation example, what are the expected complexities for empirical and population localization at radius zero?
Why does the stated symmetrization theorem not directly justify a bound for an empirically localized class?