- Улучшенное онлайн-конформное прогнозирование с помощью сильно адаптивного онлайн-обучения (arXiv)
Автор: Аадьот Бхатнагар, Хуан Ван, Каймин Сюн, Ю Бай.
Аннотация: мы изучаем проблему количественной оценки неопределенности с помощью наборов прогнозов в онлайн-режиме, где распределение данных может произвольно меняться с течением времени. В недавней работе разрабатываются онлайн-методы конформного прогнозирования, которые используют алгоритмы минимизации сожалений из литературы по онлайн-обучению для изучения наборов прогнозов с приблизительно достоверным покрытием и небольшим сожалением. Однако стандартная минимизация сожалений может оказаться недостаточной для работы в изменяющихся условиях, когда могут потребоваться гарантии производительности не только в течение всего периода времени, но и во всех (под)интервалах времени. Мы разрабатываем новые онлайн-методы конформного прогнозирования, которые минимизируют сильно адаптивное сожаление, которое измеряет сожаление в наихудшем случае на всех интервалах фиксированной длины. Мы доказываем, что наши методы обеспечивают почти оптимальное сильно адаптивное сожаление для всех длин интервалов одновременно и приблизительно достоверное покрытие. Эксперименты показывают, что наши методы постоянно обеспечивают лучшее покрытие и меньшие наборы прогнозов, чем существующие методы для реальных задач, таких как прогнозирование временных рядов и классификация изображений при сдвиге распределения.
2. Oracle-Efficient Smoothed Online Learning для кусочно-непрерывного принятия решений (arXiv)
Автор: Адам Блок, Александр Рахлин, Макс Симховиц.
Аннотация: Сглаженное онлайн-обучение стало популярной структурой для смягчения существенной потери статистической и вычислительной сложности, возникающей при переходе от классического к состязательному обучению. К сожалению, для некоторых пространств было показано, что эффективные алгоритмы страдают экспоненциально большим сожалением, чем минимаксно-оптимальные, даже когда обучающийся имеет доступ к оракулу оптимизации в пространстве. Чтобы смягчить эту экспоненциальную зависимость, в этой работе вводится новое понятие сложности, обобщенные числа, заключенные в скобки, которые объединяют ограничения противника с размером пространства и показывают, что реализация «Следуй за возмущенным лидером» может достичь низкого уровня сожаления. с оптимальным масштабированием числа обращений к оракулу оптимизации относительно среднего сожаления. Затем мы конкретизируем наши оценки в нескольких интересующих задачах, включая онлайн-прогнозирование и планирование кусочно-непрерывных функций, которые имеют множество приложений в таких разных областях, как эконометрика и робототехника.
