Задача распределенной оптимизации с консенсусом по части переменных: преимущества новой постановки

Распределенная оптимизация уже сравнительно давно выделилась в отдельное направление теории оптимизации. Она широко используется в самых разных задачах, таких как распределенное оценивание, машинное обучение на больших данных и т.п. В основе распределенных алгоритмов лежит идея локального взаимодействия агентов, каждый из которых ассоциирован с фрагментом общей целевой функции. Агенты связаны в сеть, описываемую графом (или его Лапласовской матрицей). В стандартном сценарии, наиболее изученном в литературе, локальные функции зависят от общего набора переменных и, следовательно, обмениваются всем вектором переменных на каждом раунде взаимодействия. Однако иногда встречаются сценарии, в которых каждая локальная функция зависит только от некоторого подмножества переменных. В нашей работе мы предлагаем подход, позволяющий обобщить алгоритмы распределенной оптимизации на данный случай. Наш метод состоит в том, чтобы построить другую Лапласовскую матрицу и тем самым обеспечить не только уменьшение коммуникационной нагрузки, но и во многих случаях гарантировать более высокую скорость сходимости.