Динамика SGD и феномен “double descent”: от экспериментальной репликации к интерпретации через теорию динамических систем

Короткая мотивация

Классическая U-образная кривая обобщающей ошибки (задающая компромисс смещения–дисперсии, bias–variance) не объясняет наблюдаемую на практике картину: при росте вместимости модели машинного обучения ошибка на тесте может сначала уменьшаться, затем ухудшаться у интерполяционного порога, а после снова улучшаться — феномен Double Descent. Параллельно эксперименты с большими шагами обучения выявили характерные режимы динамики градиентных методов: катапультный (временный рост лосса с последующим снижением) и край устойчивости (отношение шага к наибольшему собственному значению Гессиана на границе устойчивости).

В этом работе необходимо рассматривать SGD как дискретную динамическую систему, воспроизвести кривые double descent в простых задачах и сопоставить их с фазовыми режимами обучения.

Постановка задачи (по пунктам)

1. Обзор литературы (5–10 стр.).
   • Определить и кратко объяснить: интерполяционный порог, double descent (по размеру модели, по числу эпох), благоприятное переобучение (benign overfitting), стохастическую интерпретацию SGD (как стационарного стохастического процесса), катапультный механизм и край устойчивости.
   • Дать ссылки на первоисточники из списка литературы.
3. Репликация double descent в линейной регрессии.
   • a) Сгенерировать синтетические данные $y=X\beta ^{\star }+\xi$ (гауссов шум). Построить модель линейной регрессии с числом признаков $p$ и числом наблюдений $n$; варьировать отношение $p/n$ так, чтобы пройти через интерполяционный порог.
   • b) Реализовать два случая: (i) минимально-нормированная интерполяция (псевдообратная матрица, без регуляризации); (ii) гребневая регрессия (ridge) для сравнения.
   • c) Построить зависимости ошибки на тесте от $p$ при фиксированном $n$; показать область повышенной ошибки у порога и последующее улучшение (double descent).
5. Epoch-wise double descent на простой нейросети.
   • a) Классификация на MNIST (или подмножество CIFAR-10); однослойный MLP/небольшой CNN.
   • b) Зафиксировав размер модели, варьировать число эпох: построить кривую ошибки на тесте от числа эпох; продемонстрировать вторичное снижение после переподгонки (если наблюдается).
7. SGD как дискретная динамическая система.
   • a) Рассматривать итерации $\theta _{t+1}=\theta _{t}-\eta \,\nabla \ell (\theta _{t};{\mathcal {B}}_{t})$ как отображение в пространстве параметров. Для нескольких значений шага $\eta$ и размера батча $|{\mathcal {B}}|$ провести эксперименты и классифицировать режимы: стабильная сходимость, катапультный режим, разлёт.
   • b) Оценить резкость (sharpness): приблизить наибольшую собственную величину Гессиана лосса методом степеней/Ланцоша (или через Гаусса–Ньютона). Проверить эмпирическое соотношение режима края устойчивости ($\lambda _{\max }\approx 2/\eta$ в полном батче).
   • c) При фиксированной $\eta$ варьировать размер батча и оценить масштаб шума стохастического градиента (например, дисперсию мини-батч градиентов) и его связь с обобщением.
9. Фазовая диаграмма.
   • a) На сетке по $(\eta ,|{\mathcal {B}}|)$ построить карту режимов (цветами/маркерами), нанести уровни тестовой ошибки и отметить области, где наблюдается double descent по размеру модели или по эпохам.
11. Аналитическое обсуждение.
    • Сопоставить наблюдаемые кривые и фазовые режимы с механизмами из литературы (интерполяция и выбор минимально-нормированных решений, роль шума SGD как имплицитной регуляризации, катапультная динамика, край устойчивости).
    • Критически обсудить ограничения и воспроизводимость.
13. Требования к воспроизводимости и оформлению.
    • Код на Python (NumPy/PyTorch), фиксированные сиды, сохранённые конфигурации и графики.
    • Итоговый отчёт обязательно набран в LaTeX, включает рисунки, таблицы и краткие пояснения к экспериментам.

Ожидаемые результаты

• Кривые double descent для линейной (или random-features) регрессии и, по возможности, для небольшой нейросети.
• Демонстрация режимов динамики SGD (стабильность/катапульта/разлёт) при варьировании $(\eta ,|{\mathcal {B}}|)$ и оценка резкости.
• Связь наблюдений с теоретическими механизмами из источников (кратко и без излишней формализации).

Список литературы

1. M. Belkin, D. Hsu, S. Ma, S. Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. PNAS, 116(32):15849–15854, 2019. URL.
2. P. Nakkiran, G. Kaplun, Y. Bansal, T. Yang, B. Barak, I. Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. arXiv:1912.02292, 2019 (доступна версия на OpenReview/ICLR). URL.
3. P. L. Bartlett, P. M. Long, G. Lugosi, A. Tsigler. Benign overfitting in linear regression. PNAS, 117(48):30063–30070, 2020. URL.
4. S. Mandt, M. D. Hoffman, D. M. Blei. Stochastic Gradient Descent as Approximate Bayesian Inference. JMLR, 18(134):1–35, 2017. URL.
5. S. L. Smith, E. Elsen, S. De. On the Generalization Benefit of Noise in Stochastic Gradient Descent. arXiv:2006.15081, 2020. URL.
6. A. Lewkowycz, Y. Bahri, E. Dyer, J. Sohl-Dickstein, G. Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv:2003.02218, 2020. URL.
7. J. M. Cohen, S. Chaudhuri, S. M. Jelassi, N. Cohen, A. Shashua, S. S. Du. Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability. arXiv:2103.00065, 2021. URL.
8. M. S. Advani, A. M. Saxe. High-dimensional dynamics of generalization error in neural networks. arXiv:1710.03667, 2017. URL.

Приложение: подробные указания к пунктам

Репликация double descent в линейной регрессии (подробные шаги)

a) Генерация данных и проход через интерполяционный порог

1. i) Зафиксируйте размер обучающей выборки $n$ (напр., $n=200$) и стандарт отклика $\sigma >0$ (напр., $\sigma =0.5$).
2. ii) Сгенерируйте дизайн-матрицу $X\in \mathbb {R} ^{n\times p}$ по схеме $X_{ij}\sim {\mathcal {N}}(0,1/n)$ (масштаб $1/{\sqrt {n}}$ стабилизирует спектр $X^{\top }X$).
3. iii) Сгенерируйте истинный вектор параметров $\beta ^{\star }\in \mathbb {R} ^{p}$ по одной из схем:
   • (плотная) $\beta _{j}^{\star }\sim {\mathcal {N}}(0,1/p)$
   • или (разреженная) $\beta _{j}^{\star }=0$ кроме $k$ случайных координат.
4. iv) Сгенерируйте шум $\xi \sim {\mathcal {N}}(0,\sigma ^{2}I_{n})$ и целевой вектор $y=X\beta ^{\star }+\xi$.
5. v) Подготовьте независимую тестовую выборку $(X_{\mathrm {test} },y_{\mathrm {test} })$ аналогично, но с $n_{\mathrm {test} }\gg n$ (напр., $n_{\mathrm {test} }=5000$).
6. vi) Проведите серию экспериментов по $p\in \{10,20,40,\dots ,800\}$ (геометрическая/арифметическая сетка), проходя через интерполяционный порог $p\approx n$.
7. vii) Для статистической устойчивости используйте $R\geq 20$ независимых сидов для каждой пары $(n,p)$; в каждом прогоне фиксируйте float64, сиды ГСЧ и сохраняйте конфигурации.

b) Два оценивателя

минимально-нормированный и ридж (ridge)

1. i) Минимально-нормированная интерполяция (без регуляризации). Оценка ${\hat {\beta }}_{\min {\text{-}}\|\cdot \|}$ определяется как
   • ${\hat {\beta }}_{\min {\text{-}}\|\cdot \|}=\arg \min _{\beta }\|\beta \|_{2}\quad {\text{при условии }}X\beta =y.$
   • Эквивалентно, при $p>n$ используйте псевдообратную по Муру–Пенроузу:

     ${\hat {\beta }}_{\min {\text{-}}\|\cdot \|}=X^{\top }(XX^{\top })^{-1}y=X^{+}y.$

   • При $p<n$ это совпадает с МНК-решением ${\hat {\beta }}=(X^{\top }X)^{-1}X^{\top }y$ (при невырожденности $X^{\top }X$).
2. ii) Ридж-регрессия (для сравнения). Для $\lambda >0$ положите
   • ${\hat {\beta }}_{\mathrm {ridge} }(\lambda )=(X^{\top }X+\lambda I_{p})^{-1}X^{\top }y.$
   • Рекомендуется рассмотреть сетку $\lambda \in \{10^{-6},10^{-5},\dots ,10^{1}\}$ и выбирать $\lambda$ по отложенной валидации (или фиксировать одинаковую малую $\lambda$ для всей серии, пояснив выбор).

c) Графики и метрики

1. i) Для каждого оценивателя и каждой пары $(n,p)$ вычисляйте тестовую MSE:
   • $\mathrm {MSE} _{\mathrm {test} }={\frac {1}{n_{\mathrm {test} }}}\,\|X_{\mathrm {test} }{\hat {\beta }}-y_{\mathrm {test} }\|_{2}^{2}.$
2. ii) Агрегируйте по $R$ прогонам: показывайте медиану и межквартильный размах (IQR). На оси абсцисс — $p$ (или отношение $p/n$), на оси ординат — $\mathrm {MSE} _{\mathrm {test} }$.
3. iii) Явно отметьте вертикальной линией интерполяционный порог $p=n$. Ожидается подъём ошибки около порога и улучшение при $p\gg n$ (double descent).
4. iv) Для корректности сопроводите графики таблицей с медианной ошибкой до, у и после порога; отдельно покажите, как ридж сглаживает пик.

Epoch-wise double descent на простой нейросети (подробные шаги)

a) Постановка эксперимента

1. i) Датасет: MNIST (60k/10k) или подмножество CIFAR-10 (напр., по 10k/10k). Нормализация входов к $[0,1]$ или стандартизация по каналам.
2. ii) Модель: однослойный MLP с шириной (напр., 2048) или минимальный CNN (2 свёрточных слоя + полносвязный). Выберите вместимость так, чтобы модель могла интерполировать обучающую выборку (обучающая ошибка близка к нулю).
3. iii) Оптимизация: SGD (или SGD+momentum), фиксированная скорость обучения $\eta$ (без scheduler), батч-сайз $|{\mathcal {B}}|\in \{64,128\}$. Регуляризацию (weight decay, dropout) отключить на базовом прогоне, чтобы не подавить эффект.
4. iv) (Опционально) Для усиления эффекта разрешается добавить 5–10% шумных меток в train (сделать отдельную серию, обязательно чётко маркировать).

b) Серии по числу эпох и съёмка кривых

1. i) Зафиксировав архитектуру и $\eta$, обучайте модели до большого числа эпох (напр., $E_{\max }=200$), сохраняя после каждой эпохи: train loss/accuracy и test loss/accuracy.
2. ii) Постройте кривые test error vs epochs. Для подавления шума используйте сглаживание (напр., экспоненциальное среднее с коэффициентом 0.9) и показывайте исходные точки.
3. iii) Ищите немонотонность: типичная картина — первичное снижение ошибки, затем подъём (переподгонка), затем повторное снижение (epoch-wise double descent). Если эффект не проявился, повторите с большей $\eta$ (на границе устойчивости) или с шумными метками.
4. iv) Для воспроизводимости выполните $R\geq 5$ прогонов (разные сиды инициализации и перетасовки батчей) и покажите медиану/диапазон.

c) Отчётность и воспроизводимость

1. i) Все графики снабжайте подписями, указывайте $n,p,\eta ,|{\mathcal {B}}|,E_{\max }$, архитектуру, наличие/отсутствие label noise.
2. ii) Код сопровождайте README с командами запуска и фиксируйте версии библиотек. Численные эксперименты выполнять в float64, если позволяет память.
3. iii) Итоговый отчёт обязательно набрать в LaTeX: включить таблицу конфигураций, краткую сводку статистик (медиана/IQR), и раздел Ограничения и угрозы валидности (напр., чувствительность к сидовому шуму).

Ожидаемый результат

1. Отчёт (PDF), набранный в LaTeX (20–30 страниц без приложений), содержащий:
   • введение: определения (интерполяционный порог, double descent по размеру/по эпохам, benign overfitting, SGD как стационарный стохастический процесс, catapult/edge of stability);
   • описание и результаты экспериментов:
     • линейная регрессия: кривые $\mathrm {MSE} _{\mathrm {test} }$ vs $p$ (или $p/n$) с отметкой $p=n$, статистика по $R$ сидами (медиана/IQR), сравнение с ridge;
     • нейросеть: кривые test error vs epochs (включая случаи, когда вторичный спад проявляется/не проявляется), все гиперпараметры указаны;
     • динамика SGD: классификация режимов (стабильность/катапульта/разлёт), оценка резкости и проверка соотношения $\lambda _{\max }\approx 2/\eta$ (полный батч), влияние $|{\mathcal {B}}|$ на шум/обобщение;
     • фазовая диаграмма на сетке $(\eta ,|{\mathcal {B}}|)$ с наложением уровней тестовой ошибки и пометкой областей, где наблюдается double descent.
   • аналитическое обсуждение: сопоставление наблюдений с механизмами из литературы + ограничения/воспроизводимость.
3. Исходники отчёта: .tex (+ .bib, если используется biblatex), а также все рисунки/таблицы, использованные в PDF.
5. Репозиторий с кодом, обеспечивающий воспроизводимость:
   • requirements.txt (или environment.yml);
   • единый скрипт запуска экспериментов run_all.py (или эквивалентный);
   • README с инструкцией запуска и указанием фиксированных seed;
   • сохранение результатов (графики, таблицы, конфиги) в отдельную папку (results/ или out/).
7. Приложение (в отчёте или отдельным файлом): дополнительные графики/таблицы (в т. ч. ablation’ы по $\eta$, $|{\mathcal {B}}|$, label-noise) и/или листинги ключевых частей кода (оценка резкости, построение фазовой диаграммы).

Научный руководитель

ФИО: Мокаев Тимур Назирович [e-mail][Telegram]