Выпуклая оптимизация
Стохастическая оптимизация и адаптивные методы
Как обучать нейросеть на миллиарде примеров, если даже один проход по всем данным занимает часы, а градиент по полной выборке не помещается в память?
- GPT-4: обучение на 25 000 GPU в течение 90 дней с 10^23 операций - только Adam делает такой масштаб возможным через адаптивные шаги на координату
- YouTube рекомендации: модель обновляется онлайн на потоке 500 млн новых просмотров в день через mini-batch SGD без пересмотра истории
- Финансовый HFT: стохастическая аппроксимация оценивает параметры риска в реальном времени по потоку биржевых тиков
- Медицинский federated learning: обучение модели рака на 50 больницах через локальный SGD без обмена пациентами
Предварительные знания
- Градиентный спуск
- Выпуклые функции и L-гладкость
- Теория вероятностей
Основы SGD: стохастический градиент
Стохастический градиентный спуск (Robbins-Monro 1951) - основа всего современного глубокого обучения. Вместо точного градиента F(theta) = (1/N)*sum f_i(theta) на каждом шаге используется оценка по случайной подвыборке (мини-батчу). Это снижает стоимость итерации с O(N) до O(1) (или O(batch)), позволяя обучать модели с миллионами параметров на данных в петабайтах.
Mini-batch SGD - стандартная практика: вместо одного слагаемого используется среднее по B наблюдениям. Снижает дисперсию шума в B раз, позволяет параллельные вычисления на GPU, при этом стоимость итерации остаётся приемлемой. Типичные B - от 32 до 1024 в зависимости от модели и оборудования.
В невыпуклой задаче (типичной для глубокого обучения) SGD сходится только к стационарной точке, не обязательно глобальному оптимуму. Эмпирически стохастичность помогает выходить из плохих локальных минимумов и седловых точек - это одна из причин успеха SGD в глубоком обучении.
Почему SGD предпочтителен перед полным градиентным спуском при больших N?
Методы редукции дисперсии
Главное ограничение SGD - шум градиента, замедляющий сходимость. Методы редукции дисперсии (SVRG, SAGA, Katyusha) сочетают преимущество стохастичности с детерминированной скоростью. Идея: периодически обновлять полный градиент как опорную точку и использовать его как control variate для уменьшения дисперсии стохастической оценки.
Katyusha (Allen-Zhu 2017) - акселерированный VR-метод с оптимальной сложностью O((n + sqrt(n*kappa))*log(1/eps)) для сильно выпуклых задач. Достигает теоретической нижней границы для класса стохастических методов первого порядка.
Какое главное преимущество VR-методов перед стандартным SGD?
Адаптивные методы: AdaGrad, Adam, AdamW
Адаптивные методы автоматически настраивают шаг для каждой координаты на основе истории градиентов. AdaGrad (Duchi 2011) ввёл идею; RMSProp (Hinton 2012) и Adam (Kingma 2014) её усовершенствовали и стали стандартом в глубоком обучении. AdamW (Loshchilov 2017) исправил взаимодействие с регуляризацией. Эти методы доминируют в обучении трансформеров - GPT, BERT, PaLM все используют варианты Adam.
AdamW отделяет L2-регуляризацию от градиентного шага: вместо g_k + lambda*theta использует theta_{k+1} = (1 - lambda*alpha)*theta_k - alpha*update. Это исправляет проблему Adam, где L2 неравномерно масштабируется через v_k. Эмпирически даёт лучшую генерализацию на больших моделях.
Несмотря на повсеместность, Adam теоретически не сходится для всех выпуклых задач (Reddi 2018) - существуют контрпримеры. AMSGrad исправляет это, требуя монотонность v_k. На практике это редко проявляется, и стандартный Adam остаётся выбором по умолчанию.
Современные оптимизаторы (Lion, Sophia, Shampoo) развивают идеи Adam. Lion (2023) использует только знак градиента - сокращает память в 2 раза при сопоставимой производительности. Sophia (2024) использует приближённый гессиан для адаптации шага - даёт ускорение на 2x при обучении LLM. Эти методы активно тестируются в индустрии.
Какую проблему AdaGrad решает Adam через экспоненциальное среднее?
Ключевые идеи
- SGD заменяет полный градиент несмещённой оценкой по мини-батчу; стоимость итерации O(b) вместо O(n)
- Условие Роббинса-Монро (сумма шагов = inf, сумма квадратов < inf) гарантирует сходимость a.s.
- Скорость SGD: O(1/sqrt(K)) для выпуклых задач - нижняя граница для first-order стохастических методов
- Adam адаптирует шаг по каждой координате через первый (m) и второй (v) моменты с коррекцией смещения
- Variance reduction (SVRG, SARAH) устраняет ограничение O(1/sqrt(K)): линейная сходимость при сильной выпуклости
Связи с другими областями
Стохастическая оптимизация соединяет численные методы, статистику и теорию вероятностей.
- Стохастическая оптимизация — Базовая глава о SGD, моментуме и Adam
- Онлайн-выпуклая оптимизация — Адаптивные методы AdaGrad/Adam изначально появились в OCO-литературе
- Крупномасштабная оптимизация — Распределённые версии SGD масштабируют адаптивные методы на тысячи GPU
Вопросы для размышления
- Почему увеличение размера батча не масштабируется линейно: удвоение батча не вдвое снижает число шагов?
- Как warm-up schedule связан с нестабильностью градиентов при случайной инициализации нейросети?
- В чём принципиальное отличие variance reduction методов от gradient clipping для улучшения SGD?