Мартингальные неравенства и сходимость

Regret bound в онлайн-обучении, generalization bound в PAC-learning, сходимость SGD - всё доказывается через мартингальные неравенства. Azuma-Hoeffding, неравенство Дуба, McDiarmid - три инструмента, за которыми стоят математические гарантии всего ML. Gradient clipping - не эмпирический трюк. Это восстановление условий мартингального неравенства. EXP3 алгоритм для 1000 рычагов и миллиона раундов: Regret(T) <= O(sqrt(KT log K)). Это Azuma в действии.

• **EXP3 adversarial bandit:** Regret(T) <= sqrt(KT log K) - следствие Azuma-Hoeffding для bounded мартингальных разностей
• **PAC-learning generalization:** McDiarmid с c_i=1/n даёт P(|R_hat - R| >= t) <= 2*exp(-2nt^2) - основа VC-теории
• **SGD convergence:** L2-ограниченный мартингал сходится п.н.; cosine LR schedule - инженерная реализация условий теоремы
• **Gradient clipping:** torch.nn.utils.clip_grad_norm_ восстанавливает bounded differences - условие Azuma-Hoeffding

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

• Мартингалы

Неравенство максимума Дуба: контроль всего пути

SGD обучает модель на $T$ шагах. Важно не только финальное значение loss, но и максимальный всплеск по всей траектории - именно он определяет, «взорвётся» ли обучение. Неравенство максимума Дуба контролирует $\sup_{k \leq n} |X_k|$ через $\mathbb{E}[|X_n|^p]$ - весь путь через конечную точку.

**Неравенство максимума Дуба ($L^p$-версия):** Для мартингала $(X_n)$ и $p > 1$: $$\mathbb{E}\left[\max_{0 \leq k \leq n} |X_k|^p\right] \leq \left(\frac{p}{p-1}\right)^p \mathbb{E}[|X_n|^p]$$ **При $p=2$:** $\mathbb{E}[\max_{k \leq n} X_k^2] \leq 4 \cdot \mathbb{E}[X_n^2]$ **Слабая форма (субмартингал $X_n \geq 0$):** $$\mathbb{P}\left(\max_{k \leq n} X_k \geq \lambda\right) \leq \frac{\mathbb{E}[X_n]}{\lambda}$$ Константа 4 при $p=2$ неулучшаема. При $p \to \infty$ константа стремится к $e \approx 2.718$.

Ключевое отличие от неравенства Маркова: Марков применяется к $|X_n|$ и контролирует только конечную точку. Дуб использует мартингальную структуру и теорему об опциональной остановке, чтобы контролировать $\max_{k \leq n} |X_k|$ - весь путь. Для доказательства сходимости SGD нужен именно Дуб: нужно, чтобы процесс не «улетал» в процессе обучения.

Azuma-Hoeffding: sub-Gaussian хвосты для bounded мартингалов

EXP3 - алгоритм для $K$-руких бандитов в adversarial setting. Его regret bound $\text{Regret}(T) \leq \sqrt{KT \log K}$ - это следствие неравенства Azuma-Hoeffding. 1000 рычагов, $10^6$ раундов: гарантированный regret не хуже $\approx 10^5$. Математика гарантирует, что алгоритм никогда не будет хуже лучшего фиксированного действия более чем на 10%.

**Неравенство Azuma-Hoeffding:** Пусть $(X_n)$ - мартингал с ограниченными разностями: $|X_k - X_{k-1}| \leq c_k$ п.н. Тогда: $$\mathbb{P}(|X_n - X_0| \geq t) \leq 2 \exp\left(-\frac{t^2}{2 \sum_{k=1}^n c_k^2}\right)$$ **При $c_k = c$ (равные ограничения):** $$\mathbb{P}(|X_n - X_0| \geq t) \leq 2 \exp\left(-\frac{t^2}{2nc^2}\right)$$ **Online learning regret:** Для EXP3 выигрыш на каждом раунде - мартингальная разность, ограниченная 1. Azuma даёт $\text{Regret}(T) \leq O(\sqrt{T \log K})$ с высокой вероятностью.

Неравенство имеет sub-Gaussian форму: хвосты убывают как $\exp(-t^2 / \sigma^2)$. Это оптимальная скорость для bounded distributions. Связь с Гауссовским случаем не случайна: ограниченные мартингальные разности ведут себя «как» ограниченные гауссовские приращения с точки зрения хвостов.

**Gradient clipping - не эмпирический трюк.** Azuma-Hoeffding требует ограниченных разностей $|X_k - X_{k-1}| \leq c_k$. SGD с неограниченными градиентами - не мартингал с bounded differences. Gradient clipping (`torch.nn.utils.clip_grad_norm_`) восстанавливает это условие. Без clipping мартингальные гарантии сходимости не применимы.

Неравенство McDiarmid: generalization bounds в ML

PAC-learning (Probably Approximately Correct): сколько примеров нужно, чтобы гарантировать обобщение? Этот вопрос стоит за VC-теорией и всем статистическим обучением. Ответ дают концентрационные неравенства для функций - неравенство McDiarmid в первую очередь.

**Неравенство McDiarmid (bounded differences для функций):** Пусть $f(X_1, \ldots, X_n)$ - функция независимых случайных величин, такая что замена любого $X_i$ на $X_i'$ меняет $f$ не более чем на $c_i$: $$\sup_{x_i, x_i'} |f(\ldots, x_i, \ldots) - f(\ldots, x_i', \ldots)| \leq c_i$$ Тогда: $$\mathbb{P}(f - \mathbb{E}[f] \geq t) \leq \exp\left(-\frac{2t^2}{\sum c_i^2}\right)$$ **Связь с Azuma:** McDiarmid - это Azuma-Hoeffding для функций независимых аргументов, а не для самой последовательности.

Generalization bound для эмпирического риска: функция $f(S) = \hat{R}(h, S) = \frac{1}{n} \sum_{i=1}^n \ell(h(x_i), y_i)$ (эмпирический риск на выборке $S = (x_1,y_1), \ldots, (x_n, y_n)$). Замена одного примера $(x_i, y_i)$ на $(x_i', y_i')$ меняет $f$ не более чем на $c_i = \frac{1}{n}$ (при ограниченной функции потерь $\ell \in [0,1]$). McDiarmid даёт: $$\mathbb{P}(|\hat{R}(h,S) - R(h)| \geq t) \leq 2\exp(-2nt^2)$$ Это и есть «обобщение с $n$ примерами».

McDiarmid покрывает не только эмпирический риск. Он применяется везде, где функция имеет bounded sensitivity: онлайн-алгоритмы (каждый новый пример меняет оценку на $O(1/n)$), аугментация данных (каждое изменение в батче bounded), randomized algorithms (замена seed меняет выход на bounded amount).

L2-сходимость мартингалов и SGD

SGD сходится - но в каком смысле? Параметры случайно блуждают даже у минимума из-за мини-батч шума. Доказательство сходимости требует мартингальной теории. Ключевой факт: $L^2$-ограниченный мартингал сходится почти наверное.

**Теорема ($L^2$-сходимость мартингалов):** Если $(X_n)$ - мартингал и $\sup_n \mathbb{E}[X_n^2] < \infty$, то существует $X_\infty$ такое, что $X_n \to X_\infty$ почти наверное и в $L^2$. **Следствие для SGD:** при условиях: 1. $\sum_n \eta_n = \infty$ (шаги суммируются до $\infty$) 2. $\sum_n \eta_n^2 < \infty$ (шаги достаточно убывают, например $\eta_n = 1/n$) 3. Ограниченная дисперсия градиента ...норма отклонения параметров от траектории сходится почти наверное к нулю. Cosine LR schedule и warmup - это инженерный способ обеспечить эти условия на конечном горизонте.

Важный нюанс: $L^2$-ограниченность мартингала - не то же, что ограниченность траектории. Симметричное случайное блуждание $S_n = \sum_{k=1}^n \xi_k$ - мартингал, но $\mathbb{E}[S_n^2] = n \to \infty$. Условие $\sup_n \mathbb{E}[X_n^2] < \infty$ требует, чтобы «разброс» не рос со временем. Убывающий learning rate именно это и обеспечивает.

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

• **Неравенство Дуба:** $\mathbb{E}[\max_{k \leq n} X_k^2] \leq 4 \mathbb{E}[X_n^2]$ - контролирует весь путь через конечную точку; константа 4 неулучшаема
• **Azuma-Hoeffding:** bounded differences $\Rightarrow$ sub-Gaussian хвосты $2\exp(-t^2/2nc^2)$; основа regret bounds в online learning (EXP3, UCB)
• **McDiarmid:** функция от независимых переменных с bounded sensitivity концентрируется - основа generalization bounds в PAC-learning
• **L2-сходимость:** $\sup_n \mathbb{E}[X_n^2] < \infty$ гарантирует п.н. сходимость; для SGD - условие на LR schedule
• **Gradient clipping:** восстанавливает bounded differences для неограниченных градиентов - необходимое условие применимости мартингальных неравенств

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

Мартингальные неравенства - мост между теорией и гарантиями ML:

• Мартингалы — Определение, опциональная остановка - фундамент для неравенств
• Броуновское движение — Функциональный предел нормированных мартингалов - непрерывный аналог
• Концентрационные неравенства — Azuma и McDiarmid как специальные случаи общей теории
• PAC-learning — Generalization bounds через McDiarmid - математическая база теории обучения

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

• Почему gradient clipping необходим для применения мартингальных гарантий сходимости SGD?
• EXP3 имеет regret O(sqrt(KT log K)). Как изменится bound если K=1 (один рычаг)? Что это означает?
• McDiarmid требует независимости X_i. Как обобщить на коррелированные данные (временные ряды)?

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

• sp-04 — Определение мартингала, теорема Дуба об опциональной остановке
• prob-26-malliavin — PAC-learning generalization bounds строятся через мартингальные аргументы
• sp-07 — Броуновское движение - функциональный предел нормированных мартингалов
• prob-16-martingales