Comment Lasso s'adapte-t-il à la taille de la matrice de conception?

Si j'ai une matrice de conception , où est le nombre d'observations de dimension , quelle est la complexité de la résolution de avec LASSO, wrt et ? Je pense que la réponse devrait se référer à la façon dont une itération LASSO évolue avec ces paramètres, plutôt qu'à la façon dont le nombre d'itérations (convergence) est mis à l'échelle, sauf indication contraire. n D β = argmin β $X\in\mathcal{R}^{n\times d}$$n$$d$$\hat{\beta}=\text{argmin}_{\beta}\frac{1}{2n} ||X\beta-y||^{2} + \lambda||\beta||_{1}$$n$$d$

J'ai lu cette précédente question sur la complexité de LASSO , mais elle semble en contradiction avec la discussion sur glmnet ici et ici . Je suis conscient qu'il existe de nombreux algorithmes, y compris l'approche GLM de glmnet, mais j'écris un article sur le remplacement d'un composant LASSO par un algorithme parent et j'aimerais inclure une discussion sur la complexité de LASSO en général, en particulier avec et . Je voudrais également connaître la complexité de glmnet dans le cas de base non clairsemé, mais le document référencé est un peu déroutant car toute la complexité de l'algorithme n'est pas explicite.$d$$n$

Les réponses des références,

• pour la régression au moindre angle$\mathcal{O}(d^2n)$
• pour la descente coordonnée$\mathcal{O}(dn)$

, sont corrects.

La différence est que

Les équations LARS sont écrites sous forme fermée et trouvent une solution exacte

$O(d^2n)$

tandis que

$\mathcal{O}(dn)$

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

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

La mise à l'échelle de LARS est un problème impliquant une complexité de calcul. La descente à l'échelle des coordonnées est un problème impliquant la complexité et la convergence des calculs .