Градиентный спуск при больших шагах: хаос и фрактальная область сходимости

Тема курсовой работы (1 курс, направление «ПМИИ»).

Мотивация

При больших шагах обучения (learning rate) итерации градиентного спуска в невыпуклых моделях могут демонстрировать сложную и даже хаотическую динамику: чувствительность к инициализации, периодические и квазипериодические режимы, а также фрактальную границу области сходимости. Недавние строгие результаты для (глубокой) матричной факторизации показывают существование критического шага, ниже которого сходимость описывается гладкой областью, а в окрестности критичности возникает хаотический режим с положительной топологической энтропией и фрактальными границами бассейнов притяжения. Цель курсовой — аккуратно разобрать эти факты на простых задачах, воспроизвести эксперименты и внимательно сопоставить наблюдаемую дискретную динамику с классическими понятиями теории динамических систем.

Задание

1. Аналитическое чтение и конспект.
   • a) Внимательно прочитать основной источник (см. [1]). Кратко законспектировать: формулировки основных теорем (критический шаг сходимости в скалярно-векторной факторизации; чувствительность к инициализации; нижняя оценка топологической энтропии; фрактальная граница области сходимости с оценкой размерности), ключевые идеи доказательств (геометрия отображения обновления $\mathrm {GD} (\theta )=\theta -\eta \nabla L(\theta )$, покрывающая структура («накрывающее отображение») на компонентах параметрического пространства и др.).
   • b) Кратко сопоставить используемые понятия с классикой динамических систем: бассейны притяжения, фрактальные границы бассейнов, чувствительность к начальным условиям, топологическая энтропия.
3. Репликация минимального примера.
   • a) Реализовать в Python градиентный спуск для задачи

     $$L(u,v)={\frac {(uv-y)^{2}}{2}}+{\frac {\lambda }{2}}(u^{2}+v^{2})$$

     в $\mathbb {R} ^{2}$ (случаи $\lambda =0$ и $\lambda >0$).

   • b) Для фиксированного шага $\eta$ построить на равномерной сетке по $(u_{0},v_{0})$ карту принадлежности начальной точки бассейну сходимости/дивергенции и, при сходимости, идентификатор достигнутого минимума (цветовая разметка).
   • c) Визуализировать границу области сходимости и её самоподобие; эмпирически оценить (по счётчикам коробок) бокс-каунтинговую размерность границы (короткое описание методики и кода).
5. Чувствительность к инициализации и критический шаг.
   • a) Численно исследовать зависимость исхода (какой минимум выбирается, либо дивергенция) от малых возмущений начальной точки при $\eta$, близких к критическому значению (сравнить с теоретическими формулами из основного источника).
   • b) Построить гистограммы норм и «несбалансированности» найденных минимумов при сканировании мини-окрестностей на границе сходимости.
7. Переход к матричной факторизации.
   • a) Реализовать мелкую (глубина 2) матричную факторизацию

     $$L(U,V)={\frac {1}{2}}\|U^{\top }V-Y\|_{F}^{2}+{\frac {\lambda }{2}}{\big (}\|U\|_{F}^{2}+\|V\|_{F}^{2}{\big )}$$

     с ортогональной/идентичной инициализацией; воспроизвести срезы параметрического пространства и визуализации, аналогичные скалярному случаю.

   • b) Проверить, что наблюдаемая чувствительность и фрактальные структуры сохраняются (качественно) в выбранных срезах.
9. Сопоставление с близкими феноменами.
   • a) Кратко сопоставить полученные наблюдения с литературой об «границе устойчивости» (edge of stability) и «катапультной» динамике; отметить сходства и различия постановок.
   • b) Сопоставить результаты с классическими работами о фрактальных границах бассейнов притяжения.
11. Отчёт и репозиторий.
    • a) Подготовить отчёт в LaTeX (структура: введение, модель и методика, результаты экспериментов и визуализации, обсуждение, выводы).
    • b) Приложить полностью воспроизводимый код (Python, желателен requirements.txt / environment.yml) и README с инструкциями запуска.

Минимальные требования

Конспект с корректным изложением основных теорем; рабочий код и визуализации для скалярного случая с оценкой бокс-каунтинговой размерности границы; аккуратное сравнение с литературой.

Отчёт обязательно набирается в LaTeX.

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

1. S. Liang, G. Montúfar. Gradient Descent with Large Step Sizes: Chaos and Fractal Convergence Region. arXiv:2509.25351v2, 2025. Доказаны критический шаг сходимости, чувствительность к инициализации, нижняя оценка топологической энтропии и фрактальная геометрия границы сходимости в (глубокой) матричной факторизации. Доступ: https://arxiv.org/abs/2509.25351.
2. S. W. McDonald, C. Grebogi, E. Ott, J. A. Yorke. Fractal basin boundaries. Physica D 17(2), 125–153, 1985. Классика о фрактальных границах бассейнов притяжения.
3. H. E. Nusse, J. A. Yorke. Wada basin boundaries and basin cells. Physica D 90(3), 242–261, 1996. Классика о границах Вада.
4. K. Falconer. Fractal Geometry: Mathematical Foundations and Applications. 3rd ed., Wiley, 2014. Базовые методы оценки фрактальной размерности (в т.ч. бокс-каунтинг).
5. R. L. Devaney. An Introduction to Chaotic Dynamical Systems. 2nd ed., Westview, 2003. Вводные главы по хаосу и чувствительности к начальным условиям.
6. J. Cohen, S. Kaur, Y. Li, J. Z. Kolter, A. Talwalkar. Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability. ICLR, 2021. Современный контекст «границы устойчивости».
7. A. Lewkowycz, G. Gur-Ari, E. Dyer. The large learning rate phase of deep learning: the catapult mechanism. arXiv:2003.02218, 2020. Про «катапультную» динамику при больших шагах.
8. X. Chen, K. Balasubramanian, P. Ghosal, B. K. Agrawalla. From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression. TMLR, 2024. Строгий анализ перехода к хаосу в простой модели.

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

1. Отчёт (PDF), набранный в LaTeX, содержащий:
   • конспект ключевых теорем и идей доказательств из [1] (включая критический шаг, чувствительность к инициализации, топологическую энтропию, фрактальную геометрию границы);
   • результаты репликации минимального примера в $\mathbb {R} ^{2}$ для $\lambda =0$ и $\lambda >0$ (карты бассейнов сходимости/дивергенции на сетке по $(u_{0},v_{0})$);
   • визуализации границы области сходимости и демонстрации самоподобия;
   • оценку бокс-каунтинговой размерности границы (описание метода + графики/таблица);
   • эксперименты по чувствительности к инициализации вблизи критического $\eta$ (включая гистограммы норм и «несбалансированности» минимумов);
   • расширение на матричную факторизацию глубины 2 с качественно аналогичными визуализациями в выбранных срезах;
   • краткое сопоставление с «edge of stability», «catapult mechanism» и классическими работами о фрактальных/Вада-границах.
3. Полностью воспроизводимый код (Python) и материалы запуска:
   • requirements.txt или environment.yml, фиксированные seed;
   • скрипты генерации карт/графиков и расчёта бокс-каунтинговой размерности;
   • README с командами для полного воспроизведения всех рисунков/таблиц из отчёта.

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

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