Skip to main content
MathOverflow

Return to Revisions

1 of 6
user avatar
user avatar

For a concentration bound, we can decompose $Y$ by introducing random variables $Y_i = z_i^2 x_i$, where $x_i$ denotes the $i$-th coordinate of $X \in X_k$. Then $Y = \sum_{i=1}^n Y_i$. Assuming vectors $X \in X_k$ are chosen uniformly at random, the $Y_i$ become independent for fixed $X$ due to the independence of the $z_i$. To apply Bernstein's inequality, we must establish:

  1. Zero-Mean: Since $z_i \sim \mathcal{N}(0, \sigma^2)$, it follows that $\mathbb{E}[Y_i] = \mathbb{E}[z_i^2x_i] = 0$.
  2. Variance: Assuming each $x_i$ is chosen with probability $P(x_i=1)=k/n$, we have: $$\text{Var}[Y_i] = \mathbb{E}[\text{Var}[Y_i|x_i]]= \frac{k}{n} \cdot 2\sigma^4 = \frac{2k\sigma^4}{n}$$
  3. Since a squared Gaussian is non-negative and has a well-defined bound determined by $\sigma^2$, we can say that $|Y_i| \leq \sigma^2$ almost surely.

Applying Bernstein's inequality gives: $$\mathbb{P}\left(\left|\sum_{i=1}^n Y_i - \mathbb{E}\left[\sum_{i=1}^n Y_i\right]\right| > t\right) \leq 2\exp\left(\frac{-t^2/2}{\sum_{i=1}^n \text{Var}[Y_i] + ct/3}\right)$$

Substituting our established mean, variance, and almost-sure bound, we get the concentration inequality for $Y$: $$\mathbb{P}(|Y - \mathbb{E}[Y]| > t) \leq 2 \exp\left(-\frac{t^2/2}{n (n/k) \cdot 2\sigma^4 + t\sigma^2/3}\right)$$

A basic bound on the expectation, $\mathbb{E}[Y] \leq \binom{n}{k} \cdot k \sigma^2$, is obtained using the union bound. The union bound helps us obtain an initial bound on $\mathbb{E}[Y]$. Since there are $|X_k| = \binom{n}{k}$ vectors in $X_k$, and the squared projection onto any one can't exceed $k\sigma^2$, we get: $$\mathbb{E}[Y] \leq \binom{n}{k} \cdot k \sigma^2$$

Simulations can be used to validate the concentration inequality and explore influences on bound tightness. I ran some simulations and there seemed to be support for the concentration inequality across a range of $n$ and $k$ values The simulations indicate both the average value of $Y$ and the magnitude of the concentration bound generally increase with greater dimensionality $n$ or higher sparsity parameter $k$.

Here is some python code used for the simulation:

import numpy as np

def gen_Y(n, k, sigma, trials):
    results = []
    for _ in range(trials):
        Z = np.random.randn(n) * sigma
        X = np.random.choice([0, 1], size=n, p=[1 - k/n, k/n])
        Y = np.max(np.abs(Z @ X)**2)
        results.append(Y)
    return results

def theoretical_bound(n, k, sigma, confidence_level=0.95):
    exponent = - (confidence_level * n * (n/k) * 2 * sigma**4) / 2 
    bound = np.sqrt(exponent) / (sigma**2 / 3)
    return bound

if __name__ == "__main__":
    n_values = [10, 50, 100]
    k_values = [5, 20, 35] 
    sigma = 1 
    trials = 10000 
    confidence_level = 0.95  

    for n in n_values:
        for k in k_values:
            Y_vals = gen_Y(n, k, sigma, trials)  
            avg_Y = np.mean(Y_vals)
            tail_bound = theoretical_bound(n, k, sigma, confidence_level)
            tail_count = np.sum(np.abs(Y_vals - avg_Y) > tail_bound) 
            tail_prob = tail_count / trials 
            print(f"n: {n}, k: {k}, Avg Y: {avg_Y:.3f}, Tail Bound: {tail_bound:.3f}, Tail Count: {tail_count}, Empirical Tail Prob: {tail_prob:.4f}")
user522465