Выпуклая оптимизация
Выпуклые функции
Хорошая новость: функция потерь логистической регрессии выпуклая. Любой спуск найдёт глобальный минимум. Плохая новость: добавь один скрытый слой - и выпуклость исчезает. GPT-4 обучается в пространстве с триллионами локальных минимумов - и это работает. Jensen's inequality: $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$ для выпуклой $f$. Это неравенство сидит внутри каждого VAE как Evidence Lower Bound, внутри каждого KL-divergence как неотрицательность, внутри каждого importance sampling как коррекция смещения.
- **Линейная регрессия**: MSE-функция потерь выпуклая (Гессиан = $X^TX$ - PSD) - градиентный спуск находит глобальный минимум, решение аналитически через нормальные уравнения
- **L1 vs L2 регуляризация**: геометрически L1 = ромб (с углами), L2 = шар (без углов). Минимум на углу ромба = нулевые координаты = sparse weights. Не магия - выпуклая геометрия
- **Логистическая регрессия**: выпуклая (кросс-энтропия + PSD Гессиан). Нейросеть с двумя слоями - уже нет. Граница проходит через количество слоёв, не через архитектуру
- **Jensen's inequality в ML**: KL-дивергенция $\geq 0$, ELBO в VAE, importance sampling коррекция - всё одно и то же неравенство Йенсена 1906 года
Предварительные знания
Определение выпуклой функции и неравенство Йенсена
Хорошая новость: функция потерь логистической регрессии выпуклая. Любой градиентный спуск найдёт глобальный минимум - не застрянет, не ошибётся, не зациклится. Плохая новость: добавь один скрытый слой - и выпуклость исчезает. GPT-4 обучается в пространстве с триллионами локальных «ям» - и это каким-то образом работает. Разобраться в разнице - значит понять, где оптимизация гарантирована, а где нет.
Формальное определение: функция $f$ называется **выпуклой**, если для любых двух точек $x, y$ из области определения и любого $t \in [0, 1]$: $$f(tx + (1-t)y) \leq t f(x) + (1-t) f(y)$$ Геометрически: хорда между любыми двумя точками графика лежит **выше** (или совпадает с) графиком. Функция выгибается «чашей», а не «куполом».
Неравенство Йенсена (1906)
Йохан Людвиг Йенсен в 1906 году обобщил это наблюдение до случая случайной величины: $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$ для выпуклой $f$. Формула умещается в строку - последствия пронизывают термодинамику, теорию информации и весь современный ML. KL-дивергенция неотрицательна именно из неравенства Йенсена. Evidence Lower Bound в VAE - тоже Йенсен. Importance sampling коррекция - снова он.
Конкретно: $\text{KL}(p \| q) = \mathbb{E}_p[-\log q/p] \geq -\log \mathbb{E}_p[q/p] = 0$ - это применение Йенсена к вогнутой функции $\log$. Каждый раз, когда модель минимизирует кросс-энтропию, она неявно использует тот же принцип.
| Функция | Выпуклая? | Где встречается в ML |
|---|---|---|
| $f(x) = x^2$ | Да | MSE loss, L2-регуляризация |
| $f(x) = e^x$ | Да | Softmax numerator |
| $f(x) = |x|$ | Да | L1-регуляризация (sparse weights) |
| $f(x) = \|x\|_2$ | Да | Ridge regression, weight decay |
| $f(x) = -\log x$ | Да | Кросс-энтропия, negative log-likelihood |
| $f(x) = \log x$ | Нет (вогнутая) | ELBO в VAE (вогнутая - Йенсен даёт нижнюю оценку) |
| $f(x) = \max(x_1, \ldots, x_n)$ | Да | Softmax approximation |
| Нейросеть L>1 слоя | Нет | Поэтому нужны learning rate schedules, momentum |
**Сохранение выпуклости**: сумма выпуклых функций выпуклая. Максимум выпуклых - выпуклый. Неотрицательная взвешенная комбинация - выпуклая. Именно поэтому $\text{MSE} + \lambda \|w\|_2^2$ (Ridge) остаётся выпуклой: обе слагаемые выпуклые.
Функция потерь $L(w) = \frac{1}{n}\sum(y_i - w^T x_i)^2 + \lambda\|w\|_2^2$. Выпуклая ли она по $w$?
Подуровневые множества и геометрия регуляризации
L1 против L2 регуляризации - извечный спор. L2 даёт маленькие веса. L1 даёт нулевые веса. Почему такая разница при почти одинаковых формулах? Ответ - в геометрии подуровневых множеств.
**Подуровневое множество** (sublevel set) функции $f$ при уровне $\alpha$: $S_\alpha = \{x \mid f(x) \leq \alpha\}$. Это всё пространство «под горизонтальным срезом» на высоте $\alpha$.
Теорема: подуровневые множества выпуклой функции выпуклы. Доказательство однострочное: если $f(x) \leq \alpha$ и $f(y) \leq \alpha$, то по определению выпуклости $f(tx + (1-t)y) \leq tf(x) + (1-t)f(y) \leq \alpha$. Точка на отрезке тоже в подуровне.
Теперь про L1 против L2. Подуровневое множество $\|w\|_2 \leq r$ - это шар: гладкий, круглый, без углов. Подуровневое множество $\|w\|_1 \leq r$ - это ромб (в 2D) или октаэдр (в 3D): с острыми углами на осях координат. Минимум функции потерь на ромбе с большой вероятностью попадёт в угол - где координата равна нулю. Не магия. Геометрия.
**L1 порождает спарсность структурно**: при пересечении изолиний функции потерь (эллипсы) с L1-балом (ромб) - пересечение статистически попадает в вершину ромба, где одна или несколько координат равны нулю. L2-бал - круглый, вершин нет, пересечение приходится в обычную точку. Это объясняет, почему LASSO (L1) используют для feature selection.
**Обратное неверно**: функция с выпуклыми подуровнями не обязательно выпуклая сама. Функции с выпуклыми подуровнями называют квазивыпуклыми - более широкий класс, но с меньшими гарантиями оптимизации.
Почему L1-регуляризация (LASSO) порождает sparse решения, а L2 (Ridge) - нет?
Условие первого порядка: нулевой градиент = глобальный минимум
Для дифференцируемой выпуклой функции есть результат, который меняет всё: нулевой градиент гарантирует глобальный минимум. Не локальный. Глобальный. Это не «кажется разумным» - это теорема с точным доказательством.
**Условие первого порядка выпуклости**: $f$ выпуклая тогда и только тогда, когда для всех $x, y$: $$f(y) \geq f(x) + \nabla f(x)^T (y - x)$$ Касательная плоскость в любой точке **недооценивает** функцию. Реальный график всегда выше или на уровне касательной.
Следствие для оптимизации: если $\nabla f(x^*) = 0$, то $f(y) \geq f(x^*) + 0 = f(x^*)$ для всех $y$. Точка с нулевым градиентом - глобальный минимум. Именно так линейная регрессия решается аналитически через $w^* = (X^TX)^{-1}X^Ty$ - берём градиент MSE, приравниваем нулю, решаем.
**Для невыпуклых функций**: нулевой градиент означает только критическую точку - может быть локальный минимум, максимум или седло. По результатам Dauphin et al. (2014) в глубоких нейросетях большинство критических точек - седловые, не локальные минимумы. SGD убегает от сёдел за счёт шума. Это теоретическое обоснование того, почему Adam/SGD работают на невыпуклых задачах.
| Условие | Формула | Геометрия |
|---|---|---|
| 0-й порядок (определение) | $f(tx+(1-t)y) \leq tf(x)+(1-t)f(y)$ | Хорда выше графика |
| 1-й порядок | $f(y) \geq f(x) + \nabla f(x)^T(y-x)$ | Касательная ниже графика |
| Следствие | $\nabla f(x^*) = 0 \Rightarrow x^*$ глобальный минимум | Плоская касательная - дно чаши |
Для выпуклой дифференцируемой $f$: если $\nabla f(x^*) = 0$, то $x^*$ - это:
Условие второго порядка: Гессиан и MSE
Метод Ньютона использует Гессиан - матрицу вторых производных - для ускорения сходимости. Для нейросети с миллиардом параметров Гессиан занимает $10^{18}$ байт. Это в миллион раз больше всего интернета. Поэтому никто не считает полный Гессиан - используют SGD, Adam или методы K-FAC, аппроксимирующие матрицу Фишера (которая и есть Гессиан для вероятностных моделей) через кронекерово произведение. Но понимать, что именно аппроксимируется, важно.
**Условие второго порядка выпуклости**: дважды дифференцируемая $f$ выпукла тогда и только тогда, когда матрица Гессе $\nabla^2 f(x) \succeq 0$ (положительно полуопределённая) для всех $x$. В одном измерении: $f''(x) \geq 0$ - функция «выгибается вверх».
Конкретный пример из ML: функция кросс-энтропии для логистической регрессии выпуклая (Гессиан PSD). Для нейросети с двумя и более слоями - невыпуклая. Буквально добавление одного нелинейного слоя уничтожает выпуклость. Это теоретическое объяснение, почему теория оптимизации для глубокого обучения принципиально отличается от классической.
| Модель | Функция потерь | Гессиан | Выпуклая? |
|---|---|---|---|
| Линейная регрессия | $\|Xw - y\|^2$ | $\frac{2}{n}X^TX$ - PSD | Да (строго при полном ранге) |
| Ridge regression | $\|Xw-y\|^2 + \lambda\|w\|^2$ | $\frac{2}{n}X^TX + 2\lambda I$ - PD | Да, строго |
| Логистическая регрессия | $-\log p(y|X,w)$ | $X^T \text{diag}(p(1-p)) X$ - PSD | Да |
| Нейросеть L=1 | cross-entropy | PSD (то же, что logistic) | Да |
| Нейросеть L>=2 | cross-entropy | Не PSD (отрицательные собственные значения) | Нет |
**Метод Ньютона vs SGD**: Ньютон использует $w \leftarrow w - [\nabla^2 f]^{-1} \nabla f$ и сходится за $O(\log\log(1/\varepsilon))$ итераций для выпуклых задач. SGD требует $O(1/\varepsilon)$ итераций. Но для $d$ параметров: Ньютон $O(d^3)$ за шаг, SGD $O(d)$. При $d = 10^9$ (GPT-4) - Ньютон физически невозможен. K-FAC аппроксимирует Гессиан через матрицу Фишера в Кронекеровской структуре - компромисс.
Любая квадратичная функция выпуклая
$f(x, y) = x^2 - y^2$ - квадратичная, но невыпуклая: Гессиан $\text{diag}(2, -2)$ имеет отрицательное собственное значение.
Выпуклость квадратичной $f(x) = x^TAx + b^Tx + c$ определяется знаком матрицы $A$: только при $A \succeq 0$ функция выпуклая. Гиперболический параболоид $x^2 - y^2$ - классическое седло, невыпуклая функция.
Гессиан функции $f(w) = \|Xw - y\|^2 / n$ равен $\frac{2}{n}X^TX$. При каком условии функция строго выпуклая?
Ключевые идеи
- **Выпуклая функция**: хорда между точками выше графика (неравенство Йенсена). MSE, кросс-энтропия, L1/L2 нормы - выпуклые
- **L1 vs L2**: форма единичного шара (ромб vs круг) определяет sparse vs dense решения при регуляризации
- **Условие 1-го порядка**: касательная недооценивает функцию. Следствие: нулевой градиент = глобальный минимум для выпуклых
- **Условие 2-го порядка**: Гессиан PSD $\Leftrightarrow$ выпуклость. Логистическая регрессия: PSD. Нейросеть L$\geq$2: нет
- **Jensen's inequality**: $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$ - это KL $\geq 0$, ELBO в VAE, и причина по которой log вогнутая, а не выпуклая
Связанные темы
Выпуклые функции - ядро оптимизации:
- Выпуклые множества — Подуровни и эпиграф связывают выпуклые функции с выпуклыми множествами
- Задача выпуклой оптимизации — Целевая функция и ограничения - выпуклые функции
- Градиент — Условие 1-го порядка использует градиент; нулевой градиент = глобальный минимум
- Линейная регрессия — MSE выпуклая - поэтому МНК имеет аналитическое решение и gradient descent сходится
Вопросы для размышления
- Логистическая регрессия выпуклая. Нейросеть с одним скрытым слоем - нет. Что именно ломает выпуклость при добавлении нелинейности?
- Jensen's inequality: $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$. Докажите, что $\text{KL}(p \| q) \geq 0$ используя это неравенство для $f(t) = -\log t$.
- L1-регуляризация даёт sparse решения. При каком условии на геометрию задачи оптимума она НЕ даст sparse решение (оба веса ненулевые)?
Связанные уроки
- cvx-01 — Выпуклость функций строится поверх теории выпуклых множеств
- cvx-03 — Выпуклые функции - сердце формальной задачи оптимизации
- calc-19-gradient — Условие 1-го порядка использует градиент
- calc-20-extrema-multi — Гессиан и условие 2-го порядка для выпуклости
- stat-09-regression — MSE - выпуклая функция, поэтому линейная регрессия всегда сходится
- la-02-dot-product — PSD-гессиан проверяется через скалярное произведение
- calc-06-derivative-intro