WAVE: ускоренный консенсус на медленно меняющихся графах
Распределенная оптимизация продолжает развиваться. В децентрализованной оптимизации агенты обмениваются информацией с соседями по графу, т.е. нет единого оркестратора и не применяется All-Reduce.
Тема переменного во времени графа (time-varying graph) появилась в конце 2000-х гг. в работах Анжелии Недич, и к настоящему моменту нашим коллегой Дмитрием Ковалевым уже получены оптимальные оценки сложности для произвольно меняющегося графа. Оказалось, что на меняющемся графе ускоренный консенсус невозможен, даже если на одной итерации меняются всего два ребра! (этот результат также получен в нашей лаборатории Дмитрием Метелевым)
Однако в реальной жизни сеть, через которую коммуницируют агенты, меняется медленно, постепенно, а не скачком. Можно ли улучшить оценки в этом случае? В новой статье, поданной на ICLR, обсуждается этот вопрос.