Сходимость метода градиентного спуска

[id]

Интересует, есть ли где-нибудь доказательство сходимости метода градиентного спуска ( про минимизацию ф-ии многих переменных ) в предположении $f \in C^1 (\mathbb{R}^n)$ и выпукла. И вообще, верно ли это?

[ewert]

id в сообщении #244756 писал(а):

И вообще, верно ли это?

Верно, конечно (если, разумеется, функция выпукла строго). Мы ведь на каждом шаге хоть сколько-то, да спускаемся. Т.е. последовательность значений целевой функции строго монотонна и, следовательно, имеет предел. И этот предел не может не отвечать минимальному значению -- т.к. вне любой окрестности точки минимума модуль градиента (в силу его непрерывности) отделён от нуля.

[id]

ewert
Так, про отделенность градиента от нуля, конечно, ясно. Но как отсюда вытекает противоречие со сходимостью последовательности значений ( ведь расстояние между соседними точками тоже уменьшается )?

И как быть в общем случае нестрого выпуклой ф-ии?

[ewert]

id в сообщении #244782 писал(а):

Так, про отделенность градиента от нуля, конечно, ясно. Но как отсюда вытекает противоречие со сходимостью последовательности значений

Тут на самом деле принципиально вот что: для строго выпуклой функции прообраз любого конечного отрезка ограничен. Поэтому ограничена и последовательность приближений. Если она не стремится к точке минимума, то по некоторой подпоследовательности стремится к какой-то другой точке, в которой градиент не равен нулю. В достаточно малой окрестности этой предельной точки градиент мало меняется и, следовательно, существует некоторое гарантированное уменьшение целевой функции для любого приближения, попавшего в эту окрестность. А это противоречит тому, что значения целевой функции на приближениях стабилизируются.

id в сообщении #244782 писал(а):

И как быть в общем случае нестрого выпуклой ф-ии?

Не знаю. Как было сказано, важна не строгость выпуклости, а ограниченность прообразов. Которой в нестрогом случае может и не быть, но бороться с этим пока лень.

[id]

Цитата:

В достаточно малой окрестности этой предельной точки градиент мало меняется и, следовательно, существует некоторое гарантированное уменьшение целевой функции для любого приближения, попавшего в эту окрестность.А это противоречит тому, что значения целевой функции на приближениях стабилизируются.

Не совсем уловил. Существует гарантированная $0<\triangle<f(x_{n+1})-f(x_n)$? Да, градиент мало отличается ( по всем компонентам ), но ведь и точки $x_n$ сближаются. То есть геометрически я суть, наверно, улавливаю: в некоторой окрестности векторное поле слабо отличается от градиента в предельной точке, тогда проводя сечение по направлению градиента "выскакиваем" из данной окрестности.

[ewert]

id в сообщении #244849 писал(а):

Не совсем уловил.

Возможно, потому, что я неграмотно записал. Имелось в виду: в достаточно малой окрестности этой предельной точки градиент мало меняется и, следовательно, существует некоторое гарантированное уменьшение целевой функции для любого приближения, попавшего в несколько меньшую окрестность (ну например ровно вдвое меньшую).

Конкретнее. Допустим, в самой предельной точке модуль градиента есть $2C$. Тогда в некоторой окрестности радиуса $2\delta$ отклонение градиента от своего центрального значения не превысит по модулю $C$. Тогда для любых точек, попадающих в окрестность радиуса $\delta$, гарантировано уменьшение на следующем шаге не менее чем на $\delta\cdot C$ (поскольку расстояние от любой точки из окрестности радиуса $\delta$ до границы окрестности радиуса $2\delta$ уж никак не меньше самой $\delta$).

[id]

ewert
А почему интересует именно расстояние от границы окрестности радиуса $\delta$ до границы окрестности радиуса $2*\delta$?
Выбирается же минимум на соотв. сечении (скажем, от $x_n \in B_{\delta}$ до границы $B_{2\delta}$ по направлению градиента), и не вполне ясно, какое будет расстояние до него.

[ewert]

Неизвестно, куда в точности будет направлен антиградиент. Однако гарантировано: на отрезке, длина которого не меньше расстояния между этими двумя сферами, скорость убывания будет не ниже, чем половина четверть модуля градиента в центре.

(Я там малость ошибся в арифметике: вместо $2C$ следует читать $4C$. Но суть-то от этого не меняется.)

[id]

С градиентом-то понятно, хоть с дочностью до константы; непонятки остаются от того, откуда берется гарантированное уменьшение. Скажем, определяем $x_{n+1} = x_n - \delta_0 grad f(x_n), \ \delta_0$ - то $\delta$, на котором достигается $\min\limits_{\delta} (x_n - \delta grad f(x_n))$. Хотя $grad f$ оценить по модулю и можно, как получить оценку еще и на $\delta_0$ снизу - неясно.

[ewert]

Ну допустим: в "большой" окрестности изменения градиента по модулю не превосходят $\varepsilon|\vec g_0|$, где $\vec g_0$ -- это градиент в центре и $\varepsilon$ -- некоторое фиксированное и достаточно малое число (я в последний раз взял $\varepsilon={1\over4}$). Пусть $\vec g_n$ -- градиент в точке очередного приближения (попавшего в "маленькую" окрестность), $\vec g$ -- градиент на участке линии антиградиента, лежащем в пределах "большой" окрестности и $\Delta\vec g=\vec g-\vec g_n$. Тогда $|\Delta\vec g|\leqslant|\vec g-\vec g_0|+|\vec g_n-\vec g_0|\leqslant2\varepsilon|\vec g_0|$. Поэтому модуль производной по направлению той линии (т.е., собственно, минус производная по направлению) оценивается как

$${(\vec g,\vec g_n)\over|\vec g_n|}={(\vec g_n+\Delta\vec g,\vec g_n)\over|\vec g_n|}=|\vec g_n|+{(\Delta\vec g,\vec g_n)\over|\vec g_n|}\geqslant|\vec g_n|-|\Delta\vec g|\geqslant|\vec g_0|-\varepsilon|\vec g_0|-2\varepsilon|\vec g_0|=(1-3\varepsilon)|\vec g_0|.$$

Соответственно (учитывая, что длина того отрезка не меньше $\delta$) уменьшение целевой функции до следующего приближения никак не меньше, чем $\delta\cdot(1-3\varepsilon)|\vec g_0|$.

[id]

Цитата:

учитывая, что длина того отрезка не меньше $\delta$

А... почему?

[ewert]

id в сообщении #244952 писал(а):

Цитата:

учитывая, что длина того отрезка не меньше $\delta$

А... почему?

Как это почему?... Потому, что он выходит из маленькой окрестности и доходит до края большой.

[id]

В формуле $x_{n+1} = x_n - \delta_0 grad f(x_n)$ выходит? Т.е. $\delta_0$ такой, что $x_{n+1} \in B_{2\delta}$ не лежит в $B_{\delta}$?
Вот это мне и непонятно. Не знаю, может мы о слегка разных методах говорим?

[ewert]

id в сообщении #244956 писал(а):

В формуле $x_{n+1} = x_n - \delta_0 grad f(x_n)$ выходит? Т.е. $\delta_0$ такой, что $x_{n+1} \in B_{2\delta}$ не лежит в $B_{\delta}$?
Вот это мне и непонятно. Не знаю, может мы о слегка разных методах говорим?

Нет, метод один и тот же, просто не в этом пафос. Разность $f(x_{n})-f(x_{n+1})$ обязана в любом случае стремиться к нулю. А у нас выходит, что по некоторой подпоследовательности она ограничена снизу некоторым положительным числом. Вот и противоречие.

(Ваша $\delta_0$ -- это не то же самое, что моя $\delta$. У Вас -- это точка минимума для очередного приближения. А у меня -- некоторое расстояние, на протяжении которого функция гарантированно уменьшается, да ещё и с запасом.)

[id]

Эту часть

Цитата:

Нет, метод один и тот же, просто не в этом пафос. Разность $f(x_{n+1})-f(x_n)$ обязана в любом случае стремиться к нулю. А у нас выходит, что по некоторой подпоследовательности она ограничена снизу некоторым положительным числом. Вот и противоречие.

понял.

Так, а на промежутке длины $\delta$ ( в Вашей интерпретации ) функция убывает именно потому, что убывает по этому направлению в начальной точке - а на всем интервале градиент ( покомпонентно ) мало отличается от начального значения? ( в т.ч. по формуле

$${(\vec g,\vec g_n)\over|\vec g_n|}={(\vec g_n+\Delta\vec g,\vec g_n)\over|\vec g_n|}=|\vec g_n|+{(\Delta\vec g,\vec g_n)\over|\vec g_n|}\geqslant|\vec g_n|-|\Delta\vec g|\geqslant|\vec g_0|-\varepsilon|\vec g_0|-2\varepsilon|\vec g_0|=(1-3\varepsilon)|\vec g_0|.$$

)
Ну а так как $\delta_0$ должно быть больше $\delta$, следует и то, что приближение с $\delta_0$ будет выскакивать.