Chernoff con destino a sumas ponderadas

14

Considere , donde lambda_i> 0 e Y_i se distribuye como un estándar normal. ¿Qué tipo de límites de concentración se pueden probar en X, en función de los coeficientes (fijos) lambda_i?X=yoλyoYyo2

Si todos los lambda_i son iguales, entonces este es un límite de Chernoff. El único otro resultado que conozco es un lema de un artículo de Arora y Kannan ("Mezclas de aprendizaje de gaussianos arbitrarios", STOC'01, Lema 13), que demuestra la concentración de la forma , es decir, el límite depende de la suma de los cuadrados de los coeficientes.PAGrosi(X<mi[X]-t)<miXpag(-t2/ /(4 4yoλyo2)

La prueba de su lema es análoga a la prueba habitual del límite de Chernoff. ¿Existen otros límites "canónicos", o una teoría general de qué funciones de los lambda_i son tales que su amplitud asegura una buena concentración exponencial (aquí, la función era simplemente la suma de los cuadrados)? ¿Quizás alguna medida general de entropía?

Una referencia más estándar para el lema de Arora-Kannan también sería genial, si existe.

Thomas
fuente
¿Hasta dónde llegaste en la reproducción de su límite? Esta instancia particular del método exponencial mgf parece requerir algunos límites inteligentes y análisis de casos.
Thomas Ahle

Respuestas:

14

El libro de Dubhashi y Panconesi reúne muchos de estos límites, más numerosos de los que se pueden enumerar aquí. Si le resulta difícil acceder de inmediato, hay una encuesta en línea de límites similares a Chernoff realizada por Chung y Lu

Suresh Venkat
fuente
Gracias, esto se ve muy bien. En particular, el Teorema 3.5 de la encuesta de Chung y Lu parece ser idéntico al lema de Arora-Kannan que estaba afirmando. Tener la suma de lambda_i ^ 2 aparece es natural ya que es simplemente la varianza de X.
Thomas
El enlace de Chung y Lu está muerto. Sin embargo, Internet Archive lo tiene: web.archive.org/web/20070714095538/http://… . El título es "Desigualdades de concentración y desigualdades de martingala: una encuesta" y los autores son Fan Chung y Linyuan Lu.
jbapple