Sobre la complejidad muestral de la estimación de la media en $\ell_p$ -norm

Question

Sea $1\leq p\leq \infty$ , dejemos que ${\cal D}$ sea una distribución sobre $\mathbb{R}^d$ y suponemos que su soporte está contenido en la unidad $p$ -ball. ¿Cuál es el número mínimo $n$ de muestras i.i.d. $W_i\sim {\cal D}$ , $i=1,\ldots,n$ necesario para calcular un estimador $\tilde W$ de la media con la siguiente garantía?

$$ \mathbb{P}\{ \| \tilde W- \mathbb{E}_{W\sim {\cal D}}[W]\|_p \leq \varepsilon \} \geq 1-\delta. $$

Me interesa especialmente cómo $n$ depende de $p$ , $d$ y $\epsilon$ .

Sospecho que esto debe haberse estudiado en el pasado, pero no he sido capaz de encontrar una referencia. También podrían ser útiles otras garantías (por ejemplo, en expectativa).

Por último, esta pregunta puede plantearse de forma más general, considerando una norma arbitraria, en lugar de $\|\cdot\|_p$ . Cualquier resultado en este sentido sería muy útil.

Answer 1

Un tema estrechamente relacionado es el de desigualdades de concentración que te dan un límite (del tipo que estás buscando) que también depende del número de muestras (entre otras cosas). Concretamente, el concepto de Complejidad Rademacher es una herramienta estándar para abordar este tipo de problemas. La complejidad de Rademacher puede entenderse como una prueba de permutación, en la que se cambian las etiquetas aleatoriamente. Cuando se aplica al problema de estimar la media, el límite indica la probabilidad de acercarse a la media real por azar (la concentración de las muestras en torno a la media y, por tanto, la estabilidad de las estimaciones basadas en diferentes muestras).

Para ser más específicos, para una muestra, $X=(x_{i})$ de tamaño $l$ extraídos i.i.d. de una distribución de probabilidad, $D$ y para una clase de función de valor real, $F$ con dominio $X$ El empírico La complejidad de Rademacher es la variable aleatoria definida como, $$ \hat{R}_{l}(F) = E_{\sigma}\left[sup_{f \in F}\left|\frac{2}{l}\sum_{i=1}^{l}\sigma_{i}f(x_{i})\right|X\right] $$ donde $\sigma = (\sigma_{1},...,\sigma_{l})$ son uniformes independientes $\pm1$ -variables aleatorias valoradas. La complejidad de Rademacher es, $$ R_{l}(F) = E_{S \sim D}[\hat{R}_{l}(F)] = E_{S\sigma}\left[sup_{f \in F}\left|\frac{2}{l}\sum_{i=1}^{l}\sigma_{i}f(x_{i})\right|X\right] $$

El sup significa que busca la mayor correlación posible con el ruido aleatorio. Ahora bien, este concepto es relevante por el siguiente teorema,

Dadas las condiciones anteriores, suponiendo que $F$ es la clase de mapeos de $X$ al intervalo $[0,1]$ y que $(z_{i})$ sea una muestra de tamaño $l$ . Si arreglas $\delta \in (0,1)$ entonces con probabilidad $1-\delta$ sobre extracciones aleatorias de tamaño $l$ cada $f \in F$ satisface,

$$ E[f(z)] \leq \hat{E}[f(z)] + R_{l}(F) + \sqrt{\frac{ln(2/\delta)}{2l}} \leq \hat{E}[f(z)] + \hat{R}_{l}(F) + 3\sqrt{\frac{ln(2/\delta)}{2l}} $$

Observe que el sombrero se utiliza para indicar la expectativa empírica medida en una muestra concreta.

La idea es encontrar tal familia de f's y utilizar el teorema. Dado que $D$ tiene un soporte compacto, sabe que $(W-E[W])^{2}/R$ está limitada en $[0,1]$ donde $R$ es el radio de la bola.

Utilizando las propiedades de la complejidad de Rademacher y un segundo teorema que le da la complejidad de Rademacher para la predicción lineal (los detalles se pueden encontrar aquí y con todo detalle aquí ), se obtiene el siguiente límite para su probabilidad

$$ \sqrt{\frac{2R^{2}}{l}}\left(\sqrt2 + \sqrt{ln\frac{1}{\delta}}\right) $$

P.D. Acabo de darme cuenta de que te referías a la p-norma. Pero aún así, puedes utilizar la Desigualdad en Khintchine para limitar esa cantidad con la norma 2.

Answer 2

Permítanme que siga con esta pregunta y respuesta. Efectivamente, la conexión con la complejidad de Rademacher de las funciones lineales del cuerpo dual puede utilizarse para proporcionar límites superiores para el problema. Pero esto no es exactamente lo que Cristóbal y yo preguntamos. (Por no mencionar que la pregunta que nos hacemos es aún más fundamental).

La complejidad de Rademacher caracteriza la tasa de convergencia de la media empírica a la media real. Por tanto, puede dar un límite superior. Este límite superior es estricto en muchos casos, pero nos interesan los límites que se aplican a cualquier estimador de la media.

También nos interesan los resultados que van más allá de la simple $L_2$ (o incluso $L_p$ para $p>2$ casos contemplados en la respuesta, sino normas generales definidas por un cuerpo convexo centrado en el origen.

Answer 3

Gracias a todos por las respuestas. De hecho, la complejidad de Rademacher es una herramienta útil para obtener límites superiores. Sin embargo, la complejidad muestral también puede depender de la geometría del cuerpo convexo que nos interesa. En este sentido, se pueden utilizar las ideas de suavidad uniforme y convexidad uniforme de la teoría de espacios de Banach para obtener los índices adecuados. Esto es algo bien conocido en algunos campos, pero no he encontrado una referencia concisa, así que hemos incluido el análisis en nuestro artículo (véase el apéndice B en http://arxiv.org/pdf/1512.09170v1.pdf )

Dos cuestiones que aún me quedan por resolver son, en primer lugar: ¿Cómo derivar límites inferiores de la complejidad muestral de la media empírica basándose en la complejidad de Rademacher? Esto supongo que es estándar, pero no he encontrado ninguna referencia. La segunda pregunta es: ¿Existen ejemplos en los que la media empírica no proporcione la mejor complejidad muestral para la estimación de la media?