Оптимизация
Нелинейная оптимизация
Обучение GPT требует миллионов итераций Adam, а задачу физической симуляции решает L-BFGS за десятки итераций. Выбор оптимизатора - не деталь, а архитектурное решение. Понимание методов второго порядка объясняет, почему Adam нельзя заменить Newton и наоборот.
- **scipy.optimize.minimize:** стандарт для научных вычислений; L-BFGS-B решает задачи с тысячами параметров за секунды
- **PyTorch LBFGS:** используется для физических симуляций (PINN), style transfer, fine-tuning малых моделей на малых датасетах
- **Второй порядок в Google:** Google использует методы на основе K-FAC (Kronecker-Factored Approximate Curvature) для обучения трансформеров - аппроксимация Гессе через факторизацию
Предварительные знания
Градиентный спуск и line search
Градиентный спуск: xₖ₊₁ = xₖ - αₖ ∇f(xₖ). Ключевой вопрос - выбор размера шага αₖ. Слишком маленький шаг - медленная сходимость. Слишком большой - расходимость. **Line search** решает эту проблему: ищет αₖ, удовлетворяющий условиям Вольфа (достаточное убывание + кривизна).
**Условия Вольфа** (Wolfe conditions) - стандарт для line search: 1. Armijo: достаточное убывание f 2. curvature: шаг не слишком маленький (градиент ещё «тянет» вниз). Вместе они гарантируют сходимость градиентного спуска к локальному оптимуму.
| Стратегия шага | Плюсы | Минусы |
|---|---|---|
| Фиксированный α | Просто | Нужно тюнить; может расходиться |
| Backtracking (Armijo) | Простая реализация | Только условие убывания |
| Wolfe conditions | Гарантия сходимости | Дороже - 2 условия, line search |
| Exact line search | Оптимальный шаг | Дорогой; обычно не нужен |
Почему backtracking line search предпочтительнее фиксированного размера шага в градиентном спуске?
Метод Ньютона
Метод Ньютона использует не только градиент, но и **кривизну** (Гессе): xₖ₊₁ = xₖ - [∇²f(xₖ)]⁻¹ ∇f(xₖ). Геометрически - квадратичное приближение функции и прыжок к его минимуму. Результат - **квадратичная сходимость**: ||xₖ₊₁ - x*|| ≤ C · ||xₖ - x*||².
**Проблема метода Ньютона:** вычисление и хранение Гессе ∇²f - O(n²) памяти и O(n³) времени на инверсию. Для нейросети с 10⁸ параметров это физически невозможно. Решение: квази-Ньютоновские методы (BFGS, L-BFGS), аппроксимирующие Гессе без явного вычисления.
Метод Ньютона имеет квадратичную сходимость, но редко используется для обучения нейросетей. Почему?
BFGS и квази-Ньютон
**BFGS** (Broyden-Fletcher-Goldfarb-Shanno, 1970) аппроксимирует обратный Гессе Hₖ ≈ [∇²f(xₖ)]⁻¹ используя только градиенты. Обновление - rank-2: Hₖ₊₁ = Hₖ + (ранговые поправки из sₖ и yₖ), где sₖ = xₖ₊₁-xₖ, yₖ = ∇f(xₖ₊₁)-∇f(xₖ).
**BFGS rank-2 update:** Hₖ₊₁ = (I - ρₖsₖyₖᵀ)Hₖ(I - ρₖyₖsₖᵀ) + ρₖsₖsₖᵀ, где ρₖ = 1/(yₖᵀsₖ). Обновление требует O(n²) операций (умножение векторов), а не O(n³) для инверсии Гессе. При этом Hₖ автоматически остаётся положительно определённой при выполнении Wolfe conditions.
Чем BFGS принципиально отличается от метода Ньютона?
L-BFGS: ограниченная память
**L-BFGS** (Limited-memory BFGS) - версия для больших n. Вместо хранения матрицы Hₖ ∈ ℝⁿˣⁿ (O(n²) памяти) хранит только последние m пар (sₖ, yₖ) - векторов. Обновление через двухпетлевую рекурсию O(mn) вместо O(n²).
| Метод | Сходимость | Память | Когда использовать |
|---|---|---|---|
| GD | Линейная O(1/k) | O(n) | Простые выпуклые задачи, warm-up |
| BFGS | Суперлинейная | O(n²) | n < 10⁴, нелинейные задачи |
| L-BFGS | Суперлинейная | O(mn) | n до 10⁶, fine-tuning ML моделей |
| Newton | Квадратичная | O(n²) | n < 10³, математическая оптимизация |
| Adam/SGD | Линейная/субл. | O(n) | n > 10⁶, нейросети (non-convex) |
**Fine-tuning LLM через L-BFGS:** для небольших LLM (BERT-base, GPT-2) L-BFGS с gradient checkpointing может быть быстрее Adam на некоторых задачах fine-tuning, особенно при малых датасетах. Но требует полных батчей - несовместим со стохастическим шумом.
Для нейросетей L-BFGS лучше Adam, потому что использует кривизну
Adam лучше для нейросетей на практике из-за совместимости с SGD (малые батчи). L-BFGS требует точных градиентов (полные батчи), что непрактично для больших датасетов.
L-BFGS аппроксимирует Гессе на основе накопленной истории градиентов. Стохастические градиенты (mini-batch SGD) слишком шумные - аппроксимация Гессе деградирует. Adam адаптирует масштаб шага покоординатно через моменты, что работает с шумными градиентами. Поэтому Adam доминирует в deep learning, а L-BFGS - в физической симуляции, численной оптимизации, fine-tuning на малых данных.
Почему L-BFGS хранит только m пар (s, y) вместо полной матрицы Гессе?
Ключевые идеи
- **Line search** адаптирует размер шага: backtracking (Armijo) - быстро и просто; Wolfe - гарантия сходимости
- **Метод Ньютона** использует Гессе для квадратичной сходимости, но O(n²) память и O(n³) время делают его неприменимым для больших n
- **BFGS** аппроксимирует обратный Гессе через rank-2 обновление O(n²); суперлинейная сходимость
- **L-BFGS** хранит только m пар (s, y); O(mn) память; стандарт для нелинейных задач с n до 10⁶
Связанные темы
Методы второго порядка дополняют SGD для разных режимов:
- Стохастическая оптимизация — SGD и Adam - стохастические аналоги GD; L-BFGS несовместим с mini-batch SGD
- Ограниченная оптимизация — L-BFGS-B добавляет box constraints; KKT - условия для общих ограничений
- IPM — IPM использует шаги Ньютона внутри; shared математика - инверсия Гессе барьерной функции
Вопросы для размышления
- Почему квадратичная сходимость метода Ньютона не делает его лучшим выбором для обучения нейросетей? Какие практические ограничения важнее теоретической скорости?
- L-BFGS хранит только последние m обновлений Гессе. Как это влияет на качество аппроксимации? Какой m выбрать на практике?
- Какой метод оптимален для каждой задачи: (а) логистическая регрессия на 10⁶ примерах, (б) физическая симуляция с 1000 параметров, (в) обучение GPT-2?