Гладкость и сильная выпуклость

Зачем нужны константы

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

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

$$\htmlData{k=lower}{\frac{\mu}{2}\|y - x\|^2} \ \le \ f(y) - f(x) - \nabla f(x)^\top (y-x) \ \le \ \htmlData{k=upper}{\frac{L}{2}\|y - x\|^2}$$

Читается это так: разность между функцией и её линейным приближением зажата между двумя параболами. Для дважды дифференцируемой функции условие эквивалентно спектральному:

$\mu I \ \preceq \ \nabla^2 f \ \preceq \ L I$

то есть все собственные значения гессиана лежат в $[\mu, L]$.

Что каждая константа означает

$L$-гладкость ($\|\nabla f(x) - \nabla f(y)\| \le L\|x-y\|$) — градиент не меняется слишком резко. Это то, что даёт право делать шаги: если кривизна не превосходит $L$, шаг размера $1/L$ гарантированно уменьшает функцию.

Сильная выпуклость с параметром $\mu > 0$ — функция не бывает слишком плоской. Это то, что даёт скорость: чем сильнее выпуклость, тем быстрее сходимость и тем точнее градиент указывает на минимум.

Отношение $\kappa = L/\mu$ — число обусловленности, и следующий урок целиком о нём.

Три оценки сходимости

Всё, что нужно помнить из теории сходимости, — эта таблица.

предположения	шаг	скорость GD
только выпуклость	$1/L$	$O(1/k)$
выпуклость + $L$-гладкость + $\mu$-сильная выпуклость	$2/(L+\mu)$	$O\big(\rho^k\big)$, $\rho = \frac{\kappa - 1}{\kappa + 1}$
невыпуклая + $L$-гладкая	$1/L$	$\|\nabla f\| \to 0$ как $O(1/\sqrt{k})$

Вторая строка — единственная, где сходимость линейная (то есть ошибка убывает геометрически). Она же объясняет, зачем нужна регуляризация с точки зрения оптимизации: добавление $\frac{\lambda}{2}\|x\|^2$ к выпуклой функции делает её $\lambda$-сильно выпуклой, то есть переводит задачу из первой строки во вторую.

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

Стабильность и предел $2/L$

Самое практичное следствие $L$-гладкости — жёсткая граница на шаг. На квадратичной функции с кривизной $L$ градиентный спуск умножает отклонение на $|1 - \alpha L|$ за шаг, откуда:

шаг $\alpha$	что происходит
$\alpha < 1/L$	монотонное убывание
$\alpha = 1/L$	попадание в минимум за один шаг (по этой оси)
$1/L < \alpha < 2/L$	сходится, но с колебаниями
$\alpha = 2/L$	вечные колебания без сходимости
$\alpha > 2/L$	расходимость

Это проверяется точно: при $\alpha = 2/L$ множитель равен $|1 - 2| = 1$, и отклонение не меняется никогда. При $\alpha = 2.1/L$ множитель $1.1$, и за $200$ шагов величина вырастает в $1.1^{200} \approx 2 \cdot 10^{8}$ раз.

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

Что бывает без гладкости

$L$-гладкость — не универсальное свойство. Она нарушается там, где градиент меняется скачком:

x² — гладкая|x| — изломx⁴ — гладкая, но не равномерноx² + 0.1x⁴ — сильно выпуклаяплоское дно — не сильно выпуклая

x

0.8

f(x)

0.64

производная f'(x)

1.6

касательная секущая приближение Тейлора

Второй пример важен практически: ReLU-сети не $L$-гладкие. У них производная скачет на изломах, и формально все оценки сходимости для гладких функций к ним не применимы. Практика от этого не разваливается, но об этом стоит знать, читая теоремы: их условия реальными сетями не выполняются.

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

Как это выглядит в обучении

Практических выводов три, и все проверяемы:

• максимальный шаг определяется максимальной кривизной. Одно узкое направление задаёт порог для всех;
• регуляризация улучшает не только обобщение, но и обусловленность. Прибавив $\frac{\lambda}{2}\|w\|^2$, вы добавляете $\lambda$ ко всем собственным значениям гессиана: $\mu$ растёт с нуля до $\lambda$, и $\kappa$ падает с бесконечности до $(L+\lambda)/\lambda$;
• градиентное клипование — замена гладкости. Если $L$ не существует (или огромна на редких батчах), ограничение нормы градиента возвращает шагу предсказуемый размер. Об этом урок 090.