Keturunan gradien pada fungsi non-cembung

Situasi apa yang kita ketahui di mana gradient descent dapat ditunjukkan untuk menyatu (baik ke titik kritis atau ke minimum lokal / global) untuk fungsi non-cembung?

Untuk SGD pada fungsi non-cembung, satu jenis bukti telah ditinjau di sini, http://www.cs.cornell.edu/courses/cs6787/2017fa/Lecture7.pdf

Lihat lampiran B1 di https://web.stanford.edu/~boyd/cvxbook/ .

Fungsi dan batasannya dapat berupa non-cembung dalam Program Kuadratik Terkendali Kuadratik, dan Anda masih dapat melihat dualitas yang kuat (dijamin jika kondisi teknis yang dikenal sebagai persyaratan kualifikasi kendala Slater berlaku)

Dualitas yang kuat dalam arti yang lemah berarti kita dapat menyelesaikan masalah optimisasi. Dari masalah asli yang disebut primal, Anda dapat merumuskan masalah alternatif yang disebut masalah ganda. Solusi masalah ganda memberikan solusi yang dalam arti tertentu adalah "batas bawah terbaik" untuk masalah awal Anda

Dalam banyak masalah optimasi yang non-cembung, akan ada kesenjangan antara solusi primal dan ganda yaitu, batas bawah bisa jauh di bawah nilai optimal yang sebenarnya (bahkan tak terhingga negatif). Dalam beberapa kasus khusus, ikatannya ketat. Kasus khusus ini adalah kasus di mana kita memiliki dualitas yang kuat.

Algoritme adalah TEKNIK yang digunakan untuk sampai pada titik optimal. Solusi optimal dan kemampuan kita untuk menemukannya tergantung pada GEOMETRI masalah (yang merupakan dualitas apa yang mencoba untuk sampai pada). Secara longgar, analisis mengatakan bahwa jika optimasi yang diatur dengan benar akan menyatu ke minimum.

Secara umum, gradient descent akan konvergen ke titik stasioner. Poin ini dapat berupa minimum lokal / minimum global / minimum sadel. Dalam hanya beberapa kasus non-cembung kami dapat menjamin apa yang menyatu

Dalam jawaban ini saya akan mengeksplorasi dua makalah yang menarik dan relevan yang diangkat dalam komentar. Sebelum melakukannya, saya akan berusaha untuk memformalkan masalah dan menjelaskan beberapa asumsi dan definisi. Saya mulai dengan makalah 2016 oleh Lee et al.

Kami berupaya meminimalkan fungsi non-cembung $f: \mathbb{R}^d \to \mathbb{R}$yang dibatasi di bawah ini. Kami mengharuskannya dua kali dapat dibedakan. Kami menggunakan algoritma gradient descent dari formulir:

$\pmb{x}_{t+1} = \pmb{x}_t - \alpha\nabla f(\pmb{x}_t)$.

Selain itu, kami memiliki persyaratan berikut:

$\| \nabla f(\pmb{x}_1)-\nabla f(\pmb{x}_2) \| \leq \ell \| \pmb{x}_1 - \pmb{x}_2 \|, \quad \text{for all } \pmb{x}_1, \pmb{x}_2$.

Artinya, kita membutuhkan fungsi kita menjadi -Lipschitz dalam turunan pertamanya. Dalam bahasa Inggris ini berarti gagasan bahwa gradien kami tidak dapat berubah terlalu cepat di mana pun di domain. Asumsi ini memastikan bahwa kita dapat memilih ukuran langkah sehingga kita tidak pernah berakhir dengan langkah-langkah yang berbeda.$\ell$

Ingat bahwa suatu titik dikatakan sebagai pelana yang ketat jika dan dan . Jika semua nilai eigen Hessian memiliki tanda yang sama maka intinya adalah minimum (jika positif) atau maksimum (jika negatif). Jika ada 0 nilai eigen maka dikatakan degenerasi, dan itu bukan pelana yang ketat.$\pmb{x}$$\nabla f(\pmb{x}) = 0$$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right) < 0$$\lambda_{\max}\left(\nabla^2 f(\pmb{x})\right) > 0$

Makalah ini menunjukkan bahwa dengan asumsi di atas, bersama dengan asumsi bahwa semua titik sadel fungsi adalah sadel ketat, gradient descent dijamin akan menyatu ke minimum.

Buktinya cukup teknis, tetapi intuisinya adalah: definisikan satu set , di mana adalah titik pelana. Saya tidak suka notasi ini sama sekali. Apa yang mereka coba dapatkan adalah bahwa adalah himpunan nilai awal untuk mana peta gradien mengirim ke . Sederhananya, itu adalah set inisialisasi acak yang pada akhirnya akan menyatu menjadi pelana.$W^s(\pmb{x}^s) = \{\pmb{x} : \lim_k g^k(\pmb{x}) = \pmb{x}^s \}$$\pmb{x}^s$$W$$g : \mathbb{R}^d \to \mathbb{R}^d$$\pmb{x}_k$$\pmb{x}^s$

Argumen mereka bergantung pada Teorema Berjenis Stabil. Dengan asumsi di atas dan sekelompok matematika esoterik mereka menyimpulkan bahwa himpunan harus berukuran nol, yaitu, ada nol kemungkinan menginisialisasi secara acak pada titik yang akan konvergen ke titik pelana. Seperti yang kita ketahui bahwa gradient descent pada fungsi-fungsi dari tipe yang digariskan dalam asumsi dengan ukuran langkah kecil yang sesuai akhirnya akan mencapai titik kritis, dan kita sekarang tahu (hampir pasti) bahwa ia tidak akan pernah mendarat di pelana, kita tahu bahwa itu menyatu ke sebuah minimizer.$W^s$

Makalah kedua, yang lebih baru oleh Reddi et al. Saya akan membahas secara lebih rinci. Ada beberapa perbedaan. Pertama, mereka tidak lagi bekerja dalam kerangka deterministik, sebagai gantinya memilih kerangka kerja perkiraan stokastik yang lebih relevan secara praktis dengan jumlah yang terbatas (pikirkan Stochastic Gradient Descent). Perbedaan utama ada bahwa ukuran langkah memerlukan beberapa perawatan tambahan, dan gradien menjadi variabel acak. Selain itu, mereka mengendurkan asumsi bahwa semua sadel ketat, dan mencari titik stasioner orde kedua. Yaitu, titik sedemikian rupa, $\|\nabla(f) \| \leq \epsilon, \quad \text{and}, \quad \lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\geq -\sqrt{\rho\epsilon}$

Di mana adalah konstanta Lipschitz untuk Hessian. (Yaitu, di samping persyaratan bahwa gradien kami tidak berubah terlalu cepat, kami sekarang memiliki persyaratan serupa pada Hessian kami. Pada dasarnya, penulis mencari titik yang terlihat seperti minima dalam turunan pertama dan kedua.$rho$

Metode yang digunakan untuk mencapai hal ini adalah dengan menggunakan varian (pilih favorit Anda) dari penurunan gradien stokastik sebagian besar waktu. Tetapi di mana pun mereka menemukan titik di mana , mereka menggunakan metode urutan kedua yang dipilih secara tepat untuk menghindari pelana. Mereka menunjukkan bahwa dengan memasukkan informasi urutan kedua ini sesuai kebutuhan, mereka akan bertemu ke titik stasioner urutan kedua.$\lambda_{\min}\left(\nabla^2 f(\pmb{x})\right)\leq 0$

Secara teknis ini adalah metode gradien urutan kedua, yang mungkin atau mungkin tidak jatuh di bawah payung algoritma yang Anda minati.

Ini adalah bidang penelitian yang sangat aktif dan saya telah meninggalkan banyak kontribusi penting (ex Ge et al. ). Saya juga baru dalam topik ini sehingga pertanyaan ini telah memberi saya kesempatan untuk melihat. Saya senang melanjutkan diskusi jika ada minat.

*** Yang dipilih dengan tepat berarti satu yang ditunjukkan untuk menyatu ke titik stasioner orde kedua. Mereka menggunakan metode Newton yang diregulasi oleh Cubic, Nesterov dan Polyak.

Saya akan mencoba dan menjawab bagian "kapan Gradient Descent konvergensi ke titik kritis" dari pertanyaan.

Makalah "Konvergensi metode keturunan untuk masalah semi-aljabar dan jinak: algoritme proksimal, pemisahan maju-mundur, dan metode Gauss-Seidel yang teratur"

oleh Attouch, Bolte dan Svaiter,

menunjukkan bahwa jika fungsi obyektif memuaskan ketimpangan Kurdyka-Lojasiewicz (KL), maka GD dan metode keturunan lainnya benar-benar konvergen ke minimizer. Perhatikan bahwa kondisi KL sangat umum tetapi sulit untuk dipahami. Fungsi yang memenuhi KL misalnya diberikan oleh fungsi semi-aljabar (sekali lagi, sangat umum tetapi bukan gagasan sederhana).

Untuk memberikan beberapa intuisi tentang gagasan-gagasan ini saya akan mencoba untuk menjadi kurang kabur tetapi juga tidak terlalu teknis, jadi telanjang dengan saya. Fungsi memenuhi kondisi KL pada titik kritis jika ada fungsi (perhatikan bahwa saya mengabaikan beberapa kondisi) sehingga untuk semua sedemikian rupa sehingga untuk beberapa . Intuisi adalah bahwa ada fungsi yang mengubah fungsi minat kita$f$$\bar{x}$$\phi$

Semialgebricity di sisi lain sedikit lebih sulit. Bidang yang mempelajarinya juga dikenal sebagai geometri jinak . Saya pikir nama jinak menangkap esensi dengan sangat baik. Fungsi-fungsi yang dimiliki kelas ini tidak boleh sembarangan "liar".