Regresión de alta dimensión: ¿por qué es especial

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

Por ejemplo, aquí , la ecuación (17) dice que el ajuste $\hat{\beta}$ satisface

\frac{1}{n} ‖ X \hat{β} - X β ‖_{2}^{2} = O_{P} (σ \sqrt{\frac{\log p}{n}} ‖ β ‖_{1}) .

$\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 menor que $n$ .

¿Hay alguna intuición de por qué esta relación de $\log p/n$ es tan prominente?
Además, parece que en la literatura el problema de regresión de alta dimensión se complica cuando $\log p \geq n$ . ¿Por que es esto entonces?
¿Existe una buena referencia que discuta los problemas con qué tan rápido deberían crecer $p$ y $n$ comparación entre sí?

regression lasso convergence high-dimensional Greenparker
fuente

1. El

término

proviene de la concentración de medida (gaussiana). En particular, si tienevariables aleatorias gaussianas

IID, su máximo es del orden de

\sqrt{\log p}

$\sqrt{\log p}$

p

$p$

con alta probabilidad. Elfactor

simplemente viene del hecho de que está mirando el error de predicción promedio, es decir, coincide con el

en el otro lado, si observa el error total, no estaría allí.

σ \sqrt{\log p}

$\sigma \sqrt{\log p}$

n^{- 1}

$n^{-1}$

n^{- 1}

$n^{-1}$

mweylandt

2. Esencialmente, tiene dos fuerzas que necesita controlar: i) las buenas propiedades de tener más datos (por lo que queremos que

sea grande); ii) las dificultades tienen más características (irrelevantes) (por lo que queremos que

sea pequeño). En la estadística clásica, por lo general arreglar

y dejamos que

ir hasta el infinito: este régimen no es muy útil para la teoría de alta dimensión, ya que es en el régimen de bajas dimensiones de la construcción. Alternativamente, podríamos dejar que

vaya al infinito

permanezca fijo, pero luego nuestro error simplemente explota y llega al infinito.

n

$n$

p

$p$

p

$p$

n

$n$

p

$p$

n

$n$

mweylandt

Por lo tanto, debemos considerar que

van al infinito para que nuestra teoría sea relevante (se mantenga en alta dimensión) sin ser apocalíptica (características infinitas, datos finitos). Tener dos "botones" es generalmente más difícil de lo que tiene un solo mando, por lo que fijamos

para algunos

y dejamos que

vamos a infinito (y por lo tanto

indirectamente). La elección de

determina el comportamiento del problema. Por razones en mi respuesta a Q1, resulta que la "maldad" de las características adicionales solo crece como

mientras que la "bondad" de los datos adicionales crece como

n, p

$n, p$

p = f (n)

$p = f(n)$

f

$f$

n

$n$

p

$p$

f

$f$

\log p

$\log p$

n

$n$

mweylandt

Por lo tanto, si

mantiene constante (equivalentemente,

para algo de

), pisamos el agua. Si

(

) asintóticamente logramos un error cero. Y si

(

\log p / n

$\log p / n$

p = f (n) = Θ (C^{n})

$p = f(n) = \Theta(C^n)$

C

$C$

\log p / n \to 0

$\log p / n \to 0$

p = o (C^{n})

$p = o(C^n)$

\log p / n \to \infty

$\log p / n \to \infty$

p = ω (C^{n})

$p = \omega(C^n)$ ), el error finalmente llega al infinito. Este último régimen a veces se llama "ultradimensional" en la literatura. No es inútil (aunque está cerca), pero requiere técnicas mucho más sofisticadas que un simple máximo de gaussianos para controlar el error. La necesidad de utilizar estas técnicas complejas es la fuente principal de la complejidad que observa.

mweylandt

@mweylandt Gracias, estos comentarios son realmente útiles. ¿Podrías convertirlos en una respuesta oficial, para que pueda leerlos de manera más coherente y votarte?

Greenparker

(Movido de comentarios a una respuesta solicitada por @Greenparker)

Parte 1)

El término proviene de la concentración de medida (gaussiana). En particular, si tieneIID Gaussian variables aleatorias [F1], su máximo está en el orden de $\sqrt{\log p}$ $p$ con alta probabilidad. $\sigma\sqrt{\log p}$

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

Parte 2)

Esencialmente, tienes dos fuerzas que necesitas controlar:

i) las buenas propiedades de tener más datos (por lo que queremos que sea grande); $n$
ii) las dificultades tienen más características (irrelevantes) (por lo que queremos que sea pequeño). $p$

En la estadística clásica, por lo general arreglar y dejamos que ir hasta el infinito: este régimen no es muy útil para la teoría de alta dimensión, ya que es (asintótica) en el régimen de bajas dimensiones de la construcción . $p$ $n$

Alternativamente, podríamos dejar que vaya al infinito permanezca fijo, pero luego nuestro error simplemente explota a medida que el problema se vuelve esencialmente imposible. Dependiendo del problema, el error puede llegar al infinito o detenerse en algún límite superior natural ( por ejemplo , error de clasificación errónea del 100%). $p$ $n$

Dado que ambos casos son un poco inútiles, consideramos que van al infinito, por lo que nuestra teoría es relevante (se mantiene en alta dimensión) sin ser apocalíptica (características infinitas, datos finitos). $n, p$

Tener dos "botones" es generalmente más difícil de lo que tiene un solo mando, por lo que fijamos para algunos fija y dejamos que vamos a infinito (y por lo tanto tiende a infinito indirectamente). [F2] La elección de determina el comportamiento del problema. Por razones en mi respuesta a la parte 1, resulta que la "maldad" de las características adicionales solo crece como mientras que la "bondad" de los datos adicionales crece como . $p=f(n)$ $f$ $n$ $p$ $f$ $\log p$ $n$

Si permanece constante (equivalentemente,para algo de), pisamos agua y el problema es un lavado (el error permanece fijo asintóticamente); $\frac{\log p}{n}$ $p=f(n)=Θ(C^n)$ $C$
si () logramos asintóticamente cero error; $\frac{\log p}{n} \to 0$ $p=o(C^n)$
y si (), el error finalmente llega al infinito. $\frac{\log p}{n}→\infty$ $p=\omega(C^n)$

Este último régimen a veces se llama "ultradimensional" en la literatura. El término "ultradimensional" no tiene una definición rigurosa hasta donde yo sé, pero es informalmente solo "el régimen que rompe el lazo y estimadores similares".

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

$p = f(n) = 3n$

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()

$\frac{\log p}{n}$

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

Aquí vemos que el error de predicción (usando el mismo diseño que el anterior) se nivela en lugar de continuar a cero.

$P$ $e^n$ $e^{n^2}$ $e^{n^2}$

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

(Usé un poco aleatorio $X$ para la velocidad, así que no intentes comparar los números con los otros gráficos directamente) Es difícil ver algún repunte en este gráfico, tal vez porque evitamos que el crecimiento de UHD sea demasiado "ultra" en nombre del tiempo computacional. Usando un exponente más grande (como $e^{n^1.5}$ ) haría el crecimiento asintótico un poco más claro.

A pesar de lo que dije anteriormente y de cómo puede parecer, el régimen de dimensiones ultraaltas en realidad no es completamente inútil (aunque está cerca), pero requiere técnicas mucho más sofisticadas que un simple máximo de variables aleatorias gaussianas para controlar el error. La necesidad de utilizar estas técnicas complejas es la fuente principal de la complejidad que observa.

No hay una razón particular para pensar que $p, n$ debería crecer "juntos" de cualquier manera ( es decir , no hay una razón obvia "del mundo real" para arreglar $p = f(n)$ ), pero las matemáticas generalmente carecen de lenguaje y herramientas para discutir los límites con dos "grados de libertad", por lo que es lo mejor que podemos hacer (¡por ahora!).

Parte 3)

Me temo que no conozco ningún libro en la literatura estadística que realmente se centre en el crecimiento de $\log p$ vs $n$ explícitamente. (Puede haber algo en la literatura de detección de compresión)

Mi referencia favorita actual para este tipo de teoría son los Capítulos 10 y 11 de Aprendizaje estadístico con dispersión [F3], pero generalmente toma el enfoque de considerar $n, p$ fijo y dando propiedades de muestra finita (no asintótica) para obtener un "buen" resultado. Este es realmente un enfoque más poderoso, una vez que tiene el resultado para cualquier $n, p$ , es fácil considerar los asintóticos, pero estos resultados son generalmente más difíciles de obtener, por lo que hasta ahora solo los tengo para estimadores de tipo lazo.

Si se siente cómodo y dispuesto a profundizar en la literatura de investigación, miraría los trabajos de Jianqing Fan y Jinchi Lv, que han realizado la mayor parte del trabajo fundamental sobre problemas de dimensiones ultraaltas. ("Detección" es un buen término para buscar)

[F1] En realidad, cualquier variable aleatoria subgaussiana , pero esto no agrega mucho a esta discusión.

[F2] También podríamos establecer la escasez "verdadera" $s$ 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 escasez. Monografías sobre estadísticas y probabilidad aplicada 143. CRC Press, 2015. Disponible para descarga gratuita en https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS.pdf

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

mweylandt
fuente

(+1) Gracias, esto es muy útil y, de hecho, merece la recompensa (esperaré un poco antes de otorgar la recompensa para mantener el interés). Una pregunta: ¿puedes ampliar más sobre "

\log p / n

$\log p/n$ se mantiene constante, pisamos el agua "? Importa si esta constante es más de 1 o menos de 1?

Greenparker

Claro, he agregado un pequeño estudio de simulación para aclarar la dinámica de "pisar el agua". En términos de dinámica asintótica, no importa cuál sea la constante, pero el error será proporcional a esa constante, por lo que, por supuesto, me gustaría que sea más pequeño ceteris paribus (esto es equivalente a tener más

n

$n$ Lo cual es siempre algo bueno).

mweylandt

Regresión de alta dimensión: ¿por qué es especial

Respuestas: