Теоретики онлайн-оптимизации закрыли давний вопрос: какова точная цена доступа к допустимому множеству через оракул линейной оптимизации вместо явных проекций.
В работе установлен безразмерный минимаксный ожидаемый регрет Θ(GD·max{√T, T/(1+min{Q,BT})^{1/4}}) для выпуклых G-липшицевых функций, диаметра D, общего бюджета Q вызовов оракула и лимита B вызовов на раунд — вместе с нижней оценкой, которая делает этот результат точным, а не просто достижимым.
Практический смысл: больше вызовов оракула — ниже регрет, и теперь известна точная шкала обмена между вычислительным бюджетом и качеством обучения.
Задача: онлайн-оптимизация без проекций
Online convex optimization (OCO) — базовая модель для ситуаций, где решение нужно принимать последовательно, до того как известна функция потерь: распределение бюджета, динамическое ценообразование, маршрутизация. Классические алгоритмы вроде online gradient descent на каждом шаге делают проекцию на допустимое множество, чтобы решение осталось в ограничениях.
Проблема в том, что проекция сама по себе дорога. Для сложных допустимых множеств — матроидных, комбинаторных, с огромным числом ограничений — проекция может требовать решения трудной задачи. А вот линейная оптимизация над таким множеством часто дёшева: это ровно то, что комбинаторные решатели и LP-оракулы делают быстро. Отсюда класс projection-free методов, где проекция заменена вызовами оракула линейной оптимизации.
До этой работы оставался открытым количественный вопрос: сколько именно вызовов оракула нужно, чтобы удержать регрет на уровне √T, и что происходит при меньшем бюджете? Ответ оказался резче, чем ожидалось.
Оракул линейной оптимизации и бюджет вызовов
Модель в работе задаётся четырьмя параметрами:
- G — константа Липшица функций потерь;
- D — диаметр допустимого множества;
- Q — общий бюджет вызовов оракула на все T раундов;
- B — максимум вызовов оракула за один раунд.
Оракул для бизнеса в этой картине — удобная метафора: в реальных системах роль «дорогого чёрного ящика» играют оптимизационные решатели, симуляции или внешние сервисы, каждый вызов которых стоит денег и времени. Автоматизация бизнеса, построенная на онлайн-обучении, упирается ровно в этот ресурс — алгоритм не может дёшево проверить любое ограничение, он может лишь задавать оракулу направленные вопросы.
Точная формула: минимаксный регрет
Центральный результат — безразмерная минимаксная оценка ожидаемого регрета:
Θ(GD·max{√T, T/(1+min{Q,BT})^{1/4}})
Здесь min{Q,BT} — фактический доступный бюджет: либо общий запас Q, либо произведение лимита на раунд B на число раундов T, смотря что меньше. Формула масштабная: она не зависит от размерности задачи напрямую, только от G и D.
Как читать формулу
Два режима в max{} делят картину на зоны:
- Если бюджет велик, знаменатель растёт и второе слагаемое падает ниже √T — регрет упирается в классический барьер GD√T, знакомый по OCO с проекциями.
- Если бюджет мал, доминирует член T/(1+min{Q,BT})^{1/4} — регрет деградирует медленнее, чем линейно, но быстрее, чем √T.
Порог насыщения: чтобы выйти на режим √T, нужно min{Q,BT} порядка T². Это неочевидный и жёсткий факт — интуиция подсказывала бы, что хватит порядка T вызовов, по одному на раунд. Оказывается, нет: замена проекции оракулом обходится дороже, чем «один вызов за шаг».
Нижняя оценка
Ключевая часть работы — не только верхняя граница (алгоритм, достигающий этой величины), но и нижняя оценка для произвольных рандомизированных алгоритмов. Именно она превращает формулу из «мы умеем так» в «лучше невозможно в принципе». Любой алгоритм, работающий в этой модели с тем же бюджетом, имеет ожидаемый регрет не ниже указанного выражения с точностью до констант.
Для теории это редкая ситуация полного ответа: минимаксная цена компромисса известна точно, включая промежуточные режимы между √T и линейным регретом. Подробности режимов разобраны в разделе [Режимы: от √T к линейному регрету](#режимы-от-t-к-линейному-регрету).
Режимы: от √T к линейному регрету
Между двумя крайностями лежит непрерывная шкала. Если бюджет Q растёт как T^α при α от 0 до 2, регрет ведёт себя как T в степени (1 − α/4) с поправкой на барьер √T. Итоговая картина:
- Q ~ T² и больше: регрет Θ(GD√T) — лучший возможный;
- Q ~ T: регрет порядка T^{3/4} — заметно хуже √T, но сублинейный;
- Q ~ √T: регрет приближается к T^{7/8};
- Q константен: регрет почти линейный — обучение практически не происходит.
Отдельно работает ограничение B на вызовы в одном раунде. Даже при огромном общем бюджете Q жёсткий лимит B срезает эффективный бюджет до BT — это важно для потоковых систем, где раунд жёстко ограничен по времени. Взаимодействие Q и B описано в [формуле минимаксного регрета](#точная-формула-минимаксный-регрет).
Что это значит для практики
Резкие для бизнеса выводы из теоретической работы сводятся к трём пунктам.
Регрет для бизнеса — цена обучения
Регрет измеряет, насколько суммарные потери алгоритма хуже потерь лучшего фиксированного решения, выбранного задним числом. Регрет для бизнеса — это буквально деньги: перерасход бюджета относительно оптимального плана за период. Сублинейный регрет означает, что средние потери на раунд стремятся к оптимальным; линейный — что система так и не научилась.
Формула даёт способ заранее посчитать, какой бюджет на вызовы оракула нужен, чтобы обучение вообще сходилось к оптимуму.
Компромиссы для бизнеса считаются, а не угадываются
Компромиссы для бизнеса между точностью и стоимостью вычислений обычно обсуждаются качественно. Здесь впервые для целого класса задач дана точная кривая обмена: каждый дополнительный порядок бюджета вызовов покупает измеримое снижение регрета, и предел этой покупки известен. Планируя автоматизацию бизнеса на projection-free алгоритмах, можно обоснованно выбирать точку на кривой, а не полагаться на эмпирику.
Порог T² — главный практический сюрприз
Если система рассчитана на T раундов и хочет регрет уровня √T, суммарный бюджет оракула должен быть порядка T². Для длинных горизонтов это много — и это не дефект конкретного алгоритма, а нижняя оценка для всех. Вывод: для длинных горизонтов либо закладывайте дорогой оракул, либо миритесь с регретом T^{3/4} и хуже. Короткие горизонты, напротив, прощают скупой бюджет.
Где это применимо
Модель с линейным оракулом естественно ложится на задачи, где допустимое множество комбинаторно, а линейная оптимизация над ним — стандартная операция:
- распределение рекламного бюджета по каналам с дискретными пакетами;
- ассортиментные и логистические решения с матроидными ограничениями;
- онлайн-подбор конфигураций, где каждое «испытание» решения стоит реальных ресурсов.
Искусственный интеллект в таких системах учится не на данных из хранилища, а на потоке решений и обратных связей — и именно для этого режима формула задаёт фундаментальные пределы.
Итоги
Работа закрывает вопрос о цене projection-free онлайн-оптимизации: минимаксный ожидаемый регрет равен Θ(GD·max{√T, T/(1+min{Q,BT})^{1/4}}), и это доказано с обеих сторон — верхняя оценка алгоритмом, нижняя против любых рандомизированных алгоритмов. Три числа, которые стоит запомнить: порог бюджета T² для регрета √T, деградация T^{3/4} при бюджете T и почти линейный регрет при скупом оракуле.
Для инженерных систем это перевод разговора о вычислительном бюджете из области интуиции в область арифметики — см. практические следствия в разделе [Что это значит для практики](#что-это-значит-для-практики).
Источник: https://arxiv.org/abs/2610.00254