Градиентный спуск

Алгоритм оптимизации

Градиентный спуск в 2D

Градиентный спуск — это метод неограниченной математической оптимизации . Это итерационный алгоритм первого порядка для поиска локального минимума дифференцируемой функции многих переменных .

Идея состоит в том, чтобы сделать повторные шаги в направлении, противоположном градиенту ( или приблизительному градиенту) функции в текущей точке, поскольку это направление наибольшего спуска. И наоборот, шаг в направлении градиента приведет к локальному максимуму этой функции; тогда эта процедура известна как градиентное восхождение . Это особенно полезно в машинном обучении для минимизации функции затрат или потерь. [ ^1] Градиентный спуск не следует путать с алгоритмами локального поиска , хотя оба являются итеративными методами оптимизации .

Градиентный спуск обычно приписывают Огюстену-Луи Коши , который впервые предложил его в 1847 году. ^[2] Жак Адамар независимо предложил аналогичный метод в 1907 году. ^{[3] [4]} Его свойства сходимости для задач нелинейной оптимизации были впервые изучены Хаскелл Карри в 1944 году ^[5] , причем этот метод становился все более хорошо изученным и использовался в последующие десятилетия. ^{[6] [7]}

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

Описание

Иллюстрация градиентного спуска на серии наборов уровней

Градиентный спуск основан на наблюдении, что если функция многих переменных определена и дифференцируема в окрестности точки , то она убывает быстрее всего , если двигаться в направлении отрицательного градиента точки . Отсюда следует, что если ${\displaystyle F(\mathbf {x} )}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle F(\mathbf {x} )}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle F}$ ${\displaystyle \mathbf {a} ,-\nabla F(\mathbf {a} )}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})}$

тогда для достаточно небольшого размера шага или скорости обучения . Другими словами, член вычитается из , потому что мы хотим двигаться против градиента, к локальному минимуму. Принимая во внимание это наблюдение, мы начинаем с предположения о локальном минимуме и рассматриваем такую ​​последовательность, что ${\displaystyle \gamma \in \mathbb {R} _{+}}$ ${\displaystyle F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )}$ ${\displaystyle \gamma \nabla F(\mathbf {a} )}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle \mathbf {x} _{0}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$

Имеем монотонную последовательность

${\displaystyle F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,}$

так что, будем надеяться, последовательность сходится к желаемому локальному минимуму. Обратите внимание, что значение размера шага может меняться на каждой итерации. ${\displaystyle (\mathbf {x} _{n})}$ ${\displaystyle \gamma }$

Можно гарантировать сходимость к локальному минимуму при определенных предположениях на функцию (например, выпуклость и липшицевость ) и определенном выборе . К ним относятся последовательность ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle \nabla F}$ ${\displaystyle \gamma }$

${\displaystyle \gamma _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{T}\left[\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})\right\|^{2}}}}$

как в методе Барзилаи-Борвейна , ^{[8] [9]} или последовательность, удовлетворяющую условиям Вулфа (которую можно найти с помощью поиска по строке ). Когда функция выпуклая , все локальные минимумы также являются глобальными минимумами, поэтому в этом случае градиентный спуск может сходиться к глобальному решению. ${\displaystyle \gamma _{n}}$ ${\displaystyle F}$

Этот процесс иллюстрируется на соседней картинке. Здесь предполагается, что функция определена на плоскости и ее график имеет форму чаши . Синие кривые — это контурные линии , то есть области, в которых значение постоянно. Красная стрелка, начинающаяся в определенной точке, показывает направление отрицательного градиента в этой точке. Обратите внимание, что (отрицательный) градиент в точке ортогонален контурной линии, проходящей через эту точку. Мы видим, что градиентный спуск приводит нас ко дну чаши, то есть к точке, где значение функции минимально. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle F}$

Аналогия для понимания градиентного спуска

Туман в горах

Основную идею градиентного спуска можно проиллюстрировать гипотетическим сценарием. Человек застрял в горах и пытается спуститься вниз (т.е. пытается найти глобальный минимум). Стоит сильный туман, поэтому видимость очень низкая. Поэтому путь вниз с горы не виден, поэтому им приходится использовать местную информацию, чтобы найти минимум. Они могут использовать метод градиентного спуска, который предполагает наблюдение за крутизной холма в их текущем положении, а затем движение в направлении самого крутого спуска (т. е. под гору). Если бы они пытались найти вершину горы (т. е. максимум), то они двигались бы в направлении наибольшего подъема (т. е. в гору). Используя этот метод, они в конечном итоге спускаются с горы или, возможно, застревают в какой-нибудь дыре (т. е. в локальном минимуме или точке седла ), например в горном озере. Однако предположим также, что крутизна холма не очевидна сразу при простом наблюдении, а скорее требует сложного инструмента для измерения, который у человека в данный момент имеется. Измерение крутизны холма с помощью прибора занимает довольно много времени, поэтому им следует свести к минимуму использование прибора, если они хотят спуститься с горы до захода солнца. Тогда трудность состоит в том, чтобы выбрать частоту, с которой им следует измерять крутизну холма, чтобы не сбиться с пути.

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

Выбор размера шага и направления спуска

Поскольку использование слишком маленького размера шага замедлит сходимость, а слишком большой приведет к перерегулированию и расхождению, поиск правильной настройки является важной практической проблемой. Филип Вулф также выступал за использование на практике «умного выбора направления [спуска]». ^[10] Хотя использование направления, которое отклоняется от направления самого крутого спуска, может показаться нелогичным, идея состоит в том, что меньший уклон может быть компенсирован за счет устойчивости на гораздо большем расстоянии. ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Чтобы рассуждать об этом математически, рассмотрим направление и размер шага , а также рассмотрим более общее обновление: ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma _{n}\,\mathbf {p} _{n}}$.

Поиск хороших настроек требует некоторого размышления. Прежде всего, нам бы хотелось, чтобы направление обновления было направлено вниз. Математически, если обозначить угол между и , это требует, чтобы Чтобы сказать больше, нам нужно больше информации о целевой функции, которую мы оптимизируем. При достаточно слабом предположении непрерывной дифференцируемости мы можем доказать, что: ^[11] ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle \theta _{n}}$ ${\displaystyle -\nabla F(\mathbf {a_{n}} )}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \cos \theta _{n}>0.}$ ${\displaystyle F}$

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

В принципе неравенство ( 1 ) можно оптимизировать и выбрать оптимальный размер и направление шага. Проблема в том, что оценка второго члена в квадратных скобках требует оценки , а дополнительные оценки градиента обычно дороги и нежелательны. Некоторые способы решения этой проблемы: ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle \nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})}$

• Откажитесь от преимуществ умного направления спуска, установив , и используйте поиск по строке, чтобы найти подходящий размер шага , например тот, который удовлетворяет условиям Вульфа . Более экономичным способом выбора скорости обучения является поиск по строке с возвратом , метод, который имеет как хорошие теоретические гарантии, так и экспериментальные результаты. Обратите внимание, что не обязательно выбирать градиент; любое направление, имеющее положительное произведение пересечения с градиентом, приведет к уменьшению значения функции (при достаточно малом значении ). ${\displaystyle \mathbf {p} _{n}=\nabla F(\mathbf {a_{n}} )}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Предполагая, что это дважды дифференцируемо, используйте его гессиан для оценки. Затем выберите и оптимизируя неравенство ( 1 ). ${\displaystyle F}$ ${\displaystyle \nabla ^{2}F}$ ${\displaystyle \|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\approx \|t\gamma _{n}\nabla ^{2}F(\mathbf {a} _{n})\mathbf {p} _{n}\|.}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Предполагая, что это Липшиц , используйте его константу Липшица для оценки. Затем выберите и , оптимизируя неравенство ( 1 ). ${\displaystyle \nabla F}$ ${\displaystyle L}$ ${\displaystyle \|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\leq Lt\gamma _{n}\|\mathbf {p} _{n}\|.}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• Создайте собственную модель для . Затем выберите и оптимизируя неравенство ( 1 ). ${\displaystyle \max _{t\in [0,1]}{\frac {\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}}{\|\nabla F(\mathbf {a} _{n})\|_{2}}}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {p} _{n}}$ ${\displaystyle \gamma _{n}}$
• При более строгих предположениях о функции, такой как выпуклость , могут быть возможны более продвинутые методы. ${\displaystyle F}$

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

Решение линейной системы

Алгоритм наискорейшего спуска, примененный к фильтру Винера ^[12]

Градиентный спуск можно использовать для решения системы линейных уравнений.

${\displaystyle A\mathbf {x} -\mathbf {b} =0}$

переформулирована как задача квадратичной минимизации. Если матрица системы вещественно симметрична и положительно определена , то целевая функция определяется как квадратичная функция с минимизацией ${\displaystyle A}$

${\displaystyle F(\mathbf {x} )=\mathbf {x} ^{T}A\mathbf {x} -2\mathbf {x} ^{T}\mathbf {b} ,}$

так что

${\displaystyle \nabla F(\mathbf {x} )=2(A\mathbf {x} -\mathbf {b} ).}$

Для общей вещественной матрицы линейный метод наименьших квадратов определяет ${\displaystyle A}$

${\displaystyle F(\mathbf {x} )=\left\|A\mathbf {x} -\mathbf {b} \right\|^{2}.}$

В традиционных линейных методах наименьших квадратов для вещественных и евклидовых норм используется, и в этом случае ${\displaystyle A}$ ${\displaystyle \mathbf {b} }$

${\displaystyle \nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).}$

Минимизация линейного поиска , находящая локально оптимальный размер шага на каждой итерации, может быть выполнена аналитически для квадратичных функций, и известны явные формулы для локально оптимального размера . ^{[6] [13]} ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Например, для вещественной симметричной и положительно определенной матрицы простой алгоритм может быть следующим: ^[6] ${\displaystyle A}$

${\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

Чтобы избежать умножения дважды за итерацию, отметим, что подразумевается , что дает традиционный алгоритм, ^[14] ${\displaystyle A}$ ${\displaystyle \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} }$ ${\displaystyle \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} }$

${\displaystyle {\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{repeat in the loop:}}\\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} \\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

Этот метод редко используется для решения линейных уравнений, при этом метод сопряженных градиентов является одной из самых популярных альтернатив. Число итераций градиентного спуска обычно пропорционально спектральному числу обусловленности матрицы системы (отношению максимального и минимального собственных значений ) , тогда как сходимость метода сопряженных градиентов обычно определяется квадратным корнем из числа обусловленности, т.е. , это намного быстрее. Оба метода могут извлечь выгоду из предварительной обработки , где градиентный спуск может потребовать меньше предположений в отношении предварительной обработки. ^[14] ${\displaystyle \kappa (A)}$ ${\displaystyle A}$ ${\displaystyle A^{T}A}$

Решение нелинейной системы

Градиентный спуск также можно использовать для решения системы нелинейных уравнений . Ниже приведен пример, показывающий, как использовать градиентный спуск для решения трех неизвестных переменных: x ₁ , x ₂ и x ₃ . В этом примере показана одна итерация градиентного спуска.

Рассмотрим нелинейную систему уравнений

${\displaystyle {\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}}$

Введем ассоциированную функцию

${\displaystyle G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},}$

где

${\displaystyle \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.}$

Теперь можно определить целевую функцию

${\displaystyle {\begin{aligned}F(\mathbf {x} )&={\frac {1}{2}}G^{\mathrm {T} }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}}$

которые мы постараемся минимизировать. В качестве первоначального предположения давайте воспользуемся

${\displaystyle \mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.}$

Мы знаем это

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}\nabla F(\mathbf {0} )=\mathbf {0} -\gamma _{0}J_{G}(\mathbf {0} )^{\mathrm {T} }G(\mathbf {0} ),}$

где матрица Якобиана имеет вид ${\displaystyle J_{G}}$

${\displaystyle J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.}$

Мы рассчитываем:

${\displaystyle J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.}$

Таким образом

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},}$

и

${\displaystyle F(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.}$

Анимация, показывающая первые 83 итерации градиентного спуска, примененные к этому примеру. Поверхности являются изоповерхностями текущего предположения , а стрелки показывают направление спуска. Из-за небольшого и постоянного размера шага сходимость происходит медленно. ${\displaystyle F(\mathbf {x} ^{(n)})}$ ${\displaystyle \mathbf {x} ^{(n)}}$

Теперь нужно найти подходящее такое, чтобы ${\displaystyle \gamma _{0}}$

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)\leq F\left(\mathbf {x} ^{(0)}\right)=F(\mathbf {0} ).}$

Это можно сделать с помощью любого из множества алгоритмов поиска строк . Можно также просто догадаться , что дает ${\displaystyle \gamma _{0}=0.001,}$

${\displaystyle \mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.}$

Оценка целевой функции по этому значению дает

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.}$

Уменьшение от до значения следующего шага ${\displaystyle F(\mathbf {0} )=58.456}$

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)=23.306}$

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

Комментарии

Градиентный спуск работает в пространствах любого количества измерений, даже в бесконечномерных. В последнем случае пространство поиска обычно представляет собой функциональное пространство , и для определения направления спуска вычисляется производная Фреше функционала, который необходимо минимизировать. ^[7]

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

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

Градиентный спуск можно объединить с поиском по строке , находя локально оптимальный размер шага на каждой итерации. Выполнение поиска линии может занять много времени. И наоборот, использование фиксированного малого значения может привести к плохой сходимости, а использование большого значения может привести к расхождению. Тем не менее, можно чередовать малые и большие размеры шагов, чтобы улучшить скорость сходимости. ^{[15] [16]} ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Лучшими альтернативами могут быть методы, основанные на методе Ньютона и обращении гессиана с использованием методов сопряженных градиентов . ^{[17] [18]} Как правило, такие методы сходятся за меньшее количество итераций, но стоимость каждой итерации выше. Примером может служить метод BFGS , который заключается в вычислении на каждом шаге матрицы, на которую умножается вектор градиента, чтобы перейти в «лучшее» направление, в сочетании с более сложным алгоритмом поиска линии , чтобы найти «лучшее» значение. В случае больших задач, где преобладают проблемы с памятью компьютера, вместо BFGS или метода наикрутейшего спуска следует использовать метод ограниченной памяти, такой как L-BFGS . ${\displaystyle \gamma .}$

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

Градиентный спуск можно рассматривать как применение метода Эйлера для решения обыкновенных дифференциальных уравнений к градиентному потоку . В свою очередь, это уравнение может быть получено как оптимальный регулятор ^[19] для системы управления с заданной в форме обратной связи . ${\displaystyle x'(t)=-\nabla f(x(t))}$ ${\displaystyle x'(t)=u(t)}$ ${\displaystyle u(t)}$ ${\displaystyle u(t)=-\nabla f(x(t))}$

Модификации

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

Методы быстрого градиента

Юрий Нестеров предложил ^[20] простую модификацию, которая обеспечивает более быструю сходимость для выпуклых задач и с тех пор получила дальнейшее обобщение. Для гладких задач без ограничений этот метод называется методом быстрого градиента (FGM) или методом ускоренного градиента (AGM). В частности, если дифференцируемая функция выпукла и липшицева и не предполагается, что она сильно выпукла , то ошибка в целевом значении, генерируемая на каждом шаге методом градиентного спуска , будет ограничена . При использовании метода ускорения Нестерова ошибка уменьшается при . ^{[21] [22]} Известно, что скорость убывания функции стоимости оптимальна для методов оптимизации первого порядка. Тем не менее, существует возможность улучшить алгоритм за счет уменьшения постоянного коэффициента. Метод оптимизированного градиента (OGM) ^[23] уменьшает эту константу в два раза и является оптимальным методом первого порядка для крупномасштабных задач. ^[24] ${\displaystyle F}$ ${\displaystyle \nabla F}$ ${\displaystyle F}$ ${\displaystyle k}$ ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k}}\right)}$ ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k^{2}}}\right)}$ ${\displaystyle {\mathcal {O}}\left({k^{-2}}\right)}$

Для ограниченных или негладких задач FGM Нестерова называется методом быстрого проксимального градиента (FPGM), ускорением метода проксимального градиента .

Метод импульса или тяжелого шара

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

Этот метод используется при стохастическом градиентном спуске и как расширение алгоритмов обратного распространения ошибки , используемых для обучения искусственных нейронных сетей . ^{[26] [27]} В направлении обновления стохастический градиентный спуск добавляет стохастическое свойство. Веса можно использовать для вычисления производных.

Преимущества и недостатки

Преимущества и недостатки методов градиентного спуска обобщены в конспектах лекций Немировского и БенТала. ^{[28] : Раздел 6}

Расширения

Градиентный спуск можно расширить для обработки ограничений , включив проекцию на набор ограничений. Этот метод возможен только в том случае, если проекцию можно эффективно вычислить на компьютере. При соответствующих предположениях этот метод сходится. Этот метод является частным случаем алгоритма вперед-назад для монотонных включений (включающего выпуклое программирование и вариационные неравенства ). ^[29]

Градиентный спуск — это частный случай зеркального спуска, в котором в качестве заданного расхождения Брегмана используется квадрат Евклидова расстояния . ^[30]

Теоретические свойства

Свойства градиентного спуска зависят от свойств целевой функции и используемого варианта градиентного спуска (например, если используется шаг поиска линии ). Сделанные предположения влияют на скорость сходимости и другие свойства, которые можно доказать для градиентного спуска. ^[31] Например, если предполагается, что цель сильно выпуклая и липшицевая гладкая , то градиентный спуск сходится линейно с фиксированным размером шага. ^[1] Более мягкие предположения приводят либо к более слабым гарантиям сходимости, либо требуют более сложного выбора размера шага. ^[31]

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

• Поиск строки с возвратом
• Метод сопряженных градиентов
• Стохастический градиентный спуск
• Рпроп
• Правило Дельты
• Условия Вульфа
• Предварительное кондиционирование
• Алгоритм Бройдена–Флетчера–Гольдфарба–Шенно
• Формула Дэвидона – Флетчера – Пауэлла
• Метод Нелдера-Мида
• Алгоритм Гаусса – Ньютона
• скалолазание
• Квантовый отжиг
• CLS (непрерывный локальный поиск)
• Нейроэволюция

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

1. Бойд, Стивен; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация. Издательство Кембриджского университета. ISBN 978-0-521-83378-3.
2. Лемарешаль, К. (2012). «Коши и градиентный метод» (PDF) . Дополнительная документация по математике : 251–254.
3. Адамар, Жак (1908). «Мемуар о проблеме анализа, связанной с равновесием эластичных бляшек». Мемуары представлены дайверами и иностранцами в Академии наук Института Франции . 33 .
4. Курант, Р. (1943). «Вариационные методы решения задач равновесия и колебаний». Бюллетень Американского математического общества . 49 (1): 1–23. дои : 10.1090/S0002-9904-1943-07818-4 .
5. Карри, Хаскелл Б. (1944). «Метод наискорейшего спуска для нелинейных задач минимизации». Кварта. Прил. Математика . 2 (3): 258–261. дои : 10.1090/qam/10667 .
6. Поляк, Борис (1987). Введение в оптимизацию.
7. Акилов, ГП; Канторович, Л.В. (1982). Функциональный анализ (2-е изд.). Пергамон Пресс. ISBN 0-08-023036-9.
8. Барзилай, Джонатан; Борвейн, Джонатан М. (1988). «Методы двухточечного градиента размера шага». Журнал IMA численного анализа . 8 (1): 141–148. дои : 10.1093/иманум/8.1.141.
9. Флетчер, Р. (2005). «О методе Барзилаи-Борвейна». Ин Ци, Л.; Тео, К.; Ян, X. (ред.). Оптимизация и управление с помощью приложений . Прикладная оптимизация. Том. 96. Бостон: Спрингер. стр. 235–256. ISBN 0-387-24254-6.
10. Вулф, Филип (апрель 1969 г.). «Условия сходимости методов восхождения». Обзор СИАМ . 11 (2): 226–235. дои : 10.1137/1011036.
11. Бернштейн, Джереми; Вахдат, Араш; Юэ, Исон; Лю, Мин-Ю (12 июня 2020 г.). «О расстоянии между двумя нейронными сетями и стабильности обучения». arXiv : 2002.03432 [cs.LG].
12. Хайкин, Саймон С. Теория адаптивного фильтра. Pearson Education India, 2008. – с. 108-142, 217-242
13. Саад, Юсеф (2003). Итерационные методы для разреженных линейных систем (2-е изд.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. стр. 195. ISBN. 978-0-89871-534-7.
14. Баумистер, Хенрикус; Догерти, Эндрю; Князев, Андрей В. (2015). «Несимметричное предварительное условие для методов сопряженного градиента и наискорейшего спуска». Procedia Информатика . 51 : 276–285. arXiv : 1212.6680 . дои : 10.1016/j.procs.2015.05.241 .
15. Альтшулер, Джейсон (Джейсон М.) (2018). Жадность, хеджирование и ускорение в выпуклой оптимизации (Диссертация). Массачусетский Институт Технологий.
16. Паршалл, Эллисон (11 августа 2023 г.). «Рискованные гигантские шаги могут быстрее решить проблемы оптимизации». Журнал Кванта . Проверено 11 августа 2023 г.
17. Нажмите, WH ; Теукольский, С.А. ; Феттерлинг, WT; Фланнери, BP (1992). Численные рецепты в C: Искусство научных вычислений (2-е изд.). Нью-Йорк: Издательство Кембриджского университета . ISBN 0-521-43108-5.
18. Струц, Т. (2016). Подбор данных и неопределенность: практическое введение в метод наименьших квадратов и далее (2-е изд.). Спрингер Вьюег. ISBN 978-3-658-11455-8.
19. Росс, IM (июль 2019 г.). «Теория оптимального управления для нелинейной оптимизации». Журнал вычислительной и прикладной математики . 354 : 39–51. дои : 10.1016/j.cam.2018.12.044 . S2CID  127649426.
20. Нестеров, Юрий (2004). Вводные лекции по выпуклой оптимизации: базовый курс . Спрингер. ISBN 1-4020-7553-7.
21. Ванденберге, Ливен (2019). «Методы быстрого градиента» (PDF) . Конспекты лекций по EE236C в Калифорнийском университете в Лос-Анджелесе .
22. Уокингтон, Ноэль Дж. (2023). «Метод Нестерова выпуклой оптимизации». Обзор СИАМ . 65 (2): 539–562. дои : 10.1137/21M1390037. ISSN  0036-1445.
23. Ким, Д.; Фесслер, Дж. А. (2016). «Оптимизированные методы первого порядка для плавной выпуклой минимизации». Математическое программирование . 151 (1–2): 81–107. arXiv : 1406.5468 . дои : 10.1007/s10107-015-0949-3. ПМК 5067109 . PMID  27765996. S2CID  207055414. 
24. Дрори, Йоэль (2017). «Точная информационная сложность плавной выпуклой минимизации». Журнал сложности . 39 : 1–16. arXiv : 1606.01424 . дои : 10.1016/j.jco.2016.11.001. S2CID  205861966.
25. Цянь, Нин (январь 1999 г.). «Об импульсе в алгоритмах обучения градиентному спуску». Нейронные сети . 12 (1): 145–151. CiteSeerX 10.1.1.57.5612 . дои : 10.1016/S0893-6080(98)00116-6. PMID  12662723. S2CID  2783597. 
26. «Импульс и адаптация скорости обучения». Университет Уилламетт . Проверено 17 октября 2014 г.
27. Джеффри Хинтон ; Нитиш Шривастава; Кевин Сверски. «Метод импульса». Курсера . Проверено 2 октября 2018 г.Часть серии лекций онлайн-курса Coursera «Нейронные сети для машинного обучения». Архивировано 31 декабря 2016 г. в Wayback Machine .
28. Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .
29. Комбеттс, Польша; Песке, Ж.-К. (2011). «Методы проксимального разделения при обработке сигналов». В Баушке, Х.Х.; Бурачик, РС ; Комбеттс, Польша; Эльзер, В.; Люк, доктор медицинских наук; Волкович, Х. (ред.). Алгоритмы фиксированной точки для решения обратных задач в науке и технике . Нью-Йорк: Спрингер. стр. 185–212. arXiv : 0912.3522 . ISBN 978-1-4419-9568-1.
30. «Алгоритм спуска зеркала».
31. Бубек, С. (2014). Теория выпуклой оптимизации машинного обучения. ArXiv, абс/1405.4980.

дальнейшее чтение

• Бойд, Стивен ; Ванденберге, Ливен (2004). «Неограниченная минимизация» (PDF) . Выпуклая оптимизация . Нью-Йорк: Издательство Кембриджского университета. стр. 457–520. ISBN 0-521-83378-7.
• Чонг, Эдвин КП; Жак, Станислав Х. (2013). «Градиентные методы». Введение в оптимизацию (Четвертое изд.). Хобокен: Уайли. стр. 131–160. ISBN 978-1-118-27901-4.
• Химмельблау, Дэвид М. (1972). «Процедуры неограниченной минимизации с использованием производных». Прикладное нелинейное программирование . Нью-Йорк: МакГроу-Хилл. стр. 63–132. ISBN 0-07-028921-2.

Внешние ссылки

• Использование градиентного спуска в C++, Boost, Ublas для линейной регрессии
• В серии видеороликов Академии Хана обсуждается градиентное восхождение.
• Онлайн-книга, обучающая градиентному спуску в контексте глубоких нейронных сетей
• Архивировано в Ghostarchive и Wayback Machine: «Градиентный спуск, как обучаются нейронные сети». 3Синий1Коричневый . 16 октября 2017 г. — через YouTube .
• Справочник по теоремам сходимости для (стохастических) градиентных методов