Онлайн-выпуклая оптимизация

Хазан в 2007 году доказал, что каждый онлайн-алгоритм выпуклой оптимизации может быть представлен как FTRL с некоторым регуляризатором. Это унифицировало все методы - от OGD до мультипликативных весов - в единый фреймворк.

• Рекомендательные системы: OGD обновляет матрицу факторов после каждого взаимодействия пользователя
• Торговые алгоритмы: MWU балансирует портфель активов, минимизируя сожаление относительно лучшего актива
• Обучение нейросетей: Adam/AdaGrad - онлайн-оптимизаторы с адаптивным шагом

Предварительные знания

• Предыдущий урок

OGD и сожаление O(√T)

Зинкевич в 2003 году доказал, что Online Gradient Descent с шагом η = D/(G√T) достигает сожаления R_T ≤ DG√T, где D - диаметр множества допустимых решений, G - норма субградиента. При T→∞ среднее сожаление R_T/T → 0 - алгоритм «почти оптимален» ретроспективно.

Метод экспоненциальных весов и FTRL

Follow-The-Regularized-Leader (FTRL): w_{t+1} = argmin_w sum_{s<t} f_s(w) + R(w). При R(w) = (1/2η)||w||² - OGD; при R(w) = (1/η)∑w_i log w_i - алгоритм мультипликативных весов. Hazan et al. (2007): FTRL с адаптивной регуляризацией достигает O(√T) даже для нелипшицевых функций.

Ключевые идеи

• OGD: w_{t+1} = Π_K(w_t - η∇f_t(w_t)), R_T ≤ DG√T
• Нижняя граница: R_T = Ω(√T) - OGD оптимален
• FTRL: w_{t+1} = argmin_w [∑f_s(w) + R(w)/η]
• AdaGrad: диагональный прекондиционер G_t = ∑g_s g_s^T
• MWU: R_T ≤ 2√(T ln K) при K экспертах

Дальнейшие пути

Изученные концепции открывают следующие разделы.

• co-28-bandit-opt — extends

Вопросы для размышления

• Приведите конкретный пример вычисления.
• Как изученные концепции связаны с другими разделами математики?