Mengapa menambahkan penalti L1 ke optim R memperlambat segalanya (relatif tanpa penalti atau L2)?

Saya menjalankan beberapa optimasi dengan implementasi BFGS yang optimal. Fungsi objektif sebenarnya adalah algoritma komputasi, bukan hanya matematika. Saya menemukan ketika saya menambahkan penalti L1, segalanya melambat sedikit. Kenapa ini bisa terjadi? Apakah ada sesuatu tentang L1 yang memperlambat segalanya? Lalu bagaimana glmnetimplementasi LASSO begitu cepat?

Pencarian Google cepat menghasilkan panggilan paket "lbfgs" yang "menemukan yang optimal dari suatu tujuan ditambah norma L1 dari parameter masalah" dengan "implementasi cepat dan efisien memori dari optimasi ini, yang terutama cocok untuk masalah dimensi. " Haruskah saya mencari solusi seperti ini?

Saya akan menebak bahwa alasan mengapa menambahkan penalti L1 memperlambat segalanya secara signifikan adalah bahwa penalti L1 tidak dapat dibedakan (yaitu nilai absolut), sedangkan penalti L2 adalah. Ini berarti bahwa permukaan fungsi tidak akan mulus, dan metode kuasi-Newton standar akan memiliki banyak masalah dengan masalah ini. Ingatlah bahwa salah satu cara untuk memikirkan metode kuasi-Newton adalah bahwa ia membuat perkiraan kuadrat dari fungsi dan kemudian proposal awal akan menjadi maksimum dari perkiraan itu. Jika perkiraan kuadrat sangat cocok dengan fungsi target, kita harus mengharapkan proposal mendekati maksimum (atau minimum, tergantung pada bagaimana Anda melihat dunia). Tetapi jika fungsi target Anda tidak dapat dibedakan, perkiraan kuadratik ini mungkin sangat buruk,

Jika Anda telah menemukan paket-R yang mengimplementasikan BFGS untuk hukuman L1, silakan coba. BFGS, secara umum, adalah algoritma yang sangat umum untuk optimasi. Seperti halnya dengan algoritma generik apa pun, akan ada banyak kasus khusus yang tidak berfungsi dengan baik. Algoritma yang khusus dirancang untuk masalah Anda jelas harus lebih baik (dengan asumsi paket sebagus yang diklaim penulis: Saya belum pernah mendengar tentang lbfgs, tapi ada banyak hal hebat yang belum pernah saya dengar. Pembaruan : I telah menggunakan paket lbfgs R, dan implementasi L-BFGS yang mereka miliki cukup bagus! Saya masih belum menggunakan itu algoritma OWL-QN, yang mengacu pada OP).

Jika tidak berhasil, Anda mungkin ingin mencoba metode "Nelder-Mead" dengan R's optim. Itu tidak menggunakan turunan untuk optimasi. Dengan demikian, biasanya akan lebih lambat pada fungsi yang halus tetapi lebih stabil pada fungsi yang tidak mulus seperti yang Anda miliki.

Saya tidak tahu mengapa masalah Anda melambat saat Anda menambahkan penalti . Itu mungkin tergantung pada (1) apa masalahnya; (2) bagaimana Anda mengkodekannya; dan (3) metode optimasi yang Anda gunakan.$L_1$

Saya pikir ada "jawaban tak terucapkan" untuk pertanyaan Anda: solusi paling efisien untuk masalah numerik sering kali dibuat khusus. Algoritma tujuan umum hanya itu: tujuan umum. Solusi khusus untuk masalah khusus akan cenderung bekerja lebih baik, karena kita dapat memberikan pengamatan tentang bagaimana masalah tertentu disajikan dan sifat spesifiknya yang diketahui analis. Untuk pertanyaan spesifik Anda glmnet, ia memiliki sejumlah "trik" yang membuatnya sangat efisien - untuk masalah khusus yang ingin dipecahkannya! The Journal of Software statistik kertas pada memberikan rincian:

1. Optimalisasi untuk semua model (jaring elastis, regresi ridge, dan bukan hanya LASSO) menggunakan keturunan koordinat siklis, yang merupakan cara yang cukup baik untuk menyelesaikan masalah ini.
2. Koefisien dihitung sepanjang jalur untuk rentang nilai . Jadi alih-alih berkeliaran di permukaan respons untuk nilai tunggal dari parameter regularisasi , itu bergerak dari nilai terbesar ke nilai terkecil, menggunakan estimasi koefisien dari solusi sebelumnya sebagai titik awal. Ini mengeksploitasi fakta bahwa estimasi koefisien naik dari yang lebih kecil ke nilai yang lebih besar ketika berkurang; itu tidak harus menyelesaikan masalah yang sama berulang-ulang dari awal yang diinisialisasi secara acak seperti orang akan dengan implementasi naif rutin optimasi standar.$\lambda$$\lambda$$\lambda$

Dan itu dikodekan dalam FORTRAN.

L-BFGS adalah algoritma BFGS memori terbatas. Meskipun memiliki trik yang dapat membuatnya lebih efisien daripada BFGS standar untuk beberapa masalah, tidak jelas apakah masalah yang dipecahkan memiliki kaitan dengan masalah tertentu yang dihadapi. L-BFGS adalah salah satu opsi optimjuga, jadi saya tidak yakin mengapa Anda memerlukan paket tambahan.

Perhatikan bahwa BFGS tergantung pada turunannya, yang dihitung dengan perbedaan hingga ketika bentuk analitik tidak disediakan. Di sinilah Anda mendapatkan masalah, karena penalti tidak dapat dibedakan di mana-mana. Ini tidak hanya berarti bahwa Anda mungkin tidak akan memperkirakan koefisien LASSO tepat pada 0, tetapi bisa mendatangkan malapetaka dengan memperbarui dari iterasi ke iterasi.$L_1$