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

Optimization algorithm

Градиентный спуск в 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]

Градиентный спуск является частным случаем зеркального спуска, использующего квадрат евклидова расстояния в качестве заданной дивергенции Брегмана . ^[29]

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

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

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

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

Ссылки

1. Boyd, Stephen; Vandenberghe, Lieven (2004-03-08). Выпуклая оптимизация. Cambridge University Press. ISBN 978-0-521-83378-3.
2. Lemaréchal, C. (2012). «Коши и градиентный метод» (PDF) . Doc Math Extra : 251–254. Архивировано из оригинала (PDF) 29-12-2018 . Получено 26-01-2020 .
3. Адамар, Жак (1908). «Мемуар о проблеме анализа, связанной с равновесием эластичных бляшек». Мемуары представлены дайверами и иностранцами в Академии наук Института Франции . 33 .
4. Курант, Р. (1943). «Вариационные методы решения задач равновесия и колебаний». Бюллетень Американского математического общества . 49 (1): 1–23. doi : 10.1090/S0002-9904-1943-07818-4 .
5. Карри, Хаскелл Б. (1944). «Метод наискорейшего спуска для нелинейных задач минимизации». Quart. Appl. Math . 2 (3): 258–261. doi : 10.1090/qam/10667 .
6. Поляк, Борис (1987). Введение в оптимизацию.
7. Акилов, ГП; Канторович, ЛВ (1982). Функциональный анализ (2-е изд.). Pergamon Press. ISBN 0-08-023036-9.
8. Барзилай, Джонатан; Борвейн, Джонатан М. (1988). «Двухточечные методы градиента с шагом». Журнал численного анализа IMA . 8 (1): 141–148. doi :10.1093/imanum/8.1.141.
9. Флетчер, Р. (2005). «О методе Барзилая–Борвейна». В Qi, L.; Teo, K.; Yang, X. (ред.). Оптимизация и управление с приложениями . Прикладная оптимизация. Т. 96. Бостон: Springer. С. 235–256. ISBN 0-387-24254-6.
10. Вулф, Филипп (апрель 1969). «Условия сходимости для методов восхождения». Обзор SIAM . 11 (2): 226–235. doi :10.1137/1011036.
11. Бернстайн, Джереми; Вахдат, Араш; Юэ, Исонг; Лю, Мин-Ю (2020-06-12). «О расстоянии между двумя нейронными сетями и стабильности обучения». 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. Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). «Несимметричное предварительное обусловливание для методов сопряженного градиента и наискорейшего спуска». Procedia Computer Science . 51 : 276–285. arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 .
15. Альтшулер, Джейсон (Джейсон М.) (2018). Жадность, хеджирование и ускорение в выпуклой оптимизации (диссертация). Массачусетский технологический институт.
16. Паршалл, Эллисон (11 августа 2023 г.). «Рискованные гигантские шаги могут быстрее решать проблемы оптимизации». Журнал Quanta . Получено 11 августа 2023 г.
17. Press, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (1992). Числовые рецепты на языке C: Искусство научных вычислений (2-е изд.). Нью-Йорк: Cambridge University Press . ISBN 0-521-43108-5.
18. Страц, Т. (2016). Подгонка данных и неопределенность: практическое введение в метод взвешенных наименьших квадратов и далее (2-е изд.). Springer Vieweg. ISBN 978-3-658-11455-8.
19. Росс, ИМ (июль 2019 г.). «Оптимальная теория управления для нелинейной оптимизации». Журнал вычислительной и прикладной математики . 354 : 39–51. doi : 10.1016/j.cam.2018.12.044 . S2CID  127649426.
20. Нестеров, Юрий (2004). Вводные лекции по выпуклой оптимизации: базовый курс . Springer. ISBN 1-4020-7553-7.
21. Ванденберге, Ливен (2019). «Методы быстрого градиента» (PDF) . Конспекты лекций по EE236C в Калифорнийском университете в Лос-Анджелесе .
22. Walkington, Noel J. (2023). «Метод Нестерова для выпуклой оптимизации». SIAM Review . 65 (2): 539–562. doi :10.1137/21M1390037. ISSN  0036-1445.
23.  . А. (2016). «Оптимизированные методы первого порядка для гладкой выпуклой минимизации». Математическое программирование . 151 (1–2): 81–107. arXiv : 1406.5468 . doi :10.1007/s10107-015-0949-3. PMC 5067109. PMID 27765996. S2CID  207055414. 
24. Дрори, Йоэль (2017). «Точная информационная сложность гладкой выпуклой минимизации». Журнал сложности . 39 : 1–16. arXiv : 1606.01424 . doi : 10.1016/j.jco.2016.11.001. S2CID  205861966.
25. Цянь, Нин (январь 1999). «О члене импульса в алгоритмах обучения градиентного спуска». Нейронные сети . 12 (1): 145–151. CiteSeerX 10.1.1.57.5612 . doi :10.1016/S0893-6080(98)00116-6. PMID  12662723. S2CID  2783597. 
26. "Momentum and Learning Rate Adaptation". Willamette University . Получено 17 октября 2014 г.
27. Джеффри Хинтон ; Нитиш Шривастава; Кевин Сверски. «Метод импульса». Coursera . Получено 2 октября 2018 г.Часть цикла лекций для онлайн-курса Coursera «Нейронные сети для машинного обучения». Архивировано 31 декабря 2016 г. на Wayback Machine .
28. Combettes, PL; Pesquet, J.-C. (2011). «Методы проксимального расщепления в обработке сигналов». В Bauschke, HH; Burachik, RS ; Combettes, PL; Elser, V.; Luke, DR; Wolkowicz, H. (ред.). Алгоритмы с фиксированной точкой для обратных задач в науке и технике . Нью-Йорк: Springer. стр. 185–212. arXiv : 0912.3522 . ISBN 978-1-4419-9568-1.
29. «Алгоритм зеркального спуска».
30. Bubeck, S. (2014). Теория выпуклой оптимизации для машинного обучения. ArXiv, abs/1405.4980.

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

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

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

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