Teoretyczne badanie metod zejścia ze współrzędnymi

Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście współrzędnych odbywa się cyklicznie przez współrzędne, ustalając wszystko oprócz wybranego i minimalizując wzdłuż tej współrzędnej. W końcu ulepszenia stają się coraz wolniejsze i kończysz.$f$$f$

Moje pytanie brzmi: czy jest jakieś teoretyczne badanie metod zejścia współrzędnych, które mówi o współczynnikach zbieżności i właściwościach które sprawiają, że metoda działa dobrze i tak dalej? Oczywiście nie oczekuję w pełni ogólnych odpowiedzi, ale pomocne byłyby odpowiedzi, które wyjaśniają przypadki, w których heurystyka ma się dobrze.$f$

Poza tym: naprzemienną technikę optymalizacji stosowaną dla średnich można postrzegać jako przykład opadania współrzędnych, a algorytm Frank-Wolfe wydaje się powiązany (ale nie jest bezpośrednim przykładem frameworka)$k$

(Edytuj notatki: Zreorganizowałem to po tym, jak przeraziłem się jego długością.)

Literatura na temat opadania współrzędnych może być nieco trudna do wyśledzenia. Oto kilka powodów tego.

1. Wiele znanych właściwości metod współrzędnych jest ujętych w twierdzeniach parasolowych dla bardziej ogólnych metod zejścia. Dwa przykłady tego, podane poniżej, są szybka konwergencja pod silną wypukłość (hold dla każdego największego spadku), a ogólna konwergencja tych metod (zwykle przypisywane Zoutendijk).$l^p$

2. Nazewnictwo nie jest standardowe. Nawet termin „najbardziej stromy zjazd” nie jest standardem. Możesz odnosić sukcesy w Google, używając dowolnego terminu „cykliczne zejście współrzędnych”, „zejście współrzędnych”, „Gauss-Seidel”, „Gauss-Southwell”. użycie nie jest spójne.

3. $n$$n$

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

Ograniczenia Bez silnej wypukłości musisz zacząć być trochę ostrożny. Nie mówiłeś nic o ograniczeniach, a zatem ogólnie rzecz biorąc, minimum może być nieosiągalne. Powiem krótko na temat ograniczeń, że standardowym podejściem (z metodami opadania) jest rzutowanie na zestaw ograniczeń, ustawiając każdą iterację, aby zachować wykonalność, lub użyć barier, aby wprowadzić ograniczenia do funkcji celu. W przypadku tego pierwszego nie wiem, jak to gra ze współrzędnym opadaniem; w przypadku tego ostatniego działa dobrze przy zejściu ze współrzędnymi, a bariery te mogą być silnie wypukłe.

Bardziej konkretnie do metod współrzędnych, zamiast projekcji, wiele osób po prostu sprawia, że ​​aktualizacja współrzędnych zachowuje wykonalność: dzieje się tak na przykład w przypadku algorytmu Frank-Wolfe i jego wariantów (tj. Wykorzystywania go do rozwiązywania SDP).

Zauważę też pokrótce, że algorytm SMO dla SVM może być postrzegany jako metoda opadania współrzędnych, w której aktualizujesz dwie zmienne jednocześnie i utrzymujesz w tym czasie ograniczenie wykonalności. Wybór zmiennych jest heurystyczny w tej metodzie, więc gwarancje są tak naprawdę tylko gwarancjami cyklicznymi. Nie jestem pewien, czy to połączenie pojawia się w standardowej literaturze; Dowiedziałem się o metodzie SMO z notatek kursowych Andrew Nga i stwierdziłem, że są całkiem czyste.

$n$

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

Istnieje kilka ostatnich wyników dotyczących opadania współrzędnych, widziałem rzeczy na arXiv. Ponadto luo i tseng mają kilka nowszych dokumentów. ale to jest najważniejsze.

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

Problem z dokładnymi aktualizacjami. Ponadto bardzo często zdarza się, że nie masz zamkniętej pojedynczej aktualizacji współrzędnych. Lub dokładne rozwiązanie może po prostu nie istnieć. Ale na szczęście istnieje wiele metod przeszukiwania linii, które mają w zasadzie takie same gwarancje jak dokładne rozwiązanie. Materiał ten można znaleźć w standardowych tekstach programowania nieliniowego, na przykład w wymienionych wyżej książkach Bertsekas lub Nocedal & Wright.

Zobacz drugi akapit: kiedy działają dobrze. Po pierwsze, wiele z wyżej wspomnianych analiz pracy gradientowej dla opadania współrzędnych. Dlaczego więc nie zawsze używać opadania współrzędnych? Odpowiedź jest taka, że ​​w przypadku wielu problemów, w których stosuje się spadek gradientu, można również zastosować metody Newtona, dla których można udowodnić lepszą zbieżność. Nie znam sposobu na uzyskanie przewagi Newtona przy zejściu ze współrzędnymi. Wysokie koszty metod Newtona można również złagodzić dzięki aktualizacjom Quasinewton (patrz na przykład LBFGS).

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

Proponuję zajrzeć tutaj, wykonaliśmy trochę pracy w tym obszarze:

http://arxiv.org/abs/1107.2848

Twoje zdrowie

Piotr

Właśnie opublikowaliśmy artykuł na temat arXiv ( http://arxiv.org/abs/1201.1214 ), który dowodzi ogólnych dolnych granic dla „algorytmów statystycznych” dla problemów optymalizacyjnych, przy czym każdy „problem” ma swoją dolną granicę w zależności od jego różne właściwości.

Współrzędne opadania (i prawie wszystko, co jeszcze możemy wymyślić) mogą być postrzegane jako algorytm statystyczny w naszych ramach, więc mam nadzieję, że ten artykuł ma pewne wyniki, które mogą Cię zainteresować.

Należy zauważyć, że w optymalizacji „współczynnik konwergencji” zwykle oznacza zachowanie asymptotyczne. Oznacza to, że stawka dotyczy tylko sąsiedztwa optymalnych rozwiązań. W tym sensie Luo i Tseng udowodnili współczynniki zbieżności liniowej dla niektórych niezbyt wypukłych funkcji celu w artykule „O zbieżności metody zejścia współrzędnych w celu minimalizacji wypukłej różnicowalnej”.

Niesymptotyczny współczynnik zbieżności, zwany także „złożonością iteracji”, jest na ogół bardziej przydatny w ograniczaniu liczby iteracji algorytmów minimalizacji. W przypadku silnie wypukłych funkcji celu złożoność iteracji metod cyklicznego opadania współrzędnych jest już pokazana w granicach błędu Luo & Tsenga i analizie zbieżności wykonalnych metod opadania: podejście ogólne, jeśli stosowana jest globalna granica błędu. W przypadku problemów słabo wypukłych mamy nowe wyniki w złożoności iteracji wykonalnych metod opadania dla optymalizacji wypukłej. Mówiąc ściślej, pokazaliśmy złożoność iteracji dla metod cyklicznego opadania współrzędnych dla problemów, takich jak podwójna forma SVM i metody Gaussa-Seidela. Ponadto wyniki obejmują również inne możliwe metody zejścia, w tym zejście gradientowe i znajomych.