Статистическая теория обучения
Алгоритмическая устойчивость
Почему работает early stopping? Bousquet и Hardt (2016) дали ответ: SGD с ограниченным числом шагов β-устойчив, и эта устойчивость даёт гарантию обобщения без явного VC-анализа.
- **Early stopping:** Формальное теоретическое обоснование через β-устойчивость SGD: меньше шагов - меньше β - лучше гарантия обобщения
- **Differential privacy:** DP-SGD добавляет шум к градиентам, что формально обеспечивает устойчивость алгоритма по определению приватности
- **Meta-learning:** MAML использует устойчивость для анализа few-shot обобщения: замена одной задачи не должна сильно менять мета-параметры
- **AlphaFold 2:** DeepMind анализирует обобщение модели через устойчивость SGD при обучении на 170 000 структур белков
Предварительные знания
- Сложность Радемахера
- Агностическое PAC-обучение
- Стохастический градиентный спуск
Алгоритмическая устойчивость
DeepMind (2021) использует устойчивость SGD в анализе AlphaFold 2: при обучении на 170 000 белков со скоростью обучения η и T шагами ошибка обобщения ограничена 2Lη T/m - где L - константа Липшица потерь. Это объясняет, почему early stopping работает.
Что измеряет uniform-stability алгоритма A?
beta_n-stable: для всех S, z, z': |L(A(S), z) - L(A(S^{i, z'}), z)| <= beta_n. Чем меньше beta_n, тем меньше алгоритм "пере-обучается" на отдельные точки. Bousquet-Elisseeff (2002) показали, что устойчивость → обобщение: R(A(S)) - R_hat(A(S)) <= O(beta_n + sqrt(log(1/delta)/n)).
Стабильность и обобщение
Какая связь между sigma_n-устойчивостью и обобщающей способностью?
Bousquet-Elisseeff: для beta_n-устойчивого алгоритма E[R(A(S)) - R_hat(A(S))] <= 2 * beta_n. С большой вероятностью: |R - R_hat| <= O(beta_n + sqrt(log(1/delta)/n)). Это в духе VC, но без явного класса гипотез - сложность встроена в свойства алгоритма.
Примеры: SGD, регуляризация Тихонова
Алгоритмическая устойчивость как устойчивость врача к замене одного пациента - Врач (алгоритм) принимает решение по набору пациентов (выборке). Устойчивый врач: замена одного пациента не меняет диагнозы остальным. Нестабильный врач: один новый пациент перестраивает всю практику. Устойчивость - формализация здравого смысла: хороший алгоритм не должен кардинально меняться от одного нового примера.
Почему SGD на выпуклой L-Липшицевой функции потерь является устойчивым алгоритмом?
Hardt-Recht-Singer (2016): SGD на выпуклых L-Липшицевых функциях имеет uniform stability beta_n = O(T*L²/n). При T = O(n) и eta = 1/sqrt(T): generalization error = O(L²/sqrt(n)). Для невыпуклых функций (DNN) границы слабее, но общий механизм работает.
Связи с другими темами
Алгоритмическая устойчивость связывает теорию обобщения с практическими методами регуляризации и конфиденциальности.
- Дифференциальная приватность — Связанная тема
- L2-регуляризация — Связанная тема
- Равномерная устойчивость vs Радемахерова сложность — Связанная тема
- Мета-обучение — Связанная тема
Итоги
- β-устойчивость: замена одного примера в S изменяет потерю на любой точке не более чем на β
- Граница Bousquet-Elisseeff: L(h) не хуже L-hat_S(h) + β + O((mβ + M)·sqrt(log(1/δ)/m))
- SGD: β = 2L²ηT/m, растёт линейно с T - early stopping формально обоснован
- L2-регуляризация: β = M²/(2λm), увеличение λ улучшает устойчивость
- Устойчивость - альтернатива VC-анализу: даёт гарантии через свойства алгоритма, а не класса
Как изменяется устойчивость SGD при увеличении числа шагов T (при фиксированном η и m)?
Устойчивость SGD: β = 2L²ηT/m. Линейный рост с T означает, что early stopping (малое T) улучшает устойчивость и обобщение.