Выпуклая оптимизация
Распределённая оптимизация
Как обучать модель на тысячах машин одновременно, если каждая видит лишь часть данных - и при этом получить то же решение, что и при обучении на одной машине?
- Google PaLM: обучение 540 млрд параметров на 6144 TPU через консенсусный протокол - глобальная синхронизация каждые 100 шагов через AllReduce
- Federated Learning: Google Keyboard обучается на 500 млн телефонов без передачи личных данных - каждое устройство решает локальную задачу, сервер усредняет веса
- Энергосети Smart Grid: балансировка нагрузки 10 000 узлов через децентрализованный ADMM - оптимальная мощность без центрального диспетчера
- Финансы: 300 банков совместно обучают антифрод-модель через консенсусную оптимизацию без раскрытия транзакций конкурентам
Предварительные знания
- Выпуклые функции и субградиенты
- Метод множителей Лагранжа
- Градиентный спуск
ADMM: альтернирующий метод направлений
ADMM (Alternating Direction Method of Multipliers, Glowinski-Marrocco 1975, Gabay-Mercier 1976) - универсальный метод решения задач выпуклой оптимизации с разделяемой структурой. Сочетает декомпозицию по координатам с превосходными сходящимися свойствами методов множителей. В 2010-х получил массовое применение в обучении больших моделей: PaLM от Google обучался на 6144 TPU через консенсусный ADMM с глобальной синхронизацией каждые 100 шагов.
Критерий остановки ADMM требует обоих условий: прямая невязка ||Ax + Bz - c|| < eps_prim AND двойственная rho*||A^T(z^{k+1} - z^k)|| < eps_dual. Boyd et al. рекомендуют адаптивные допуски с абсолютным и относительным компонентами.
Выбор параметра rho в ADMM критичен: типичные значения от 0.1 до 10. Адаптивное правило: если прямая невязка намного больше двойственной, удвоить rho; если наоборот - уменьшить вдвое. При квадратичных f, g оптимальное rho вычисляется аналитически как геометрическое среднее констант Липшица.
Какое условие достаточно для сходимости ADMM при rho > 0?
Консенсусные алгоритмы
Консенсусная оптимизация - формулировка распределённой задачи, в которой N агентов независимо хранят локальные копии параметра x_i и приходят к согласию через локальные обмены информацией. Возникает в федеративном обучении, multi-agent control, sensor networks - везде, где централизация недопустима из-за приватности, географической распределённости или отказоустойчивости.
EXTRA (Shi et al. 2015) и DIGing (Nedic et al. 2017) исправляют систематическое смещение DGD при постоянном шаге. Идея - локальная коррекция через разность между двумя последовательными шагами смешивания. Достигают точной сходимости в распределённой среде.
Federated averaging (FedAvg) - частный случай локального ADMM с множественными локальными шагами между раундами связи. Снижение коммуникационной нагрузки достигается ценой смещения при гетерогенности данных - явление client drift. FedProx и SCAFFOLD исправляют это через proximal-член или коррекцию направления.
В чём ключевое преимущество консенсусной формулировки через ADMM?
Влияние топологии сети на сходимость
В децентрализованных методах граф коммуникации между агентами кардинально влияет на скорость сходимости. Спектральные свойства матрицы смешивания W (doubly stochastic, согласованная с графом) определяют, как быстро локальные оценки сходятся к глобальному консенсусу. Плотные графы дают быстрый консенсус ценой высокой коммуникационной нагрузки на каждом узле; разрежённые сети дешёвые на узел, но требуют больше итераций.
Метропольский выбор весов: W_ij = 1/(1 + max(d_i, d_j)) для рёбер, W_ii = 1 - sum_{j in N(i)} W_ij. Гарантирует doubly stochastic свойство без знания глобальной структуры графа - каждому узлу нужны только степени его соседей.
Что определяет скорость консенсуса в децентрализованной сети?
Ключевые идеи
- ADMM разбивает min f(x)+g(z) s.t. Ax+Bz=c на три шага: x-минимизация, z-минимизация, обновление множителей
- Консенсусная формулировка с x_i = z позволяет N агентам параллельно минимизировать локальные f_i
- Сходимость O(1/k) по невязкам при выпуклых f, g для любого rho > 0; при сильной выпуклости - линейная
- Децентрализованный DGD работает без центрального сервера через doubly stochastic матрицу смешивания W
- Критерий остановки требует одновременного выполнения прямой и двойственной невязок ниже порога
Связи с другими областями
Распределённая оптимизация объединяет выпуклый анализ, теорию графов и системы связи.
- Federated Learning — Связанная тема
- Двойственная теория — Связанная тема
- Теория графов — Связанная тема
Вопросы для размышления
- Почему параметр rho в ADMM влияет на скорость сходимости, хотя теоретически любой rho > 0 гарантирует сходимость?
- Как связаны двойственные переменные lambda в ADMM с ценами равновесия в экономических моделях?
- В чём принципиальное отличие DGD от ADMM с точки зрения требований к коммуникации между агентами?