Velocidad, gastos computacionales de PCA, LASSO, red elástica

Question

Estoy intentando comparar la complejidad computacional / velocidad de estimación de tres grupos de métodos para la regresión lineal, tal como se distinguen en Hastie et al. "Elements of Statistical Learning" (2ª ed.), Capítulo 3:

1. Selección de subconjuntos
2. Métodos de contracción
3. Métodos que utilizan direcciones de entrada derivadas (PCR, PLS)

La comparación puede ser muy aproximada, sólo para dar una idea. Deduzco que las respuestas pueden depender de la dimensión del problema y de cómo se ajuste a la arquitectura del ordenador, así que para un ejemplo concreto se puede considerar un tamaño de muestra de 500 y 50 regresores candidatos. Me interesa sobre todo la motivación que subyace a la complejidad computacional / velocidad de estimación, pero no el tiempo que se tardaría en un determinado procesador para el ejemplo dado.

Answer 1

Grupo 1 :
La complejidad/velocidad del grupo 1. no parece demasiado difícil de averiguar si se utilizan algoritmos de fuerza bruta (aunque puede haber alternativas más eficientes, como el algoritmo "leaps and bounds"). Por ejemplo, la selección completa de subconjuntos requerirá $2^K$ regresiones que deben ajustarse a partir de un conjunto de $K$ características del candidato. Un ajuste OLS de una regresión lineal tiene la complejidad de $\mathcal{O}(K^2 n)$ (según esta entrada ) donde $n$ es el tamaño de la muestra. Por lo tanto, la complejidad total de la selección de subconjuntos completa por fuerza bruta debería ser $\mathcal{O}(2^K K^2 n)$ .

Grupo 2 :
La complejidad/velocidad del grupo 2. se analiza en las secciones 3.8 y 3.9 del libro. Por ejemplo, cresta regresión con una penalización determinada $\lambda$ tiene la misma complejidad computacional que una regresión normal. Dado que $\lambda$ debe hallarse mediante validación cruzada, la carga computacional aumenta linealmente en el número de divisiones de datos utilizadas en la validación cruzada (digamos, $S$ ). Si el $\lambda$ rejilla tiene $L$ puntos, la complejidad total de la regresión ridge avec afinar la $\lambda$ será $\mathcal{O}(LSK^2 n)$ .
Se habla bastante de LASSO en el libro, pero no he podido encontrar exactamente lo que necesito. Sin embargo, encontré en la p. 443 de Efron et al. "Regresión de ángulo mínimo" (2004) que la complejidad LASSO para un determinado $\lambda$ es la misma que la complejidad de un ajuste OLS de regresión lineal si se utiliza el método LARS. Entonces, la complejidad total de LASSO con ajuste del $\lambda$ será $\mathcal{O}(LSK^2 n)$ . (No leí ese documento con atención, así que por favor corríjanme si me equivoqué).
Red elástica combina cresta y LASSO; los dos tienen la misma complejidad computacional; por lo tanto, la complejidad de la red elástica debería ser $\mathcal{O}(ALSK^2 n)$ donde $A$ es el tamaño de la cuadrícula del parámetro de ajuste $\alpha$ que equilibra las ponderaciones de la cresta frente a LASSO.

Grupo 3 :
I todavía echo de menos cualquier nota sobre la complejidad/velocidad para el grupo 3. que consiste en la regresión de componentes principales (PCR) y los mínimos cuadrados parciales (PLS).

Answer 2

Es sólo para una parte de la pregunta 2 del grupo 3 (PLS), pero puede ser informativo: Srinivasan et al (2010, informe técnico; véase https://www.umiacs.umd.edu/~balajiv/Papers/UMD_CS_TR_Pls_Gpu.pdf ) realizaron algunas mediciones sobre PLS utilizando el algoritmo NIPALS -declarando que la complejidad temporal (y espacial) de este algoritmo es O(dN)- para la extracción e inclusión de estos en diferentes modelos para a) detección de humanos en imágenes, y b) reconocimiento facial. Las mediciones se realizaron utilizando su propia implementación basada en GPU.