Generalization paradox в deep learning

2017 год. Команда Google Brain берёт ResNet и заменяет все labels в CIFAR-10 на случайные. Сеть обучается до 100% точности на трейне - и затем обобщает нормально на реальных данных. Для теоретика это как 2+2=5. PAC-теория говорит: это невозможно. Что-то фундаментально сломано. Если сеть способна запомнить полный шум - значит её VC-размерность огромна. Значит VC bounds говорят: ей нужно O(25M) примеров для обобщения. На ImageNet всего 1.2M. По классической теории ResNet не должен работать вообще. Он работает. С 4.9% ошибкой. Каждый день в проде. Это не технический баг и не грязный эксперимент. Это свидетельство того, что классическая теория обобщения описывает принципиально другой объект, чем реальное глубокое обучение. Что именно - вопрос открытый по сей день.

• **Любая deployed нейросеть - необъяснённая:** GPT-4, Gemini, ResNet в медицинской диагностике - ни для одной из них нет строгой теоремы что она обобщается. Есть эмпирика, есть PAC-Bayes первые шаги, но полной теории нет. Это не метафора - буквально отсутствие математических гарантий
• **Регуляризация без теории:** dropout, weight decay, batch normalization - все они помогают обобщению на практике. Почему именно - частичные объяснения через PAC-Bayes и implicit bias SGD, но унифицированной теории нет
• **Double descent на production:** команды Google и OpenAI наблюдают double descent при масштабировании моделей. Увеличение параметров поначалу ухудшает generalization loss на checkpoint-ах mid-training - ровно предсказание теории Belkin 2019

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

• PAC framework: R(h) <= R_hat(h) + sqrt(VCdim / 2m) - классический bound
• Вакуусный bound: когда VCdim >= m, выражение под sqrt отрицательное или >= 1
• KL-дивергенция: KL(Q||P) = E_Q[log Q/P] >= 0, мера информационного расстояния

• PAC-Bayes: первая нон-вакуусная граница для нейросетей
• Margin-based bounds: почему SVM обобщается

Парадокс Zhang 2017 и провал классических bounds

Эксперимент Zhang-Bengio-Hardt-Recht-Vinyals (ICLR 2017) был намеренно жестоким. Берётся CIFAR-10 - 50 000 картинок, 10 классов. Labels заменяются случайными числами от 0 до 9. Никакого сигнала нет - чистый шум. Запускается стандартный ResNet с SGD. Результат: train accuracy = 100%. Сеть идеально выучила соответствие картинка-шум для всех 50 000 примеров. Время обучения увеличилось, но не принципиально. Потом тот же ResNet обучается на реальных labels. И обобщается нормально на тесте. Что это означает: сеть способна одновременно (1) меморизовать произвольное отображение на обучающей выборке и (2) обобщаться на тестовой, если данные имеют структуру. Классическая теория не различает эти два режима.

**Почему VC bounds вакуусны (формально):** ВС-теорема: $R(h) \leq \hat{R}(h) + \sqrt{\frac{\text{VCdim}(\mathcal{H}) \cdot \log(em/d) + \log(1/\delta)}{2m}}$ Если сеть меморизует $n$ случайных примеров с произвольными labels, то $\text{VCdim}(\mathcal{H}) \geq n$. Для ResNet на CIFAR-10 с $n = 50{,}000$: $\text{VCdim} \geq 50{,}000 = m$. Логарифм $\log(em/d)$ при $d \geq m$ близок к нулю или отрицателен. Bound становится $\geq 1$ - вакуусный. Для ResNet-50 на ImageNet: $W = 25 \times 10^6$, $m = 1.2 \times 10^6$. Bound $\approx \sqrt{25M / 2.4M} \approx 3.2$. Гарантия: ошибка не превышает 320%. Это математически корректно и абсолютно бесполезно.

Ключевой вывод Zhang et al.: classical complexity measures - VC dimension, Rademacher complexity, uniform stability - не коррелируют с фактическим обобщением нейросетей. Модели с одинаковой архитектурой и одинаковым числом параметров могут иметь принципиально разное обобщение в зависимости от данных и алгоритма обучения. Это не значит что теория обобщения неверна. Это значит что она измеряет не то свойство модели, которое важно для DL. Нужна принципиально другая мера сложности.

Double descent и интерполяционный порог

Классическая теория предсказывает U-образную кривую bias-variance: слишком простая модель - высокий bias; слишком сложная - высокая variance, переобучение. Оптимум посередине. Это правило, которому учат на первом курсе ML. Belkin, Hsu, Ma, Mandal (2019) показали: кривая ошибки в действительности имеет два минимума. Сначала U-образный спуск как в классике. Затем резкий рост вблизи interpolation threshold - точки, где модель ровно достаточно сложна чтобы идеально подогнать обучающие данные. И затем ещё один спуск при дальнейшем увеличении сложности. Это double descent. Модели в режиме сильного overparameterization (правее порога) могут обобщаться лучше, чем модели в классическом режиме underparameterization.

**Double descent (Belkin et al. 2019):** Пусть $n$ - размер обучающей выборки, $p$ - число параметров модели. - $p \ll n$ (underparameterized): классический bias-variance tradeoff, U-кривая - $p \approx n$ (interpolation threshold): пик ошибки - модель с трудом интерполирует, решение неустойчивое - $p \gg n$ (overparameterized): второй спуск - модель интерполирует, но среди всех интерполирующих решений SGD/минимальная норма выбирает простейшее **Benign overfitting:** при $p \gg n$ модель может идеально подогнать обучающие данные (train error = 0) и всё равно хорошо обобщаться. Это противоречит классическому определению переобучения. **Минимальная норма интерполяция:** при $p > n$ существует бесконечно много решений с нулевой ошибкой. Gradient descent (и SGD) из нулевой инициализации находит решение с минимальной L2-нормой - наиболее "простое" из всех.

Что происходит в точке интерполяции? При $p \approx n$ задача interpolation почти singular: матрица признаков $\Phi$ квадратная, маленькие изменения в данных приводят к большим изменениям в весах. Модель нестабильна, variance огромна. При $p \gg n$ систем уравнений бесконечно много решений. Gradient descent из нулевой инициализации находит решение минимальной нормы - это теорема (не эвристика). Минимальная норма = гладкая интерполяция = разумное обобщение. Связь с SGD и нейросетями: эмпирически нейросети работают в глубоко overparameterized режиме и находят решения с малой нормой весов. Double descent объясняет почему это безопасно. Открытый вопрос: точный механизм, по которому SGD выбирает среди всех интерполирующих решений.

Современные объяснения: PAC-Bayes, NTK, implicit SGD bias

Три направления дают частичные объяснения generalization paradox. Ни одно не закрывает вопрос полностью - это важно понимать. **PAC-Bayes Dziugaite-Roy 2017.** Первая нон-вакуусная граница для реальных нейросетей: 16% bound на MNIST при 2% тестовой ошибке. Инструмент: вместо одной гипотезы - распределение Q над гипотезами с center в обученных весах. KL(Q||P) измеряет информационную сложность конкретного решения SGD, а не всего класса. Ключ: SGD находит flat minima с малым KL, поэтому bound конечный. **NTK (Neural Tangent Kernel, Jacot-Gabriel-Hongler 2018).** При ширине сети -> infinity веса меняются мало при обучении, и динамика сводится к kernel regression с фиксированным ядром K(x,x') = J(x)J(x')^T, где J - якобиан сети. В NTK режиме обобщение определяется спектральным распадом K - классическая kernel theory применима. Проблема: реальные сети далеки от infinite width, NTK режим - математический предел, а не описание практики. **Implicit SGD regularization.** Hochreiter-Schmidhuber 1997, Keskar et al. 2017, Wilson et al. 2017: SGD с маленьким batch size предпочитает flat minima - области где Hessian функции потерь имеет малый trace. Flat minimum по определению мало чувствителен к возмущениям весов. Через PAC-Bayes: flat minimum = большая sigma в posterior = малый KL = лучший bound. Это связь между алгоритмом (SGD) и теорией (PAC-Bayes), но механизм предпочтения flat minima формально не доказан для произвольных архитектур.

**Три инструмента и их ограничения:** | Подход | Что объясняет | Ограничение | |--------|--------------|-------------| | PAC-Bayes (Dziugaite-Roy 2017) | Конечный bound для конкретного алгоритма | 16% при 2% error - gap большой; для больших сетей bound вакуусный | | NTK (Jacot 2018) | Обобщение в infinite-width пределе | Реальные сети конечные, NTK - предел, а не описание практики | | Implicit SGD bias | SGD находит flat minima | Почему SGD предпочитает flat - неформально; зависит от lr, batch size, архитектуры | **Margin bounds (Bartlett-Foster-Telgarsky 2017):** bound через spectral norm произведения весовых матриц: $R(h) \leq O\left(\frac{\prod_l \|W_l\|_{op} \cdot \text{depth}}{\gamma \sqrt{m}}\right)$. Работает для сетей с большим margin $\gamma$ - объясняет почему правильно обученные сети обобщаются лучше чем bound через одни только параметры. **Статус (2024-2025):** открытая проблема. Нет единой теории, объясняющей обобщение произвольной нейросети с полезными guarantees. PAC-Bayes - наиболее продвинутый инструмент, но gap между bound и реальной ошибкой остаётся большим для реальных архитектур.

Почему это всё ещё открытая проблема в 2025 году? Первое: PAC-Bayes bounds улучшаются, но для больших сетей (GPT-4, ResNet-152 на ImageNet) они по-прежнему вакуусны. Dziugaite-Roy работает для маленьких сетей на MNIST. Второе: NTK описывает бесконечно широкие сети, где feature learning не происходит. Реальные нейросети учат features - это принципиально другой режим. Попытки объединить NTK и feature learning (mean-field regime, tensor programs) продолжаются. Третье: у нас нет теоремы вида 'SGD на задаче X находит решение с property Y'. Implicit bias SGD - набор эмпирических наблюдений и результатов для специальных случаев, не общая теория. Четвёртое: double descent описывает феномен, но не объясняет почему именно minimum-norm interpolation обобщается. Для линейных моделей есть формальный результат (Hastie et al. 2022), для нейросетей - нет.

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

• **Zhang et al. 2017:** современные сети меморизуют произвольные labels и обобщаются на реальных. VC bounds при этом вакуусны - требуют O(параметры) примеров. Теорема правильная, но описывает не то, что важно для DL
• **Double descent (Belkin 2019):** кривая ошибки двугорбая. У interpolation threshold (p=n) - пик из-за нестабильности. При p >> n - второй спуск: minimum-norm interpolation SGD обобщается. Benign overfitting: train=0, test - нормальная
• **PAC-Bayes Dziugaite-Roy 2017:** первая нон-вакуусная граница - 16% при 2% test error на MNIST. Ключ: KL(Q||P) измеряет сложность конкретного решения SGD, а не всего класса. Flat minima = малый KL = хороший bound
• **NTK (Jacot 2018):** в infinite-width пределе сеть = kernel regression. Даёт объяснение для бесконечных сетей, неприменимо напрямую к конечным
• **Implicit SGD bias:** small-batch SGD неявно находит flat minima через gradient noise. Flat minimum = большой sigma_q в posterior = малый KL. Механизм - эмпирически подтверждён, формально не доказан в общем случае
• **Открытая проблема:** нет единой теории generalization для произвольных нейросетей с полезными bounds. PAC-Bayes - лучший инструмент на сейчас, но gap до реальных ошибок остаётся большим для больших архитектур

Связи с другими концепциями

Generalization paradox - точка пересечения всего курса по теории обучения:

• PAC-Bayes — Dziugaite-Roy 2017 применили PAC-Bayes к нейросетям - получили первые нон-вакуусные bounds. Flat minima через KL - прямая связь
• Margin bounds — Bartlett-Foster-Telgarsky 2017 spectral norm bounds - работают для сетей с большим margin, дополняют PAC-Bayes объяснение
• No-Free-Lunch — Zhang 2017 показывает: без prior о структуре данных нет обобщения. SGD implicit bias - неявный prior о flat solutions
• VC-размерность — VC bounds вакуусны для нейросетей - отправная точка всей дискуссии о generalization paradox

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

• Double descent показывает что minimum-norm interpolation при p >> n обобщается. Но нормы весов в нейросетях зависят от инициализации, learning rate и batch size - не только от архитектуры. Можно ли управлять выбором 'какое именно минимальной нормы решение' находит SGD, меняя только гиперпараметры? Что предсказывает PAC-Bayes про эти решения?
• NTK даёт объяснение для infinite-width сетей - там feature learning нет, веса почти не двигаются. Реальные Transformer-ы явно учат features (attention heads специализируются). Как вы думаете - где граница между NTK режимом и feature learning режимом? Что было бы нужно чтобы построить теорию для feature learning?
• PAC-Bayes bound для ResNet-50 (25M params, ImageNet 1.2M) с гауссовым prior N(0, 0.01 I): KL ~ W * (w_norm^2 / 2*lambda + ...) ~ 25M * 3 = 75M. Bound: sqrt(75M / 2.4M) ~ 5.6 - вакуусный. Что нужно изменить в подходе Dziugaite-Roy чтобы получить нон-вакуусный bound для больших сетей? Есть ли принципиальное препятствие или только техническое?

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

• stat-01-sampling