¿Cuál es la asintótica en el tiempo la complejidad de Lazo de regresión como el número de filas o columnas que crece?
Respuesta
¿Demasiados anuncios?
Recordemos que el lazo es un modelo lineal con un $l_1$ regularización.
Encontrar los parámetros puede ser formulado como un problema de optimización sin restricciones, donde los parámetros están dados por
$argmin_\beta ||y - X\beta||^2 + \alpha||\beta||_1$.
En el restringido formuation los parámetros están dados por
$argmin_\beta ||y - X\beta||^2 s.t.||\beta||_1 < \alpha$
Que es un problema de programación cuadrática y por lo tanto el polinomio.
Casi todas las rutinas de optimización convexa, incluso para los flexibles no lineal cosas como las redes neuronales, se basan en calcular la derivada de su destino w.r.t. los parámetros. Usted no puede tomar la derivada de $\alpha||w||_1$, aunque. Como tal, usted depende de diferentes técnicas. Hay muchos métodos para encontrar los parámetros. Aquí está un artículo de revisión sobre el tema, Menos Plazas de Optimización con L1-Norma de Regularización. El tiempo-la complejidad del proceso iterativo de optimización convexa es un poco complicado de analizar, ya que depende de un criterio de convergencia. En general, iterativo problemas que convergen en un menor número de épocas como las observaciones de aumento.
