Выпуклость

Определение и что оно даёт

$$\htmlData{k=graph}{f\big(\lambda x + (1-\lambda) y\big)} \ \le \ \htmlData{k=chord}{\lambda f(x) + (1-\lambda) f(y)} \qquad \forall \lambda \in [0,1]$$

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

У выпуклой функции всякий локальный минимум является глобальным.

Доказательство в одну строку: если бы существовала точка $y$ с $f(y) < f(x)$ при локально минимальном $x$, то на отрезке от $x$ к $y$ значения были бы не больше хорды, то есть уже вблизи $x$ нашлись бы точки со значением меньше $f(x)$ — противоречие с локальной минимальностью.

Отсюда всё остальное: любой метод, который умеет останавливаться в точке с нулевым градиентом, на выпуклой задаче находит ответ, а не «какой-то ответ». Ни инициализация, ни путь не важны.

Как проверять

Три критерия, от самого общего к самому удобному:

критерий	условие	когда применим
по определению	хорда над графиком	всегда
первого порядка	$f(y) \ge f(x) + \nabla f(x)^\top (y - x)$	$f$ дифференцируема
второго порядка	$\nabla^2 f \succeq 0$	$f$ дважды дифференцируема

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

Третий — самый практичный: матрица Гессе положительно полуопределена, то есть все её собственные значения неотрицательны. Это ровно то условие из урока про собственные значения (блок 1, урок 070), и здесь оно наконец получает применение.

Посмотрите на кривые: у выпуклых секущая всегда над графиком, у остальных — не всегда.

x²eˣ|x|x⁴ − 3x² + xσ(x)

x

0.8

f(x)

0.64

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

1.6

показать касательную показать секущую

Второй пример стоит отметить отдельно: $e^x$ выпукла, а минимума у неё нет. Выпуклость даёт «локальный ⟹ глобальный», но не обещает, что минимум существует. Для этого нужна дополнительно коэрцитивность (рост на бесконечности) или компактность области.

Операции, сохраняющие выпуклость

Это то, что позволяет проверять выпуклость реальных задач, не считая гессианы:

• сумма выпуклых выпукла (отсюда: лосс плюс L2-регуляризатор выпуклы, если лосс выпуклый);
• максимум выпуклых выпукл (отсюда: hinge loss, ReLU, $\|x\|_\infty$);
• композиция с линейным: $f(Ax + b)$ выпукла, если $f$ выпукла (отсюда: почти любой лосс от линейной модели);
• неотрицательная комбинация выпуклых выпукла.

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

Что выпукло в машинном обучении

Список короткий, и его полезно знать точно:

задача	выпукла?
линейная регрессия с MSE	да
ridge, lasso	да
логистическая регрессия	да
SVM с hinge loss	да
softmax-регрессия	да
MSE с сигмоидой на выходе	нет
любая сеть с ≥ 1 скрытым слоем	нет
матричная факторизация	нет

Шестая строка — полезная деталь. Один и тот же классификатор с сигмоидой даёт выпуклую задачу с кросс-энтропией и невыпуклую с MSE. Это ещё один аргумент в пользу кросс-энтропии, независимый от того, что был в блоке 3: она не только выведена из правдоподобия, но и сохраняет выпуклость.

Почему невыпуклость не катастрофа

Естественный вывод «значит, глубокое обучение обречено» — неверен, и стоит понимать, почему.

• локальные минимумы в высокой размерности редки. Чтобы точка с нулевым градиентом была локальным минимумом, все $d$ собственных значений гессиана должны быть положительны. При случайном спектре вероятность этого падает экспоненциально с $d$, и почти все критические точки оказываются седловыми;
• плохие минимумы редко хуже хороших. Эмпирически (и с теоретическими подтверждениями для широких сетей) большинство найденных минимумов дают близкое значение лосса;
• настоящая трудность не в невыпуклости, а в обусловленности. Этому посвящён урок 050, и он объясняет большую часть практических неудач обучения.

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