Offsets and Constants in Contraction Bounds

Why Offsets Need Care

A contraction bound compares the complexity of a class of functions with the complexity of their transformed values. The Lipschitz property controls how much the transformation can change distances, but a transformation need not send zero to zero. That difference matters when stating the bound: the cleanest form applies to a transform centered by subtracting its value at zero.

A fixed additive constant can often be removed without changing the complexity of interest. But “often” is not “always.” In an expected Rademacher supremum, a common constant contributes a signed sum whose expectation is zero. In a centered empirical process, a common numerical constant cancels between the empirical and population averages. An additive function of the observation, by contrast, need not cancel from that process.

Definitions and the Contraction Inequality

Definition: For a nonempty class $\mathcal F$ of real-valued functions and fixed observations $x_1,\ldots,x_n$, its empirical Rademacher complexity, in the non-absolute convention used here, is $$ \widehat{\mathfrak R}_n(\mathcal F;x_1,\ldots,x_n) = E_{\varepsilon}\left[ \sup_{f\in\mathcal F}\frac{1}{n}\sum_{i=1}^n\varepsilon_i f(x_i) \right], $$ where $\varepsilon_1,\ldots,\varepsilon_n$ are independent Rademacher signs: each equals $1$ or $-1$ with probability $1/2$. For a random sample $X_1,\ldots,X_n$, the expected Rademacher complexity is $E[\widehat{\mathfrak R}_n(\mathcal F;X_1,\ldots,X_n)]$, when the expectation is defined.

The supremum here is not inside an absolute value. This convention is useful for contraction and symmetrization bounds. For a nonempty finite class, the expectation is nonnegative: the expected supremum is at least the expectation of the signed sum for any one fixed member, which is zero.

We use the standard Rademacher contraction inequality in its finite-class form. If $T$ is a nonempty finite subset of $\mathbb R^n$, and each $\phi_i:\mathbb R\to\mathbb R$ is $L$-Lipschitz, then

E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^n\varepsilon_i\phi_i(t_i) \leq L E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^n\varepsilon_i t_i.

Here $L$-Lipschitz means $|\phi_i(u)-\phi_i(v)|\leq L|u-v|$ for every $u,v\in\mathbb R$. The inequality does not require $\phi_i(0)=0$. The zero-at-zero condition is sometimes included in textbook statements because it simplifies the formulation; the offset argument below explains why it can be imposed without loss for this expected supremum. For suitable measurable, separable classes, finite-class inequalities extend by approximation; finite classes suffice for the derivations here.

Worked Example: Removing an Affine Offset

Let $n=2$ and let $T=\{(1,0),(0,1)\}$. First compute the unnormalized Rademacher supremum for $T$. For the four equally likely sign pairs $(1,1),(1,-1),(-1,1),(-1,-1)$, the suprema are $1,1,1,-1$, respectively. Thus

E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^2\varepsilon_i t_i =\frac{1+1+1-1}{4} =\frac12.

Now take $\phi(u)=7+2u$. Its Lipschitz constant is $2$, and $\phi(0)=7$. The transformed vectors are $(9,7)$ and $(7,9)$. For any sign pair, their signed sums equal $7(\varepsilon_1+\varepsilon_2)$ plus twice the corresponding signed sum for $T$. The expected first term is zero, so

E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^2\varepsilon_i\phi(t_i) = 2\left(\frac12\right)=1.

After dividing by $n=2$, the transformed complexity is $1/2$, exactly twice the original complexity $1/4$. Subtracting $\phi(0)=7$ gives the centered transform $2u$, which has the same expected Rademacher supremum as $\phi$.

Centering a Lipschitz Transform at Zero

For a single $L$-Lipschitz map $\phi$, define its centered version by

\psi(u)=\phi(u)-\phi(0).

Then $\psi(0)=0$, and $\psi$ has the same Lipschitz constant: subtracting a fixed number does not change differences, so $|\psi(u)-\psi(v)|=|\phi(u)-\phi(v)|\leq L|u-v|$.

Theorem: Let $T$ be a nonempty finite subset of $\mathbb R^n$, and let $\phi:\mathbb R\to\mathbb R$ be $L$-Lipschitz. Then $$ E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^n\varepsilon_i\phi(t_i) = E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^n\varepsilon_i\bigl(\phi(t_i)-\phi(0)\bigr) \leq L E_{\varepsilon}\sup_{t\in T}\sum_{i=1}^n\varepsilon_i t_i. $$

Proof. For every sign vector, the offset $\phi(0)$ is the same for every $t\in T$. Therefore it can be pulled outside the supremum:

\sup_{t\in T}\sum_{i=1}^n\varepsilon_i\phi(t_i) = \phi(0)\sum_{i=1}^n\varepsilon_i + \sup_{t\in T}\sum_{i=1}^n\varepsilon_i\bigl(\phi(t_i)-\phi(0)\bigr).

Taking expectations removes the first term because $E[\varepsilon_i]=0$ for every $i$. The centered map $\psi(u)=\phi(u)-\phi(0)$ is $L$-Lipschitz and satisfies $\psi(0)=0$. Applying the contraction inequality to $\psi$ proves the inequality. $\square$

For a function class $\mathcal F$, use $T=\{(f(x_1),\ldots,f(x_n)):f\in\mathcal F\}$. Dividing the theorem by $n$ gives the corresponding bound for empirical Rademacher complexities. Centering does not change the expected supremum, but it makes explicit which part of the transform is controlled by its Lipschitz constant.

Worked Example: A Shifted Absolute-Value Map

Use $T=\{(1,0),(0,1)\}$ again, and let $\phi(u)=|u-2|$. This map is $1$-Lipschitz and $\phi(0)=2$, so its centered form is $\psi(u)=|u-2|-2$. At the two input values, $\psi(1)=-1$ and $\psi(0)=0$. Thus the centered transformed vectors are $(-1,0)$ and $(0,-1)$.

For sign pairs $(1,1),(1,-1),(-1,1),(-1,-1)$, the suprema of the signed sums over these two centered vectors are $-1,1,1,1$. Their average is $1/2$. The original class $T$ also has expected supremum $1/2$, so in this case the contraction bound holds with equality.

The uncentered transformed vectors are $(1,2)$ and $(2,1)$, each equal to its centered version plus $(2,2)$. That common vector contributes $2(\varepsilon_1+\varepsilon_2)$ to every signed sum. Its expectation is zero, leaving the same expected supremum $1/2$. The offset affects individual sign outcomes, but not their expected supremum.

Why Constants Disappear from Centered Empirical Processes

Let $P$ be a probability distribution, let $X_1,\ldots,X_n$ be observations, and define $P_n g=n^{-1}\sum_{i=1}^n g(X_i)$ and $Pg=E[g(X)]$ for an integrable function $g$, where $X$ has distribution $P$. The centered empirical process applied to $g$ is $(P_n-P)g=P_ng-Pg$.

Proposition: If $c$ is a finite numerical constant, then for every integrable $g$, $$ (P_n-P)(g+c)=(P_n-P)g. $$ Consequently, for any class $\mathcal G$ of integrable functions for which the suprema are defined, $$ \sup_{g\in\mathcal G}(P_n-P)(g+c) = \sup_{g\in\mathcal G}(P_n-P)g. $$

Proof. The empirical average of the constant function $c$ is $P_n c=n^{-1}\sum_{i=1}^n c=c$. Its population average is $Pc=E[c]=c$. Hence

$$ (P_n-P)(g+c) =P_ng+c-(Pg+c) =P_ng-Pg =(P_n-P)g. $$

This equality holds for each $g$, so taking the supremum over the class preserves it. $\square$

In particular, if a transformed class consists of $\phi\circ f$ and $\phi(0)$ is a common numerical constant, centering each transformed function by subtracting $\phi(0)$ changes neither its centered empirical process nor the supremum of those processes. This exact cancellation is distinct from the Rademacher calculation: the latter uses expectation over signs, while the former subtracts two averages that each contain the same constant.

Worked Example: Checking Cancellation Against a Population Mean

Suppose $X$ is Bernoulli with $P(X=1)=1/4$, and the observed sample of size $2$ is $X_1=X_2=0$. For $g(x)=x$, the population average is $Pg=1/4$, while the empirical average is $P_ng=0$. Therefore

(P_n-P)g=0-\frac14=-\frac14.

Add the common constant $c=5$. Then $P_n(g+5)=5$ and $P(g+5)=1/4+5=21/4$, so

(P_n-P)(g+5)=5-\frac{21}{4}=-\frac14=(P_n-P)g.

The two averages each shift by $5$; their difference does not change.

Offsets Shared Across Coordinates

For a fixed sample, a coordinate-dependent offset can also be removed from an expected Rademacher supremum if it is shared by every member of the class. Specifically, suppose each candidate vector $t\in T$ is replaced by $(t_1+a_1,\ldots,t_n+a_n)$, where $a_1,\ldots,a_n$ do not depend on $t$. For each sign vector, the supremum increases by $\sum_i\varepsilon_i a_i$; its expectation is zero. The offset need not be the same in every coordinate.

That statement does not imply that coordinate-dependent offsets vanish from centered empirical processes. If the common addition is a function $b(x)$, then

$$ (P_n-P)(g+b)=(P_n-P)g+(P_n-P)b. $$

The extra term is zero for a numerical constant $b(x)=c$, but it need not be zero for a nonconstant function. This distinction matters, for example, when the offset depends on an observed label or covariate: it may be fixed across candidate functions at the observed coordinates, yet still vary with the observation.

Common Mistakes

Assuming $\phi(0)=0$ is necessary for offset removal. It is not necessary for the expected non-absolute Rademacher supremum. Subtract $\phi(0)$, apply contraction to the centered map, and use the zero mean of the signs to restore the original expected supremum.
Dropping an offset inside a supremum pointwise. The signed offset generally changes each sign-specific supremum. It disappears after taking expectation because it is common to all candidates and has mean zero.
Claiming any shared function cancels from a centered empirical process. A numerical constant cancels exactly. A nonconstant shared function contributes its own $(P_n-P)b$, which may not be zero.
Changing the complexity convention without checking the argument. Here the supremum is not inside an absolute value. Translation invariance of the expected supremum follows from adding the same signed term to every candidate; an absolute value around each sum changes that reasoning.

Key takeaway: Center a Lipschitz map as $\phi(u)-\phi(0)$ before invoking the zero-at-zero form of contraction. A common scalar offset leaves the expected Rademacher supremum unchanged and cancels exactly from $P_n-P$; observation-dependent offsets require separate care.

Check Your Understanding

Use the definitions and distinctions in this tutorial to answer the following.

Why does subtracting $\phi(0)$ preserve the Lipschitz constant of $\phi$?
For a fixed sample, what happens to the expected Rademacher supremum if the same constant is added to every coordinate of every candidate vector? Give the reason.
Explain why a numerical constant cancels from $(P_n-P)g$, but a nonconstant function added to every member of a class need not cancel.
If the offset in coordinate $i$ is $a_i$, shared across all candidate vectors, why does it still disappear from the expected Rademacher supremum?
Does the contraction inequality stated here put an absolute value around each signed sum? Why does that detail matter for the offset argument?