Выпуклая оптимизация
Теоретические гарантии сходимости
Почему мы доверяем, что нейросеть обучилась? Почему Nesterov быстрее GD - и это не эмпирика, а математический факт? Зачем Google использует Adagrad, а не SGD? Теория сходимости - это не скучная математика, это **гарантии надёжности** и **дорожная карта** для создания более быстрых алгоритмов.
- **TensorFlow и PyTorch**: выбор оптимизатора (Adam, SGD, Adagrad) - это прикладная теория сходимости; Adam обоснован как приближённый натуральный градиент с адаптивным κ для каждого параметра
- **Обучение LLM**: GPT-4 тренируется с cosine lr schedule - это не эмпирика, а следствие теории: убывающий lr необходим для сходимости SGD; cosine аппроксимирует оптимальное убывание 1/k
- **Сертификация ML систем**: в автономных автомобилях и медицинских системах нужны гарантии - теоремы сходимости дают математически строгие утверждения о поведении алгоритмов
Скорости сходимости: GD, Nesterov и strongly convex
На L-гладких выпуклых задачах градиентный спуск даёт зазор O(1/k); ускоренный метод Нестерова 1983 года - O(1/k²). При обучении модели на 175 миллиардов параметров эта квадратичная разница превращает 1 эпоху в 1000. Теория выпуклой оптимизации классифицирует алгоритмы по **скорости сходимости** - как быстро убывает зазор f(xₖ) - f*. Скорость зависит от класса функций: выпуклая, сильно выпуклая, гладкая (L-Lipschitz gradient) или нет. Понимание этих классов объясняет, почему Nesterov быстрее GD и почему Adam работает лучше SGD на практике.
Важно понимать разницу между **сублинейной** O(1/k) и O(1/k²) сходимостью и **линейной** e^{-αk} сходимостью. Линейная означает, что точность удваивается за фиксированное число итераций - это экспоненциально быстро в реальном времени. Для сильно выпуклых функций оба метода (GD и Nesterov) дают линейную сходимость, но с разными константами: κ vs √κ.
Условие Поляка-Лоясевича (PL): ½‖∇f(x)‖² ≥ μ(f(x) - f*). Это слабее сильной выпуклости, но достаточно для линейной сходимости GD! Функция может быть невыпуклой, но удовлетворять PL - например, softmax cross-entropy при достаточной ширине сети. Это объясняет, почему GD на overparameterized нейросетях сходится линейно, хотя задача невыпукла.
Почему для сильно выпуклых функций метод Нестерова даёт √κ-кратное ускорение над GD, а не κ-кратное?
Нижние оценки сложности: теорема Немировского-Юдина
Знание скоростей сходимости конкретных алгоритмов - это верхние оценки. Но насколько хорош **лучший возможный алгоритм** первого порядка? **Нижние оценки сложности** отвечают на этот вопрос: ни один метод первого порядка не может сходиться быстрее определённой границы на наихудшем примере.
Нижние оценки Немировского-Юдина применяются к **black-box** методам первого порядка - алгоритмам, знающим только f(x) и ∇f(x) в точках запроса. Если задача имеет **дополнительную структуру** (разреженность, сепарабельность, специальный граф), то существуют методы быстрее нижней оценки. Например: покоординатный спуск для сепарабельных задач, ADMM для структурных задач. Нижние оценки - это ограничения для «слепых» методов, а не для всех алгоритмов.
Почему обычный GD (скорость O(1/k)) не является оптимальным для выпуклых задач?
Сходимость SGD: выпуклый и сильно выпуклый случаи
В машинном обучении мы используем **стохастический градиентный спуск (SGD)** вместо полного градиента. Это вносит дисперсию: gₜ = ∇fᵢₜ(xₜ) - несмещённая, но шумная оценка ∇f(xₜ). Теория SGD анализирует, как этот шум влияет на скорость сходимости и что можно сделать.
Парадоксально: в ML стохастический шум SGD часто **помогает**, а не только мешает. Шум работает как имплицитная регуляризация: SGD избегает острых локальных минимумов с плохой обобщающей способностью и предпочитает пологие (flat minima). Эмпирически: модели, обученные SGD, обобщаются лучше, чем обученные полным GD с той же точностью на обучающей выборке. Это «шум как регуляризатор» - область активных исследований.
SGD для сильно выпуклых задач сходится со скоростью O(1/k), а детерминированный GD - линейно (e^{-k/κ}). Почему не можем использовать SGD с уменьшением дисперсии (SVRG) вместо GD?
Теория ускорения: momentum, Catalyst и оптимальность
Метод Нестерова (1983) - загадочный: зачем «переосмыслить» точку обновления? Почему это работает? Три интерпретации: momentum (инерция), полиномиальная аппроксимация, и геометрическая (estimate sequence). Современная теория даёт unified framework, объясняющий ускорение через lower bound matching.
Catalyst показывает, что **ускорение - это внешняя оболочка**, применимая к любому алгоритму. Это похоже на то, как Adam - не новый алгоритм, а SGD с адаптивным масштабированием. Современное понимание: ускорение Нестерова - оптимальный способ «накапливать» информацию о градиентах в black-box методах первого порядка. Нижние оценки Немировского-Юдина + верхние оценки Нестерова = полная картина оптимальности.
Catalyst framework ускоряет SVRG с O(n + nκ) до O(n + √(nκ)·log(1/ε)). Как это возможно, если нижняя оценка для методов первого порядка уже достигнута Нестеровым?
Ключевые идеи
- **Скорости сходимости**: GD = O(1/k) для выпуклых, O(e^{-k/κ}) для strongly convex; Нестеров = O(1/k²) и O(e^{-k/√κ}) - оптимальны
- **Нижние оценки Немировского-Юдина**: Ω(1/k²) для выпуклых, Ω(e^{-k/√κ}) для strongly convex - ни один black-box метод первого порядка не быстрее
- **Сходимость SGD**: O(1/√k) для выпуклых, O(1/k) для strongly convex; Variance Reduction (SVRG, SAGA) восстанавливает линейную скорость
- **Catalyst**: универсальный framework ускорения любого метода первого порядка до оптимальной сложности finite-sum задач
Связанные темы
Теория сходимости - фундамент всего курса выпуклой оптимизации:
- Оптимизация на многообразиях — Riemannian GD сходится со скоростью O(1/k) для геодезически выпуклых функций - риманов аналог теорем сходимости
- Оптимизация в задачах RL — TRPO и PPO имеют гарантии монотонного улучшения политики - теоретические следствия trust region и surrogate objective
- Федеративная оптимизация — Теоремы сходимости FedAvg и FedProx - прямые следствия теории SGD с гетерогенными функциями потерь
Вопросы для размышления
- Почему нижние оценки Немировского-Юдина применяются только к black-box методам, и как структурные знания о задаче помогают их обойти?
- Если метод Нестерова оптимален, почему на практике Adam обгоняет его для обучения нейросетей?
- Может ли рандомизация алгоритма принципиально изменить нижние оценки сложности, или они одинаковы для детерминированных и рандомизированных методов?