Apa kompleksitas waktu dari regresi Lasso?

14

Berapakah kompleksitas waktu asimtotik dari regresi Lasso ketika jumlah baris atau kolom bertambah?

pengguna2763361
sumber

Jawaban:

4

Ingatlah bahwa laso adalah model linier dengan regularisasi .l1

Menemukan parameter dapat dirumuskan sebagai masalah optimasi yang tidak dibatasi, di mana parameter diberikan oleh

argminβ||yXβ||2+α||β||1

Dalam formasi terbatas parameter diberikan oleh

argminβ||yXβ||2s.t.||β||1<α

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.α||w||1

Jessica Collins
sumber
4
Beberapa hal: mengatakan bahwa masalah adalah "polinomial" tidak terlalu membantu, kecuali mungkin Anda sedang melihat beberapa jenis masalah kombinatorik (yang biasanya eksponensial). Kedua, menghitung derivatif tidak selalu merupakan langkah pembatas. Ketiga, biasanya ketika membahas kompleksitas waktu dari suatu algoritma iteratif, orang biasanya melihat biaya per langkah , dan dengan demikian tidak tergantung pada kriteria konvergensi. Akhirnya, tidak biasanya terjadi lebih banyak pengamatan = lebih sedikit iterasi.
Cliff AB
13

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. )KnO(K3+K2n)

  • Untuk , dan kompleksitas komputasional LASSO adalah , yang sama dengan regresi dengan variabel ( Efron et al., 2004 , hal 443-444; juga dikutip dalam Schmidt, 2005 , bagian 2.4; untuk kompleksitas komputasi dari suatu regresi, lihat posting ini ).K<nK3<K2nO(K2n)K
  • Untuk , dan kompleksitas komputasional LASSO adalah ( Efron et al., 2004 ).KnK3K2nO(K3)

Referensi:

Richard Hardy
sumber
Richard, dapatkah Anda mengomentari kompleksitas iterasi untuk pendekatan GLM di sini stats.stackexchange.com/questions/280304/… ?
rnoodle
@ moodle, saya tidak bisa tanpa menggali jauh ke dalam (yang saya tidak punya waktu untuk saat ini), tetapi +1 untuk pertanyaan Anda.
Richard Hardy
Saya sudah melihat, tetapi tidak jelas - akan baik untuk mendapatkan sepasang mata kedua di atasnya. Jadi ada kompleksitas iterasi dan kompleksitas konvergensi penuh, dan saya pikir literatur agak kabur kadang-kadang atas definisi. Pada dasarnya saya memiliki algoritma yang menggunakan lasso solver dalam posisi yang sangat kritis sehingga kompleksitas algoritma saya sangat tergantung pada solver. Akan baik untuk mengatasi ini. Bersulang! Saya akan memberi hadiah untuk input Anda
rnoodle
@rnoodle, saya sangat ragu saya akan dapat membantu Anda di sana dalam waktu dekat, tetapi hadiah pasti dapat menarik orang lain yang lebih tahu. Semoga berhasil!
Richard Hardy