Bagaimana skala Lasso dengan ukuran matriks desain?

Jika saya memiliki matriks desain , di mana adalah jumlah pengamatan dimensi , apa kompleksitas penyelesaian untuk dengan LASSO, wrt dan ? Saya pikir jawabannya harus merujuk pada bagaimana satu iterasi LASSO skala dengan parameter ini, daripada bagaimana jumlah iterasi (konvergensi) skala, kecuali Anda merasa sebaliknya.$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$

Saya telah membaca pertanyaan kompleksitas LASSO ini sebelumnya , tetapi tampaknya bertentangan dengan diskusi tentang glmnet di sini dan di sini . Saya sadar bahwa ada banyak algoritma di luar sana, termasuk pendekatan GLMnet glmnet, tetapi saya menulis makalah tentang mengganti komponen LASSO ke algoritma induk dan ingin memasukkan diskusi tentang kompleksitas LASSO secara umum, terutama dengan dan . Saya juga ingin mengetahui kompleksitas glmnet dalam kasus dasar non-sparse, tetapi makalah yang dirujuk agak membingungkan karena keseluruhan kompleksitas algoritma tidak eksplisit.$d$$n$

Jawaban dari referensi,

• untuk regresi sudut terkecil$\mathcal{O}(d^2n)$
• untuk penurunan koordinat$\mathcal{O}(dn)$

, benar.

Perbedaannya adalah itu

Persamaan LARS ditulis dalam bentuk tertutup dan menemukan solusi yang tepat

$O(d^2n)$

sementara

$\mathcal{O}(dn)$

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

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

Scaling LARS adalah masalah yang melibatkan kompleksitas komputasi. Penskalaan koordinat penurunan adalah masalah yang melibatkan kompleksitas komputasi dan konvergensi.