Информационно-теоретические границы обобщения

VC-теория говорит: для нейросетей с миллиардами параметров generalization gap бесконечен. Но GPT-4 generalize-ит. Что-то не сходится. Russo, Zou в 2016 предложили альтернативу: generalization не зависит от размера модели, а от того, сколько модель ЗАПОМНИЛА из данных. Mutual information между весами и выборкой. Эта идея запустила post-VC эру learning theory - где deep networks больше не парадокс, а математически объяснимы.

• **Information bottleneck (Tishby 2017):** SGD автоматически compresses representations - implicit regularization без явного штрафа
• **PAC-Bayes for DNNs (Dziugaite, Roy 2017):** первые конечные bounds для нейросетей - 16% при 2% test error на MNIST
• **Scaling laws через MI:** Anthropic, OpenAI используют info-theoretic анализ для прогноза performance крупных моделей
• **Network pruning с гарантиями:** Google и Meta применяют PAC-Bayes-style сжатие для формальных guarantees после прунинга

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

• Mutual information $I(X; Y) = H(X) - H(X \mid Y)$ - сколько случайности в $X$ устраняется знанием $Y$
• KL-дивергенция $\text{KL}(Q \| P) = \mathbb{E}_Q[\log Q/P]$ - информационное расстояние между распределениями
• PAC-Bayes bound: $\mathbb{E}_Q[R] \leq \mathbb{E}_Q[\hat{R}] + \sqrt{(\text{KL}(Q \| P) + \log(1/\delta))/(2n)}$
• $\sigma$-субгауссова случайная величина: $\mathbb{E}[e^{\lambda(X - \mathbb{E}X)}] \leq e^{\lambda^2 \sigma^2 / 2}$

• VC dimension - классическая комбинаторная сложность
• PAC-Bayes - стохастический предшественник info bounds
• Deep generalization - применение info bounds к сетям

Mutual information и обобщение: формула Russo-Zou

Классическая PAC-теория строит границы через VC-размерность и Rademacher complexity. Для overparametrized нейросетей это не работает: $\text{VCdim} \geq W$ может быть в миллиардах, формальная граница вакуусна. Но в реальности GPT-4 и ResNet обобщаются. Значит, мера сложности должна зависеть не от класса гипотез, а от связи между обученной моделью и обучающей выборкой. Russo, Zou (2016) предложили такую меру: mutual information $I(W; S)$ между случайными весами $W$ обученной модели и обучающей выборкой $S$. Их теорема: для $\sigma$-субгауссовой потери $$\mathbb{E}[R(W) - \hat{R}_S(W)] \leq \sqrt{\frac{2 \sigma^2 I(W; S)}{n}}.$$ Интуиция: $I(W; S)$ - сколько информации о выборке записано в весах. Если $W$ независимы от $S$ ($I = 0$), generalization gap нулевой. Чем больше модель запомнила про $S$, тем больше потенциальный gap. Это количественное определение memorization.

**Почему это работает там, где VC не работает:** VC bound зависит от $\text{VCdim}(\mathcal{H})$ - наихудшего случая по всему классу. Информационная граница зависит от $I(W; S)$ - конкретного алгоритма обучения и распределения данных. Для overparametrized сетей $\text{VCdim} \geq n$, но $I(W; S)$ может быть $O(\log n)$ или меньше: SGD проходит по выборке, но обновления зашумлены, и итоговые веса хранят лишь сжатый сигнал. Xu, Raginsky (2017) доказали: для SGLD (стохастический Langevin) после $T$ шагов $I(W_T; S) \leq \frac{\eta T L^2}{\sigma^2 n}$, где $\eta$ - learning rate, $L$ - липшицевая константа градиента. Граница не зависит от числа параметров - только от шума и числа шагов. **Information bottleneck (Tishby, Schwartz-Ziv 2017):** SGD во время обучения проходит две фазы - fitting (растёт $I(\text{features}; \text{labels})$) и compression (падает $I(\text{features}; \text{input})$). Compression коррелирует с улучшением обобщения. Эмпирическое подтверждение информационной интерпретации generalization.

MI напрямую почти невозможно оценить в высоких размерностях. На практике используют variational оценки: MINE (Belghazi 2018), InfoNCE (Oord 2018), CLUB (Cheng 2020). Все они дают нижнюю или верхнюю оценку на $I(W; S)$ через нейросетевой критик. Для PAC-Bayes-style анализа достаточно верхней границы - её даёт KL между posterior и data-independent prior.

Conditional Mutual Information bounds

У формулы Russo-Zou есть слабое место: $I(W; S)$ часто оказывается бесконечной для детерминированных алгоритмов с непрерывными весами. Если SGD из фиксированной инициализации даёт детерминированную функцию от $S$, то $H(W \mid S) = 0$ и $I(W; S) = H(W)$ - бесконечно для континуальных $W$. Steinke, Zakynthinou (2020) предложили обходной приём - conditional mutual information через supersample. Берётся 2n независимых примеров $\tilde{Z} = (Z_0, Z_1)$, где каждая пара $(Z_{i,0}, Z_{i,1})$ - два iid примера. Случайный битовый вектор $U \in \{0,1\}^n$ выбирает по одному из каждой пары: $S = \{Z_{i, U_i}\}$. Алгоритм обучается на $S$, получает веса $W$. CMI определяется как $\text{CMI}(\mathcal{A}) = I(W; U \mid \tilde{Z})$ - сколько информации о выборе $U$ записано в $W$, учитывая знание всех 2n примеров. Их теорема: $$\mathbb{E}[R(W) - \hat{R}_S(W)] \leq \sqrt{\frac{2 \text{CMI}(\mathcal{A})}{n}}.$$ Ключ: $\text{CMI} \leq n \log 2$ - конечная всегда, в отличие от $I(W; S)$. Для алгоритмов с малой чувствительностью к $U$ (то есть похожим выходом на $S = Z_0$ и $S = Z_1$) CMI близка к нулю.

**Чем CMI лучше vanilla MI:** | Свойство | $I(W; S)$ | $\text{CMI}(\mathcal{A})$ | |----------|-----------|---------------------------| | Конечность | Не всегда (бесконечна для детерминированных алгоритмов) | Всегда $\leq n \log 2$ | | Зависимость от $\mathcal{H}$ | Да | Только через алгоритм | | Оценка эмпирически | Сложно | Через supersample experiment | | Tightness | Часто завышена | Tighter в среднем | **Supersample эксперимент в коде:** 1. Сгенерировать $2n$ примеров. 2. Многократно сэмплировать $U \in \{0,1\}^n$, обучать модель на $S(U)$. 3. Оценить $I(W; U \mid \tilde{Z})$ через variational bound на разнице log-likelihoods. **Где CMI даёт tight bounds:** - kNN: алгоритм игнорирует большинство примеров, $\text{CMI} = O(k \log n)$. - Gaussian process regression: $\text{CMI} \approx \frac{1}{2} \log \det(I + K/\lambda)$ - effective dimension ядра. - SGD на overparametrized linear regression: Microsoft Research показали (Negrea et al. 2019, Haghifam et al. 2020) tight CMI bounds для benign overfitting в линейных моделях.

Линия Steinke-Zakynthinou открыла серию улучшений: Haghifam et al. (2020) показали как комбинировать CMI с stability arguments; Hellström, Durisi (2022) обобщили на f-divergences; Wang, Mao (2023) дали tight CMI bounds для трансформеров на synthetic data. Это активная research line - почти каждый год NeurIPS/ICML приносит новые улучшения для конкретных классов алгоритмов.

PAC-Bayes через информационную линзу

PAC-Bayes formula McAllester-Catoni - это информационная граница, замаскированная под классическую. Для prior $P$ (data-independent) и posterior $Q$ (data-dependent): $$\mathbb{E}_{h \sim Q}[R(h)] \leq \mathbb{E}_{h \sim Q}[\hat{R}_S(h)] + \sqrt{\frac{\text{KL}(Q \| P) + \log(1/\delta)}{2n}}.$$ KL-член $\text{KL}(Q \| P) = \mathbb{E}_{h \sim Q}[\log Q(h)/P(h)]$ - чисто информационная величина: на сколько $Q$ отошла от $P$. И через цепное правило $\mathbb{E}_S[\text{KL}(Q_S \| P)] = I(S; H)$, где $H \sim Q_S$. То есть PAC-Bayes - алгоритм-зависимая верхняя оценка для $I(S; H)$ через выбор prior. **Dziugaite, Roy (2017)** оптимизировали $Q$ - распределение над весами малой DNN на MNIST - так чтобы балансировать train error и KL. Получили первую нон-вакуусную границу для нейросети: 16% при 2% test error. Не tight, но конечно. До этого для нейросетей вообще не было конечных bounds. **Развитие линии:** - Dziugaite (2018): data-dependent priors - центрировать $P$ в окрестности initialization, KL уменьшается. - Zhou et al. (2019): bound через сжатие сети до короткого описания - tight для сильно прунинговых архитектур. - Pérez-Ortiz et al. (2021): PAC-Bayes meta-learning - prior учится на похожих задачах. - Self-distillation perspective: student с posterior $Q$ близким к teacher prior $P$ имеет малый KL, отсюда tight bound (Mobahi 2020).

**Эквивалентность PAC-Bayes и MI bounds:** For любой алгоритм $\mathcal{A}$, выходящий $W = \mathcal{A}(S)$: $$I(W; S) = \mathbb{E}_S[\text{KL}(P_{W \mid S} \| P_W)],$$ где $P_W$ - маргинал. То есть mutual information = ожидаемая KL posterior относительно маргинального prior. PAC-Bayes использует свободу выбора $P$ (любой data-independent prior). Если выбрать $P = P_W$ (маргинальный по выборке prior), KL term ровно совпадает с conditional KL, и в среднем по $S$ даёт $I(W; S)$. То есть PAC-Bayes - upper bound для MI bound с data-dependent posterior optimization. **Mass concentration на flat minima:** flat minimum (малый Hessian trace) позволяет взять $Q$ с большим $\sigma$ (gauss посередине минимума) без увеличения $\mathbb{E}_Q[\hat{R}]$. Большой $\sigma$ при центре около prior $P$ даёт малый KL. Связка: flat minimum -> большой $\sigma$ posterior -> малый KL -> tight PAC-Bayes bound. Это формальное обоснование почему SGD small-batch (находящий flat minima) даёт хорошее обобщение - не через прямой алгоритмический анализ, а через информационную емкость найденного решения. **Применение в индустрии:** Google Research, Meta AI используют PAC-Bayes-style сжатие для tight generalization guarantees в network pruning. Цель: после pruning описание сети короче -> меньше KL относительно coding prior -> формальная гарантия performance.

Frontier: stochastic gradient and chained MI

Самое мощное применение информационных bounds - анализ SGD. Hardt, Recht, Singer (2016) показали algorithmic stability SGD: если функция потерь $L$-липшицева и $\beta$-гладкая, то после $T$ шагов SGD $\epsilon$-uniformly stable с $\epsilon = O(L^2 \beta T / n)$. Stability напрямую переводится в generalization bound. Информационная переформулировка: stability подразумевает малый $I(W_T; S)$. Замена примера в $S$ меняет $W_T$ слабо -> $W_T$ слабо зависит от конкретных примеров -> малый mutual information. Проблема исходной формулы Russo-Zou: для длинного training $I(W_T; S)$ может расти с $T$. Решение - chained MI (Asadi, Abbe, Verdú 2018): $$I(W_T; S) \leq \sum_{t=1}^{T} I(W_t; S \mid W_{t-1}).$$ Каждый член $I(W_t; S \mid W_{t-1})$ ограничен дисперсией одного gradient step. Для SGD с шумом масштаба $\sigma_g$: $I(W_t; S \mid W_{t-1}) = O(\eta^2 / \sigma_g^2)$ - зависит от ratio learning rate к шуму, не от $n$ или $W$. Содержательный вывод: SGD с большим шумом (large learning rate, small batch) даёт лучшее обобщение через информационную линзу. Это формализация эмпирического наблюдения о implicit regularization SGD.

**Что info bounds объясняют, чего не могут VC bounds:** | Феномен | VC bound | Info bound | |---------|----------|------------| | Overparametrization без переобучения | Вакуусный (VC >= n) | Малая $I(W;S)$ для шумного SGD | | Double descent | Не предсказывает | Частично (Bartlett et al. 2020 для линейных) | | Implicit SGD regularization | Не видит | Прямой механизм через $\sum I(W_t; S \mid W_{t-1})$ | | Scaling laws | Противоречие (больше параметров - хуже bound) | Согласовано если $I/n$ остаётся ограниченным | | Self-distillation | Не объясняет | Student имеет малый KL от teacher = регуляризация | **Открытые проблемы 2024-2026:** - **Adaptive optimizers (Adam, Lion):** preconditioner $V_t$ зависит от истории градиентов, $I(V_t; S)$ растёт сложным образом. Tight bounds открыты. - **Chinchilla scaling laws (Hoffmann 2022):** оптимальный $N \sim D$ - можно ли вывести информационно? Anthropic interpretability team работает над IT-формулировкой. - **Foundation models:** $I(W; S)$ для pretraining vs fine-tuning - надо ли считать совместный MI или separate. Активная research line в Anthropic, OpenAI. - **Mechanistic interpretability:** $I(\text{circuit}; \text{task})$ - сколько информации о задаче содержится в конкретной подсхеме сети. Связь с $I(W; S)$ не формализована. **Anthropic's scaling hypothesis:** утверждение что capabilities emerge при увеличении масштаба - имеет частичную IT-теоретическую базу через scaling of $I(W; S)$ при фиксированном $I(W; S)/N$ ratio.

Информационные bounds - не панацея. Текущие границы остаются вакуусными для GPT-4-масштабных сетей: точные оценки $I(W; S)$ требуют либо variational методов с большой variance, либо conservative upper bounds через PAC-Bayes с вакуусным KL. Прогресс есть (Lotfi et al. 2022, Pérez-Ortiz 2021), но gap между bound и реальной ошибкой для больших архитектур остаётся в десятки процентов. Утверждение 'теория обобщения для DL решена' - неверно. Утверждение 'есть инструмент, объясняющий направление и качественные эффекты' - корректно.

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

• **Russo-Zou (2016):** $\mathbb{E}[R - \hat{R}] \leq \sqrt{2 \sigma^2 I(W; S) / n}$. Generalization gap определяется mutual information между весами и выборкой - алгоритм-зависимая мера, ушедшая от VC-комбинаторики
• **Steinke-Zakynthinou CMI (2020):** supersample trick делает MI всегда конечной ($\leq n \log 2$). Tight bounds для kNN, GP, certain DNNs - обходит проблему бесконечной MI для детерминированных алгоритмов
• **PAC-Bayes как информационная граница:** $\text{KL}(Q \| P)$ - upper bound для $I(W; S)$, при $P = P_W$ совпадают в среднем. Свобода выбора prior - источник tightness. Dziugaite-Roy 2017 первая нон-вакуусная для DNN
• **Chained MI Asadi-Abbe-Verdú (2018):** $I(W_T; S) \leq \sum I(W_t; S \mid W_{t-1})$. Раскладывает trajectory analysis на per-step MI - формализует implicit SGD regularization через learning rate и gradient noise
• **Что объясняют info bounds:** overparametrization без переобучения, implicit SGD bias, эффект шумного gradient descent, частично double descent, scaling laws с фиксированным $I/n$
• **Открытые проблемы:** tight bounds для adaptive optimizers (Adam), foundation models (pretraining + fine-tuning), mechanistic interpretability circuits. Активная research line 2024-2026 в Anthropic, Microsoft Research, DeepMind

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

Куда ведут info-theoretic bounds:

• VC dimension — Классические bounds, которые info-theoretic улучшают - VC даёт worst-case по классу, MI - algorithm-specific
• PAC-Bayes — Информационная переформулировка PAC: $\text{KL}(Q \| P)$ - upper bound для $I(W; S)$
• Deep generalization — Применение info bounds к нейросетям объясняет paradox Zhang 2017 без вакуусности
• Information theory: entropy and MI — Базовые определения mutual information и энтропии - инструментарий всех bounds в этом уроке
• Information projection — PAC-Bayes posterior $Q$ как KL-проекция на ограничение train error - геометрия в пространстве распределений

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

• Russo-Zou bound даёт $\sqrt{2\sigma^2 I(W; S)/n}$. Для overparametrized сети с шумным SGD утверждается что $I(W; S)$ может быть малой даже при $W$ в миллиардах. Какие условия на алгоритм и распределение данных нужны чтобы это утверждение было доказуемым, а не просто эвристическим? Достаточно ли SGD-стабильности или нужны более сильные структурные предположения о геометрии loss surface?
• PAC-Bayes Dziugaite-Roy 2017 даёт bound 16% при test error 2% на MNIST. Для ResNet-152 на ImageNet прямое применение даёт вакуусные bounds. Что именно ломается при масштабировании - сам формализм PAC-Bayes (например, неподходящий prior space для гигантских сетей) или техника оптимизации posterior, или фундаментальный предел информационных bounds для сетей такого размера? Какой эксперимент мог бы различить эти гипотезы?
• Chained MI bound разлагает $I(W_T; S)$ на per-step contributions. Для SGD с шумом каждый шаг даёт $O(\eta^2/\sigma_g^2)$. Но в реальности fine-tuning foundation models - это short training с low noise (не SGLD-подобное). Как по информационной линзе объяснить почему fine-tuning не разрушает обобщение, если pretraining уже потратил всю 'информационную ёмкость' модели? Связано ли это с feature learning vs feature reuse и можно ли формализовать через decomposition $I(W_{\text{ft}}; S_{\text{ft}}) = I(W_{\text{ft}}; S_{\text{ft}} \mid W_{\text{pre}}) + I(W_{\text{ft}}; W_{\text{pre}}; S_{\text{ft}})$?

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

• lt-04-vc-dimension — Info-theoretic bounds tighten classical VC results
• lt-09-pac-bayes — PAC-Bayes is info-theoretic in disguise
• lt-13-deep-generalization — Deep nets are the canonical use case for these bounds
• it-01 — Mutual information is the core quantity
• ig-08-info-projection — Both use KL/MI on parameter spaces