Studi teoritis metode penurunan koordinat

Saya sedang menyiapkan beberapa materi kursus tentang heuristik untuk optimisasi, dan telah mencari metode penurunan koordinat. Pengaturan di sini adalah fungsi multivarian yang ingin Anda optimalkan. memiliki properti yang terbatas pada variabel tunggal mana pun, mudah dioptimalkan. Jadi mengoordinasikan keturunan hasil dengan bersepeda melalui koordinat, memperbaiki semua kecuali yang dipilih dan meminimalkan sepanjang koordinat itu. Akhirnya, perbaikan melambat dan Anda berhenti.$f$$f$

Pertanyaan saya adalah: apakah ada studi teoritis tentang metode penurunan koordinat yang berbicara tentang tingkat konvergensi, dan properti yang membuat metode ini bekerja dengan baik, dan seterusnya? Jelas, saya tidak mengharapkan jawaban yang sepenuhnya umum, tetapi jawaban yang menerangi kasus-kasus di mana heuristik bekerja dengan baik akan sangat membantu.$f$

Selain itu: teknik optimasi bolak-balik yang digunakan untuk berarti dapat dilihat sebagai contoh penurunan koordinat, dan algoritma Frank-Wolfe tampaknya terkait (tetapi bukan contoh langsung dari kerangka kerja)$k$

(Edit catatan: Saya mengatur ulang ini setelah panik panjangnya.)

Literatur tentang penurunan koordinat dapat sedikit sulit untuk dilacak. Inilah beberapa alasan untuk ini.

1. Banyak sifat yang diketahui dari metode koordinat ditangkap dalam teorema payung untuk metode keturunan yang lebih umum. Dua contoh dari ini, diberikan di bawah ini, adalah konvergensi cepat di bawah cembung yang kuat (berlaku untuk semua$l^p$

2. Penamaan bukan standar. Bahkan istilah "keturunan paling curam" tidak standar. Anda mungkin berhasil googling salah satu istilah "keturunan koordinat siklik", "keturunan koordinat", "Gauss-Seidel", "Gauss-Southwell". penggunaannya tidak konsisten.

3. $n$$n$

$\mathcal O(\ln (1/\epsilon))$$l^p$

Kendala. Tanpa cembung yang kuat, Anda harus mulai sedikit berhati-hati. Anda tidak mengatakan apa-apa tentang kendala, dan dengan demikian secara umum, infimum mungkin tidak dapat dicapai. Saya akan mengatakan secara singkat pada topik kendala bahwa pendekatan standar (dengan metode keturunan) adalah memproyeksikan ke kendala Anda mengatur setiap iterasi untuk mempertahankan kelayakan, atau menggunakan hambatan untuk menggulung kendala ke dalam fungsi tujuan Anda. Dalam kasus yang pertama, saya tidak tahu bagaimana cara bermain dengan keturunan koordinat; dalam kasus yang terakhir, ia bekerja dengan baik dengan penurunan koordinat, dan hambatan ini bisa sangat cembung.

Lebih khusus untuk mengoordinasikan metode, daripada memproyeksikan, banyak orang hanya membuat pembaruan koordinat mempertahankan kelayakan: ini misalnya persis dengan algoritma Frank-Wolfe dan variannya (yaitu, menggunakannya untuk menyelesaikan SDP).

Saya juga akan mencatat secara singkat bahwa algoritma SMO untuk SVM dapat dilihat sebagai metode penurunan koordinat, di mana Anda memperbarui dua variabel sekaligus, dan mempertahankan batasan kelayakan saat Anda melakukannya. Pilihan variabel bersifat heuristik dalam metode ini, sehingga jaminannya benar-benar hanya jaminan siklik. Saya tidak yakin apakah koneksi ini muncul dalam literatur standar; Saya belajar tentang metode SMO dari catatan mata kuliah Andrew Ng, dan ternyata cukup bersih.

$n$

$\mathcal O(\ln(1/\epsilon))$ .

Ada beberapa hasil terbaru tentang penurunan koordinat, saya telah melihat hal-hal di arXiv. Juga, luo & tseng memiliki beberapa kertas baru. tapi ini hal utama.

$\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$$g$$(a_i)_1^m$$\lambda$$\exp(1/\epsilon^2)$$\mathcal O(1/\epsilon)$

Masalah dengan pembaruan yang tepat. Juga, sangat sering terjadi bahwa Anda tidak memiliki pembaruan koordinat tunggal formulir tertutup. Atau solusi yang tepat mungkin tidak ada. Tetapi untungnya, ada banyak dan banyak metode pencarian garis yang pada dasarnya mendapatkan jaminan yang sama sebagai solusi tepat. Bahan ini dapat ditemukan dalam teks pemrograman nonlinier standar, misalnya dalam buku Bertsekas atau Nocedal & Wright yang disebutkan di atas.

Vis a vis paragraf kedua Anda: ketika ini bekerja dengan baik. Pertama, banyak analisis yang disebutkan di atas untuk pekerjaan gradien untuk penurunan koordinat. Jadi mengapa tidak selalu menggunakan keturunan koordinat? Jawabannya adalah bahwa untuk banyak masalah di mana gradient descent dapat diterapkan, Anda juga dapat menggunakan metode Newton, di mana konvergensi superior dapat dibuktikan. Saya tidak tahu cara untuk mendapatkan keuntungan Newton dengan koordinat turun. Juga, biaya tinggi metode Newton dapat dikurangi dengan pembaruan Quasinewton (lihat misalnya LBFGS).

$l^0$$k$$k$$k$$k$$f$

Saya sarankan mencari di sini, kami telah melakukan beberapa pekerjaan di bidang ini:

http://arxiv.org/abs/1107.2848

Bersulang

Peter

Kami baru saja memasang makalah di arXiv ( http://arxiv.org/abs/1201.1214 ) yang membuktikan batas bawah generik untuk "algoritma statistik" untuk masalah pengoptimalan, dengan setiap "masalah" memiliki batas bawah sendiri tergantung pada berbagai sifat.

Turunkan koordinat (dan hampir semua hal lain yang dapat kita pikirkan) dapat dilihat sebagai algoritma statistik dalam kerangka kerja kami, jadi semoga makalah ini memiliki beberapa hasil yang akan menarik bagi Anda.

Perhatikan bahwa dalam optimasi, "tingkat konvergensi" biasanya berarti perilaku asimptotik. Artinya, tarif hanya berlaku untuk lingkungan solusi optimal. Dalam hal itu, Luo & Tseng memang membuktikan tingkat konvergensi linier untuk beberapa fungsi objektif non-sangat cembung dalam makalah "Pada konvergensi metode penurunan koordinat untuk minimalisasi cembung dibedakan".

Tingkat konvergensi non-asimptotik, alias "kompleksitas iterasi", umumnya lebih berguna dalam membatasi jumlah iterasi dari algoritma miniisasi. Untuk fungsi objektif yang sangat cembung, kompleksitas iterasi dari metode penurunan koordinat siklik telah ditunjukkan dalam batas Kesalahan Luo & Tseng dan analisis konvergensi dari metode penurunan yang layak: pendekatan umum jika digunakan batas kesalahan global. Untuk masalah yang tidak terlalu cembung, kami memiliki beberapa hasil baru di Kompleksitas Iterasi Metode Keturunan Layak untuk Optimasi Cembung. Untuk lebih spesifik, kami telah menunjukkan kompleksitas iterasi untuk metode penurunan koordinat siklik pada masalah seperti bentuk ganda metode SVM dan Gauss-Seidel. Selanjutnya, hasilnya juga mencakup metode keturunan layak lainnya termasuk gradien keturunan dan teman-teman.