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

Правило

$$x_{k+1} = x_k - \htmlData{k=step}{\alpha} \, \htmlData{k=dir}{\nabla f(x_k)}$$

Направление обосновано в блоке 2: минус градиент даёт наибольшее убывание среди всех направлений единичной длины. Обратите внимание, что это утверждение локальное — оно про производную в точке, а не про путь к минимуму. Именно поэтому «наискорейший спуск» и «быстрый метод» — разные вещи.

Шаг — единственный параметр, и на нём держится всё.

Что происходит при разных шагах

Возьмите первый ландшафт — круглую чашу — и подвигайте шаг. Кривизна там равна $2$, то есть $L = 2$ и порог устойчивости $2/L = 1$.

круглая чашавытянутая чашабанан Розенброка

лосс, логарифмическая шкала

шаг α

0.1

итераций

40

f в конце

1.28e-7

обусловленность κ

1

порог 2/L

1

 

сходится

Четыре режима, которые стоит пройти на круглой чаше:

шаг	что видно
$0.05$	плавно, но медленно: много итераций
$0.5 = 1/L$	попадание в минимум за одну итерацию
$0.8$	сходится, но траектория перескакивает через минимум
$1.0 = 2/L$	вечные колебания, лосс не падает
$1.1$	расходимость, лосс уходит в бесконечность

Строка $2/L$ — та, которую полезно увидеть своими глазами: метод не «сходится плохо», он не сходится вообще, и при этом не расходится. Ровно на границе.

Как выбирают шаг на практике

Теоретический оптимум $\alpha = 2/(L+\mu)$ требует знать спектр гессиана, которого нет. Поэтому:

подход	как работает	где применяют
подбор по сетке	пробуют $10^{-1}, 10^{-2}, \dots$	глубокое обучение
поиск максимального устойчивого	увеличивают, пока лосс не взорвётся, берут вдвое меньше	практическое правило
линейный поиск (Armijo)	уменьшают шаг, пока лосс не упадёт достаточно	классическая оптимизация
адаптивные методы	шаг свой у каждой координаты	Adam, урок 080

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

Условие Armijo, кратко

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

$f(x - \alpha \nabla f) \ \le \ f(x) - c\,\alpha \|\nabla f\|^2, \qquad c \in (0, 1)$

Правая часть — «столько, сколько обещала касательная, умноженное на $c$». Обычно $c = 10^{-4}$, то есть требование очень слабое: получить хотя бы малую долю обещанного. Шаг уменьшают вдвое, пока условие не выполнится, — это и есть backtracking.

Чего градиентный спуск не умеет

Три ограничения, и все проявятся в следующих уроках:

• скорость определяется обусловленностью, а не шагом. Даже при идеально подобранном шаге число итераций пропорционально $\kappa$ (урок 030). На вытянутой чаше метод зигзагует, и никакой $\alpha$ этого не исправит;
• направление наискорейшего спуска не ведёт к минимуму. На втором ландшафте видно: градиент почти перпендикулярен нужному направлению почти всюду. «Наискорейший» — локальное свойство;
• на невыпуклой задаче гарантируется только $\|\nabla f\| \to 0$. Куда именно сойдётся, зависит от старта.

Первое лечится моментом (урок 070) и предобусловливанием (уроки 080, 100), второе — теми же средствами, третье не лечится и принимается как факт.

Полный градиент против стохастического

И последнее, что делает всё сказанное почти неприменимым напрямую. Всё выше предполагает, что $\nabla f$ вычисляется точно, то есть по всей выборке. В обучении это невозможно: один шаг по миллиону примеров стоит столько же, сколько тысяча шагов по тысяче примеров, а полезной информации в нём немногим больше.

Поэтому реальный метод — стохастический, и его свойства другие: он не монотонен, не останавливается в точке, и шум в нём играет двоякую роль. Об этом следующий урок.