Contraction for Lipschitz Coordinate Transforms

Why Coordinatewise Contraction Matters

Rademacher complexity measures how well a class of functions can align with random signs on a fixed sample. Many transformations change the values of every function in a class without making the class arbitrarily more complex. If each transformed coordinate changes by at most a fixed multiple of the change in the original coordinate, the Rademacher contraction inequality gives a direct comparison of the two complexities.

The essential message is simple: a coordinatewise \(L\)-Lipschitz transformation can increase the standard Rademacher complexity by at most a factor of \(L\). The result concerns a supremum over a class, not just the transformation of one function. Its usefulness is that it controls the whole transformed class at once.

Rademacher Complexity on a Fixed Sample

Fix sample points \(x_1,\ldots,x_n\) and a finite class \(\mathcal F\) of real-valued functions defined at those points. Let \(\varepsilon_1,\ldots,\varepsilon_n\) be independent Rademacher signs: each sign equals \(1\) or \(-1\) with probability \(1/2\). The sample is fixed here, so the expectation below is only over these signs.

Definition: The empirical Rademacher complexity in the non-absolute convention is

\widehat{\mathfrak R}_S(\mathcal F) = \frac{1}{n}E_{\varepsilon} \left[ \sup_{f\in\mathcal F}\sum_{i=1}^n \varepsilon_i f(x_i) \right],

where \(S=(x_1,\ldots,x_n)\). The unnormalized version omits the factor \(1/n\). For a finite class the supremum is measurable and the expectation is well-defined.

Equivalently, associate to each \(f\) its value vector \(v_f=(f(x_1),\ldots,f(x_n))\in\mathbb R^n\). The complexity is determined by how large the signed inner product \(\sum_i\varepsilon_i v_{f,i}\) can be when \(f\) ranges over the class.

The Rademacher Contraction Inequality

For each coordinate, let \(\phi_i:\mathbb R\to\mathbb R\) be a scalar transformation. Say that \(\phi_i\) is \(L\)-Lipschitz if \(|\phi_i(u)-\phi_i(v)|\le L|u-v|\) for every \(u,v\in\mathbb R\). The transformed class consists of functions whose value at sample coordinate \(i\) is \(\phi_i(f(x_i))\). The transformations may differ across coordinates.

Theorem (Rademacher contraction inequality): Let \(\mathcal F\) be a finite class of real-valued functions on the fixed sample \(x_1,\ldots,x_n\). Suppose each \(\phi_i:\mathbb R\to\mathbb R\) is \(L\)-Lipschitz, for a common \(L\ge 0\). Then

E_{\varepsilon}\left[ \sup_{f\in\mathcal F} \sum_{i=1}^n\varepsilon_i\phi_i(f(x_i)) \right] \le L E_{\varepsilon}\left[ \sup_{f\in\mathcal F} \sum_{i=1}^n\varepsilon_i f(x_i) \right].

Consequently, the empirical Rademacher complexity of the transformed value class is at most \(L\widehat{\mathfrak R}_S(\mathcal F)\).

The statement uses the same signs in both expressions and the same candidate function \(f\) on each side. The supremum is not taken separately at each coordinate. If coordinate \(i\) has its own Lipschitz constant \(L_i\), the common-constant statement applies with \(L=\max_i L_i\). Thus the general bound uses the largest coordinatewise Lipschitz constant; it does not assert that an average of the \(L_i\)'s can be substituted.

The displayed theorem is for the non-absolute convention defined above. A quantity defined instead using \(\sup_{f\in\mathcal F}|\sum_i\varepsilon_i f(x_i)|\) is a different convention. The theorem as written does not, by itself, justify replacing its supremum by that absolute-value supremum.

Worked Example: A Nonlinear Map on a Three-Function Class

Take \(n=2\) and a finite class whose value vectors on the sample are \((0,0)\), \((1,0)\), and \((0,1)\). Apply the same map \(\phi(t)=t^2\) to both coordinates. On \([0,1]\), this map is \(2\)-Lipschitz because \(|u^2-v^2|=|u-v||u+v|\le 2|u-v|\).

First compute the original unnormalized complexity. For signs \((\varepsilon_1,\varepsilon_2)\), the three signed sums are \(0,\varepsilon_1,\varepsilon_2\). For the four equally likely sign pairs, the suprema are \(1,1,1,0\), respectively. Therefore

E_{\varepsilon}\sup_{v\in\{(0,0),(1,0),(0,1)\}}\varepsilon\mathbin{\cdot}v = \frac{1+1+1+0}{4} = \frac{3}{4}.

All coordinates in these vectors are \(0\) or \(1\), so squaring leaves every vector unchanged. The transformed unnormalized complexity is also \(3/4\), and contraction gives the valid, though not tight, upper bound \(2(3/4)=3/2\). Dividing by \(n=2\), the original and transformed empirical complexities are both \(3/8\), while the theorem bounds the transformed one by \(3/4\).

Worked Example: Linear Scaling Attains the Lipschitz Factor

Consider \(n=2\) and the class with value vectors \((a,a)\) for \(-1\le a\le 1\). Its unnormalized supremum for fixed signs is \(\sup_{|a|\le1}a(\varepsilon_1+\varepsilon_2)=|\varepsilon_1+\varepsilon_2|\). The four sign pairs give absolute values \(2,0,0,2\), so the expectation is \(1\). The empirical complexity is \(1/2\).

Now use \(\phi(t)=3t\), which is \(3\)-Lipschitz. The transformed vectors are \((3a,3a)\), so their unnormalized expected supremum is \(3\). The empirical complexity is \(3/2\), exactly three times the original \(1/2\). In this example the contraction bound is attained; the factor \(L\) cannot generally be dropped.

Worked Example: Different Coordinatewise Lipschitz Constants

Let the class have two value vectors, \(v_1=(1,0)\) and \(v_2=(0,1)\). Before transformation, the signed sums are \(\varepsilon_1\) and \(\varepsilon_2\). For the four equally likely sign pairs, their maximum is \(1,1,1,-1\), so the unnormalized complexity is \(1/2\).

Choose \(\phi_1(t)=t\) and \(\phi_2(t)=4t\). Their Lipschitz constants are \(1\) and \(4\), so the common bound uses \(L=4\). The transformed vectors are \((1,0)\) and \((0,4)\). The four maxima of their signed sums are \(4,1,4,-1\), giving

E_{\varepsilon}\sup_{v\in\{(1,0),(0,4)\}}\varepsilon\mathbin{\cdot}v = \frac{4+1+4-1}{4} = 2.

The theorem’s bound is \(4(1/2)=2\), so it holds with equality. Here \(n=2\), and the normalized complexities are \(1/4\) before transformation and \(1\) afterward. This example also shows why the largest coordinatewise Lipschitz constant is the safe common multiplier.

Two Useful Consequences

The theorem gives simple rules for keeping track of normalization and for chaining coordinatewise maps. These consequences require no additional assumptions beyond the finiteness and Lipschitz conditions stated above.

Corollary 1 (normalization): If \(\mathcal G\) is the class with values \(g_f(x_i)=\phi_i(f(x_i))\), then \(\widehat{\mathfrak R}_S(\mathcal G)\le L\widehat{\mathfrak R}_S(\mathcal F)\).

Derivation. By definition, each side of the unnormalized contraction inequality is divided by the same positive integer \(n\) to obtain its empirical complexity. Dividing the inequality by \(n\) preserves its direction and gives the stated result. \(\square\)

Corollary 2 (composition): Suppose \(\phi_i\) is \(L\)-Lipschitz and \(\psi_i:\mathbb R\to\mathbb R\) is \(K\)-Lipschitz for every coordinate \(i\). The class with values \(\psi_i(\phi_i(f(x_i)))\) has empirical Rademacher complexity at most \(KL\widehat{\mathfrak R}_S(\mathcal F)\).

Derivation. For any real \(u,v\), the two Lipschitz conditions give \[ |\psi_i(\phi_i(u))-\psi_i(\phi_i(v))| \le K|\phi_i(u)-\phi_i(v)| \le KL|u-v|. \] Thus each composite coordinate map \(\psi_i\circ\phi_i\) is \(KL\)-Lipschitz. Apply the contraction inequality to these composite maps, then divide by \(n\) as in Corollary 1. \(\square\)

Why the Bound Is Useful

A typical use is to control the complexity of a transformed class without enumerating every transformed value vector. Once a Lipschitz constant is known over the relevant range, contraction transfers an existing complexity bound to the transformed class. If the original empirical complexity is small and the transformation has moderate Lipschitz constant, the transformed complexity is controlled as well. This is one reason the inequality is useful in uniform-deviation arguments: it can reduce a new class to a class whose complexity is already understood.

The bound is an upper bound, not an equality in general. A nonlinear map may shrink the class substantially, or even leave its value vectors unchanged on the sample, as in the first worked example. The Lipschitz constant records a guaranteed worst-case expansion; it need not describe the actual expansion for a particular class.

Common Mistake

A common error is to apply the theorem to \(\sup_f|\sum_i\varepsilon_i\phi_i(f(x_i))|\) and immediately claim a bound by \(L\) times the corresponding absolute-value complexity, without checking the convention or its hypotheses. The stated contraction inequality has no absolute value inside its supremum. These expressions are not interchangeable by notation alone; the absolute-value form needs its own justification and appropriate assumptions. A second frequent error is to use a Lipschitz constant smaller than the largest one when the coordinate maps differ. For a single common multiplier, verify that every coordinate map satisfies the stated bound.

Check Your Understanding

Use the non-absolute empirical Rademacher complexity convention from this tutorial.

For \(n=4\), the unnormalized contraction bound is \(2\). What empirical complexity bound follows when the coordinate maps are all \(3\)-Lipschitz?
Why does the linear map \(\phi(t)=ct\) have Lipschitz constant \(|c|\), and what factor does contraction give?
If the coordinatewise Lipschitz constants are \(2,5,3\), what common constant can be used directly in the theorem?
In the first worked example, why is the transformed value class identical to the original value class even though the map is nonlinear?
What must be checked before using the theorem for a complexity defined with an absolute value inside the supremum?