Условия оптимальности

Необходимое и достаточное

$$\htmlData{k=first}{\nabla f(x^*) = 0} \qquad \text{и} \qquad \htmlData{k=second}{\nabla^2 f(x^*) \succ 0}$$

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

Второе — достаточное вместе с первым: если градиент нулевой, а гессиан положительно определён, точка — строгий локальный минимум. Между ними есть щель: при $\nabla^2 f \succeq 0$ с нулевым собственным значением решить нельзя ничем, кроме анализа более высоких порядков (пример — $x^4$ и $x^3$ в нуле: у обеих $f'' = 0$, у первой минимум, у второй нет).

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

вид	спектр гессиана
локальный минимум	все $\lambda_i > 0$
локальный максимум	все $\lambda_i < 0$
седловая точка	есть и положительные, и отрицательные
вырожденная	есть $\lambda_i = 0$

Седла на картинке

Потащите точку к началу координат на седле: градиент обращается в нуль, а точка минимумом не является — вдоль одной оси функция растёт, вдоль другой падает.

чаша x² + y²седло x² − y²вырожденное x²обезьянье седло

f(x, y)

2.25

градиент

2.4, 1.8

норма градиента

3

Почему седла — правило

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

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

$P(\text{локальный минимум}) = P(\text{все } \lambda_i > 0) = 2^{-d}$

$d$	вероятность минимума
$2$	$1/4$
$10$	$1/1024$
$100$	$10^{-30}$
$10^9$	неотличима от нуля

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

Практические следствия три:

• бояться локальных минимумов не нужно. Их почти нет; те, что есть, обычно дают сравнимый лосс;
• седла замедляют, а не останавливают. Из седла есть направление спуска, но около него градиент мал, и метод «залипает» на много шагов. Именно с этим борется момент;
• условия второго порядка бесполезны на практике. Гессиан размера $10^9 \times 10^9$ не то что не диагонализуется — он не существует в памяти. Проверить оптимальность в глубоком обучении невозможно, и никто не проверяет.

Что делают вместо проверки

Раз условие второго порядка недоступно, останавливаются по эвристикам:

критерий	что означает
норма градиента мала	приблизились к критической точке — любой
лосс не падает $N$ шагов	плато, седло, или слишком малый шаг
валидационный лосс растёт	пора остановиться независимо от оптимальности

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

Ограничения меняют условие

Всё сказанное относится к минимуму внутри области. На границе градиент нулевым быть не обязан: минимум $x^2$ на отрезке $[1, 2]$ достигается в $x = 1$, где $f' = 2 \ne 0$.

Правильное условие для задач с ограничениями — это условия ККТ, и им посвящён урок 110. Пока достаточно запомнить: «градиент равен нулю» — условие для внутренней точки, и при активных ограничениях оно просто неверно.