Теория вероятностей

Сходимость случайных величин

Выборочное среднее $\bar X_n$ сходится к $\mu$ - но в каком смысле? Сходимость по вероятности, почти наверное, в $L^2$ и по распределению - четыре разных понятия с разными импликациями. Неправильный выбор может привести к некорректным статистическим выводам.

SGD сходится к критической точке 'почти наверное' при убывающих шагах - именно в смысле сходимости п.н. Это строже, чем сходимость по вероятности, и позволяет утверждать, что одна траектория алгоритма сходится, а не только что большинство траекторий.
ЦПТ утверждает сходимость по распределению: $(\bar X_n - \mu)/(\sigma/\sqrt{n}) \xrightarrow{d} \mathcal{N}(0,1)$. Это основа доверительных интервалов - но не означает сходимость самого $\bar X_n$ к нормальной случайной величине.
Bootstrap оценивает дисперсию статистик через сходимость по распределению: бутстраповское распределение $\hat\theta^* - \hat\theta$ аппроксимирует $\hat\theta - \theta$. Это обосновано именно сходимостью по распределению.

Цели урока

Различать четыре типа сходимости: п.н., по вероятности, в $L^p$ и по распределению
Строить контрпримеры, показывающие неэквивалентность типов сходимости
Применять ЦПТ и теорему непрерывного отображения для анализа статистик

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

Случайные величины и их распределения
Математическое ожидание и дисперсия
Интеграл Лебега и измеримые функции

Иерархия типов сходимости

Пусть $X_n, X$ - случайные величины на одном вероятностном пространстве. Сходимость почти наверное: $P(\lim_n X_n = X) = 1$. Сходимость по вероятности: $P(|X_n - X| > \varepsilon) \to 0$ для любого $\varepsilon > 0$. Сходимость в $L^p$: $\mathbb{E}[|X_n - X|^p] \to 0$. Сходимость по распределению: $F_{X_n}(x) \to F_X(x)$ в точках непрерывности $F_X$. Импликации: п.н. $\Rightarrow$ по вер., $L^p \Rightarrow$ по вер., по вер. $\Rightarrow$ по распределению; обратное неверно.

Теорема Портманто (о сходимости по распределению): $X_n \xrightarrow{d} X$ равносильно: $\mathbb{E}[f(X_n)] \to \mathbb{E}[f(X)]$ для всех ограниченных непрерывных $f$. Это определение не требует общего вероятностного пространства и обобщается на метрические пространства - основа слабой сходимости мер.

Сходимость по распределению не влечёт сходимость ожиданий. Классический пример: $X_n = n \cdot \mathbf{1}_{[0,1/n]}$ на $[0,1]$. Тогда $X_n \xrightarrow{d} 0$, но $\mathbb{E}[X_n] = 1 \not\to 0 = \mathbb{E}[0]$. Равномерная интегрируемость - достаточное условие для перехода к пределу под знаком ожидания.

Центральная предельная теорема и её вариации

ЦПТ Линдеберга-Леви: если $X_i$ i.i.d. с $\mu = \mathbb{E}[X_i]$, $\sigma^2 = \mathrm{Var}(X_i) < \infty$, то $\sqrt{n}(\bar X_n - \mu)/\sigma \xrightarrow{d} \mathcal{N}(0,1)$. Скорость сходимости: теорема Берри-Эссеена $\sup_x |F_n(x) - \Phi(x)| \leq C \mathbb{E}[|X|^3]/(\sigma^3 \sqrt{n})$. Дельта-метод: если $\sqrt{n}(\bar X_n - \mu) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$ и $g$ дифференцируема в $\mu$, то $\sqrt{n}(g(\bar X_n) - g(\mu)) \xrightarrow{d} \mathcal{N}(0, [g'(\mu)]^2 \sigma^2)$.

Сходимость по вероятности и закон больших чисел

ChatGPT-4 training (OpenAI, 2023, $100M+ compute) использует SGD convergence theory: 10¹³ токенов через градиентный спуск с теорией почти-наверное сходимости. При обучении нейросети loss на 1 000 000 шагах SGD не просто «уменьшается» - он сходится в конкретном математическом смысле. Тип сходимости определяет гарантии алгоритма: сходимость по вероятности означает, что вероятность большого отклонения стремится к нулю, но «катастрофические» шаги всё ещё возможны. Именно это наблюдается в SGD с уменьшающимся learning rate.

Последовательность случайных величин Xₙ сходится по вероятности к X, если для любого ε > 0 вероятность отклонения |Xₙ − X| > ε стремится к нулю при n → ∞. Это самый слабый из практически значимых режимов сходимости.

В ML сходимость по вероятности гарантирует: при достаточно большой выборке empirical risk сходится к expected risk (закон больших чисел). Это основа PAC-learning (Probably Approximately Correct): с вероятностью ≥ 1−δ отклонение ≤ ε при n ≥ O(log(1/δ)/ε²) примерах.

Последовательность Xₙ ~ Uniform(0, 1/n). Докажите, что Xₙ → 0 по вероятности.

Ответ следует непосредственно из определения и свойств рассматриваемого математического объекта.

Сходимость почти наверное и сильный ЗБЧ

Сходимость почти наверное (п.н., almost sure, a.s.) строже сходимости по вероятности. Если gradient descent сходится почти наверное - это означает: для почти каждой реализации случайности (выбора mini-batches) путь оптимизации в конечном счёте достигает цели. Множество «неудачных» реализаций имеет вероятность ноль.

Различие между сходимостью по вероятности и почти наверное критично в анализе онлайн-алгоритмов. Сходимость SGD почти наверное (при определённых условиях на learning rate и градиент) означает, что конкретный запуск алгоритма с вероятностью 1 достигнет стационарной точки - более сильная гарантия, чем «в среднем».

Последовательность Xₙ сходится к X по вероятности. Означает ли это автоматически сходимость почти наверное? Приведите контрпример.

Различные виды сходимости случайных величин образуют иерархию: п.н. → по вероятности → по распределению.

Центральная предельная теорема и сходимость по распределению

Градиентный шум в SGD с mini-batch размера B усредняется по B примерам. При B → ∞ центральная предельная теорема (ЦПТ) гарантирует: распределение усреднённого градиента сходится к гауссовскому независимо от формы распределения отдельных градиентов. Это обосновывает предположение о гауссовском шуме в теоретическом анализе SGD.

Теорема Слуцкого: если Xₙ → X по распределению и Yₙ → c по вероятности (c - константа), то XₙYₙ → cX и Xₙ + Yₙ → X + c по распределению. Это позволяет строить асимптотические доверительные интервалы с оценённой дисперсией - основа статистики для ML: A/B тесты, bootstrap confidence intervals.

При mini-batch SGD с batch_size=64 дисперсия одного градиента равна σ²=16. Какова дисперсия усреднённого градиента, и к какому распределению он сходится при больших batch?

Градиент указывает направление наибольшего роста функции и является вектором частных производных.

Контрпример: по вер. без п.н.

На $[0,1]$ с мерой Лебега: $X_n = \mathbf{1}_{[k/2^j, (k+1)/2^j]}$ где $n = 2^j + k$, $0 \leq k < 2^j$. Последовательность: $\mathbf{1}_{[0,1]}$, $\mathbf{1}_{[0,1/2]}$, $\mathbf{1}_{[1/2,1]}$, $\mathbf{1}_{[0,1/4]}$, $\ldots$ Тогда $P(|X_n| > \varepsilon) = 2^{-j} \to 0$ (сходимость по вер.), но для каждого $x \in [0,1]$ последовательность $X_n(x)$ не сходится (бегущая волна). Значит, п.н. сходимости нет.

Итоги

Четыре типа сходимости образуют иерархию: п.н.
и $L^p$ строже сходимости по вероятности, которая строже сходимости по распределению.
ЦПТ утверждает сходимость по распределению нормированного среднего.
Дельта-метод распространяет ЦПТ на гладкие функции статистик.

Связь с другими темами

Концентрация меры (prob-22) усиливает ЦПТ: вместо сходимости по распределению получают экспоненциальные хвостовые оценки. PAC-обучение (prob-26) использует сходимость по вероятности для доказательства обобщения. Большие отклонения - теория, изучающая скорость убывания $P(|\bar X_n - \mu| > \varepsilon)$ экспоненциально в $n$.

Prob 22 — связан
Prob 26 — связан

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

Дельта-метод утверждает, что $\sqrt{n}(\log \bar X_n - \log \mu) \xrightarrow{d} \mathcal{N}(0, \sigma^2/\mu^2)$ при $\mu > 0$. Как это использовать для построения доверительного интервала на $\log\mu$ (и затем $\mu$) с лучшим покрытием, чем прямой ДИ для $\mu$?

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