Czy spadek gradientu zawsze jest zbieżny z optymalnym?

Zastanawiam się, czy istnieje scenariusz, w którym zejście gradientu nie jest zbieżne do minimum.

Zdaję sobie sprawę, że nie zawsze gwarantuje się, że zejście gradientu zbliży się do globalnego optimum. Wiem również, że może różnić się od optymalnego, jeśli powiedzmy, że stopień jest zbyt duży. Wydaje mi się jednak, że jeśli odbiegnie od jakiegoś optymalnego, ostatecznie przejdzie do innego optymalnego.

W związku z tym gwarantowane jest zejście gradientu do lokalnego lub globalnego optimum. Czy to prawda? Jeśli nie, czy możesz podać przybliżony przykład?

Gradient Descent to algorytm zaprojektowany w celu znalezienia optymalnych punktów, ale te optymalne punkty niekoniecznie są globalne. I tak, jeśli zdarza się, że odbiega od lokalnej lokalizacji, może zbiegać się w inny optymalny punkt, ale jego prawdopodobieństwo nie jest zbyt duże. Powodem jest to, że rozmiar kroku może być zbyt duży, co powoduje, że cofa się on o jeden optymalny punkt, a prawdopodobieństwo, że oscyluje, jest znacznie więcej niż zbieżnością.

Na temat spadku gradientu istnieją dwie główne perspektywy, era uczenia maszynowego i era głębokiego uczenia się. W erze uczenia maszynowego uznano, że opadanie gradientu znajdzie optymalną wartość lokalną / globalną, ale w erze głębokiego uczenia, w której wymiar cech wejściowych jest zbyt duży, w praktyce wykazano, że prawdopodobieństwo, że wszystkie cechy zostaną tam umieszczone w optymalnej wartości w jednym punkcie nie jest zbyt wiele i raczej mając optymalne lokalizacje w funkcjach kosztów, przez większość czasu obserwuje się punkty siodłowe. Jest to jeden z powodów, dla których trening z dużą ilością danych i epok treningu powoduje, że modele głębokiego uczenia przewyższają inne algorytmy. Więc jeśli trenujesz swój model, znajdzie objazd lub znajdzie drogę do zjazdu i nie utknie w punktach siodłowych, ale musisz mieć odpowiednie rozmiary stopni.

Aby uzyskać więcej intuicji, sugeruję zapoznanie się tu i tutaj .

Oprócz wspomnianych punktów (konwergencja do nieglobalnych minimów i duże rozmiary kroków, które mogą prowadzić do niekonwergentnych algorytmów), „zakresy przegięcia” mogą również stanowić problem.

Rozważ następujący typ funkcji „fotela rozkładanego”.

Oczywiście można to skonstruować tak, aby istniał zakres pośrodku, w którym gradient jest wektorem 0. W tym zakresie algorytm może zostać zablokowany na czas nieokreślony. Punkty zapalne zwykle nie są uważane za ekstrema lokalne.

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

[Uwaga 5 kwietnia 2019 r .: Nowa wersja artykułu została zaktualizowana na arXiv z wieloma nowymi wynikami. Wprowadzamy również wersje Momentum i NAG w zakresie cofania i udowadniamy zbieżność przy takich samych założeniach, jak w przypadku gradientu zejścia wstecznego.

Kody źródłowe są dostępne w GitHub pod linkiem: https://github.com/hank-nguyen/MBT-optimizer

Ulepszyliśmy algorytmy aplikowania do DNN i uzyskaliśmy lepszą wydajność niż najnowocześniejsze algorytmy, takie jak MMT, NAG, Adam, Adamax, Adagrad, ...

Najbardziej wyjątkową cechą naszych algorytmów jest to, że są one automatyczne, nie ma potrzeby ręcznego dostrajania wskaźników uczenia się jako powszechnej praktyki. Nasze automatyczne dostrajanie ma inny charakter niż Adam, Adamax, Adagrad, ... i tak dalej. Więcej szczegółów znajduje się w artykule.

]

Na podstawie bardzo najnowszych wyników: W mojej wspólnej pracy w tym dokumencie https://arxiv.org/abs/1808.05160

$f$

W związku z powyższym zaproponowaliśmy nową metodę głębokiego uczenia się, która jest na równi z obecnymi najnowocześniejszymi metodami i nie wymaga ręcznego dostrajania wskaźników uczenia się. ( Krótko mówiąc , chodzi o to, że przez pewien czas uruchamiasz gradient gradientu wstecznego, aż zobaczysz, że wskaźniki uczenia się, które zmieniają się z każdą iteracją, stabilizują się. Spodziewamy się tej stabilizacji, w szczególności w krytycznym punkcie, który jest C ^ 2 i nie jest zdegenerowany, ze względu na wynik konwergencji, o którym wspomniałem powyżej. W tym momencie przełączasz się na standardową metodę opadania gradientu. Zobacz cytowany artykuł, aby uzyskać więcej szczegółów. Metodę tę można również zastosować do innych optymalnych algorytmów .)

PS Jeśli chodzi o twoje oryginalne pytanie o standardową metodę zejścia gradientowego, o ile wiem, tylko w przypadku, gdy pochodną mapy jest globalnie Lipschitz, a szybkość uczenia się jest na tyle mała, że ​​udowodniono, że standardowa metoda zejścia gradientowego jest zbieżna. [Jeśli te warunki nie są spełnione, istnieją proste kontrprzykłady pokazujące, że żaden wynik zbieżności nie jest możliwy, patrz cytowany artykuł dla niektórych.] W artykule cytowanym powyżej argumentowaliśmy, że na dłuższą metę metoda opadania gradientu wstecznego stanie się standardowa metoda opadania gradientu, która wyjaśnia, dlaczego standardowa metoda opadania gradientu zwykle działa dobrze w praktyce.