Berapakah kompleksitas waktu asimtotik dari regresi Lasso ketika jumlah baris atau kolom bertambah?
sumber
Berapakah kompleksitas waktu asimtotik dari regresi Lasso ketika jumlah baris atau kolom bertambah?
Ingatlah bahwa laso adalah model linier dengan regularisasi .
Menemukan parameter dapat dirumuskan sebagai masalah optimasi yang tidak dibatasi, di mana parameter diberikan oleh
Dalam formasi terbatas parameter diberikan oleh
Yang merupakan masalah pemrograman kuadrat dan dengan demikian polinomial.
Hampir semua rutinitas optimasi cembung, bahkan untuk hal-hal nonlinier yang fleksibel seperti jaringan saraf, bergantung pada perhitungan turunan dari parameter target Anda. Anda tidak dapat mengambil turunan dari . Karena itu Anda mengandalkan teknik yang berbeda. Ada banyak metode untuk menemukan parameter. Berikut makalah tinjauan tentang subjek, Least Squares Optimization dengan Regularisasi L1-Norm . Kompleksitas waktu dari pengoptimalan cembung iteratif agak sulit untuk dianalisis, karena tergantung pada kriteria konvergensi. Secara umum, masalah iteratif bertemu dalam lebih sedikit zaman ketika pengamatan meningkat.
Sementara @JacobMick memberikan ikhtisar yang lebih luas dan tautan ke makalah ulasan, izinkan saya memberikan "jawaban pintasan" (yang dapat dianggap sebagai kasus khusus dari jawabannya).
Biarkan jumlah variabel kandidat (fitur, kolom) menjadi dan ukuran sampel (jumlah pengamatan, baris) menjadi . Pertimbangkan LASSO diimplementasikan menggunakan algoritma LARS ( Efron et al., 2004 ). Kompleksitas komputasi LASSO adalah ( ibid. )K n O(K3+K2n)
Referensi:
sumber