Поиск с возвратом по строке

Эта статья включает список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Сентябрь 2020 г. ) ( Узнайте, как и когда удалять это сообщение )

В (неограниченной) математической оптимизации возвратный линейный поиск — это метод линейного поиска для определения величины перемещения в заданном направлении поиска . Его использование требует, чтобы целевая функция была дифференцируемой и чтобы ее градиент был известен.

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

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

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

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

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

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

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

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

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

Это условие взято из Armijo (1966). Начиная с максимального значения размера шага кандидата , используя параметры управления поиском и , алгоритм поиска линии обратного отслеживания может быть выражен следующим образом:${\displaystyle \alpha _{0}>0\,}$${\displaystyle \тау \,\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 \mathbf {x} _{n+1}=\mathbf {x} _{n}+\alpha (\mathbf {x} _{n},\mathbf {p} _{n})\,\mathbf {p} _{n}}$${\displaystyle n}$
3. Возвращаем как минимизирующую позицию и как минимум функции.${\displaystyle \mathbf {x} _{n}}$${\displaystyle f(\mathbf {x} _{n})}$

Для обеспечения хорошего поведения необходимо, чтобы некоторые условия были выполнены . Грубо говоря, не должно быть слишком далеко от . Точная версия выглядит следующим образом (см., например, Bertsekas (2016)). Существуют константы , так что выполняются следующие два условия:${\displaystyle \mathbf {p} _{n}}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \nabla f(\mathbf {x} _{n})}$${\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})}$

Это решает вопрос, существует ли систематический способ найти положительное число — в зависимости от функции f, точки и направления спуска — так, чтобы все скорости обучения удовлетворяли условию Армихо. Когда , мы можем выбрать в порядке , где — локальная константа Липшица для градиента вблизи точки (см. непрерывность Липшица ). Если функция равна , то близка к гессиану функции в точке . Подробнее см. Armijo (1966).${\displaystyle \beta (\mathbf {x} ,\mathbf {p} )}$${\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} }$

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

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

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

Аргументом против использования линейного поиска с возвратом, в частности, в масштабной оптимизации, является то, что удовлетворение условия Армихо требует больших затрат. Существует способ (так называемый двухсторонний возврат), чтобы обойти его, с хорошими теоретическими гарантиями, и он был протестирован с хорошими результатами на глубоких нейронных сетях , см. Truong & Nguyen (2020). (Там можно найти также хорошие/стабильные реализации условия Армихо и его комбинации с некоторыми популярными алгоритмами, такими как Momentum и NAG, на таких наборах данных, как Cifar10 и Cifar100.) Можно заметить, что если последовательность сходится (как и хотелось бы при использовании итеративного метода оптимизации), то последовательность скоростей обучения должна мало меняться, когда n достаточно велико. Поэтому, если при поиске всегда начинать с , можно было бы потратить много времени, если бы оказалось, что последовательность остается далеко от . Вместо этого следует искать , начиная с . Второе наблюдение заключается в том, что может быть больше, чем , и, следовательно, следует разрешить увеличить скорость обучения (а не просто уменьшить, как в разделе Алгоритм). Вот подробный алгоритм для двустороннего обратного отслеживания: На шаге n${\displaystyle \mathbf {x} _{n}}$${\displaystyle \alpha _{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}}$

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

(В работе Nocedal & Wright (2000) можно найти описание алгоритма с 1), 3) и 4) выше, который не был протестирован в глубоких нейронных сетях до цитируемой статьи.)

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

1. Установить счетчик итераций j=0.
2. На этапах используйте двусторонний возврат.${\displaystyle jN+1,\ldots ,jN+m}$
3. На каждом шаге k в наборе : Установите . Если , то выберите и . (Так что в этом случае используйте скорость обучения без изменений.) В противном случае, если , используйте двусторонний возврат. Увеличьте k на 1 и повторите.${\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}$
4. Увеличьте j на 1.

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

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

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

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

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

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

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

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

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

• Эбсил, ПА; Махони, Р.; Эндрюс, Б. (2005). «Сходимость итераций методов спуска для аналитических функций стоимости». SIAM J. Optim. 16 (2): 531– 547. doi :10.1137/040605266.
• Армиджо, Ларри (1966). «Минимизация функций, имеющих непрерывные по Липшицу первые частные производные». Pacific J. Math . 16 (1): 1– 3. doi : 10.2140/pjm.1966.16.1 .
• Attouch, H.; Bolte, J.; Svaiter, BF (2011). «Сходимость методов спуска для полуалгебраических и ручных задач: проксимальные алгоритмы, прямое-обратное расщепление и регуляризованные методы Гаусса-Зейделя». Математическое программирование . 137 ( 1– 2): 91– 129. doi : 10.1007/s10107-011-0484-9 .
• Берцекас, Димитрий П. (2016), Нелинейное программирование, Athena Scientific , ISBN 978-1886529052
• Берцекас, Д.П.; Цициклис, Дж.Н. (2006). «Сходимость градиента в градиентных методах с ошибками». SIAM J. Optim. 10 (3): 627– 642. CiteSeerX  10.1.1.421.193 . doi : 10.1137/S1052623497331063 .
• Брей, А. Дж.; Дин, Д. С. (2007). «Статистика критических точек гауссовых полей на пространствах большой размерности». Physical Review Letters . 98 (15): 150– 201. arXiv : cond-mat/0611023 . Bibcode :2007PhRvL..98o0201B. doi : 10.1103/PhysRevLett.98.150201 . PMID  17501322.
• Дофин, YN; Паскану, R.; Гульчехре, C.; Чо, K.; Гангули, S.; Бенжио, Y. (2014). «Определение и решение проблемы седловой точки в многомерной невыпуклой оптимизации». NeurIPS . 14 : 2933– 2941. arXiv : 1406.2572 .
• Ланге, К. (2013). Оптимизация . Нью-Йорк: Springer-Verlag Publications. ISBN 978-1-4614-5838-8.
• Деннис, Дж. Э .; Шнабель, Р. Б. (1996). Численные методы неограниченной оптимизации и нелинейных уравнений . Филадельфия: SIAM Publications. ISBN 978-0-898713-64-0.
• Ли, Дж. Д.; Симховиц, М.; Джордан, М.И.; Рехт, Б. (2016). «Градиентный спуск сходится только к минимизаторам». Труды исследований машинного обучения . 49 : 1246–1257 .
• Нокедаль, Хорхе ; Райт, Стивен Дж. (2000), Численная оптимизация, Springer-Verlag , ISBN 0-387-98793-2
• Panageas, I.; Piliouras, G. (2017). «Градиентный спуск сходится только к минимизаторам: неизолированные критические точки и инвариантные области». 8-я конференция «Инновации в теоретической информатике» (ITCS 2017) (PDF) . Leibniz International Proceedings in Informatics (LIPIcs). Том 67. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. стр. 2:1–2:12. doi : 10.4230/LIPIcs.ITCS.2017.2 . ISBN 9783959770293.
• Panageas, I.; Piliouras, G.; Wang, X. (2019). «Методы первого порядка почти всегда избегают седловых точек: случай исчезающих размеров шагов» (PDF) . NeurIPS . arXiv : 1906.07772 .
• Роббинс, Х.; Монро, С. (1951). «Метод стохастической аппроксимации». Annals of Mathematical Statistics . 22 (3): 400– 407. doi : 10.1214/aoms/1177729586 .
• Truong, TT; Nguyen, H.-T. (6 сентября 2020 г.). «Метод градиентного спуска с обратным отслеживанием и некоторые его применения в крупномасштабной оптимизации. Часть 2: Алгоритмы и эксперименты». Прикладная математика и оптимизация . 84 (3): 2557– 2586. doi : 10.1007/s00245-020-09718-8 . hdl : 10852/79322 .{{cite journal}}: CS1 maint: date and year (link)