¿Cómo se escala Lasso con el tamaño de la matriz de diseño?

Si tengo un diseño de matriz , donde n es el número de observaciones de dimensión d , lo que es la complejidad de la solución para β = argmin β $X\in\mathcal{R}^{n\times d}$$n$$d$con LASSO, wrtny? Creo que la respuesta debería referirse a cómounaiteración de LASSO se escala con estos parámetros, en lugar de cómo se escala el número de iteraciones (convergencia), a menos que sienta lo contrario.$\hat{\beta}=\text{argmin}_{\beta}\frac{1}{2n} ||X\beta-y||^{2} + \lambda||\beta||_{1}$$n$$d$

He leído esta pregunta anterior de complejidad de LASSO , pero parece estar en desacuerdo con la discusión sobre glmnet aquí y aquí . Soy consciente de que existen muchos algoritmos, incluido el enfoque GLMnet de glmnet, pero estoy escribiendo un documento sobre el reemplazo de un componente LASSO a un algoritmo padre y me gustaría incluir una discusión sobre la complejidad de LASSO en general, especialmente con y . También me gustaría saber la complejidad de glmnet en el caso básico no disperso, pero el documento de referencia es un poco confuso ya que la complejidad del algoritmo no es explícita.$d$$n$

Las respuestas de las referencias,

• para la regresión de ángulo mínimo$\mathcal{O}(d^2n)$
• para descenso coordinado$\mathcal{O}(dn)$

son correctos

La diferencia es que

Las ecuaciones LARS se escriben en forma cerrada y encuentran una solución exacta

$O(d^2n)$

mientras

$\mathcal{O}(dn)$

$d$$\mathcal{O}((d-k)n+k^2)$$d-k$$k$

$d^2n$$d$$d$$d>>100$$d=100$

Escalar LARS es un problema que involucra complejidad computacional. El descenso de coordenadas de escala es un problema que involucra complejidad computacional y convergencia.