Star-Shaped Classes and Sub-Root Complexity

Why Star-Shapedness Matters

Localized Rademacher complexity measures how large random fluctuations can be among functions whose squared size is limited. The limit is important: functions close to a risk minimizer often have small excess risk, and restricting attention to such functions can give a sharper complexity measure than studying the entire class at once.

The key geometric condition in this tutorial is star-shapedness around zero. It says that shrinking any function in the class toward zero keeps it in the class. This lets us compare two localization radii: a function allowed at the larger radius can be shrunk until it is allowed at the smaller one. Because Rademacher averages scale linearly under this shrinking, the localized complexity inherits a square-root scaling inequality.

For example, given a risk minimizer \(f^\star\) and a loss function \(\ell_f\), an excess-loss function has the form \(g_f(x)=\ell_f(x)-\ell_{f^\star}(x)\). The class of these functions is not automatically star-shaped: the condition requires that \(a g_f\) belong to the excess-loss class for every \(a\in[0,1]\). The functions may take negative values at individual observations even when their expectations are nonnegative.

Two Localized Complexities

Let \(X_1,\ldots,X_n\) be independent observations with common distribution \(P\), and let \(\epsilon_1,\ldots,\epsilon_n\) be independent Rademacher random variables, independent of the observations: each sign is \(+1\) or \(-1\) with probability \(1/2\). Write \(P_n g^2=n^{-1}\sum_{i=1}^n g(X_i)^2\) for the empirical second moment and \(P g^2=E[g(X)^2]\) for the population second moment.

The two definitions localize in different ways. The empirical version restricts functions using the observed sample, while the population version uses their second moment under \(P\). In either case the random average is evaluated on the sample. For the results below, assume the functions are measurable, the suprema are measurable (for example, \(\mathcal G\) is countable), and the displayed expectations are finite. A uniformly bounded class is a convenient sufficient condition for finiteness. Since \(0\in\mathcal G\), each localized class contains zero, and each complexity is nonnegative.

Monotonicity and Square-Root Scaling

The first property needs no star-shapedness. Increasing \(r\) only enlarges the set over which the supremum is taken. The second property is the geometric payoff: star-shapedness lets us shrink every function admissible at a larger radius so it becomes admissible at a smaller radius.

Proof. First fix the sample. If \(r_1\leq r_2\), then \(\{g\in\mathcal G:P_n g^2\leq r_1\}\) is contained in \(\{g\in\mathcal G:P_n g^2\leq r_2\}\). For every fixed sign vector, the supremum over the smaller set cannot exceed the supremum over the larger set. Taking expectation over the signs proves \(\widehat\psi_S(r_1)\leq\widehat\psi_S(r_2)\). For population localization the same inclusion holds with \(P g^2\) in place of \(P_n g^2\). Taking expectation over observations and signs proves that \(\psi_n\) is nondecreasing.

Now fix \(0<r_1\leq r_2\) and set \(a=\sqrt{r_1/r_2}\), so \(a\in(0,1]\). For any \(g\in\mathcal G\) with \(P_n g^2\leq r_2\), star-shapedness gives \(ag\in\mathcal G\), and \[ P_n(ag)^2=a^2P_n g^2\leq a^2r_2=r_1. \] The Rademacher average is linear in the function: \(n^{-1}\sum_i\epsilon_i(ag)(X_i)=a n^{-1}\sum_i\epsilon_i g(X_i)\). Thus, for each sign vector, the supremum at radius \(r_1\) is at least \(a\) times the supremum at radius \(r_2\). To see this directly, the scaled versions \(ag\) of all functions admissible at \(r_2\) are among those admissible at \(r_1\), and \(a\geq0\). Taking sign expectations yields the empirical scaling inequality.

For population localization, if \(P g^2\leq r_2\), then \(P(ag)^2=a^2P g^2\leq r_1\). The same linearity argument applies to each observed sample and sign vector. Taking expectation over both proves the population scaling inequality. Dividing either inequality by \(\sqrt{r_1}\) gives that the ratio at \(r_1\) is at least the ratio at \(r_2\), as claimed. \(\square\)

How the Properties Point to a Critical Radius

A localized complexity bound is often compared with the squared radius itself. The radius describes the size permitted for functions; the complexity describes the scale of their random fluctuations. A critical radius is a scale at which these quantities balance, commonly expressed through an equation such as \(\psi(r)=r\), or through the point beyond which \(\psi(r)\leq r\). This tutorial establishes the shape properties that make such a comparison useful; determining a fixed point and using it in a risk bound require additional arguments.

Sub-root behavior gives a simple way to read the comparison. The complexity is nondecreasing, but it grows no faster than the square-root scaling inequality permits: shrinking the radius by a factor \(c\) shrinks the complexity by at least a factor \(\sqrt c\), for \(0<c\leq1\). Thus the ratio \(\psi(r)/\sqrt r\) decreases as the localization region expands. This is a structural statement, not a numerical rate by itself; calculating an actual critical radius still requires a bound or formula for \(\psi\).

Common Pitfall

• Confusing monotonicity with sub-root scaling. Nested localized sets always make the supremum nondecreasing with radius. That fact alone does not show that \(\psi(r)/\sqrt r\) decreases. The latter conclusion uses star-shapedness and the linear scaling of the Rademacher average.
• Assuming an excess-loss class is star-shaped automatically. The definition of excess loss does not guarantee that \(ag_f\) is another excess loss. Verify the closure property for the class under consideration rather than inferring it from the word “excess.”
• Treating \(r\) as an unsquared function size. The constraint is on \(P g^2\) or \(P_n g^2\). Scaling a function by \(a\) scales this radius quantity by \(a^2\), which is why the complexity comparison involves \(\sqrt{r_1/r_2}\).