Онлайн-выпуклая оптимизация за 20 лет дошла от теории до Adam и LLM

Двадцать лет назад online convex optimization (OCO) оставалась молодым направлением на стыке теоретической информатики, машинного обучения и оптимизации. Сегодня её язык (регрет, адаптивные обновления, последовательные решения без знания будущего) встроен в то, как обучают современные модели. Китайское издание Jiqizhixin посвятило этому пути большой материал с ироничным заголовком: человек, который всю жизнь изучал «сожаление», говорит, что ни о чём не жалеет. В доступном нам фрагменте текст обрывается на перечислении методов (Online Newton Step и далее), а имя героя не названо. Поэтому ниже мы опираемся на публичную историю области, а не на детали самого интервью.

Что измеряет регрет

Обычная постановка задачи оптимизации знает всю функцию потерь заранее. В OCO всё иначе. На каждом шаге алгоритм выбирает точку, и только после этого среда показывает выпуклую функцию потерь. Качество измеряют регретом: суммой потерь алгоритма минус сумма потерь лучшего фиксированного решения, которое можно выбрать задним числом.

Главное достижение области в том, что регрет удаётся сделать сублинейным. Тогда средние потери алгоритма стремятся к потерям лучшего постоянного выбора, причём без статистических предположений о данных. Классическая работа Мартина Зинкевича 2003 года показала, что онлайн-градиентный спуск даёт регрет порядка √T на выпуклых липшицевых функциях. Это стало отправной точкой.

От Online Newton Step к адаптивным оптимизаторам

Около 2006 года Элад Хазан, Амит Agarwal и Сатьен Кейл предложили алгоритм Online Newton Step. Для так называемых exp-concave функций он даёт регрет порядка log T, то есть заметно лучше √T. Идея в использовании информации второго порядка: шаг подстраивается под геометрию накопленных градиентов.

Дальше эта линия привела к методам, знакомым каждому, кто запускал обучение:

• AdaGrad (Duchi, Hazan, Singer, 2011): отдельный масштаб шага для каждого параметра. Хорошо работает на разреженных признаках.
• RMSProp и Adam (2014): практические потомки той же идеи с экспоненциальным усреднением градиентов.
• Регрет-анализ как стандарт доказательств: исходное обоснование сходимости Adam строилось именно в рамках OCO.

Есть и показательный эпизод. В 2018 году статья «On the Convergence of Adam and Beyond» (Reddi и соавторы, ICLR) показала, что исходное доказательство для Adam содержит ошибку и что метод может не сходиться на некоторых выпуклых задачах. Исправление, AMSGrad, тоже сформулировано на языке регрета. Теория не просто описывала практику, она ловила её на ошибках.

Почему это важно сейчас

Большие языковые модели обычно обучают вариантами Adam, чаще всего AdamW. Задача там невыпуклая, и гарантии OCO напрямую не переносятся. Но интуиция переносится: адаптивные шаги, предобусловливание, учёт кривизны. Современные исследования оптимизаторов с матричными предобуславливателями продолжают ту же линию, где диагональная адаптация AdaGrad уступает место более богатой структуре.

Отдельная ветка связана с онлайн-обучением в чистом виде. Регрет-минимизация лежит в основе алгоритмов для игр, рекомендательных систем, динамического ценообразования и распределения ресурсов. В этих задачах будущее действительно неизвестно, а данные не обязаны быть независимыми.

Что из этого взять на практике

Если вы обучаете или дообучаете модели, полезно помнить, откуда взялись гиперпараметры оптимизатора. Эпсилон, бета-коэффициенты и расписание шага не случайны, у них есть теоретический смысл. Он помогает отлаживать нестабильное обучение: расходимость часто связана с тем, что адаптивное усреднение «забывает» редкие, но крупные градиенты, как раз в духе контрпримера к Adam.

Для тех, кто строит системы с последовательными решениями (рекомендации, ставки в рекламных аукционах, маршрутизация запросов между моделями), OCO даёт готовую рамку. Она позволяет сравнивать алгоритмы с честным эталоном и получать гарантии без допущений о распределении. Для входа в тему подойдёт учебник Хазана «Introduction to Online Convex Optimization». Полный текст интервью на сайте Jiqizhixin стоит прочитать в оригинале: за заголовком про «ноль сожалений» там, судя по анонсу, личная история двадцати лет развития метода.