Skip to main content
3 of 3
added 66 characters in body
bolzano
  • 143
  • 4

Concentration inequalities for sets

Assume that we have a random set $B$ which is constructed by selecting elements from $U = \{ X_1, \dots, X_n \}$ where $X_i$ are independent samples from Gaussians with means $\mu_i$ and variances $\sigma_i^2 = 1$.

I am interested at is selecting a subset of $m \le n$ vectors that are closest to the origin according to their Euclidean norm.

Let $A$ be the set constructed by applying same rule to the set $W = \{ \mathbb E[X_1], \dots, \mathbb E[X_n] \} = \{ \mu_1, \dots, \mu_n \}$. I want to ask if there are such problems in probability/learning theory literature and whether there are concentration (or anti-concentration) bounds for them. More specifically I am interested in bounds that bound the following event

$$\Pr[ |A \ominus B| \ge t]$$

where $A \ominus B = (A \setminus B) \cup (B \setminus A)$ (i.e. the symmetric difference between $A$ and $B$) and $t \in \mathbb N - \{ 0 \}$.

Intuitively I want to find references where the "expected set" $A$ is "close" (or not) to the actual set $B$.

bolzano
  • 143
  • 4