Крупномасштабная оптимизация: от кластера к суперкомпьютеру

GPT-4 обучался на тысячах GPU через AllReduce SGD. LibSVM (100M+ downloads) использует SMO - покоординатный спуск. scikit-learn LASSO внутри - CD. PyTorch L-BFGS - для физических симуляций. Выбор алгоритма определяет, сколько часов или дней займёт обучение.

• AllReduce SGD (PyTorch DDP, Horovod): распределённое обучение на кластере GPU
• FedAvg в Google Keyboard: миллионы Android-устройств без передачи данных
• LibSVM, scikit-learn: SMO и CD как внутренние солверы для SVM и LASSO
• L-BFGS в физических симуляциях: молекулярная динамика, оптика

Распределённая оптимизация и федеративное обучение

Adam optimizer (Kingma 2014, 100 000+ цитирований) - стандартный для обучения GPT-4: β₁=0.9, β₂=0.999, ε=10⁻⁸. **Распределённая оптимизация** разбивает задачу min f(x) = 1/N ∑ᵢ fᵢ(x) по узлам кластера. **Федеративное обучение (FedAvg)** - специальный случай: данные не покидают устройства (смартфоны), а сервер усредняет обновлённые модели. Ключевые проблемы: задержки коммуникации, heterogeneous data, privacy.

**Federated Learning в продакшне:** Google использует FedAvg для обучения клавиатурного автодополнения на 500M+ Android-устройств. Apple применяет FL для Siri на iOS. Главные проблемы: 1. client drift при non-IID данных 2. коммуникационная эффективность (quantization, sparsification) 3. privacy (differential privacy + secure aggregation).

Методы второго порядка: L-BFGS и масштабируемый Ньютон

**Метод Ньютона** использует Гессиан: x_{k+1} = x_k − H⁻¹∇f(x_k). Имеет квадратичную сходимость вблизи минимума, но требует O(d²) памяти и O(d³) для обращения Гессиана. **L-BFGS** аппроксимирует H⁻¹ через последние m пар (Δx, Δg), требует O(md) памяти. Стандартный алгоритм для выпуклых задач средней размерности.

**L-BFGS в продакшне:** PyTorch включает torch.optim.LBFGS (но не рекомендуется для DL из-за несовместимости с мини-батчами). Для выпуклых задач (логистическая регрессия, SVM, GP) L-BFGS в scikit-learn - стандарт. Стохастический L-BFGS (oLBFGS) и online Hessian estimation - активные направления исследований для DL.

Покоординатный спуск: параллелизм без общей памяти

**Покоординатный спуск (CD)** минимизирует по одной переменной за раз, держа остальные фиксированными. При сепарабельной структуре f часто имеет аналитическое обновление координаты. **Hogwild!** (Niu et al., 2011) - параллельный CD без блокировок: потоки пишут одновременно, и при разреженных данных это работает!

**Когда выбирать CD vs SGD vs L-BFGS:** 1. Разреженные данные, LASSO/SVM - CD (SMO). 2. Большие нейросети, мини-батчи - SGD/Adam. 3. Средние выпуклые задачи (d ≤ 10⁶), точное решение - L-BFGS. 4. Нет градиентов, дорогая функция, d ≤ 20 - BayesOpt. Выбор алгоритма - такая же задача оптимизации!

Ключевые идеи

• FedAvg: локальные шаги SGD + усреднение; client drift при non-IID данных → FedProx, SCAFFOLD
• Метод Ньютона: квадратичная сходимость, O(d³) стоимость; практически невозможен при d > 10⁴
• L-BFGS: суперлинейная сходимость, O(md) память; стандарт для выпуклых задач d ≤ 10⁶
• Покоординатный спуск: аналитические обновления для LASSO (мягкий порог), SVM (SMO)
• Hogwild!: параллельный CD без блокировок корректен при разреженных данных

Связанные темы

Крупномасштабная оптимизация объединяет все методы курса.

• Проксимальные методы — CD для LASSO = проксимальный шаг по каждой координате; ADMM масштабируется на кластер
• Стохастическая оптимизация — AllReduce SGD - распределённый мини-батч SGD; variance reduction в FedAvg
• Байесовская оптимизация — BayesOpt выбирает гиперпараметры для всех методов этого урока

Вопросы для размышления

• Почему standard FedAvg расходится при сильной гетерогенности данных? Как FedProx (добавление проксимального члена) решает эту проблему математически?
• При каком условии покоординатный спуск быстрее SGD? Постройте конкретный пример с разреженной матрицей A.
• В чём отличие distributed SGD (AllReduce) от federated learning на практике? Почему Google не может использовать AllReduce для обучения клавиатуры?

Связанные уроки

• alg-05-merge-sort