Поиск строки с возвратом - Backtracking line search

В (без ограничений) минимизация, а поиск строки с возвратом, схема поиска на основе Условие Армихо – Гольдштейна, это линейный поиск метод определения суммы, на которую нужно двигаться по заданному направление поиска. Он включает в себя начало с относительно большой оценки размера шага для перемещения по направлению поиска и итеративное уменьшение размера шага (то есть «возврат с возвратом») до тех пор, пока не уменьшится целевая функция наблюдается, что адекватно соответствует уменьшению, которое ожидается, исходя из локального градиента целевой функции.

Поиск строки с возвратом обычно используется для градиентный спуск, но его также можно использовать в других контекстах. Например, его можно использовать с Метод Ньютона если Матрица Гессе является положительно определенный.

Мотивация

Учитывая исходную позицию ${\displaystyle \mathbf {x} }$ и направление поиска ${\displaystyle \mathbf {p} }$, задача поиска строки - определить размер шага ${\displaystyle \alpha >0}$ что адекватно снижает целевую функцию ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ (предполагается ${\displaystyle C^{1}}$ т.е. непрерывно дифференцируемый ), т.е. найти значение ${\displaystyle \alpha }$ что уменьшает ${\displaystyle f(\mathbf {x} +\alpha \,\mathbf {p} )}$ относительно ${\displaystyle f(\mathbf {x} )}$. Однако, как правило, нежелательно тратить значительные ресурсы на поиск значения ${\displaystyle \alpha }$ чтобы точно минимизировать ${\displaystyle f}$. Это связано с тем, что вычислительные ресурсы, необходимые для нахождения более точного минимума в одном конкретном направлении, могут вместо этого использоваться для определения лучшего направления поиска. Как только улучшенная начальная точка была идентифицирована с помощью линейного поиска, другой последующий линейный поиск обычно будет выполняться в новом направлении. Таким образом, цель состоит в том, чтобы просто определить ценность ${\displaystyle \alpha }$ что обеспечивает разумное улучшение целевой функции, а не нахождение фактического минимизирующего значения ${\displaystyle \alpha }$.

Поиск строки с возвратом начинается с большой оценки ${\displaystyle \alpha }$ и многократно сжимает его. Сжатие продолжается до тех пор, пока не будет найдено значение, достаточно маленькое, чтобы обеспечить уменьшение целевой функции, адекватно соответствующее ожидаемому уменьшению на основе градиента локальной функции. ${\displaystyle \nabla f(\mathbf {x} )\,.}$

Определите локальный наклон функции ${\displaystyle \alpha }$ по направлению поиска ${\displaystyle \mathbf {p} }$ в качестве ${\displaystyle m=\nabla f(\mathbf {x} )^{\mathrm {T} }\,\mathbf {p} =\langle \nabla f(\mathbf {x} ),\mathbf {p} \rangle }$ (куда ${\displaystyle \langle \cdot ,\cdot \rangle }$ обозначает скалярное произведение ). Предполагается, что ${\displaystyle \mathbf {p} }$ - вектор, для которого возможно некоторое локальное убывание, т. е. предполагается, что ${\displaystyle m<0}$.

На основе выбранного параметра управления ${\displaystyle c\,\in \,(0,1)}$, условие Армийо – Гольдштейна проверяет, может ли пошаговое движение из текущей позиции${\displaystyle \mathbf {x} }$ на измененную позицию ${\displaystyle \mathbf {x} +\alpha \,\mathbf {p} }$ достигает адекватно соответствующего уменьшения целевой функции. Условие выполнено, см. Армийо (1966), если ${\displaystyle f(\mathbf {x} +\alpha \,\mathbf {p} )\leq f(\mathbf {x} )+\alpha \,c\,m\,.}$

Это условие, при правильном использовании как часть поиска строки, может гарантировать, что размер шага не будет чрезмерно большим. Однако одного этого условия недостаточно, чтобы гарантировать, что размер шага будет почти оптимальным, поскольку любое значение ${\displaystyle \displaystyle \alpha }$ который достаточно мал, будет удовлетворять условию.

Таким образом, стратегия поиска строки с возвратом начинается с относительно большого размера шага и многократно сжимает его в раз. ${\displaystyle \tau \,\in \,(0,1)}$ до тех пор, пока не будет выполнено условие Армийо – Гольдштейна.

Поиск завершится через конечное количество шагов для любых положительных значений ${\displaystyle c}$ и ${\displaystyle \tau }$ которые меньше 1. Например, Armijo использовал¹⁄₂ для обоих ${\displaystyle c}$ и ${\displaystyle \tau }$ в Армийо (1966).

Алгоритм

Это состояние от Армийо (1966). Начиная с максимального возможного значения размера шага ${\displaystyle \alpha _{0}>0\,}$, используя параметры управления поиском ${\displaystyle \tau \,\in \,(0,1)}$ и ${\displaystyle c\,\in \,(0,1)}$, алгоритм поиска строки с возвратом можно выразить следующим образом:

1. Набор ${\displaystyle t=-c\,m}$ и счетчик итераций ${\displaystyle j\,=\,0}$.
2. Пока не будет выполнено условие, ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\alpha _{j}\,\mathbf {p} )\geq \alpha _{j}\,t,}$ многократно увеличивать ${\displaystyle j}$ и установить ${\displaystyle \alpha _{j}=\tau \,\alpha _{j-1}\,.}$
3. Возвращаться ${\displaystyle \alpha _{j}}$ как решение.

Другими словами, уменьшить ${\displaystyle \alpha _{0}}$ в разы ${\displaystyle \tau \,}$ в каждой итерации, пока не будет выполнено условие Армиджо – Гольдштейна.

Минимизация функций с помощью поиска по строке с возвратом на практике

На практике вышеупомянутый алгоритм обычно повторяется для создания последовательности ${\displaystyle \mathbf {x} _{n}}$, ${\displaystyle n=1,2,...}$, сводиться к минимуму, если такой минимум существует и ${\displaystyle \mathbf {p} _{n}}$ выбирается соответствующим образом на каждом шаге. Для градиентного спуска ${\displaystyle \mathbf {p} _{n}}$ выбран как ${\displaystyle -\nabla f(\mathbf {x} _{n})}$.

Значение ${\displaystyle \alpha _{j}}$ для ${\displaystyle j}$ которое удовлетворяет условию Армийо – Гольдштейна, зависит от ${\displaystyle \mathbf {x} }$ и ${\displaystyle \mathbf {p} }$, и поэтому ниже обозначается ${\displaystyle \alpha (\mathbf {x} ,\mathbf {p} )}$. Это также зависит от ${\displaystyle f}$, ${\displaystyle \alpha _{0}}$, ${\displaystyle \tau }$ и ${\displaystyle c}$ конечно, хотя эти зависимости можно оставить неявными, если предполагается, что они зафиксированы в отношении проблемы оптимизации.

Таким образом, подробные шаги см. Армийо (1966), Бертсекас (2016):

1. Выберите начальную отправную точку ${\displaystyle \mathbf {x} _{0}}$ и установить счетчик итераций ${\displaystyle n=0}$.
2. Пока не будет выполнено какое-либо условие остановки, выберите направление спуска. ${\displaystyle \mathbf {p} _{n}}$, приращение ${\displaystyle n}$, и обновите позицию на ${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}+\alpha (\mathbf {x} _{n},\mathbf {p} _{n})\,\mathbf {p} _{n}}$.
3. Возвращаться ${\displaystyle \mathbf {x} _{n}}$ как минимизирующая позиция и ${\displaystyle f(\mathbf {x} _{n})}$ как минимум функции.

Чтобы гарантировать хорошее поведение, необходимо, чтобы некоторые условия выполнялись ${\displaystyle \mathbf {p} _{n}}$. Грубо говоря ${\displaystyle \mathbf {p} _{n}}$ не должен быть слишком далеко от ${\displaystyle \nabla f(\mathbf {x} _{n})}$. Точная версия выглядит следующим образом (см., Например, Бертсекас (2016) ). Есть константы ${\displaystyle C_{1},C_{2}>0}$ так что выполняются следующие два условия:

1. Для всех n, ${\displaystyle \|\mathbf {p} _{n}\|\geq C_{1}\,\|\nabla f(\mathbf {x} _{n})\|}$. Здесь, ${\displaystyle \|y\|}$ это Евклидова норма из ${\displaystyle y}$. (Это гарантирует, что если ${\displaystyle \mathbf {p} _{n}=0}$, то также ${\displaystyle \nabla f(\mathbf {x} _{n})=0}$. В более общем смысле, если ${\displaystyle \lim _{n\rightarrow \infty }\mathbf {p} _{n}=0}$, то также ${\displaystyle \lim _{n\rightarrow \infty }\nabla f(\mathbf {x} _{n})=0}$.) Более строгий вариант требует также обратного неравенства: ${\displaystyle \|\mathbf {p} _{n}\|\leq C_{3}\,\|\nabla f(\mathbf {x} _{n})\|}$ для положительной постоянной ${\displaystyle C_{3}>0}$.
2. Для всех n, ${\displaystyle \|\mathbf {p} _{n}\|\,\|\nabla f(\mathbf {x} _{n})\|\leq -C_{2}\,\langle \mathbf {p} _{n},\nabla f(\mathbf {x} _{n})\rangle }$. (Это условие гарантирует, что направления ${\displaystyle \mathbf {p} _{n}}$ и ${\displaystyle -\nabla f(\mathbf {x} _{n})}$ похожи.)

Нижняя граница скорости обучения

Это решает вопрос о том, существует ли систематический способ найти положительное число. ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ - в зависимости от функции f точка ${\displaystyle \mathbf {x} }$ и направление спуска ${\displaystyle \mathbf {p} }$ - чтобы все скорость обучения ${\displaystyle \alpha \leq \beta (\mathbf {x} ,\mathbf {p} )}$ удовлетворяют условию Армийо. Когда ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$, мы можем выбрать ${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$ в порядке ${\displaystyle 1/L(\mathbf {x} )\,}$, куда ${\displaystyle L(\mathbf {x} )\,}$ - локальная константа Липшица для градиента ${\displaystyle \nabla f\,}$ рядом с точкой ${\displaystyle \mathbf {x} }$ (видеть Липшицева преемственность ). Если функция ${\displaystyle C^{2}}$, тогда ${\displaystyle L(\mathbf {x} )\,}$ близка к гессиану функции в точке ${\displaystyle \mathbf {x} }$. Видеть Армийо (1966) для более подробной информации.

Верхняя граница скорости обучения

В той же ситуации, когда ${\displaystyle \mathbf {p} =-\nabla f(\mathbf {x} )}$, интересный вопрос заключается в том, насколько большие скорости обучения могут быть выбраны в условии Армийо (то есть, когда нет ограничения на ${\displaystyle \alpha _{0}}$ в разделе «Минимизация функций с помощью поиска по строке с возвратом на практике»), поскольку большая скорость обучения при ${\displaystyle \mathbf {x} _{n}}$ ближе к предельной точке (если существует) может ускорить сходимость. Например, в Условия Вульфа, нет упоминания о ${\displaystyle \alpha _{0}}$ но вводится другое условие, называемое условием кривизны.

Показано, что существует верхняя граница скорости обучения, если требуется построенная последовательность ${\displaystyle \mathbf {x} _{n}}$ сходится к невырожденная критическая точка, видеть Чыонг и Нгуен (2020): Скорость обучения должна быть ограничена сверху примерно ${\displaystyle ||H||\times ||H^{-1}||^{2}}$. Здесь H - гессиан функции в предельной точке, ${\displaystyle H^{-1}}$ это его обратный, и ${\displaystyle ||.||}$ это норма линейного оператора. Таким образом, этот результат применяется, например, когда используется поиск строки с возвратом для Функции Морса. Обратите внимание, что в измерении 1 ${\displaystyle H}$ является числом, и поэтому эта верхняя граница имеет тот же размер, что и нижняя граница в разделе «Нижняя граница для скорости обучения».

С другой стороны, если предельная точка вырождена, скорость обучения может быть неограниченной. Например, модификация линейного поиска с обратным прослеживанием, названная Unbounded backtracking gradient descent (см. Чыонг и Нгуен (2020) ) позволяет скорость обучения быть размером ${\displaystyle ||\nabla f(\mathbf {x} _{n})||^{-\gamma }}$, куда ${\displaystyle 1>\gamma >0}$ является константой. Эксперименты с простыми функциями, такими как ${\displaystyle f(x,y)=x^{4}+y^{4}}$ показывают, что неограниченный градиентный спуск с обратным отслеживанием сходится намного быстрее, чем базовая версия в разделе «Практическая минимизация функций с использованием обратного поиска по строке».

Эффективность времени

Аргументом против использования строкового поиска с возвратом, в частности при крупномасштабной оптимизации, является то, что выполнение условия Armijo обходится дорого. Есть способ (так называемый двусторонний возврат) с хорошими теоретическими гарантиями, который был протестирован с хорошими результатами на Глубокие нейронные сети, видеть Чыонг и Нгуен (2020). Заметим, что если последовательность ${\displaystyle \mathbf {x} _{n}}$ сходится (по желанию, когда используется метод итеративной оптимизации), то последовательность скоростей обучения ${\displaystyle \alpha _{n}}$ должен немного отличаться, когда n достаточно велико. Поэтому в поисках ${\displaystyle \alpha _{n}}$, если всегда начинать с ${\displaystyle \alpha _{0}}$, можно было бы потратить много времени, если бы выяснилось, что последовательность ${\displaystyle \alpha _{n}}$ находится далеко от ${\displaystyle \alpha _{0}}$. Вместо этого нужно искать ${\displaystyle \alpha _{n}}$ начиная с ${\displaystyle \alpha _{n-1}}$. Второе наблюдение: ${\displaystyle \alpha _{n}}$ может быть больше, чем ${\displaystyle \alpha _{n-1}}$, а значит, нужно позволить увеличить скорость обучения (а не просто уменьшить, как в разделе Алгоритм). Вот подробный алгоритм двустороннего поиска с возвратом: На шаге n

1. Набор ${\displaystyle \gamma _{0}=\alpha _{n-1}}$. Набор ${\displaystyle t=-c\,m}$ и счетчик итераций ${\displaystyle j\,=\,0}$.
2. (Увеличьте скорость обучения, если выполняется условие Армиджо.) Если ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$, то пока это условие и условие, что ${\displaystyle \gamma _{j}\leq \alpha _{0}}$ удовлетворены, повторно устанавливаются ${\displaystyle \gamma _{j}=\alpha _{j-1}/\tau }$ и увеличиваем j.
3. (В противном случае уменьшите скорость обучения, если условие Армийо не выполняется.) Если наоборот ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{0}\,\mathbf {p} )<\gamma _{j}\,t,}$, то до выполнения условия ${\displaystyle f(\mathbf {x} )-f(\mathbf {x} +\gamma _{j}\,\mathbf {p} )\geq \gamma _{j}\,t,}$ многократно увеличивать ${\displaystyle j}$ и установить ${\displaystyle \alpha _{j}=\tau \,\alpha _{j-1}\,.}$
4. Возвращаться ${\displaystyle \gamma _{j}}$ для скорости обучения ${\displaystyle \alpha _{n}}$.

Можно дополнительно сэкономить время, используя гибридную смесь двустороннего обратного отслеживания и базового алгоритма стандартного градиентного спуска. Эта процедура также имеет хорошую теоретическую гарантию и хорошие результаты испытаний. Грубо говоря, мы запускаем двусторонний поиск с возвратом несколько раз, а затем используем скорость обучения, которую мы получаем, без изменений, за исключением случаев, когда значение функции увеличивается. Вот как это делается. Заранее выбирают число N, а число ${\displaystyle m\leq N}$.

1. Установить счетчик итераций j = 0.
2. На ступеньках ${\displaystyle jN+1,\ldots ,jN+m}$, используйте двусторонний возврат.
3. На каждом шаге k в множестве ${\displaystyle jN+m+1,\ldots ,jN+N-1}$: Набор ${\displaystyle \alpha =\alpha _{k-2}}$. Если ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})\geq 0}$, тогда выбирай ${\displaystyle \alpha _{k-1}=\alpha _{k-2}}$ и ${\displaystyle x_{k}=x_{k-1}+\alpha _{k-1}p_{k-1}}$. (Итак, в этом случае используйте скорость обучения ${\displaystyle \alpha _{k-2}}$ без изменений.) В противном случае, если ${\displaystyle f(x_{k-1})-f(x_{k-1}+\alpha p_{k-1})<0}$, используйте двусторонний поиск с возвратом. Увеличьте k на 1 и повторите.
4. Увеличьте j на 1.

Теоретическая гарантия (для градиентного спуска)

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

Критические точки - это точки, в которых градиент целевой функции равен 0. Локальные минимумы являются критическими точками, но есть критические точки, которые не являются локальными минимумами. Пример - седловые точки. Седловые точки являются критическими точками, в которых есть хотя бы одно направление, в котором функция является (локальным) максимумом. Следовательно, эти точки далеки от локальных минимумов. Например, если функция имеет хотя бы одну седловую точку, то она не может быть выпуклый. Актуальность седловых точек для алгоритмов оптимизации заключается в том, что при крупномасштабной (то есть многомерной) оптимизации можно увидеть больше седловых точек, чем минимумов, см. Брей и Дин (2007). Следовательно, хороший алгоритм оптимизации должен уметь избегать седловых точек. В обстановке Глубокое обучение, также распространены седловые точки, см. Dauphin et al. (2014). Таким образом, применить в Глубокое обучение, нужны результаты для невыпуклых функций.

Для сходимости к критическим точкам: например, если функция стоимости является вещественная аналитическая функция, то он отображается в Абсил, Махони и Эндрюс (2005) эта сходимость гарантирована. Основная идея - использовать Неравенство Лоясевича которым пользуется реальная аналитическая функция. Для негладких функций, удовлетворяющих Неравенство Лоясевича, указанная выше гарантия сходимости расширяется, см. Attouch, Bolte & Svaiter (2011). В Бертсекас (2016), есть доказательство того, что для каждой последовательности, построенной с помощью поиска по строке с возвратом, точка кластера (т.е. предел одного подпоследовательность, если подпоследовательность сходится) является критической точкой. В случае функции с не более чем счетным числом критических точек (например, Функция Морса ) и компактный подуровни, а также с липшицевым непрерывным градиентом, где используется стандартный GD со скоростью обучения <1 / L (см. раздел о стохастическом градиентном спуске), то сходимость гарантируется, см., например, главу 12 в Ланге (2013). Здесь предположение о компактных подуровнях состоит в том, чтобы убедиться, что мы имеем дело только с компактными множествами евклидова пространства. В общем случае, когда f предполагается только равным ${\displaystyle C^{1}}$ и имеют не более чем счетное число критических точек, сходимость гарантирована, см. Чыонг и Нгуен (2020). В той же ссылке аналогичная сходимость гарантируется для других модификаций поиска по строке с возвратом (таких как неограниченный градиентный спуск с возвратом, упомянутый в разделе «Верхняя граница скорости обучения»), и даже если функция имеет несчетное количество критических точек, все же можно вывести некоторые нетривиальные факты о поведении сходимости. В стохастической настройке, при том же предположении, что градиент является липшицевым, и используется более ограничивающая версия (требующая, кроме того, чтобы сумма скоростей обучения была бесконечной, а сумма квадратов скоростей обучения была конечной) схемы убывающей скорости обучения (см. раздел Стохастический градиентный спуск) и, кроме того, функция строго выпуклая, то сходимость устанавливается в известном результате Роббинс и Монро (1951), видеть Бертсекас и Цициклис (2006) для обобщений до менее строгих версий схемы убывающей скорости обучения. Ни один из этих результатов (для невыпуклых функций) до сих пор не был доказан ни для одного другого алгоритма оптимизации.^{[нужна цитата ]}

Во избежание седловых точек: например, если градиент функции стоимости является липшицевым и выбирается стандартный GD со скоростью обучения <1 / L, то со случайным выбором начальной точки ${\displaystyle \mathbf {x} _{0}}$ (точнее, вне набора Мера Лебега нуля) построенная последовательность не будет сходиться к невырожденный седловая точка (доказано в Ли и др. (2016) ), и в более общем смысле также верно, что построенная последовательность не будет сходиться к вырожденной седловой точке (доказано в Панагеи и Пилиурас (2017) ). При том же предположении, что градиент является липшицевым и используется схема убывающей скорости обучения (см. Раздел «Стохастический градиентный спуск»), то устранение седловых точек устанавливается в Панагеас, Пилиурас и Ван (2019).

Особый случай: (Стандартный) Стохастический градиентный спуск

Хотя тривиально упомянуть, что если градиент функции стоимости является липшицевым, с константой Липшица L, то при выборе постоянной скорости обучения и размера 1 / L возникает особый случай поиска строки с возвратом (для градиентный спуск). Это использовалось по крайней мере в Армийо (1966). Однако эта схема требует наличия хорошей оценки для L, иначе, если скорость обучения слишком велика (относительно 1 / L), то схема не имеет гарантии сходимости. Можно увидеть, что пойдет не так, если функция стоимости представляет собой сглаживание (около точки 0) функции f (t) = | t |. Однако такая хорошая оценка трудна и трудоемка для больших размеров. Кроме того, если градиент функции не является глобально липшицевым, эта схема не имеет гарантии сходимости. Например, это похоже на упражнение в Бертсекас (2016), для функции стоимости ${\displaystyle f(t)=|t|^{1.5}\,}$ и для любой выбранной постоянной скорости обучения со случайной начальной точкой последовательность, построенная по этой специальной схеме, не сходится к глобальному минимуму 0.

Если не заботиться об условии, что скорость обучения должна быть ограничена 1 / L, то эта специальная схема использовалась гораздо раньше, по крайней мере, с 1847 г. Коши, который можно назвать Standard GD (в отличие от SGD). В настройке Stochastic (например, в настройке мини-партии в Глубокое обучение ), Стандартный GD называется Стохастический градиентный спуск, или SGD.

Даже если функция стоимости имеет глобально непрерывный градиент, хорошая оценка константы Липшица для функций стоимости в глубоком обучении может оказаться невыполнимой или желательной, учитывая очень высокие размеры Глубокие нейронные сети. Следовательно, существует методика тонкой настройки скорости обучения при применении Standard GD или SGD. Один из способов - выбрать несколько скоростей обучения из поиска по сетке в надежде, что некоторые из скоростей обучения могут дать хорошие результаты. (Однако, если функция потерь не имеет глобального липшицевого градиента, то пример с ${\displaystyle f(t)=|t|^{1.5}\,}$ выше показывает, что поиск по сетке не может помочь.) Другой способ - это так называемый адаптивный Стандартный GD или SGD, некоторые представители - Adam, Adadelta, RMSProp и так далее, см. Стохастический градиентный спуск. В адаптивном стандартном GD или SGD скорости обучения могут изменяться на каждом шаге n итерации, но другим способом, чем при поиске линии с возвратом для градиентного спуска. По-видимому, было бы дороже использовать поиск по строке с возвратом для градиентного спуска, поскольку нужно выполнять поиск по петле до тех пор, пока не будет выполнено условие Armijo, в то время как для адаптивных стандартных GD или SGD поиск петли не требуется. Большинство из этих адаптивных стандартных GD или SGD не имеют свойства спуска. ${\displaystyle f(x_{n+1})\leq f(x_{n})}$, для всех n, как поиск строки с возвратом для градиентного спуска. Лишь немногие обладают этим свойством и имеют хорошие теоретические свойства, но они оказываются частными случаями поиска по строке с возвратом или, в более общем смысле, условия Армийо. Армийо (1966). Первый - это когда кто-то выбирает постоянную скорость обучения <1 / L, как упоминалось выше, если можно получить хорошую оценку L. Второй - это так называемая скорость обучения с диминшингом, используемая в известной статье Роббинс и Монро (1951), если снова функция имеет глобально непрерывный липшицев градиент (но константа Липшица может быть неизвестна) и скорость обучения сходится к 0.

Резюме

Таким образом, поиск линии с обратным прослеживанием (и модификации) - это метод, который легко реализовать, применим для очень общих функций, имеет очень хорошую теоретическую гарантию (как для сходимости к критическим точкам, так и для избежания седловых точек) и хорошо работает на практике. Несколько других методов, которые имеют хорошую теоретическую гарантию, такие как Уменьшение скорости обучения или Стандартный GD со скоростью обучения <1 / L - оба требуют, чтобы градиент целевой функции был непрерывным по Липшицу, оказываются частным случаем поиска строки с обратным отслеживанием или удовлетворяют условию Армийо. Несмотря на то, что априори требуется, чтобы функция стоимости была непрерывно дифференцируемой для применения этого метода, на практике этот метод можно успешно применить также для функций, которые непрерывно дифференцируемы на плотном открытом подмножестве, таком как ${\displaystyle f(t)=|t|}$ или же ${\displaystyle f(t)=ReLu(t)=\max\{t,0\}}$. Последние функции появляются в Глубокие нейронные сети.

Смотрите также

• Градиентный спуск
• Стохастический градиентный спуск
• Условия Вульфа

Рекомендации

• Absil, P. A .; Mahony, R .; Эндрюс, Б. (2005). «Сходимость итераций методов спуска для аналитических функций стоимости». SIAM J. Optim. 16 (2): 531–547. Дои:10.1137/040605266.
• Армийо, Ларри (1966). «Минимизация функций, имеющих липшицевы первые частные производные». Pacific J. Math. 16 (1): 1–3. Дои:10.2140 / pjm.1966.16.1.
• Attouch, H .; Bolte, J .; Свайтер, Б. Ф. (2011). «Сходимость методов спуска для полуалгебраических и ручных задач: проксимальные алгоритмы, расщепление вперед – назад и регуляризованные методы Гаусса – Зейделя». Математическое программирование. 137: 91–129. Дои:10.1007 / s10107-011-0484-9.
• Бертсекас, Дмитрий П. (2016), Нелинейное программирование, Афина Сайентифик, ISBN  978-1886529052
• Бертсекас, Д. П .; Цициклис, Дж. Н. (2006). «Сходимость градиентов в градиентных методах с ошибками». SIAM J. Optim. 10 (3): 627–642. Дои:10.1137 / S1052623497331063.
• Bray, A.J .; Дин, Д. С. (2007). «Статистика критических точек гауссовских полей на больших размерных пространствах». Письма с физическими проверками. 98: 150–201. Дои:10.1103 / PhysRevLett.98.150201.
• Dauphin, Y.N .; Pascanu, R .; Gulcehre, C .; Чо, К .; Ganguli, S .; Бенджио, Ю. (2014). «Выявление и решение проблемы седловой точки в невыпуклой оптимизации большой размерности». NeurIPS. 14: 2933–2941.
• Ланге, К. (2013). Оптимизация. Нью-Йорк: Springer-Verlag Публикации. ISBN  978-1-4614-5838-8.
• Деннис, Дж. Э.; Шнабель, Р. Б. (1996). Численные методы безусловной оптимизации и нелинейных уравнений. Филадельфия: СИАМ Публикации. ISBN  978-0-898713-64-0.
• Lee, J.D .; Simchowitz, M .; Jordan, M. I .; Рехт, Б. (2016). «Градиентный спуск сходится только к минимизаторам». Труды исследования машинного обучения. 49: 1246–1257.
• Нокедаль, Хорхе; Райт, Стивен Дж. (2000), Численная оптимизация, Springer-Verlag, ISBN  0-387-98793-2
• Panageas, I .; Пилюрас, Г. (2017). «Градиентный спуск сходится только к минимизаторам: неизолированным критическим точкам и инвариантным областям» (PDF). Конференция "Инновации в теоретической информатике": 2:1–2:12. Дои:10.4230 / LIPIcs.ITCS.2017.2.
• Panageas, I .; Piliouras, G .; Ван, X. (2019). «Методы первого порядка почти всегда избегают седловых точек: случай исчезающих размеров шага» (PDF). NeurIPS.
• Роббинс, H .; Монро, С. (1951). «Метод стохастической аппроксимации». Анналы математической статистики. 22 (3): 400–407.
• Truong, T. T .; Нгуен, Х.-Т. (6 сентября 2020 г.). «Метод обратного градиентного спуска и некоторые приложения в крупномасштабной оптимизации. Часть 2: Алгоритмы и эксперименты». Прикладная математика и оптимизация: 30. Дои:10.1007 / s00245-020-09718-8.