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

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

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

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

Мотивация

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

Подробные шаги см. в Armijo (1966) , Bertsekas (2016) :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткое содержание

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

См. также

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

Ссылки

• Абсил, Пенсильвания; Махони, Р.; Эндрюс, Б. (2005). «Сходимость итераций методов спуска для аналитических функций стоимости». СИАМ Дж. Оптим. 16 (2): 531–547. дои : 10.1137/040605266 .
• Армихо, Ларри (1966). «Минимизация функций, имеющих липшицевы непрерывные первые частные производные» . Пасифик Дж. Математика . 16 (1): 1–3. дои : 10.2140/pjm.1966.16.1 .
• Аттач, Х.; Болт, Дж.; Свайтер, Б.Ф. (2011). «Сходимость методов спуска для полуалгебраических и ручных задач: проксимальные алгоритмы, расщепление вперед-назад и регуляризованные методы Гаусса – Зейделя» . Математическое программирование . 137 (1–2): 91–129. дои : 10.1007/s10107-011-0484-9 .
• Берцекас, Дмитрий П. (2016), Нелинейное программирование , Athena Scientific , ISBN  978-1886529052
• Берцекас, ДП; Цициклис, Ю.Н. (2006). «Градиентная сходимость в градиентных методах с ошибками» . СИАМ Дж. Оптим. 10 (3): 627–642. CiteSeerX   10.1.1.421.193 . дои : 10.1137/S1052623497331063 .
• Брей, Эй Джей; Дин, DS (2007). «Статистика критических точек гауссовских полей на пространствах большой размерности» . Письма о физических отзывах . 98 (15): 150–201. arXiv : cond-mat/0611023 . Бибкод : 2007PhRvL..98o0201B . doi : 10.1103/PhysRevLett.98.150201 . ПМИД   17501322 .
• Дофин, Ю.Н.; Паскану, Р.; Гульчере, К.; Чо, К.; Гангули, С.; Бенджио, Ю. (2014). «Идентификация и решение проблемы седловой точки в многомерной невыпуклой оптимизации» . НейриПС . 14 : 2933–2941. arXiv : 1406.2572 .
• Ланге, К. (2013). Оптимизация . Нью-Йорк: Публикации Springer-Verlag . ISBN  978-1-4614-5838-8 .
• Деннис, JE ; Шнабель, РБ (1996). Численные методы неограниченной оптимизации и нелинейных уравнений . Филадельфия: SIAM Публикации . ISBN  978-0-898713-64-0 .
• Ли, доктор юридических наук; Симховиц, М.; Джордан, Мичиган; Рехт, Б. (2016). «Градиентный спуск сходится только к минимизаторам» . Труды исследований машинного обучения . 49 : 1246–1257.
• Носедаль, Хорхе ; Райт, Стивен Дж. (2000), Численная оптимизация , Springer-Verlag , ISBN  0-387-98793-2
• Панагеас, И.; Пилиурас, Г. (2017). «Градиентный спуск сходится только к минимизаторам: неизолированным критическим точкам и инвариантным областям». 8-я конференция «Инновации в теоретической информатике» (ITCS 2017) (PDF) . Международные труды Лейбница по информатике (LIPIcs). Том. 67. Замок Дагштуль – Центр информатики Лейбница. стр. 2:1–2:12. дои : 10.4230/LIPIcs.ITCS.2017.2 . ISBN  9783959770293 .
• Панагеас, И.; Пилиурас, Г.; Ван, X. (2019). «Методы первого порядка почти всегда избегают седловых точек: случай исчезающего размера шага» (PDF) . НейриПС . arXiv : 1906.07772 .
• Роббинс, Х.; Монро, С. (1951). «Метод стохастической аппроксимации» . Анналы математической статистики . 22 (3): 400–407. дои : 10.1214/aoms/1177729586 .
• Труонг, ТТ; Нгуен, Х.-Т. (6 сентября 2020 г.). «Метод градиентного спуска с возвратом и некоторые приложения в крупномасштабной оптимизации. Часть 2: Алгоритмы и эксперименты» . Прикладная математика и оптимизация . 84 (3): 2557–2586. дои : 10.1007/s00245-020-09718-8 . hdl : 10852/79322 . {{cite journal}}: CS1 maint: дата и год ( ссылка )