Минимаксная оптимизация на медленно меняющихся графах

Распределенная оптимизация – важное направление исследований в современной теории оптимизации. Ее приложения включают машинное обучение на больших данных, распределенную обработку сигналов и другие области. В статье исследуется децентрализованная оптимизация для седловых задач. Седловые задачи возникают при обучении генеративно-состязательных сетей, а также в робастном машинном обучении. Основное внимание в работе уделяется оптимизации на медленно меняющихся сетях. Топология сети меняется время от времени, и скорость этих изменений ограничена. В работе показано, что достаточно изменять два ребра на каждой итерации для того, чтобы замедлить сходимость метода оптимизации до случая, когда граф меняется произвольным образом. Одновременно с этим исследуются несколько классов меняющихся сетей, для которых коммуникационная сложность может быть уменьшена.