Agnostic PAC: когда истинной гипотезы нет

Число-шок: в realizable случае удвоение точности (epsilon -> epsilon/2) стоит удвоения данных. В agnostic - учетверения. Квадрат - не случаен. Это цена за то, что природа не обязана укладываться в H. Все современные задачи ML - agnostic. Logistic regression на зашумлённых медицинских данных, трансформер на интернет-тексте, RLHF на человеческих оценках - везде c не в H. Realizable case - красивая теорема. Agnostic PAC - реальность.

• **SGD batch size и квадрат epsilon**: оценка дисперсии mini-batch gradient через Hoeffding-bound - это agnostic PAC для оптимизации. Variance шума градиента убывает как 1/B (B - batch size). Удвоение точности требует учетверения batch - та же O(1/epsilon^2) структура. Adam и AdamW знают это неявно: адаптивный lr компенсирует квадратичный рост.
• **Логистическая регрессия и шумные метки**: ECG-датасеты размечаются кардиологами, и cardiologist agreement около 85%. c не в H по определению - данные противоречивы. Agnostic PAC гарантирует: достаточно примеров - и ERM достигнет ошибки не хуже лучшего линейного классификатора плюс epsilon. Это и есть rationalisation за отсутствие overfitting при L2-регуляризации.
• **RLHF и нереализуемость человеческих предпочтений**: человеческий feedback противоречив (разные raters не согласны), нестационарен, зашумлён. Bradley-Terry модель - это ERM на agnostic данных. Sample complexity RLHF прямо следует из Hoeffding-bound: для 1% улучшения alignment-score нужно в 100 раз больше human feedback чем для 10%.
• **Kearns-Schapire-Sellie 1992**: первая формальная агностическая теорема. Три автора доказали: ERM в agnostic случае с m >= C/epsilon^2 * log(|H|/delta) достигает excess risk <= epsilon. Прямая линия к modern generalization bounds: VC-dimension, Rademacher complexity, PAC-Bayes - все используют ту же Hoeffding-технику.
• **Регрессия и MSE**: среднеквадратичная ошибка - agnostic PAC для вещественных меток. min_{h in H} E[(h(x) - y)^2] > 0 почти всегда (реальные данные не линейны). OLS находит ERM с шумом. Sample complexity через Hoeffding для bounded функций: O(1/epsilon^2) примеров для epsilon-close к oracle predictor.

Kearns-Schapire-Sellie 1992: честность как теорема

Статья 'Toward Efficient Agnostic Learning' (COLT 1992) появилась через восемь лет после Валианта. Валиант строил теорию на идеальных данных - c в H. Кирнс, Шапир и Селли спросили: а что если нет? Результат жёсткий: sample complexity растёт с O(1/epsilon) до O(1/epsilon^2). Без допущений - нет халявы. Это не ухудшение алгоритма, это нижняя граница: любой PAC-алгоритм на агностических данных не может обойтись меньшим числом примеров. Шапир позже стал одним из создателей AdaBoost - первого алгоритма, который работал в agnostic-режиме с практическими гарантиями. Прямая линия от 1992 до современного ML.

Концепт 1: agnostic-постановка - что меняется без c в H

Концепт 1: agnostic-постановка - что меняется без c в H

Realizable case предполагал: c в H, существует h* с R(h*) = 0. Это сильное допущение. В реальности данные шумные - один и тот же x может иметь разные метки. Природа нелинейна, признаки неполны, рейтеры не согласны. c не в H - норма, не исключение.

Концепт 2: неравенство Хёффдинга - откуда квадрат

Концепт 2: неравенство Хёффдинга - откуда квадрат

В realizable-доказательстве ключевым был union bound: плохая гипотеза выживает с вероятностью $(1-\varepsilon)^m$. В agnostic-случае это не работает: нет гипотезы с hat-R = 0, критерий провала другой. Нужен инструмент для оценки отклонения среднего от матожидания. Хёффдинг его даёт.

**Hoeffding и mini-batch SGD**: variance mini-batch gradient есть sigma^2/B, где B - batch size. Это прямое следствие Hoeffding-bound для среднего. Epsilon-close gradient требует B >= sigma^2/epsilon^2. AdamW с adaptive lr по сути компенсирует именно квадратичный рост цены точности. Agnostic PAC и стохастическая оптимизация - одна математика.

Концепт 3: O(1/epsilon^2 log(|H|/delta)) - числа и следствия

Концепт 3: O(1/epsilon^2 log(|H|/delta)) - числа и следствия

Формула agnostic sample complexity знакома по realizable, но epsilon в квадрате меняет всё. Вот что это значит в числах и в практике.

Здесь важен переход от конечного H к бесконечному. В примере выше $|H| = \infty$ - и формула через $\ln|H|$ не работает. Замена: VC-dimension $d$ вместо $\ln|H|$. Структура та же - $O(d/\varepsilon^2)$, только $d$ считается по-другому. Это тема lt-04, но agnostic-механика остаётся: Hoeffding, union bound, квадрат epsilon.

Ключевые идеи

• **Agnostic setup**: c не в H - норма для реальных данных. Цель смещается: не R(h_S) <= epsilon, а R(h_S) <= min_H R(h) + epsilon. Excess risk - единственно честная метрика.
• **Hoeffding-неравенство**: P[|hat-R(h) - R(h)| > eps] <= 2*exp(-2*m*eps^2). Это инструмент для оценки концентрации среднего - core техника agnostic доказательства.
• **Квадрат epsilon**: agnostic bound m >= (1/(2*eps^2))*ln(2|H|/delta). Realizable: O(1/eps). Agnostic: O(1/eps^2). Разница - нижняя граница, не артефакт доказательства.
• **Uniform convergence**: hat-R(h) approx R(h) одновременно для всех h in H - это то, что Hoeffding + union bound реально доказывают. ERM работает потому что выбирает h с малым hat-R, а hat-R и R близки.
• **Kearns-Schapire-Sellie 1992**: первая формализация. Прямая линия к VC-dimension, Rademacher complexity, PAC-Bayes - все они агностические по природе.
• **GPT-4 и шумные задачи**: провал на физическом рассуждении - не баг. Это agnostic PAC предсказывает: на задачах где c не лежит в H трансформера, excess risk > 0 по математическому закону.

Что разблокирует этот урок

Agnostic PAC - первый честный результат: без допущения c в H. Всё дальнейшее строится поверх.

• VC dimension — Заменяет log|H| на VC-dim для бесконечных H; agnostic-структура сохраняется
• Uniform convergence — Строгое доказательство того что hat-R approx R для всех h одновременно
• No-Free-Lunch — Нижняя граница: без ограничений на H никакая гарантия agnostic-типа невозможна
• PAC-Bayes bounds — Agnostic PAC для stochastic classifiers - tight bounds через KL-divergence

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

• GPT-4 провалился на задачах физического рассуждения. Это говорит о том что c не в H трансформера для этих задач - или о недостаточном числе обучающих примеров? Как различить?
• Agnostic bound O(1/eps^2) - нижняя граница для worst-case распределений. Для конкретных задач (например, линейно разделимые данные с margin gamma) bound лучше. Почему?
• RLHF использует противоречивые human preferences. Как agnostic PAC объясняет необходимость большого числа human feedback-пар для хорошего alignment?
• Realizable PAC даёт O(1/eps), agnostic - O(1/eps^2). Что значит 'знание c in H' в информационном смысле - почему это так дёшево стоит?

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

• lt-02-realizable-learning — Realizable - базовый случай, agnostic его обобщает
• lt-04-vc-dimension — VC-dim расширяет agnostic bounds на бесконечные классы
• lt-07-uniform-convergence — Uniform convergence - формальное основание agnostic PAC
• lt-08-no-free-lunch — No-Free-Lunch строится поверх agnostic-постановки
• prob-22-concentration — Хёффдинг и концентрационные неравенства - ядро доказательства
• stat-01-sampling