Apakah gradient descent selalu menyatu ke optimal?

Saya bertanya-tanya apakah ada skenario di mana gradient descent tidak menyatu ke minimum.

Saya sadar bahwa gradient descent tidak selalu dijamin akan menyatu dengan global optimal. Saya juga sadar bahwa itu mungkin berbeda dari optimal jika, katakanlah, ukuran langkah terlalu besar. Namun, bagi saya tampaknya, jika itu menyimpang dari beberapa optimal, maka pada akhirnya akan pergi ke optimal lain.

Oleh karena itu, penurunan gradien akan dijamin untuk menyatu ke optimum lokal atau global. Apakah itu benar? Jika tidak, bisakah Anda memberikan contoh kasar?

Gradient Descent adalah algoritma yang dirancang untuk menemukan titik optimal, tetapi titik optimal ini tidak harus bersifat global. Dan ya jika itu terjadi bahwa itu menyimpang dari lokasi lokal mungkin menyatu ke titik optimal lain tetapi kemungkinannya tidak terlalu banyak. Alasannya adalah bahwa ukuran langkah mungkin terlalu besar yang mendorongnya mundur satu titik optimal dan probabilitas bahwa itu berosilasi lebih dari sekadar konvergensi.

Tentang gradient descent ada dua perspektif utama, era pembelajaran mesin dan era pembelajaran yang mendalam. Selama era pembelajaran mesin dianggap bahwa gradient descent akan menemukan optimum lokal / global tetapi di era pembelajaran yang mendalam di mana dimensi fitur input terlalu banyak ditunjukkan dalam praktik bahwa probabilitas semua fitur berada di sana dengan nilai optimal pada satu titik tidak terlalu banyak dan lebih suka melihat lokasi yang optimal dalam fungsi biaya, sebagian besar titik pelana waktu diamati. Ini adalah salah satu alasan bahwa pelatihan dengan banyak data dan periode pelatihan menyebabkan model pembelajaran yang dalam mengungguli algoritma lainnya. Jadi jika Anda melatih model Anda, itu akan menemukan jalan memutar atau akan menemukan jalannya untuk turun dan tidak terjebak dalam poin pelana, tetapi Anda harus memiliki ukuran langkah yang tepat.

Untuk intuisi lainnya, saya sarankan Anda merujuk di sini dan di sini .

Selain dari poin yang Anda sebutkan (konvergensi ke minimum non-global, dan ukuran langkah besar yang mungkin mengarah ke algoritma non-konvergen), "rentang infleksi" mungkin juga menjadi masalah.

Pertimbangkan jenis fungsi "kursi malas" berikut.

Jelas, ini dapat dibangun sehingga ada rentang di tengah di mana gradien adalah vektor 0. Dalam kisaran ini, algoritme dapat macet tanpa batas. Titik belok biasanya tidak dianggap sebagai ekstrema lokal.

$x = 0$$f(x) = x^3$

[Catatan 5 April 2019: Versi baru makalah ini telah diperbarui di arXiv dengan banyak hasil baru. Kami juga memperkenalkan versi backtracking Momentum dan NAG, dan membuktikan konvergensi di bawah asumsi yang sama seperti untuk Backtracking Gradient Descent.

Kode sumber tersedia di GitHub di tautan: https://github.com/hank-nguyen/MBT-optimizer

Kami meningkatkan algoritme untuk mendaftar ke DNN, dan memperoleh kinerja yang lebih baik daripada algoritma canggih seperti MMT, NAG, Adam, Adamax, Adagrad, ...

Fitur paling khusus dari algoritme kami adalah algoritme itu otomatis, Anda tidak perlu melakukan penyesuaian tingkat pembelajaran secara manual sebagai praktik umum. Penyesuaian otomatis otomatis kami berbeda dari Adam, Adamax, Adagrad, ... dan seterusnya. Rincian lebih lanjut ada di koran.

]

Berdasarkan hasil yang sangat baru: Dalam pekerjaan bersama saya di makalah ini https://arxiv.org/abs/1808.05160

$f$

Berdasarkan hal di atas, kami mengusulkan metode baru dalam pembelajaran mendalam yang setara dengan metode mutakhir dan tidak memerlukan penyesuaian tingkat pembelajaran secara manual. ( Singkatnya , idenya adalah bahwa Anda menjalankan backtracking gradient descent dalam jumlah waktu tertentu, sampai Anda melihat bahwa laju pembelajaran, yang berubah dengan setiap iterasi, menjadi stabil. Kami mengharapkan stabilisasi ini, khususnya pada titik kritis yang merupakan C ^ 2 dan non-degenerate, karena hasil konvergensi yang saya sebutkan di atas. Pada saat itu, Anda beralih ke metode gradient descent standar. Silakan lihat kertas yang dikutip untuk lebih detail. Metode ini juga dapat diterapkan pada algoritma optimal lainnya .)

PS Mengenai pertanyaan awal Anda tentang metode penurunan gradien standar, setahu saya hanya dalam kasus di mana turunan peta secara global Lipschitz dan tingkat pembelajaran cukup kecil sehingga metode penurunan gradien standar terbukti menyatu. [Jika kondisi ini tidak terpenuhi, ada contoh tandingan sederhana yang menunjukkan bahwa tidak ada hasil konvergensi yang mungkin terjadi, lihat kertas yang dikutip untuk beberapa.] Dalam makalah yang dikutip di atas, kami berpendapat bahwa dalam jangka panjang metode backtracking gradient descent akan menjadi metode penurunan gradien standar, yang memberikan penjelasan mengapa metode penurunan gradien standar biasanya bekerja dengan baik dalam praktik.