Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometry

💡 О чём статья?
Большая часть теории оптимизации живёт в комфортном мире:
· шум считается i.i.d.
· пространство (геометрия) евклидово
· SGD / Adam с обычным батчированием «как-нибудь работает»
Но в реальных задачах всё иначе.

В reinforcement learning, distributed systems и online-обучении шум зависим во времени и имеет марковскую структуру, а параметры живут в сложных пространствах: симплексах, шариках в разных нормах, странных многообразиях.

Классическая теория тут либо ломается, либо дает заведомо неоптимальные гарантии.

⚠️ Почему это проблема?
Такая «неидеальная» стохастика возникает повсеместно:
🤖 Reinforcement learning данные приходят из траекторий Марковской цепи
📡 Distributed / decentralized optimization зависимые обновления и задержки
📊 Policy optimization вероятностные политики живут не во всем пространстве, а на симплексе

🎯 Что мы предлагаем?
Мы строим единую теорию оптимизации, которая одновременно учитывает:
🧩 Марковский шум (через “правильное” MLMC батчирование)
📐 Произвольную геометрию (arbitrary norms + Bregman divergences)
🔄 Обобщенные постановки (минимизация + вариационные неравенства)

Ключевые результаты:
- Оптимальные оценки (Markovian Accelerated Mirror Descent, Markovian Mirror Prox)
- Единственный в литературе анализ MLMC-батчинга в произвольной норме (на самом деле и обычного батчинга тоже)


✨ Почему это важно?
· Теория ближе к реальным задачам
· Работает за пределами евклидовой геометрии
· Дает оптимальные гарантии
· Закрывает разрыв между классической оптимизацией и практикой

Эксперименты на RL-задачах подтверждают: методы не только «красивые на бумаге», но и конкурентоспособны на практике.

📊 Подробности, алгоритмы, теоремы и эксперименты — в статье

🔗 Статья
💻 Код

#разборстатьи