Uniform Convergence: единый bound на всё гипотезное пространство

ERM выбирает гипотезу minimizing training error на конкретной выборке. Та же выборка использовалась и для оценки качества - может оказаться так, что для самого переобученного решения training error равен нулю, а true error - 50%. Pointwise concentration (LLN) гарантирует совпадение $L_S(h) \to L_D(h)$ для каждого фиксированного $h$, но fixed $h$ не равен $\hat{h}$ - последний выбирается ПО данным. Uniform convergence снимает эту проблему одним движением: с высокой вероятностью $L_S$ близок к $L_D$ ОДНОВРЕМЕННО для всех $h \in H$. Тогда выбор $\hat{h}$ по $L_S$ автоматически даёт хорошее $L_D$ - именно это и делает ERM honest learner.

• **SVM regularization:** ограничение $\|w\|_2 \leq B$ сужает класс гипотез ровно настолько, чтобы UC bound стал нетривиальным. Без ограничения - infinite VC, никаких гарантий обобщения
• **Neural network capacity control:** weight decay, dropout, early stopping - все эти техники неявно работают как сужение эффективного класса гипотез до уровня, на котором UC применима
• **Modern paradox:** GPT-4 имеет $\sim 10^{12}$ параметров и vacuous classical UC bounds, но обобщается лучше любых классических моделей. Открытый вопрос: что ЗАМЕНЯЕТ UC в этом режиме (см. lt-13, lt-14)

Зачем нужен uniform convergence

ERM выбирает $\hat{h}$ minimizing training error на конкретной выборке. Но та же выборка использовалась для оценки качества - может оказаться так, что для самого переобученного $\hat{h}$ training error равен нулю, а true error - 50%. Pointwise concentration (LLN) гарантирует совпадение $L_S(h) \to L_D(h)$ для каждого фиксированного $h$, но fixed $h$ не равен $\hat{h}$ - последний выбирается ПО данным. Uniform convergence снимает эту проблему одним движением: с высокой вероятностью $L_S$ близок к $L_D$ ОДНОВРЕМЕННО для всех $h \in H$. Тогда выбор $\hat{h}$ по $L_S$ автоматически даёт хорошее $L_D$ - именно это и делает ERM honest learner.

Pointwise convergence $L_S(h) \to L_D(h)$ - следствие закона больших чисел, выполняется покоординатно для каждого $h$. Uniform convergence - радикально более сильное утверждение: $\sup_{h \in H} |L_S(h) - L_D(h)| \to 0$. Различие принципиально, когда $|H|$ велико или бесконечно.

**Контрпример pointwise vs uniform.** Пусть $H = \{h_S : S \subseteq X, |S| < \infty\}$ - класс индикаторов конечных множеств. Для любого фиксированного $h_S$ при непрерывном $D$ верно $L_D(h_S) = L_S(h_S) = 0$ (множество меры ноль). Но $\sup_h |L_S(h) - L_D(h)| = 1$ всегда - можно выбрать $h$ равный единице ровно на обучающей выборке. Pointwise convergence есть, uniform - нет. Класс не learnable несмотря на тривиальную pointwise сходимость. **ML applications inline:** - **SVM regularization:** ограничение $\|w\|_2 \leq B$ сужает класс гипотез ровно настолько, чтобы UC bound стал нетривиальным - **Neural network capacity control:** weight decay, dropout, early stopping - все эти техники неявно работают как сужение эффективного класса гипотез - **Modern paradox:** GPT-4 имеет $\sim 10^{12}$ параметров и vacuous classical UC bounds, но обобщается лучше любых классических моделей

Формальное определение и фундаментальная теорема

Класс $H$ обладает свойством uniform convergence относительно $D$, если эмпирический риск равномерно концентрируется вокруг истинного: $$\Pr_{S \sim D^n}\left[\sup_{h \in H} |L_S(h) - L_D(h)| > \epsilon\right] \to 0 \text{ при } n \to \infty.$$ Equivalent formulation через $\epsilon$-representativeness: training set $S$ называется $\epsilon$-representative для $H$, если $|L_S(h) - L_D(h)| < \epsilon$ для всех $h \in H$ одновременно. UC = выборка $\epsilon$-representative с большой вероятностью.

**Fundamental Theorem of Statistical Learning (Vapnik-Chervonenkis 1971, Blumer-Ehrenfeucht-Haussler-Warmuth 1989).** Для класса бинарных гипотез $H$ следующие утверждения эквивалентны: 1. $H$ имеет свойство uniform convergence 2. ERM является PAC-learner для $H$ 3. $H$ является agnostic PAC learnable 4. $\text{VCdim}(H) < \infty$ То есть конечная VC-размерность - НЕОБХОДИМОЕ И ДОСТАТОЧНОЕ условие learnability через ERM. **Sample complexity, выводимая из uniform convergence:** $$m_H(\epsilon, \delta) \leq O\!\left(\frac{\text{VCdim}(H) \log(1/\epsilon) + \log(1/\delta)}{\epsilon^2}\right).$$ Для realizable case (есть гипотеза с нулевым риском) показатель $1/\epsilon^2$ улучшается до $1/\epsilon$. Для agnostic case оставляется $1/\epsilon^2$ - это теоретический предел.

**ML hook: VC dimension neural network = $\Theta(W \log W)$ (Bartlett-Maiorov-Meir 1998), где $W$ - число параметров.** Для GPT-4 с $W \sim 10^{12}$: классический UC bound даёт sample complexity $\sim 10^{13}$ примеров для значимой точности - больше всего интернета. Bound верен математически, но vacuous практически. Почему GPT обобщается на куда меньших данных - открытый вопрос, обсуждаемый в lt-13 и lt-14.

Rademacher complexity: tight UC bound

VC-bound для UC distribution-free и часто слишком пессимистичен. Rademacher complexity (lt-06) даёт data-dependent версию того же неравенства - намного более тугую на практике. $$\hat{R}_S(H) = \mathbb{E}_\sigma\!\left[\sup_{h \in H} \frac{1}{n}\sum_{i=1}^n \sigma_i h(x_i)\right], \quad \sigma_i \in \{-1, +1\} \text{ i.i.d.}$$

**Rademacher uniform convergence bound.** Для loss $\ell$ ограниченного $[0, 1]$ с вероятностью не менее $1 - \delta$ по $S \sim D^n$ для всех $h \in H$ одновременно: $$|L_S(h) - L_D(h)| \leq 2\hat{R}_S(H) + 3\sqrt{\frac{\log(2/\delta)}{2n}}.$$ Ключевая особенность: $\hat{R}_S(H)$ оценивается прямо по обучающей выборке - bound вычислим эмпирически без знания истинного распределения. **Преимущества над VC-bound:** - **Data-dependent:** bound учитывает структуру конкретной выборки $S$, а не худший случай по всем возможным $D$ - **Computable:** $\hat{R}_S(H)$ оценивается симуляцией - случайно метить $S$ знаками $\sigma$ и обучать модель на этой случайной разметке - **Tighter:** для kernel SVM с margin $\gamma$ Rademacher даёт bound $O(BR/(\gamma\sqrt{n}))$ без зависимости от размерности feature space - VC-bound в этой ситуации vacuous (бесконечная VC) - **Compositional:** Rademacher хорошо ведёт себя при композициях (Lipschitz-функции, выпуклые комбинации), что нужно для анализа нейросетей

**ML hook: PyTorch Lightning's effective batch size.** Калибровка batch size при distributed training частично опирается на Rademacher-style анализ: эффективный размер батча должен быть таким, чтобы concentration term $\sqrt{\log(1/\delta)/n}$ оставался малым относительно $\hat{R}_S$. На практике это переводится в эвристики типа linear scaling rule (Goyal 2017): $\eta \propto B$ для $B \leq 8192$, дальше нужны warmup-стратегии.

Когда UC не работает: современный фронт

Классическая UC-теория опирается на три предположения, каждое из которых нарушается в современном ML: - **Конечная VC-размерность.** Deep networks с миллиардами параметров формально имеют конечную, но огромную VC-dim. Bound $\sqrt{\text{VCdim}/n}$ становится больше единицы - vacuous. - **Bounded loss.** Cross-entropy на rare tokens (LLM training) даёт heavy-tailed losses: $-\log p$ при $p \to 0$ неограничен. Стандартные concentration inequalities (Hoeffding, McDiarmid) ломаются. - **i.i.d. выборка.** Distribution shift между training и deployment, online learning, RLHF - всё это off-i.i.d. сценарии. - **Algorithm-independence.** Классическая UC рассматривает весь класс $H$. Но SGD не пробегает весь класс - implicit bias оптимизатора сильно сужает достижимые гипотезы.

**Современные альтернативы UC.** - **PAC-Bayes (lt-09):** bound через распределение над гипотезами $Q$ и его расхождение с приором $P$. Дзугатэ-Рой 2017 получил первый non-vacuous bound для CNN на MNIST: $0.165$ при реальной ошибке $0.013$ - **Information-theoretic bounds (lt-14):** generalization gap ограничивается mutual information $I(S; \hat{h})$. Xu-Raginsky 2017 показали $\mathbb{E}[\text{gap}] \leq \sqrt{2\sigma^2 I(S; \hat{h})/n}$ - bound зависит от того, СКОЛЬКО информации о выборке закодировано в гипотезе - **Implicit regularization analysis:** Soudry-Hoffer-Srebro 2018 доказали, что SGD на linearly separable data сходится к max-margin solution - неявное сужение класса до min-norm гипотез - **Neural Tangent Kernel:** в режиме бесконечной ширины обучение сети сводится к kernel method с известным RKHS, для которого классическая теория даёт нетривиальные гарантии

**ML hook: GPT-4 paradox.** Классический UC bound для GPT-4 vacuous на много порядков. Тем не менее модель демонстрирует zero-shot generalization на задачи, не виденные при обучении. Гипотезы объяснения: feature learning (representations обобщаются лучше класса целиком), implicit SGD bias (оптимизатор находит solution с малой effective capacity внутри огромного класса), sparse activations (реальная вычислительная сложность сети много меньше номинальной capacity), data overlap (train distribution настолько богата, что покрывает большую часть test). Каждая - активная research direction. Единого ответа пока нет.

Что забрать из урока

• **Uniform convergence:** $\sup_{h \in H} |L_S(h) - L_D(h)| \to 0$ - принципиально сильнее pointwise concentration; именно UC делает ERM honest learner, выбирающим гипотезу не вслепую
• **Fundamental theorem of statistical learning:** для бинарных классов UC $\Leftrightarrow$ ERM is PAC learner $\Leftrightarrow$ $\text{VCdim}(H) < \infty$. Конечная VC - необходимое и достаточное условие learnability
• **Sample complexity:** $m(\epsilon, \delta) \leq O(\text{VCdim}/\epsilon^2 + \log(1/\delta)/\epsilon^2)$ для agnostic case; Rademacher даёт data-dependent уточнение через $2\hat{R}_S(H) + 3\sqrt{\log(2/\delta)/(2n)}$
• **Когда UC ломается:** overparameterized сети (vacuous bounds), heavy-tailed losses, distribution shift, implicit algorithmic bias. Замены - PAC-Bayes (lt-09), information-theoretic bounds (lt-14), implicit regularization analysis

Куда дальше

Uniform convergence - центральная теорема классической теории обобщения. Куда она ведёт:

• VC dimension — VC-размерность входит в UC bound как главный множитель сложности; конечная VC - необходимое условие UC
• Rademacher complexity — Data-dependent уточнение UC bound; единственный нетривиальный bound для kernel methods с бесконечной VC
• Information-theoretic bounds — Современная замена UC через mutual information $I(S; \hat{h})$ - даёт нетривиальные гарантии там, где UC vacuous

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

• Класс из одной фиксированной гипотезы $H = \{h_0\}$ имеет $\text{VCdim} = 0$ и прямолинейно удовлетворяет UC. Почему такой класс не интересен с практической точки зрения, и как это связано с trade-off между approximation error и estimation error?
• Симуляция Empirical Rademacher для нейросети требует обучения модели на случайных метках - именно то, что делал Zhang et al. 2017. Почему это эмпирически показывает, что классический Rademacher bound для современных архитектур vacuous, и какие альтернативы (PAC-Bayes, info-theoretic) обходят эту проблему?
• Fundamental theorem утверждает эквивалентность UC и PAC learnability через ERM. Существуют ли learnable классы, для которых ERM проваливается, но другой алгоритм работает? Подсказка: это связано с разницей между proper и improper learning, и с тем, что для some classes (например, k-DNF) computational complexity ERM делает его неприменимым на практике.

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

• lt-04-vc-dimension — VC bounds the UC sample complexity
• lt-06-rademacher — Tighter UC bound via Rademacher
• lt-09-pac-bayes — Bayesian relaxation of UC
• lt-13-deep-generalization — UC fails for deep nets - what replaces it
• lt-14-info-bounds — Information-theoretic UC alternatives
• stat-01-sampling