Rademacher complexity: data-dependent сложность

VC-теория видит худший случай. Rademacher видит конкретные данные, конкретную архитектуру, конкретный шум. 2002 год. Bartlett и Mendelson переписывают теорию обобщения одним вопросом: насколько хорошо класс гипотез подгоняется под случайные знаки на этих самых обучающих точках? Если плохо - класс прост на этих данных, неважно сколько у него VC-измерений.

• **SVM с RBF-ядром:** VC-dim бесконечна, но margin bound через Rademacher даёт непустую (non-vacuous) гарантию - именно поэтому soft-margin SVM работает на практике
• **Zhang et al. 2017 'Rethinking generalization':** ResNet-50 идеально запоминает случайные метки на CIFAR-10 (zero training error). Rademacher complexity класса при таком обучении максимальна - но на реальных метках сеть обобщается. Этот разрыв обнажает дыру в классических bounds
• **Empirical Rademacher оценивается за один прогон:** случайно пометить выборку знаками $\pm 1$, обучить модель на этой случайной разметке, померить тренировочную точность - готово
• **Norm-based bounds для нейросетей** (Bartlett 2017, Neyshabur 2018) выражают Rademacher через Frobenius-норму матриц весов - первая попытка получить непустые bounds для глубоких сетей

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

• VC-размерность и shattering как distribution-free мера сложности
• Эмпирический риск $\hat{R}(h) = \frac{1}{m}\sum_i \mathbf{1}[h(x_i) \neq y_i]$
• Hoeffding-неравенство для концентрации среднего

• VC dimension: мера сложности гипотезного класса
• Growth function и лемма Сауэра

Empirical Rademacher: насколько H подгоняется под шум

Empirical Rademacher: насколько H подгоняется под шум

Дана выборка $S = (x_1, \ldots, x_m)$. Берётся $m$ независимых случайных знаков $\sigma_1, \ldots, \sigma_m \in \{-1, +1\}$, каждый с вероятностью $1/2$. Эти знаки - шум, не имеющий ничего общего с истинными метками. Вопрос: насколько хорошо класс $\mathcal{H}$ умеет коррелировать со случайными знаками на этой конкретной выборке?

Внутри супремум: класс ищет гипотезу, максимально согласованную со случайными знаками. Снаружи матожидание: усредняется по всем способам выбрать $\sigma$. Результат - число от $0$ до $1$. Ноль означает, что класс вообще не умеет подстраиваться под шум на $S$. Единица - что для любого случайного шума найдётся гипотеза, идеально его реализующая.

**Ключевая инверсия мышления.** VC спрашивает: "какой максимальный шум класс способен выразить теоретически?" Rademacher спрашивает: "какой шум он реально выражает на этих $m$ точках?". Первое - комбинаторика, второе - измеряемая величина. Класс с $\text{VCdim} = \infty$ может иметь $\hat{\mathfrak{R}}_S(\mathcal{H}) \to 0$ на структурированных данных - это и есть data-dependence.

Тот же класс линейных классификаторов даёт разный $\hat{\mathfrak{R}}_S$ на разных данных - это и есть точность, которой VC-теория лишена по построению. На сжатых данных линейный класс простой, на разреженных - сложный.

Expected Rademacher и generalization bound

Expected Rademacher и generalization bound

Empirical Rademacher $\hat{\mathfrak{R}}_S(\mathcal{H})$ зависит от конкретной выборки. Берётся матожидание по выборке - получается **expected Rademacher complexity**:

Эта величина зависит от распределения $\mathcal{D}$ - в этом смысл слова "data-dependent". Один и тот же класс на распределении кошек MNIST и на распределении гауссова шума будет иметь разный $\mathfrak{R}_m$.

**Теорема Bartlett-Mendelson 2002.** Для класса $\mathcal{H}$ функций со значениями в $[0, 1]$ и любого $\delta \in (0, 1)$ с вероятностью не менее $1 - \delta$ по выборке $S$ размера $m$ для всех $h \in \mathcal{H}$: $$R(h) \leq \hat{R}(h) + 2\mathfrak{R}_m(\mathcal{H}) + \sqrt{\frac{\log(1/\delta)}{2m}}$$ В data-dependent варианте $\mathfrak{R}_m$ заменяется на $\hat{\mathfrak{R}}_S$ - оценивается прямо по обучающей выборке.

Структура bound та же, что у VC-варианта: эмпирический риск плюс штраф за сложность плюс concentration term. Принципиальное отличие - штраф $2\mathfrak{R}_m(\mathcal{H})$ зависит от $\mathcal{D}$. Для распределений, на которых класс "реально прост", штраф маленький, даже если VC-dim бесконечна.

**Margin bounds для SVM (Bartlett-Mendelson 2002, теорема 21).** Пусть $\mathcal{H}$ - класс линейных классификаторов с $\|w\|_2 \leq B$ на данных $\|x\|_2 \leq R$. Тогда $\mathfrak{R}_m(\mathcal{H}) \leq BR/\sqrt{m}$. Подставляя в общий bound, получается классический margin bound: ошибка $\leq$ доля точек с margin меньше $\gamma$ + $O(BR/(\gamma\sqrt{m}))$. **VC-измерение в эту формулу не входит вообще** - что критично для kernel SVM, где VC бесконечна.

Rademacher для нейросетей: vacuous bounds и переосмысление

Rademacher для нейросетей: vacuous bounds и переосмысление

Bartlett 1998 даёт первый Rademacher-bound для нейросетей через произведение Frobenius-норм матриц весов: $\mathfrak{R}_m \leq \frac{c}{\sqrt{m}} \prod_{l=1}^{L} \|W_l\|_F$. Для современных архитектур произведение норм огромно - bound становится больше единицы. Bound верен, но vacuous: говорит "ошибка не больше 100%", что бесполезно.

Neyshabur et al. 2018 уточняют через спектральные нормы и path norms - bound становится плотнее, но всё ещё на порядки больше эмпирической ошибки. Дзугатэ-Рой 2017 пробуют PAC-Bayes - первый непустой bound для CNN на MNIST: предсказание $0.165$ при реальной ошибке $0.013$. Прорыв и одновременно граница того, что пока умеет теория.

Поэтому в современных работах Rademacher complexity всё чаще заменяется на margin-Rademacher (Bartlett 2017), data-dependent norm bounds или PAC-Bayesian аналоги. Все они - производные той же идеи: измерять сложность через корреляцию с шумом, но привязывать измерение к чему-то более узкому, чем весь класс.

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

• **Empirical Rademacher** $\hat{\mathfrak{R}}_S(\mathcal{H}) = \mathbb{E}_\sigma[\sup_h \frac{1}{m}\sum \sigma_i h(x_i)]$ - насколько класс коррелирует со случайными знаками на конкретной выборке
• **Expected Rademacher** $\mathfrak{R}_m(\mathcal{H}) = \mathbb{E}_S[\hat{\mathfrak{R}}_S(\mathcal{H})]$ - усреднение по распределению $\mathcal{D}$, главное отличие от distribution-free VC
• **Generalization bound (Bartlett-Mendelson 2002):** $R(h) \leq \hat{R}(h) + 2\mathfrak{R}_m(\mathcal{H}) + \sqrt{\log(1/\delta)/(2m)}$
• **Margin bounds для SVM:** $\mathfrak{R}_m \leq BR/\sqrt{m}$ для $\|w\| \leq B$, $\|x\| \leq R$ - VC в формулу не входит, что критично для kernel methods
• **Нейросети:** norm-based bounds через Frobenius-нормы дают vacuous результат для современных архитектур; Zhang et al. 2017 показал что класс идеально подгоняется под случайные метки
• **Современный фронт:** algorithm-dependent bounds, PAC-Bayes, margin-Rademacher - попытки сузить класс с помощью данных или процесса оптимизации

Что дальше

Rademacher complexity - центральная мера сложности в современной теории обобщения:

• Uniform convergence — Главный bound в теории Вапника-Червоненкиса выражается напрямую через $\mathfrak{R}_m(\mathcal{H})$
• Margin bounds — SVM, boosting и нейросети анализируются через margin-Rademacher complexity
• PAC-Bayes — Альтернативная теория, дающая плотные bounds через распределения над гипотезами
• Deep generalization — Объяснение почему классические Rademacher-bounds vacuous для overparameterized сетей
• Concentration inequalities — McDiarmid и Hoeffding - технический инструментарий для перехода Rademacher → generalization

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

• Класс линейных классификаторов с $\|w\| \leq 1$ имеет $\mathfrak{R}_m \sim 1/\sqrt{m}$ независимо от размерности $d$. VC-bound даёт $O(\sqrt{d/m})$. Почему data-dependent оценка не страдает от проклятия размерности, а distribution-free страдает?
• Empirical Rademacher оценивается через симуляцию: случайно метить выборку $\pm 1$, обучать модель, мерить training accuracy. Какие проблемы возникают при оценке $\hat{\mathfrak{R}}_S$ для сложных классов вроде нейросетей и как это связано с экспериментом Zhang et al. 2017?
• Margin bound для kernel SVM содержит $BR/\sqrt{m}$ без VC-dim. Почему именно это позволяет kernel methods с бесконечной VC-dim вообще работать в реальных приложениях?

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

• lt-04-vc-dimension — VC-dim - distribution-free предшественник; Rademacher уточняет его data-dependent оценкой
• lt-05-growth-sauer — Growth function через лемму Сауэра - комбинаторный потолок, Rademacher даёт более тонкую оценку
• lt-07-uniform-convergence — Uniform convergence bounds выражаются через Rademacher complexity напрямую
• lt-11-margin-bounds — Margin bounds для SVM и нейросетей - прямое следствие Rademacher-анализа
• lt-13-deep-generalization — Norm-based bounds для нейросетей через Frobenius-норму весов - прямой потомок Rademacher-bounds
• prob-22-concentration — McDiarmid и Hoeffding неравенства - инструменты для перевода Rademacher в generalization bound
• stat-01-sampling