25

Учитывая выпуклую функцию стоимости, используя SGD для оптимизации, мы будем иметь градиент (вектор) в определенной точке в процессе оптимизации.

Мой вопрос, учитывая точку на выпуклом, градиент только указывает в направлении, в котором функция увеличивается / уменьшается быстрее всего, или градиент всегда указывает на оптимальную / крайнюю точку функции стоимости ?

Первое является локальной концепцией, второе - глобальной.

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

Направление градиента должно быть направлением, в котором функция быстрее всего увеличивается / уменьшается в этой точке, верно?

neural-networks optimization gradient-descent sgd convex Тайлер 十三将士归玉门
источник

6

Вы когда-нибудь шли прямо вниз по склону горы, только чтобы оказаться в долине, которая продолжает спускаться в другом направлении? Задача состоит в том, чтобы представить себе такую ситуацию с выпуклой топографией: подумайте о лезвии ножа, где гребень самый крутой на вершине.

whuber

4

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

Chill2Macht

3

@ Тайлер, почему твой вопрос конкретно о стохастическом градиентном спуске? Вы представляете что-то другое по сравнению со стандартным градиентным спуском?

Секст Эмпирик

2

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

\frac{π}{2}

$\frac{\pi}{2}$

Восстановить Монику

5

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

малоО

36

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

Серьезное замечание: в этой ветке есть гораздо лучшие ответы, которые также заслуживают одобрения.

Ян Кукацка
источник

27

А сегодняшний контрпример - это ... авокадо!

JDL

11

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

Ян Кукацка

28

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

Интуитивное представление - представить путь спуска, который является изогнутым путем. Смотрите, например, примеры ниже.

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

Если вы можете принять выпуклость

Тогда вы знаете, что есть только одна крайняя точка.
Тогда вы знаете, что вы непременно достигнете крайней точки, пока будете двигаться вниз.
И тогда вы также знаете, что угол между самым крутым направлением спуска и оптимальным направлением всегда не больше $\pi/2$ , как упоминалось в комментариях к секрету Соломонова.

Без выпуклости

Угол может превышать $\pi/2$ . На изображении ниже это подчеркивается рисованием стрелки направления спуска для конкретной точки, где окончательное решение находится за линией, перпендикулярной направлению спуска.

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

В стохастическом градиентном спуске

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

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

Выше изображения для 4 точек данных, генерируемых функцией:

Y_{я} знак равно е^{- 0,4 {Икс}_{я}} - е^{- 0.8 {Икс}_{я}} + ε_{я}

$y_i = e^{-0.4x_i}-e^{-0.8 x_i} + \epsilon_i$

x = 0      2      4      6           
y = 0.006  0.249  0.153  0.098

что приводит к:

невыпуклая задача оптимизации, когда мы минимизируем (нелинейную) функцию стоимости
$S (a, б) знак равно \underset{я знак равно 1}{Σ} {(Y_{я} - (е^{- a {Икс}_{я}} - е^{- б {Икс}_{я}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$ $\nabla S (a, б) знак равно [\begin{matrix} \underset{я знак равно 1}{Σ} 2 {Икс}_{я} е^{- a {Икс}_{я}} (Y_{я} - е^{- a {Икс}_{я}} - е^{- б {Икс}_{я}}) \\ \underset{я знак равно 1}{Σ} - 2 {Икс}_{я} е^{- б {Икс}_{я}} (Y_{я} - е^{- a {Икс}_{я}} - е^{- б {Икс}_{я}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} 2 x_i e^{-a x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \\ \sum_{i=1} -2 x_i e^{-b x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \end{bmatrix}$
выпуклая задача оптимизации (как и любые линейные наименьшие квадраты), когда мы минимизируем
$S (a, б) знак равно \underset{я знак равно 1}{Σ} {(Y_{я} - (a е^{- 0,4 {Икс}_{я}} - б е^{- 0.8 {Икс}_{я}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (a e^{-0.4 x_i}- b e^{-0.8 x_i} )\right)^2$ $\nabla S (a, б) знак равно [\begin{matrix} \underset{я знак равно 1}{Σ} - 2 е^{- 0,4 {Икс}_{я}} (Y_{я} - a е^{- 0,4 {Икс}_{я}} - б е^{- 0.8 {Икс}_{я}}) \\ \underset{я знак равно 1}{Σ} 2 е^{- 0.8 {Икс}_{я}} (Y_{я} - a е^{- 0,4 {Икс}_{я}} - б е^{- 0.8 {Икс}_{я}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ \sum_{i=1} 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$
выпуклая задача оптимизации (но не с одним минимумом), когда мы минимизируем для некоторого конкретного с градиентом это имеет несколько минимумов (есть несколько и для которого ) $i$
$S (a, б) знак равно {(Y_{я} - (a е^{- 0,4 б {Икс}_{я}} - б е^{- 0.8 {Икс}_{я}}))}^{2}$ $S(a,b) = \left( y_i - (a e^{-0.4 b x_i}- b e^{-0.8 x_i}) \right)^2$ $\nabla S (a, б) знак равно [\begin{matrix} - 2 е^{- 0,4 {Икс}_{я}} (Y_{я} - a е^{- 0,4 {Икс}_{я}} - б е^{- 0.8 {Икс}_{я}}) \\ 2 е^{- 0.8 {Икс}_{я}} (Y_{я} - a е^{- 0,4 {Икс}_{я}} - б е^{- 0.8 {Икс}_{я}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$ $a$ $b$ $S = 0$

Автор StackExchangeStrike

Секст Эмпирик
источник

17

Крутой спуск может быть неэффективным, даже если целевая функция сильно выпуклая.

Обыкновенный градиентный спуск

Я имею в виду «неэффективный» в том смысле, что наискорейший спуск может предпринимать шаги, которые резко отклоняются от оптимального, даже если функция сильно выпуклая или даже квадратичная.

Рассмотрим . Это выпукло, потому что это квадратик с положительными коэффициентами. Из проверки видно, что он имеет глобальный минимум при . Он имеет градиент $f(x)=x_1^2 + 25x_2^2$ $x=[0,0]^\top$

\nabla е (Икс) знак равно [\begin{matrix} 2 {Икс}_{1} \\ 50 {Икс}_{2} \end{matrix}]

$\nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix}$

При скорости обучения и начальной догадке мы получаем обновление градиента $\alpha=0.035$ $x^{(0)}=[0.5, 0.5]^\top,$

{Икс}^{(1)} знак равно {Икс}^{(0)} - α \nabla е ({Икс}^{(0)})

$x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right)$

который демонстрирует этот дико колеблющийся прогресс к минимуму.

Действительно, угол образованный между и только постепенно уменьшается до 0. Что это означает в том, что направление обновления иногда неправильное - самое большее, оно почти на 68 градусов - даже если алгоритм сходится и работает правильно. $\theta$ $(x^{(i)}, x^*)$ $(x^{(i)}, x^{(i+1)})$

Каждый шаг сильно колеблется, потому что функция намного круче в направлении чем в направлении . Из-за этого факта мы можем сделать вывод, что градиент не всегда или даже обычно указывает на минимум. Это общее свойство градиентного спуска, когда собственные значения гессиана находятся в разных масштабах. Прогресс является медленным в направлениях, соответствующих собственным векторам с наименьшими соответствующими собственными значениями, и наиболее быстрым в направлениях с самыми большими собственными значениями. Именно это свойство в сочетании с выбором скорости обучения определяет, насколько быстро прогрессирует градиентный спуск. $x_2$ $x_1$ $\nabla^2 f(x)$

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

Стохастический градиентный спуск

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

Больше информации:

Этот ответ заимствует этот пример и рисунок из главы 9 « Дизайн нейронных сетей» (2-е изд.) Мартина Т. Хейгана, Говарда Б. Демута, Марка Хадсона Била, Орландо де Хесуса.

Sycorax говорит восстановить Монику
источник

13

Местное крутое направление не совпадает с глобальным оптимальным направлением. Если бы это было так, то ваше направление градиента не изменилось бы; потому что если вы всегда идете к своему оптимальному значению, ваш вектор направления будет всегда указывать оптимальный. Но это не так. Если бы это было так, зачем беспокоиться о расчете градиента на каждой итерации?

Гюнеш
источник

3

В других ответах освещаются некоторые досадные проблемы со скоростью конвергенции для GD / SGD, но ваш комментарий «SGD может в конечном итоге сойтись ...» не всегда корректен (игнорируя педантичные замечания по поводу слова «может», поскольку кажется, что вы имели в виду "воля").

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

({Икс}_{0}, Y_{0}) знак равно (1, 0)

$(x_0,y_0)=(1,0)$

α

$\alpha$

е (Икс, α) знак равно \sqrt{α^{2} - α Икс},

$f(x,\alpha)=\sqrt{\alpha^2-\alpha x}.$

С MSE в качестве нашей функции стоимости это упрощается до выпуклой функции. Предположим, что мы плохо выбираем скорость обучения чтобы наше правило обновления было следующим:Теперь наша функция стоимости имеет минимум в , но если мы начнем буквально где-нибудь, кроме тогда SGD просто отскочит между циклами между начальной точкой и и никогда не сойдется .

(е ({Икс}_{0}, α) - Y_{0})^{2} знак равно α^{2} - α,

$(f(x_0,\alpha)-y_0)^2=\alpha^2-\alpha,$

β

$\beta$

α_{N + 1} знак равно α_{N} - β (2 α_{N} - 1) знак равно α_{N} - (2 α_{N} - 1) знак равно 1 - α_{N},

$\alpha_{n+1}=\alpha_n-\beta(2\alpha_n-1)=\alpha_n-(2\alpha_n-1)=1-\alpha_n.$

α = \frac{1}{2}

$\alpha=\frac12$ $p=\frac12$

p

$p$

1 - p

$1-p$

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

SGD также может приближаться / получать циклы любой конечной длины, расходиться в направлении , колебаться в направлении (извините за обозначения) и иметь множество других патологических поведений. $\infty$ $\pm\infty$

Одна интересная вещь во всей ситуации состоит в том, что существует бесчисленное множество функций (таких как SGD), которые принимают произвольные выпуклые функции в качестве входных данных, а затем выводят правило обновления, которое всегда быстро сходится к глобальному минимуму (если он существует). Хотя концептуально их существует множество, все наши лучшие попытки выпуклой оптимизации имеют патологические контрпримеры. Каким-то образом идея простого / интуитивно понятного / производительного правила обновления противоречит идее достоверно корректного правила обновления.

Ханс Масгрейв
источник

1

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

β = 1

$\beta=1$

Секст Эмпирик

1

Обратите внимание, что доказательство сходимости SGD предполагает уменьшение размера шага ...

Ян Кукацка

@MartijnWeterings Хорошее наблюдение. Я предполагаю, что мой пример действительно указывает правильное направление. Должен ли я обновить его с 2D-примером, который никогда не указывает правильное направление и расходится?

Ганс Масгрейв

β = 1

$\beta=1$

β > 0

$\beta>0$

β

$\beta$

f (x, α) = \sqrt{\frac{α^{2} - α x}{β}} .

$f(x,\alpha)=\sqrt{\frac{\alpha^2-\alpha x}{\beta}}.$

f

$f$

β

$\beta$

2

Возможно, ответы на этот вопрос требуют быстрого обновления. Похоже, что SGD дает глобальный минимум и в невыпуклом случае (выпуклый это только частный случай этого):

SGD приближается к глобальному минимуму в области глубокого обучения по Star-Convex Path, анонимные авторы , статья под двойным слепым обзором на ICLR 2019

https://openreview.net/pdf?id=BylIciRcYQ

Авторы устанавливают сходимость SGD к глобальному минимуму для невыпуклых задач оптимизации, которые обычно встречаются при обучении нейронной сети. Аргумент использует следующие два важных свойства: 1) потеря тренировки может достичь нулевого значения (приблизительно); 2) SGD следует звездно-выпуклому пути. В таком контексте, хотя SGD долгое время считался рандомизированным алгоритмом, в статье раскрывается, что он по своей сути сходится к глобальному минимуму.

Это должно быть принято с зерном соли, хотя. Статья еще находится на рассмотрении.

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

Толга Бердал
источник

Для выпуклых задач всегда ли градиент в Стохастическом градиентном спуске (SGD) указывает на глобальное экстремальное значение?

Ответы:

Если вы можете принять выпуклость

Без выпуклости

В стохастическом градиентном спуске

Обыкновенный градиентный спуск

Стохастический градиентный спуск