Speaker
Dmitry Metelev
Description
Мы рассматриваем задачу децентрализованной оптимизации, где каждый агент имеет сильно выпуклую и гладкую функцию, а целью сети является минимизация суммы всех функций по узлам. В данной постановке можно рассматривать как статическую, так и изменяющуюся во времени сеть. В обоих случаях существуют оптимальные алгоритмы, нижние границы которых выражаются через $\chi$, число обсуловленности сети. Недавно были получены некоторые нижние оценки для задачи децентрализованной оптимизации при различных асимптотических ограничениях на скорость изменения сети. В данной работе мы показываем, что при константных ограничениях нижние границы такие же, как и в случае изменяющейся во времени сети, тем самым улучшая существующие результаты.
