Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 158-168

1. ВВЕДЕНИЕ

В данной статье изучаются задачи минимаксной оптимизации типа

где функции ${{f}_{m}}(x,y)$ выпуклы по x и вогнуты по y, а $\mathcal{X},\;\mathcal{Y}$ – замкнутые выпуклые множества. Каждая функция ${{f}_{m}}(x,y)$ хранится локально на некотором компьютере. Пусть эти компьютеры соединены друг с другом через децентрализованную коммуникационную сеть. Каждый компьютер может выполнять локальные вычисления и обмениваться информацией со своими непосредственными соседями в сети. Кроме того, сеть может меняться со временем. Из-за некоторых сбоев или помех связи в сети могут время от времени выходить из строя или появляться вновь. Этот тип сетей называется меняющимися графами.

У оптимизации на меняющихся графах существует множество приложений [13, 15]. К ним относятся распределенное машинное обучение [5, 14, 16], распределенное управление энергетическими системами [6, 17], управление группой автономных транспортных средств [18], управление распределенными системами сенсоров [1].

Методы децентрализованной оптимизации и минимаксной оптимизации первого порядка используют два типа шагов: локальные градиентные шаги и коммуникации между вычислительными машинами. Мы рассматриваем случай, когда коммуникация осуществляется синхронизированными раундами. Поэтому сложность метода измеряется двумя величинами: количество коммуникационных раундов и количество вызовов локального оракула. Эти величины зависят от характеристик задачи, к которым относятся число обусловленности сети $\chi $, число обусловленности функции $L{\text{/}}\mu $ и желаемая точность $\varepsilon $. Здесь $L$ – константа Липшица градиента целевой функции, а $\mu $ – константа сильной выпуклости.

Данная статья посвящена медленно меняющимся графам. Это означает, что после каждого шага обмена данными может меняться только ограниченное количество ребер. Мы приводим нижние оценки сложности для рассматриваемого класса задач. Также мы предлагаем методы минимаксной оптимизации с улучшенной коммуникационной сложностью для двух конкретных классов медленно меняющихся сетей.

Для оптимизации по сетям (не минимаксной) известны нижние оценки, а также соответствующие оптимальные алгоритмы. Для постоянных графов нижние оценки были получены в [19], и в той же статье был предложен оптимальный двойственный (т.е. с использованием двойственного оракула) алгоритм. Оптимальные децентрализованные методы с использованием прямого оракула были предложены в [9]. Для меняющихся графов (с произвольными изменениями на каждой итерации) в [8] были предложены нижние оценки сложности. Оптимальный алгоритм с прямым оракулом был предложен в той же статье [8], а оптимальный двойственный метод впервые появился в [10]. После этого в [12] были изучены нижние оценки для медленно меняющихся графов с разными скоростями изменений сети. В [11] было показано, что достаточно менять только два ребра на каждой итерации, чтобы сделать сложность коммуникации равной случаю произвольной меняющейся сети. Обзор нижних оценок для децентрализованной оптимизации представлен в табл. 1 (обозначение $\Omega ( \cdot )$ опущено).

Результаты для децентрализованных седловых задач аналогичны стандартной децентрализованной оптимизации. Нижние оценки для минимаксной оптимизации по статическим графам приведены в [4]. В той же статье [4] предложены алгоритмы, оптимальные с точностью до логарифмического члена. Случай (произвольных) меняющихся графов изучался в [2] вместе с методами, оптимальными с точностью до логарифмического множителя. Оптимальные алгоритмы для вариационных неравенств типа суммы (обобщение седловых задач) были предложены в [7]. Наконец, в этой статье изучаются нижние оценки для седловых задач на медленно меняющихся графах (только два ребра меняются за итерацию). Соответствующие результаты представлены в табл. 2. Стоит отметить, что нижние границы сложности такие же, как и для оптимизации (табл. 1), за исключением замены $\sqrt {L{\text{/}}\mu } $ на $L{\text{/}}\mu $.

Данная статья организована следующим образом. В разделе 2 мы вводим необходимые предположения и обозначения. После этого в разделе 3 мы покажем, как добиться ускорения по коммуникациям, используя дополнительные предположения о изменяющейся сети. В разделе 4 мы приводим нижние оценки для медленно меняющихся сетей.

2. ОБОЗНАЧЕНИЯ И ПРЕДПОЛОЖЕНИЯ

Гладкость и сильная выпуклость

Мы рассматриваем задачу (1), где множества $\mathcal{X} \subseteq {{\mathbb{R}}^{{{{n}_{x}}}}}$ и $\mathcal{Y} \subseteq {{\mathbb{R}}^{{{{n}_{y}}}}}$ являются замкнутыми и выпуклыми. Кроме того, мы вводим множество $\mathcal{Z} = \mathcal{X} \times \mathcal{Y} \subseteq {{\mathbb{R}}^{{{{n}_{z}}}}}$, $z = (x,y)$, ${{n}_{z}} = {{n}_{x}} + {{n}_{y}}$, и оператор F:

Предположение 1. Пусть функции $f(x,y)$ и ${{f}_{m}}(x,y)$ удовлетворяют следующим условиям:

1. Функция $f(x,y)$ является $L$-гладкой, т.е. для всех ${{z}_{1}},{{z}_{2}} \in \mathcal{Z}$ выполнено

2. Для любого $m$, ${{f}_{m}}(x,y)$ является ${{L}_{{{\text{max}}}}}$-гладкой, т.е. для всех ${{z}_{1}},{{z}_{2}} \in \mathcal{Z}$ выполнено

3. Функция $f(x,y)$ является сильно выпуклой-сильно вогнутой с константой $\mu $, т.е. для всех ${{z}_{1}},{{z}_{2}} \in \mathcal{Z}$ выполнено

Децентрализованная коммуникация

На каждом шаге обмена данными мы используем граф для представления соединения между вычислительными машинами. Обозначим коммуникационную сеть, меняющуюся во времени, последовательностью графов $\{ {{\mathcal{G}}^{k}}\} _{{k = 0}}^{\infty }\, = \,\{ (\mathcal{V},{{\mathcal{E}}^{k}})\} _{{k = 0}}^{\infty }$, где $\mathcal{V} = \{ 1, \ldots ,M\} $ – множество узлов (каждый узел соответствует одному компьютеру), а ${{\mathcal{E}}^{k}}$ – множество доступных соединений на k-м коммуникационном раунде. Для каждого узла $m \in \mathcal{V}$, мы используем $\mathcal{N}_{m}^{k} = \{ i \in \mathcal{V}\,{\text{|}}\,(i,m) \in {{\mathcal{E}}^{k}}\} $ для обозначения множества его соседей на k-м раунде, и в это время он может взаимодействовать только с узлами в $\mathcal{N}_{m}^{k}$.

Матрицы коммуникации. Каждый узел m содержит свой локальный вектор ${{z}_{m}} = ({{x}_{m}},{{y}_{m}})$. Требуется удовлетворить ограничения консенсуса ${{z}_{1}} = \ldots = {{z}_{M}}$. Для этой цели мы используем матрицы коммуникации.

Предположение 2. Каждый граф в коммуникационной сети соответствует матрице ${{W}^{k}} \in {{\mathbb{R}}^{{M \times M}}}$, которая удовлетворяет следующим свойствам.

1. ${{W}^{k}}$ является положительно полуопределенной,

2. $W_{{i,j}}^{k} = 0$ если $i \ne j$ и $(i,j) \notin {{\mathcal{E}}^{k}}$,

3. $\ker {{W}^{k}} = {\text{span}}({\mathbf{1}})$, где ${\mathbf{1}} = (1, \ldots ,1) \in {{\mathbb{R}}^{M}}$.

Число $\chi (W) = \frac{{{{\lambda }_{{\max }}}(W)}}{{\lambda _{{\min }}^{ + }(W)}}$ называется числом обусловленности матрицы W, где ${{\lambda }_{{\max }}}(W)$ и $\lambda _{{\min }}^{ + }(W)$ обозначают соответственно наибольшее и наименьшее положительные собственные значения матрицы коммуникации W. Для меняющейся сети $\{ {{\mathcal{G}}^{k}}\} _{{k = 1}}^{\infty }$, число обусловленности имеет вид χ = = $\mathop {\sup }\limits_{k \in \mathbb{N} \cup \{ 0\} } \frac{{{{\lambda }_{{\max }}}({{W}^{k}})}}{{{{\lambda }_{{\min }}}({{W}^{k}})}}$.

В этой статье мы рассматриваем матрицы Лапласа ${\mathbf{L}}({{\mathcal{G}}^{k}})$, которые являются типичным примером матрицы коммуникации.

Мы вводим консенсусное подпространство $\mathcal{L}\, \subseteq \,{{\mathbb{R}}^{{M{{n}_{z}}}}}$, определенное как

Рассмотрим также пространство ${{\mathcal{L}}^{ \bot }} \subseteq {{\mathbb{R}}^{{M{{n}_{z}}}}}$ которое является ортогональным дополнением к пространству $\mathcal{L}$, определенное как

3. ВЕРХНИЕ ОЦЕНКИ

В этом разделе мы рассмотрим два класса меняющихся во времени сетей: сети со связным остовом и сети с небольшими случайными марковскими изменениями. Для обоих сценариев мы предлагаем децентрализованный алгоритм оптимизации, использующий вспомогательную процедуру консенсуса. Показано, что для рассмотренных классов задач зависимость сложности коммуникации от фактора $\chi $ можно свести от $\chi $ до $\sqrt \chi $ с дополнительными слагаемыми. Обзор результатов представлен в табл. 3 (обозначение O(⋅) опущено).

Наши алгоритмы основаны на экстраградиентном методе с консенсусной процедурой. После каждого экстраградиентного шага они совершают несколько раундов общения. После достаточного количества сообщений достигается консенсус с желаемой точностью. Такое приближенное усреднение делает траектории вычислительных машин практически синхронизированными. Для каждого класса меняющихся во времени сетей мы используем соответствующую процедуру консенсуса и включаем ее в экстраградиентный метод, чтобы получить децентрализованный алгоритм оптимизации.

Ускоренный консенсус для графов со связным остовом и невосстанавливаемыми ребрами

Рассмотрим тип графов со связным остовом. Мы предполагаем, что все графы в последовательности имеют общий связный подграф, который мы называем связным остовом. Ребра по-прежнему могут появляться и исчезать, но каждая машина запоминает, какие инцидентные ей ребра хотя бы раз вышли из строя, и прекращает связь по этим направлениям. Эту стратегию мы называем невосстанавливаемые ребра. Фактически сеть связи только теряет ребра на каждой итерации, но остается связной. Другими словами, интересующую последовательность графов можно назвать “монотонно убывающей”.

Предположение 3 Последовательность графов $\{ {{\mathcal{G}}^{k}}\, = \,(\mathcal{V},{{\mathcal{E}}^{k}})\} _{{q = 0}}^{\infty }$ имеет связный остов: существует связный граф $\hat {\mathcal{G}}\, = \,(\mathcal{V},\hat {\mathcal{E}})$ такой, что для всех $k\, \in \,\mathbb{N}\, \cup \,\{ 0\} $ имеем $\hat {\mathcal{E}}\, \subset \,{{\mathcal{E}}^{k}}$, ${{\lambda }_{{{\text{max}}}}}({\mathbf{L}}({{\mathcal{G}}^{k}}))\;\leqslant \;{{\lambda }_{{{\text{max}}}}}$ и $\lambda _{{{\text{min}}}}^{ + }\,\leqslant \,\lambda _{{{\text{min}}}}^{ + }(\hat {\mathcal{G}})$.

Учитывая эти свойства сети, мы вводим следующий алгоритм консенсуса.

Algorithm 1. Ускоренный консенсус с невосстанавливаемыми ребрами (AccGossipNonRecoverable)

Вход: Векторы ${{z}_{1}}, \ldots ,{{z}_{M}}$, количество итераций H, текущий раунда связи ${{k}_{0}}$. Размеры шага $\eta ,\beta > 0$

  1: Построить вектор-столбец ${\mathbf{z}} = (z_{1}^{T} \ldots z_{M}^{T}{{)}^{T}}$

  2: Пусть u⁰ = z⁰ = z

  3: Каждая машина $i = 1,2, \ldots ,M$ инициализирует набор соседей ${{\mathcal{N}}_{i}} = \mathcal{N}_{i}^{{{{k}_{0}}}}$

  4: for $k = 0,1, \ldots ,H - 1$ do

  5:    for $i = 1,2, \ldots ,M$ do

  6:      Обновить набор машин, с которыми общается машина: ${{\mathcal{N}}_{i}} = {{\mathcal{N}}_{i}} \cap \mathcal{N}_{i}^{{{{k}_{0}} + k}}$

  7:      $u_{i}^{{k + 1}} = z_{i}^{k} - \eta \left( {{\text{|}}{{\mathcal{N}}_{i}}{\text{|}}z_{i}^{k} - \sum\limits_{j \in {{\mathcal{N}}_{i}}}^{} {z_{j}^{k}} } \right)$

  8:      $z_{i}^{{k + 1}} = (1 + \beta )u_{i}^{{k + 1}} - \beta u_{i}^{k}$

  9:    end for

  10: end for

  11: return $z_{1}^{H}, \ldots z_{M}^{H}$

Лемма 1 (Из доказательства теоремы 4.3 в [12]). Пусть предположение 3 выполнено и $\{ {{\hat {z}}_{M}}\} _{{m = 1}}^{M}$ будет выходом алгоритма 1 с входом $\{ {{z}_{m}}\} _{{m = 1}}^{M}$ и размеры шага $\eta = 1{\text{/}}{{\lambda }_{{\max }}}$, $\beta = (\sqrt \chi - 1){\text{/}}(\sqrt \chi + 1)$, где χ = = ${{\lambda }_{{\max }}}{\text{/}}\lambda _{{\min }}^{ + }$. Тогда после H итераций имеем следующее неравенство

где $\bar {z} = \frac{1}{M}\sum\limits_{m = 1}^M {{{z}_{m}}} $.

На основе алгоритма 1 можно разработать децентрализованный алгоритм решения седловой задачи 1 с последовательностью графов, имеющих связный остов и невосстанавливаемые ребра.

Теорема 1. Пусть выполнены предположения 1 и 3. Пусть задача (1) решается алгоритмом 2 с $\gamma \;\leqslant \;\frac{1}{{4{{L}_{{\max }}}}}$. Тогда, чтобы достигать консенсуса с точностью ${{\varepsilon }_{0}}$ на каждой итерации, требуется

где ${{Q}^{2}} = \frac{1}{M}\sum\limits_{m = 1}^M {{\text{||}}{{F}_{m}}(z{\kern 1pt} *){\text{|}}{{{\text{|}}}^{2}}} $ и z* является решением (1).

Доказательство. Пусть после k итераций достигнута точность консенсуса ${{\varepsilon }_{0}}$, т.е.

Algorithm 2. Экстраградиентный метод на переменных сетях с невосстанавливаемыми ссылками

Вход: Размер шага $\gamma > 0$; количество AccGossipNonRecoverable шагов H, количество раундов коммуникации $K$, количество итераций N

1: Выбрать $({{x}^{0}},{{y}^{0}}) = {{z}^{0}} \in \mathcal{Z}$, $z_{m}^{0} = {{z}^{0}}$

2: for $k = 0,1,2, \ldots ,N - 1$ do

3:       Каждая машина m вычисляет $\hat {z}_{m}^{{k + 1/2}} = z_{m}^{k} - \gamma \cdot {{F}_{m}}(z_{m}^{k})$

4:       Коммуникация: $\tilde {z}_{1}^{{k + 1/2}}, \ldots ,\tilde {z}_{M}^{{k + 1/2}}$ = AccGossipNonRecoverable$(\hat {z}_{1}^{{k + 1/2}}, \ldots ,\hat {z}_{M}^{{k + 1/2}},H)$

5:       Каждая машина m вычисляет $z_{m}^{{k + 1/2}} = {\text{pro}}{{{\text{j}}}_{\mathcal{Z}}}(\tilde {z}_{m}^{{k + 1/2}}$)

6:       Каждая машина m вычисляет $\hat {z}_{m}^{{k + 1}} = z_{m}^{k} - \gamma \cdot {{F}_{m}}(z_{m}^{{k + 1/2}})$

7:       Коммуникация: $\tilde {z}_{1}^{{k + 1}}, \ldots ,\tilde {z}_{M}^{{k + 1}}$ = AccGossipNonRecoverable$(\hat {z}_{1}^{{k + 1}}, \ldots ,\hat {z}_{M}^{{k + 1}},H)$

8:       Каждая машина m вычисляет $z_{m}^{{k + 1}} = {\text{pro}}{{{\text{j}}}_{\mathcal{Z}}}(\tilde {z}_{m}^{{k + 1}})$

9: end for

Введем обозначения:

и

Имеем

Пусть $T = 2\chi {{\left( {1 - \frac{1}{{\sqrt \chi }}} \right)}^{H}}$. Тогда

С другой стороны,

Пусть ${{Q}^{2}} = \frac{1}{M}\sum\limits_{m = 1}^M {{\text{||}}{{F}_{m}}(z{\kern 1pt} *){\text{|}}{{{\text{|}}}^{2}}} $, тогда имеем

Если положить

то

Аналогично получается точно такая же оценка для H, дающая

Следовательно, для достижения точности ${{\varepsilon }_{0}}$, необходимо выполнить

коммуникаций.

Теорема 2 (Теорема 6 в [3]). Пусть ${{\{ z_{m}^{k}\} }_{{k \geqslant 0}}}$ – итерации алгоритма 2 для решения задачи (1). Пусть выполняются предположения 1, 3. Тогда, если $\gamma \;\leqslant \;\frac{1}{{4{{L}_{{\max }}}}}$, имеем следующие оценки

Следствие 2.1. В условиях теоремы 1 и теоремы 2, если $H = \mathcal{O}\left( {\sqrt \chi \log \chi \log (1{\text{/}}\varepsilon )} \right)$, тогда количество коммуникационных раундов, требующихся алгоритму 2 для достижения точности $\varepsilon $, ограничено сверху следующим выражением:

и количество локальных вычислений на каждом устройстве не превосходит

Консенсус в сетях с марковскими изменениями

Данный раздел посвящен медленно меняющимся графам со случайными изменениями. На каждой итерации несколько случайно выбранных ребер появляются или исчезают. Выбор ребер зависит только от текущей топологии графа, поэтому последовательность графов является марковским процессом.

Введем предположения на переменный граф с марковскими изменениями.

Предположение 4. Коммуникационная сеть удовлетворяет следующим условиям.

1. $\{ {{W}^{k}}\} _{{k = 0}}^{\infty }$ является стационарной марковской цепью на $({{W}_{G}},{{W}_{\sigma }})$, где ${{W}_{G}}$ – набор всевозможных матриц коммуникации, ${{W}_{\sigma }}$ – $\sigma $-поле над ${{W}_{G}}$ и цепь $\{ {{W}^{k}}\} _{{k = 0}}^{\infty }$ имеет марковское ядро Q и единственное стационарное распределение $\pi $.

2. Q является равномерно геометрически эргодичным со временем перемешивания $\tau \in \mathbb{N}$, т.е. для каждого $m \in \mathbb{N}$,

3. Для всех $k\, \in \,\mathbb{N}\, \cup \,\{ 0\} $ выполняется ${{\mathbb{E}}_{\pi }}[W(q)]\, = \,\bar {W}$ и $\bar {W}$ удовлетворяет предположению 2.

Обозначим ${{\lambda }_{{\max }}} = {{\lambda }_{{\max }}}(\bar {W})$, $\lambda _{{\min }}^{ + } = \lambda _{{\min }}^{ + }(\bar {W})$, $\chi = \frac{{{{\lambda }_{{\max }}}}}{{{{\lambda }_{{\min }}}}}$.

4. Для всякого графа $\mathcal{G}$ в последовательности сетей выполняется:

Рассмотрим следующую задачу поиска консенсуса

где ${\mathbf{z}} = (z_{1}^{T}, \ldots ,z_{M}^{T}{{)}^{T}}$.

Algorithm 3. Ускоренный консенсус для графов с марковскими изменениями (ACOGWMC)

Вход: Размер шага $\gamma > 0$, коэффициенты инерции $\theta ,\;\eta ,\;\beta ,\;p$, количество итераций $N$, предельный             размер батча $S$

1:       Выбрать $z_{f}^{0} = {{z}^{0}}$, ${{T}^{0}} = 0$, одинаково инициализировать генератор случайных чисел $\{ {{J}_{k}}\} $ на всех             устройствах

2:        for $k = 0,1, \ldots ,N - 1$ do

3:              $z_{g}^{k} = \theta z_{f}^{k} + (1 - \theta ){{z}^{k}}$

4:             Сгенерировать ${{J}_{k}} \sim {\text{Geom}}(1{\text{/}}2)$

5:             Разослать $z_{g}^{k}$ соседям в сетях $\{ {{\mathcal{G}}^{{{{T}^{k}} + i}}}\} _{{i = 1}}^{{{{2}^{{^{{{{J}_{k}}}}B}}}}}$

6:              Вычислим ${{g}^{k}} = g_{0}^{k} + \left( \begin{gathered} {{2}^{{{{J}_{k}}}}}(g_{{{{J}_{k}}}}^{k} - g_{{{{J}_{k}} - 1}}^{k}),\quad {\text{если}}\;{{2}^{{{{J}_{k}}}}}\;\leqslant \;S \hfill \\ 0,\quad {\text{иначе}} \hfill \\ \end{gathered} \right.$

             с $g_{j}^{k}{{ = 2}^{{ - j}}}{{B}^{{ - 1}}}\sum\limits_{i = 1}^{{{2}^{j}}B} {{{W}^{{{{T}^{k}} + i}}}z_{g}^{k}} $

7:              $z_{f}^{{k + 1}} = z_{g}^{k} - p\gamma {{g}^{k}}$

8:              ${{z}^{{k + 1}}} = \eta z_{f}^{{k + 1}} + (p - \eta )z_{f}^{k} + (1 - p)(1 - \beta ){{z}^{k}} + (1 - p)\beta z_{g}^{k}$

9:              ${{T}^{{k + 1}}} = {{T}^{k}} + {{2}^{{{{J}_{k}}}}}B$

10: end for

Теорема 3 (Теорема 1 из [11]). Пусть выполнены предположения 4. Пусть задача (5) решается алгоритмом 3. Тогда для любого $b \in \mathbb{N}$,

и $\beta ,\;\theta ,\;\eta ,\;p,\;S,\;B$, удовлетворяющих выполняется где $z_{M}^{*} = \frac{1}{M}\sum\limits_{i = 1}^M {{{z}_{i}}} $ для $m = 1, \ldots ,M$.

Следствие 3.1. В предположениях теоремы 3, если $b = \tau $ и $\gamma \simeq {\text{min}}\left\{ {\frac{1}{{{{\lambda }_{{{\text{max}}}}}}};\frac{{\lambda _{{{\text{min}}}}^{3}}}{{{{\rho }^{4}}}}} \right\}$, тогда для достижения решения с точностью $\varepsilon $ (в терминах $\mathbb{E}[{\text{||}}z - z{\kern 1pt} *{\text{|}}{{{\text{|}}}^{2}}] \lesssim \varepsilon $) требуется

Algorithm 4. Экстраградиентный метод на переменных сетях с марковскими изменениями

Вход: Размер шага $\gamma \;\leqslant \;\frac{1}{{4L}}$, количество ACOGWMC шагов $H$, количество итераций N

  1: Выбрать $({{x}^{0}},{{y}^{0}}) = {{z}^{0}} \in \mathcal{Z}$, $z_{m}^{0} = {{z}^{0}}$

  2: for k = 0, 1, 2, ..., N do

  3:  Каждая машина $m$ вычисляет $\hat {z}_{m}^{{k + 1/2}} = z_{m}^{k} - \gamma \cdot {{F}_{m}}(z_{m}^{k})$

  4:  Коммуникация: $\tilde {z}_{1}^{{k + 1/2}}, \ldots ,\tilde {z}_{M}^{{k + 1/2}}$ = ACOGWMC$(\hat {z}_{1}^{{k + 1/2}}, \ldots ,\hat {z}_{M}^{{k + 1/2}},H)$

  5:  Каждая машина m вычисляет $z_{m}^{{k + 1/2}} = {\text{pro}}{{{\text{j}}}_{\mathcal{Z}}}(\tilde {z}_{m}^{{k + 1/2}}$)

  6:  Каждая машина m вычисляет $\hat {z}_{m}^{{k + 1}} = z_{m}^{k} - \gamma \cdot {{F}_{m}}(z_{m}^{{k + 1}})$

  7:  Коммуникация: $\tilde {z}_{1}^{{k + 1}}, \ldots ,\tilde {z}_{M}^{{k + 1}}$ = ACOGWMC$(\hat {z}_{1}^{{k + 1}}, \ldots ,\hat {z}_{M}^{{k + 1}},H)$

  8:  Каждая машина m вычисляет $z_{m}^{{k + 1}} = {\text{pro}}{{{\text{j}}}_{\mathcal{Z}}}(\tilde {z}_{m}^{{k + 1}}$)

  9: end for

Теорема 4. Пусть выполнены предположения 1, 4. Пусть проблема (1) решается алгоритмом 4. Тогда, если $\gamma \,\leqslant \,\frac{1}{{4{{L}_{{\max }}}}}$ и H = $\mathcal{O}\left( {\tau \left[ {\sqrt \chi \, + \,\frac{{{{\rho }^{2}}}}{{\lambda _{{{\text{min}}}}^{2}}}{\text{log}}\frac{1}{\varepsilon }} \right]} \right)$, то для достижения $\varepsilon $-решения (такого что $\mathbb{E}[f(z)\, - \,f(z{\kern 1pt} *)]\, \lesssim \,\varepsilon $) требуется

4. НИЖНИЕ ОЦЕНКИ

Предыдущий раздел был посвящен применению новых алгоритмов консенсуса для конкретных типов меняющихся сетей: сетей со связным остовом и графам, меняющимся по марковскому закону. В этом разделе мы покажем, что без конкретных ограничений на сети, таких как связный остов или марковские изменения, ускорение не достигается на медленно меняющихся графах общего вида, даже если ограничения на скорость изменений очень высоки. То есть при постоянных сетевых ограничениях, когда за итерацию изменяется не более постоянного числа ребер в сети, наихудшая зависимость от $\chi $ не может быть улучшена по сравнению с произвольно меняющимися сетями. В частности, мы показываем, что за итерацию достаточно изменить только два ребра.

Мы начнем с определения класса алгоритмов в модели черного ящика, на основе которого мы будем строить нижнюю оценку.

Определение 1. Алгоритм с T локальными итерациями и $K$ коммуникационных раундами, удовлетворяющими следующим свойствам, работающий в модели черного ящика, обозначается $BBP(T,K)$.

Каждый узел $m$ поддерживает локальную память с $\mathcal{M}_{m}^{x}$ и $\mathcal{M}_{m}^{y}$ для $x$- и $y$-переменных, которые инициализируются как $\mathcal{M}_{m}^{x} = \mathcal{M}_{m}^{y} = \{ 0\} $. $\mathcal{M}_{m}^{x}$ и $\mathcal{M}_{m}^{y}$ обновляются следующим образом:

$ \bullet $ Локальные вычисления: Каждый узел $m$ вычисляет и добавляет к своим $\mathcal{M}_{m}^{x}$ и $\mathcal{M}_{m}^{y}$ конечное число точек $x$, $y$, каждая из которых удовлетворяет

$\begin{gathered} x \in {\text{span}}\{ x{\kern 1pt} ',{{\nabla }_{x}}{{f}_{m}}(x{\kern 1pt} '{\kern 1pt} ',y{\kern 1pt} '{\kern 1pt} ')\} , \\ y \in {\text{span}}\{ y{\kern 1pt} ',{{\nabla }_{y}}{{f}_{m}}(x{\kern 1pt} '{\kern 1pt} ',y{\kern 1pt} '{\kern 1pt} ')\} , \\ \end{gathered} $

для данных $x{\kern 1pt} ',x{\kern 1pt} '{\kern 1pt} ' \in \mathcal{M}_{m}^{x}$ и $y{\kern 1pt} ',y{\kern 1pt} '{\kern 1pt} ' \in \mathcal{M}_{m}^{y}$.

$ \bullet $ Коммуникация: $\mathcal{M}_{m}^{x}$ и $\mathcal{M}_{m}^{y}$ обновляются следующим образом

где ${{\mathcal{G}}^{k}} = (\mathcal{V},{{\mathcal{E}}^{k}})$ – текущее состояние сети.

$ \bullet $ Выход: Окончательный глобальный результат в текущий момент времени рассчитывается как:

Чтобы оценить нижнюю оценку распределенной минимаксной проблемы (1), нам нужно предоставить “плохую функцию” и “плохую последовательность графов”, такие, что никакой алгоритм не может решить задачу, используя меньше данного количества шагов. Используя меняющуюся сеть из [11] и целевую функцию из [20], мы можем доказать следующую теорему.

Теорема 5. Для любых $L > \mu > 0$ и любого $\chi \; \geqslant \;1$, существует децентрализованная распределенная седловая задача на $\mathcal{X} \times \mathcal{Y} = {{\mathbb{R}}^{n}} \times {{\mathbb{R}}^{n}}$ (где $n$ достаточно велико) с $x{\kern 1pt} *,y{\kern 1pt} * \ne 0$, последовательностью графов $\{ {{\mathcal{G}}^{k}} = (\mathcal{V},{{\mathcal{E}}^{k}})\} _{{k = 0}}^{\infty }$, где последовательные графов отличаются не более чем двумя ребрами, и последовательность соответствующих матриц коммуникации $\{ {{W}^{k}}\} _{{k = 0}}^{\infty }$ c числом обусловленности $\chi $, такие, что для любого выхода $\hat {x},\;\hat {y}$ после $K$ коммуникационных раундов любой процедуры $BBP(T,K)$ имеется следующая оценка:

Доказательство. Представим граф ${{T}_{{a,b}}}$ из [11]. Этот граф содержит два разбиения: левое и правое, эти разбиения состоят из a и b вершин соответственно. Каждая вершина в разбиении соединена со своим корнем. Эти корни соединены с другой вершиной, называемой центральным корнем.

Рассмотрим сеть с ${\text{|}}\mathcal{V}{\text{|}} = 2d + 3$ узлов ($d\; \geqslant \;2$). Мы выбираем узел в качестве центрального корня и два других узла в качестве левого и правого корней. Центральный корень может со временем меняться, но корни разбиения фиксированы. Также для каждого разбиения выбираем $\left[ {\frac{d}{2}} \right]$ фиксированных вершин и обозначаем их ${{\mathcal{V}}_{1}}$ (левое разбиение) и ${{\mathcal{V}}_{2}}$ (правое разбиение). На каждом коммуникационном раунде $k$, граф ${{\mathcal{G}}^{k}}$ имеет вид ${{T}_{{a,b}}}$, где $a + b = 2d$ и $a,b\; \geqslant \;\left[ {\frac{d}{2}} \right]$.

Коммуникационная сеть меняется поочередно в две фазы. Первая фаза начинается с графа ${{T}_{{2d - \left[ {\frac{d}{2}} \right],\left[ {\frac{d}{2}} \right]}}}$ и заканчивается графом ${{T}_{{\left[ {\frac{d}{2}} \right],2d - \left[ {\frac{d}{2}} \right]}}}$.

На каждой итерации центральный корень перемещается в правое разбиение, центральным корнем становится одна вершина из левого разбиения, но не в ${{\mathcal{V}}_{1}}$. Вторая фаза проходит по тому же принципу, но справа налево.

Мы модифицируем целевую функцию из раздела B.1 в [3] на основе нашего типа графов:

где ${{e}_{1}} = (1,0, \ldots ,0)$ и

Рассмотрим задачу с глобальной целевой функцией:

Мы оцениваем количество коммуникационных раундов, необходимых для получения нового ненулевого элемента в локальной памяти, используя следующую лемму.

Лемма 2. Пусть задача (1) решается некоторым алгоритмом $BBP(T,K)$. Тогда после K коммуникаций не более $\left\lfloor {\frac{K}{d}} \right\rfloor $ первых координат выхода алгоритма могут быть ненулевыми, в то время как оставшиеся $n - \left\lfloor {\frac{K}{d}} \right\rfloor $ координат строго равны нулю.

Доказательство. Заметим, что новая ненулевая координата появляется, только когда информация доходит от вершин ${{\mathcal{V}}_{1}}$ до вершин ${{\mathcal{V}}_{2}}$ и происходит градиентный шаг на одной из вершин ${{\mathcal{V}}_{2}}$ (или в обратном направлении). После каждого такого распространения информации добавляется не более одной координаты.

Между двумя последовательными коммуникационными раундами только узлы из ${{\mathcal{V}}_{1}}$ и ${{\mathcal{V}}_{2}}$ могут добавлять в свою локальную память новую ненулевую координату, но в этом интервале два узла из ${{\mathcal{V}}_{1}}$ и ${{\mathcal{V}}_{2}}$ не могут выполнять одновременно. Более того, между двумя раундами связи можно добавить не более одной новой ненулевой координаты (подробнее см. [3]).

Следовательно, нам постоянно приходится передавать информацию из множества узлов ${{\mathcal{V}}_{1}}$ в ${{\mathcal{V}}_{2}}$ и обратно, чтобы получить новые ненулевые координаты. Для каждой новой ненулевой координаты нам нужно хотя бы одно локальное вычисление. Таким образом, требуется $T > K$. Из [11] мы знаем, что каждая передача требуется как минимум $d$ коммуникационных раундов. Таким образом, после K коммуникационных раундов не более первых $\left\lfloor {\frac{K}{d}} \right\rfloor $ координат выхода алгоритма могут быть ненулевыми.

Следующие вспомогательные леммы позволяют получить нижние оценки сложности.

Лемма 3 (Лемма 4 из [3].) Пусть $\alpha = \frac{{4{{\mu }^{2}}}}{{{{L}^{2}}}}$ и q = = $\frac{1}{2}(2 + \alpha - \sqrt {{{\alpha }^{2}} + 4\alpha } ) \in (0;1)$ – меньший корень уравнения ${{q}^{2}} - (2 + \alpha )q + 1 = 0$. Также введем $\bar {y}{\kern 1pt} *$

Тогда ошибка между аппроксимацией и реальным решением задачи (7) может быть ограничена как

Лемма 4 (Лемма 5 из [3]). Рассмотрим распределенную седловую задачу вида (6), (7) с последовательностью графов $\{ {{\mathcal{G}}_{k}} = (\mathcal{V},{{\mathcal{E}}_{k}})\} _{{k = 0}}^{\infty }$ и соответствующей последовательностью матриц коммуникации $\{ W({{\mathcal{G}}_{k}})\} _{{k = 0}}^{\infty }$. Для всех пар $T,K(T > K)$ можно показать, что размер задачи $n\, \geqslant \,{\text{max}}\left\{ {2{\text{lo}}{{{\text{g}}}_{q}}\left( {\frac{\alpha }{{4\sqrt 2 }}} \right),2K} \right\}$, где $\alpha = \frac{{4{{\mu }^{2}}}}{{{{L}^{2}}}}$ и q = $\frac{1}{2}(2 + \alpha - \sqrt {{{\alpha }^{2}} + 4\alpha } ) \in (0;1)$. Тогда для всякой пары $\hat {x},\;\hat {y}$, выданной некоторым алгоритмом ${\mathbf{BBP}}(T,K)$ после K коммуникационных раундов и $T$ локальных вычислений, выполняется

Используя результаты доказательства из утверждения 3.6 из [20], получаем

Каждому графу в нашей последовательности сопоставим взвешенный лапласиан из леммы 8 в [11], так что $\chi \;\leqslant \;8d$. Имеем

Далее, получаем

Таким образом,

Следствие 5.1. Для достижения точности $\varepsilon $ в условиях теоремы 5, количество коммуникационных раундов ограничено снизу величиной

а количество локальных вызовов оракула ограничено снизу величиной

5. ЗАКЛЮЧЕНИЕ

В статье изучались децентрализованные минимаксные задачи на медленно меняющихся сетях. Мы показали, что если изменения графа враждебны и меняется константное число ребер на каждой итерации, то нижние оценки сложности совпадают с произвольными переменными сетями. Более того, мы показали, что для определенного класса переменных графов – сетей со связным остовом и сетей с марковскими изменениями – возможно ускорение коммуникационной процедуры. Были предложены соответствующие алгоритмы для седловых задач для данных двух классов сетей.

ИСТОЧНИК ФИНАНСИРОВАНИЯ

Исследование выполнено за счет гранта Российского научного фонда (проект № 23-11-00229), https://rscf.ru/project/23-11-00229/.