Regresión de alta dimensionalidad: ¿por qué es especial $\log p/n$?

Question

Estoy tratando de informarme sobre la investigación en el área de la regresión de alta dimensionalidad; cuando $p$ es mayor que $n$, es decir, $p >> n$. Parece que el término $\log p/n$ aparece a menudo en cuanto a la tasa de convergencia de los estimadores de regresión.

Por ejemplo, aquí, la ecuación (17) dice que el ajuste de lasso, $\hat{\beta}$ satisface $$ \dfrac{1}{n}\|X\hat{\beta} - X \beta\|_2^2 = O_P \left(\sigma \sqrt{\dfrac{\log p}{n} } \|\beta\|_1\right)\,.$$

Por lo general, esto también implica que $\log p$ debería ser más pequeño que $n.

1. ¿Hay alguna intuición sobre por qué este cociente de $\log p/n$ es tan prominente?
2. También, parece por la literatura que el problema de regresión de alta dimensionalidad se complica cuando $\log p \geq n$. ¿Por qué es así?
3. ¿Hay alguna referencia buena que discuta los problemas con cuán rápido deberían crecer $p$ y $n$ en comparación uno con el otro?

Answer 1

(Se cambió de comentarios para responder lo solicitado por @Greenparker)

Parte 1)

El $\sqrt{\log p}$ término proviene de (Gauss) la concentración de la medida. En particular, si usted tiene $p$ IID Gaussiano variables aleatorias[F1], su máxima es del orden de $\sigma\sqrt{\log p}$ con una probabilidad alta.

El $n^{-1}$ factor viene solo hecho de que usted está buscando en el promedio del error de predicción - es decir, coincide con la $n^{-1}$ en el otro lado - si miraba total error, no estaría allí.

Parte 2)

Esencialmente, usted tiene dos fuerzas que necesita para controlar:

• i) las buenas propiedades de contar con más datos (por lo que queremos $n$ a ser grande);
• ii) las dificultades que han de tener más (irrelevante) características (por eso queremos $p$ a ser pequeño).

En la estadística clásica, por lo general, fix $p$ y deje $n$ ir hasta el infinito: este régimen no es super útil para alta dimensión de la teoría ya que no es (asintóticamente) en el bajo-dimensional régimen de la construcción.

Alternativamente, se podría dejar el $p$ ir hasta el infinito y $n$ permanece fija, pero nuestro error golpes hasta que el problema se convierte en prácticamente imposible. Dependiendo del problema, el error puede ir hasta el infinito, o parar en algunos naturales límite superior (por ejemplo, el 100% de error en la clasificación de error).

Ya que ambos de estos casos son un poco inútiles, que en lugar de considerar $n, p$ tanto va hasta el infinito, de modo que nuestra teoría es relevante (estancias de grandes dimensiones) sin ser apocalíptico (infinito características, finito de datos).

Con dos "perillas" es por lo general más difícil de tener un mando único, lo que soluciona $p=f(n)$ fijos $f$ y deje $n$ ir hasta el infinito (y, por tanto, $p$ va al infinito indirectamente).[F2] La elección de $f$ determina el comportamiento del problema. Por razones que en mi respuesta a la parte 1, resulta que la "maldad" de las características adicionales que sólo crece en la medida en $\log p$, mientras que la "bondad" de la extra de datos crece como $n$.

• Si $\frac{\log p}{n}$ permanece constante (lo que es equivalente, $p=f(n)=Θ(C^n)$ algunos $C$), calcamos el agua y el problema es un lavado (error se mantiene fijo asintóticamente);
• si $\frac{\log p}{n} \to 0$ ($p=o(C^n)$) nos asintóticamente lograr error de cero;
• y si $\frac{\log p}{n}→\infty$ ($p=\omega(C^n)$), el error se llega hasta el infinito.

Este último régimen es a veces llamado "ultra-alta-dimensionales" en la literatura. El término "ultra-alta-dimensional" no tiene una definición rigurosa como lo que yo sé, pero de manera informal sólo "el régimen que se rompe el lazo y similares estimadores."

Podemos demostrar esto con un pequeño estudio de simulación bastante bajo condiciones ideales. Aquí, tomamos la orientación teórica en la elección óptima de $\lambda$ a partir de [BRT09] y pick $\lambda = 3 \sqrt{\log(p)/n}$.

Primero considere un caso en el $p = f(n) = 3n$. Esto es en el 'manejable' grandes dimensiones régimen descrito anteriormente y, como predice la teoría, vemos que el error de predicción converge a cero:

Código para reproducir:

library(glmnet)
library(ggplot2)

# Standard High-Dimensional Asymptotics: log(p) / n -> 0

N <- c(50, 100, 200, 400, 600, 800, 1000, 1100, 1200, 1300)
P <- 3 * N

ERROR_HD <- data.frame()

for(ix in seq_along(N)){
  n <- N[ix]
  p <- P[ix]

  PMSE <- replicate(20, {
    X <- matrix(rnorm(n * p), ncol=p)
    beta <- rep(0, p)
    beta[1:10] <- runif(10, 2, 3)
    y <- X %*% beta + rnorm(n)

    g <- glmnet(X, y)

    ## Cf. Theorem 7.2 of Bickel et al. AOS 37(4), p.1705-1732, 2009. 
    ## lambda ~ 2*\sqrt{2} * \sqrt{\log(p)/n} 
    ## is good scaling for controlling prediction error of the lasso
    err <- X %*% beta - predict(g, newx=X, s=3 * sqrt(log(p)/n))
    mean(err^2)
  })

  ERROR_HD <- rbind(ERROR_HD, data.frame(PMSE=PMSE, n=n, p=p))
}

ggplot(ERROR_HD, aes(x=n, y=PMSE)) + geom_point() + theme_bw() + 
xlab("Number of Samples (n)") + 
ylab("Mean Prediction Error (at observed design points)") + 
ggtitle("Prediction Error Converging to 0 under High-Dim Asymptotics") + 
scale_x_continuous(sec.axis = sec_axis(~ 3 * ., name="Number of Features (p)")) + 
scale_y_log10()

Podemos comparar esto con el caso donde $\frac{\log p}{n}$ se mantiene aproximadamente constante: yo llamo a esto el "límite" de ultra-alta-dimensional régimen, pero eso no es un término estándar:

P <- 10 + ceiling(exp(N/120))

Aquí podemos ver que el error de predicción (usando el mismo diseño que el anterior) los niveles en lugar de seguir a cero.

Si establecemos $P$ a crecer más rápido de lo $e^n$, (por ejemplo, $e^{n^2}$), el error de predicción aumenta sin límite. Estos $e^{n^2}$ es ridículamente rápido y conduce a enormes problemas / problemas numéricos, así que aquí es un poco más lento, pero aún UHD ejemplo:

P <- 10 + ceiling(exp(N^(1.03)/120))

(He utilizado una escasa random $X$ para la velocidad, así que no trates de comparar las cifras con las de otras parcelas directamente) Es difícil ver cualquier repunte en este gráfico, tal vez porque hemos mantenido la UHD crecimiento también de ser "ultra" en el nombre de tiempo de cálculo. El uso de un exponente más grande (como $e^{n^1.5}$) haría que el crecimiento asintótico un poco más claro.

A pesar de lo que he dicho anteriormente y cómo puede aparecer, la ultra-alto-dimensional régimen no es en realidad completamente desesperada (aunque sea cerca), pero se requiere mucho más sofisticadas técnicas que una simple max de variables aleatorias Gaussianas para controlar el error. La necesidad de utilizar estas técnicas complejas es la fuente última de la complejidad que se nota.

No hay ninguna razón especial para pensar que $p, n$ debe crecer "juntos" de alguna manera (es decir, no hay una evidente "mundo real" de la razón para solucionar $p = f(n)$), pero la matemática en general, carece de lenguaje y herramientas para la discusión de los límites con dos "grados de libertad", así que es lo mejor que podemos hacer (por ahora!).

Parte 3)

Me temo que no conozco a ninguno de los libros en la literatura estadística que realmente se centran en el crecimiento de $\log p$ vs $n$ explícitamente. (Puede que haya algo en la resistencia a la compresión de detección de la literatura)

Mi favorito actual de referencia para este tipo de teoría es la de los Capítulos 10 y 11 de Aprendizaje Estadístico con Dispersión [F3] pero por lo general toma el enfoque de considerar $n, p$ fijo y dando finito de muestras (no asintótica) de las propiedades de obtener un resultado "bueno". Esto es en realidad un alcance más poderoso - una vez que tenga el resultado de las $n, p$, es fácil considerar la asymptotics - pero estos resultados son por lo general más difícil derivar, por lo que actualmente sólo tienen ellos por lazo-tipo de estimadores que yo sepa.

Si usted se siente cómodo y dispuesto a profundizar en la investigación de la literatura, me gustaría ver las obras por Jianqing Ventilador y Jinchi Lv, que han hecho la mayor parte de la obra fundacional en la ultra-alto-dimensional problemas. ("Screening" es un buen término para la búsqueda)

[F1] en Realidad, cualquier subgaussian variable aleatoria, pero esto no le agrega mucho a esta discusión.

[F2] también Podemos establecer la "verdad" dispersión $s$ a depender de $n$ ($s = g(n)$) pero eso no cambia demasiado las cosas.

[F3] T. Hastie, R. Tibshirani, y M. Wainwright. Aprendizaje estadístico con la Dispersión. Monografías sobre Estadística y Probabilidad Aplicada 143. CRC Press, 2015. Disponible para descarga gratuita en https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS.pdf

[BRT] Pedro J. Bickel, Ya'acov Ritov, y Alexandre B. Tsybakov. "El Análisis simultáneo de Lazo y de Dantzig Selector." Anales de Estadística 37(4), p. 1705-1732, 2009. http://dx.doi.org/10.1214/08-AOS620