Return to Revisions

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

• Mean: Given $z_i \sim \mathcal{N}(0, \sigma^2)$ and $\mathbf{x}_i$ has a binary distribution with $P(\mathbf{x}_i=1) = \frac{k}{n}$. $$\mathbb{E}[\mathbf{Y}_i] = \mathbb{E}[z_i^2] \mathbb{E}[\mathbf{x}_i] = \sigma^2 \cdot \frac{k}{n}$$

• Variance: We have $$\operatorname{Var}(\mathbf{Y}_i) = \mathbb{E}[z_i^4] \mathbb{E}[\mathbf{x}_i^2] - (\mathbb{E}[z_i^2] \mathbb{E}[\mathbf{x}_i])^2$$ and $$\sum_{i=1}^n \operatorname{Var}[\mathbf{Y}_i] = n \cdot \left( 2\sigma^4 \cdot \frac{k}{n} + \sigma^4 \cdot \frac{k}{n}\left(1 - \frac{k}{n}\right) \right)$$

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] + Mt/3}\right)$$

We can calculate $M$ using the 99th percentile of the chi-squared distribution with 1 degree of freedom, scaled by $\sigma^2$. The 99th percentile of a chi-squared distribution with 1 degree of freedom is approximately $6.635$. Thus, for $z_i^2$, $M = 6.635 \cdot \sigma^2$. Substituting our established mean, variance, and almost-sure bound, we get the concentration inequality for $Y$: $$\mathbb{P}\left(\left|\sum_{i=1}^n \mathbf{Y}_i - \mathbb{E}\left[\sum_{i=1}^n \mathbf{Y}_i\right]\right| \right) \leq 2\exp\left(-\frac{t^2}{2(\sigma^2 + Mt/3)}\right)$$

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. An increase in the sparsity parameter $k$ leads to a higher variability in $Y$, evidenced by the rise in empirical tail probabilities. So basically the more non-zero components in the vector $X$ contribute to greater dispersion in the sum of squared variables, aligning with theoretical expectations. Also, the impact of dimensionality $n$ on the concentration properties of $Y$) is evident, with larger dimensions amplifying the effects of sparsity on variability. The simulations further validate the theoretical predictions provided by Bernstein's inequality, demonstrating its efficacy in bounding deviations from the expected sum.

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  # Generate Gaussian random variables
        X = np.random.choice([0, 1], size=n, p=[1 - k/n, k/n])  # Generate X vector with specified sparsity
        Y = np.sum(Z**2 * X)  # Calculate Y as the sum of Y_i = z_i^2 * x_i
        results.append(Y)
    return results

def theoretical_bound(n, k, sigma, t, M=3):
    # Assuming M as a placeholder for the maximum deviation bound for simplification
    var_Y_i = (k/n) * 2 * sigma**4 + (k/n) * (1 - (k/n)) * sigma**4
    sum_var_Y_i = n * var_Y_i
    bound = 2 * np.exp(-t**2 / (2 * (sum_var_Y_i + M * t / 3)))
    return bound

n_values = [10, 50, 100]
k_values = [5, 20, 35]
sigma = 1
t = 1  # Example threshold value
trials = 10000
simulation_results = []

for n in n_values:
    for k in k_values:
        # Ensure k is not greater than n
        if k <= n:
            Y_vals = gen_Y(n, k, sigma, trials)
            avg_Y = np.mean(Y_vals)
            tail_bound = theoretical_bound(n, k, sigma, t)
            tail_count = np.sum(np.abs(Y_vals - avg_Y) > t)
            tail_prob = tail_count / trials
            simulation_results.append((n, k, avg_Y, tail_bound, tail_count, tail_prob))
        else:
            print(f"Skipping invalid parameters: n = {n}, k = {k} (k must be <= n)")

for result in simulation_results:
    print(f"n: {result[0]}, k: {result[1]}, Avg Y: {result[2]:.3f}, Tail Bound: {result[3]:.3f}, Tail Count: {result[4]}, Empirical Tail Prob: {result[5]:.4f}")