Оптимизация
Выпуклая оптимизация: основы
Почему машинное обучение работает надёжно для логистической регрессии и SVM, но не всегда для нейросетей? Ответ - выпуклость. Когда задача выпуклая, любой алгоритм гарантированно находит глобальный оптимум. Понимание выпуклости объясняет, когда ваша модель точно сойдётся, а когда - только надеяться.
- **Портфельная оптимизация:** задача Марковица (mean-variance portfolio) - классическая выпуклая QP; CVXPY решает её за миллисекунды
- **SVM обучение:** dual-задача SVM - выпуклая QP с гарантией глобального оптимума; поэтому SVM не нужен multi-start
- **Lasso/Ridge регрессия:** выпуклые функции потерь с регуляризацией дают единственный воспроизводимый результат независимо от инициализации
Предварительные знания
Выпуклые множества
Множество C называется **выпуклым**, если отрезок между любыми двумя его точками целиком лежит внутри: для любых x, y ∈ C и θ ∈ [0,1] выполняется θx + (1-θ)y ∈ C. Геометрически - множество «без вмятин и выступов».
**Ключевое свойство:** пересечение любого числа выпуклых множеств - выпуклое множество. Это объясняет, почему допустимая область LP (пересечение полупространств) всегда выпукла, и минимум линейной функции на ней - в вершине.
В ML выпуклые множества встречаются повсюду: вероятностный симплекс (распределения вероятностей), множество положительно полуопределённых матриц (ковариационные матрицы), L2-шар (weight decay в регуляризации).
Какое из следующих множеств НЕ является выпуклым?
Выпуклые функции
Функция f: ℝⁿ → ℝ **выпукла**, если её эпиграф (множество точек выше графика) - выпуклое множество. Эквивалентно: для любых x, y и θ ∈ [0,1] выполняется f(θx + (1-θ)y) ≤ θf(x) + (1-θ)f(y). Хорда между двумя точками лежит не ниже графика.
| Функция | Тип | Применение в ML |
|---|---|---|
| MSE: ||Ax-b||² | Выпуклая (строго) | Линейная регрессия |
| Log loss: -Σyᵢlog(pᵢ) | Выпуклая (для линейного классификатора) | Логистическая регрессия |
| Hinge loss: max(0, 1-yᵢxᵢ) | Выпуклая (кусочно-линейная) | SVM |
| Cross-entropy + нейросеть | Невыпуклая | Deep learning (много локальных минимумов) |
| L1 регуляризация: ||w||₁ | Выпуклая (не дифференцируема в 0) | Lasso (sparse solutions) |
**Правила сохранения выпуклости:** 1. неотрицательная сумма выпуклых функций выпукла 2. max выпуклых функций выпукла 3. аффинная подстановка f(Ax+b) сохраняет выпуклость. Это позволяет строить сложные выпуклые функции из простых.
Функция потерь логистической регрессии L(w) = Σlog(1+exp(-yᵢwᵀxᵢ)) - выпуклая или нет?
Локальный = Глобальный минимум
Главная теорема выпуклой оптимизации: **любой локальный минимум выпуклой функции на выпуклом множестве является глобальным**. Это радикально упрощает оптимизацию: не нужно бояться «застрять» в плохом локальном минимуме - любое место, где градиент равен нулю, уже является решением.
**Условие первого порядка:** для дифференцируемой выпуклой f точка x* - глобальный минимум тогда и только тогда, когда ∇f(x*) = 0. Для ограниченной задачи (min f(x) s.t. x ∈ C) условие: ∇f(x*)ᵀ(y-x*) ≥ 0 для всех y ∈ C (градиент «указывает» из допустимой области).
Именно это свойство делает выпуклую оптимизацию «решённой проблемой»: градиентный спуск, метод Ньютона, interior point - все эти методы сходятся к глобальному оптимуму для выпуклых задач. Для нейросетей нет такой гарантии - отсюда и важность правильной инициализации.
Алгоритм градиентного спуска остановился в точке x* с ∇f(x*) = 0. f - выпуклая. Что можно утверждать?
Условия второго порядка и CVXPY
Матрица Гессе ∇²f(x) - инструмент проверки выпуклости. f выпукла тогда и только тогда, когда ∇²f(x) ≽ 0 (положительно полуопределённа) для всех x в области определения. Строгая выпуклость - при ∇²f(x) ≻ 0. Для нелинейных функций это проверяется аналитически или через собственные числа.
| Тип задачи | Условие на Гессе | Примеры в ML |
|---|---|---|
| LP | ∇²f = 0 (линейная) | Линейный SVM, LP-relaxation |
| QP (выпуклая) | ∇²f ≽ 0, квадратичная | Linreg (MSE), L2-SVM |
| SOCP | Second-order cone | Robust regression, Portfolio |
| SDP | Матричные constraints | Matrix completion, SDP-relaxation ILP |
**Ограничение CVXPY:** задача должна быть выпуклой и записана через DCP-правила (Disciplined Convex Programming). Если попытаться записать невыпуклую задачу (например, перемножить две переменные), CVXPY выдаст ошибку. Это помогает избежать случайной ошибки формулировки.
Нейросети обучаются с помощью выпуклой оптимизации
Обучение нейросетей - невыпуклая задача из-за произведений матриц весов. SGD работает, но без гарантий глобальной оптимальности.
Loss function нейросети невыпукла по весам (W₁, W₂): f(W₁,W₂)=||W₂W₁x-y||². Выпуклость - это свойство функции, не алгоритма. SGD находит «хорошие» локальные минимумы благодаря шуму, batch normalization и правильной инициализации, но не гарантирует глобальный оптимум.
Матрица Гессе f(x) = xᵀQx имеет собственные числа [-1, 3, 5]. Выпукла ли f?
Ключевые идеи
- **Выпуклое множество:** отрезок между любыми двумя точками - внутри; пересечение выпуклых - выпукло
- **Выпуклая функция:** хорда не ниже графика; ∇²f ≽ 0 - критерий второго порядка
- **Локальный = глобальный:** для выпуклой f на выпуклом C любой локальный минимум глобален; ∇f(x*)=0 ↔ оптимум
- **CVXPY + DCP:** автоматическая проверка выпуклости и выбор solver; стандарт для выпуклой оптимизации в Python
Связанные темы
Выпуклость - фундамент для методов решения:
- Метод внутренней точки — Эффективно решает выпуклые задачи (QP, SOCP) с полиномиальной гарантией
- KKT условия — Условия оптимальности для ограниченных выпуклых задач обобщают ∇f=0
- Стохастическая оптимизация — SGD гарантирует сходимость к глобальному оптимуму только для выпуклых функций
Вопросы для размышления
- Почему выпуклость loss function так важна для надёжности ML-моделей? Что происходит при обучении, когда функция потерь невыпукла?
- Lasso и Ridge регрессия используют разные регуляризаторы (L1 и L2). Обе ли они выпуклы? Почему Lasso даёт sparse решения, а Ridge - нет?
- CVXPY автоматически проверяет, является ли задача выпуклой. Почему это важная фича, а не просто удобство?