Online Convex Optimization: учиться на потоке

В 2003 году Мартин Зинкевич доказал, что простой проективный градиентный спуск даёт $O(\sqrt{T})$ regret против любого adversarial противника. Через шесть лет Yahoo Research поставили contextual bandits на production-ранжирование новостей. Сегодня Vowpal Wabbit обучает миллиарды примеров online без единого batch-прохода, а в Spotify каждый skip трека обновляет рекомендательную модель за миллисекунды. Online Convex Optimization - это не теоретическая абстракция, это инженерный язык streaming ML.

• **Vowpal Wabbit (Microsoft Research):** обучается online с начала проекта, single-pass на терабайтных датасетах рекламных кликов, обновление модели за микросекунды на каждом примере
• **Spotify recommendations:** contextual bandits на skip-сигнале и audio-features, online-обновление эмбеддингов треков и юзеров после каждой сессии прослушивания
• **Yahoo News article ranking (Li et al. 2010):** LinUCB как первое production-внедрение contextual bandits, A/B показал прирост CTR на 12.5 процентов против batch-моделей

Online setting: данные приходят по одному

Online setting радикально отличается от batch. На раунде $t$ алгоритм выбирает точку $x_t \in K$ ДО того как видит loss-функцию $f_t$. После выбора $f_t$ открывается, выплачивается штраф $f_t(x_t)$, и наступает раунд $t+1$. Никакой возможности пересчитать прошлые ходы - решения принимаются в реальном времени.

Зачем online: streaming-данные (Twitter trends обновляются каждую секунду), нестационарность (распределение кликов сегодня не такое, как вчера), big data (один проход по данным - дешевле, чем хранить и переобучать).

Vowpal Wabbit от Microsoft Research построен online с самого начала: модель обновляется на каждом примере без хранения датасета. В рекомендательных системах Netflix эмбеддинги юзеров пересчитываются после каждого просмотра - типичное online-обновление с миллиардами раундов в день.

Regret bounds: что значит хорошо учиться online

Regret - центральная метрика online-обучения: $R_T = \sum_{t=1}^T f_t(x_t) - \min_{x^* \in K} \sum_{t=1}^T f_t(x^*)$. Сравнение идёт с лучшей фиксированной точкой $x^*$, выбранной задним числом с полным знанием всех $f_t$. Цель алгоритма - сделать $R_T$ как можно меньше.

Online Gradient Descent (Zinkevich 2003): $x_{t+1} = \Pi_K(x_t - \eta_t \nabla f_t(x_t))$. При $\eta_t = D / (G \sqrt{t})$ достигает $R_T = O(\sqrt{T})$ regret для convex Lipschitz losses, и $O(\log T)$ для strongly convex.

No-regret свойство: $R_T / T \to 0$. Это значит, что средний loss алгоритма сходится к лучшему фиксированному решению. Lower bound $\Omega(\sqrt{T})$ Abernethy-Bartlett-Rakhlin 2008 показывает, что улучшить $\sqrt{T}$ для general convex losses нельзя без дополнительной структуры.

Связь с SGD: Stochastic Gradient Descent - частный случай OGD, где $f_t$ - случайная выборка из распределения. Regret-анализ объясняет, почему SGD generalize: bound на regret превращается в bound на excess risk через online-to-batch conversion (Cesa-Bianchi-Conconi-Gentile 2004).

Mirror descent: универсальный no-regret алгоритм

Mirror Descent (Nemirovski-Yudin 1983) обобщает OGD: вместо евклидовой проекции используется Bregman divergence $D_\phi(x, y) = \phi(x) - \phi(y) - \langle \nabla \phi(y), x - y \rangle$, порождённая mirror map $\phi$. Update: $x_{t+1} = \arg\min_{x \in K} [\langle \nabla f_t(x_t), x \rangle + \frac{1}{\eta} D_\phi(x, x_t)]$.

Выбор $\phi$ подгоняется под геометрию $K$. На probability simplex $\Delta^n$ с $\phi(x) = \sum x_i \log x_i$ (negative entropy) Bregman divergence становится KL-дивергенцией, и mirror descent превращается в multiplicative weights / Hedge / EXP3.

Regret bound mirror descent: $R_T \le \sqrt{2 R^2 G_*^2 T / \sigma}$, где $R$ - радиус $K$ в $\phi$-геометрии, $G_*$ - dual норма градиента, $\sigma$ - сила выпуклости $\phi$. Для simplex с entropy получается $O(\sqrt{T \log n})$ против $O(\sqrt{Tn})$ у евклидового OGD - выигрыш $\sqrt{n / \log n}$ раз.

AdaGrad (Duchi-Hazan-Singer 2011) - mirror descent с data-dependent $\phi_t$, накапливающим квадраты градиентов. Adam - эвристическая mirror-descent-вариация с moving averages. В information geometry mirror descent с $\phi$-divergence для exponential family совпадает с natural gradient descent.

Bandit feedback: только loss, не gradient

Bandit setting - online setting с partial feedback: видно только $f_t(x_t)$ как скаляр, без градиента и без значений в других точках. Это реалистично для production-систем: при показе рекламы наблюдается клик/не-клик по выбранному варианту, но нет данных о том, что произошло бы с другими.

Multi-armed bandits: $K$ дискретных рук, на каждом шаге выбирается одна. UCB1 (Auer-Cesa-Bianchi-Fischer 2002) даёт $O(\sqrt{KT \log T})$ regret через верхние доверительные оценки. Thompson Sampling (Thompson 1933, переоткрыт в 2010-х) использует Bayesian posterior - часто лучше UCB на практике.

Contextual bandits: на шаге $t$ дан контекст $c_t$, выбирается действие, видна награда. LinUCB (Li-Chu-Langford-Schapire 2010) предполагает линейную модель ожидаемой награды и применяет UCB к её confidence интервалам. EXP3 (Auer-Cesa-Bianchi-Freund-Schapire 2002) - mirror descent на simplex рук с importance-weighted estimates для adversarial bandits.

Yahoo News применяли LinUCB для ранжирования статей с 2009 года - первое production-внедрение contextual bandits в news. Spotify использует contextual bandits для recommendations: skip-сигнал как loss, контекст из истории прослушиваний и audio-features.

Bandit gradient estimation для непрерывных $K$: SPSA (Spall 1992) и one-point estimators строят несмещённую оценку градиента из одного-двух запросов loss. Цена - дисперсия растёт, скорость сходимости падает с $\sqrt{T}$ до $T^{2/3}$ или $T^{3/4}$ в зависимости от структуры.

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

• **Online setting:** decision $x_t$ перед раскрытием $f_t$, sequential данные без повторного прохода. Regret $R_T = \sum f_t(x_t) - \min_{x^*} \sum f_t(x^*)$ - метрика качества против best-in-hindsight
• **OGD достигает $O(\sqrt{T})$ regret** для convex Lipschitz losses через простую проекцию $x_{t+1} = \Pi_K(x_t - \eta_t \nabla f_t(x_t))$. Lower bound $\Omega(\sqrt{T})$ - улучшить нельзя без структуры
• **Mirror descent с entropy** на simplex даёт regret $O(\sqrt{T \log n})$ вместо $O(\sqrt{Tn})$ у OGD. AdaGrad и Adam - data-dependent варианты mirror descent в production
• **Bandit feedback:** видно только $f_t(x_t)$, не градиент. UCB и Thompson Sampling для MAB, LinUCB и EXP3 для contextual/adversarial. Yahoo News, Spotify, adaptive trials - всё это bandits в production

Связанные темы

Online Convex Optimization связывает streaming ML, learning theory и information geometry:

• Online Learning Theory: regret minimization — Regret-анализ как universal framework для online algorithms; lower bounds Abernethy-Bartlett-Rakhlin задают границы возможного
• Mirror Descent как Natural Gradient — Mirror descent с $\phi$-divergence для exponential family совпадает с natural gradient в information geometry - один и тот же алгоритм с двух сторон
• Градиентные методы (cvx-04) — OGD - online-вариант градиентного спуска; regret bound объясняет почему SGD generalize через online-to-batch conversion
• Bayesian inference (Thompson Sampling) — Thompson Sampling выбирает действие по posterior probability оптимальности - чисто Bayesian подход к exploration-exploitation

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

• OGD даёт $O(\sqrt{T})$ regret против любого adversarial противника. Что меняется, если loss-функции $f_t$ выбираются стохастически из распределения, а не противником? Какие более сильные bounds возможны?
• Multiplicative weights даёт $O(\sqrt{T \log n})$ regret на simplex с $n$ экспертами. Как этот алгоритм связан с softmax-классификацией в нейронных сетях, и почему cross-entropy loss - естественная функция для оптимизации?
• Spotify использует skip-события как loss-сигнал для contextual bandit. Какие проблемы возникают при таком определении loss (selection bias, delayed feedback, non-stationarity), и как их адресовать в online-алгоритме?

Связанные уроки

• lt-12-online-regret — Online learning theory in context of regret minimization
• ig-09-mirror-descent — Mirror descent in IG is the same algorithm
• cvx-04 — Need gradient methods foundation
• cvx-09 — Convex sets and projections
• prob-04-bayes — Thompson sampling is Bayesian
• prob-17