On the Rademacher complexity of a set.

230 Views Asked by At

Given a sequence $\{ \theta_j \}_{j=1}^{\infty} \in l^2(N)$, i.e., such that $\sum_{j=1}^{\infty} \theta_j^2 \le \infty$.

Given a strictly positive sequence $\{ \mu_j \}_{j=1}^{\infty}$ we define

$$T := \left \{ \{ \theta_j \}_{j=1}^{\infty} \in l^2(N) \ | \ \sum_{j=1}^{\infty} \frac{\theta_j^2}{\mu_j} \le 1 \right \} $$

We define the Rademacher complexity of this set as

$$ E_{\epsilon} \left[ \sup_{\theta \in T} \sum_{j=1}^{\infty} \epsilon_j \theta_j \right] $$

where the $\epsilon_j$ are Rademacher random variables.

Why is

$$ E_{\epsilon} \left[ \sup_{\theta \in T} \sum_{j=1}^{\infty} \epsilon_j \theta_j \right] = \sup_{\theta \in T} \sum_{j=1}^{\infty} | \theta_j |$$ ?

1

There are 1 best solutions below

0
On BEST ANSWER

For a given sequence $\epsilon: \mathbb{N} \to \{-1, +1\}$, define $f_{\epsilon}: T \to T$ by $(f_{\epsilon} \theta)_j = -\theta_j$ if $\epsilon_j \theta_j < 0$ and $(f_{\epsilon} \theta)_j = \theta_j$ otherwise. Then $\sum_{j= 1}^{\infty} \epsilon_j (f_{\epsilon} \theta)_j = \sum_{j=1}^{\infty} |\theta_j| \geq \sum_{j= 1}^{\infty} \epsilon_j \theta_j$. Define the set $T_{\epsilon} = \{ \theta \in T: f_{\epsilon} \theta = \theta \}$, i.e. the set of all $\theta \in T$ with $\epsilon_j \theta_j = |\theta|_j$ for all $j$. Clearly

$$\sup_{\theta \in T} \sum_{j= 1}^{\infty} \epsilon_j \theta_j = \sup_{\theta \in T_{\epsilon} } \sum_{j= 1}^{\infty} \epsilon_j \theta_j = \sup_{\theta \in T_{\epsilon} } \sum_{j= 1}^{\infty} |\theta_j| = \sup_{\theta \in T} \sum_{j= 1}^{\infty} |\theta_j|$$

Since equality holds for each Rademacher sequence $\epsilon$, it must hold for the expectation over all $\epsilon$.