Оптимизация с изменяющимся во времени параметром для потоковых данных посредством временного взвешивания

Основная информация

• ID статьи: 2510.13052
• Название: Time-Varying Optimization for Streaming Data Via Temporal Weighting
• Авторы: Muhammad Faraz Ul Abrar (Arizona State University), Nicolò Michelusi (Arizona State University), Erik G. Larsson (Linköping University)
• Классификация: cs.LG cs.AI cs.SY eess.SP eess.SY math.OC
• Дата публикации: 15 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.13052

Аннотация

Классическая теория оптимизации занимается фиксированными, не зависящими от времени целевыми функциями. Однако оптимизация с изменяющимся во времени параметром стала важной темой для принятия решений в динамических средах. В данной работе мы исследуем проблему обучения на потоковых данных с точки зрения оптимизации с изменяющимся во времени параметром. В отличие от предыдущих работ, сосредоточенных на универсальных формулировках, мы вводим структурированную взвешенную формулировку, которая явно отражает источники потоковых данных с изменяющимися во времени целевыми функциями, где агент на каждом временном шаге стремится минимизировать взвешенное среднее потерь всех прошлых образцов данных. Мы сосредоточиваемся на двух конкретных стратегиях взвешивания: (1) равномерное взвешивание, которое одинаково обрабатывает все образцы; (2) дисконтированное взвешивание, которое геометрически затухает влияние старых данных. Для обеих схем мы выводим плотные границы для "ошибки отслеживания" (TE) при обновлениях градиентного спуска (GD), где TE определяется как отклонение параметров модели от оптимального решения с изменяющимся во времени параметром на данном временном шаге. Мы доказываем, что при равномерном взвешивании TE асимптотически исчезает со скоростью убывания O(1/t), тогда как дисконтированное взвешивание приводит к ненулевой нижней границе ошибки, контролируемой коэффициентом дисконтирования и количеством обновлений градиента, выполняемых на каждом временном шаге.

Исследовательский контекст и мотивация

Определение проблемы

Основная проблема, которую решает данная работа, заключается в оптимизации с изменяющимся во времени параметром при обучении на потоковых данных. Конкретно:

1. Ограничения классической оптимизации: Классическое машинное обучение оптимизирует статические целевые функции, предполагая статическое распределение данных, однако реальные решения работают в динамически развивающихся средах
2. Вызовы потоковых данных: Данные поступают последовательно, целевая функция эволюционирует во времени, что приводит к нестационарным задачам оптимизации
3. Вычислительные ограничения: В режиме реального времени или при ограниченных ресурсах на каждом временном шаге можно выполнить только ограниченное количество обновлений

Значимость

Данная проблема имеет важное значение в нескольких критических областях применения:

• Отслеживание мобильных роботов в автономных транспортных средствах
• Локализация движущихся целей
• Оптимизация портфеля
• Управление рисками на волатильных финансовых рынках
• Адаптация контроллеров к динамике систем, изменяющихся во времени

Ограничения существующих методов

1. Слабые границы универсальных формулировок: Большинство существующих работ сосредоточены на универсальных формулировках, изменяющихся во времени, игнорируя внутреннюю структуру потоковых данных, что может привести к слабым границам ошибки отслеживания
2. Отсутствие структурированного анализа: Существующие методы не используют явно структуру взвешивания потоковых данных для получения более плотных границ производительности
3. Разрыв между теорией и практикой: Методы в области непрерывного обучения в основном являются эмпирическими и лишены теоретической основы

Основные вклады

1. Предложение структурированной взвешенной формулировки: Введение целевой функции, изменяющейся во времени, которая явно отражает структуру потоковых данных, определяемой как взвешенное среднее потерь всех прошлых образцов
2. Теоретический анализ двух стратегий взвешивания:
   • Равномерное взвешивание: Доказательство того, что ошибка отслеживания асимптотически исчезает со скоростью O(1/t)
   • Дисконтированное взвешивание: Вывод явной границы ненулевой асимптотической ошибки отслеживания
3. Вывод плотных границ: Использование структуры потоковых данных для получения более плотных границ TE по сравнению с существующим универсальным анализом, изменяющимся во времени
4. Теоретическая и экспериментальная верификация: Проверка действительности теоретических результатов посредством численного моделирования

Подробное описание методов

Определение задачи

Рассмотрим установку обучения, в которой отдельный агент (например, граничный или облачный сервер) стремится отследить параметры модели машинного обучения, изменяющиеся во времени:

• Входные данные: На каждой итерации t≥1 агент получает новый образец данных (x_t, y_t)
• Выходные данные: Параметры модели w_t, минимизирующие взвешенное среднее потерь накопленных данных
• Ограничение: На каждом временном шаге можно выполнить только E обновлений градиента

Основные математические формулы

Целевая функция, изменяющаяся во времени: $w_t^* = \arg\min_{w \in \mathbb{R}^d} F_t(w), \quad \text{где} \quad F_t(w) = \sum_{i=1}^t a_i(t)f_i(w)$

где:

• $a_i(t)$ — вес i-го образца в момент времени t
• $f_i(w)$ — функция потерь для i-го образца данных
• Веса удовлетворяют: $0 \leq a_i(t) \leq 1$ и $\sum_{i=1}^t a_i(t) = 1$

Обновление градиентного спуска: $w_{t,k+1} = w_{t,k} - \eta\nabla F_{t+1}(w_{t,k}) = w_{t,k} - \eta\sum_{i=1}^{t+1} a_i(t+1)\nabla f_i(w_{t,k})$

Определение ошибки отслеживания: $\text{TE}(t) = \|w_t - w_t^*\|$

Две стратегии взвешивания

1. Равномерное взвешивание

Установка $a_i(t) = 1/t$ для всех $i = 1, \ldots, t$, целевая функция становится: $F_{t+1}(w) = \frac{t}{t+1}F_t(w) + \frac{1}{t+1}f_{t+1}(w)$

2. Дисконтированное взвешивание

Использование геометрического дисконтирования: $a_i(t) = \frac{1-\gamma}{1-\gamma^t}\gamma^{t-i}$, где $0 < \gamma < 1$ — коэффициент дисконтирования.

Технические инновации

1. Структурированный анализ: В отличие от универсальной оптимизации, изменяющейся во времени, явное использование структуры взвешивания потоковых данных
2. Анализ дрейфа минимизатора: Понимание изменения целевой функции посредством анализа $\|w_{i+1}^* - w_i^*\|$
3. Рекурсивный анализ ошибок: Установление рекурсивных соотношений для отслеживания эволюции ошибок

Теоретический анализ

Основные предположения

Предположение 1 (L-гладкость и μ-сильная выпуклость): Функция потерь каждого образца данных удовлетворяет:

• $\|\nabla f_t(x) - \nabla f_t(y)\| \leq L\|x-y\|$
• $f_t(y) \geq f_t(x) + \nabla f_t(x)^T(y-x) + \frac{\mu}{2}\|y-x\|^2$

Предположение 2 (Ограниченный минимизатор): Существует $C > 0$ такое, что $\|w_t^*\| \leq C$ для всех t.

Основные теоретические результаты

Ошибка отслеживания при равномерном взвешивании

Предложение 1: Для равномерного взвешивания ошибка отслеживания удовлетворяет: $\text{TE}(t) \leq \alpha^t\|w_0 - w_1^*\| + \frac{C'A}{t}$

где $\alpha = (1-\eta\mu)^E < 1$, $C' = (1+\sqrt{L/\mu})\frac{LC}{\mu}$.

Ключевой вывод: TE убывает со скоростью O(1/t), асимптотическая ошибка отслеживания равна нулю.

Ошибка отслеживания при дисконтированном взвешивании

Предложение 2: Для дисконтированного взвешивания асимптотическая ошибка отслеживания равна: $\text{ATE}_\gamma = \limsup_{t\to\infty} \|w_t - w_t^*\| \leq \left(1+\sqrt{\frac{L}{\mu}}\right)\frac{LC}{\mu} \cdot \frac{(1-\gamma)\alpha}{1-\alpha}$

Ключевой вывод: Существует ненулевая нижняя граница ошибки, контролируемая коэффициентом дисконтирования γ и количеством обновлений градиента E.

Экспериментальная установка

Генерация данных

Использование скалярной квадратичной функции потерь: $f_t(w) = \frac{\mu}{2}(w-c_t)^2$

Параметры установки:

• $c_t$ генерируется согласно ограниченному случайному блужданию: $c_{t+1} = \max(-C_{\max}, \min(c_t + z_{t+1}, C_{\max}))$
• $z_t \sim \mathcal{N}(0, \sigma^2)$, $C_{\max} = 100$, $\sigma^2 = 100$, $\mu = 0.1$

Метрики оценки

• Среднеквадратичная ошибка отслеживания
• Максимальная (наихудший случай) ошибка отслеживания
• Статистические результаты 1000 независимых прогонов

Результаты экспериментов

Результаты равномерного взвешивания

• Верификация убывания O(1/t): Эксперименты ясно демонстрируют монотонное убывание, согласующееся с теоретическими предсказаниями
• Влияние количества обновлений градиента: Увеличение E с 10 до 20 улучшает эмпирическую TE примерно на коэффициент 0.09, что количественно совпадает с теоретическими предсказаниями
• Долгосрочное поведение: Для больших t TE доминируется остаточной ошибкой от дрейфа минимизатора

Результаты дисконтированного взвешивания

• Ненулевая нижняя граница ошибки: Все показатели ошибок сходятся к ненулевой асимптотической границе ошибки отслеживания
• Влияние коэффициента дисконтирования: Больший γ приводит к более низкой асимптотической ошибке отслеживания
• Теоретическая верификация: При γ=0.99 TE приближается к случаю равномерного взвешивания, что подтверждает теоретический анализ

Сложность градиента

Предложение 3: Для обеспечения $\text{ATE}_\gamma \leq \epsilon$ необходимо выполнить: $E \geq \frac{\ln\left(\frac{\epsilon}{C'(1-\gamma)+\epsilon}\right)}{\ln(1-\eta\mu)}$ обновлений градиента, что приводит к сложности градиентных итераций O(ln(1/ε)).

Связанные работы

Оптимизация, изменяющаяся во времени

• Ранние работы: Алгоритмы ньютоновского типа, использующие информацию второго порядка для достижения экспоненциальной сходимости
• Условия ограниченного дрейфа: Методы, предполагающие $\|w_{t+1}^* - w_t^*\| \leq C$
• Схемы предсказание-коррекция: Методы, сочетающие предсказание и коррекцию градиента

Непрерывное обучение

• Обучение на последовательности задач: Обучение моделей машинного обучения на последовательности задач
• Катастрофическое забывание: Проблема деградации производительности старых задач при обучении новым задачам
• Эмпирические методы: Существующие методы в основном являются эмпирическими и лишены теоретической основы

Уникальность вклада данной работы

Данная работа впервые соединяет оптимизацию, изменяющуюся во времени, и непрерывное обучение с теоретической точки зрения, обеспечивая явный анализ структуры потоковых данных.

Заключение и обсуждение

Основные выводы

1. Равномерное взвешивание: Достижение ошибки отслеживания с убыванием O(1/t), асимптотическое идеальное отслеживание
2. Дисконтированное взвешивание: Производство явно количественной ненулевой асимптотической ошибки, отражающей забывание старых данных
3. Структурированный анализ: Использование структуры потоковых данных для получения более плотных границ по сравнению с универсальными методами

Теоретические идеи

• Равномерное vs дисконтированное: Равномерное взвешивание разбавляет влияние каждого нового образца до O(1/t), тогда как дисконтированное взвешивание сохраняет дрейф O(1)
• Сходимость весов: При γ→1 дисконтированное взвешивание сходится к равномерному взвешиванию, соответственно ATE_γ→0
• Компромисс вычислительного бюджета: Больше обновлений градиента E может уменьшить ошибку отслеживания, но увеличивает вычислительные затраты

Ограничения

1. Предположение о памяти: Предполагается доступ ко всем градиентам исторических образцов, не учитываются ограничения памяти
2. Специфичные функции потерь: Теоретический анализ основан на предположениях L-гладкости и μ-сильной выпуклости
3. Ограниченный минимизатор: Требуется предположение об равномерной ограниченности минимизаторов

Направления будущих исследований

1. Анализ с ограничениями памяти: Исследование обучения, изменяющегося во времени, при ограничениях памяти
2. Более общие функции потерь: Расширение на невыпуклые или другие типы потерь
3. Распределенные установки: Применение в распределенных средах, таких как федеративное обучение
4. Адаптивные веса: Исследование стратегий динамического взвешивания, управляемых данными

Глубокая оценка

Преимущества

1. Теоретическая строгость: Обеспечение полного математического анализа и вывода плотных границ
2. Структурированный подход: Явное использование структуры потоковых данных, получение более точных результатов по сравнению с универсальными методами
3. Практическая ценность: Две стратегии взвешивания соответствуют различным сценариям практического применения
4. Экспериментальная верификация: Численные результаты высоко согласуются с теоретическими предсказаниями
5. Ясное изложение: Хорошо организованная статья с четкими математическими выводами

Недостатки

1. Ограничения предположений: Предположения L-гладкости и μ-сильной выпуклости могут быть чрезмерно строгими в практических приложениях
2. Требования к памяти: Необходимость хранения всех исторических градиентов нереалистична в крупномасштабных приложениях
3. Одноагентная установка: Рассмотрение только одноагентной установки, без многоагентных или распределенных сценариев
4. Простые эксперименты: Эксперименты используют простую квадратичную функцию потерь, не хватает верификации в сложных сценариях

Влияние

1. Теоретический вклад: Обеспечение важной теоретической основы для оптимизации, изменяющейся во времени, и непрерывного обучения
2. Методологическая ценность: Метод структурированного анализа может быть обобщен на другие задачи обучения, изменяющегося во времени
3. Практическое применение: Обеспечение теоретического руководства для проектирования систем онлайн-обучения и адаптивных систем
4. Воспроизводимость: Подробное описание теоретических результатов и экспериментальной установки облегчает воспроизведение

Применимые сценарии

1. Системы онлайн-обучения: Системы машинного обучения, которые должны непрерывно адаптироваться к новым данным
2. Адаптивное управление: Проектирование контроллеров для систем, изменяющихся во времени
3. Финансовое моделирование: Инвестиционные стратегии, которые должны адаптироваться к изменениям рынка
4. Приложения Интернета вещей: Обработка данных в реальном времени в сетях датчиков
5. Системы рекомендаций: Алгоритмы рекомендаций, которые должны адаптироваться к изменяющимся предпочтениям пользователей

Библиография

Статья цитирует 40 связанных работ, охватывающих ключевые области оптимизации, изменяющейся во времени, непрерывного обучения, выпуклой оптимизации и других, обеспечивая прочную теоретическую основу для исследования.