Краткое содержание

arXiv:2405.03472v4 Тип объявления: replace-cross Аннотация: С целью понимания поведения алгоритма Alternating Mirror Descent (AMD) для билинейных игр с нулевой суммой мы исследуем дискретизацию потока Гамильтона в непрерывном времени с помощью симплектического метода Эйлера. Мы представляем аналитический подход, использующий результаты из гамильтоновой динамики, алгебры Ли и симплектических численных методов, с акцентом на существование и свойства сохраняющейся величины — модифицированного гамильтониана (МГ) — для симплектического метода Эйлера. Мы вычисляем МГ в замкнутой форме, когда исходный гамильтониан является квадратичной функцией, и показываем, что в общем случае он отличается от другой известной сохраняющейся величины для этого случая. Мы выводим новые оценки погрешности МГ при его усечении до различных порядков шага в зависимости от числа итераций, $K$, и используем эти оценки, чтобы показать улучшенную общую оценку регрета $\mathcal{O}(K^{1/5})$ и оценку двойственного разрыва для средних итератов $\mathcal{O}(K^{-4/5})$.